[운영체제 Step 14] - Language level 솔루션

지금까지 다루어 봤던 솔루션들은 사실 꽤나 low-level에 속한 솔루션들입니다.

그로 인해 구현하기 어렵다는 단점이 존재하고 에러가 발생할 확률도 올라간다는 단점이 있었습니다.

물론 OS가 support해주면서 성능은 향상시킬 수 있었지만 그에 따른 눈에 안보이는 단점도 존재할 수 있습니다.

따라서 이번 시간에 배워볼 것은 조금 더 가벼운 수준에서 이 상호배제를 풀어나가보려고 합니다.

이번 시간에 배울 솔루션은 명암으로도 구분이 되는 Monitor라는 솔루션입니다.

지금까지 했던 것보다 사용이 쉽다는 특징을 가지고 있는데 어떤 것인지 살펴보겠습니다.

모니터라는 것은 Critical data와 CS영역을 모아놓은 하나의 방이라고 생각하시면 되겠습니다.

예를 들어 책 방인데, 한 방에 한 명만 들어갈 수 있는 책 방이라고 생각하면 좋겠습니다.

따라서 Critical data는 하나의 책이 될 것이고 CS영역은 책을 대출 또는 반납하는 카운터라고 생각합시다.

이 모니터는 2가지 변수로 연산이 가능합니다. 뒤에서 살펴보겠습니다.

제일 먼저 모니터의 구조입니다.

entry queue는 진입 큐라고도 불리는데요.

진입 큐는 모니터 내의 procedure 즉, function이라고 생각하셔도 좋습니다.

따라서

앞에서의 entry queue의 각 procedure를 하나의 function이라고 생각하셔도 되겠습니다.

또한 이 모니터는 항상 하나의 프로세스만 진입이 가능하다는 특징을 가지고 있다는 상호 배제의 성격을 띕니다.

이것을 누가 보장해줄까요?

바로 Language가 보장해줍니다.

또한 한 방에 하나의 프로세스만 존재하기 때문에 정보의 은폐성을 가지고 있습니다.

 

조건 큐는 무엇일까요?

특정 조건을 기다리는 프로세스들이 대기하는 대기실이라고 생각하시면 되겠습니다.

그리고 시그널 큐는 전화부스라고 생각하시면 좋습니다.

그래서 시그널 큐가 시그널을 보내기 위해 조건 큐에 전화를 걸면 프로세스가 조건 큐를 만족하여 실행되는 구조입니다.

따라서 모니터에는 굳이 신호제공자 큐가 여러 개 존재할 필요가 없습니다.

하나의 프로세스만 실행이 가능하기 때문에 구조적으로 신호제공자 큐도 하나만 존재해야 합니다.

따라서 신호제공자 큐가 signal() 신호를 보내면, 프로세스가 임시 대기하고 있다고 조건 큐에 맞추어서 실행이 되는, 그런 흐름이라고 생각하면 좋겠습니다.

예제를 통해 알아보겠습니다.

참고로 자바의 Monitor 클래스입니다.

 

자 자원 할당 문제입니다.

R이라는 자원을 한 번에 한 명만 쓸 수 있다고 하겠습니다.

이 자원을 요청하는 function이 있고 반납하는 function이 있다고 하겠습니다.

이 R을 책이라고 할 때, 왼쪽의 releaseR()과 requestR()을 각각 procedure 즉, function이 되겠습니다.

그리고 책방 안에는 requestR()과 releaseR()이라는 노란색 직사각형이 대출과 반납하는 책방의 공간이라고 합시다.

오른쪽의 condition queue는 책을 빌릴 수 있는지 물어보는 대기실이고, signaler queue는 전화부스 역할이므로 대기실에 대기실에 있는 깨우는 공간이라고 생각하고 넘어가보겠습니다.

 

자원할당 문제입니다.

우리는 requestR() 즉, 책을 대출하러 왔습니다.

제일 먼저 R_Available -> 책을 이용할 수 있는지. 거기에 ~을 붙혔으니 책이  없으면~ 이 됩니다.

그리고 만약 그렇다면, wait()를 써서 기다려라는 의미가 됩니다.

그런데 그렇지 않다면 즉, R_Available이 true라면 if문이 실행되지 않고 밑의 문으로 가서 이것을 false로 바꾸고 책을 대출합니다.

한 마디로 정의하자면 책이 있으면 빌리고 없으면 대기하겠다고 해석이 가능합니다.

그리고 releaseR()은 어떨까요?

반납하러 왔으니 R_Available을 일단 true로 만들고 R_Free에서 기다리고 있는 친구에게 signal()을 줘서 대기실에 있는 녀석을 깨우고 종료됩니다.

상당히 쉽지요?

그럼 이게 어떻게 가능한지 내부 동작을 살펴보겠습니다.

제일 먼저 Pj가 도착해서 책을 빌리러 왔다고 가정해보겠습니다.

그럼 이용 가능한 R_Available은 1에서 0이 될테고 requestR()에는 Pj가 담깁니다.

그리고서는 책을 빌리고 나와서 R이라는 공간에서 책을 열심히 보고 있다고 해봅시다.

이런 상황에서 Pj는 procedure에서 지워지게 되고 다음으로 Pk와 Pm이 도착했다고 해보겠습니다.

Pk가 와서 봤더니, 책방에 책이 있나요? 없겠죠??

따라서 책이 생길 때 까지 기다리는 대기실에서 Pk와 Pm도 기다릴 것입니다.

이렇게 그려지겠지요.

그러다가 Pj가 자신의 책을 다 읽고 반납하러 왔다고 해봅시다.

그럼 왼쪽의 releaseR()로 이동하게 되는데, 아무도 없으므로 releaseR() 노란색 직사각형에 담깁니다.

그리고 R_Available은 0에서 1이 되고 대기실에서 기다리고 있던 Pk와 Pm을 깨워야 합니다.

따라서 Pj는 signaler queue로 이동하여 책방에 아무도 없게끔 만들고 Pk를 깨운 뒤 Pk가 다시 requestR()로 이동합니다.

굉장히 간단하죠??

 

그럼 이제 생산자-소비자 문제로 다시 넘어가보겠습니다. (세마포어에서도 했었죠?)

제일 먼저 procedure는 2가지로 정의할 수 있겠습니다.

하나는 fillBuf() 즉, 물건을 넣는 것, 나머지 하나는 emptyBuf()로서 물건을 비우는 것이라고 합니다.

앞에서 한 것과 유사하게 이것 역시 fillBuf()은 생산자, emptyBuf()는 소비자 역할을 할 것입니다.

오른쪽의 bufHasData는 데이터를 가지고 있는지, bufHasSpace는 공간을 가지고 있는지 묻습니다.

중앙에 있는 in과 out은 물건을 어디서 넣고 뺄지를 나타내는 위치 변수입니다.

validBufs는 물건의 개수를 저장하는 변수가 되겠습니다.

같이 한 번 살펴보겠습니다.

제일 먼저 생산자 procedure가 물건을 채우러 왔습니다.

validBufs가 N개라는건 물건이 다 찼다는 것이므로 bufHasSpace에 가서 wait()기다리라는 것입니다.

따라서 그 아래의 위치에 물건인 data를 놓고 validBufs를 +1해주고 in은 mod연산을 합니다.

이후 bufHasData에 물건을 기다리고 있는 프로세스가 있다면 그것들을 signal() 즉, 깨워주러 갑니다.

 

소비자입장에선 어떨까요?

제일 처음 validBufs 즉, 물건 수가 0인지를 확인합니다.

만약 물건 수가 0이라면 bufHasData에 가서 wait합니다.

이후 물건이 생겼다면 물건을 꺼내고 validBufs를 -1하고 bufHasSpace에 signal()을 주고 깨우러 갑니다.

 

다른 문제도 살펴보겠습니다.

Reader-Writer 문제입니다.

기본적으로 Reader는 여러 명이 존재해도 되었고 Writer는 한 명만 존재해야하는 것이 장려되었습니다.

읽고 있을 때 쓸 수 없었고 쓰고 있을 때 읽을 수 없다는 특징을 가지고 있습니다.

자 만약 쓰는 것이 허락되어 있다면 그럼 readingAllowed를 기다리라고 할 수 있습니다.

그리고 그렇지 않다면 numReaders 즉, 읽는 사람을 +1 해주고 reading이 허락되었는지 여부를 확인 후 확인이 되었다면 readingAllowed에게 signal()을 줍니다.

그리고 reading을 다했다면 읽는 사람을 -1해주고 만약 읽는 사람이 0인 것이 확인이 되었다면 writingAllowed에게 signal()을 줍니다.

반대의 경우에서도 똑같으니, 이건 넘어가겠습니다.

 

그 다음으로 살펴볼 것은 5명 철학자의 저녁식사 문제입니다.

굉장히 재미있는 문제인데요.

이 철학자들은 하는 일이 생각, 스파게티 먹기만 반복합니다.

그런데 스파게티를 먹으려면 포크가 2개 있어야 있어야 한다고 해봅시다.

만약 P1이 좌,우의 포크를 이용하여 스파게티를 먹는다면 P2는 먹을 수 없겠지요.

우리가 이것을 모니터로 어떻게 구현할 수 있을까요?

일단 P는 프로세스가 될 것이고 포크는 Shared Data가 될 것입니다.

일단 제일 먼저 먹기 위해선 포크를 집어야 할 것입니다.

따라서 pickup(i)에서 포크를 집고, 먹고, 포크를 내려놓고, 생각하고 끝내는 메커니즘을 가집니다.

자, 최초의 상태에서는 다들 포크를 2개씩 사용할 수 있을 것입니다.

그러므로 제일 먼저 확인해야할 것은 자신에게 포크가 2개 있는지를 확인해야합니다.

그래서 만약 2개가 아닐 경우는 ready라는 큐에서 기다리게 합니다.

그러다가 포크가 있으면 자신의 오른쪽과 왼쪽의 포크를 하나씩 집게되고 자신의 오른쪽, 왼쪽 포크를 1 뺍니다.

이후 음식을 다 먹었으면 포크를 내려놓아야겠죠??

그러므로 오른쪽, 왼쪽의 포크를 +1해주어 내려놓습니다.

그 다음에 만약 오른쪽 나의 오른쪽에 있는 사람이 포크가 2개인지 즉, 기다리고 있었는지 여부를 확인합니다.

만약 그렇다면 오른쪽 사람을 깨워야 하기 때문에 signal()을 줄 것입니다.

왼쪽도 마찬가지입니다.

결국 자신이 포크를 이용하여 스파게티를 먹다가 다 먹으면 기다리고 있던 친구에게 포크를 넘겨준다는 내용으로 함축할 수 있겠습니다.

 

어려워 보이지만 재밌는 문제도 이렇게 풀어봤습니다.

확실히 세마포어, eventcount 등의 솔루션보다 훨신 쉽고 error가 발생 가능성이 적습니다.

다만, 지원하는 언어에서만 사용할 수 있고 컴파일러가 os를 이해하고 있어야 한다는 단점을 가지고 있습니다. 만약 언어로 이 프로그램을 짜게 된다면 기계어로 번역을 해야하고 이를 컴파일러가 수행합니다. 그런데 컴파일러가 적합한 기계어로 번역을 하려면 os를 이해해야만 가능하기 때문에 어려울 수 있겠습니다.

감사합니다.