kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.
1. The Critical-Section Problem
n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우, 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재한다.
Problem: 하나의 프로세스가 ciritical section에 있을 때, 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
충족 조건
1. Mutual Exclusion
프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical sectoin에 들어가면 안 된다.
2. Progress
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
3. Bounded Waiting
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. -> mutual exclusion에 의한 무한 대기, starvation이 생기면 안된다.
가정
- 모든 프로세스의 수행 속도는 0보다 크다.
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
초기 시나리오
프로세스들의 일반적인 구조는 다음과 같다.
do {
entry section
critical section
exit section
remainder section
} while(1);
프로세스들은 수행의 동기화(synchronization)을 위해 몇몇 변수를 공유할 수 있다. -> synchronization variable
Algorithm 1
Synchronization variable
- int turn;
initially turn = 0; -> Pi는 if (turn == i) 일 때 critical section에 진입 가능하다.
- Process P0
do{
while(turn!=0); //자신의 turn인지 확인
critical section
turn=1; //critical section에서 빠져나온 후, 자신의 turn으로 변경
remainder section
} while(1);
만약 P1이 critical section에 있어서 turn이 1이라면 P0는 while(turn!=0); 문을 계속 돌기 때문에 critical section에 진입하지 못한다. 이후 P1이 critical section을 빠져나와 turn을 0으로 바꾸면, P0는 critical section에 진입해서 코드를 수행할 수 있다.
Mutual exclusion을 만족하지만, Progress는 만족하지 못함
과잉양보: 위의 알고리즘은 각 프로세스가 critical section 수행 후 빠져나와 turn을 바꿔줘야만 다음 프로세스가 critical section에 진입 가능하다. 즉, 반드시 한번식 교대로 들어가야만 한다.(swap-turn)
그렇다면 특정 프로세스가 더 빈번이 critical section을 들어가야 한다면? 만약 P0는 critical section을 자주 들어가야하는 프로세스이고, P1은 드물게 들어가는 프로세스라고 가정해보자. P1이 critical section을 진입한 이후 turn값을 바꿔줘야 P0가 critical section 진입이 가능하기 때문에 P1에 의해 P0까지 critical section에 진입하고 싶어도 못하는 상황이 발생한다. 따라서 Progress를 만족하지 못한다.
Algorithm 2
Synchronization variable
- boolean flag[2];
initially flag[모두] = false; -> 아무도 critical section에 없음. if (flag[i] == true), Pi가 critical section에 진입할 준비가 됨.
- Process Pi
do{
flag[i] = true; //CS에 진입할 의사가 있음
while(flag[j]); //다른 프로세스가 CS에 진입하고 싶어하면 기다림
critical section
flag[i] = false; //critical section에서 빠져나온 후, flag를 false로 변경. 의사 없음.
remainder section
} while(1);
다른 프로세스가 critical section에 진입 중이라면 Pi는 while(flag[j]);를 돌면서 기다린다. 다른 프로세스가 critical section을 빠져나오면서 flag를 false로 바꾸면, Pi가 critical section에 진입한다.
Mutual exclusion을 만족하지만, Progress는 만족하지 못함
둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능.
만약, P0가 flag[0] = true; 수행 후 CPU를 빼앗겼다고 가정해보자. P1 역시 flag[1] = true; 수행 후 2행으로 넘어가게 될 것이다. 그럼 while(flag[0]);에 의해 대기를 하게 될 것이고 다시 P0가 CPU를 잡아도 역시 while(flag[1]);에 의해 무한대기를 하는 상황이 발생한다. 즉, 두 프로세스 모두 critical section에 진입하지 못하므로 Progress를 만족하지 못한다.
Algorithm 2 (Peterson's Algorithm)
- combined synchronization variables of algorithms 1 and 2.
- Process Pi
do{
flag[i] = true; //CS에 진입할 의사가 있음
turn = j; //다른 프로세스의 turn으로 세팅
while(flag[j] && turn==j); //다른 프로세스가 CS에 진입할 의사가 있고 그의 turn일 때만 기다림
critical section
flag[i] = false; //critical section에서 빠져나온 후, flag를 false로 변경.
remainder section
} while(1);
다른 프로세스가 critical section에 진입할 의사가 있고, 역시 그의 turn인 경우에만 waiting을 한다.
Mutual exclusion, Progress, Bounded wating을 모두 만족함
그러나 Busy Waiting 발생(=spin lock). 계속 while문을 돌면서 CPU와 Memory를 사용하며 wait하기 때문에 매우 비효율적이다.
'CS > 운영체제' 카테고리의 다른 글
[운영체제] 6. Process Synchronization (4) (0) | 2022.12.24 |
---|---|
[운영체제] 6. Process Synchronization (=Concurrency Control) (3) (0) | 2022.12.22 |
[운영체제] 6. Process Synchronization (1) (0) | 2022.12.13 |
[운영체제] 5. CPU Scheduling (2) (0) | 2022.12.02 |
[운영체제] 5. CPU Scheduling (1) (0) | 2022.12.02 |