原子操作

操作の原子性が正確にどのように達成されるかが興味深いものになりました。 誰が気にします-猫へようこそ。


アトミック操作 -全体として実行される操作、またはまったく実行されない操作。 つまり、実行中の操作であり、この操作によって読み取られた/変更されたデータは、別の操作によって変更することはできません。 操作がアトミックであることをプロセッサーに伝える特別なアセンブラー命令があります。 アトミック性を実現するために使用できるコマンドには、ロードリンクおよびストア条件付き（ LL / SC ）、比較交換（ CAS ）などのいくつかのタイプがあります。

1. LL / SC

LL / SCコマンドの例：
ldl_l / stl_cおよびldq_l / stq_c（Alpha）、lwarx / stwcx（PowerPC）、ll / sc（MIPS）、およびldrex / strex（ARMバージョン6以降）。
最初にオペランドの現在の値をレジスタまたは他の制御された場所にロードするため、コマンドはペアで与えられます。 一緒に、それらの間のすべてのコマンドが、LLを使用してロードされたオペランドの同じバージョンで動作することを保証します。 たとえば、lwarx / stwcx（PowerPC）のペアを使用します。

void atomic_incr(int * operand, int incr) { asm volatile ( "loop:\n\t" /* repeat until this succeeds */ "lwarx 6,0,%0\n\t" /* reserve the operand */ "add 6,6,%1\n\t" /* add incr to it */ "stwcx. 6,0,%0\n\t" /* put the sum back, and release it */ "bne- loop" /* start-over on failure */ : : "r" (operand), "r" (incr) : "r6" ); } 

コードはここから取得されます。
オペランドからのデータは6番目のレジスタにロードされ、それ（オペランド）は予約されます。 次に、6番目のレジスタで、オペランドとincrの合計を取得します。 最後に、受け取った金額をレジスタからオペランドにアンロードして解放します。 オペランドの予約とリリースの間隔で、その値が現在の操作以外のどこかで変更される場合（オペランドに既に格納されている同じ値が割り当てられている場合でも）、エラーが発生します。 これにより、5行目がチェックされ、エラーが発生した場合に操作が再開されます。

2. CAS

操作の原理は単純です-オペランドに格納されている値を調べます。 それが私たちが期待するものである場合、新しいものに変更します。
アルゴリズム：

 int compare_and_swap (int* reg, int oldval, int newval) { int old_reg_val = *reg; if (old_reg_val == oldval) *reg = newval; return old_reg_val; } 

CAS拡張-二重比較およびスワップ（ CAS2 ）。 それぞれ1つの変数の代わりに、2つの独立した変数へのポインターがそれぞれ与えられ、それぞれの変数に2つの期待値と2つの新しい値があります。
しかし、このチームのグループは、状況が考えられるため、LL / SCよりも「弱」です。
初期条件：compare_and_swap（reg、5、7）および* reg = 5;
1）int old_reg_val = * reg; （old_reg_val = 5）
2）別の操作では* reg = 42; funny_stuff; * reg = 5;
3）if（old_reg_val == oldval）-ステートメントはtrueですが、変数の値に2つの変更があります。 つまり、変更が発生しましたが、私たちのオペレーションはそれを認識していません。 この状況はABA問題と呼ばれます 。
この問題には多くの回避策があります。 Double-Word Compare-And-Swapを使用した方法は興味深いものでした（Double Compare And Swapと混同されることがよくあります）。
例：

 /* double-compare-and-swap: atomically sets the two-word data at address @mem * to the two-word value of @new if value at @mem * equals @old * @mem: pointer to value * @old: old value * @new: new value * * returns: 0 on failure, non-zero on success */ static inline char DWCAS(volatile DWORD *mem, DWORD old, DWORD new) { char r = 0; unsigned long old_h = old >> SHIFT, old_l = old; unsigned long new_h = new >> SHIFT, new_l = new; __asm__ __volatile__("lock; " CMPXCHGxB " (%6);" "setz %7; " : "=a" (old_l), "=d" (old_h) : "0" (old_l), "1" (old_h), "b" (new_l), "c" (new_h), "r" (mem), "m" (r) : "cc", "memory"); return r; } 

コードはここから取得されます。
接頭辞「lock;」は、メモリアクセスバスがそれに続くコマンドでのみ使用できることを意味します。
送信されたワードには、必要な値を持つメモリへのポインタと、各操作で変化するABA番号が含まれています（これは特許の 1つで見ました）。

3.単純なアトミック操作。

これは通常、加算または増分です。
コマンドの例：addl（i386）、xaddl（x86）。
ウィキペディアからのアトミック追加の実装は次のとおりです。

 void atomic_add(int * operand, int incr) { asm volatile ( "lock; xaddl %1, (%0)\n" // add incr to operand : // no output : "r" (operand), "r" (incr) ); } 

一部のアーキテクチャでは、「lock;」プレフィックスは不要です。 例は、Itaniumで増分しています（ ここから取得）。

 void atomic_oneup(int * operand) { uint64_t res; // this MUST be 64 bits asm volatile ( "fetchadd4.rel %0=%1,%2" : "=r" (res) : "m" (*operand), "i" (1) : "memory" ); } 

ちなみに、C ++のインクリメント、デクリメント、+ =、-=はアトミックです（少なくともx86およびx86_64では）。 接頭辞「lock;」はないため、原子性もありません。 原子操作はC ++ 11で登場しました。

 int a =0; ++a; 

にコンパイルする

 c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp) 83 45 fc 01 addl $0x1,-0x4(%rbp) 

デクリメントについてはサブルになります。

おわりに

Q：これはすべての学生に知られています！ なぜそれについて書くのですか？
A：どのように機能するのかと思っていました。 ある種のロックが存在すると想像しただけです。 私はそれが他の誰かにとって興味深いものであったことを願っています。

Q：この記事には多くのエラーと不正確さがあります。
A：書いて、喜んで修正します。

Q：なに？ すでに結論ですか？ 記事自体はどこにありますか？ MSI 、 Cache Coherence、 ％else_with_smart_words％はどこにありますか？
A：深く掘り下げたわけではありません。 これらのトピックを知っている人々がこれについて書くことを望みます。

UPD：修正してくれたlesha_penguinとTheShadeに感謝します。