[운영체제] Monitors

💡MONITORS

Problems of semaphore :

• difficult to code
• difficult to prove correctness
• requires volumtary cooperation
• single misuse affects entire system

세마포어를 사용하기에는 사용자 입장에서 코딩하기가 어렵다 보니 보다 쉬운 monitor가 도입된 계기를 만들었다.

 

monitior

• 응용프로세서가 효과적으로 호출할 수 있도록 하는 동기화 메커니즘
• a high-level abstraction that provides a convenient and effective mechanism for process synchronization

semaphore 사용 시 일어날 수 있는 상황

 

>> Mutual Exclusion property is violated

: mutex의 값을 증가시키는 signal 함수만 호출되어서

critical section에 여러 개의 process 가 들어와서 mutual exclusion을 위배한다.

 

>> Deadlock occurs

: mutex의 값을 감소시키는 wait 함수만 호출되어서

어떤 프로세스도 critical section 에 들어갈 수 없고 프로세스들 모두가 wait 함수에서

빠져나오지 못해 deadlock 이 걸리는 상황이 발생한다.

GOAL : Only one process at a time can be active within the monitor

Monitor는 class 와 매우 유사하게 구현하고 있다.

Critical Section에 1개의 process 만 들어오게 하기 위해서 즉 mutual exclusion 을 만족하기 위해서

class에

• Condition Variable 추가
• Wait, Signal 추가 >> condition variable에 접근할 수 있는 함수

1. Condition Variable하나의 프로세스만 active하고, 다른 프로세스는 기다리게 하도록 도입된게 condition 변수 입니다.
   condition 변수가 있어야 mutual exclusion 을 보장할 수 있습니다.
   condition 변수에 접근이 가능한 함수는 오직 wait 과 signal 함수만 가능합니다.
2. wait()
   세마포어의 wait 함수는 while을 문을 만족해야 suspend 상황이 발생하지만
   Monitior의 wait 함수는 호출되면 무조건적인 suspend 상황을 발생시킵니다.
   즉 wait 함수를 호출한 프로세스는 컨디션 변수를 기다리는 큐에 insert 되도록 합니다.
3. singal()
   signal 함수는 wait 함수에 의해 큐에서 기다리고 있는 프로세스를 깨우는 함수입니다.

Monitor Code

 

 

 

 

 

 

 

1. 공유 변수 busy 는 처음에 false라서 처음 진입하는 프로세스는 조건문에 걸리지 않아 바로 critical section 에 즉 resource에 접근이 가능합니다.

2. 이후 이 프로세스는 busy 를 true로 바꿉니다.

3. 두번째로 오는 프로세스는 if 문에 걸려서 wait 함수를 호출합니다

 >> mutual exclusion 속성 보장을 위해.

 

 

위에 사진처럼 monitor는 구현되어 있지만. 사용자는 옆에 사진처럼 함수만 호출하면 되는 아주 편리한 기능을 제공합니다.

즉 acquire() 를 통해 resource를 확보하고,

release()를 통해 리소스를 놓아 줍니다.

 

💡Liveness

Monitor를 사용 시에 synchronization을 지키기 위해 가장 중요한 함수는 wait 함수 입니다.

즉, 두 번째로 오는 프로세스는 첫 번째 프로세스가 critical section에 있으면 기다리게 됨.

wait 함수를 잘못 사용하게되면 프로세스가 아예 progress를  안하게 되는데 이것을 "DeadLock" 이라고 한다.

"deadlock"은 어떤 경우에도 빠져나갈 수 없는 경우를 말하며 이를 "indefinite block" 이라고도 한다.

💡Deadlock

two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

즉, 두 개 이상의 프로세스가 무한정 수행이 안되는 경우를 의미한다.

1. S와 Q를 1로 초기화 ( == binary semaphore)

2. p1이 wait(Q)를 호출 Q=0 으로 바뀜

3. Context Switch 돼서 P0 가 wait(S)를 호출해서 S가 0으로 바뀜.

4. 다시 context switch 되어 p1이 wait(s) 호출 시에 s=0이므로 밑으로 수행 안됨 즉 wait 함수 빠져나가지 못한다.

5. p0에서도 wait(q) 호출 시 빠져나가지 못함. 

두 개의 프로세스 다 wait함수 빠져나가지 못해 deadlock

+ starvation : indefinite blocking. A process may never be removed from the semaphore queue in which it's suspended 

                      deadlock과의 공통점은 무한정으로 waiting하는 것.

💡Bounded buffer problem

Producer / Consumer process가 따로 있고,

공유 변수는 circular queue로 구현

mutex는 producer와 consumer 모두 circular queue에 접근하기에 필요하다.

• Binary
  mutex의 값이 1이나 0인 경우
• counting
  mutex의 값에 제약 조건 없이 정수 값을 가짐.

ch 3장 에서는 Synchronization을 위해 Spin Lock 을 사용했었음.

Counting 의 경우에는 full 함수는 producer가 차있는 갯수를 나타내고 empty 함수는 비어있는 슬롯의 개수를 나타냅니다.

Full 0으로 초기화 / empty 는 N으로 초기화

• Producer : empty가 0이라면 wait(empty) 에 진입
• Consumer : full이 0이라면 wait(full) 에 진입

 

1. 버퍼의 크기를 체크하는 것은 wait(empty)로

2. producer가 critical section에 진입했다면 consumer는 진입하지 못하게 설정하기 위해 wait(mutex)로 관리한다.

cf. critical section은 여기서 버퍼를 채우는 영역이다.

3. critical section에서는 buffer에 item을 추가한다.

4. signal(mutex)로 mutex 값을 1로 바꾸고 consumer도 c-s에 진입 가능하게 해준다.

5.signal(full)을 호출로 buffer에 한 개 추가됐다고 설정해준다.

---

1. wait(full) : buffer에 차 있는 것이 없다면 waiting

2. wait(mutex) : producer가 critical section 에 진입해 있다면 mutex의 값은 0으로 consumer는 waiting

3. signal(mutex)

4. signal(empty) : buffer에 있는 아이템을 사용했기에 비어있는 공간이 늘어났다고 설정해준다.

 

 

 

---

>> Dining-Philosophers Problem

: 다섯 명의 철학자가 같이 밥을 먹는데 젓가락이 철학자 사이에 하나씩 있고 서로 share한다고 가정한다. 한 사람이 젓가락을 사용하면 옆 사람을 기다려야하는 상황이다.

다섯 명의 동기화를 위해서 spinlock 사용은 복잡하여 semaphore 변수를 사용한다.

 

 

 

---

chopstick[5]는 다 1로 초기화.

chopstick[i]는 본인 기준 왼쪽 젓가락

chopstick[ (i+1) % 5 ] 는 오른쪽 젓가락

 

둘 중 하나라도 wait 문을 빠져나오지 못한다면 젓가락 사용 불가.

두 개를 다 확보했더라면

// eat

식사가 끝나면 왼쪽.오른쪽 젓가락에 대한 signal 함수를  호출

semaphore 값 1증가 다른 철학자 식사 가능

 

---

문제점 : Deadlock

다들 첫 번째 line인 왼쪽 젓가락을 가지고 있고, 오른쪽 젓가락의 available을 기다리면 아무도 식사 못하는 deadlock 상황.

Solution 1 : 동시에 앉을 수 있는 철학자는 최대 4명으로 설정

Solution 2 : 두 개의 젓가락을 집는 것을 atomic 하게

Solution 3 : 젓가락 집는 순서 명시

    (1) Odd philosopher 는 왼쪽 젓가락 먼저

    (2) Even philosopher 는 오른쪽 젓가락 먼저