병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성에는 문제점이 생길 수 있다.
동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라고 한다.
경쟁 상황으로부터 보호하기 위해, 우리는 한순간에 하나의 프로세스만이 데이터를 조작하도록 보장해야 한다. 이러한 보장을 위해, 우리는 어떤 형태로든 프로세스들이 동기화되도록 할 필요가 있다.
Preemptive Kernel은 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.
Nonpreemptive Kernel은 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행된다.
커널 모드 프로세스가 대기 중인 프로세스에 프로세서를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널은 더 응답이 민첩할 수 있다. 하지만 선점형 커널을 설계하기 앞서 race condition을 잘 고려해야만 한다.
각 프로세스는 임계구역(critical section)이라고 부르는 코드를 포함하고 있고, 그 안에서는 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있다. 이 시스템의 중요한 특징은 한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스들은 그들의 임계구역에 들어갈 수 없다는 사실이다.
상호 배제(mutual exclusion)
프로세스 Pi가 자기의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없다.
진행(progress)
자기 임계구역에 실행중인 프로세스가 없고, 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는 데 참여할 수 있으며, 이 선택은 무한정 연기될 수 없다.
한정된 대기(bounded waiting)
프로레스가 자기의 임계구역에 진입하려는 요청을 한 후 요청이 허용될 때까지 다른 프로세스들이 그들의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
int turn;
boolean flag[2];
변수 turn은 임계구역으로 진입할 순번을 나타낸다. 만약 turn == i 이면 프로세스 P(i)가 임계구역에서 실행될 수 있다.
flag 배열은 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.
만약 flag[1] = true 라면 P(1)은 임계구역으로 진입할 준비가 되었다는 것이다.
임계 구역으로 진입하기 위해서는 P(i)는 먼저, flag[i]를 true로 만들고 turn을 j로 지정한다.
이렇게 함으로써, 프로세스 j가 임계 구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.
프로세스 P(i)
while(true){
flag[i] = true;
turn = j;
while(flag[j] && turn == j)
// critical section
flag[i] = false;
//remainder section
}
프로세스 P(j)
while(true){
flag[j] = true;
turn = i;
while(flag[i] && turn == i)
// critical section
flag[j] = false;
//remainder section
}
boolean test_and_set(boolean *target){
boolean rv = *target;
*target = TRUE;
return rv;
}
do{
while(test_and_set(&lock))
//do nothing
//critical section
lock = FALSE;
//remainder section
}while(true);
lock이라는 공유 변수가 한 프로세스에서 false일 경우 lock을 true로 만들고 자신은 Critical Section으로 들어간다. Critical Section에서 빠져나온 프로세스가 lock을 false로 만들면 다른 프로세스가 Critical Section에 들어가고 이러한 과정이 반복된다.
boolean swap(boolean *a, boolean *a){
boolean temp = *a;
*a = *b;
*b = temp;
}
while(true) {
key = TRUE;
while(key == TRUE)
swap(&lock, &key);
//critical section
lock = FALSE;
//remainder section
}
lock이라는 공유 변수가 한 프로세스에서 false일 경우 lock을 true로 만들고 key는 false로 만들어 자신은 Critical Section으로 들어간다. Critical Section에서 빠져나온 프로세스가 lock을 false로 만들면 다른 프로세스가 Critical Section에 들어가고 이러한 과정이 반복된다.
정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공한다. 원자적 변수는 카운터가 증가할 때와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는데 사용할 수 있다.
원자적 변수를 지원하는 대부분의 시스템은 원자적 변수에 접근하고 조작하기 위한 기능뿐만 아니라 특별한 원자적 데이터 유형을 제공한다.
세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적(atomical) 연산 wait()와 signal()로만 접근할 수 있다.
wait(S) {
while (S <= 0);
S--;
}
signal(S) {
S++;
}
Semaphore S; // initailized to 1
wait(S);
// Critical Section
signal(S);
운영체제는 카운팅(counting)과 이진(binary) 세마포를 구분한다.
카운팅 세마포는 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.
먼저 세마포는 가용한 자원의 개수로 초기화되며, 각 자원을 사용하려는 프로세스는 세마포에 wait() 연산을 수행하고, 세마포의 값은 감소한다.
자원을 방출할 때는 signal() 연산을 수행하고, 세마포는 증가하게 된다. 만약 세마포의 값이 0이면 모든 자원이 사용 중임을 나타내는 것이다.
Busy Waiting을 피하기 위해 세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal() 연산을 실행하면 재시작되어야 한다. 프로세스는 sleep() 연산에 의해서 일시 중지되고 wakeup() 연산에 의하여 재시작된다. (대기상태 <-> 준비 완료 상태)
typedef struct {
int value;
struct process *list;
}semaphore;
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);
}
}
wakeup()과 block()은 프로세스를 일시 중지 or 재실행시키는 운영체제의 기본적인 시스템 콜이다.
세마포의 프로세스 리스트는 Bounded Waiting를 보장하도록 잘 구현해야만 한다.
mutex락 혹은 세마포어를 사용할 때에도 타이밍 오류는 여전히 발생할 수 있다.
예로들어, wait()과 signal() 연산의 순서가 뒤바뀌는 경우
Critical Section이 끝나고 signal()대신 wait()이 호출되는 경우
모니터(monitor)는 이러한 오류를 처리하기 위한 한 가지 전략으로 간단한 동기화 도구를 통합하여 고급 언어 구조물을 제공하는 것이다.
모니터 형은 모니터 내부에서 프로그래머가 정의한 상호 배제가 보장되는 일련의 연산자 집합을 포함하는 ADT이다. 모니터 형은 인스턴스의 상태를 정의하는 변수들과 이를 조작할 수 있는 프로시저 또는 함수들의 본체도 같이 포함하고 있다.
따라서 모니터 내에 정의된 함수만이 오직 모니터 내에 지역적으로 선언된 변수들과 형식 매개변수들에만 접근할 수 있다.
모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장해 준다. 그러나 지금까지 정의한 모니터 구조물은 어떤 동기화 기법을 모델링하는 데에는 충분한 능력을 제공하지 않는다.
condition이라는 구조물로 동기화 기법들을 제공해 보자. 자신의 동기화 기법을 작성할 필요가 있는 프로그래머는 하나 이상의 condition 형의 변수를 정의할 수 있다.
condition x,y;
이 condition 형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()이다. x.wait()은 이 연산을 호출한 프로세스는 다른 프로세스가 x.signal()을 호출할 때까지 일시 중지 되어야 한다는 것을 의미한다.
라이브니스는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성을 말한다.
대기 큐를 가진 Semaphore 구현은 두 개 이상의 프로세스들이, 오로지 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 signal()연산를 무한정 기다리는 상황이 발생할 수 있다. 이런 상태에 도달했을 때, 이들 프로세스들을 교착 상태(deadlock)라고 한다.
한 집합 내의 모든 프로세스가 그 집합 내의 다른 프로세스만이 유발할 수 있는 이벤트를 기다릴 때, 이 프로세스들의 집합이 교착 상태에 있다고 말한다. 우리가 여기서 주로 관심을 두고 있는 “이벤트”들은 mutex 락과 Sempahore 같은 자원의 획득과 방출이다.