|
Go back OS Review Device Driver NS Tools Home Papers Daily Link To Main |
8. 세마포어-동기화를 위한 도구 (Semaphore - Synchronization Hardware)
자! 이제 우리의 오에스에 대한 논의는 어느덧 클라이맥스에 이르른듯 싶습니다. 세마포어 역시 교과서의 6장에 나오는 내용으로써 6장의 핵심에 해당됩니다. 전장에서 제시되었던 베이커리 알고리즘으로 우리는 여러 프로세스 사이에서 일어나는 CS문제를 나름대로 해결할 수 있었습니다. 허나, 베이커리 알고리즘의 한계가 무엇인지 곰곰히 생각해보셨는지요? 알고리즘 자체는 훌륭했습니다만, 그것이 결국은 소프트웨어적으로 구현이 되었다는 한계를 지적을 할수 있겄습니다. 그렇다면, 이 문제를 좀더 효과적인 하드웨어로 해결하는 방법은 없을까하는 의문점이 자연스럽게 등장하고, 그러면 단순하게 두 프로세스가 공유하고 있는 변수를 조작할 시에는 인터럽트 자체를 불가능 하게 만들면 해결되지 않을까!? 라는 획기적인 아이디어를 내보지만, 멀티프로세서 시스템에서는 이방법이 전혀 통하지를 않게 된다는 사실을 알아야겠죠. 왜냐하면 프로세스 한개가 "나 이제 CS에 돌입한당께~"라고 메시지를 모든 씨피유에 보냄으로써 다른 인터럽트들을 모조리 막어버린다는 발상 자체가 일단 매우 괘씸하며 시간을 낭비하는 짓이기 때문입니다. 결국 시스템의 효율은 저하되어 버리고, 만일 시스템 클럭이 인터럽트로 업데이트 되고 있다면, 이것조차 엉망이 되어버리고 말겄죠. 따라서 특수하게 제공되는 하드웨어적 명령어가 있으니, 이 명령어는 먼저 조건을 판별해본뒤 한 워드(word-CPU가 처리하는 단위 데이터의 길이입니다)의 값을 바꾸거나 두 워드 사이의 내용을 바꿔치기(swap) 하는 작업을 한칼에!!!(atomically:1.분할이 불가능한; 2.우주소년아톰같은) 해치워버리는 것을 목적으로 하게 되겠습니다. 즉, 데이터 업데이트시 그것이 한번의 씨피유 클럭에 처리되버린다는 사실에서 프로세스간에 공유하는 데이터 업데이트 문제를 근본적으로 해결하려는 의도이죠. 먼저 조건을 판별하고 값을 세팅하는 것으로써 Test-and-Set()이라는 함수가 교과서에서 소개되고요, 바꿔치기 하는 함수로써 Swap() 이라는 함수가 소개됩니다. 이 둘은 그러나 막상 조금이라도 복잡한 CS 문제를 해결하려고 적용을 하기에는 도저히 용서가 안되는 관계로 좀더 쉽게 CS 문제를 해결하기 위하여 싱크전용 도구인 우리의 세마포아(Semaphore)가 화려하게 등장을 하게 됩니다. 짜잔,,, 세마포어 S는 정수값 변수입니다. 초기화 과정을 제외하고 이 정수값은 전장에서 언급된 시피유 내에서 3단계에 걸친 업데이트가 아닌 한칼에! 업데이트되는 특별한 변수이죠. 또한 이 정수값은 단 2개의 함수로 만이 조작이 가능한데 그것은 각각 wait(S)와 signal(S)입니다. 여러분, 위의 두 함수는 각각 단 한칼에(아토믹하게) 실행 된다는 사실을 절대 앞으로 잊으시면 안되요. 매우 중요한 사실입니다. 먼저 wait(S)및 sigal(S)라는 함수를 살펴보도록 하지요.
wait(S): while S<0 do no-op;
S:=S-1;
signal(S): S:=S+1;
단 한칼!에 위에서 제시한 함수가 실행된다는 것에 덧붙여서 세마포어 S는 반드시 한번에 한가지 함수만을 실행시킬수 있는 상호배타성, 즉 뮤텍스가 보장된다는 사실입니다. 무슨말이냐, wait(S)를 어떤 프로세스가 실행하고 있는 순간에 다른 프로세스가 wait(S)는 물론이요, signal(S)또한 절대로 실행을 할 수 가 없다는 것입니다. 그렇다면, 위의 세마포어를 CS문제에 도데체 어떻게 이용을 하는지 한번 살펴보도록 합시다. 아래의 코드를 봐주시길. 참고로 각 프로세스마다 아래의 코드를 스스로가 실행하고 있다는 전제입니다.
repeat
wait(mutex);
CS
signal(mutex);
RS
until false;
위의 예에서는 뮤텍스(mutex-Mutual Exclusion(상호 배타성)을 간결하게 표현한것)라는 세마포어를 이용해서 CS문제를 껌으로 해결하는 모습을 보여줍니다. 한번 곰곰히 어떻게 저렇게 단순한것이 그 엄청난 문제를 해결하는지를 알아볼까요? 제일먼저 mutex값을 1로 초기화를 시켰다고 전제하고(꽤 중요한 전제입니다), 임의의 프로세스가 자신의 CS에 돌입하기 위하여 wait(mutex)를 호출했다고 칩시다. 만일 다른 프로세스가 이미 CS에 들어가 있다면, mutex값은 이미 0이 되어있는바, while루프를 맴돌며 mutex가 1로 돌아오기를 애타게 기다리는것 외에는 아무것도 취할수 있는 행동이 없게 되지요. 바로 문앞에서 턱~! 막히는 경우입니다. 이미 CS에 들어있던 프로세스는 나오면서 반드시 signal(mutex)를 호출할테고, 이순간 mutex값은 다시 1로 환원이 되지요? 고로 while루프 안에서 뺑이돌던 프로세스가 이번에는 while문에서 벗어나 자신의 CS로 돌입하게 된는것이죠. 세마포어라는 특수성으로 인해 절대로 동시에 두 프로세스가 wait(mutex)를 호출하는것이 원천봉쇄 되느니 만큼, 절대로 두 프로세스가 각자의 CS에서 콩깍지 까는 일 절대 안일어 납니다. 이렇듯, 단칼에 수행되는 함수 두개(wait과 signal)와 절대로 동시에 엑세스 할수 없는 변수(세마포어) 한개로 정말 깔끔하게 CS문제가 해결 되지요? 자, 이쯤해서 불현듯 뭔가 껄쩍지근,,,한게 머리를 스쳐야 하는데,,, 아니! 이럴수가!!!??? 두 프로세스간에는 절대로 변수를 공유할수 없다고 전에 말해놓고(전역변수조차 지맘대로 각자 내부에 복사해놓고 쓴데매,,,) 세마포어라는 공유하는 변수를 쓴다는거 개소리 아닙미까!? 라고 질문하는 녀석, 내 이뻐해주리라,,,넌 똑옥또옥한 놈이야,,, 그렇습니다. 세마포어의 정체를 여기서 밝혀야 할때가 온것입니다. 세마포어는 3대 IPC(Inter Process Communication) 패밀리중 우두머리 였던것입니다. 그럼 여기서 잠깐 IPC를 간략하게 살펴보고 넘어갈까요? IPC란, 여러개의 프로세스들 사이의 통신을 의미합니다. 전에 프로세스의 개념을 설명드리면서 각 프로세스는 각각의 데이터구조 및 데이터를 가지고 있기에 전역변수나 로컬변수등은 전혀 그들 사이에서는 의미가 없다라는 사실을 이야기한적이 있죠? 예를 들어 패런트 프로세스가 차일드 프로세스를 생성할시에는 자신이 가지고 있던 모든 데이터를 그대로 복사! 시키기에 a라는 전역 변수가 패런트 프로세스 내에 있었을 지라도 패런트 프로세스내에서만 이것이 전역이지, 그렇다고 차일드까지 똑같은 a를 참조한다고 생각하면 착각입니다. 차일드에게도 전역변수 a가 있으나, 그것은 이미 복사본의 전혀 다른 전역변수 a라는 것이죠. 고로 두 프로세스간에 동시에 공유할수 있는 데이터를 형성하는 방법이 요구될때 등장하는 것이 바로 IPC이며, 이것은 일종의 통신의 개념이 되어버린다는 것이죠. IPC는 크게 3가지 테크닉이 존재합니다. 세마포어(semaphore), 공유메모리(shared memory-앞으로 그냥 쉐어드 메모리라고 하죠), 그리고 메시지(message)를 이용하는 방법등이죠. 각각에 대한 활용예는 앞으로도 간략하게나마 나오니만큼 지금은 IPC로 두 프로세스간에 공유하는 데이터를 생성시켜줄수 있다는 사실만을 주지 하시면 됩니다. 자, 그러면 내친김에 다음의 코드또한 봐주십쇼.
P0 P1 wait(S); wait(Q); wait(Q); wait(S); ... ... signal(S); signal(S); signal(Q); signal(Q); 왼편은 프로세스0이 자신의 내부에서 세마포어를 쓰고 있는 모습이고, 오른편은 프로세스1이 자신의 내부에서 세마포어를 쓰고있는 모습입니다. 뭔가 대칭적인 모습이기도 하고, 저게 뭐다냐,,,라는 느낌도 들겠지만, 가만이 들여다보면 P0과 P1은 더이상 숨쉬고 있지 않고 있음을 알게될것입니다. 그렇습니다. 죽은 프로세스가 되어버렸어요. 프로세스0은 현재 프로세스1이 Q라는 세마포어를 signal해주기를 기다리고 있고, 프로세스1은 반대로 프로세스0이 S라는 세마포어를 signal해주기를 기다립니다. 바로 데드락!(dead-lock)이 일어난 순간이라고 합니다. 영원히 서로만을 기다리면서 생을 마감할 프로세스들입니다. 세마포어가 주는 기쁨도 잠시, 이렇게 세마포어를 사용할지라도 또다른 위험이 또아리를 틀고 있다는 사실을 알게 됩니다. 사실 데드락(레드락!을 떠올린자,,,허허)을 완전히 해결하기는 불가능합니다. 하지만, 이것을 미연에 방지하거나 일단 데드락이 발생했다는 사실을 발견하고 두 프로세스를 조용이 숙청해버리는 방법이 없는것이 아니죠. 곧 데드락에 대한 개념의 정의와 이의 해결법을 다룰테니 이또한 기대해 주시기 바랍니다. 세마포어가 내포하고 있는 또하나의 문제점은 바로 바쁜 기다림(busy waiting)입니다. 세마포어는 각 프로세스가 자신의 CS에 들어가기전에 먼저 세마포어 값을 확인하면서 이것이 0보다 작을때에는 while 루프 내에서 빙빙 돌고 있죠? 뭐 한두개의 프로세스가 빙빙 돈다면 그나마 봐줄만 하지만, 수천개, 수만개가 지 안의 루프내에서 빙빙 돌고있는 경우를 상상해 보십쇼. 유저는 돌아버립니다. 이렇게 바쁘게 돌면서 귀중한 씨피유 클럭을 소비하는 프로세스, 허나 정작 아무일도 못하고 세마포어의 신호가 떨어질때까지 하염없이 기다리는 프로세스의 상태를 우리는 비지웨이팅이라고 합니다. 이 문제를 또한 해결하기 위하여 실제적으로 signal()과 wait()을 정의를 약간 바꾸어주죠. 즉, wait()의 경우 만일 세마포어 값이 음수일경우는 레디큐로 프로세스를 세마포어와 함께 보내고, 프로세스의 상태를 기다림(waiting)상태로 전환을 시켜주게 됩니다. 재빨리 컨트롤은 씨피유 스케줄러에게 넘어가고 스케줄러는 전에 설명했듯이 레디큐에서 대기중이던 프로세스 한개를 골라서 씨피유에 넘겨주지요. signal()의 새로운 정의는 역으로 레디큐에 잡혀들어간 프로세스를 다시 깨워주는 과정을 포함하게 되겠죠? 세마포어는 크게 0과 1값사이만을 가질수 있는 바이너리(binary) 세마포어와 임의의 정수값을 가질수 있는 카운팅(counting) 세마포어로 그 종류를 나누고 바이너리 세마포어로 카운팅 세마포어를 만드는 알고리즘 또한 책에 등장합니다만, 교수님은 이 알고리즘 황이다라고 막 욕을,,,그러면서 자신의 알고리즘을 따로 설명해주었는데, 더 모르겄더구먼유. 그밖에 CS문제 외에도 전에 언급했던 컨슈머-프로듀서 사이에 발생하는 싱크문제를 세마포어로 해결하는 방법과 리더(reader)와 라이터(writer) 문제등이 책에서는 소개가 되지만, 세마포어가 무엇인지에 대한 개념은 앞에서 설명한 예로 충분히 납득이 되셨으리라는 자만심아래 이번장을 마칠까 합니다. 세마포어를 유닉스에서 사용하는 방법은 조금 복잡합니다. 먼저 세마포어를 사용하기 위한 헤더파일들이 준비되어야 하고, 각각 사용될 세마포어 셋(set:집합)등을 프로그래머가 직접 정의해주어야 하지요. 세마포어는 크게 세마포어의 형성, 세마포어의 제어, 그리고 세마포어의 적용등의 단계를 코드화해서 사용하게 되는데, 세마포어를 잘못 사용했을경우, 이것은 컴파일러조차 찝어내지 못하는 심각한 논리에러로 연결이 되지요. 일단 그러한 점을 주지해 주시고 관심이 있으신 분은 제 홈페이지에 기재되어있는 Assignment5의 소스코드와 결과를 참고하시면 될것입니다. Assignment5는 먼저 searcher(s), inserter(i), deleter(d)라는 링크드 리스트를 관리해주는 세개의 바이너리(각각 main()함수가 있는 컴파일된 실행파일입니다)를 만든뒤, 이것을 메인(Assignment5의 main())에서 각각 차일드 프로세스와 exec**()콜로 합체시켜버립니다. 각각 3개씩의 s, i, 그리고 d(총 9개의 차일드 프로세스가 태어나요)를 만든다음 각각은 자신의 갯수 및 서로의 뮤텍스 조건등을 세마포어와 쉐어드 메모리를 이용하여 트래킹해주게 되지요. 예를들어 s는 다른 i나 d와 동시에 실행될수 있으나 d는 다른 s나 i, 심지어 다른 d와도 함께 실행되서는 안된다는 조건등입니다. 이때 현재 활성중인 s, i, 그리고 d의 갯수를 제대로 트래킹해주려면 세마포어가 반드시 필요하게 되겠죠? 다음장에서는 교과서 6장의 후반부인 다이닝필로소퍼스 문제(The Dining-Philosophers Problem:밥쳐먹는 몽상가들)에 대한 제시와 해결법, 그리고 세마포어 외의 CS문제를 해결하기 위해 고안된 특수한 구조체등을 살펴보면서 악명높은 교과서 6장을 마무리 지을 예정입니다. 여기까지 어줍잖은 저의 글 읽느라고 수고하신 여러분, 정말 수고가 많으셨습니다. -duffer 경준 (http://vorlon.cwru.edu/~kxm73)
|