The Critical-Section Problem
- n 개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
- 각 프로세스의 코드에는 공유 데이터를 접근하는 코드인 critical section이 존재.
Initial Attempts to solve problem
do {
entry section
critical section
exit section
remainder section
} while (...)- 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다. (Synchronization variable)
프로그램적 해결법의 충족 조건
가정 1) 모든 프로세스의 수행속도는 0보다 크다.
가정 2) 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
1. Mutual exclusion (상호 배제)
프로세스 A가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
2. Progress (진행)
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야한다.
3. Bounded Waiting (유한 대기)
프로세스가 임계 영역에 들어가려고 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 영역에 들어가는 횟수에 한계가 있어야함.
Algorithm 1
- synchronization variable
int turn;
initially turn = 0; => Pi can enter its critical section if (turn == i)크리티컬 섹션을 번갈아 들어가도록 된 구조.
do {
while (turn != 0)
critical section
turn = 1;
remainder section
} while (...)반드시 한번씩 교대로 들어가야만 함.
상대가 turn 변수 값을 나의 turn 값으로 바꿔줘야만 내가 들어갈 수 있음.
특정 프로세스가 더 빈번히 critical section에 들어가야 한다면 문제가 됨.
-> 동시에 들어가는 문제는 해결했으나 아무도 안들어가있을 때 진행이 안되는 경우를 해결하지 못함.
Algorithm 2
플래그를 두어 임계영역에 들어가고자 하는 프로세스는 요청을 보내는 방식.
다른 프로세스의 플래그가 켜져있다면, 임계영역에 바로 들어가지 않고 대기한다. (동시접근 대기)
임계영역에서 작업이 끝나면 플래그를 꺼서 다른 프로세스가 들어가게 해준다.
do {
flag[i] = true;
while (flag[i])
critical section
flag[i] = false;
remainder section
} while (1);동시에 들어가는 문제는 해결.
깃발을 들엇다는건 내가 임계영역에 들어가겠다는 의사표현.
깃발만 들고 아직 임계영역에 들어가지 않은 상태에서 CPU를 빼앗기고, 다른 프로세스가 깃발을 들게 되면, 상대 깃발이 들려있는 것을 보고 임계영역으로 들어가지 못하는. 깃발만 들고 아무도 못들어가는 문제가 생김.
Algorithm 3 (Peterson's Algorithm)
- 알고리즘 1, 2를 결합하여 만든 동기화 방식.
플래그를 통해 의사표현을 하고, 누가 플래그를 들었는지 확인하는 과정 존재.
동시에 플래그를 든 경우, 깃발을 든 경우에 한해 턴을 통해 차례를 정함.
do {
flag[i] = true;
turn = j;
while (flag[j] && turn ==j);
critical section
flag [i] = false;
remainder section
} while (...);깃발을 들어 임계영역 진입 의사 표시
턴을 상대 턴으로 만들어둔다.
상대방이 깃발을 들고 있고 상대 턴인지를 확인. (이 외 케이스에서는 임계 진입)
이후 임계영역을 나오면 내 깃발을 내려준다.
깃발이 올라가있고, 상대 턴이면 대기. 그렇지 않으면 임계 진입.
플래그 먼저 바꾸고, 턴값이 바뀌어야함. 순서를 지키지 않으면 문제가 발생하니 주의할 것.
세 가지 조건을 모두 만족하나, Busy waiting 하여 비효율적인 문제.
내가 임계 영역에 못들어갈 상황이라면, 반복문을 돌며 CPU, memory만 낭비가 되며 기다림.(spin lock 이라고도 함)
복잡한 코드를 통해 데이터 레이스를 방지하였다.
하지만 하드웨어적으로 atomic 하게 데이터를 사용하게 한다면 훨씬 쉽게 문제가 해결된다.
Synchronization Hardware
하드웨어적으로 Test & modify 를 atomic하게 수행할 수 있도록 지원하는 경우(아래 코드에선 Test_and_Set(lock)) 앞선 문제를 간단히 해결 가능하다.
값을 먼저 읽고(Read) -> 1이든 0 이든 상관없이 1 로 세팅.
bool lock = false;
do {
while (Test_and_Set(lock));
critical section
lock = false;
remainder section
}하드웨어적 연산 하나가 지원되면 쉽게 해결됨.
Semaphores
앞의 방식들을 추상화. 일종의 추상 자료형.
추상 자료형 : 오브젝트와 오퍼레이션으로 구성되는 정의가 있는 자료형.
ex) 정수 추상 자료형. 정수가 있고, 그 정수에 대해 정의된 연산( + - / * 등) 이 있는 경우.
Semaphore S
- integer variable
- 아래 두 가지 atomic 연산에 의해서만 접근 가능
P(S) : while (s <= 0) do no-op; S--;
-> S가 양수라면, S-- 후 진입.
-> 그렇지 않다면, S가 양수가 될 때까지 Busy-wait.
-> 락 거는 과정. 자원의 획득.
V(S) : S++;
-> 락 푸는 과정. 자원의 반납
S가 5라면, 자원이 5개 있는거고 자원을 얻으려면 P(S) 연산을 해야함.
자원이 다 떨어져서 없다면, 기다려야한다.
자원을 반납하려면 V(S) 연산은 해야한다.
세마포어 추상 자료형으로 임계영역 문제를 해결하자.
busy-wait(spin lock)는 효율적이지 못함.
누군가 세마포어를 통해 자원을 획득하여 0이 되면, 다른 프로세스가 P 연산을 하게 될 때 반복문만 돌면서 비효율 발생.
만약 누군가 이미 임계영역에 들어가서 세마포어가 0이었다면, 굳이 자꾸 체크를 할 필요가 없을것.
그래서 그냥 CPU를 반납하고, Block 상태로 큐에 들어가면서 누군가 세마포어 자원을 반납할때까지 CPU를 굳이 얻지 않는 방식
-> Block & Wakeup(Sleep lock) 방식의 구현 을 하게 됨.
- block: 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음.
- wakeup(P): block 된 프로세스 P를 wakeup시킴. 이 프로세스의 PCB를 ready queue로 옮김.
Which is better?
Busy wait vs Block/wakeup
일반적으로 블록/웨이크업이 좋다. 자원의 효율성 측면에서.
프로세스 상태를 블록하고 변경하는 것이 오버헤드이기도 하다.
임계영역 길이가 길다면, 블록/웨이크업이 적당하나, 임계영역이 짧고 임계영역에 대한 경합이 치열하지 않다면 블록하는 것에 대한 오버헤드가 커서 그냥 busy-wait의 오버헤드가 작을 수 있다.
