1. Dekker's Algorithm
# 프로세스 i 측의 코드
while True:
''' LOCK '''
# 프로세스 i가 임계영역에 진입하려함을 표시
flag[i] = True
# 만약 프로세스 j도 임계영역에 진입하려할 경우
while flag[j]:
# 프로세스 j가 진입할 차례라면 임계영역에 대한 진입 시도를 취소하고
# j의 차례가 끝날때까지 대기한 뒤 다시 진입시도
if turn == j:
flag[i] = False
while turn == j:
pass
flag[i] = True
''' END LOCK '''
''' 임계 영역 '''
''' UNLOCK '''
# 임계 영역에서의 작업이 끝나고 빠져나옴
flag[i] = False
# 프로세스 j 측에 차례를 넘김
turn = j
''' END UNLOCK '''
- 두 개의 프로세스간의 상호배제를 보장하는 최초의 알고리즘
- turn 과 flag 두 개의 공유 데이터를 사용하여 구현
=> turn 만을 사용할 경우 한쪽이 실행되지 않을 경우 차례가 넘어가지 않아 하나의 프로세스가
임계영역에 연속으로 진입할 수 없는 문제가 발생
=> flag 만을 사용할 경우 서로 동시에 임계영역에 진입하려할 경우 교착상태(Deadlock)에 빠지는 문제가 발생
- Dekker's Algorithm은 이 두가지를 동시에 사용하여 상호배제를 보장
=> 프로세스 j측은 i와 j의 위치를 맞바꾸어 작성하면 된다
2. Peterson's Algorithm
# 프로세스 i측의 코드
while True:
''' LOCK '''
# 프로세스 i가 임계영역에 진입하려함을 알림
flag[i] = True
# 차례를 우선 프로세스 j에게 넘겨준다
turn = j
# 만약 j의 차례이고 j가 임계영역에 들어가고자 할 경우 대기
while flag[j] && turn == j:
pass
''' END LOCK '''
''' 임계 영역 '''
''' UNLOCK '''
# 임계 영역에서의 작업이 끝나고 빠져나왔음을 알림
flag[i] = False
''' END UNLOCK '''
- Dekker's Algorithm 과 거의 유사하지만 차례를 상대에게 양보하는 형태로 이루어지며 보다 단순한 구조를 가짐
- 둘이 거의 동시에 실행됐지만 i가 차례를 양보하는 것이 미세하게 빨랐을 경우를 가정
- 프로세스 i와 j는 모두 flag 값을 True로 하여 진입의사를 밝힌다.
- i가 먼저 j에게 차례를 넘기고 직후에 j도 i에게 차례를 넘겨 결국 i의 차례가 된다.
- j가 진입을 원하고있지만 i의 차례이기에 프로세스 i가 임계영역에 들어간다
- j는 i가 진입을 원하고있고 i의 차례이기에 대기상태에 들어간다(Busy Waiting)
- i는 작업을 마치고 임계영역을 빠져나오며 flag 값을 False로 한다.
- j는 여전히 i의 차례이지만 i가 flag 값을 False로 했기에 임계영역에 진입하여 작업을 수행하고 빠져나온다.
3. Dijkstra's Algorithm
# 프로세스의 상태(flag)
# idle : 프로세스가 임계 영역에 진입을 시도하고있지 않은 경우
# want-in : 프로세스가 임계 영역 진입을 시도하고있는 경우
# in-CS : 프로세스가 임계 영역 직전 또는 임계 영역 내에 있는경우
# 프로세스 i측의 코드
while True:
''' LOCK '''
while True:
''' 임계 영역 진입 시도 1단계 '''
# 프로세스 i가 임계 영역에 진입하려함을 알림
flag[i] = want-in
# 자신의 차례가 아닐 경우
while turn != i:
# 현재 실행중이던 프로세스의 작업이 끝났는지 확인, 끝났을 경우 자신의 차례로 돌리고 진입
# 이 과정에서 여러개의 프로세스가 동시에 통과하여 2단계에 진입할 수 있다.
if flag[turn] == idle:
turn = i
# 1단계를 통과한 일부 프로세스들은 2단계에 진입
# 임계 영역 직전에 있음을 알림
flag[i] = in-CS
# 모든(n개의) 프로세스들의 flag값을 확인하여 자신 외에도 in-CS 상태인 프로세스가 존재하는지 확인
j = 0
while j < n and (j == i or flag[j] != in-CS):
j = j + 1;
# 만약 자신 외에 in-CS 상태인 프로세스가 존재하지 않는다면 반복문을 빠져나가 임계 영역에 진입
if j == n:
break
''' END LOCK '''
''' critical section '''
''' UNLOCK '''
# 임계 영역에서의 작업을 마치고 idle 상태로 돌아간다.
flag[i] = idle
''' END UNLOCK '''
- 프로세스의 상태를 idle, want-in, in-CS 3단계로 나누어 n개의 프로세스간의 상호배제를 구현
- turn 의 경우 반드시 임계영역에 들어간 프로세스의 번호가 되진 않지만 그럴 경우
1단계로 되돌아간 프로세스 중 다시 진입을 시도하는 프로세스가 while turn != i 반복문을
바로 통과하여 다시 2단계로 진입하게되기 때문에 문제는 없다.
4. SW Solution의 문제점
- 복잡한 구현
- 느린 속도
=> Dijkstra의 알고리즘만 보더라도 의미없는 반복을 계속하는 경우가 많이 발생할 것을 예상할 수 있음
- lock, unlock 연산 수행중 스케줄러에 의해 자원을 회수당할 수 있음(Preemption)
=> 해당 연산 수행중 interrupt를 억제하는 것으로 해결할 수 있지만 오버헤드 발생
- Busy Waiting, 즉 대기시간동안 계속해서 반복문 내를 순환하는 방식이기에 비효율적