[운영체제(OS)] 동기화(Synchronization) 와 임계구역 문제(Critical Section Problem) - 2

0. 들어가면서

 

저번 시간에는 운영체제에서의 동기화가 무엇인지 살펴보았고, 임계 구역 문제가 무엇인지 알아봤습니다.

이번 시간에는 임계구역을 어떻게 관리하는지, 동기화 문제를 어떻게 해결하는지 방법들을 알아보려고 합니다.

 

 

1. 임계구역 문제 SW 해결 방법들(Software-only-solution)

 

1 - 1. 먼저 프로세스가 두 개일 때의 해결 방법에 대해서 알아보겠습니다.

 

//Process P1
do {
    while(turn!=i);
    	//critical section
    turn = j
       	//remainder section
}

 

위의 코드를 살펴보겠습니다. turn이라는 공유 변수는 어떤 프로세스/쓰레드에 자원이 할당될지 넣어놓는 변수입니다.

turn 변수가 자기 자신인 i를 가리키기 전까지 critical section에 들어갈 수 없습니다. 또한 critical section에서 빠져나올 때 trun 변수에 다른 프로세스/쓰레드인 j를 할당해줌으로써 critical section에 들어갈 수 있게 합니다.

 

하지만 이 방법에는 문제가 있죠. 자신의 turn이 아닌 여러 프로세스/쓰레드들은 while문에 갇혀서 아무것도 하지 못하고 빙빙 도는 Spinlock현상에 빠지게 됩니다. 그리고 while 문에서 kill 당하는 프로세스가 있다면 다른 프로세스 j 한테 turn을 넘겨주지 못하기 때문에 다음 자원을 아무도 못쓰게 됩니다. 이 과정에서 critical section을 관리하기 위한 조건중 3번, Progress 조건을 충족시키지 못하게 되죠.

 

(critical section을 관리하기 위한 조건을 모르시는 분은 아래 포스팅을 꼭 참고해주세요!)

[운영체제(OS)] 동기화(Synchronization) 와 임계구역(Critical Section) 문제 - 1

 

다음 방법을 알아보겠습니다.

 

do {
    flag[i] = true;
	while(flag[j]);
    	//critical section
    flag[i] = false;
       	//remainder section
}while(1)

 

위의 코드를 살펴보겠습니다. 먼저 공유 변수로 boolean flag [2]를  false로 초기화시켜줍니다. 여기서 flag [i] = true라는 코드는 i 번째 프로세스/쓰레드가 critical section에 들어가겠다는 것을 의미합니다. 자기 자신이 '나 여기 들어간다!'라고 말하는 것이죠.

 

flag를 모두 false로 초기화시킨 상황에서 프로세스/쓰레드 i가 flag [i]를 true로 바꾸고 critical section에 들어갑니다. 그럼 현재 critical section에는 i 프로세스/쓰레드가 있을 겁니다. 이 때 다른 프로세스/쓰레드 j가 flag[j]를 true로 바꿨다고 가정하겠습니다. 이미 flag[i] = true가 있는 상황에서 critical section에는 i가 있기 때문에 j는 Spinlock에 빠지게 됩니다.

 

그럼 이제 맨 처음 동시에 i, j 프로세스/쓰레드가 자신의 flag값을 true로 바꿨다고 가정해볼까요?

 

그렇다면 서로의 flag값이 true인 것을 보고 둘 다 critical section에 들어가지 않고 critical section에는 어떠한 프로세스/쓰레드도 들어가지 못하게 됩니다. 이 방법도 Progress 조건이 깨지게 되는 것이죠.

 

그렇다면 SW 방법은 임계 구역을 관리할 수 없을까요? 

 

 

위 문제들을 해결해 줄  Peterson's Algorithm에 대해서 이야기해보겠습니다.

 

Peterson's Algorithm 은 위에서 소개했던 두 알고리즘을 결합한 아이디어입니다.

 

do {
    flag[i] = true;
    turn = j;
    while(flag[j] and turn == j);
        //critical section
    flag[i] = false;
        //remainder section
}while(1);

 

위 코드를 보면서 Peterson's Algorithm은 위 문제들을 어떻게 해결했는지 알아보겠습니다.

 

먼저 공유 변수로 flag와 turn을 함께 사용하는 것을 알 수 있습니다. flag = true는 들어가고 싶어!라고 알리는 거고 turn은 실제로 누구 차례인지를 나타냅니다.

 

flag [i] = true에서 프로세스/쓰레드 i가 critical section에 먼저 접근하기 위해 flag를 true로 설정해줍니다.

 

여기서 그럼 turn = i 가 되어야 하는 거 아닐까요? 아닙니다. i 녀석은 일단 먼저 들어가겠다고 선언하고 j한테 turn을 돌려줍니다. 여기까지는 그럼 flag [j] = true, turn=i 겠죠? 이후  i 가 j 한테 차례를 넘겨주자마자 while문 실행이 가능하게 되고 critical section 진입이 가능해집니다.

 

while(flag [j] and turn =j)를 보면 critical section에 들어가기 위해서는 자기 차례여야 합니다. i 일 때는 turn=i가 되어야 하고 j 일 때는 turn=j여야 하는 것이죠. 따라서 위 과정에서 turn 이 i로 바뀌거나 j가 critical section에 진입하고 싶지 않아!라고 한다면 Spinlock을 빠져나와서 critical section에 접근할 수 있게 됩니다. 이런 방식으로 turn과 flag를 이용해서 동시 접근을 막는 것이죠.

 

 

1 - 2. 이제는 프로세스가 N개일 때의 해결 방법에 대해서 알아보겠습니다.

 

프로세스가 N개일 때는 다익스트라 알고리즘을 사용합니다. 다익스트라 알고리즘이 생소하신 분들은 아래 포스팅을 참고해주시면 됩니다

다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap))

 

 

위의 과정을 거치고 critical section 진입을 시도하는 과정을 두 단계로 직렬연결해서 프로세스/쓰레드 경쟁에 따른 부하를 최소화했습니다. Loop문 시작 전에 상태를 선언해주고, 루프문 내에서 유효성을 검토하는 과정을 거칩니다.

 

 

2. 임계 구역 문제 HW 해결 방법들(Hardware-atomic-soultion)

 

HW 해결 방법은 SW 코드를 사용해서 동기화 문제를 해결하기에는 너무 느리고 비효율적이라서 고안된 방법입니다.

크게 두 가지가 있는데요, TAS(Test-And-Set) 방식과 Swap 방식이 있습니다.

 

TAS(Test-And-Set) 방식

 

do{
    while(TestAndSet(lock));
    // critical section
    lock = false;
    // remainder section
}

 

위 코드를 살펴보겠습니다. 먼저 lock 변수를 false로 초기화해줍니다.

 

동작 방식은 굉장히 간단합니다. lock 변수가 처음에 true이면 no-ops 상태, lock 변수가 false일 때, critical section에 진입할 수 있게 하는 것이죠. 다시 나갈 때는 lock을 false로 바꾸고 나갑니다. 하지만 원하는 프로세스/쓰레드가 마음대로 critical section을 쓸 수 있기 때문에 bounded waiting 조건이 충족되지 않습니다.

 

Swap 방식

 

do{
    key = true;
    while(key == true);
    swap(lock,key);
    // critical section
    lock = false;
    // remainder section
}

 

위 코드를 살펴보겠습니다. TAS 방식과 동일한 원리입니다. 차이점이라고 하면 lock과 key를 바꾸는 것인데, 문이 잠겨있지 않을 때 (lock==false) 일 때, lock이 false 이면 lock 과 key가 바뀌면서 lock은 true key는 false가 되어 while문을 빠져나가게 되는 방식이죠. while문을 빠져나가면 critical section에 접근할 수 있게 되고 접근하고 있는 동안은 lock이 true이므로 다른 프로세스가 접근하지 못하게 됩니다. 끝난 뒤에는 lock을 false로 만들어서 다른 프로세스가 접근할 수 있도록 해주는 방식이죠.

 

4. SW, HW Solution 방식 정리

 

자 이렇게 SW, HW 방식을 알아봤습니다.

 

SW Solution의 문제점으로는 많은 반복문을 구현하는 과정에서 속도 저하가 발생하게 되고, 구현이 복잡합니다. 또한 interrupt를 억제함으로써 해결할 수는 있지만 그만큼 overhead가 발생합니다. 그리고 가장 큰 문제점으로는 원하는 자원을 얻기 위한 권한을 얻을 때까지 반복해서 확인해야만 하는 Busy waiting 현상이 발생하게 되죠.

 

HW Solution의 문제점으로는  SW Solution에서의 문제점이기도 했던 Busy waiting 현상을 극복하지 못했다는 점입니다.

 

5. 정리

 

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

 

하지만 우리가 이번 시간에 정리했던 모든 알고리즘은 Spinlock이라는 문제점이 존재했습니다.

 

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

 

감사합니다!