[운영체제/OS] 동기화 이슈 처리하기 - (1)

💡 0. 문제 상황

// Producer = 데이터를 추가하는 역할(counter 증가)
register A := counter; // load 
register A := registerA + 1; // add 
counter := registerA; // store

// Consumer = 데이터를 빼는(소모하는) 역할(counter 감소)  
registerB := counter; // load  
reigsterB := registerB - 1; // sub  
counter := registerB; // store

위 코드에서 counter라는 변수가 공유 변수라면 Register A, B가 동시에 counter 변수를 사용했을 때 결과값이 모호해지는 현상이 발생했습니다.

 

그리고, 이를 해결하기 위해 이전 시간에 Critical Section과 Lock에 대해 잠깐 이야기를 했었는데요.

 

이번 시간에는 이 내용을 조금 더 발전시켜서 이야기해보려고 합니다.

 

---

 

📒 1. 저차원 해결책들(Low-level synchronization primitve(Spinlocks🥲))

1) 소프트웨어(코드)로 해결해보기 - Software-only solution

Software-only solution은 아래처럼 소프트웨어만을 이용해서 Lock을 구현하는 방법입니다. 쉽게 말해 코드를 짜서 Critical Section을 관리하겠다는 것이죠.

[1] repeat: 
    // turn은 공유 변수로 turn = i라는 것은 Process i의 차례라는 뜻이다. 
    while turn != i do no-ops; // 내 차례가 아니면 spinlock 
        critical section // 내 차례면 CS 진입 
    turn := j; // 나가면서 다른 녀석에게 turn 넘겨줌 
        remainder section 
    until false;`

위 코드의 원리는 간단합니다. turn이라는 변수는 어떤 프로세스/쓰레드에게 자원이 할당될 것인지를 알려주는 변수입니다. turn변수가 자신을 가리키기 전까지는 Critical Section에 진입하지 못하며 Critical Section에서 나올 때는 turn 변수를 다른 프로세스/쓰레드에게 할당하여 Critical Section에 진입할 수 있게 하죠.

 

하지만, 이 방법에서는 여러가지 문제점이 있습니다. 우선 자신의 turn이 아닌 녀석들은 계속 while문에 갇혀서 아무것도 하지 못하는 Spinlock 현상에 빠지게 됩니다. 또한 Critical Section안에서 자원을 사용하던 프로세스/쓰레드가 Kill되면 다른 프로세스에게 turn을 넘겨주지 않기 때문에 자원을 그 누구도 쓰지 못하여 Progress 조건이 깨지게 됩니다.

 

* Critical Section을 관리하기 위한 세 가지 조건에 대해 모르시는 분은 꼭 이전 포스팅을 참고해주세요.

[운영체제/OS] 동기화 이슈의 원인과 임계 구역(Critical Section)의 개념

 

그렇다면 위 방법에서 조금 더 발전된 두 번째 방법을 보겠습니다.

[2] repeat: 
    flag[i] := true;             // 맨 처음에 false로 초기화되어 있던 걸 Process i가 들어가겠다고 선언 
    while flag[j] do no-ops;     
        critical section 
    flag[i] := false; 
        remainder section 
    until false;`

이 방법에서는 flag라는 boolean type의 변수를 사용합니다. flag[i]가 true라는 것은 i번째 프로세스/쓰레드가 Critical Section에 들어가겠다는 것을 의미합니다. 자기 자신이 말하는 겁니다.

 

맨 처음에 flag값들은 모두 false로 선언되어 있는 상황에서 어떤 프로세스/쓰레드 i가 flag[i]를 true로 바꾸고 Critical Section에 진입합니다. 그러면 현재 Critical Section에는 i라는 녀석이 있겠죠. 이 때, 다른 프로세스/쓰레드 j가 Critical Section에 진입하겠다고 flag[j]를 true로 바꿉니다. 하지만 flag[i] = true가 이미 있는 상황, 즉, Critical Section안에는 i가 있기 때문에 j는 spinlock에 빠지게 됩니다. 

 

하지만 맨 처음에 순간적으로 i, j라는 두 녀석이 자신의 flag값을 true로 바꿨다고 해봅시다(flag 변수는 지금 공유 변수니까요). 그러면 두 녀석 모두 다른 녀석의 flag값이 true인걸 보고는 Critical Section에 진입하지 않고 Spinlock에 빠지게 됩니다. 즉, Critical Section안의 자원은 누구에게도 할당되지 못하는 상황이죠. Progress 조건이 깨지게 됩니다.

 

---

지금까지 위의 두 방식이 결국 Critical Section을 제대로 관리하지 못한다는 것을 확인했습니다. 그러면 이제 Peterson's Algorithm에 대해 이야기해보겠습니다. 문제점이 있는 녀석들을 소개하고 Peterson's Algorithm을 소개하는 것을 보면, 이 알고리즘은 위 문제들을 해결하리라는 기대감이 있겠죠...?

[3] Peterson's algorithm
// Process i
repeat
    // 공유변수로 flag와 turn을 동시에 사용 
    // flag == true는 들어가고 싶다는 뜻이고 turn은 실제로 누구 차례인지를 나타냄
    flag[i] := true;        // Process i가 와서 "나 들어가고 싶다고 선언"
    turn := j;              // turn을 i가 아니라 j에게 줘버림. 그러면 늦게 온 j는 turn을 i에게 주겠지.
    while(flag[j] and turn=j) do no-ops;    // 내 차례가 아니거나 들어가고 싶지 않은 상태면 spinlock
        ...
        Critical Section
        ...
    flag[i] = false;        // 볼 일 다봤으니까 이제 들어가고 싶지 않다고 선언
        remainder section
until false;

위의 Peterson's algorithm은 Critical section을 처리하기 위해 필요한 3가지 요건(Mutual exclusion, Progress, bounded waiting)을 모두 충족시킵니다.

 

그렇다면 어떻게 모든 조건을 충족시킬 수 있는지 자세히 생각해보겠습니다.

flag[i] = true;
// 프로세스 i가 먼저 Critical Section에 접근하기 위해 flag[i]를 true로 설정하여 신호를 보낸다.

turn = j;
// 프로세스 i는 내가 먼저 들어간다고 선언하고 조금 늦게 도착한 j에게 turn을 돌려준다.
// 여기까지 진행된 상태라면 j 입장에서는 flag[j] = true, turn =i일 것이다.
// 그러면 프로세스 i가 j 프로세스로 차례를 넘겨주자마자 아래의 while문을 수행하고 Critical Section에 진입할 수 있다.

while(flag[j] && turn == j);
// Critical section에 들어가기 위해서는 당연히 내 차례여야 한다.
// 따라서 내 차례이거나(turn = i), j가 Critical Section에 진입하고 싶지 않다면(flag[j] = false)
// Spinlock을 빠져나와서 Critical section에 진입할 수 있게 된다.
// 이렇게 turn과 flag 변수를 이용해서 동시 접근을 막는 것이다.

이렇게 하면 내 순서가 아니면 접근을 할 수 없게 되고 / 내 순서가 아니더라도 남들이 아무도 안 쓰면 쓸 수 있게 되고 / i 입장에서 turn은 j가 바꿔주는 것이기 때문에 critical section을 무한정 쓸 수는 없게 됩니다. 남이 도와줘야 하기 때문이죠.

 

따라서 Peterson algorithm은 software-only solution에서 동기화 문제를 해결하는 방법이 됩니다.

 

 

✅  2) 하드웨어의 도움을 받아서 해결해보기(Hardware Atomic solution)

Hardware Atomic solution은 위처럼 소프트웨어 코드만으로는 동기화 문제를 해결하기에 너무 느리고 복잡해서 고안된 방식입니다.

 

이 방법은 Atomic instruction을 통해서 동기화 문제를 해결하고자 하는 것인데, Atomic instruction에는 크게 Test-and-Set instruction과 Swap(or xchg) instruction이 있습니다.

• 1) Test-and-Set
  • Test-and-Set instruction은 공유 데이터로 처음에 false로 초기화된 var lock을 사용합니다. 동작 방식은 간단한데, lock 변수가 true이면 no-ops 상태여야 하고, lock 변수가 false일 때만 Critical Section에 진입할 수 있게 하는 것입니다. 그리고 다시 나갈 때는 lock을 false로 바꾸고 나갑니다. 하지만 내가 들어가서 그냥 무한대로 Critical section을 쓸 수 있기 때문에 bounded waiting조건은 충족되지 않습니다.
• 2) Swap(xchg)
  • Swap 역시 test-and-set방법과 마찬가지로 bounded waiting 문제는 해결되지 않습니다. Swap 역시 마찬가지로 최초에 false로 초기화된 lock 변수를 가지고 있습니다. 프로세스가 Critical section에 진입하려고 하면 key = true;로 바꾼 후에 Swap(lock, key)를 수행합니다. 그렇게 되면 lock이 true가 되고 key는 false가 된 후 critical section에 진입하게 되고, 나갈 때는 lock을 다시 false로 만들어주면 되죠.

Test-and Set Instruction과 Swap instruction을 간단한 코드로 보면 아래와 같습니다.

///////// Test-and-Set
repeat
    while Test-and-Set(lock) do no-ops;
        Critical section
    lock = false;
        remainder section
until false;

//////// Swap 
do{ /* lock is initially false */
    key = true;
    while(key == true) Swap(lock, key);
        critical section
    lock = false;
        remainder section
}

---

✅  3) Software Solution, Hardware Solution 방식의 문제점

두 방식 모두 Spinning lock이라는 말처럼 프로세스나 쓰레드가 Critical Section에 접근하지 못하는 상황에서는 계속 while loop를 돌고 있기 때문에 비효율을 낳게 됩니다.

 

이렇게 되면 무한루프를 돌고 있는 쓰레드는 다른 쓰레드에게 CPU 할당을 넘겨주지 않아서 스위칭이 잘 일어나지 못하게 되죠. 그리고 Critical section에서 처리해야 할 작업이 많으면 많을수록 Spinning lock의 시간이 길어지게 됩니다.

---

 

이번 시간에는 Software only solution의 세 가지 방법과 Hardware atomic solution에 대해 공부해봤는데요. Peterson's Algorithm같은 경우에는 Critical Section을 관리하기 위한(동기화 이슈를 해결하기 위한) 세 가지 조건을 모두 만족했다는 데서 의미가 있는 알고리즘이었습니다.

 

하지만, 이 모든 알고리즘은 Spinlock이라는 문제점이 존재한다는 것을 봤습니다.

 

다음 시간에는 High-level Synchronization 기법인 세마포어(Semaphore)와 모니터(Monitor)에 대해 공부해보겠습니다.

 

감사합니다.