クリティカルセクション

2023年2月7日 20:47

アトミック操作

あるデータに対する操作で、
操作が完了するまで
途中の状態を他（のプロセス、スレッド）から干渉できないような、割り込み不可能な操作。
システムの他の部分から見て、一つの操作に見えるもの。

ＣＰＵなど、ハード的に実装され、保障されているものもあれば、
ソフト的に、アルゴリズムで実装されるものもある。
ただし、ソフト的に、アルゴリズム的に実装する場合はアトミックな操作の組み合わせによって構築される。

アトミックな命令

テスト・アンド・セット（Test-and-Set、TAS）

値（主に1）をセットする。
同時にテストも完了する。これは例えば成否の２値。0か1。true/falseを返す行為。
２つの動作、役割を同時に果たすことが重要。

例えば何らかのフラグを確かめてからフラグを立て、他が入ってこれないようにしてからクリティカルセクションに入りたいとする。
しかし複数のプロセスやスレッドが入り乱れている場合、フラグを確かめてからフラグを立てるまでの間に割り込まれて破綻する可能性がある。
ゆえにフラグを確かめることとフラグを立てることは、他のプロセスやスレッドからみて同時に実行される必要がある。

ハード的に実装されるアトミック操作。
テスト・アンド・セット命令が存在しない場合、アトミックなRead–modify–write、またはコンペア・アンド・スワップを用いてテスト・アンド・セット命令を構築することができる。

また、スピンロックを構築したりできる。
スピンロックの項を参照。

In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. The caller can then "test" the result to see if the state was changed by the call. If multiple processes may access the same memory location, and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process's test-and-set is finished. A central processing unit (CPU) may use a test-and-set instruction offered by another electronic component, such as dual-port RAM; a CPU itself may also offer a test-and-set instruction.

コンピュータサイエンスにおいて、テスト＆セット命令は、あるメモリ位置に1を書き込み（セット）、その古い値を単一のアトミック（つまり割り込みできない）操作として返すために使用する命令です。呼び出し側はその結果を「テスト」して、呼び出しによって状態が変更されたかどうかを確認することができます。複数のプロセスが同じメモリ位置にアクセスでき、あるプロセスが現在テストアンドセットを実行している場合、最初のプロセスのテストアンドセットが終了するまで、他のプロセスは別のテストアンドセットを開始することはできません。中央演算処理装置（CPU）は、デュアルポートRAMなどの他の電子部品が提供するテスト・アンド・セット命令を使用することができ、CPU自体もテスト・アンド・セット命令を提供することができます。

テスト・アンド・セット : gccの場合

フェッチ・アンド・アッド（Fetch-and-Add）

1を足す。

ハード的に実装されるアトミック操作。
メモリ位置の値をインクリメントする。

コンペア・アンド・スワップ（Compare-and-Swap、CAS）

あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納する。

Read–modify–write

In computer science, read–modify–write is a class of atomic operations (such as test-and-set, fetch-and-add, and compare-and-swap) that both read a memory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent race conditions in multi-threaded applications. Typically they are used to implement mutexes or semaphores. These atomic operations are also heavily used in non-blocking synchronization.

コンピュータサイエンスでは、メモリ位置の読み取りと新しい値の書き込みを同時に行うアトミック操作（テスト・アンド・セット、フェッチ・アンド・アッド、コンペア・アンド・スワップなど）の一種であり、完全に新しい値または以前の値の関数のどちらかを使用します。これらの操作は、マルチスレッド・アプリケーションにおける競合状態を防止します。一般的には、ミューテックスやセマフォを実装するために使用されます。これらのアトミック操作は、ノンブロッキング同期にも多用されます。

ロック

ロック、またはミューテックス。
すなわち２値セマフォ。

セマフォ

セマフォとは、クリティカルセクションの問題を回避するために用いられる変数または抽象データ型のことである。セマフォは同期プリミティブの一種である。セマフォは、プログラマが定義した条件に応じて変化する（たとえば、インクリメント、デクリメント、トグル）平凡な変数である。

セマフォのうち、資源の数を任意に設定できるものをカウンティングセマフォ、0と1（またはロック/アンロック、使用不可/使用可能）に限定したものをバイナリセマフォと呼び、ロックの実装に利用されている。バリナリセマフォはミューテックス。

セマフォには1つの変数と2つの操作がある。
変数はＳ。
操作はＰとＶ。語源はダイクストラ先生のオランダ語。
Ｐは各種ＡＰＩやライブラリではwaitなんちゃら関数である。
Vはsignal, postだのcloseだのreleaseだのなんちゃら関数である。

Ｓの値は現在利用可能なリソースの個数。
この値が0なら現在使用可能なリソースは存在しない。
この値の最大値が1ならミューテックスである。

Ｐ(wait)はまずＳをデクリメントする。
$${0\leq S}$$ならば処理を継続。
$${S<0}$$ならばリソースが利用可能になるまでブロック状態とする。

V(signal)は$${S\leq 0}$$ならば、ブロック状態のプロセス、スレッドを待機状態にする。
Ｓをインクリメントする。
インクリメントする前からＳが負値なら誰か待ってるやつがおるということである。

また、
待機状態とはwhileをぐるぐる回している状態であり、
ブロック状態とはそれすらしないでキューに入れておく状態である。

P(S);
//クリティカルセクション
V(S);

セマフォ : Win32で使う場合。

セマフォ : POSIXで使う場合。

ただしChatGPTが返してきたもの。試してない。

#include <semaphore.h> 
#include <pthread.h> 
sem_t sem; 
void *thread_func(void *arg) 
{ 
    // Wait for the semaphore to be released 
    sem_wait(&sem); 
    // Access the shared resource 
    // ... 
    // Release the semaphore 
    sem_post(&sem); 
    return NULL; 
} 
int main(void) 
{ 
    // Initialize the semaphore with a value of 1 (representing the number of available resources) 
    sem_init(&sem, 0, 1); 
    pthread_t t1, t2; 
    pthread_create(&t1, NULL, thread_func, NULL); 
    pthread_create(&t2, NULL, thread_func, NULL); 
    pthread_join(t1, NULL); 
    pthread_join(t2, NULL); 
    sem_destroy(&sem); 
    return 0; 
}

セマフォ : Linuxで使われてるのを学ぶ場合。

多分プロセス間通信。

セマフォ構造体

/* One semaphore structure for each semaphore in the system. */ 
struct sem { 
	int	semval;		/* current value */ 
	/* 
	 * PID of the process that last modified the semaphore. For 
	 * Linux, specifically these are: 
	 *  - semop 
	 *  - semctl, via SETVAL and SETALL. 
	 *  - at task exit when performing undo adjustments (see exit_sem). 
	 */ 
	struct pid *sempid; 
	spinlock_t	lock;	/* spinlock for fine-grained semtimedop */ 
	struct list_head pending_alter; /* pending single-sop operations */ 
					/* that alter the semaphore */ 
	struct list_head pending_const; /* pending single-sop operations */ 
					/* that do not alter the semaphore*/ 
	time64_t	 sem_otime;	/* candidate for sem_otime */ 
} ____cacheline_aligned_in_smp;

ミューテックス

セマフォ変数が１のセマフォ。バイナリセマフォ。

ビジーウェイト

条件を満たすまで何もしない手法、機構。
条件は例えば時間、入力、ロック。

NOPを用いてwhileでループすればスピンロック。
スピンロックはビジーウェイトの具体的な手法の一つ。

NOP

NOP（ノップ）あるいは NOOP（ノープ）
no operation

なにもしないという命令。

スピンロック

test_and_setなどを用いて実現される。

test_and_setの疑似コード。
このような挙動がアトミックなまま達成されなければならない。

#define LOCKED 1

int test_and_set(int* lockPtr) {
    int oldValue;
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    return oldValue;
}

スピンロックの疑似的なC実装

volatile int lock = 0;

void critical() {
    while (test_and_set(&lock) == 1);  
    
    //クリティカルセクション

    lock = 0;  //クリティカルセクションを抜けたらロックを解除する。
}

lock値は全てのプロセス、スレッドからアクセスできる。
volatileがないとコンパイラが勝手なことするが、あっても動作の保証はされない。

test_and_setはlock値を1にしてロックする。
ロックを取得したプロセス、スレッドがクリティカルセクションを通過し、ロックを解錠(lock=0)しない限り、
他のプロセス、スレッドはロックを取得できない（この場合、test_and_setが0を返さない）し、クリティカルセクションには進入できない。

test_and_setの戻り値（oldValue）が1ならば他がロックしているということ。その場合、while (test_and_set(&lock) == 1);はループし続ける。

lock==0ならば
test_and_setは0を返し、lockは1となる。
この場合、whileループを抜けてクリティカルセクションに入ることができる。
0を返してるのがテストにあたり、
lockが1となるのがセットにあたる。

lock==1ならば
test_and_setは1を返し、lockは1となる。
この場合、whileループは抜けることができない。
1を返してるのがテストにあたり、
lockが1となるのがセットにあたる。

つまり最初にlockを1にしたプロセス、スレッドが、
責任を持ってlockを0にしない限り、
他のプロセス、スレッドはクリティカルセクションに進入できない。
クリティカルセクションに進入したプロセス、スレッドがlockを0にし忘れると、無限ループに陥る。

テストとセットが１回の動作で実行され、アルゴリズムに組み込まれることが重要である。

テストとセットが分離している場合、以下のようになる。
lockが0ならwhileを抜け、lockに1をセットして他のプロセス、スレッドがクリティカルセクションに入れないようにする。
しかしこの場合、while(lock==1);とlock=1;の間で割りこまれる可能性がある。

while(lock==1);
lock=1;
//クリティカルセクション
lock=0;

; Intel syntax

locked:                      ; The lock variable. 1 = locked, 0 = unlocked.
     dd      0

spin_lock:
     mov     eax, 1          ; Set the EAX register to 1.
     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
                             ; This will always store 1 to the lock, leaving
                             ;  the previous value in the EAX register.
     test    eax, eax        ; Test EAX with itself. Among other things, this will
                             ;  set the processor's Zero Flag if EAX is 0.
                             ; If EAX is 0, then the lock was unlocked and
                             ;  we just locked it.
                             ; Otherwise, EAX is 1 and we didn't acquire the lock.
     jnz     spin_lock       ; Jump back to the MOV instruction if the Zero Flag is
                             ;  not set; the lock was previously locked, and so
                             ; we need to spin until it becomes unlocked.
     ret                     ; The lock has been acquired, return to the calling
                             ;  function.

spin_unlock:
     xor     eax, eax        ; Set the EAX register to 0.
     xchg    eax, [locked]   ; Atomically swap the EAX register with
                             ;  the lock variable.
     ret                     ; The lock has been released.

xchg命令
２つのオペランドをアトミックに交換、スワップする。
test命令
２つのオペランドのANDをとる。
結果がゼロならゼロフラグ(ZF)を立てる。
jnz命令
ゼロフラグがゼロならジャンプ。
ゼロフラグは演算結果がゼロの時に立つフラグ。
ゼロフラグが1なら演算結果はゼロ。
ゼロフラグが0なら演算結果はゼロじゃない(not zero)。

この記事が気に入ったらサポートをしてみませんか？