[운영체제] 5주차: 동기화를 위한 H/W적 수단

일반적으로 시스템에서 Synchronization hardware를 제공해 critical section 문제를 해결함

 

가장 간단한 방법은 interrupt를 비활성화해 context switch가 일어나지 않도록 하는 것이나 이 경우에는

다른 부분에도 영향을 많이 미칠 수 있음

특히 Uniprocessor가 아닌 Multiprocessor의 경우 전체 프로세스에 대해 모든 interrupt를 disable해야 하기 때문에 비용도 많이 든다.

 

구성

앞에서 본 Critical section 문제를 해결하는 방법이랑 똑같다고 보면 됨

Critical section에 진입하기 전에 lock을 획득하고 Critical section 실행이 끝나면 lock을 release 함

 

 

Hardware instruction

다음의 atomic(non-interruptable)한 instruction을 이용해 critical section 문제를 해결할 수 있다.

 

$TestAndSet()$

$Swap()$

 

 

$TestAndSet$

boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = true;
    
    return rv;
}

target으로 들어온 값을 내부 변수에 저장한 후 그 값을 true로 바꾸고 내부 값을 반환함

 

Solution using $TestAndSet$

do {
    while(TestAndSet(&lock));
    //Critical section
    lock = false;
    //Remainder section
} while(true)

($lock$은 $false$로 초기화되어 있다)

 

이 solution은 Bounded waiting 조건 을 만족하지 못 한다.

$P_1$, $P_2$가 있을 때 $P_1$가 critical section에 진입했다 나온 후 다시 진입하려면 $lock$이 $false$로 바뀌어있기 때문에

$P_1$은 언제든 다시 critical section에 진입할 수 있다. 결국 $P_2$는 무한정 기다리게 될 수 있다.

따라서 Mutual exclusion은 만족하지만 Bounded waiting은 만족하지 못 한다.

 

 

$compare\_and\_swap$

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

 

Solution using $compare\_and\_swap$

do {
    while(compare_and_swap(&lock, 0, 1) != 0);
    //Critical section
    lock = 0;
    //RemainderSection
} while(true);

이 solution 역시 TestAndSet과 같은 이유로 Bounded waiting을 만족하지 못 한다.

 

 

Bounded Waiting을 만족하려면 다음과 같이 코드를 작성해야 한다.

do {
    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);

5개의 process $P_0,\; P_1,\; P_2,\; P_3,\; P_4$가 있다고 하자.

처음에 $P_2$가 critical section에 진입하려 한다고 하자.

$key$를 $true$로 바꾸고 $waiting[2]$도 $true$로 바뀌므로 $while$ 문에 진입한다.

$lock$은 $false$로 초기화되어 있다. 따라서 $key$ 값은 $false$, $lock$은 $true$가 된다.

그러면 $while$ 문을 빠져나와 $waiting[2]$는 $false$가 된다.

이제 $P_2$는 critical section에 있다.

 

$P_4$도 critical section에 진입할 준비가 되었다고 하자.

그러면 $waiting[4]$는 $true$로, $key$도 $true$로 바뀐다.

따라서 $P_4$는 $while$ 문에 진입해 계속 loop를 돌게 된다.

 

$P_0$도 critical section에 진입할 준비가 되었다고 하자.

그러면 $waiting[0]$는 $true$로, key도 true로 바뀐다.

마찬가지로 $P_0$는 $while$ 문에 진입해 계속 loop를 돌게 된다.

 

이제 $P_2$가 critical section에서 나왔다고 하자.

그러면 $j = (i + 1)%n$을 반복함으로써(인덱스를 하나씩 늘림으로써) 다른 process가 critical section에 진입할 준비가 되어 있는지 확인한다.

반복이 끝나는 조건은 다시 자신의 인덱스로 돌아오거나($j == i$)

critical section에 진입할 준비가 되어 있는 process가 존재하는 것($waiting[j] == true$)이다.

 

현재 $waiting[0]$과 $waiting[4]$가 $true$인데, 인덱스는 3부터 시작해 하나씩 늘려가며 확인하므로

$waiting[0]$보다 $waiting[4]$가 먼저 $false$가 된다.

$key$는 현재 $true$고, $waiting[4]$는 $false$이므로 while 문을 빠져나와 $P_4$가 critical section에 진입하게 된다.

 

만약 $waiting[2]$ 빼고 전부 다 $false$면 $i==j$가 되어 $lock$은 $false$가 된다.

결국 $key = test_and_set(\&lock)$에 의해 $key=false$되어 $P_2$가 다시 critical section에 진입하게 된다.

 

 

7개의 process $P_0,\; P_1,\; P_2,\; P_3,\; P_4,\; P_5,\; P_6$가 있고

$waiting[2] = waiting[4] = true$고 나머지는 $false$라 하자.

그리고 $P_3$이 현재 critical section에 있다고 하자.

15행~18행의 조건식은 $P_3$이 critical section에서 나온 후 $P_5$가 critical section에 진입함을 보장한다.

즉 3보다 인덱스가 크면서 critical section에 진입할 준비가 된 프로세스 중 가장 인덱스가 작은 프로세스가 현재 critical section에 있는 프로세스의 종료 후 바로 들어감을 보장한다. 즉 $N$개의 프로세스가 있다면 적어도 $(N-1)$개의 프로세스가 빠져나온 후에는 무조건 critical section에 진입할 수 있음을 보장한다. 따라서 Bounded waiting을 보장한다.

만약 이 조건이 없다면 모든 프로세스가 $lock=false$를 실행하므로 보장되지 않는다.

 

 

Mutex Locks

운영체제가 제공하는 별도의 solution 중 하나. mutex는 MUTual EXclusion의 약자

프로세스가 critical section에 진입하기 위해 mutex lock을 획득하고($acquire()$), critical section에서 빠져나오면

mutex lock을 release($release()$)한다.

이 때 $acquire()$과 $release()$는 atomic하다.

 

Busy wait

$acquire()$에서 $available$ 값이 $true$가 될 때까지 계속 while 문을 돌면서 확인함: Spin lock

단점: 쓸데없이 CPU를 소비한다

장점: Context switch가 불필요하다.

       특히 critical section에서 소요되는 시간이 짧다면 CPU 낭비가 많지 않으므로 오히려 좋다

 

 

Semaphore(중요)

$S$로 표현되는 정수형 변수

두 개의 atomic한 operation에 의해서만 접근된다.

The operations of Semaphore

Busy wait: Mutex의 $acquire()$와 같이 loop를 돌면서 계속 $S$ 값을 확인한다

 

 

Binary semaphore

$S$ 값은 0 또는 1 -> Mutex lock이랑 같음

Critical section에는 한 개의 프로세스만 진입한다.

 

Counting semaphore

$S$ 값은 0부터 $N$

Critical section에는 $N$개의 프로세스가 동시에 진입한다.

 

 

Critical section problem

Ex) Mutex

 

Process synchronization

프로세스의 실행 순서도 semaphore로 제어할 수 있다.

Semaphore $sync$의 값은 0으로 초기화되어있다.

$P_2$는 $wait$($sync$가 0 이하일 경우 $while$ 문을 계속 돈다)

-> $P_1$이 실행 후 $signal$로 sync 값을 1로 만들면 $wait()$의 루프가 종료되고 $S_2$가 실행됨

따라서 $S_1$이 실행된 후 $S_2$가 실행됨을 보장할 수 있다.

 

 

Semaphore implementation

Mutex와 같이 Busy waiting으로 구현할 수도 있고 Block & Wakeup으로 구현할 수도 있다.

Busy wait: 구현은 쉽지만 CPU를 낭비하게 된다. 다만 Critical section에서의 소요되는 시간이 아주 짧다면 더 좋음

 

 

Block & Wakeup

while 문을 계속 도는 게 아니라 그 프로세스를 waiting queue에 넣어서 CPU를 다른 프로세스에 할당한다.

-> 쓸데없이 CPU를 낭비하는 Busy wait의 약점을 개선한다.

 

Waiting queue의 각 entry는 다음의 두 데이터를 갖는다.

 

$value$: 이 semaphore의 값 (integer)

$list$: 이 semaphore와 관련된 waiting queue

 

그리고 다음의 두 operation을 갖는다.

$block$: waiting queue에 프로세스를 올린다. (semaphore 값이 0 이하일 때)

-> value가 음수면 현재 waiting queue에서 대기 중인 프로세스를 나타낸다.

 

$wakeup$: list에 있는 프로세스를 가져와 ready queue에 올린다. (semaphore 값이 0보다 클 때)

 

$wait$

$S$ 값 $1$ 감소

$S$ 값이 $0$보다 작으면 waiting queue에 현재 프로세스($P$) 추가 후 $block(P)$

-> Busy waiting과 달리 계속 loop를 돌지 않는다.

 

$signal$

$S$ 값 $1$ 증가

$S$ 값이 $0$보다 작거나 같으면 현재 대기 중인 프로세스가 존재함을 의미한다

-> waiting queue에서 프로세스 하나($P$) 제거 후 $wakeup(P)$

 

 

Problems

Deadlock

잘못 사용했을 때 발생하는 문제

여러 개의 프로세스가 어떤 이벤트의 발생을 무한정 기다리는 현상

$S = 1,\; Q = 1$

$P_0$: $wait(S)$ ->  $S = 0$

(Context switch)

$P_1$: $wait(Q)$ -> $Q = 0$

(Context switch)

$P_0$: $wait(Q)$ -> Looping(Waiting)

(Context switch)

$P_1$: $wait(S)$ ->  Looping($\because\;\; S=0$)

 

결국 $P_0$는 $P_1$에서 $signal(Q)$ 하기를 기다리고 있고 $P_1$는 $P_0$에서 $signal(S)$ 하기를 기다리고 있지만

둘 다 계속 기다리기만 함 -> 무한 대기

Deadlock은 항상 발생하는 것이 아니고, 발생해도 똑같은 패턴으로 발생하는 게 아니라서 debugging이 까다로움

만약에 Context switch가 다음과 같이 일어나면 Deadlock은 발생하지 않음

 

$P_0$: $wait(S)$

$P_0$: $wait(Q)$

(Context switch)

$P_1$: $wait(Q)$

$P_1$: $wait(S)$

(Context switch)

$P_0$: $signal(S)$

$P_0$: $signal(Q)$

 

 

 

Starvation

잘못 구현했을 때 발생하는 문제

Queue에 프로세스를 올리고 빼는 과정을 LIFO(Last-In First-Out)로 하면 안 Starvation 문제 발생

-> FIFO(First-In First-Out)로 하면 됨