6.2 The Critical-Section Problem

 프로세스 동기화를 고려할 때, 빼놓을 수 없는 논쟁이 critical-section problem이다. n개의 프로세스가 있다고 치자(P_0, P_1, ..., P_(n-1)) 각 프로세스는 공유 데이터에 접근하고 수정하는 critical section이라는 구역이 있다. 시스템은 이러한 critical section만 무사히 건너기만(하나의 프로세스만 그 section을 실행하도록) 하면 될 것이다.

 이를 위해 프로세스 간에 프로토콜을 설계해야 한다. 즉, 프로세스가 이 critical section에 진입하기 위한 허가 요청(request)이 필요하다는 것이다. 이 요청을 구현하는 코드 부분이 진입 섹션(entry section)이라고 하며, 진입이 된 상태면 critical section 을 실행하며, 그 뒤 따라 종료 섹션(exit section) 올 수 있게 된다(나머지 코드는 나머지 섹션(remainder section) 이라고 한다).

while (true) {
  /* 1. entry section
  
     2. critical section
  
     3. exit section
  
     4. remainder section */
}

위의 코드는 다음 요구사항(M.P.B.)을 만족해야 한다.

1. Mutual Exclusion(상호배재의 원칙): 프로세스 P_i가 critical section에 있다면, 어떤 프로세스도 critical section에 진입할 수 없다. 즉 entry section에 머물러 있어야 한다.
2. Progress(진행의 원칙): 만약 어떤 프로세스도 critical section에 있지 않고, 여러 프로세스가 critical section에 들어가고 싶다면, 그 프로세스들 중에 remainder section에 들어가보지 못한 프로세스들만이 critical section에 들어갈 수 있도록 하나의 프로세스를 결정해야하며, 이 결정이 무기한 연기되어선 안된다.
3. Bounded Waiting(유한 대기의 원칙): 한 프로세스가 critical section에 들어가려고 기다리는 동안에, 다른 프로세스들이 critical section에 들어가는 횟수에 제한을 두어야 한다.

 위의 원칙에 따라 다음 두 예제를 보자.

 두 프로세스가 동일한 파일에 접근을 하려고 했을 상황을 보자. 만약 두 개의 파일이 동시에 열리고, 서로 다른 곳을 수정하고 파일을 닫으려고 할때, 업데이트 되는게 서로 다르기 때문에 race condition이 발생할 수 있게 된다.

 또 다른 예로는 위에 두 프로세스가 자식 프로세스를 만들려고할 때, 같은 pid를 가진 자식이 두 개 생길 수 있다는 것(쌍둥이(?))이다. 프로세스 id는 고유한 식별자로서 primary key가 되어야 하기 때문에 이러한 일을 방지해야 한다.

 위 두 상황 모두 Mutual Exclusion에 위배되는 상황이기 때문에 이를 위해 커널이 사용하는 데이터 구조는 데이터를 수정하는 동안에 인터럽트가 발생하지 않도록 하는 장치가 있다. 이를 통해 critical section 문제를 해결할 수 있고, 이 방식으로 명령어 순서가 소멸되지 않고 실행되기 때문에 공유 변수에 대한 예기치 못한 수정이 일어나지 않게 된다.

 하지만 이런 솔루션이 멀티프로세서 환경에서 잘 동작하지 않을 수 있는데, 멀티프로세서에서 인터럽트를 비활성화 하는 것은 모든 프로세서로 메시지를 전달해야 하기 때문에 시간이 오래 걸린다. message passing은 각 크리티컬 섹션 진입을 지연시키고, 시스템 효율성을 저하시키기 때문에 시스템 클럭에 미치는 부정적인 영향을 고려해야 한다.

 운영체제에서 critical section을 처리하는 데 두 가지 일반적인 접근법이 사용된다. 하나는 preemptive kernel, 다른 하나는 nonpreemptive kernel이다. preemptive 라는 개념은 스케줄링 알고리즘에서 많이 봤으니 설명은 생략한다. 공통적으로 커널 모드 프로세스는 커널 모드를 종료하거나 차단하거나 CPU의 제어를 자발적으로 양도할 때까지 실행된다.

 물론 이런 nonpreemptive kernel 은 커널 데이터 구조에 대한 race condition이 없으며, preemptive kernel 에 대해서는 이러한 말을 할 수가 없기 때문에 커널의 shared data 방식은 race condition에서 자유로워야 한다. preemptive kernel 은 특히 SMP 아키텍처에 대해 설계가 어렵다. 왜냐면 이런 환경은 서로 다른 CPU 코어에서 동시에 두 개의 커널 모드 프로세스가 서로 경쟁하면서 실행될 수 있기 때문이다. 여기서 preemptive kernel은 CPU를 대기중인 프로세스에게 양도하기 전에 커널 모드 프로세스가 임의로 긴 시간동안 실행되지 않을 가능성이 적으므로 더 빠르게 반응할 수 있다. 게다가 선점 커널은 실시간 프로그래밍에 더 적합하며, 이러한 이유들로 인해 nonpreemptive보다는 preemptive kernel을 쓰게 된다.