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>
1
2
3
4
5
6
7
|
while(true) {
while(counter == BUFFER_SIZE);
buffer[i] = nextProduced;
in = (in + 1)%BUFFER_SIZE;
counter++;
}
|
cs |
<Consumer>
1
2
3
4
5
6
7
|
while(true) {
while(counter == BUFFER_SIZE);
nextConsumed = buffer[out];
out = (out + 1)%BUFFER_SIZE;
counter--;
}
|
cs |
$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_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하게 동작한다고 가정한 것이다.
'강의노트 > 운영체제' 카테고리의 다른 글
[운영체제] 6주차: Process synchronzation (0) | 2021.04.12 |
---|---|
[운영체제] 5주차: 동기화를 위한 H/W적 수단 (0) | 2021.04.06 |
[운영체제] 4주차: CPU scheduling (0) | 2021.03.29 |
[운영체제] Term project: Nachos (0) | 2021.03.28 |
[운영체제] 3주차: Thread (0) | 2021.03.23 |