chan blog: OS Chapter 5 : Process Synchronization

critical-section problem을 소개. 그것의 솔루션은 공유 데이터의 일관성을 보장하기 위해 사용될 수 있다.
critical-section 문제에 대해 소프트웨어와 하드웨어 솔루션 둘 다 보여준다.
몇 가지 고전적 프로세스 동기화 문제를 조사.
프로세스 동기화 문제를 해결하기 위해 사용되는 몇 가지 툴을 조사.

* Background

이 챕터에서, 우리는 concurrent or parallel execution이 여러 프로세스들에 의해 공유되는 data의 integrity를 포함한 문제들에 어떻게 기여할 수 있는지를 설명한다.
bounded buffer에 count 변수를 추가하여, 생산자와 소비자가 올리거나 줄인다고 했을 때 해결되는 것 처럼 보이지만, concurrently하게 실행될 때 정확히 실행되지 않을지도 모른다.
counter++와 counter--의 low level statements에서 살펴보면 lower-level 명령어들은 어떤 순서로 중간에 끼여들게 되는데, 그러한 끼어들기가 다음과 같다:

T0 : producer execute register1 = counter {register1 = 5}

T1 : producer execute register1 = register1 + 1 {register1 = 6}

T2 : consumer execute register2 = counter {register2 = 5}

T3 : consumer execute register2 = register2 - 1 {register2 = 4}

T4 : producer execute counter = register1 {counter = 6}

T5 : consumer execute counter = register2 {counter = 4}

우리는 두 프로세스들이 변수 counter를 concurrently하게 조작하는 것을 허용했기 때문에 부정확한 상태에 도달할 것이다. 몇 가지 프로세스들이 같은 데이터에 concurrently하게 접근하고 그 실행의 결과가 프로세스가 접근하는 특정 순선에 의존하는 이러한 상황은 race condition이라고 불려진다. 위의 race condition으로부터 보호하기 위해서, 우리는 한 번에 오직 한 프로세스만이 그 변수 counter를 조작할 수 있도록 보장할 필요가 있다. 그러한 보장을 하기 위해서, 우리는 그 프로세스들이 어떤 방식으로 synchronized 되는 것을 요구한다.
설명된 것과 같은 상황들은 운영체제에서 자주 발생하는데, 그 시스템의 다른 부분들이 자원을 조작하기 때문이다. 명확히 우리는 그러한 활동으로부터 발생하는 어떤 변화들이 서로를 간섭하지 않기를 원한다. 이 문제의 중요성 때문에, 우리는 이 챕터의 대부분을 cooperating processes사이의 process synchronization(프로세스 동기화)과 coordination(조정)에 헌신한다.

* The Critical-Section Problem

소위 critical-section problem을 이야기해서 프로세스 동기화를 고려하기 시작한다. n개의 프로세스들 {P0, ..., P(n-1)}로 구성된 시스템을 고려하자. 각 프로세스는 critical section이라고 불려지는 코드의 한 segment를 가지고 있는데, 거기에서 그 프로세스는 공통된 변수를 바꾸고, 한 테이블을 업데이트하고, 한 파일을 쓰거나 등등을 할 지도 모른다. 그 시스템의 중요한 기능은, 한 프로세스가 critical section에서 실행될 때, 어떠한 다른 프로세스도 그것의 critical section에서 실행되지 않도록 하는 것이다. 즉, 어떠한 두 개의 프로세스들은 그들의 critical sections에서 동시에 실행될 수 없다. 그 critical-section problem은 그 프로세스들이 협력하기 위해 사용할 수 있는 protocol을 설계하는 것이다. 각 프로세스는 그것의 critical section에 들어가기위해 허가를 요청해야 한다. 이 요청을 구현하는 코드의 section이 entry section이다. 그 critical section 다음에 exit section이 나올지도 모른다. 나머지 코드는 remainder section이다.
critical-section problem에 대한 솔루션은 다음의 세 가지 요구사항을 만족해야만 한다:

1. Mutual exclusion (상호배제) : 만약 process Pi가 그것의 critical section에서 실행하고 있다면, 그러면 어떠한 프로세스들이 그들의 critical sections에서 실행할 수 없다.
2. Progress (진행) : 만약 그것의 critical section에서 어떠한 프로세스도 실행되고 있지 않고, 어떤 프로셋드ㅡㄹ이 그들의 critical sections에 들어가길 원한다면, 그것들의 remainder sections에 실행되고 있지 않은 프로세스들만 그것의 critical section에 다음에 들어갈지를 결정하는데 참여할 수 있고, 이 선택은 무기한적으로 연장될 수 없다.
3. Bounded waiting (한정된 대기) : 한 프로세스가 그것의 critical section을 들어가는 요청을 하고난 후와 그 요청이 받아들여지기 전에 다른 프로세스들이 critical sections에 들어가도록 허용되는 횟수에 제한이 존재한다.

주어진 한 시점에서, 많은 kernel-mode 프로세스들은 운영체제에서 활성화되어 있을지도 모른다. 결과적으로, 한 운영체제 (kernel code)를 구현하는 코드는 몇 가지 가능한 race conditions에 종속된다. 한 예로서 시스템에서 모든 open files의 목록을 유지하는 kernel 자료 구조를 고려해라. 이 리스트는 한 새로운 파일이 열리거나 닫혀졌을 때 (그 파일을 리스트에 더하거나, 그 리스트에서 그것을 제거하거나), 수정되어야만 한다. 만약 두 프로세스들이 동시에 파일을 열었다면, 이 리스트에대한 별개의 업데이트들은 race conditions을 발생시킬 수 있다. race conditions 발생하기 쉬운 다른 kernel data structures는 메모리 할당을 유지하기 위한 구조, 프로세스 리스트들을 유지하기위한 구조, interrupt handling을 위한 자료구조를 포함한다. 그 운영체제가 그러한 race conditions에 자유롭도록 보장하는 것은 kernel 개발자에게 달려있다.
두 개의 일반적인 접근법이 운영체제에서 critical sections을 다루기 위해 사용된다: preemptive kernels와 nonpreemptive kernels. preemptive kerenl은 한 프로세스가 그것이 kernel mode에서 작동하고 있는 동안에 preempted(선점)되는 것을 허용한다. 한 nonpreemptive kernel은 kernel mode에서 작동하고 있는 한 프로세스가 선점되는 것을 허용하지 않는다; 한 kernel-mode process는 그것이 kernel mode, blocks을 종료하거나 자의적으로 CPU control을 포기할 때 까지 작동할 것이다. 명백히 nonpreemptive kernel은 커널 자료구조에서 race conditions으로부터 본질적으로 자유롭다, 왜냐하면 오직 한 프로세스만이 한 번에 kernel에서 활성화 되기 때문이다. 우리는 preemptive kerenels에서 똑같이 말할 수 없다. 그래서 그것들은 shared kerenel data가 race conditions로부터 자유롭도록 보장하기위해 조심스럽게 설계되어야 한다. Preemptive kerenls은 특히 SMP architectures에 대해 설계하기에 어려운데, 이러한 환경에서, 두 개의 kernel-mode processes들이 다른 프로세서들에서 동시에 작동하는 것이 가능하기 때문이다.
왜 어떤 사람은 nonpreemptive kernel보다 preemptive kernel를 선호하는 것일까? preemptive kernel은 좀 더 responsive하다. 왜냐하면 한 kernel-mode process가 그 processor를 waiting processes를 포기하기 전에 임의로 긴 시간동안 작동할 위험이 더 적기 때문이다. (물론, 이 위험은 이 방식으로 행동하지 않는 커널 코드를 설계하여 최소화될 수 있다.) 게다가, preemptive kernel은 real-time programming에 더 적절한데, 그것이 real-time process가 kernel에 현재 작동하는 한 프로세스를 선점하게 허용할 것이기 때문이다.

* Peterson's Solution

다음으로 우리는 Peterson's solution이라고 알려진 critical-section problem의 고전적인 software 기반의 솔루션을 설명한다. 현대 컴퓨터가 load와 store같은 기본 기계어 명령어를 수행하는 방식 때문에, Peterson's solution이 그러한 아키텍쳐에서 정확히 작동할 보장은 없다. 그러나, 그것이 critical-section problem에 대한 좋은 알고리즘적인 설명을 제공하고, 상호배제, 진행, 한정된 대기의 요구사항을 다루는 소프트웨어를 설계할 때 관련된 복잡성을 보여주기 때문에 우리는 이 솔루션을 보여준다.
Peterson의 solution은 critical sections과 remainder sections사이에서 실행을 번갈아 하는 두 개의 프로세스들에 제한된다. 그 프로세스들은 P0과 P1으로 번호를 받는다. 편의성을 위해 Pi를 나타낼 떄, 우리는 Pj를 다른 프로세스로 표기한다.; 즉, j는 1 - i와 같다. Peterson의 solution은 두 개의 프로세스들이 두 개의 data items을 공유하는 것을 요구한다 :

int turn;

boolean flag[2];

그 변수 turn는 그것이 critical section에 들어갈 turn을 가리킨다. 즉, turn == i이라면, process pi는 그것의 critical section에서 실행되는 것을 허용한다. flag array는 한 프로세스가 그것의 critical section에 들어갈 준비가 되어있는지를 가리키는데 사용된다.

{

flag[i] = true;

turn = j;

while (flag[j] && turn == j);

critical section

flag[i] = false;

remainder section

}while(true);

critical section에 들어가기 위해, process Pi는 처음에 flag[i]를 true로 설정하고, turn을 j값으로 설정한다. 그것으로 인해, 만약 다른 프로세스가 critical section에 들어가길 원한다면 그것이 그렇게 할 수 있게 한다. 만약 두 프로세스가 동시에 들어가려고 한다면, turn은 대강 동시에 i와 j로 설정될 것이다. 이러한 할당들 중 하나만이 남을 것이다. 다른 것은 발생할 것이지만, 즉시 덮여 씌워질 것이다. turn의 최종 값은 그 두 개의 프로세스들 중 어떤 것이 그것의 critical section에 처음 들어갈 지를 결정한다.
우리는 이제 이 솔루션이 옳다는 것을 증명한다. 우리는 다음을 보여줄 필요가 있다:

1. Mutual exclusion이 보존된다.
2. progress requirement가 만족된다.
3. bounded-waiting requirement가 충족된다.

특성 1을 증명하기 위해, 각 Pi가 그것의 critical section을 flag[j] == false or turn == i여야 들어갈 수 있다는 것을 주목한다. 또한 만약 두 프로세스가 그것들의 critical sections에서 동시에 실행한다면, 그러면 flag[0] == flag[1] == true이다. 이러한 두 개의 관찰은 P0과 P1이 성공적으로 동시에 while statements를 실행할 수 없다는 것을 암시한다. turn의 값이 0 또는 1 둘 중 하나일 것이기 때문이다. 그러므로 그 프로세스들 중 하나는 성공적으로 while 문을 실행했을 것이지만, 반면에 다른 것은 적어도 한 부가적 명령어를 실행시켰어야 한다 ("turn == j"). ~~

* Synchronization Hardware

Peterson의 것과 같은 software-based solutions은 현대 컴퓨터 아키텍쳐에서 작동하는 것이 보장되지 않는다. 다음의 이야기에서, 우리는 critical-section problem에 대한 좀 더 많은 몇 가지 솔루션들을 볼건데, 커널 개발자와 어플리케이션 프로그래머 둘 다에게 이용가능한 하드웨어에서 부터 소프트웨어 기반 API까지 범위를 가진 기법들을 사용할 것이다. 모든 이러한 솔루션들은 locking의 전제에 기반을 둔다 - 즉, locks을 사용해서 critical sections을 보호하는 것이다. 우리가 보게 되듯이, 그러한 locks의 설계는 꽤 정교해질 수 있다.
많은 시스템에서 이용가능한 어떤 간단한 하드웨어 명령어들은 보여주고, 그것들이 어떻게 그 critical-section problem을 해결하는데 효과적으로 사용될 수 있는지를 보여주어 시작한다. 하드웨어 기능들은 어떤 프로그래밍 task를 더 쉽게 만들 수 있고, 시스템 효율성을 개선할 수 있다.
critical-section problem은 single-processor 환경에서 쉽게 해결될 수 있는데, 만약 우리가 인터럽드들이 shared variable이 수정되는 동안 발생하지 않도록 방지한다면. 이 방식으로, 우리는 명령어의 현재 sequence가 선점없이 순서대로 실행되도록 허용될 수 있는 것을 확신할 수 있다. 어떠한 다른 명령어도 실행되지 않을 것이고, 그래서 어떠한 예상치 못한 수정이 shared variable에 만들어지지 않을 것이다. 이것은 종종 nonpreemptive kernels에 의해 취해지는 접근법이다. 불행하게도, 이 솔루션은 multiprocessor 환경에서 그럴듯 하지 않다. multiprocessor에서 interrupts를 비활성화하는 것은 시간을 소모적일 수 있다. 왜냐하면 그 메세지가 모든 프로세서에게 전달되기 때문이다. 이 전달되는 메세지는 각 critical section으로의 입장을 지연시키고, 시스템 효율성을 줄인다.
많은 현대 컴퓨터 시스템들은 그러므로 우리가 한 word의 내용을 테스트하고 수정할지 또는 두 개의 words의 내용을 atomically하게 swap할지 둘 중 하나를 하도록 특별한 하드웨어 명령어를 제공한다 - atomically는, 즉, 하나의 interrupt불가능한 단위이다. 우리는 이러한 특별한 명령어를 상대적으로 간단한 방식으로 critical-section 문제를 해결하기 위해 사용할 수 있다. 한 특정한 기계에 대해 한 가지 특정한 명령어를 이야기하기 보다, 우리는 test_and_set()과 compare_and_swap() 명령어를 설명하여 이러한 유형의 명령어 뒤에 있는 주된 개념들을 추상화한다.
test_and_set() 명령어는 그림 5.3에서 보이듯이 정의될 수 있다.

boolean test_and_set(boolean* target)

{

boolean rv = *target;

*target = true;

return rv;

}

이 명령어의 중요한 특징은 그것이 atomically하게 실행되는 것이다. 따라서, 만약 두 개의 test_and-set() 명령어가 동시에 실행된다면 (다른 CPU에서 각각), 그것들은 어떤 임의의 순서로 순차적으로 실행될 것이다. 만약 그 기계가 test_and_set() 명령어를 지원한다면, 우리는 false로 초기화된 boolean 변수 lock을 선언하여 mutual exclusion을 구현할 수 있다. 프로세스 Pi의 구조는 그림 5.4에 보여진다.

{

while(test_and_set(&lock))

; /* do nothing */

/* critical section */

lock = false;

/* remainder section */

} while (true);

compare_and_swap() 명령어는 test_and_set()과 대조적으로, 세 개의 operands에 작동한다; 그것은 그림 5.5에 정의된다.

int compare_and_swap(int* value, int expected, int new_value)

{

int temp = *value;

if(*value == expected)

*value = new_value;

return temp;

}

value operand는 만약 그 표현 (*value == expected)가 true라면 new_value로 설정된다. 상관없이, compare_and_swap()은 항상 value 변수의 원래 값을 반환한다. test_and_set() 명령어 처럼, compare()_and_swap()은 atomically하게 실행된다. Mutual exclusion은 다음과 같이 제공될 수 있다: global variable (lock)은 선언되고 0으로 초기화된다. compare_and_swap()을 불러오는 첫 번째 프로세스는 lock을 1로 설정할 것 이다. 그것은 그러고나서 그것의 critical section에 들어갈 것인데, ock의 원래 값이 0의 expected value와 같기 때문이다. comapre_and_swa()에 대한 나중의 호출들은 성공하지 못할 것인데, lock이 이제 0의 예상된 값과 다르기 때문이다. 한 프로세스가 그것의 critical section을 끝낼 때, 그것은 lock을 0으로 다시 설정하고, 이것은 또 다른 프로세스가 그것의 critical section에 들어가도록 허용한다.
비록 이러한 알고리즘들이 상호배제 요구사항을 만족시킬지라도, 그것들은 bounded-waiting 요구사항을 만조깃키지 않는다. 그림 5.7에서, 우리는 test_and_set() 명령어를 사용하여 모든 critical-section 요구사항을 만족시키는 또 다른 알고리즘을 보여준다. 그 공통 자료구조는

boolean waiting[n];

boolean lock;

{

waiting[i] = true;

key = true;

while (waiting[i] && key)

key = test_and_set(&lock);

waiting[i] = false;

/* critical section */

j = (i + 1) % n;

while( (j != i) && !waiting[j])

j = (j + 1) % n;

if(j == i) lock = false;

else waiting[j] = false;

/* remainder section */

} while (true);

이러한 자료구조는 false로 초기화된다. 상호 배제 요구사항이 충족되는 것을 증명하기 위해, 우리는 process Pi가 그것의 critical section을 오직 waiting[i] == false or key == false 둘 중 하나인 경우에만 들어갈 수 있다. key의 값은 test_and_set()이 실행되기만 한다면 false가 될 수 있다. test_and_set()을 실행하는 그 첫 번째 프로세스는 key == false인 거를 알게 될 것이다; 모든 다른 것들이 기다려야 한다. 변수 waiting[i]는 만약 또 다른 프로세스가 그것의 critical section을 떠나다면 false가 될 수 있다; 즉, 한 waiting[i]이 false로 설정되고, 상호 배제 요구사항이 유지된다.
progress requirement가 충족되는 것을 증명하기 위해, 우리는 상호 배제를 위해 보여진 인자들이 또한 여기에 적용되는 것을 주목한다. critical section을 종료하는 한 프로세스가 lock을 false하거나 또는 waiting[j]를 false 로 둘 중 하나를 설정한다. 둘 다 critical section을 들어가기를 기다리는 한 프로세스가 진행되도록 한다.
bounded-waiting requirement가 충족되는지 증명하기 위해, 한 프로세스가 그것의 critical section을 떠날 때, 그것은 cyclic ordering으로 waiting 배열을 스캔한다. 그것은 이 순서소로 entry section에 있는 (wainting[h] == true)인 첫 번째 프로세스를 critical section에 들어갈 다음 것으로 지정한다. 그것의 critical section에 들어갈 기다리는 어떤 프로세스는 따라서 n - 1 turns안에 그렇게 할 것이다.

* Mutex Locks

Section 5.4에서 보여진 critical-section problem에 대한 하드웨어 기반 솔루션들은 복잡할 뿐만 아니라 일반적으로 어플리케이션 프로그래머들에게 접근가능하지 않다. 대신에, 운영체제 설계자들은 critical-section problem을 해결할 소프트웨어 도구를 만든다. 이러한 도구들 중 가장 간단한 것은 mutex lock이다. (사실, mutex라는 용어는 mutual exclusion을 줄인 것이다.) 우리는 critical regions을 보호하고 따라서 race conditions을 방지하기 위해 mutex lock을 사용한다. 즉, 한 프로세스는 critical section에 들어가기 전에 그 locm을 얻어야만 한다; 그것은 그것이 critical section을 종료할 때 lock을 해제한다. acquire() 함수는 그 lock을 얻고, release() 함수는 그 lock을 해제한다.

acquire()

{

while(!available)

; /* busy wait */

available = false;

}

release()

{

available = true;

}

{

acquire lock

critical section

release lock

remainder section

} while (true);

mutex lock은 value가 그 lock이 이용가능한지 안한지를 가리키는 boolean 변수 available를 가진다. 만약 그 lock이 이용가능하다면, acquire()에 대한 호출은 성공하고, 그 lock은 그러고나서 unavailable하다고 고려된다. unavailable lock을 얻으려고 하는 한 프로세스는 그 lock이 해제될 때 까지 봉쇄(blocked)된다. acquire() 또는 release()에 대하 호출 둘 중 하나는 atomically 하게 수행되어야 한다. 따라서, mutex locks은 종종 섹션 5.4에 설명된 하드웨어 메커니즘 들 중 하나를 사용하여 구현된다.
여기에서 주어진 구현의 주된 단점은 그것이 busy waiting을 요구한다는 것이다. 한 프로세스가 그것의 critical section에 있는 반면에, 그것의 critical section에 들어갈려고 하는 어떤 다른 프로세스는 acquire()에 대한 호출에서 지속적으로 loop를 해야한다. 사실, 이러한 mutex lock의 종류는 spinlock이라고 불려지는데, 그 프로세스가 그 lock이 이용가능해지기를 기다리면서 "spins"하기 때문이다. 이 지속적인 looping은 한 single CPU가 많은 프로세스들 사이에서 공유되는 real multiprogramming system에서 명백히 한 문제이다. Busy waiting은 어떤 다른 프로세스가 생산적으로 사용할지도 모르는 CPU cycles을 낭비한다.
Spinlocks은 그러나, 한 프로세스가 lock에 대해 기다려야 할 때 어떠한 context switch가 요구된다는 점에서 이점을 가지고 있고, 한 context switch는 상당한 시간이 걸릴지도 모른다. 따라서, locks이 짧은 시간에 대해 유효하길 기대될 때, spinlocks은 유용하다. 그것들은 종종 한 쓰레드가 한 프로세서에 대해 "spin"할 수 있는, 그리고 또 다른 쓰레드가 또 다른 프로세서에서 그것의 critical section을 수행하고 있는 multiprocessor systems에서 이용된다.

* Semaphores

semaphore S는 초기화와 별개로 오직 두 개의 표준 atomic operations를 통해서만 접근 가능한 정수 변수이다 : wait() and signal(). wait() 연산은 원래 P라고 용어가 정해졌다 (네덜란드어 proberen, "to test"); signal은 원래 V로 불려졌다 (verhogen으로부터, "to increment"). wait()과 signal()의 정의는 다음과 같다:

wait(S)

{

while(S <= 0)

; // busy wait

S--;

}

signal(S)

{

S++;

}

wait()과 signal() 연산에서 semaphore의 정수값에 대한 모든 수정은 분리되지 않게 실행되어야 한다. 즉, 한 프로세스가 세마포어 값을 수정할 때, 어떠한 다른 프로세스는 그 같은 세마포어 값을 동시에 수정할 수 없다. 게다가, wait(S)의 경우에, 그 S의 정수값에 대한 테스팅 뿐만 아니라, 그것의 가능한 수정 (S--)도 interruption 없이 실행되어야 한다.
운영체제는 counting semaphores와 binary semaphores 사이를 구분한다. counting semaphore의 값은 제한되지 않는 영역까지의 범위를 갖을 수 있다. binary semaphore의 값은 오직 0에서 1사이의 범위만을 갖을 수 있다. 따라서, binary semaphores는 mutex locks와 유사하게 행동한다. 사실, mutex locks을 제공하지 않는 시스템들에서, binary semaphores는 mutual exclusion을 제공하는 대신에 사용되어질 수 있다.
Counting semaphores는 유한한개수의 인스턴스들로 구성된 주어진 resource에 대한 접근을 제어하기 위해 사용될 수 있다.그 세마포어는 이용가능한 자원의 개수로 초기화된다. 한 자원을 사용하길 원하는 각 프로세스는 그 세마포어에서 wait() 연산을 수행한다 (그것으로 인해 그 count를 감소시킨다.) 한 프로세스가 한 resource를 해제할 때, 그것은 signal() 연산을 수행한다 (그 count를 증가시킨다). semaphore에 대한 count가 0으로 될 때, 모든 자원들이 사용되고 있는 중이다. 그 이후에, 한 자원을 사용하길 원하는 프로세스들은 그 count가 0보다 더 커지게 될 때까지 봉쇄(block)될 것이다.
우리는 다양한 동기화 문제들을 해결하기 위해 세마포어들을 또한 사용할 수 있다. 예를들어, 두 개의 concurrently하게 작동하는 프로세스들을 고려해라: 명령어 S1를 가진 P1과 명령어 S2를 가진 P2. S2가 오직 S1이 완료된 후에만 실행되어야 하는 것을 요구한다고 가정하자. 우리는 이 전략을 쉽게 P1과 P2가 0으로 초기화된 공통의 semaphore synch를 공유하게 하여 이 전략을 구현할 수 있다

S1;

signal(synch);

프로세스 P2에서, 우리는 다음의 명령어를 넣는다

wait(synch);

S2;

왜냐하면 synch는 0으로 초기화 되기 때문에, P2는 P1이 signal(synch)를 불러온 후에만 S2를 실행할 것이다. 그리고 이것은 S1이 실행되고 난 후이다.

mutex locks이 busy waiting의 단점이 있다는 것을기억해라. 여기에서 설명된 wait()과 signal()의 세마포어 연산들의 정의들도 같은 문제를 보여준다. busy waiting에 대한 필요성을 극복하기 위해, 우리는 wait()과 signal() 연산을 다음의 정의로 수정할 수 있다: 한 프로세스가 wait() 연산을 실행하고 그 semaphore 값이 양수가 아닌 것을 발견했을 때, 그 프로세스 그 자체로 봉쇄될 수 있다. 그 block operation은 한 프로세스를 그 세마포어와 관련된 waiting queue에 넣는다. 그러고나서 제어가 CPU scheduler에 넘겨지고, 그 스케쥴러는 실행한 또 다른 프로세스를 선택한다. semaphore S에 대기하고 있는 봉쇄된 한 프로세스는 어떤 다른 프로세스가 signal() 연산을 실행할 때 재개되어야 한다. 그 프로세스는 wakeup() 연산으로 재개될 수 있고, 그것은 그 프로세스를 waiting state에서 ready state로 바꾼다. 그 프로세스는 그러고나서 ready queue에 배치되어진다. (그 CPU는 작동하는 프로세스에서 새롭게 준비된 프로세스로 바껴질 수도 아닐지도 모른다. 이것은 cpu 스케쥴링 알고리즘에 따른다.)
이 정의 하에서 세마포어를 구현하기 위해서, 우리는 세마포어를 다음과같이 정의한다:

typedef struct

{

int value;

struct process* list;

} semaphore;

각 세마포어는 한 정수 value와 프로세스의 한 리스트인 list를 갖는다. 한 프로세스가 한 세마포어를 기다려야만 할 때, 그것은 프로세스들의 리스트에 더해진다. signal() 연산은 대기하고있는 프로세스의 리스트에서 한 프로세스를 제거하고, 그 프로세스를 깨운다. 이제 그 wait(), signal() semahore 연산은 다음으로 정의될 수 있다

wait(semaphore* S)

{

S->value--;

if(S->value < 0)

{

add this process to S-> list;

block();

}

signal(semaphore* S)
{
S->value++;
if(S->value <= 0)
{
remove a process P from S->list;
wakeup(P);
}
}

그 block() 연산은 그것을 불러내는 프로세스를 중지시킨다. 그 wakeup(P) 연산은 봉쇄된 프로세스 P의 실행을 재개한다. 이러한 두 개의 연산은 운영체제에 의해 기본 시스템 호출로서 제공된다. 이 구현에서, 세마포어 값들이 음수일지도 모른다는 것에 주목해라, 바면에 세마포어 값들은 busy waiting이 있는 세마포어의 고전적인 정의하에서는 결코 음수가 아니다. 만약 한 세마포어 값이 음수라면, 그것의 크기는 그 세마포어를 대기하는 프로세스들의 개수이다. 이 사실은 decrement의 순서를 바꾸는 것과 wait() 연산의 구현에서 테스트에 의한 것이다.
대기하는 프로세스들의 리스트는 쉽게 각 process control block(PCB)에서의 link field에의해 구현될 수 있다. bounded waiting을 보장하기위해서 그 리스트에서 프로세스들을 더하고 제거하는 한 방법은 FIFO queue를 사용하는 것이다. 거기에서 그 세마포어는 그 큐에 대해 head와 tail pointers 둘 다를 포함한다. 그러나, 일반적으로, 그 리스트는 어떠한 queueing strategy든지 사용할 수 있다. 세마포어에 대한 올바른 사용은 그 세마포어 lists에 대한 특정한 queueing strategy에 의존하지 않는다.
세마포어 연산들이 atomically하게 실행되는 것이 중요하다. 우리는 어떠한 두 프로세스가 wait() and signal() 연산을 같은 세마포어에 대해 동시에 실행할 수 없도록 보장해야만 한다. 이것이 critical-section problem이다; 그리고 single-processor 환경에서, 우리는 간단히 wait()/signal() 연산이 실행되는 시간 동안 interrupts를 금지하여 그것을 해결 할 수 있다. 이 전략은 단일 프로세서 환경에서 효과가 있는데, 왜냐하면 일단 interrupts가 금지되기만 한다면, 다른 프로세스로 부터의 명령어들이 interleaved 되어질 수 없기 때문이다. 오직 그 현재 작동하는 프로세스는 interrupst가 재활성화되고 스케듈러가 제어를 다시 얻을 때 까지 실행된다.
multiprocessor 환경에서, interrupts는 모든 프로세서에 대해 비활성화되어야 한다. 그렇지 않다면, 다른 프로세스로부터의 명령어들이 어떤 임의의 방식으로 끼어들지도 모른다. 모든 프로세서에 대해 interrupts를 비활성화하는 것은 어려운 일일 수 있고, 게다가 심각하게 성능을 감소시킬 수 있다. 그러므로, SMP systems은 compare_and_swap() or spinlocks 같은 대안적인 locking 기법을 wait()과 signal()이 atomically하게 수행되는 것을 보장하기 위해 제공해야만 한다.
우리가 완전히 이 wait()과 signal() 연산의 정의로 busy waiting으 제거하지 않았다는 것을 인정하는 것이 중요하다. 오히려, 우리는 busy waiting을 application program의 entry section에서 critical sections으로 옮겼다. 게다가, 우리는 busy waiting을 wait()/signal() 연산의 critical sections에 제한하고, 이러한 섹션들은 짧다 (만약 적절히 코딩된다면, 그것들은 10개 이상의 명령어가 되서는 안된다). 따라서, 그 critical section은 거의 결코 점유되지 않고, busy waiting은 드물게 일어난다, 오직 짧은 시간 동안만. critical sections이 길거나 (몇 분 또는 몇 시간) 또는 항상 점유될지도 모르는 어플리케이션 프로그램이 가진 전적으로 다른 상황이 존재한다. 그러한 경우에, busy waiting은 매우 비효율적이다.
waiting queue를 가진 semaphore의 구현은 두 개 이상의 프로세스들이 그 waiting processes들 중의 하나에 의해서만 발생할 수 있는 한 사건을 무기한으로 기다리는 상황을 발생시킬지도 모른다. 그 궁금한 event는 signal() 연산의 실행이다. 그허나 한 상태가 도달되었을 때, 이러한프로세스들은 deadlocked되었다고 말해진다. 이것을 보이기 위해서, 두 개의 프로세스들 P0과 P1로 구성된 하 닛스템을 고려하자, 그리고 각각은 1로 설정된 두 개의 세마포어들 S와 Q에 접근한다:

P0 P1

wait(S); wait(Q);

wait(Q); wait(S);

... ...

signal(S); signal(Q);

signal(Q); signal(S);

P0이 wait(S)를 실행하고, 그러고나서 P1이 wait(Q)를 실행한다고 가정하자. P0이 wait(Q)를 실행할 때, 그것은 P1이 signal(Q)를 실행할 때 까지 기다려야 한다. 유사하게, P1이 wait(S)를 실행할 때, 그것은 P0이 signal(S)를 실행할 때 까지 기다려야 한다. 이러한 signal() 연산들이 실행될 수 없기 때문에, P0과 P1은 deadlocked 된다. 우리는 프로세스들의 한 집합에서 모든 프로세스가 그 집합에 있는 또 다른 프로세스에 의해서만 발생될 수 있는 한 event를 기다리고 있을 때, 그 프로세스들의 한 집합이 deadlocked state에 있다고 말한다. 우리가 주로 여기에 관련이 있는 events들은 resource acquisition과 release이다. events들의 또 다른 유형들은 deadlocks을 발생시킬지도 모른다. deadlock과 관련된 또 다른 문제는 indefinite blocking(무기한 봉쇄) 또는 starvation(기아)이다. 이것은 프로세스들이 무기한으로 그 세마포어 내에서 대기하는 상황이다. 무기한 봉쇄는 만약 우리가 LIFO 순서로 한 세마포어와 관련된 리스트에서 프로세스들을 제거한다면 발생할지도 모른다.
scheduling challenge는 더 높은 우선순위의 프로세스가 더 낮은 우선순위의 프로세스에 의해 현재 접근되고 있는 kernel data를 읽거나수정할 필요가 있을 때 발생한다. kernel data는 일반적으로 lock으로 보호되기 때문에, 더 높은 우선순위의 프로세스는 더 낮은 우선순위의 것이 그 자원을 가지고 작업하는 것을 마무리하도록 기다릴 것이다. 그 상황은 더 낮은 우선순위의 프로세스가 더 높은 우선순위를 가진 또 다른 프로세스를 옹호하여 선점된다면 복잡하게 된다. 예를들어, 세 개의 프로세스들 L,M,H가 있고, L < M < H 순서로 우선순위가 있다고 가정하자. 프로세스 H가 현재 프로세스 L에 접근되고 있는 자원 R에을 요구한다고 가정하자. 보통으로, 프로세스 H는 L이 자원 R을 사용하는 것을 마무리하는 것을 기다릴 것이다. 그러나, 프로세스 M이 작동할 수 있게 되어 프로세스 L를 선점한다고 가정하자. 간접적으로, 더 낮은 우선순의 한 프로세스가 (프로세스 M) 프로세스 H가 L이 자원 R을 포기하도록 얼마나 오랫동안 기다릴지에 대해 영향을 미쳤다.
이 문제는 priority inversion이라고 알려져 있다. 그것은 오직 두 개 이상의 우선순위를 가진 시스템에서만 발생하는데, 그래서 한 솔루션은 오직 두 개의 우선순위만을 갖는 것이다. 그러나, 그것은 대부분의 general-purpose 운영체제에 대해 불충분한다. 일반적으로 이러한 시스템은 priority-inheritance protocol (우선순위-상속 통신규약)을 구현하여 그 문제를 해결한다. 이 프로토콜에 따르면, 더 높은 우선순위의 프로세스에 의해 필요한 자원에 접근하는 모든 프로세스들은 그것들이 문제가 된 자원들과 마무리 될 때 까지 더 높은 우선순위를 상속 받는다. 그거들이 끝났을 때, 그들의 우선순위는 그들의 원래 값으로 돌아간다. 위의 예제에서, priority-inheritance protocol은 processL이 일시적으로 프로세스 H의 우선순위를 상속받도록 한다. 그것으로 인해 프로세스 M이 그것의 실행을 선점하지 못하게 막는다. 프로세스 L이 자원 R을 사용하는 것을 끝냈을 때, 그것은 그것의 상속된 우선순위를 H로부터 포기하고, 그것의 원래 우선순위를 맡게된다. resource R이 이제 이용가능해졌기 때문에, 프로세스 H - M이 아닌 - 다음에 작동할 것이다.

* Classic Problems of Synchronization

bounded-buffer problem은 Section 5.1에서 소개되었었다; 그것은 흔히 synchronization primitives의 힘을 보이기 위해 사용된다. 여기에서 우리는 어떤 특정한 구현에 집중하지 않고 이 전략에 대한 일반적인 구조를 보여준다. 우리의 문제에서 producer와 consumer processes는 다음의 자료구조를 공유한다:

int n;

semaphore mutex = 1;

semaphore empty = n;

semaphore full = 0;

우리는 그 pool이 n개의 버퍼들로 구성되고, 각각이 한 아이템을 보유할 수 있따고 가정한다. 그 mutex semaphore는 buffer pool에 대한 접근에 대해 mutual exclusion을 제공하고, 1의 값으로 초기화 된다. 그 empty와 full 세마포어는 empty와 full buffers의 개수를 센다. 그 semaphore empty는 n으로 초기화 된다; full 세마포어는 0으로 초기화된다.

{

...

/* produce an item in next produced */

wait(empty);

wait(mutex);

...

/* add next_produced to the buffer */

...

signal (mutex);

signal (full);

} while (true);

{

wait(full);

wait(mutex);

...

/* remove an item from buffer to next_consumed */

...

signal(mutex);

signal(empty);

...

/* consume the item in next_consumed */

...

} while (true);

producer와 consumer 사이의 대칭성에 주목해라. 우리는 이 코드를 consumer를 위한 full buffers를 생산하는 producer로서 해석하거나, producer를 위해 empty buffers를 생산하는 consumer로서 해석할 수 있다.
database에서 접근해서 concurrently하게 read/write하는 상황에서, writers가 database에 writing하는 동안 shared database에 대해 exclusive access를 갖도록 요구한다. 이 동기화 문제는 readers-writers problem으로서 언급된다. 그것이 말해진 이후로, 거의 모든 새로운 동기화 primitive를 테스트하기위해 사용되어졌다. reader-writers 문제는 몇 가지 변형을 가지는데, 모두 우선순위를 포함한다. first readers-writers problem이라고 언급되는 가장 간단한 것은, 만약 한 writer가 이미 shared object를 사용하는 허가를 얻지못했다면 어떠한 reader도 기다려서는안된다는 것을 요구한다. 다시말해서, 한 writer가 기다리고 있기 때문에 어떠한 reader도 간단히 다른 독자들이 끝내는 것을 기다려서는 안된다. 그 second readers-writers problem은 한 writer가 준비되기만 한다면, 그 writer는 가능한 빨리 그것의 write를 수행한다. 다시 말해서, 한 writer가 그 오브젝트에 접근하기를 기다린다면, 어떠한 새로운 readers들은 읽기 시작하지 못할지도 모른다.
둘 중 하나 문제에 대한 해결책은 starvation을 만들지도 모른다. 첫 번째 경우에, writers는 starve할지도 모른다; 두 번째 경우에서, readers가 starve할지도 모른다. 이 이유 때문에, 그 문제에 대한 다른 변수들이 제안된다. 다음에, 우리는 첫 번째 readers-writers problem에 대한 해결책을 제안한다. first readers-writers problem에 대한 솔루션에서, 그 reader processes는 다음의 자료구조를 공유한다:

semaphore rw_mutex = 1;

semaphore mutex = 1;

int read_count = 0;

mutex와 rw_mutex 세마포어는 1로 초기화된다; read_count는 0으로 초기화 된다. 그 세마포어 rw_mutex는 reader와 writer processes 둘 다에 공통이다. mutex semaphore는 그 변수 read_count가 업데이트될 때 상호 배제를 보장하도록 사용된다. read_count 변수는 얼마나 많은 프로세스들이 현재 그 오브젝트를 읽고 있는지를 추적한다. rw_mutex 세마포어는 writers에 대해 상호배제 세마포어로서 기능을 한다. 그것은 또한 그 critical section에 들어가거나 종료하는 첫 번째 또는 마지막 독자에 의해 사용된다. 그것은 다른 독자들이 그들의 critical sections에 있는 동안 들어가거나 나갈 독자들에 의해서 사용되지 않는다.

{

wait(rw_mutex);

...

/* writing is performed */

...

signal(rw_mutex);

} while (true);

{

wait(mutex);

read_count++;

if(read_count == 1)

wait(rw_mutex);

signal(mutex);

...

/* reading is performed */

...

wait(mutex);

read_count--;

if(read_count == 0)

signal(rw_mutex);

signal(mutex);

} while (true);

만약 한 writer가 critical section에 있고 n명의 readers가 기다리고 있다면, 그러고나서 한 reader는 rw_mutex에 queued 되고, n-1 readers는 mutex에 queued 된다. 또한 한 writer가 signal(rw_mutex)를 실행할 때, 우리는 기다리고 있는 readers들 중 또는 한 명의 단일 waiting writer 둘 중의 하나의 실행을 재개할지도 모른다. 그 선택은 스케쥴러에 의해서 된다. readers-writers problem과 그것의 솔루션들은 reader-writer locks을 시스템에 제공하는 것으로 일반화된다. reader-writer lock을 얻는 것은 lock의 mode를 명시하는 것을 요구한다: read or write access 둘 중 하나. 한 프로세스가 shared data를 읽기만을 원할 때,그것은 read mode에서 그 reader-writer lock을 요청한다. 그 shared data를 수정하기를 원하는 한 프로세스는 write mode의 lock을 요청한다. 여러 프로세스들은 concurrently하게 read mode의 reader-writer lock을 얻도록 허가 되지만, 오직 한 프로세스만이 writing에 대한 lock을 얻을지 모른다. exclusive access가 wirters에 대해 요구되기 때문이다. Reader-writer locks는 다음의 상황에서 가장 유용하다:

어떤 프로세스들이 shared data를 읽기만하고, 어떤 프로세스들이 shared data를 쓰기만 하는지를 식별하기 쉬운 어플리케이션에서
writers보다 좀 더 많은 readers를 가진 어플리케이션에서. 이것은 왜냐하면 reader-writer locks이 일반적으로 semaphores or mutual-exclusion locks보다 구성하기에 좀 더 많은 오버헤드를 요구하기 때문이다. 그 여러 readers를 허용하는 것의 증가된 concurrency는 reader-writer lock을 설정할 때와 관련된 오버헤드를 보상한다.

dining-philosophers problem은 classic synchronization problem으로 고려되는데,그것의 실제적인 중요성 또는 컴퓨터 과학자들이 철학자들을 싫어해서가 아니라, 그것이 concurrency-control problems의 큰 class의 한 예시이기 때문이다. 그것은 deadlock-free and starvation-free 방식으로 여러 프로세스 사이에서 여러개의 자원들을 할당할 필요성에 대한 간단히 대표하는 것이다. 한 가지 간단한 솔루션은 각 chopstick을 semaphore로 나타내는 것이다. 한 철학자는 그 세마포어에 대해 wait() 연산을 실행하여 한 젓가락을 잡으려고 한다. 그녀는 signal() 연산을 그 적절한 세마포어에 실행하여 그녀의 젓가락을 해제한다. 따라서, 그 공유되는 데이터는

semaphore chopstick[5];

{

wait(chopstick[i]);

wait(chopstick[(i + 1) % 5);

...

/* eat for awhile */

...

signal(chopstick[i]);

signal(chopstick[(i + 1) % 5]);

/* think for a whilte */

...

} while (true);

여기에서 chopstick의 모든 원소들은 1로 초기화 된다. 비록 이 솔루션이 어떠한 두 이웃들이 동시에 먹지 않도록 보장할지라도, 그것은 그럼에도 불구하고, deadlock을 만들 수 있기 때문에 거절되어야만 한다. 모든 다섯명의 철학자들이 동시에 배고파져서 각각이 그녀의 왼쪽 chopstick을 집었다고 가정하자. chopstick의 모든 원소들은 이제 0과 같아질 것이다. 각 철학자가 그녀의 오른쪽 젓가락을 잡으려고 할 때, 그녀는 영원히 delayed 될 것이다. 그 데드락 문제에 대해 몇 가지 가능한 치료법이 다음으로 대체된다:

최대 4명의 철학자가 테이블에 동시에 앉을 수 있도록 하기.
두 젓가락이 이용가능할 때에만, 한 철학자가 그녀의 젓가락들을 집을 수 있도록 하기 (이것을 하기 위해서, 그녀는 critical section에서 그것들을 집어야 한다).
asymmetric solution 사용하기 - 즉, 홀수 숫자의 철학자가 그녀의 왼쪽 젓가락을 먼저 집고, 그러고나서 그녀의 오른쪽 젓가락을 집기. 반면에 짝수 숫자의 철학자는 그녀의 오른쪽 젓가락을 집고, 그러고나서 왼쪽 젓가락을 집기.

Section 5.8에서 dining-philosophers problem에 대해 deadlocks으로부터 자유를 보장하는 솔루션을 보여준다. 그러나, 그 문제에 대한 어떠한 만족스러운 솔루션도 그 철학자들 중 하나가 굶어서 죽게될 가능성에 대해서 보호해야만 한다는 것에 주목해라. deadlock-free solution은 반드시 starvation의 가능성을 제거하지 않는다.

* Monitors

비록 세마포어가 프로세스 동기화에 대해 편리하고 효과적인 메커니즘을 제공할지라도, 그것들은 부정확하게 사용하는 것은 탐지하기에 어려운 timing errors를 발생시킬 수 있다. 이러한 에러들은 특정한 실행 순서가 발생해야만 발생할 수 있고,이러한 순서들이 항상 발생하는 것이 아니기 때문이다. 여러가지 문제들을 처리하기 위해서, 연구원들은 high-level language constructs를 개발해왔다. 이 섹션에서, 우리는 한 가지 기본적인 high-level synchronization construct를 설명한다 - monitor type.
abstract data type or ADT는 ADT의 특정한 구현과는 독립적인 데이터에 작동할 함수들의 한 집합으로 데이터를 캡슐화 한다. monitor type은 monitor 내에서 mutual exclusion을 제공받는 프로그래머가 정의한 연산들의 한 집합을 포함하는 ADT이다. 그 monitor type은 또한 값이 그 type의 instance의 상태를 정의하는 변수들을 선언한다. 이 때 그러한 변수들에 작동할 함수들의 bodies도 함께 있다. monitor type의 syntax는 다음과 같다:

monitor monitor name

{

/* shared variable declarations */

function P1 ( . . . )

{ ... }

function P2 ( . . . )

{ ... }

function Pn ( . . . )

{ ... }

initialization code ( . . .)

{ ... }

}

monitor type의 표기는 다양한 프로세스들에서 직접적으로 사용될 수 없다. 따라서, 한 monitor 내에서 정의된 한 함수는 monitor 내에서 locally하게 선언된 변수들과 그것의 formal parameters들만 접근할 수 있다. 유사하게, 한 monitor의 local variables는 오직 그 local functions에 의해서만 접근될 수 있다. monitor construct는 오직 한 프로세스가 한 time에 monitor 내에서 활성화되도록 한다. 결과적으로, 그프로그래머는 이 동기화 제약을 explicitly하게 코드할 필요가 없다. 그러나, 지금까지 정의된 monitor construct는 어떤 동기화 전략을 모델링하는데 충분히 강력하지 않다. 이 모겆ㄱ에 대해서, 우리는 부갖거인 동기화 메커니즘을 저으이할 필요가 있다. 이러한 메커니즘들은 condition constuct에 의해 제공된다. tailor-made synchronization scheme을 쓸 필요가 있는 한 프로그래머는 condition type의 한 개 이상의 변수들을 정의할 수 있다:

condition x, y;

한 condition 변수에 대해 불러와질 수 있는 유일한 연산들은 wait()과 signal()이다. 그 연산은 x.wait(); 이고, 이것은 이 연산을 부른프로세스가 또 다른 프로세스가 x.signal()를 부를 때 까지 중지되는 것을 의미한다. x.signal() 연산은 정확히 한 개의 중지된 프로세스를 재개한다. 만약 어떠한 프로세스도 중지되어있지 않다면, 그러면 signal() 연산은 어떠한 효과도 갖지 않는다; 즉, 그 x의 상태는 그 연산이 결코 실행되지 않는 것과 같게 된다. 이 연산과 세마포어와 관련된 signal() 연산을 대조시키면, 그것은 항상 세마포어의 상태에 영향을 미친다.
x.signal() 연산이 한 프로세스 P에 의해 불러와졌을 때, condition x와 관련된 중지된 프로세스 Q가 있다고 가정하자. 명백히, 만약 그 중지된 프로세스 Q가 그것의 실행을 재개하도록 허용된다면, 그 signal을 한 프로세스 P는 기다려야만 한다. 만약그렇지 않다면, P와 Q 둘 다 그 monitor 내에서 둘 다 활성화될 것이다. 그러나, 개념적으로 두 프로세스 모두 그들의 실행으로 계속할 수 있다는 것에 주목해라. 두 가지 가능성이 존재한다:

Signal and wait. P는 Q가 monitor를 떠날 때 까지 기다리거나 또는 또 다른 condition을 기다린다.
Signal and coontinue. Q는 P가 monitor를 떠날 때 까지 기다리거나, 또 다른 condition을 기다린다.

다음으로, 우리는 dining-philosophers problem에 deadlock-free solution을 보여주어서 monitor 개념을 보여준다. 이 솔루션은 한 철학자가 젓가락 두 개 다 이용가능할 때에만 젓가락을 집도록 하는 제한을 부과한다. 이 솔루션을 코딩 하기 위해, 우리는 철학자에게서 발견할지도 모르는 세 개의 상태 사이에서 구분할 필요가 있다. 이 목적을 위해, 우리는 다음의 자료구조를 도입한다:

enum {THINKING, HUNGRY, EATING} state[5];

철학자 i는 그녀의 두 이웃이 먹고 있지 않을 때 즉, state[(i + 4) % 5] != EATING and state[(i + 1) % 5] != EATING 일 때에만 state[i] = EATING을 설정할 수 있다.

monitor DiningPhilosophers

{

enum {THINKING, HUNGRY, EATING} state[5];

condition self[5];

void pickup(int i )

{

state[i] = HUNGRY;

test(i);

if(state[i] != EATING)

self[i].wait();

}

void putdown(int i)

{

state[i] = THINKING;

test((i + 4) % 5);

test((i + 1) % 5);

}

void test(int i)

{

if( (state[(i + 4) % 5] != EATING) && state[i] == HUNGRY &&

(state[(i + 1) % 5] != EATING))

{

state[i] = EATING;

self[i].signal();

}

initialization code()

{

for(int i = 0; i < 5; ++i)

state[i] = THINKING;

}

condition self[5]는 철학자 i가 그녀가 배고프지만 그녀가 필요한 젓가락을 얻을 수 없을 때 그녀 자신을 지연시키게 한다. 각 철학자가 먹기 시작하기 전에, 연산 pickup()을 불러야만 한다. 이 행동은 철학자 프로세스의 중지를 일으킬지도 모른다. 그 연산의 성공적인 완료 후에, 그 철학자는 먹을지도 모른다. 이것 후에, 그 철학자는 putdown() 연산을 부른다. 따라서, 철학자 i는 pickup()과 putdown() 연산을 불러야만 한다.
우리는 이제 세마포어를 사용하여 모니터 메커니즘의 가능한 구현을 고려한다. 각 모니터에 대해, 한 세마포어 mutex (1로 초기화 된)가 제공된다. 한 프로세스는 monitor에 들어가기전에 wait(mutex)를 실행해야만 하고, 그 모니터를 나가기 전에 signal(mutex)를 실행해야만한다. signal을 보내는 프로세스는 그 재개된 프로세스가 나가거나 또는 기다릴 때까지 기다려야 해서, 부가적인 세마포어인 next가 0으로 초기화되어 도입된다. 그 signaling processes는 그들 자신을 중지하기위해 next를 사용할 수 있다. 정수 변수 next_count는 또한 next에 중지된 프로세스들의 수를 세기 위해 제공된다. 따라서, 각 external function F는 다음으로 대체된다

wait(mutex);

...

body of F

...

if(next_count > 0)

signal(next);

else

signal(mutex);

한 monitor 내에서 상호배제가 보장된다. 우리는 이제 condition 변수들이 어떻게 구현되었는지를 또한 설명할 수 있따. 각 condition x에 대해, 우리는 x_sem 세마포어를 도입하고, 정수 변수 x_counter를 둘 다 0으로 초기화하여 도입한다. x.wait() 연산은 이제 다음으로 구현된다

x.count++;

if(next_count > 0)

signal(next);

else

signal(mutex);

wait(x.sem);

x.count--;

x.signal() 연산은 다음으로 구현될 수 있다:

if(x_count > 0)

{

next_count++;

signal(x_sem);

wait(next);

next_count--;

}

이 구현은 Hoare와 Brinch-Hansen 둘다 에의해 주어지는 monitors의 정의에 적용가능하다.
이제 우리는 monitor 내에서 process-resumption 주제로 돌린다. 만약 여러 프로세스들이 condition x에 중지되어 있고, x.signal() 연산이 어떤 프로세스에 의해 실행된다면, 그러면 우리는 중지된 프로세스들 중 어떤 것이 다음에 재개되도록 결정하는가? 한 가지 간단한솔루션은 first-come, first-served(FCFS) ordering이다. 이것은 가장 오랫동안 기다리고 있는 프로세스가 처음에 재개된다. 그러나, 많은 상황에서 그러한 간단한 스케쥴링 전략은 적절하지 않다. 이 목적에 대해, conditional-wait construct가 사용될 수 있다. 이 construct는 x.wait(c)라는 형태를 갖는다. 여기에서 c는 wait() 연산이 실행될 때, evaluated 되는 정수 표현이다. priority number라고 불려지는 c의 값은 그러고나서 중지된 프로세스의 이름과 함께 저장된다. x.signal()이 실행될 때, 가장 작은 우선순위 숫자를 가진 프로세스가 다음애 재개된다.
이 새로운 메커니즘을 보이기 위해서, ResourceAllocator monitor를 고려해라. 이것은 경쟁하는 프로세스 사이에서 단일 자원의 할당을 제어한다.

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;

}

각 프로세스가, 이 자원에 대한 할당을 요청할 때, 그 자원을 사용할 계획의 최대 시간을 명시한다. 그 monitor는 그 자원을 최단 시간-할당 요청을 가진 프로세스에게 할당한다. 문제가 되는 자원에 접근할 필요가 있는 한 프로세스는 다음의 순서를 관찰해야만 한다:

R.acquire(t);

...

access the resource;

...

R.release();

R이 ResourceAllocator type의 한 instance이다. 불행하게도, monitor concept은 선행하는 access sequence가 관찰되어지는 것을 보장할 수 없다. 특히, 다음의 문제들이 발생할 수 있다:

한 프로세스는 처음에 자원에 대해 접근 허가를 얻지않고 한자원에 접근할지도 모른다.
한 프로세스는 그것이 자원에 대한 접근을 받는다면 한 자원을 결코 해제하지 않을지도 모른다.
한 프로세스는 그것이 결코 요청하지 않은 자원을 해제하려고 할지도 모른다.
한 프로세스는 같은 자원을 두 번 요청 할지도 모른다 (처음에 그 자원을 해제하지 않고서)

그 같은 어려움들은 세마포어의 사용하면서 만나지고, 이러한 어려움들은 우리가 처음에 monitor constructs를 개발하려고 격려하는 것들과 비슷하다. 이전에, 우리는 세마포어의 올바른 사용에 걱정해야만 했었다. 이제, 우리는 higher-level programmer-defined operations의 올바른 사용에 대해 걱정해야만 한다. 그리고 컴파일러는 더 이상 우리를 도와줄 수 없다.
그 현재의 문제에 대한 한 가지 가능한 솔루션은 ResourceAllocator monitor안에 resource-access operations를 포함시키는 것이다. 그러나, 이 솔루션을 사용하는 것은 스케쥴링이 우리가 코딩한 것보다는 built-in monitor-scheduling algorithm에 의해 처리된다는 것을 의미할 것이다.

* Synchronization Examples

우리는 Windows, Linux, Solaris, Pthreads API에 의해 제공되는 동기화 메커니즘을설명한다. 세 가지 운영체제들은 커널을 동기화하는 것에 대해 다른 접근법들의 좋은 예시들을 제공한다. Pthread API는 UNIX와 Linux 시스템의 개발자들에 의해 thread creation과 동기화를 위해 널리 사용되기 때문이다.
Windows 운영체제는 real-time applications and multiple processors에 대한 지원을 제공하는 multithreaded kernel이다. Window kernel이 single-processor system에 있는 global resource에 접근할 때, 그것은 일시적으로 global resource에 또한 접근할지도 모르는 모든 interrupt handlers에 대해 interrupts를 mask한다. 멀티프로세서 시스템에서, Windows는 spinlocks을 사용하여 global resources에 대한 접근을 보호한다. 비록 그 kernel이 짧은 코드 segments만을 보호하기 위해 spinlocks을 사용할지라도. 게다가, 효율성의 이유 때문에, kernel은 한 쓰레드가 spinlock을 보유하면서 결코 선점되지 않도록 보장한다.
kernel밖의 쓰레드 동기화를 위해, 윈도우즈는 dispatcher objects를 제공한다. dispatcher object를 사용하여, threads는 mutex locks, semaphores, events, and timers를 포함하는 여러 다른 메커니즘들에 따라서 동기화한다. 그 시스템은 한 쓰레드가 데이터에 접근하는 mutex에 대한 소유권을 얻도록 요구하고, 그것이 마무리 되었을 때 해제하도록 하여 공유데이터를 보호한다. 세마포어는 Section 5.6에서 설명한대로 작동한다. Events는 condition 변수와 유사하다; 즉, 그것들은 한 요구된 condition이 발생할 때, waiting thread에 알려줄지도 모른다. 마지막으로, timers는 한 쓰레드 (또는 한 개 이상의)에게 한 정해진 시간의 양이 지났다는 것을 알려주기 위해 사용된다.
Dispatcher objects는 signaled state 또는 nonsignaled state 둘 중 하나에 있을지도 모른다. signaled state에있는 한 오브젝트는 이용가능하고, 한 thread는 그 오브젝트를 획득할 때 봉쇄되지 않을 것이다. nonsignaled state에 있는 한 오브젝트는 이용가능하지 않고, 그 오브젝트를 얻으려고 하는 한 쓰레드는 봉쇄될 것이다. dispatcher object의 상태와 쓰레드의상태 사이에 관계가 존재한다. 한 thread가 nonsignaled dispatcher object에 대해 봉쇄될 때, 그것의 상태는 ready에서 waiting으로 변하고, 그 thread는 그 오브젝트에 대해 waiting queue에 배치된다. dispatcher object에 대한 상태가 signaled로 바뀔 때, 그kernel은 어떤 쓰레드들이 그 오브젝트에서 기다리고 있는지를 체크한다. 만약 그렇다면, 그 커널은 한 thread를 - 가능하면 그 이상을 - waiting state에서 ready state로 움직인다. 거기에서 그것들을 실행을 재개할 수 있다. kernel이 waiting queue에서 선택하는 쓰레드들의 개수는 그것이 기다리고 있는 dispatcher object의 유형에 달려있다. 한 mutex에 대한 waiting queue의 로부터 커널은 하나의 thread만을 고를 것이다. 왜냐하면 mutex object는 오직 단일 쓰레드에 의해서 소유될 것이기 때문이다. 한 event object에 대해, 그 커널은 그 event에 대해 기다리고 있는 모든 쓰레드들을 선택할 것이다.
critical-section object는 kernel의 개입 없이 종종 획득되거나 해제될 수 있는 user-mode mutex이다. 멀티프로세서 시스템에서, critical-section object는 처음에 다른 쓰레드들이 그 오브젝트를 해제하기를 기다리는 동안 spinlock을사용한다. 만약 그것이 너무 오랫동안 spins한다면, 그 획득하려는쓰레드는그러고나서 kernel mutex를 할당하고, 그것의 CPU를 포기한다. Critical-section objects는 특히 효율적인데, 왜냐하면 kernel mutex가 그 오브젝트에 대해 경쟁이 있을 때에만 할당되기 때문이다. 실제로, 거의 경쟁은 없어서,그래서 그 절약은 매우 크다.
Version 2.6이전에, Linux는 비선점형 커널이였는데, 이것은 kernel mode에서 작동하는 한 프로세스가 선점될 수 없다는것을 의미한다 - 비록 더 높은 우선순위 프로세스가 작동할 수 있게 이용가능 할지라도. 그러나, 이제 Linux kernel은 완전히 선점형이다. 그래서 한 task는 kernel에서 작동할 때 선점되어질 수 있다. Linux는 kernel에서 동기화를 위해 몇 가지 다른 메커니즘을 제공한다. 대부분의 컴퓨터 아키텍쳐가 간단한 수학 연산을 위해 atomic versions에 대해 명령어를 제공하기 때문에, Linux kernel내에서 가장 간단한 동기화 기법은 atomic integer이다. 이것은 opaque data type atomic_t를 사용하여 나타내어진다. 그 이름이 암시하듯이, atomic integers를 사용하는 모든 수학 연산들은 interruption없이 수행된다. 다음의 코드는 atomic integer counter를선언하고, 그러고나서 다양한 atomic 연산을 수행하는 것을 보여준다:

atomic_t counter;

int value;

atomic_set(&counter, 5); // counter = 5

atomic_add(10, &counter; // counter = counter + 10

atomic_sub(4, &counter); // counter = counter - 4

atomic_inc(&counter); // counter = counter + 1

value = atomic_read(&counter); // value = 12

Atomic integers는 특히 정수 변수 (counter 같은)가 업데이트될 필요가 있는 상황에서 효율적이다. 왜냐하면 atomic operations가 locking mechanisms의 오버헤드를 요구하지 않기 때문이다. 그러나, 그것들의사용은 이러한 시나리오의 종류에 제한된다. 가능한 race condition에 기여하는 몇 가지 변수가 있는 상황에서, 좀 더 정교한 locking tools이 사용되어야 한다.
kernel내의 critical sections을 보호하기 위해 Mutex locks을 사용하는것이 Linux에서 가능하다. 여기에서, 한task는 critical section을 들어가기전에 mutex_lock() 함수를 불러야만하고, critical section을 종료한 후에 mutex_unlock() 함수를 호출 해야만 한다. 만약 그 mutex lock이 이용가능하지 않다면, mutex_lock()을 호출한 task는 sleep state에 들어가고, lock의 주인이 mutex_unlock()을 부를 때 깨어난다. Linux는 또한 kernel에서 locking을 위해 spinlocks과 semaphores를 제공한다 (뿐만 아니라, 이러한 두 개의 locks의 reader-writer versions). SMP machines에서, 기본 locking mechanism은 spinlock이고, 그 kernel은 spinlock이 짧은 시간동안만 보유되도록 설계된다. 오직 단일 프로세싱 코어를 가진 임베디드 시스템 가은 단일프로세서 머신에서, spinlocks은 사용하기에 부적절하고, kernel 선점을 활성화/비활성화 하여 대체된다. 즉, 단일 프로세서 시스템에서, spinlock을 보유하기 보다, 그 kernel은 kernel 선점을 비활성화 한다; 그리고 spinlock을 해제하기 보다는, 그것은 kernel preemption을 활성화한다.
Linux는 kernel 선점을 비활성화하고 활성화 하는데 흥미로운 접근법을 상요한다. 그것은 커널 선점을 비활성화하고 활성화 하는데 두 개의 간단한 system calls을 제공한다 - preempt_disable()과 preempt_enable(). 그러나 만약 kernel에서 작동중인 한task가 lcok을 보유하고 있따면, 그 kernel은 선점되지 않는다. 이 규칙을 강화하기위해, 그 시스템에 있는 각 task는 그 task에 의해 보유된 locks의 개수를 가리키기 위해 counter인 preempt_count를 포함하는 자료구조 thread-info를 가진다. 한 lock이 얻ㅇ질 때, preempt_count는 증가한다. 한 lock이 해제될 때, 그것은 해제된다. 만약 현재 커널에서 작동중인 그 task에 대한 preempt_count의 값이 0보다 크다면, kernel을 선점하는 것은 안전하지 않다. 이 task가 현재 lock을 가지고 있기 때문이다. 만약 그 count가 0이라면, 그 커널은 안전하게 인터럽트 될 수 있다. kernel preemption을 활성화하고 비활성화하는 것과 함께, Spinlocks은 한 lock이 짧은 시간 보유될 때 (kernel preemption을 비활성화 하는 것)에만, kernel에서 사용된다. 한 lock이 더 오랜 시간 동안 보유될 떄, 세마포어나 mutex locks이 사용하기에 적절하다.
critical sections에 대해 접근을 제어하기 하기 위해, Solaris는 adaptive mutex locks, condition variables, semaphores, reader-writer locks, and turnstiles을 제공한다. adaptive mutex는 모든 critical data item에 대한 접근을 보호한다. 멀티프로세서 시스템에서, adaptive mutex는 spinlock으로 구현된 표준 세마포어로서 시작한다. 만약 그 데이터가 locked 되고 그러므로 이미 사용되고 있따면, 그 adaptive mutex는 두 가지 것들 중 하나를 한다. 만약 그 lock이 현재 또 다른 CPU에서 작동하고 있는 한 쓰레드에 의해 보유되었다면, 그 쓰레드는 그 lock이 이용해지기를 기다리면서 spins한다. 왜냐하면 그 lock을보유한 쓰레드가 곧 끝낼 가능성이 높기 때문이다. 만약 그 lock을 보유한 쓰레드가 현재 run state가 아니라면, 그 thread는봉쇄되고, 그 lock의 해제에 의해서 깨어날 때 까지 sleep 된다. 그것은 기다리는 동안 spin하지 않도록 하기 위해 sleep에 들어간다. 왜냐하면 그 lock이 곧 해제되지 않을 것이기 때문이다. sleeping thread에 의해 보유된 한 lock은 이 종류에 있을 가능성이 높다. 단일 프로세서 시스템에서, 그 lock을 보유한 쓰레드는 만약 그 lock이또 다른 쓰레드에 의해 테스트되고 있다면 결코 작동하지 않는다. 그러므로, 이러한 시스템의 유형에서, 쓰레드들은 항상 그들이 한 lock을 만나면 spin하기 보다 sleep 한다.
Solaris는 short code segments에 의해서 접근되는 데이터만을 보호하기 위해 adaptive-mutex method를 사용한다. 즉, 한 mutex는 한 lock이 몇 백개 안되는 명령어 아래에 대해서만 보유된다면 사용된다. 만약 그 code segment가 그것보다 더 길다면, spin-waiting method는 과도하게 비효율적이다. 이러한 긴 코드 segments에 대해, condition variables와 semaphores가 사용된다. 만약 그 요구되는 lock이 이미 보유되었다면, 그 쓰레드는 wait을 말하고 sleeps한다. 한 쓰레드가 그 lock을 해제 할 때, 그것은 queue에 있는 다음 sleeping thread에 신호를 보낸다. 한 쓰레드를 sleep에 들게하고, 그것을 깨우는 것의 추가 비용과 연관된 context switches의 비용은, spinlock에서 기다리는 몇 백개의 명령어를 기다리는 것의 비용 보다 더 낮다.
Reader-writer locks은 빈번히 접근되지만 read-only 방식으로 보통 접근되는 데이터를 보호하기 위해 사용된다. 이러한 상황에서, reader-writer locks은 세마포어보다 더 효율적인데, 여러 쓰레드들이 concurrently하게 데이터를 읽을 수 있기 때문이다. 반면에 세마포어는 항상 데이터에 대한 접근을 serialize한다. Reader-writer locks은 상대적으로 구현하기에 비싸다. 그래서 다시, 그것들은 코드의 긴 sections에 대해서만 사용된다.
Solaris는 adaptive mutex 또는 reader-writer lock 둘 중 하나를 얻으려고 기다리는 쓰레드들의 리스트를 순서짓기 위해 turnstiles를 사용한다. turnstile은 한 lock에 대해 봉쇄된 threads를 포함하는 queue structure이다. 예를들어, 만약 한 쓰레드가 현재 동기화된 오브젝트에 대해 lock을 소유한다면, 그 lock을 얻으려고 하는 모든 다른 쓰레드들은 봉쇄될 것이고, 그 lock에 대한 turnstile에 그 lock의 다음 owner로서 들어갈 것이다. 적어도 그 오브젝트의 lock에 봉쇠된 하나의 thread와 함께 각 동기화된 오브젝트는 별개의 turnstile을 요구한다. 그러나, 한 turnstile과 각 동기화된 오브젝트를 연관짓기 보다, Solaris는 각 커널 쓰레드에게 그것 자신의 turnstile을 준다. 한 쓰레드는 오직 한 오브젝트에 대해 한 time에 봉쇄될 수 있기 때문에, 이것은 각 오브젝트에 대해 turnstile을 갖는 것보다 더 효율적이다.
한 동기화된 오브젝트에 대해 봉쇄된 첫 번째 쓰레드에 대한 turnstile은 그 자체로 그 오브젝트에 대한 turnstile이 된다. 그 lock에 봉쇄된 쓰레드들은 나중에 이 turnstile에 더해질 것이다. 초기 thread가 그 lock을 해제할 때, 그것은 kernel에 의해 유지되는 free turnstiles의 리스트로부터 새로운 turnstiles을 얻는다. priority inversion을 방지하기 위해서, turnstiles은 priority-inheritance protocol을 따라서 구성된다.

chan blog

Post Lists

2019년 2월 25일 월요일

OS Chapter 5 : Process Synchronization

댓글 없음:

댓글 쓰기