[디지털공학]데커알고리즘, 피터슨알고리즘 dekker알고리즘, peterson알고리즘

소개

데커알고리즘과 피터알고리즘에 대해 설명 및 구현

목차

Dekker알고리즘
Peterson알고리즘

본문내용

데커 알고리즘은 2개의 프로세스를 위한 상호 배제의 문제를 최초로 정확하게 소프트웨어적인 해결 방법으로 알려져 있다.
Repeat
:
Flag[i] : = True;
While Flag[j] Do Skip;
If (Turn = j)
Then Flag[i] : = False;
While (Turn = j) Do Skip;
Flag[i] : = True;
End If
임계 구역(Critical Section)
:
Turn : = j;
Flag[i] : = False;
잔류 구역(Remainder Section)
:
Until False;

Dekker 알고리즘은 Flag변수와 Turn변수의 사용에 의의가 있다.
2개의 프로세스 P₀과 P₁은 공유 변수 “Var Flag : Array [0..1] of Boolean;"과 Integer Turn을 사용한다. 이 공유 변수의 초기 값은 Flag[0] = Flag[1] = False이고, Turn은 0 또는 1이다.
이 알고리즘에서 Pi가 임계 구역에 들어가려면 Flag[i]에 들어가겠다는 의사 표시를 True로 한다. 그리고 Pj가 똑같이 임계 구역에 들어가려 하는지를 확인한다. 만약 Flag[j]가 False이어서 Pj가 임계 구역에 있지 않고, 들어가려 하지도 않음이 확인되면, Pi는 임계 구역으로 들어간다. 그러나 그렇지 않으면 Turn 변수가 j일 때, Pj에게 우선권을 내준다. Turn 변수가 i라면 Flag[j]가 False가 되기를 기다린다.
임계 구역에서 나오는 프로세스는 Flag[i]를 False로 함으로써 빠져 나옴을 알리고, Turn은 다음 번에 임계 구역에 들어갈 때 충돌이 생기면 기회를 양보하기 위해 Turn = j 이면 Pj가 임계 구역에 진입할 자격이 주어지는 것이고, Turn = i라면 Pi가 임계 구역에 진입할 자격이 주어지게 된다.

참고자료

· 운영체제