상호 배제 알고리즘
SW solutions
- Dekker’s algorithm
- 두 개의 프로세스 간 상호 배제를 보장하는 최초의 알고리즘
Flag: 임계 구역에 들어가있는지 여부를 알려주는 변수Turn: 어느 프로세스가 임계 영역에 들어가겠다고 요구할 권한이 있는지 알려주는 변수
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while(1) { // 프로세스i의 진입 영역
flag[i] = ture; // 프로세스i가 임계구역에 진입하기 위해 진입을 알림
while(flag[j]) { // 프로세스j가 임계구역에 진입하려고 하는지 확인
if (turn == j) { // 프로세스j가 임계구역에 있다면
flag[i] = flase; // 프로세스i가 진입을 취소하고
while (turn == j); // 프로세스i의 차례가 올 때까지 대기 함.
flag[i] =ture; // 차례가 넘어왔다면 진입을 알림.
}
} // Critical Section
turn = j; // 임계구역의 사용이 끝났다면 차례를 프로세스j에게 넘김.
flag[i] = false; // 진입을 취소하여 임계구역 사용완료를 알림.
}
- Peterson’s algorithm
- 프로세스가 두 개일 때 상호 배제를 보장하는 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
while(1) { // 프로세스i의 진입 영역
flag[i] = ture; // 프로세스i가 임계구역에 진입하기 위해 진입을 알림.
turn = j; // 프로세스j에게 진입을 양보함.
// (두 프로세스중 먼저 양보한쪽이 먼저 임계구역에 들어가게 됨.)
while (flag[j] && turn = j); // 프로세스i의 차례가 될 때까지 대기를 함.
// critical section
flag[i] = false // 임계구역 사용완료를 알림.
}
- Dijkstra’s algorithm
- 프로세스 n개의 상호배제 문제를 해결한 최초의 알고리즘
- flag[i] 변수 상태
idle: 프로세스가 임계 구역에 진입 시도를 하고 있지 않은 상태want-in: 프로세스의 임계구역 진입 시도 1단계in-CS: 프로세스의 임계구역 진입 시도 2단계 및 임계구역 내에 있을 때
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
while(1) { // 프로세스i의 진입 영역
do {
// 임계구역 진입시도 1단계
flag[i] = want-in // 1단계 진입시도를 한다고 알림
while (turn != i ) { // 자신의 차례가 될 때까지 대기를 함.
if (flag[turn] == idle) { // 임계구역에 프로세스가 없다면,
turn = i; // 자신의 차례로 변경함.
}
}
// 임계구역 진입시도 2단계
flag[i] = in-CS // 임계구역에 진입하겠다고 알림.
j = 0;
while ((j < n) && (j == i|| flag[j] != in-CS ){ // 자신을 제외한 in-CS 상태의 프로세스가 있는지 검사 함.
j = j + 1;
}
} while(j < n) // 자신 외에 2단계 진입을 시도하는 프로세스가 있다면 다시 1단계로 돌아감.
// critical section // in-CS 상태의 프로세스가 자신밖에 없다면 임계영역에 진입함.
flag[i] = idle; // 임계구역 사용완료를 알림.
}
- Knuth’s algorithm
- 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여 프로세스에 프로세서 할당
- 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 오래 기다려야 한다.
- Eisenberg and McGuire’s algorithm
- Lamport’salgorithm
- 프로세스 n개의 상호 배제 문제를 해결한 알고리즘
- 프로세스에게 고유한 번호를 부여하고, 번호를 기준으로 우선순위를 정하여 우선순위가 높은 프로세스(번호가 낮은 프로세스)가 먼저 임계 구역에 진입하도록 구현되었습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
while(1) { // 프로세스i의 진입 영역
choosing[i] = ture; // 번호표 받을 준비
number[i] = max(number[0], number[1], ..., number[n-1]) + 1; // 번호표 부여
// (번호표 부여중 선점이 되어 같은 번호를 부여 받는 프로세스가 발생할 수 있음)
chossing[i] = false; // 번호표를 받음
for (j = 0; j < n; j++) { // 모드 프로세스와 번호표를 비교함.
while (choosing[j]); // 프로세스j가 번호표를 받을 때까지 대기
while ((number[j] != 0) &&
((number[j] < number[i]) // 프로세스 j가 프로세스 i보다 번호표가 작거나(우선순위가 높고)
|| (number[j] == number[i] && j < i)); // 또는 번호표가 같을 경우 j 가 i 보다 작다면
// 프로세스 j가 임계구역에서 나올 때까지 대기.
}
// Critical Section
number[i] = 0; // 임계구역 사용완료를 알림.
}
소프트웨어 솔루션의 문제점
- 속도가 느리고 구현이 복잡하다.
- 수행 도중 preemption이 발생할 수 있으며, 운영체제가 이런 인터럽트를 막아준다고 하더라도 오버헤드가 발생한다.
- busy waiting이 발생하여 비효율적이다.
HW solution
- TestAndSet(TAS) instruction
- Test와 Set을 한번에 수행하는 기계어
TAS를 이용한 상호배제 구현
1 2 3 4 5 6 7 8 9 10 11 12
boolean TestAndSet(boolean &target) { boolean rv = target; target = true; return rv; } // lock의 초기값은 false, 처음 실행한 프로세스는 첫 반복문 (while)을 통과 do { while(TestAndSet(lock)); // lock을 걸어줌, lock이 풀릴떄까지 다른 프로세스는 CS에 접근 불가 // critical section lock = false; // remainder section }
- Test와 Set을 한번에 수행하는 기계어
N개의 프로세스에서 상호배제 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
boolean lock = false;
do {
waiting[i] = true; // 프로세스 i를 대기열에 넣음.
key = true;
while (waiting[i] && key) // 대기가 풀리거나 lock이 풀릴 때까지 대기함
key = TestAndSet(&lock); // lock 값을 key에 반환
waiting[i] = false; // CS에 접근할 수 있으므로 대기를 풀어줌.
// Critical Section
j = (i + 1) % n;
while((j != i) && !waiting[j]) // 대기 중인 프로세스를 찾음
j = (j + 1) % n;
if(j == i) // 대기 중인 프로세스가 없으면
lock = false; // 다른 프로세스의 진입을 허용할 수 있게 lock을 풀어줌.
else // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입하게 함.
waiting[j] = false; // 임계 영역에 진입할 수 있도록 대기를 품.
} while (true);
하드웨어 솔루션의 문제점
- 하드웨어가 한번에 수행되는 것을 보장해 주기 때문에 소프트웨어 솔루션에 비해 구현이 간단하지만 Busy waiting 문제가 있어 비효율적이다.
OS supported SW solution
- Spinlock
- 임계 구역에 진입이 불가능할 때 진입이 가능할 때까지 루프르르 돌면서 재시도하는 방식으로 구현된 락을 가리킨다.
- 운영체제의 스케줄링 지원을 받지 않기 때문에, 해당 스레드에 대한 문맥 교환이 일어나지 않는다. 멀티 프로세서 시스템에서만 사용할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 자원이 없다면 while 루프를 돌면서 기다리는 방식(busy-waiting)
wait(S) {
while (S <= 0); // 자원이 없다면 while 루프를 돌며 대기를 함.
S--; // 자원을 획득함.
}
signal(S) {
S++; // 자원을 해제함.
}
// 자원이 없다면 blocked 상태에서 기다리는 방식
typedef struct
{
int value; /* semaphore */
struct process *list; /* process wait queue */
} semaphore;
wait(semaphore *S) {
S->value--;
if (S->value < 0 ) { // 자원이 없다면
add this process to S->list; // 프로세스를 큐에 넣고
block(); // block 시킴
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) { // 자원이 0이하라면 block중인 프로세스가 있다는 의미임.
remove a process P from S->list; // 대기하고 있는 프로세스를 가져옴.
wakeup(P); // 가져온 프로세스를 깨움.
}
}
- Semaphore
- Busy waiting 문제를 해결함
- 이진 세마포어
- 0 또는 1 값만 가질 수 있는 세마포어
- 임계 구역 문제를 해결하는데 사용하며 자원이 하나이기 때문에 뮤텍스로도 사용할 수 있다.
- 개수 세마포어
- 도메인이 0이상인 임의의 정수값인 세마포어
- 여러개의 자원을 가질 수 있으며 제한된 자원을 가지고 액세스 작업을 할 때 사용한다.
- Eventcount/sequencer
- 은행의 번호표와 비슷한 개념
- Sequencer
- 정수형 변수
- 생성 시 0으로 초기화, 감소하지 않음
- 발생 사건들의 순서 유지
- ticket() 연산으로만 접근 가능
- ticket(S)
- 현재까지 ticket() 연산이 호출 된 횟수를 반환
- eventcount
- 정수형 변수
- 생성시 0으로 초기화, 감소하지 않음
- 특성 사건의 발생 횟수를 기록
- read(E), advance(E), await(E, v) 연산으로만 접근 가능
- read(E)
- 현재 Eventcount 값 반환
- advance(E)
- E <- E + 1
- E를 기다리고 있는 프로세스를 깨움(wake-up)
- await(E, v)
- V는 정수형 변수
- if(E < v)이면 E에 연결된 Qe에 프로세스 전달(push) 및 CPU scheduler 호출
- No busy waiting
- No starvation
- Semaphore보다 더 low-level control이 가능 (순서를 컨트롤 할 수 있음)
Language-Level solution
- Monitor
- 공유 데이터와 Critical section 의 집합
- 한 번에 하나의 프로세스만 모니터 개체 내에 프로시저를 사용할 수 있습니다. 모니터에 접근하지 못한 프로세스는 entry queue에서 대기하게 된다. (상호배제)
- 모니터 개체 내 공유 자원은 직접 접근할 수 없으며 프로시저를 통해서만 가능합니다. (정보은닉)