[운영체제] 5주차: 동기화

Review

CPU Scheduling

Preemptive와 Non-preemtive로 나뉘며 다음과 같은 알고리즘이 있다

 

Ready queue가 한 개 일 때

FCFS: Convoy effect

SJF: Optimal

Priority scheduling: Starvation 가능 -> Aging

RR: Time quantum이 중요함

 

Ready queue가 여러 개 일 때

Multilevel Queue scheduling

Multilevel Feedback Queue scheduling

 

Real-Time CPU Scheduling algorithms

Deadline 안에 작업을 마무리해야 함

 

Rate monotonic scheduling

Earliest deadline first scheduling

 

 

 

Process synchronization

한 데이터에 여러 thread가 동시에 접근하면 데이터가 깨질 수 있다.

 

컴파일을 하면 기계어 코드가 만들어진다.

 

Machine instruction

0과 1로만 이루어진, CPU가 이해할 수 있는 언어

 

Assembly language

기계어와 one-to-one으로 match됨

 

High-level languages

고수준 언어 한 문장이 여러 개의 기계어로 match됨

= 프로세스 동기화 문제가 발생하는 최초의 원인

 

C)

$x = y + 133;$

 

Assembly)

$MOVE\;\;\;\;R1,\; (y)$

$ADD\;\;\;\;\;\;R1,\; 133$

$MOVE\;\;\;\;(x),\; R1$

 

 

프로세스 동기화로 인해 생길 수 있는 문제

Process는 동시에 여러 개가 실행될 수 있다.

그리고 Shared data를 동시에 access할 수 있는데, 이 때 olderly execution을 만족하지 않으면 데이터가 깨질 수 있다.

즉 A가 access하는 중에 B가 access하면 안 되고, A가 access를 끝낸 후에 B가 access 해야 함

 

 

Producer-Consumer

BUFFER_SIZE만큼 다 사용할 수 있음

counter: 버퍼에 얼마나 많은 데이터가 들어있는가?

두 프로세스는 counter를 공유함

 

<Producer>

while(true) {
    while(counter == BUFFER_SIZE);
    
buffer[i] = nextProduced;
in = (in + 1)%BUFFER_SIZE;
    counter++;
}

 

 <Consumer>

while(true) {
    while(counter == BUFFER_SIZE);
    
    nextConsumed = buffer[out];
    out = (out + 1)%BUFFER_SIZE;
    counter--;
}

 

$counter++$는 다음과 같은 기계어와 대응되고,

$register1 = counter$

$register1 = register1 + 1$

$counter = register1$

 

$counter--$는 다음과 같은 기계어와 대응된다.

$register2 = counter$

$register2 = register2 + 1$

$counter = register2$

 

 

위와 같은 코드를 사용하면 문제가 발생한다.

$counter$의 초기값이 5라고 하면,

$counter$ 값은 5가 되어야 하는데, Producer에서는 6, Consumer에서는 4임

 

Race condition

Shared data에 여러 개의 프로세스가 동시에 access할 때 실행 순서에 따라 shared data의 값이 달라지는 상황

공유 데이터를 access하는 부분에서 발생하며 이 부분을 Critical section이라 함

 

Critical section(중요)

위 코드에서는 $counter++;$ 부분이 해당됨

 

여러 프로세스가 동시에 자신의 Critical section에 접근하지 않도록 해야 함

 

궁극적인 해결방안은 Critical section에서 여러 개의 프로세스가 동시에 실행되고 있지 않도록 하는 것이다.

즉 Critical section에 들어가기 전에 뭘 하고 빠져나온 후에 뭘 할 건지 지정해서

여러 프로세스가 동시에 Critical section에 접근하지 않도록 한다.

 

이를 위해서는 다음의 세 조건을 모두 만족해야 한다. (이 부분 중요)

 

Mutual exclusion

한 순간에 한 프로세스만 임계 구역에 들어간다.

 

Progress

$P_1$, $P_2$, $P_3$의 세 프로세스가 있다고 하자.

$P_1$, $P_2$는 critical section에 진입할 준비가 되어 있고 $P_3$는 Critical section과 상관없는 프로세스라면

어느 프로세스가 critical section에 진입할 지는 $P_1$, $P_2$ (진입할 준비가 된 프로세스) 중에서만 결정한다.

이 때 이 결정을 무한히 기다리지는 않는다.

 

Bounded waiting

이미 한 프로세스가 critical section에 진입할 준비가 되었다면, 일정 시간 후 에는 반드시 진입해야 한다.

즉 무한히 기다리지 않는다.

 

Assumption: 프로세스간의 상대적 속도를 가정해선 안 된다.

= critical section에 진입한 프로세스가 언제 context switch할 지 가정할 수 없으므로, context switch가 언제든 발생할 수 있다는 가정 하에 solution을 고려해야 한다.

 

 

Peterson's solution

이론적인 solution

소프트웨어를 이용한 solution

 

Assumption

ⓐ 두 개의 프로세스에 대해서만 동작

ⓑ LOAD와 STORE는 instruction은 atomic하게 동작한다고 가정한다.

ⓑ = 즉 LOAD나 STORE 명령어를 실행할 때에는 interrupt가 발생하지 않는다($i.e.$ context switch가 일어나지 않는다).

 

두 프로세스는 다음 두 변수를 공유한다.

 

$int turn$

어느 프로세스가 critical section에 진입할지 결정

 

$boolean flag[2]$

$P_0$ 프로세스가 진입할 준비가 되면 $flag[0]$을 $true$로 만들고, $P_1$ 프로세스가 진입할 준비가 되면 $flag[1]$을 $true$로 만든다.

 

$P_i$의 코드

$P_j$의 코드

$P_j$의 코드를 보자.

$flag[j]$를 $true$로 하고 $turn$은 $i$로 한다.

그 다음 $while$ 문에서 $P_i$가 critical section에 진입할 준비가 될 때까지($flag[i] == TRUE$) 기다린다.

 

ⓐ Mutual exclusion: 만족

결과적으로 $turn$은 $i$ 또는 $j$중 한 값만 가질 수 있으므로 두 프로세스 모두 critical section에 진입할 수는 없다.

($\because$ critical section에 진입했다 = $while$ 문을 통과했다)

 

ⓑ Progress: 만족

$P_i$가 critical section에 진입할 준비가 되어 있고($flag[i] == true$), $P_j$가 critical section에서 실행 중이라 하자.

$P_j$는 critical section에서의 실행이 끝난 후 자신의 $flag$ 값을 $false$로 바꾼다.

그러면 $P_i$ 코드에서 $while$ 문에 진입하지 않으므로 $P_i$가 실행된다.

 

$flag[i]$, $flag[j]$ 모두 $true$일 때 $turn$에 의해 둘 중 한 프로세스가 critical section에 진입하게 된다.

 

ⓒ Bounded waiting

$P_i$가 critical section에 진입할 준비가 되어 있고($flag[i] == true$), $P_j$가 critical section에서 실행 중이라 하자.

$P_j$는 critical section에서의 실행이 끝난 후 자신의 $flag$ 값을 $false$로 바꾼다.

이 때 여전히 CPU가 $P_j$에 할당이 되어있어서 다시 $P_j$의 코드가 실행된다고 하자.

그러면 $flag[j]$는 $true$가 되고 $turn$은 $i$가 된다.

따라서 $while$ 문에 진입해 기다리게 된다. 반면 $P_i$의 $while$ 문에는 진입하지 않으므로

$P_i$가 critical section에 진입하게 된다.

 

앞서 LOAD와 STORE라는 instruction은 atomic하게 동작한다고 가정했다

STORE는 코드 상에서 $flag$ 와 $turn$의 값을 설정하는 부분에 해당하고, LOAD는 $while$ 문에서 조건을 확인하는 부분에 해당한다.

이 때 $while$ 문에서 조건을 확인하는 도중에 $flag$나 $turn$의 값이 바뀌면 정상적으로 작동하지 않을 수 있으므로

LOAD와 STORE라는 instruction은 atomic하게 동작한다고 가정한 것이다.