|
Go back OS Review Device Driver NS Tools Home Papers Daily Link To Main |
7. 크리티컬 섹션 문제 (The Critical Section Problem)
아, 지금 책에서 즐겁게 뛰어노는 저 공룡은 내맘을 아는지 모르는지,,,본 장에서 다룰 내용은 교과서 6장에 대응 됩니다. Process Synchronization(Sync)이죠. 전에 한번 싱크가 무엇인지를 간략하게 설명한 적이 있습니다만, 여기서의 싱크란 좀더 구체적으로 말하면 여러개의 프로세스가 공동으로 참조하려는 데이터를 일관성있게 유지시키는 동기화를 의미하게 됩니다. 바로 전장에서 한 프로세스가 변화를 주는 과정에 있는 데이터를 다른 프로세스가 참조하려는 행위는 참으로 위험하다고 말한 바가 있죠? 이 사건에 대한 대책을 이번장에서는 다루는 것이죠. 교과서의 6장은 사실, 이 OS개론의 핵심이기도 합니다. 얼만큼 핵심이냐,,,제가 들은 본과목의 강의의 중간고사 시험범위가 바로 6장, 이 한장이었다는 사실만으로도 느낌이 오실거라 생각되는군요. 하여간 책에 간간이 등장하는 알고리즘들을 여러분들이 그냥 한번 읽고 이해를 하신다면 여러분은 틀림없는 천재라는 사실을 먼저 말씀드리고 싶군요. 겁주자는거 절대 아닙니다. 단지 조금 어려울수도 있지만 여러번 반복해서 생각해보면 깨달음이 올것이라는 저의 격려입니다 ^^. 참고로 저는 책에 등장하는 모든 알고리즘들을 여기서는 다루지 않을것입니다. 한 알고리즘 설명하는데 이런 문서 한장정도가 소요될수도 있거든요. 그럼 슬슬 시작을 하겄습니다. 책의 초반부에 등장하는 것은 바로 컨수머-프로듀서(consumer-producer) 패러다임입니다. 이것은 무엇이냐, 한 프로세스는 데이터를 생산해내고, 또한 프로세스는 데이터를 소비하게 되는 것이지요. 이 둘간의 프로세스는 고로 일종의 '통신'을 필요로 하게 되는데 프로듀서와 컨수머는 각각 어느 데이타가 오고 갔다는 사실을 트랙킹하기 위해서 카운터(counter)를 필요로 하게 되죠. 이때 그 카운터를 두개의 프로세스가 공유하면서 유지한다는 사실을 우리들은 주지할 필요가 있고, 그 카운터는 코드상에서는 그냥 "counter=counter+1" 또는 "counter=counter-1"등으로 나타내줌으로써 각각 증가 또는 감소 시킨다는 것쯤은 우리도 알고 있겠죠. 자, 이때 counter라는 변수가 씨피유 내부 에서는 어떻게 증가하고 또 감소되는지 한번 봅시다. 앞으로 등장하는 모든 알고리즘들은 모두 파스칼(Pascal)버젼입니다.
counter의 증가 counter의 감소 register1:=counter; 1단계 register2:=counter; register1:=register+1; 2단계 register2:=register-1; counter:=register1; 3단계 counter:=register2; 그렇습미다! 알고보니 겨우 1증가 시키는 연산조차 멍청한 씨피유는 총 3단계로 나누어서 수행을 하고 있었음을 우리는 여기서 알수 있게되죠. 참고로 레지스터란 씨피유 내부에 있는 아주 크기가 작지만 매우 빠른 임시기억소자라고 전에 말씀드린적 있죠? 이때, 프로듀서가 데이터 한개가 생겼음을 나타내기 위해 카운터 증가의 2단계를 수행하고 있는 순간 갑자기 컨수머가 카운터의 값이 뭐냐! 싶어서 카운터를 읽어들였다고 칩시다. 순간, 이미 때는 늦었고, 프로듀서와 컨수머는 각각의 카운터 값으로 서로 착각속에서 신나게 만들어 대고 신나게 소비합니다. 결국 둘은 서로 삽질하는 가운데 나중에는 숫자하나 서로 제대로 못세는 븅따리가 되어버리고 맙니다. 바로, 이순간, 위의 총 3단계처럼 프로세스들간에 공유하는 어떤 값이나 데이터, 또는 테이블을 업데이트 하는 순간을 담고있는 코드의 부분(segment)을 바로 크리티컬 섹션(Critical-Section)이라고 일컫고, 이문제를 정의하고 해결하는 방법론을 제시하는것을 Critical-Section Problem이라고 합니다. 이문제를 피할수 있는 방법은 결국 시간적으로 한 프로세스가 자신의 크리티컬 섹션에 돌입하면 다른 프로세스들은 절대로 같은 시간에 자신의 크리티컬 섹션에 돌입 못하게 만드는 상호 배타(mutually exclusive-앞으로는 그냥 뮤텍스(mutex)라고 하겠습니다)성을 부여해줌으로서 해결하는 것이죠. 즉, 한 프로세스가 공유 데이터를 바꾸고 있는 와중에는 다른 프로세스는 그 데이터를 절대로 읽는것은 물론이요, 변경자체를 못하게 한다는 말입니다. 임의의 프로세스를 크리티컬 섹션(앞으로는 CS라고 간단하게 말하죠)을 고려한 기준에서 구조화 시켜보면 아래와 같이 볼수 있어요.
repeat
entry section
Critical Section(CS)
exit section
Remainder Section(RS)
until false;
즉, 프로세스는 크게 흐름상 CS와 RS로 나눌수가 있다는 말입니다. 이때 CS 문제를 해결하는 알고리즘은 다음의 3가지 조건을 반드시 만족해줘야 합니다. 1. 상호배타성(뮤텍스:mutual exclusion) : 프로세스 Pi가 자신의 CS에 돌입하면, 다른 프로세스는 절대로 그들의 CS로 돌입하지 못한다. 2. 진행성(progress) : 만일 어떤 프로세스도 자신의 CS에 돌입한 상태가 아니고, CS에 돌입하기를 원하는 임의의 프로세스들이 존재한다면, 자신의 RS에 돌입한 프로세스를 제외한 프로세스들의 CS내부로의 진입이 무기한 연기되서는 안된다. 3. 정해진 기다림(bounded waiting) : 한 프로세스가 CS에 돌입하기를 요청한뒤 CS에 실제로 돌입하기 전까지는 정해진 횟수 이하 만큼의 기다림이 존재해야 한다. 흠,,,말이 조금 어렵죠? 그래도 할수 없어요, 쉽게 모든걸 얻으려하는자 도둑놈이라닌깐,,, 먼저 책에는 2가지의 알고리즘이 등장하지요, 비교적 단순한 알고리즘들로써 첫째 알고리즘은 turn이라는 변수로 어떤 프로세스가 CS에 들어갈것인가를 결정해주는 알고리즘이고, 두번째 알고리즘은 flag[]라는 배열을 이용해서 각 프로세스의 상태(CS에 있는지 아니면 그 밖에 있는지)에 대한 정보를 유지하는 알고리즘 들이죠. 이 두 알고리즘은 모두 상호 배타성을 만족시켜는 주지만 진행성에서 꽝이 되버립니다. 그래서 등장하는 것이 제 3의 알고리즘인데 여기에서 turn과 flag[]를 교묘하게 섞어서 위의 3가지 조건을 모두 다 만족시켜주는 쾌거를 이룩합니다. 허나! 좋아하기에는 아직 이릅니다. 왜냐하면 이것은 프로세스가 단지 2개 있을때만 사용이 가능한 짝퉁 알고리즘이기 때문입니다. 그렇다면, 여러개의 프로세스들에 대한 CS문제를 해결할수는 없는가? 당연이 있지요. 바로 그 이름도 유명한 Bakery Algorithm입니다. 베이커리 알고리즘은 마치 빵집에 빵을 사려 들어왔으나 사람들이 워낙 북적거려서 대기표를 받고 빵을 구입하려 기다리는 사람들을 프로세스에 비유를 해서 만든 알고리즘이랍니다. 책이 없는 분과 책은 있으나 전혀 이해가 가지 않는분을 위해 더퍼군, 이렇게 손수 알고리즘및 그 원리를 기술해드립니다. Bakery Algorithm 본 알고리즘은 Pi가 CS에 돌입하기 위해서 사용하는 알고리즘이며, 먼저 모든 프로세스 사이에서 공동으로 사용되는 변수들을 알아보죠.
var choosing: array[0..n-1] of boolean;
number: array[0..n-1]of integer;
또한 여기서 사용하는 기호에 대한 의미를 정의하면 다음과 같습니다.
(a,b)<(c,d) : a가 c보다 크거나 또는 a와 c가 같고 d가 b보다 큰경우 참이됨. max(a0, ...an-1) : 말그대로 a0과 an-1 사이(총 n개가 있죠?)에서 제일 큰놈. no-op : 아무짓 하지 말라는 소리임. 알고리즘 몸통은 다음과 같습니다.
repeat
choosing[i]:=true;
number[i]:=max(number[0], number[1],...,number[n-1])+1;
choosing[i]:=false;
for j:=0 to n-1
do begin
while choosing[j] do no-op;
while number[j]!=0
and(number[j],j)<(number[i],i) do no-op;
end;
CS
number[i]:=0;
RS
until false;
쨘~ 멋진 알고리즘이 아닐수 없습니다요. 허허허,,,그럼 다음 내용으로 스멀스멀 넘어가기 전에 알고리즘 분석 한번 해봅시다. 제일먼저, 여러분들이 헷갈리는것을 미연에 방지하기 위하여 모든 프로세스들은 본 알고리즘을 자신의 내부에 내장하고 있다는 전제이며, 제 3자가 본 알고리즘들을 통해 각 프로세스들을 통제하는 것이 아니라, 각각의 프로세스들이 주체가 되어 본 알고리즘을 이용해서 자신이 CS에 들어가야할지, 아니면 더 기다려야 할지를 결정한다는 사실입니다. 일단, CS에 들어갈 준비가 된 순간 프로세스 i는 i번째 번호표를 부여받습니다(이때 i는 프로세스 자신의 번호이기도 합니다). 바로 number[i]에 부여받은 번호가 들어가게 되는데, 잘보시면 끝에 "+1"이 있습니다. 그렇죠, 현재 대기중인 가장 큰 번호보다 한개가 더 큰 번호가 번호표에 기재됩니다. 또 보시면 알겠지만 CS돌입 준비가 끝나고 번호를 받는 순간 choosing[i]은 참값이 된다는 사실에서, 다른 프로세스(CS 돌입 준비를 끝내고 대기중인)들 역시 for 루프내에서 모종의 음모를 꾸미다가 어떤 프로세스가 CS돌입을 위한 번호표를 받을때면 모든것을 엄숙하게 중단하고 번호표를 받는 프로세스를 주시하게 되지요. 새로운 프로세스의 번호표에 번호가 기재됬음을 확인한 다음에야 비로서 다시 for 루프는 돌아갑니다. 아, 서로를 존중해주는 정말 바람직한 알고리즘이야,,, for 루프 내부를 한번 봅시다. 먼저 for 루프는 0부터 n-1개 까지, 즉 총 n개의 번호표 number[]를 차례로 훑어 보면서 각 번호표에 번호가 새겨져있는지를 확인하게 되요. 0은 아무 번호도 기재되어있지 않다는 뜻이죠. 이때 해당 번호의 프로세스들은 CS 돌입에 대한 의사가 없는 프로세스들입니다. 그래서 모두 0이면 for loop를 유유자적하게 빠져나와 CS에 돌입하게 되겠죠. 허나, 누군가의 번호표가 0이 아님과 동시에(누군가 CS돌입을 신청했군요) 이것이 자신의 번호표보다 작은 값인지를 확인하죠. 만일 작은 값이거나 값이 같더라도 프로세스 번호가(번호표의 번호와 프로세스 번호는 다르다는것을 주지하시길) 자신보다 작다면 그냥 루프는 돌아간다는 사실에서 아직 자신은 CS에 들어갈때가 아니라는 것을 알게 됩니다. 만일 위의 경우가 아니라면 자신의 번호표 번호가 가장 작거나 번호표 번호가 같더라도 프로세스 번호가 자신이 가장 작은 경우이므로 기냥~ 루프에서 벗어나면서 CS로 쇽~ 들어가는 기득권을 얻게 됩니다. 이 알고리즘에서 번호표의 번호와 프로세스 번호를 각각 고려하는 이유는 보시면 알겠지만 공통 데이터 스트럭쳐인 배열들(바로 choosing[]과 number[]) 자체도 CS문제를 안고 있기에 동시에 두 프로세스가 CS돌입 준비를 하면서 번호표에 똑같은 번호를 받는 경우가 발생할수 있어요!!!(+1을 한참 하려는 와중에 또 다른 프로세스가 CS돌입을 준비 해버리면 업데이트 되기도 전에 번호표를 같이 부여받는 경우이죠) 고로 그 경우에 대한 해결책으로써 만일 두 번호표의 내용이 같다면!? 그때는 프로세스의 고유 번호를 비교하게 되고, 결국 프로세스 번호가 낮은 녀석이 기득권을 쥐게 됩니다. 멋지죠?! CS에서 일을 해결하고 나오면서 자신이 부여받은 번호표의 내용을 0으로 다시 초기화 시킴으로써 다른 사람들이 프로세스들이 CS에 돌입할수 있도록 배려를 해주게 됩니다. 그리고 나서 여유를 가지고 RS에서 자기 하고픈일 계속 하게 되지요. 베이커리 알고리즘은 위에 제시한 3가지 조건을 모두 만족합니다. 그리고 그것에 대한 증명을 교과서는 얄밉게도 문제 6.2를 위해서 일부러 하지 않았다고 뻔뻔스레 말을 합니다. 그러니 여러분들이 스스로 안해보신다고 저는 비난하지 않습니다. 다음 장에서는 그렇다면 매번 이런식으로 골치아픈 장치를 프로세스마다 부과해주어야하는가에대한 회의를 하드웨어적으로 해결해주는 세마포어(Semaphore)에 대해서 이야기 해볼까 합니다. 일단 꽤 골치아픈 산을 넘었으니 축배의 맥주라도 한잔 하심이 어떨까요? :) -duffer 경준 (http://vorlon.cwru.edu/~kxm73)
|