6.7 Monitors

세마포어가 프로세스 동기화를 위한 편리하고 효과적인 메커니즘을 제공하지만, 이를 잘못 사용하면 특정 실행 순서에서만 발생하는 타이밍 오류로 인해 감지하기 어려운 문제가 생길 수 있다(프로그래머가 잘못 짤 경우임). 이러한 오류는 항상 발생하는 것이 아니기 때문에 더욱 발견하기 어렵다. 생산자-소비자 문제의 해결책에서 카운트를 사용하는 예를 통해 이러한 오류를 본 적이 있을 것이다(컴파일러의 최적화 때문에 재배열 때문), 이 Mutex Lock이나 Semaphore 마저도 사용할 때도 여전히 타이밍 오류가 발생할 수 있다...

 모든 프로세스는 1로 초기화된 binary semaphore 가 가지는 변수인 mutex를 공유하며, critical section에 진입하기 전에 wait(mutex)를 실행해야 하고, exit section에서 signal(mutex)를 반드시 실행해야 한다. 이 순서를 안지키면 두 프로세스가 동시에 임계 구역에 있을 수 있다(항상 말하지만 재배열 때문).

 이런 잘못된 상황은 다양한데 다음과 같다.

• 프로그램이 semaphore의 mutex 변수에 대해 wait(mutex) 및 signal(mutex) 작업이 실행되는 순서가 바뀌었다고 가정하자.
  signal(mutex);
  ...
  critical section
  ...
  wait(mutex);
  그러면 여러 프로세스가 중요한 섹션에서 동시에 실행되어서 Mutual Exclusion 요구사항을 위반할 수 있다. 이 오류는 여러 프로세스가 동시에 자신의 임계 구역에서 활성화 됐을 때 발생 할 수 있다(재현하기는 힘들 수 있음).
  
  
• 만약 signal자리에 wait가 들어갔다고 해보자.
  wait(mutex);
  ...
  critical section
  ...
  wait(mutex);
  이 경우는 모든 프로세스가 wait에 걸려서 Bounded Waiting과 Progress가 위배되는 상황이다.
  
  
• 프로세스가 wait(mutex)나 signal(mutex) 또는 둘 다를 생략한다고 가정하자. 이 경우 Mutual Exclusion이 위반되거나 프로세스가 영구적으로 차단된다.
  
  

 위는 모두 설계자가 잘못 코드를 짠 형태이다.

 이러한 예시들은 프로그래머가 critical section 문제를 해결하기 위해 semaphore 나 mutex lock 을 잘못 사용할 때 발생하는 다양한 유형의 오류이며,  이러한 프로그래밍적 오류를 다루는 한 가지 해결법은 high-level language 에서 간단한 동기화 도구를 포함시키는 것이다. 대표적인 예가 바로 Monitor이다.

 

6.7.1 Monitor Usage

 ADT(Abstract Data Type)를 먼저 보면 데이터를 encapsulation하고 조작하는 일련의 function들이 테이블 처럼 짜여져 있는 구성이다. monitor type 이라는 것은 프로그래머가 정의한 연산(function 같은거)들의 집합을 포함하는 ADT로, 모니터 내에서 Mutual Exclusion을 제공한다(semaphore와 다른점, 세마포어를 자체적으로 가지고 있어서 실행할 것만 넣어주면 그만). monitor type은 그 타입의 인스턴스 상태를 정의하는 변수(condition)들과 그 변수를 조작하는 함수들의 설계도라고 볼 수 있다.

monitor monitor name
{
  /* shared variable declarations */
  
  function P1 ( ... )
  {
    ...
  }
  
  function P2 ( ... )
  {
    ...
  }
  
  ...
  
  function Pn ( ... )
  {
    ...
  }
  
  initialization_code ( ... )
  {
    ...
  }
}

 

 모니터 타입의 표현은 다양한 프로세스에 의해 직접적으로 사용되는게 아니라서 모니터 내에서 정의된 함수는 오직 모니터 내에서만 사용하고 모니터 내의 변수들만 그것의 매개변수로 들어갈 수 있으며, 모니터 내의 변수들 또한 모니터 내의 함수들끼리만 접근할 수 있다(완전히 독립된 코드 조각이라고 보면 됨). 모니터는 한 번에 하나의 프로세스 만이 모니터 내에서 활동할 수 있도록 보장하며, 이 동기화 제약을 명시적으로 코딩할 필요가 없다.

 하지만 정의된 모니터 구조만으로는 모든 동기화 체계를 모델링하는데 충분히 강력하지는 않아서 추가적인 동기화 메커니즘이 필요할 수 있다. 이런 메커니즘은 condition 변수에 의해 제공된다.

condition x, y;

condition에서 호출 할 수 있는 유일한 연산은 wait(), signal() 뿐이다.

x.wait();
x.signal();

 x.wait() 연산은 호출하는 프로세스가 다른 프로세스가 signal을 호출할 때까지 중단되어 있음을 의미하며, x.signal() 연산은 정확히 하나의 중단된 프로세스에 대해 다시 실행하도록 한다(아무도 block된게 없으면 signal은 그냥 아무것도 안함). 이를 semaphore와 비교해본다면 세마포어 signal은 항상 semaphore의 상태에 영향을 주게 되지만 monitor의 signal은 monitor 그 자체로 있기 때문에 어떠한 상태를 가지고 있지 않고, 단지 활성화 된 프로세스를 관리하기만 하면 된다. 모든건 "condition이 알아서 해주기 때문"이다.

 프로세스 P가 x.signal() 연산을 호출할 때를 생각해보자. 만약 condition 변수 x와 관련된 중지된 프로세스 Q가 있다면, P가 `x.signal()`을 호출하면 중지된 프로세스 Q가 실행을 재개할 수 있게 된다. 이때 신호를 보내는 프로세스 P는 기다리게 된다.
(하지만, 이론적으로는 두 프로세스가 모두 실행을 계속할 수도 있다!)

 

이제 Monitor 내에서는 기본적으로 두가지 상황으로 정리될 수 있다. 프로세스 P, Q가 있다고 가정하고, Q는 대기중인 프로세스라고 가정하자.

1. Signal and wait: P가 signal을 호출하면, Q가 모니터를 떠나길 기다리거나 아니면 P가 다른 condition의 signal 을 기다리거나 이 말은 즉슨
   1. P가 signal을 호출하여 Q를 깨운 후, P는 모니터 내부에서 더 이상 진행하지 않고 대기 상태로 들어감
   2. Q가 깨어나서 모니터 내부에서 작업을 수행하고 모니터를 떠날 때까지
      P는 기다리거나 아니면 P는 다른 condition에 대한 signal을 기다리거나
      
      
2. Signal and continue: P가 signal을 호출하면, Q는 P가 모니터를 떠날 때까지 기다리거나, 다른 조건을 기다리거나 이 말은 즉슨
   1. P가 signal을 호출하여 Q를 깨운 후, P는 계속해서 모니터 내부에서 작업을 수행함
   2. Q는 P가 모니터 내부에서 작업을 완료하고
      P가 모니터를 떠날 때까지 기다리거나
      Q는 다른 condition에 대한 signal을 기다리거나

 위의 두 가지 직면 가능한 상황이 있다. P가 이미 모니터에서 한 번 실행됐던 적이 있기 때문에 Q가 계속 실행되는 signal-and-continue의 방법이 더 맞는 것으로 보이지만, P를 계속 수행하게 된다면, Q가 재개될 때 Q가 기다리던 논리적 조건이 더 이상 유효하지 않을 때 두 가지 선택 사이에 타협도 필요하다. 즉, P가 모니터를 떠날 때까지 Q는 대기 상태에 있으며, 이때 Q가 기다리던 조건이 이미 변경되어 더 이상 유효하지 않을 확률이 있다라는 것 그래서 프로세스 간의 동기화와 관련된 condition의 유효성을 고려해서 짜야함.

 

6.7.2 Implementing a Monitor Using Semaphore

이제 세마포어를 사용한 모니터를 구현해보자. 모니터에서 상호 배제를 위한 binary semaphore으로 mutex가 필요하고, 모니터에 들어가기 전에 wait(mutex)가 되어야 하며, 모니터를 떠난 후에는 signal(mutex)를 수행해야 한다.

 따라서 signal-and-wait 의 방식을 사용해서 신호를 보내는 프로세스는 재개된 프로세스가 떠나거나 대기할 때까지 기다려야 하므로 추가적인 binary semaphore로 next를 쓰고, 0으로 초기화 한다. 신호를 보내는 프로세스는 자신을 일시 정지시키기 위해 next를 사용할 수 있고, next에서 일시정시된 프로세스의 수를 세는 정수 변수 next_count가 따로 제공(next에 있는게 아님 그냥 따로 있음)되게 된다. 그래서 모니터 외부에서 실행될 함수는 다음과 같다.

 

 각 condition x에 대해서 binary semaphore x_sem 과 정수 x_count를 넣고, 둘 다 0으로 초기화하며, x.wait() 연산을 다음과 같이 구현 가능하다.

// x.wait()

x_count++;
if (next_count > 0)
    signal(next);
else
    signal(mutex);
wait(x_sem);
x_count--;

x.signal은 다음과 같다

// x.signal()

if (x_count > 0)
{
  next_count++;
  signal(x_sem);
  wait(next);
  next_count--;
}

monitor ResourceAllocator
{
  boolean busy;
  condition x;
  
  void acquire(int time)
  {
    if (busy)
      x.wait(time);
    busy = true;
  }
  
  void release()
  {
    busy = false;
    x.signal();
  }
  
  initialization_code()
  {
    busy = false;
  }
}

위 구현은 Hoare and Brinch-Hansen이 제시한 모니터의 정의에 적용된다. 하지만 위보다 더 효율성을 크게 향상시키는 구현 또한 가능하다.

 

 condition variable은 다중 스레딩 프로그래밍에서 스레드 간의 동기화를 위해 사용되는 프로그래밍 구조다. condition variable은 특정 조건이 충족될 때까지 스레드가 대기하게 할 수 있고, 충족되면 대기하고 있던 스레드를 깨워서 실행을 재개하게 한다. 이런 조건 변수는 일반적으로 shared data에 대한 접근 제어나 특정 상태의 변경을 기다리는 용도로 사용된다. 제시된 코드는 조건 변수 x의 wait 연산을 구현한 것이며, 여기서 x_count 는 x condition을 기다리고 있는 스레드의 수를 세는 변수이며, x_sem은 해당 조건 변수를 위한 세마포어이다.

 

6.7.3 Resuming Processes within a Monitor

 이제 모니터 내에서 어떤 프로세스에게 자원을 먼저 할당시킬 것인지에 대해 보자. 이전에 봤던 scheduling 알고리즘들이 여기서 쓰이는데, 가지 간단한 해결책은 선입선출(FCFS) 순서를 사용하는 것으로, 가장 오래 기다린 프로세스를 먼저 재개한다. 그러나 실제 상황에서는 이러한 단순한 스케줄링 방식은 미흡하다. 이러한 상황에서 conditional-wait 구조를 사용할 수 있다.

x.wait(c);

여기서 c는 wait() 연산이 실행될 때 평가되는 정수 표현식으로, priority number라고 불린다. priority number는 중단된 프로세스의 이름과 함께 저장되며, x.signal()이 실행될 때, 가장 작은 우선순위 번호를 가진 프로세스가 먼저 실행되게 된다.

monitor ResourceAllocator
{
  boolean busy;
  condition x;
  
  void acquire(int time)
  {
    if (busy)
      x.wait(time);
    busy = true;
  }
  
  void release()
  {
    busy = false;
    x.signal();
  }
  
  initialization_code()
  {
    busy = false;
  }
}

 이전에 봤던 ResourceAllocator 모니터를 보자. 이 모니터는 경쟁 프로세스 사이에서 단일 자원의 할당을 제어하고, 자원을 요청하는 각 프로세스는 자원을 사용할 계획인 최대 시간(변수 priority number)을 지정하게 된다. 여기서 모니터는 가장 짧은 시간 할당 요청을 가진 프로세스에게 자원을 할당하게 된다. 자원 접근은 추후에 나오겠지만, 다음과 같은 절차를 따라야 한다.

R.acquire(t);

...

access resource;

...

R.release();

(여기서 R은 ResourceAllocator의 인스턴스)

 여기서 모니터 개념은 또 다른 문제를 직면하는데, 앞서 언급된 자원 접근 순서가 보장되지 않는다. 이 때문에 다음과 같은 문제가 발생할 수 있다.

- 프로세스가 자원에 대한 접근 허가(lock)를 먼저 얻지 않고 자원에 접근하는 경우
- 프로세스가 자원에 접근 허가를 받은 후에 자원을 절대로 해제하지 않는 경우(bounded wait X)
- 프로세스가 요청한 적이 없는 자원을 해제하려고 시도할 수 있음
- 프로세스가 해당 자원을 해제하지 않고, 동일한 자원을 중복 요청할 수 있음

세마포어를 사용할 때도 같은 어려움이 발생하며, 이러한 어려움은 모니터 구조를 처음 개발하게 된 동기와 유사하다. 이전에는 세마포어의 올바른 사용에 대해 걱정해야 했지만, 이제는 컴파일러가 더 이상 도움을 줄 수 없는 high-level 에서 프로그래머들이 자원의 올바른 사용에 대해 걱정을 하게 된다.

 프로그래머들이 이런 까다로운 문제를 겪게 하지 않도록 한 가지 가능한 해결책은 ResourceAllocator 혹은 Monitor 내에서 자원 접근 작업을 포함하는 것인데, 이 방법을 사용하면 내장된 모니터 스케줄링 알고리즘에 따라 스케줄링이 이루어지기 때문에, 프로세스가 적절한 순서로 실행되도록 보장하려면 ResourceAllocator 모니터와 관리되는 자원을 사용하는 모든 프로그램들을 전부 검토해야 한다.

 이 시스템의 정확성을 확립하기 위해 두 가지 가정이 들어가야 한다.

1. 사용자 프로세스는 모니터에서 호출을 올바른 순서대로 수행해야 함 - Monitor나 Resource Allocator 에서 제공하는 메서드를 올바른 순서대로 호출해야만 한다는 것, 예를 들어 자원을 요청하기 전에 반드시 자원 할당기에 접근하여야 하며, 자원 사용이 끝나면 반드시 자원을 반환해야 함.
   
   
2. 비협조적인 프로세스가 모니터가 제공하는 상호 배제 게이트웨이를 무시하고 공유 자원에 직접 접근하지 않도록 해야 함 - Monitor나 Resource Allocator 가 제공하는 상호 배제 메커니즘을 무시하고 공유 자원에 직접 접근하려는 프로세스가 없어야 함. 즉, 모니터가 제공하는 동기화 기능을 억지로 우회하거나 무시하지 말아야 함.

 이 두 가지 조건을 보장할 수 있을 때에만 시간 의존적 오류 없이 스케줄링 알고리즘이 성공적으로 실행할 수 있다. 하지만 이 두 조건이 성립되는 시스템은 작고 정적인 시스템에 대해서는 가능할 수 있지만, 대규모 시스템이나 동적 시스템에 대해서는 합리적이지 않을 수 있다. 이는 17장에서 논의한다.