데커알고리즘과 피터슨알고리즘 -알고리즘의 개념과 적용을 분석하고 데커알고리즘 (Dekker Algorithm), 피터슨 알고리즘 (Peterson Algorithm)을 기술

소개글

데커알고리즘과 피터슨알고리즘 -알고리즘의 개념과 적용을 분석하고 데커알고리즘 (Dekker Algorithm), 피터슨 알고리즘 (Peterson Algorithm)을 기술에 대한 보고서 자료입니다.

목차

Ⅰ. 알고리즘

Ⅱ. 알고리즘의 분석기준
1. 알고리즘의 판단기준
2. 알고리즘의 분석이유
3. 알고리즘의 분석단계
4. 알고리즘의 분석기준
5. 알고리즘 분석
6. 알고리즘의 수행시간 의존요인

Ⅲ. 병행프로세스
1. 병행프로세스
2. 프로세스의 종류

Ⅲ. 상호배제 문제의 해결 및 데커알고리즘 (Dekker Algorithm), 피터슨 알고리즘 (Peterson Algorithm)
1. 결정성과 경쟁 조건
2. 상호배제(Mutual Exclusion)
3. 데커 알고리즘 (Dekker Algorithm)
4. 피터슨 알고리즘 (Peterson Algorithm

본문내용

의도가 있다 하더라도 변수 which가 process0이
들어가야 할 차례임(which = 0)을 판정해 주면 됨.
상호 배제, 진행, 한계 대기의 3가지 조건을 모두 만족.
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가 임계 구역에 진입할 자격이 주어지게 된다.
while (1) {
...
flag[i] = true; // 임계영역에 들어가려고 시도
while (flag[j]) { // Pj가 임계영역에 있는지 조사
if (turn == j) { // Pj가 들어갈 기회라면
flag[i] = false; // 일단 진입 취소
while (turn == j) ; // 순서를 기다림
flag[i] = true; // 재진입 시도
}
}
// 임계영역 (critical section)
...
turn = j; // 진입 순서 양보
flag[i] = false; // 임계영역 사용 완료 지정
...
}
4. 피터슨 알고리즘 (Peterson Algorithm)
프로세스들은 bool flag[2], int turn의 공유 변수를 가짐
프로세스 Pi의 구조
. 임계영역에 진입하려면 먼저 flag[i]=true로 하여 임계영역에 들어가고 싶다는 의사 표시.
. turn=j로 설정한 후, 프로세스 j가 임계영역에 들어갈 의사가 없다면(flag[j]=false) 임계영역에 들어갈 수 있음.
. 두 개의 프로세스가 동시에 임계영역에 진입하려고 한다면 turn변수가 늦게 수행된 프로세스가 기회를 양보.
. 임계영역에서 나오는 프로세스는 flag[i]를 false로 함으로써, 다른 프로세스가 임계영역에 들어가도록 허용.
while (1) {
...
flag[i] = true; // 임계영역에 들어가려고 시도
turn = j; // 상대방에 진입 기회 양보
while (flag[j] && turn == j); // 상대방이 진입하려고 한다면 대기
// 임계영역(critical section)
...
flag[i] = false; // 임계영역 사용 완료 지정
...
}

키워드

알고리즘,   데커알고리즘,   피터슨알고리즘,   데커 알고리즘,   피터슨 알고리즘,   프로세스,   병행프로세스,   상호배제