Bakery Algorithm
독일 빵집에서 아침부터 번호표를 받아 빵을 사는 것에서 유래되었다.
n개의 프로세스를 위한 동기화 알고리즘이다.
프로세스 Pi가 있다고 해보자.
1. Boolean choice[n];
2. int number[n];
3. choice[i] = TRUE;
4. number[i] = 1 + max(number[0], ..., number[n-1]);
5. choice[i] = FALSE;
6. for(j = 0; j < n, i !=j; j++)
7. {
8. while(choice[j]);
9. while(number[j] != 0 && (number[j], j) < (number[i], i));
10. }
11. [critical section]
12. number[i] = 0
13. [non-critical section]- 번호표를 받기 전에는 TRUE로 설정해준다.
- 현재 대기중인 가장 큰 번호보다 1이 큰 번호를 받는다.
- 번호를 받으면 FALSE로 설정해준다.
- 0부터 n까지 번호를 확인하면서 for문을 돈다.
- 어떤 프로세스가 번호를 받고 있으면 아무것도 하지 않는다.
- 어떤 프로세스의 번호가 0이 아니면 현재 자신의 번호와 비교해서 작은지 확인하고 기다린다.
- 번호가 가장 작으면 임계영역에 진입한다.
- 번호를 0으로 바꾼다.
(number[j], j) < (number[i], i) ==> (number[j] <= number[i]) && (j < i)
하나의 Boolean 변수를 사용하여 임계영역을 관리할 경우에는 시간차에 의해 끼어들어서 임계영역에 동시에 진입할 수 있다. 따라서 원했던 결과가 나오지 않을 수 있다.
Semaphores
낮은 강제성 때문에 개발되었다.
그 전의 문제점들
- 상호배제 조건을 만족하고 deadlock이 없도록 임계영역에 진입하고 나오는 entry/exit protocol을 설계하는 것이 무척 힘들다
- protocol을 설계하고 이해하고 검증하는 것이 매우 어렵다.
- 상호배제 조건을 만족하는 유연하고 표준적인 고급방식이 필요하다.
- 최소한 상호배체, deadlock-free, fairness를 만족해야 한다.
따라서 세마포는 두개의 강제적인 원자성 동작으로 구성된다. 동작이 끝날 때까지 다른 동작이 끼어들지 못한다. 그 두개는 P(wait)와 V(signal)이며 각각 entry protocol과 exit protocol이다.
세마포는 정수값을 가진 0 이상의 변수인데 두 동작은 세마포 S에 정의된다.
세마포는 초기 값으로 음이 아닌 값을 가진다.
- P(S) 또는 Wait(S)
while(S <= 0);
S--;아무것도 하지 않고 S가 0보다 작거나 같은지 계속 확인한다. atomic하기 때문에 이 동작 중에는 끼어들면 안되고 임계영역에도 들어가지 못한다.
S가 0보다 커지면 1만큼 감소시키고 임계영역에 진입한다.
- V(S) 또는 Signal(S)
S++임계영역 사용이 끝나면 1만큼 증가시킨다.
P(S)와 V(S)는 atomic하다. 즉 어떤 동작도 ()안을 테스트하고 S--, S++동작 사이에 끼어들 수 없다.
유니티