운영체제론[11]: 스레드 동기화 (하드웨어 명령어)

while(test_and_set(&lock));
// CS
lock = false;

test_and_set : 인자로 들어온 값을 true로 변경하고, 변경 전 target의 값을 반환한다.

 

스핀락을 구현하기 위해, 인자로 lock이 들어간다고 할 때, 이미 누군가 임계구역에 들어가 있어서 lock이 사용중이라면 true를 반환하므로 true를 반환하는 동안에는 임계구역에 접근을 막는다. 만약 false를 반환했다면 임계구역에 들어가 있는 스레드가 없는 것이므로, 자신이 임계구역에 들어간다. 임계구역에서 벗어날 때는 lock을 false로 바꾼다.

 

 

 

while(compare_and_swap(&lock, 0, 1) != 0);
// CS
lock = false;

compare_and_swap : 첫 번째 인자로 들어온 값이 두 번째 인자와 같으면 세 번째 인자로 바꾸고, 첫 번째 인자의 원래 값을 반환

 

위 코드에서 작동 방법은, test_and_set과 비슷하다. lock이 0과 같으면 1로 바꾸고 lock의 원래 값인 0을 반환한다. 0이 아니라면 아무 작업도 하지 않고 lock(0)을 반환한다.

 

 

expected = false;
while(!compare_and_exchange(&lock, &expected, 1)) expected = false;
// CS
lock = false;

compare_and_exchange : lock과 expected과 같으면 lock을 세 번째 인자인 1로 바꾸고 true를 반환하고, 다르면 expected를 lock으로 바꾸고 false 반환한다.

 

이 또한 test_and_set과 비슷하다. lock이 true라면 expected가 true가 되므로 다시 false로 바꿔준다.

compare_and_exchange_weak와 strong이 있는데, weak의 경우 object와 expected가 같아도 false를 주는 거짓 부정이 가능하다.

 

 

 

waiting[i] = true;
key = 1;
while(waiting[i] && key == 1) key = compare_and_swap(&lock,0,1);
waiting[i] = false;

// CS

j = (i+1) % n;
while((j!=i) && !waiting[j]) j = (j+1) % n;
if(j == i) lock = false;
else waiting[j] = false;

CAS를 사용해서 CS에 순차적으로 들어가는 알고리즘이다.

i는 본인 스레드의 번호이고, waiting[i]는 i번 스레드가 CS에 들어가기를 대기중이라는 것을 뜻한다.

key는 lock의 현재 값과 같다. (compare_and_swap에 의하여)

따라서, 본인이 대기 상태이면서, lock까지 걸려있다면 누가 내 waiting을 풀어주거나 lock이 풀릴 때까지 대기한다.

(단, lock이 풀리는 경우는 첫 번째 진입이여서 lock이 애초에 풀려있는 경우만 해당한다)

 

임계구역을 빠져나올 때는, 실행중인 n개의 스레드를 순회하여 waiting이 있는지 검사한다.

waiting이 있다면 그 waiting을 풀어주고, 없다면 lock을 풀어준다.