[Operating System] Monitors

• Semaphore, Mutex는 물론 Synchronization 문제를 해결하는 데에 많은 도움이 되는 도구들이지만, 실제로 프로그래밍 시에 실수를 굉장히 자주하게 되는 부분이기도 하다.
• 간단한 high-level language construct를 이용하는 것이 좋다. -> Monitor가 있다.

Monitor Usage

• abstract data type(ADT)는 데이터와 데이터에 작용할 수 있는 함수들을 캡슐화한다.
• monitor type 또한 mutual exclusion을 구현하는 데에 사용되는 ADT이다.
  
• local variable은 local function으로만 접근 가능하다. -> OOP의 class와 비슷한 개념인듯.
• 기본적으로 monitor construct에는 동시에 하나의 프로세스만 존재할 수 있다.
• 이 외에도 condition struct가 존재해서 다양한 synchronization을 해결할 수 있다.
• condition variable
  • condition x, y;
  • x.wait() : 이 operation을 수행하는 프로세스를 suspend시키는데,
  • x.signal() : 다른 프로세스에서 x.signal()을 호출하기 전 까지 suspend시킨다.
    • 정확히 하나의 suspended process만 재개한다.
    • suspended process가 없다면, signal() operation은 아무 영향이 없다.
      <->
      semaphore의 경우 waiting process가 없더라도 signal operation은 value값을 증가시킬 수 있다. (물론 꽉찬 경우는 아니겠지만)
• 만약에 프로세스 P의 x.signal() operation이 suspended process Q를 resume시키기 위해서는, monitor에서 동시에 수행되지 않아야 하므로 P는 wait 상태로 바뀌어야 한다. 이와 관련해 두 가지 경우가 존재한다.
  1. Signal and wait : P는 Q가 monitor를 빠져 나가거나 다른 condition을 위해 기다리기 전까지 wait된다.
  2. Signal and continue : Q는 P가 monitor를 빠져 나가거나 다른 condition을 위해 기다리기 전까지 wait된다.
• 각각에는 장단점이 있다.
• 이미 P가 실행중이었으므로, signal-and-continue 방법이 더 그럴듯하다. 하지만, 이 경우 Q가 불린 시점에서의 필요한 값이 P가 계속 실행되면서 사라지거나 바뀌어 버릴 수 있기 때문에 즉각적인 조치가 필요한 상황에서는 별로 좋지 않다.
• 둘 다 쓰까놓은 방법도 존재하는데, P가 signal을 하고 나서 바로 monitor를 빠져나가버리는 것이다.

Implementing a Monitor Using Semaphores

• 우선 각 monitor의 mutual exclusion을 위해서 binary semaphore mutex(initialized to 1)가 필요하다. enter전에 wait(mutex), leave 후에 signal(mutex)를 해야 한다.
• 위의 두 가지 방법중에 signal-and-wait방법을 사용할 것이다.
• signaling process는 resumed process가 leave나 wait하기 전까지 wait해야 하므로 추가적인 binary semaphore next가 필요하고, 0으로 초기화되어 있다. integer-value next_count 또한 next에 suspended 되어있는 프로세스의 수를 세는 데 필요하다.
  
  • 각 external function F는 위와 같이 바뀌게 된다.
  • 완전한 구조는 아니지만 이런 식으로 작동한다고 생각하면 될 것 같다.
  • monitor에 들어가기 전에 wait(mutex)를 실행하고, 이것저것 실행하다가 next에 의해 wait된 프로세스가 있다면(signal을 실행하고 멈춘 프로세스) 그것을 먼저 실행시키고, 없으면 signal(mutex)를 실행한다.
• condition variable의 경우 구현되는 방법
  • 각 condition x에 대해서 binary semaphore x_sem과 integer variable x_count가 필요하고, 둘 다 0으로 초기화되어 있다.
  • x.wait()의 구현
    
    • x_count를 증가시켜서 x.signal()이 wait중인 프로세스가 있을 때에만 작동하도록 한다.
    • 마찬가지로 next_count > 0이라면 next를 우선으로, 아니라면 mutex를 실행.
    • signal-and-wait을 구현해야 하므로 signal 후에 바로 wait(x_sem)를 실행한다.
  • x.signal()의 구현
    
    • x.signal() 실행 후에는 wait이 되어야 하고, next에 담겨야 하므로 next_count를 증가시키고 x.wait()을 구현하는데에 쓰인 x_sem semaphore에 대한 signal을 해주고, 그 이후에 wait(next)을 한다.
• 이와 같은 구현은 Hoare과 Brinch-Hansen의 minitor 정의에 부합한다.

Resuming Processes within a Monitor

• 여러 프로세스들이 condition x에 대해 suspend되어 있고, x.signal()이 호출되었을 때 어떤 프로세스가 먼저 실행되어야 하는 문제가 생기게 된다.
• 무지성 FCFS ordering -> 간단, but 적합하지 않은 상황이 다수 발생 -> conditional-wait construct가 쓰인다.
• x.wait(c)의 꼴을 가진다.
  - c : priority number
  - 프로세스가 wait할 때 c의 priority를 가진 상태로 wait하게 된다.
  - x.signal()이 호출되었을 때, smallest priority number를 가진 프로세스가 먼저 실행된다.
  
• 위 예시를 보자.
• 각 프로세스는 하나의 resource를 두고 경쟁하고 있다.
• 프로세스가 resource를 요청할 때, 그 자원을 사용하는 데에 필요한 최대 시간을 같이 명시해준다.
• monitor는 shortest time-allocation 우선으로 할당해준다.
• 이 monitor를 이용해서 자원을 할당받는 프로세스는 다음과 같이 동작한다.
  
  • R은 ResourceAllocator의 instance이다.
• 위의 방법처럼 monitor를 사용했을 때에 발생할 수 있는 문제점들
  • 프로세스가 resource에 permission을 얻지 않고 resource를 얻을 수 있다.
  • 프로세스가 resource를 얻고 나서 release를 하지 않는다.
  • 프로세스가 요청하지도 않은 resource에 release시도를 할 수 있다.
  • 프로세스가 같은 resource를 release하지 않고 두 번 request할 수 있다.
• 결국, 처음 monitor가 등장하게 된 원인이 완전히 제거되지 않았다고 볼 수 있다. (결국 semaphore를 사용했을 때와 동일한 문제들에 해당함.)
• 해결방법? : ResourceAllocator monitor 내부에 resource-access operation 집어넣기
  -> 단점 : scheduling이 monitor에 의해서 이루어진다.(내 맘대로 스케줄링 못함)
• 두 가지를 체크해야 한다.
  1. user process는 monitor call을 순서에 맞게 실행해야 한다.
  2. uncooperative process는 monitor를 통해서가 아닌 직접 접근을 통해서 shared resource를 접근하려고 한다는 것을 주의해야 한다.
     -> time-dependent error를 막을 수 있고, scheduling algorithm도 우리 입맛에 맞게 짤 수 있다.
• 사실 아직 정확하게 이해는 못함. 왜 쓰는지를 모르겠다. -> 예제 좀 찾아봐야 될 듯.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition