[OS / 운영 체제] Monitors, Condition Variable, Implementing a Monitor Using Semaphore, Deadlock and Starvation, Bounded Buffer Problem

 

Monitors

Monitor에서 실행할 수 있는 것 자체가 Resource이다. Spin lock과 Block의 방법으로 Waiting 시키는 방법을 사용한다. Waiting 은 Linked List로 구현을 한다. Monitor 자체는 Mutual Exclusion을 지원하기 때문에 신경쓰지 않아도 된다. 

 

Monitor in Java

synchronized라는 키워드를 제공한다. 메소드를 정의할 때 사용을 하면 한 번에 하나의 Thread만이 실행될 수 있는 함수인 것이다. System.Threading.Monitor의 특성을 전해 받으면 Monitor의 특성을 가질 수 있게 된다.

 

 

Condition Variable

얼음 땡 놀이. 변수를 선언하고 x.wait으로 실행을 하면 얼음과 동일한 상태가 된다. Signal을 보내면 땡을 해서 다시 실행할 수 있게 된다. wait() signal()은 Semaphore에서 들어봤다. 굉장히 비슷한 역할을 한다. 하지만 아주 중요한 차이점이 존재한다. 첫 번째 Process가 들어오더라도 wait을 만나면 멈추게 된다. 또한 아무도 기다리고 있지 않으면 signal을 실행하지 않는다. 

Semaphore도 첫 번째 Process부터 멈추게 하는 방법. S가 0에서 시작하게 하면 된다. 

 

 

Condition Variable

Q가 첫 번째 Process라고 해보자. Monitor 안에 들어갈 수 있다. x.wait()을 호출하게 되면 멈추게 된다. 멈추는 순간 기다리는 친구들을 넣게 해줘야 하는지 아닌지를 생각해봐야 한다. 기다리는 Process들을 집어넣야 한다. 만약 기다리는 Process를 놔두게 되면 무슨 일이 벌어지는가. 영원히 wait하는 상태가 될 수 있다. 그래서 다음 Process가 들어와서 signal을 보내서 땡하게 해준다. 이때 두 가지 Process가 살아있기 때문에 둘 중 하나를 재워야 한다. signal and wait은 잠 자던 프로세스를 깨우고 자신은 멈춘다. Signal and continue의 경우 Singal만 보내고 자신을 실행시킨다. 순서가 정확히 이해되어야 한다. 

 

 

Implementation a Monitor Using Semaphore

1. Exclusive

2. wait

3. Signal 

3가지를 연관되게 구현을 해야 한다. 

 

mutex 변수는 mutual exclusive를 보장하기 위한 함수. 초깃값은 1이다. 만약 0으로 초기화된다면 첫 번째 Process부터 막힌다. 그 Process를 깨우는 방법은 Signal밖에 존재하지 않는다. wait()을 하고 signal()로 깨워준다. 

next에 대해서 signal을 보낸다는 의미가 존재한다. 이는 첫 번째 Process가 나가면서 mutex를 1로 증가하는 것이 아니라 현재 next에 대해서 wait한 Process를 깨워져야 한다. 하지만 Next에 의해서 wait된 Procress들이 몇 개인지 개수를 세어야 한다. 이때 counter의 값을 활용한다. 기다리는 친구가 없으면(counter == 0) Mutex를 증가시켜줘야 한다. 

 

Implementing a Monitor Using Semaphore

mutex의 초깃값은 1로 되어야 Mutually Exclusive를 보장해줄 수 있다. 

 

 

Implementing a Monitor Using Semaphore

x_sem은 0으로 초기화 해야 한다. 이렇게 되면 첫 번째 것을 포함해서 멈추게 할 수 있다. x_count 는 x에 대해서 기다리는 친구를 셀 것이다. 기다리는 Process의 숫자가 없으면 signal을 작동하지 않을 것이므로 필요한 변수이다. 

wait

x_count++로 기다리는 프로세스가 증가되었음을 표시한다. wait(x_sem)에서 s_sem이 0으로 초기화되었으므로 무조건 멈추게 된다. 

깨워줄 수 있는 상황은 두 가지가 존재한다. wait을 하고 다음 프로세스가 들어와서 깨워주는 경우. wait하고 signal 받고 다시 wait을 하게 되는 경우 깨워줘야 하는 것이 기다리는 Process인지 Next에 대해 wait을 하고 있는 Process인지를 확인해야 한다. 

signal

signal(x_sem)은 무엇을 하는가. x_sem을 깨워주게 된다. 그리고 next에 대해서 wait을 하게 된다. next의 값은 0이다. 

 

 

Resuming Process within in a Monitor

제일 간단하게는 FIFO 또는 Random하게 깨우면 된다. 하지만 우선순위를 부여하면 깨우는 순서가 생기게 된다.

 

 

Liveness

Progress를 잘 만족하면서 진행되는 상황을 의미한다. 

 

 

Deadlock and Starvation

P0와 P1이 동시에 실행되면 P0는 P1을 기다리고 P1은 P0를 기다리게 된다. 

 

Priority Inversion

 

 

7장. Synchronization Examples

 

 

Bounded Buffer Problem

Buffer의 size가 n으로 제한되어 있다. 빈 공간의 개수는 Producer 입장에서 Resource이고 Item의 개수는 Consumer의 입장에서 Resource가 된다.

 

 

Bounded Buffer Problem

counting semaphore를 사용해서 빈 칸의 개수를 셀 수 있다. Data item을 Counting Semaphore로 나타내어야 한다. empty의 초깃값은 n이 된다. full 은 0으로 초기화가 되어야 한다. 만드는 코드는 Remainder section이고 집어 넣는 코드가 Critical Section이 된다. wait(empty)는 empty라는 자원을 하나 소비하겠다고 하는 것이다. empry에 대해서 signal을 호출한다. 

Consumer의 입장에서 full의 item을 사용하고 empty에 대해서 signal을 호출해야 한다.