[운영체제] Chapter6. Synchronization Tools(동기화)

CS/Operating System

[운영체제] Chapter6. Synchronization Tools(동기화)

TERRY✨ 2022. 5. 30. 20:33

1. Background

이 장에서는 프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성에 어떤 문제를 일으키는 지에 관해 설명한다.

Process communication method 인 1)message passing 2)Shared memory가 이루어 질때 충돌이 일어날 수 있다.

예) Producer-consumer problem

- 공유메모리(shared memory)를 사용할 때 Producer와 Consumer의 과정이 이루어 지면서 Buffer가 이용되는데 이때 충돌이 발생할 수 있다.

: Concurrent Access of Shared Data(공유데이터로의 동시접근)

자세하게 설명을 하자면, size가 5인 buffer(circular queue)가 있다고 할 때, Producer는 counter를 1씩 증가시키고, Consumer는 counter를 1씩 감소시킨다. 아래 producer와 consumer는 이를 구현한 코드이다.

Producer

//Producer
While(true){
    while(counter == BUFFER_SIZE); //true = 버퍼가 꽉참 / false = 버퍼 공간 있음, 다음줄로
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFERSIZE;
    counter++;
}

producer는 buffer입장에서 상시대기로 buffer에 채울 수 있는 공간이 있다면(버퍼가 비어있다면) 버퍼를 채우고 counter를 증가시키는 역할을 한다.

Consumer

//Consemer
while(true){
    while(counter == 0);//true = 버퍼 빔 / false = 버퍼 비어있지 않음
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
}

consumer는 producer와 완전히 반대로 돌아간다고 생각하면 된다.

하지만 여기서 문제가 발생할 수 있다!

Synchronization Problem

먼저 producer가 먼저 실행된 상태에서부터 상황을 살펴보자.

그 전에 counter라는 변수의 값이 어떤 과정을 거쳐 증가하고 감소하는 지 간략히 보자.

- counter++의 과정

//counter의 값이 레지스터에 저장되고 증가된 레지스터의 값을 counter에 다시 저장시키는 과정으로 진행된다. 
register_1 = counter
register_1 = register_1 + 1
counter = register_1

- counter--의 과정

register_2 = counter
register_2 = register_1 - 1
counter = register_2

[Normal situation]

- counter의 기존 값은 5

- producer와 consumer가 동시에 값을 증가시키고 감소시키는 상황

- 이상적으로는 counter가 5가 될 것으로 예상이 간다. 하지만 그렇지 않다.

Producer	Consumer
register_1 = counter (register_1 = 5)
register_1 = register_1 + 1 (register_1 = 6)
	register_2 = counter (register_2 = 5)
	register_2 = register_2 - 1 (register_2 = 4)
counter = register_1 (counter = 6)
	counter = register_2 (counter = 4)

synchronization problem 과정

counter의 값이 5이기 때문에 producer와 consumer모두 counter의 값을 5로 받아온다. 그래서 register_1, register_2에는 각각 5가 저장이 된다.
producer와 consumer는 각각 register의 값을 1 증가시키고 감소시킨다.
register의 값을 counter에 저장하는 과정에서 producer은 6의 값을 받고, consumer에서는 4의 값을 받음을 확인할 수 있고 이때 problem이 발생한다.

따라서,

이처럼 프로세스가 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 Race condition(경쟁 상태)라고 한다.

race condition을 해결하기 위해서 synchronization이 되어져야 한다고 생각하면 된다.

2. The Critical-Section Problem

프로세스 동기화에 대한 문제는 critical section problem이라고 불리는 문제로부터 시작한다.

여기에 n개의 프로세스 {p0, p1, ..., p(n-2)}가 존재한다고 하자.

그 전에 critical section이란?

- 코드에서 race condition이 발생할 수 있는 특정 부분을 critical section이라고 한다.

- critical section이 사용되는 시스템에서는 한 프로세스가 자신의 임계구역에서 수행하는 동안에 다른 프로세서들은 그들의 임계구역에 들어갈 수 없다.

즉, critical-section problem이란 프로세서들이 데이터를 협력적으로 공유하기 위하여 자신들의 활동을 동기화할 때 사용할 수 있는 프로코톨(약속)을 설계하는 것이다.

각 프로세스는 자신의 critical section으로 진입하려면 entry section에서 진입 허가를 요청해야 하고, critical section 뒤에는 exit section이 따라올 수 있다. 코드의 나머지 부분들을 총칭하여 remainder section이라고 한다.

이를 코드로 나타내면 아래와 같다.

do{
    entry section
        critical section
    exit section
        remainder section
}while(true);

각 프로세서에서 critical section의 데이터는 shared data에서 데이터를 공유할 수 있다.

Critical Section Problem을 해결하기 위해선 몇가지 조건을 충족해야 한다.

Mutual Excludion(상호 배재) : 이미 한 process가 critical section에서 작업중이면 다른 process는 critical section에 진입해서는 안된다.
Progress(진행) : critical section에서 작업중인 process가 없다면 다른 process가 critical section에 진입할 수 있어야 한다.
Bounded Waiting(한정 대기) : critical section에 진입하려는 process가 무한하게 대기해서는 안된다.

Critical-section Handling in OS

- pid를 할당할 때 race condition의 예

프로세스 p0와 p1이 동시에 fork()를 이용하여 child processes를 만들려고 한다.
다음으로 이용가능한 process의 id(pid)를 나타내는 'next_available_pid' 변수에서 race condition이 일어난다.
만일 mutual exclusion(상호 배재)가 없다면 같은 pid가 두개의 다른 프로세스에 배정될 수 있다.

- 운영체제 내에서 critical section을 다루기 위해 Preemptive kernels과 Non-preemptive kernels의 두가지 일반적인 접근법이 사용된다.

preemptive kernels(우선순위 높은거)
- 프로세스가 커널 모드에서 수행되는 동안 선점되는 것을 허용한다.
- 선점형 커널에 대해서는 동일한 주장을 할 수 없어 race condition이 발생할 수 있기 때문에 공유되는 커널 자료구조에서 race condition이 발생하지 않는다는 것을 보장하도록 신중하게 설계되어야 한다.
Non-preemptive kernels
- 커널 모드에서 수행되는 프로세스의 선점을 허용하지 않고 커널 모드 프로세스는 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 수행된다.
- 한 순간에 커널 안에서 실행 중인 프로세스는 하나밖에 없으므로 race condition을 염려할 필요는 없다.

커널모드 프로세서가 대기 중인 프로세서를 양도하기 전에 오랫동안 실행할 위험이 적기 때문에 선점형 커널은 더 응답이 민첩할 수 있다. 하지만 선점형 커널을 설계하기 앞서 경쟁 조건을 잘 고려해야만 한다.

3. Peterson's Solution

Peterson's Solution이란 critical-section problem을 다루기 위한 고전적인 소프트웨어 기반 해결책이다.

modern architecture에는 사용될 수 있는지는 보장되지 않음
하지만 그 문제를 해결하기에는 좋은 알고리즘 설명이다.
Critical section과 Remainder section을 번갈아 가며 실행하는 두개의 프로세서(pi, pj)로 한정된다.
load와 store machine language 명령어가 atomic하다. 즉 두 명령어는 실행중에 중단하지 않는다(interrupt 되지 않는다.)
두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.
- int turn; //critical section으로 진입할 순번을 나타내는 변수
- boolean falg[2]; // 각 프로세서가 critical section으로 진입할 준비가 되었다는 것을 표현한 배열

Pi의 Peterson 알고리즘

int turn;
boolean flag[2]; //flag[i] == true -> pi 준비됐다!
...
while(true){
    flag[i] = true;
    turn = j;
    while(falg[j] && turn == j);
    /* critical section */
    flag[i] = false;
    /* remainder section */
}

peterson's solution의 과정(상태)

p0, p1의 프로세서들이 존재한다고 가정하자.

p0가 먼저 시작
- flag[0] = true
- turn = 1
그 뒤로 바로 p1도 시작
- flag[0] = true
- flag[1] = true
- turn = 1 -> 0
p0 critical section 진입 ( while(flag[1] && turn == 1); -> false)
- flag[0] = true -> false
- flag[1] = true
- turn = 0
p1 critical section 진입( while(flag[0] && turn == 0); -> false)
- flag[0] = false
- flag[1] = false
- turn = 0
p0 입장에서 critical section 다음으로 while문을 또 돌고 있다. 그런데 4번에서 flag[1] = false가 됐으므로 p0은 critical section진입 가능
- flag[0] = true-> false(CS 진입이후)
- flag[1] = false
- turn = 1
- p1에서도 turn = 0으로 바꾸므로 p0이후로 critical section 진입 가능, 계속 반복적 -> atomic

Proof of Peterson's Solution

peterson's solution이 critical section 문제를 해결하기 위해선 3가지 요구조건을 만족해야 한다.

Mutual Exclusion(상호배재)
- 만약 pi와 pj가 둘다 critical section에 들어갔다면,
- flag[0] = flag[1] = true 일수밖에 없고
- turn도 0, 1둘다 해당되어져야만 한다. 하지만 turn은 그럴 수 없다.
- 그러므로 mutual exclusion은 만족한다.
Progress(진행) & Bounded waiting(한정 대기)
- pi의 blocking condition : while(flag[j] && turn == j);
  - 만약 pj가 아직 critical section에 들어갈 준비가 안됐다면 : flag[j] = false; -> pi는 critical section에 들어갈 수 있음!
  - 만약 pj가 while문에서 기다리고 있고, turn은 i, j 둘 다 가능일때
  - 만약 turn = i가 된다면 pi는 critical section에 들어감
  - 만약 turn = j가 된다면 pj는 critical section 에 들어감
    - pj가 critical section을 끝낸다면 pj는 flag[j] = false로 만든다. 그리고 pi는 critical section으로 들어갈 수 있다. pj가 turn을 i로 바꿨기 때문!
- 그러므로 pi는 critical section으로 들어갈 수 있고(progress), 그저 하나의 process만 기다리게 된다 (bounded waiting)

Peterson's solution은 최신 컴퓨터구조에서는 작동한다고 보장되지 않는다. 주된 이유는 시스템 성능을 향상하기 위해 프로세스 또는 컴파일러가 종속성이 없는 읽기 및 쓰기 작업을 재정렬 할 수 있기 때문이다. 예로 들어, Peterson 해결안의 entry section의 첫 두 문장의 순서를 바꾸게 되면(아래 예시) critical solution의 문제를 해결 할 수 없다.

entry section에서의 첫 두문장의 순서를 바꿨을 때 예시

두 개의 thread가 공유하는 데이터
- boolean flag = false;
- int x = 0;
Thread1
- while(!flag);
- print x;
Thread2
- x = 100;
- flag = true;
예상되는 output
- 100이 출력 될 것임.
- 하지만 만약 Thread2에서 두 줄의 위치를 서로 바꾼다면? -> output = 0

이 예시가 peterson's solution으로 적용된다면?

4. Hardware Support for Synchronization

Critical Section Problem의 소프트웨어 기반 해결책(peterson's solution)은 최신 컴퓨터구조에서 작동하지 않을 수 있다.

그래서 hardware의 지원이 필요한데, 4절에서는 Critical section problem을 해결하기 위한 자원을 제공하는 세 가지 하드웨어 명령(hardware support)을 제시한다.

Memory barriers
Hardware instructions
Atomic variables

1) Memory Barriers(메모리 장벽)

: 컴퓨터구조는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장한다. 이러한 명령어를 메모리 장벽(Memory Barriers) 또는 메모리 펜스(Memory Fences)라고 한다.

메모리 장벽 명령어가 실행될 때, 시스템은 후속 load 또는 store 연산이 수행되기 전에 모든 load 및 store 연산이 메모리에서 완료되도록 한다. 따라서 명령이 재정렬 되더라도 메모리 장벽은 future load 또는 store 작업이 수행되기 전에 저장 작업이 메모리에서 완료되어 다른 프로세서에 보이도록 한다.
이 작업은 매우 low-level(낮은 수준)의 작업이다.
일반적으로 Mutual Exclusion을 보장하는 특수 코드를 작성할 때 커널 개발자만 사용한다.

예시)

위에 나왔던 x = 100을 출력하는 예시를 가져와보자

//Thread1
//x 전에 flag가 load 되는 것을 보장함
while(!flag)
	memory_barrier();
print x;

//Thread2
//x 가 발생하는 것을 ensure. flag가 assign 되기 전에
x = 100;
memory_barrier();
flag = true;

memory_barrier();을 해줌으로써 x와 flag가 저장되는 것을 보장한다.

//Peterson's solution
while(true){
	flag[i] = true;
    memory_barrier();
    turn = j;
    while(flag[j] && turn == j);
    ...
}

2) Hardware Instructions

많은 현대 기계들은 한 워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 atomical하게(계속적으로) 교환할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공한다. 우리는 이들을 사용하여 간단한 방식으로 Critical Section 문제를 해결할 수 있다.

Test-and-Set instruction
Compare-and-Swap instruction

Test-and-Set instruction

//Definition
boolean test_and_set(boolean *target){
    boolean rv = *target;
    *target = true;

    return rv;
}

계속적으로(atomically) 실행된다.
매개변수의 기존 값(original value)을 return한다.
매개변수의 값에 새 값을 설정한다.

이를 활용한 Critical Section의 Mutual Exclusion 해결 알고리즘은 아래와 같다.

do{
    while(test_and_set(&lock));
    /* critical section */
    lock = false;
    /* remainder section */
}while(true);

만약 process가 두개(p0, p1)가 있다고 하자.

기존의 lock이 false이면, p0는 false를 반환받아 critical section으로 들어갈 수 있다. 하지만 실제 lock의 값은 true로 변경되었으니 p1은 계속 while에 갇혀있게 된다. p0에서 critical section으로 들어갔다면 lock은 false로 바뀌면서 p1의 while조건인 test_and_set의 반환이 false가 되어 p1은 critical section으로 들어간다. 이때 lock은 또 true로 바뀌므로 p0은 while문에 갇히게 된다. 이렇듯 p0와 p1이 왔다갔다 계속적으로 반복할 수 있다.

Compare-and-Swap instruction

//Definition
int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}

또한 atomical하게 작동된다.
전달된 매개변수 값의 기존 값(original value)를 return 한다.
매개변수의 값은 new_value로 바꿔준다. 하지만 이는 *value == expected 가 true일때만 실행하도록 한다.

이를 활용한 Critical Section의 Mutual Exclusion 해결 알고리즘은 아래와 같다.

while(true){
    while(compare_and_swap(&lock, 0, 1) != 0);
    /* critical section */
    lock = 0;
    /* remainder section */
}

역시나 프로세스가 p0, p1 두개가 있다고 하자

원래 lock = 0이라고 하고 시작하자. p0이 먼저 compare_and_swap을 실행하면 기존값이던 0을 반환하므로 while문 조건은 false가 되어 critical section으로 들어간다. p1 입장에서 보면 lock은 1로 바꼈으니 compare_and_swap이 1을 반환하므로 조건은 true가 되어 critical section으로 들어가지 못한다. 하지만 p0가 critical section에서 lock=0을 수행하게 되면 그때 p1은 compare_and_swap이 0을 반환하여 조건이 false가 되고 critical section으로 들어갈 수 있다. 이러한 일이 반복적으로 수행된다.

이를 그림으로 표현하면 아래와 같다.

하지만, 위의 예시는 bounded waiting 요구를 충족하지 못한다.

이유는 아래와 같다.

Bounded waiting mutual exclusion을 만족하기 위해선 아래와 같은 코드로 작성이 되어야 한다.

boolean waiting[n]; //n = process개수, initialized to false
int lock; //initialized to 0
while(true){
    waiting[i] = true;
    key = 1;
    while(waiting[i] && key == 1)
        key = compare_and_swap(&lock, 0, 1);
    waiting[i] = false;
    /* critical section */
    j = (i +1) % n;
    while((j != i) && !waiting[j])
        j = (j+1) % n;
    if(j == i)
        lock = 0;
    else
        waiting[j] = false;
    /* remainder section */
}

pi가 critical section에 진입하는 경우는 오직 waiting[i] == false 이든지 key == 0 이 되어야 한다. lock이 0일 때에만 key가 0이 되고 lock 이 1로 바뀌면서 무한 루프에서 빠져나올 수 있다.

waiting[i]를 false로 바꾸고 critical section을 실행한 뒤, i를 순차적으로 증가시켜 자신과 같을 때까지 혹은 i가 기다리고 있을 때까지 무한 루프를 돌고, 선택된 프로세스를 critical section에 진입할 수 있도록 해주는 알고리즘이다.

3) Atomic Variables

Atomic Variable은 integers 및 booleans과 같은 기본 데이터 유형에 대한 Atomic 연산을 제공한다. Atomic Variable은 카운터가 증가할 때와 같이 갱신되는 동안 단일 변수에 대한 데이터 경쟁이 있을 수 있는 상황에서 상호 배제를 보장하는데 사용될 수 있다.

예)

//increment function
void increment(atomic_int *v){
    int temp;
    do{
        temp = *v;
    }while(temp != compare_and_swap(v, temp, temp+1));
}
//p1 : temp = 10, *v = 11
//p2 : temp = 10, *v = 12

5. Mutex Locks

Mutex lock은 mutual exclusion lock의 축약형태로 Critical section 문제를 해결하기 위한 Hardware기반의 해결책(ex.Peterson's solution)보다 상위 수준의 해결책이다. Critical Section을 보호하고, 따라서 Race condition을 방지하기 윈해서 mutex lock을 사용한다.

Mutex lock에서는 세가지를 알아야 한다.

acquire(): lock을 획득하는 함수
release(): lock을 반환하는 함수
available: lock의 가용 여부를 표시하는 변수

acquire함수와 release함수는 반드시 atomic하게 작동되어야 한다.

//acquire 함수
acquire(){
    /* busy waiting */
    while(!available);
    available = false;
}

//release 함수
release(){
    available = true;
}

mutex lock을 사용하여 critical section problem을 해결하는 알고리즘은 아래와 같다.

while(true){
    acquire lock
        critical section
    release lock
        remainder section
}

하지만 이러한 구현 방식의 단점은 busy waiting을 해야한다는 것이다. busy waiting이란 프로세스가 critical section에 있는 동안 critical section에 들어가기 원하는 다른 프로세스들은 acquire()함수를 호출하는 반복문을 계속 실행해야 하는 상황을 말한다. 이러한 busy waiting은 다른 프로세스가 생산적으로 사용할 수 있는 CPU 주기를 낭비한다.

이러한 busy waiting을 일으킬 수 있는 mutex lock과 같은 유형은 spinlock(스핀락)이라고 불리기도 한다.

6. Semaphores

Semaphores 역시 동기화 툴이다. 그런데 Semaphores은 Mutex lock보다 더 세련된 방법이다. 세마포는 카운터를 이용해 동시에 리소스에 접근할 수 있는 프로세스를 제한한다. 세마포는 P와 V라는 명령으로 접근할 수 있다.

아래 코드에서 Semaphore S 는 정수 변수로서, 초기화를 제외하고는 단지 두개의 표준 atomical 연산 wait()와 signal()로만 접근할 수 있다.

wait()는 아래와 같다.

wait(S){
    while(S <= 0); //waits for the lock
    S--; // holds the lock
}

signal()는 아래와 같다.

signal(S){
	S++; // release the lock
}

1) Semaphores Usage

운영체제는 Counting과 binary 세마포를 구분한다.

Counting Semaphores
- Interger value S는 제한없는 값을 가짐
- 유한한 개수를 가진 자원(가능한 자원의 개수로 초기화 됨)에 대한 접근을 제어하는데 사용될 수 있다.
Binary Semaphores
- Integer value는 0과 1 중에만 가능하다.
- mutex lock과 비슷하다.

2) Semaphore Implememtation

위 wait()의 while은 spinlock으로 busy waiting이 일어난다. 이러한 busy waiting을 피하기 위해 세마포 S를 대기하면서 일시 중지된 프로세스는 다른 프로세스가 signal()연산을 실행하면 재시작되어야 한다. 프로세스는 sleep()에 의해서 일시 중지된고 wakeup()에 의해 재시작된다.

세마포를 이용해서 critical section problem을 해결하는 알고리즘을 구현하기 위한 세마포의 정의는 아래와 같다.

typedef struct{
    int value;
    struct process *list; // head of linked list for waiting queue
}semaphore;

변경된 wait()와 signal()은 아래와 같다.

wait(semaphore *S){
	S->value--;
    if(S->value < 0){
    	add this process to S->list;
        sleep(); //suspend
    }
}

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

wakeup()과 sleep()는 프로세스를 일시 중지 또는 재실행시키는 운영체제의 기본적인 시스템 콜이다.

세마포의 프로세스 리스트는 Bounded Waiting을 보장하도록 잘 구현해야만 한다.

단일 Processor 환경에서는 wait()와 signal()이 atomic하게 실행되는 것을 보장하기 위해 실행되는 동안 인터럽트를 금지함으로써 해결할 수 있지만, 다중 코어 환경에서는 모든 처리 코어에서 인터럽트를 금지하여야만 한다. 이는 매우 어려울 수 있으며 성능을 심각하게 감소시킬 수 있음으로 많은 부분을 고려해야만 한다.

7. Monitors(모니터)

mutex lock 또는 Semaphore를 사용할 때에도 타이밍 오류는 발생할 수 있다. 예를 들어, wait()와 signal()의 순서가 뒤바뀌는 경우, Critical Section이 끝나고 signal()대신 wait()가 호출되는 경우에 그렇다.

Semaphore의 올바른 사용법은 아래와 같다.

wait(mutex);
/* critical section */
signal(mutex);

이러한 오류를 해결하기 위한 한가지 전략은 모니터(Monitor)를 사용하는 것이다.

1) Monitors란?

편리하고 효과적인 동기화 도구를 지지하기 위한 high-level language contructs.

Monitor type: 모니터 내부에서 프로그래머가 정의한 mutual exclusion이 보장되는 일련의 연산자 집합을 포함하는 ADT이다.
- ADT(추상화된 데이터 형, abstract data type)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호한다. 이때 함수의 구현은 ADT의 특정한 구현과 독립적이다.
- 오직 하나의 프로세스만 모니터에서 active하다(mutual exclusion)
Pseudocode syntax of monitor

monitor monitor-name
{
    //shared variable declarations
    function P1 (...) {...}
    function P2 (...) {...}
    function P3 (...) {...}
    initialization code (...) {...}
}

2) Schematic view of a Monitor

monitor의 개략도는 아래와 같다.

모니터 안에는 3가지의 components들이 정의가 되어야 하는데, shared data, operations, initialization code가 이에 해당된다.
또한 entry queue가 존재하는데, entry queue안에는 프로세스가 있다. 이 프로세스들은 모니터에 들어가기 위해 기다리고 있다.

모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화되도록 보장해 준다(mutual exclusion). 하지만 지금까지 정의한 모니터 구조물은 어떤 동기화 기법을 모델링하는 데에는 충분한 능력을 제공하지 않는다.

monitor의 예

- Monitor in Java : Synchronized method

class Producer{
    private int product;
    ...
    private synchronized void produce(); //mutually exclusive
}

synchronized method를 이용하여 mutual exclusion을 보장할 수 있다.

만약 위 코드에서 private synchronized void B();라는 함수가 추가가 된다고 가정하자. Process A, Process B가 있는 상황에서 PA가 produce()함수에 접근하길 원하고 PB가 B()함수에 접근하기 원한다고 한다면 Synchronized method에 의해서 오직 한 프로세스가 하나의 함수만 접근할 수 있다.

3) Condition Variables

Condition Variables은 추가적인 동기화 기법(additional synchronization mechanism)이다.

Condition 형의 변수 정의(Variable declaration)
- condition x, y;
condition형 변수에 호출될 수 있는 연산은 오직 wait()와 signal()이다.
- x.wait(); // 이 연산을 호출한 프로세스는 다른 프로세스가 x.signal()을 호출할 때까지 일시 중지 되어야 한다는 것을 의미한다.
- x.signal(); // 일시 중지된 프로세스를 풀어준다. 만약 waiting하고 있는 프로세스가 없다면 아무일도 일어나지 않는다.

4) Condition Variables Choices

만약 process P가 x.signal()을 호출하고, process Q가 x.wait()에서 일시 중단 됐다면, 무엇이 다음에 일어날까?
- Q와 P 모두 동시에 실행될 수 없기 때문에 Q가 진행됐다면 P는 대기해야 한다. 모니터에서는 오직 하나의 프로세스만 실행이 가능하기 때문이다. 그래서 여기에는 두가지 상황이 일어날 수 있다. 그것은 아래와 같다.
두 가지 옵션(상황)
- Signal and wait: 만약 P가 x.signal()을 불렀다면 Q가 실행되고 P는 Q가 monitor을 떠날때까지 기다리거나 다른 condition을 기다랴야 한다. (Q가 먼저 시작)
- Signal and continue: P가 x.signal()을 불렀다면 Q는 P가 monitor을 떠날때까지 기다리거나 다른 condition을 기다려야 한다. (P가 끝날때까지 기다리기)
- 위의 둘은 모두 장단점이 존재한다. 하지만 signal and continue가 조금 더 reasonable하다.

5) Implementing a Monitor Using Semaphores

각 모니터마다 mutex라는 binary semaphore가 정의되고 그 초기 값은 1이다. 프로세스는 모니터로 들어가기 전에 wait(mutex)를 실행하고 모니터를 나온 후에 signal(mutex)을 실행해야 한다.

Funtions to implement(실행시킬 함수들)
- External procedures
- wait() of condition variable
- signal() of condition variable

모니터 구현 시 signal-and-wait기법을 사용한다. signaling 프로세스는 실행 재개되는 프로세스가 모니터를 떠나는지 아니면 wait()할 때까지 그 자신이 다시 기다려야 하므로 next라는 binary semaphore 가 추가로 필요하게 되고 0으로 초기화 된다.

두개의 semaphores가 필요하다.
- semaphore mutex = 1; // mutual exclusion
- semaphore next = 0; // signaling process should wait until the resumed process leaves monitor
- int next_count = 0; // the number of precesses suspended on next(semaphore)
External procedure F

wait(mutex);
    ...
    body of F;
    ...
if(next_count > 0)
    signal(next)
else
    signal(mutex);

Conditional variables
- Required data
  - semaphore x_sem; // (initially, 0)
  - int x_count = 0; // wait 하고 있는 프로세스의 수

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--;
    }
}

6) Resuming Precesses within a Monitor

If several processes queued on conditio variable x, and x.signal() is executed, which process should be resumed?(조건 변수 x에 여러 프로세스가 일시 중지 되어 있을 때, 어떠한 프로세스를 수행 재개시킬 것인가?)
FCFS(First Come First Served)순이 가장 간단한 방법으로 사용될 수 있다고 생각이 들지만 많은 경우 이러한 간단한 스케줄링 기법은 충분하지 않다.
이를 위해 conditional-wait 구조를 사용할 수 있다.
- 이 구조는 다음과 같은 형태를 가진다.
- x.wait(c);
- 여기서 c는 정수이며, 우선순위 번호(priority number)라고 불린다. 일시 중지 되는 프로세스의 이름과 함께 저장된다.
- x.signal()이 수행되면 가장 작은 우선순위 번호를 가진 프로세스가 다음번에 수행 재개 된다.

7) Single Resource Allocation

모니터는 Resource를 사용할 최대 시간을 지정하는 우선 순위 번호를 사용하여 여러 경쟁 프로세스 중에서 한 개의 Resource을 할당해 준다. 이 Resource를 액세스 하려는 프로세스는 아래의 순서를 따라야 한다.

R.acquire(t);
...
access the resource;
...
R.release;

여기서 R은 ResourceAllocator type의 한 instance이다.

8) A Monitor to Allocate Single Resource

아래는 ADT인 ResourceAllocator 모니터를 구현한 것이다.

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;
    }
}

8. Liveness(라이브니스)

라이브니스란 프로세스가 실행 life cycle 동안 진행(progress)되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성을 말한다.

라이브니스 실패의 예: 프로세스가 lock을 얻기 위해 무기한 대기하는 것

liveness 실패의 이유

Deadlock
Priority inversion
Many other reasons

Deadlock(교착상태)
- 대기 큐를 가진 Semaphore 구현에서 두 개 이상의 프로세스들이, 오로지 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 signal()을 무한정 기다리는 상황이 발생할 수 있다. 이런 상태에 도달했을 때, 이들 프로세스들을 deadlock이라고 한다.
- 즉, 두 개 이상의 프로세스가 대기 중인 프로세스 중 하나로 인해 발생할 수 있는 이벤트를 무한정 대기하고 있는 상황이다.
- 이때 "이벤트"란, mutex lock과 Semaphore같은 Resource의 획득과 방출이다.
Starvation (infinite blocking)
- Semaphore에서 한 프로세스가 무한정하게 기다리고 있는 상황
- ex) waiting list is implemented by LIFO order
Priority inversion(우선순위 역전)
- 높은 우선순위 프로세스가 현재 낮은 우선순위 프로세스 또는 연속된 낮은 우선순위 프로세스들에 의해 접근되고 있는 커널 데이터를 읽거나 변경할 필요가 있을 때 스케줄링의 어려움이 생기게 된다.
- 커널데이터는 락에 의해 보호되기 때문에 낮은 우선순위 프로세스가 자원의 사용을 마칠 때까지 높은 우선순위 프로세스가 기다려야 한다. 낮은 우선순위 프로세스가 또 다른 높은 우선순위 프로세스에 의해 선점되는 경우에 상황은 더욱 복잡해진다. 이러한 경우 낮은 우선순위 프로세스는 계속 기다려야만 한다.
  - 예시**
  - L, M, H 세 개의 process가 존재
  - 우선순위는 L < M < H
  - H는 L에 의해 Semaphore S를 기다린다.
  - L은 M을 기다려야 한다. 그것의 낮은 우선순위 때문에
  - 따라서 H도 M을 기다린다.