- 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
- 본 글은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성되었습니다.
- 강의 링크 : http://www.kocw.net/home/search/kemView.do?kemId=1226304
공유데이터 접근 문제는 High-level Language에서 한 문장에 해당하는 instruction이 Low-level에서 기계어로서 CPU에서 실행될 때 atomic하게 한 번에 처리될 수 없기 때문에 발생하는 문제이다.
이 문제 해결되기 위해서는 다음 조건들을 모두 충족해야 한다.
- Mutual Exclusion (상호 배제) : 동시에 critical section을 수행하면 안된다.
- Progress (진행) : 아무도 critical section에 없을 때, 해당 section에 들어가고자 하는 프로세스가 있으면 허락해 주어야 한다.
3. Bounded Waiting (유한 대기 시간) : 기다리는 시간이 유한해야 한다. 즉, starvation problem을 방지해야 한다.
Algorithm 1. Synchronization Variable Setting
critical section에 들어가려고 하는 프로세스가 P0, P1로 두 개가 있다고 하자. 그때 Synchronization variable을 두며, critical section에 들어가기 전에 Synchronization variable(여기서는 int turn)을 체크한다. turn이 0이면 P0차례라는 것이고, 1이면 P1차례라는 것이다. 이때 turn이라는 변수는 상대방 프로세스에 의해서 바뀌게 된다.
그러나 이 방법에 문제는 있다. 이 방법은 반드시 critical section에 들어가려고 하는 프로세스가 번갈아가며 들어가게 된다. 그런데 만약 P0이 자주 들어가는 프로세스이고, P1이 한 번 혹은 한 번도 안들어가는 프로세스라면? 영원히 P0 차례가 돌아오지 않게 된다. 결국 동시에 들어가는 문제는 해결할 수 있지만 과잉 양보 문제로 인해 제대로 동작하지 않는 코드가 된다. 즉, 앞서 언급한 조건에서 1번 상호 배제는 충족했지만 2번 Progress이 충족되지 못했다.
Algorithm 2. Flag Setting
프로세스마다 각자 flag를 두어 해결하는 방식이다. 먼저 들어가고 싶다면, 각 프로세스에 해당하는 flag 변수를 세팅하여 들어가고 싶다는 의중을 표한다. 그리고 혹시 상대방도 flag를 들고 있는지를 체크한다. 이것이 밑 Pseudo-code에서 while (flag[j]);로 표현되었다. 상대방의 flag가 내려지면 그때 flag를 reset한다.
이 방법은 어떨까? 일단 동시에 들어가는 문제는 해결이 된다. 즉, 1번 상호 배제 조건은 충족된다. 그러나 이 문제도 2번 조건이 충족되지 않을 수 있다. 어떤 상황인가? flag를 세팅했다는 것은 실제로 critical section에 들어간 것은 아니다. 들어가겠다는 의사 표현만 한 상태이다. 그러니까 flag만 세팅이 되어있고 다른 프로세스가 critical section에 들어가지 않은 상태일 때, CPU를 빼앗겼다고 한다면 모두가 flag만 세워놓고 눈치만 보다가 아무도 못들어가는 상황이 발생할 수 있다. 따라서 이 문제도 2번 조건을 충족하지 못한다는 것이다.
Algorithm 3. Perterson's Algorithm
여기서는 알고리즘 1, 2에서 사용한 모든 변수들을 사용한다. 그러면 알고리즘 1에서 발생했던 문제 : turn이 존재하여, 들어가기를 원하든 원하지 않든 반드시 다른 프로세스가 turn을 바꿔주어야만 critical section에 들어가는 문제 + 알고리즘 2에서 발생했던 문제 : 모든 프로세스가 서로 들어가지는 않고 양보만 하는 문제. 이 둘을 어떻게 해결할 것인가?
turn과 flag를 모두 활용하여 이를 해결한다. critical section에 들어가기 전에 flag를 세팅하여 들어가겠다는 의중을 표한다. 그리고 turn을 상대방으로 만들어 놓는다. 다음에 상대방이 flag를 들고 있는지, and 정말로 상대방 turn인지를 체크한다. 두 조건을 모두 충족해야만 기다리고 아니면 critical section에 들어간다. section에서 나오면 flag를 reset한다.
여기서 주의할 점은 flag[i] = true; turn = j; 의 순서를 바꾸면 안된다는 것이다.
그러나 이 방법에도 문제는 있다(뭐야 그럼 왜 배웠음?). 동작은 제대로 하는데 비효율적인 것이 문제가 된다. 뭐가 비효율적인가? 만약에 현재 i가 while문에 걸려서 계속 못들어갈 상황이면 CPU를 가지고 있으면서 while문만 계속 돌 것이다. CPU를 기껏해서 가져놓고선 한다는 것이 while문만 돈다는 것이 문제이다. 즉 CPU만 계속해서 낭비하게 되는데 이 상황을 Busy waiting, 혹은 Spin lock이라고 한다.
Synchronization Hardware
지금까지 Synchronization variable을 따로 두면서 프로그램을 설계하여 문제를 해결하려 했지만, 하드웨어적으로 이 문제를 해결할 수도 있다. 지금까지 동기화 문제를 해결하는 알고리즘에서 문제가 발생했던 이유는 CPU instruction이 atomic하지 않고 여러 단계로 나누어져 있기 때문에 그 중간에 CPU를 빼앗기는 등의 일이 일어났기 때문이다 . 만약 critical section에 들어가기 전에 Test 하고 modify하는 부분의 intruction을 atomic하게 수행하지 않는다면 앞선 문제는 쉽게 해결할 수 있다(Test_and_set instruction) Test_and_set(a)는 a라는 값을 읽어 가고, a라는 값을 참으로 만드는 것을 한 번에 수행하는 하드웨어 연산이다. 예시로 살펴보자.
만약 Synchronization variable인 lock이 0이었을 때 while(Test_and_Set(lock))을 들어가면, lock을 1로 바꿔주는 작업을 하면서 critical section으로 직행하는 일을 동시에 하게 되는 코드이다.
Semaphores (Abstract Data Type)
Semaphore은 자료구조에서 배웠던 어떤 ADT 이다. 이 Semaphore는 어떤 정수 값으로서 정의된다. Semaphore에 대해 정의되는 연산은 P (S)와 V(S)로 구성된다. P연산은 자원을 획득하는 과정 (Critical section 문제에서는 Lock을 거는 과정), V연산은 자원을 반납하는 과정(Critical section 문제에서는 Lock을 푸는 과정)이라 생각하자. 만약 어떤 Semaphore 타입의 Object Semaphore S의 값이 5라면 자원이 5개 있는 것이다. 그 와중에 P연산을 하면 S가 하나 줄어들고 자원을 가져다 쓰게 된다. 그러다가 S가 0보다 같거나 작아지면 자원을 획득할 수 없으므로 P연산을 수행 못하고 기다린다. 그러다가 다 쓰고 V연산을 하면 S가 하나 증가한다. (앞서 Synchronization problem 해결 조건에서 1번 Mutual Exclusion에서는 S의 값을 1로 둔다. 즉, 자원을 1개만 두는 것이다.)
Critical Section Problem Solved by Busy-waiting Implementation of Semaphore
이제 Critical Section에 Semaphore를 통해 해결해보자. Critical Section 문제에서 Semaphore와 같은 추상 자료형이 사용 가능하다면 다음과 같이 해결할 수 있을 것이다.
Semaphore mutex = 1; 로 (mutex는 mutual exclusion) 초기화 된 상태이며, 어떤 프로세스가 critical section에 들어가기 전에 mutex라는 semaphore 의 P 연산을 하게 되면 자원을 하나 사용하기 때문에 mutex가 하나 감소하게 되며 해당 프로세스가 critical section을 실행하고 나오면 V 연산을 통해 자원을 다시 반납하여 mutex가 증가하는 형태로 프로그램이 흘러갈 것이다.
아까 발생했던 Busy-waiting 문제에 대해 다시 살펴보자. 어떤 프로세스가 V연산을 통해 자원을 반납하기 전까지는 while문을 계속 돌면서 P연산을 못빠져 나간다. 위 그림 6은 Peterson's Algorithm과 마찬가지로 Busy-waiting(=spin lock) 문제가 여전히 발생한다. 왜냐하면 while문을 계속해서 돌고 있는 프로세스는 CPU를 갖고 있을 필요가 없기 때문이다. 따라서 이것보다는 Block/Wakeup 방식으로 구현하는 것이 좀 더 효율적이다.
Critical Section Problem Solved by Block/Wakeup Implementation of Semaphore (i. e. Sleep lock)
Semaphore 구조체에는 자원의 개수를 나타내는 value 뿐만 아니라 process를 줄세우는 프로세스 큐(struct process *L)를 따로 두어 Critical Section을 들어가지 않는 프로세스들을 이 큐에다가 줄세워서 기다리게 하고, 한 프로세스가 Critical Section에서 나오면 큐에서 기다리는 프로세스를 깨우는 방식으로 해결할 수 있다. 우리가 지난 3~4강에서 프로세스 큐에 대해서 공부할 때 배운 그림 8을 참조해보면, 공유데이터를 사용하려고 하는 프로세스들을 Resource queue에 넣어두는 것을 확인할 수 있다. Ready queue가 아니라 Blocked 상태 큐에다가 프로세스들을 집어넣었는데 그때 그것이 바로 이 Semaphore을 활용하여 구현될 수 있는 것이다. 그러면서 공유데이터를 쓰고 나간 프로세스는 Resource queue에서 한 프로세스를 꺼내어서 Blocked -> Ready queue로 바꾸어 놓으면 되는 것이다. 이것을 Sleep lock방식으로도 부르기도 한다.
그런데 이 Block/Wakeup 방식의 구현은 앞서 그림 5~6에서 봤던 Busy-waiting 방식의 구현과는 다르다. 앞에서는 값이 양수일 때 값을 하나 뺐지만 여기서는 상태에 상관없이 일단 값을 하나 뺀다. 여분이 없는 상태에서 뺐다면 음수가 되고 S.L (blocked queue)에 이 프로세스를 넣고 Block을 시킨다. 그러다가 다른 프로세스가 자원을 내어 놓는데(S.value++), 자원을 반납했어도 0이하라는 것은 누군가가 들어가고 싶어서 잠들어 있는 상태라는 것을 의미한다. 자원을 반납했는데 양수라는 것은 자원이 남아돈다는 뜻이기 때문에 깨울 필요가 없다는 것을 의미한다.
Trade-off
일반적인 상황이나 자원의 여분이 없을 때는 Block/Wakeup이 좋다. 근데 Block/Wakeup의 오버헤드는 분명히 존재하기 때문에 Critical Section을 들어가려는 경쟁이 치열하지 않거나 Section에 들어가는 일이 빈번하지 않다면 Busy-wait 방식이 더 나을 수 있다.
Two types of Semaphores
지금까지는 0 또는 1값만 가지는 semaphore로 Binary semaphore (for mutex)를 다루며 lock/unlock으로 통제했지만 자원의 개수가 여러 개일 때는 자원의 개수를 세는 방식으로서 Counting semaphore도 사용할 수 있다.
