Peterson 알고리즘

운영체제 수업시간에 공부했었던 피터슨 알고리즘에 관한 내용이다.

내용

병행 프로세스에서 순서를 지켜서 프로세스가 연산을 할 때 경고 변수와 잠금 변수를 사용하여, 간섭이 일어나지 않도록 하기 위한 알고리즘을 소스코드로 구현합니다.

미리 한번 해보았던 예제 코드의 for문으로 변수의 값을 1씩 5번 증가 시키는 것을 사용하여, 프로세스가 연산하는 값들을 출력하게끔 구현 하여 보았다.

 

Jbaci를 이용하여 테스트한 소스코드

const int FALSE = 0; // FALSE 값을 0으로 정의

const int TRUE = 1; // TRUE 값을 1로 정의

const int N = 2; //

const int m =5; // 각 프로세스가 하는 연산 횟수를 지정하는 변수

int turn; // 자신의 턴을 정하는 변수

int interested[N]; // 상대편의 연산 수행의 끝을 알 수 있는 배열

void leave_region(int process) //leave_region함수는 한 프로세스가 임계구역에 들어가서 수행을 다 한 후

{ //자신이 임계구역에서 나갔음을 알려주기 위한 함수.

cout<<process<<" process is calculate complete"<<endl; // 연산이 끝났다는 출력문 작성.

interested[process] = FALSE; //자신의 interested배열의 값을 FALSE로 바꿔줌으로써 상대편 프로세스의

} //busy Waiting 상태를 풀어 다음 연산을 실행 할 수 있도록 함

void enter_region(int process) //한 프로세스가 실행되고 나면 조건들을 비교하여, 연산 수행 중에 다른 프로세스

{ //가 연산하려고 접근을 할 때, 연산이 완료 될 때까지 while문에서 잡아두는 함수.

int n=0; // 연산을 위한 변수

int i; // 연산을 위한 변수

int other; // 상대편 프로세스 아이디를 담는 변수

other = 1-process; //두 프로세스가 0과1로 되어있으므로, 이 연산으로 상대편프로세스번호를 // 담을 수 있다.

interested[process] = TRUE; //interested의 자신의 번호를 TRUE로 만들어서, 다른 프로세스가 접근을 //할 때 while문의 (interested[other] == TRUE) 부분을 참을 만들어 //waiting 상태로 빠질 수 있게 만든다.

turn = process; //이 trun 변수 로 인하여 둘 다 busy waiting 상태로 빠지는 것을 방지한 한

//다. 두 프로세스가 동시에 접근을 하였을 때, interested값들도 다 TRUE가 //될 것이고, turn 변수도 자신의 이름을 쓰겠지만, turn 은 공용변수라서 조 //금이 라도 늦게 기록한 프로세스 값이 나오게 되고, 그렇다면 그 이외의 프 //로세스 가 진입을 할 수 있게 되고, 늦게 쓴 프로세스는 while 문에 의해 //busy waiting 상태에 빠지게 된다.

 

while( (turn == process) && (interested[other] == TRUE) ) //이 while 문에서 조건이 FALSE 가

{ //될 때 아래 연산을 수행 할 수 있다.

cout<<"["<<process<<" process is Wating...]"<<endl; // 대기 중인 프로세스를 알리는

} // 출력문.

cout<<"enter process is "<<process<<" process"<<endl; //while 문을 통과하여 연산을 시작한

//프로세스를 알리는 출력문.

cout<<process<<" process's calculate"<<endl;

for(i=1; i<=m; i=i+1) // 간단한 더하기 연산을 하는 for문

{

n = n+1;

cout<<process<<" process"<<" n = "<<n<<" i = ";

cout<<i<<" "<<process<<" process"<<endl;

}

cout<<process<<" process's calculate result is "<<n<<endl; //연산의 결과를 알려주는 출력문.

}

void process(int process) // 일을 하는 스레드

{

enter_region(process); //프로세스가 enter_region을 실행후 leave_region을 실행하여 다음 프로세스가

leave_region(process); //진입 할 수 있도록 만들어줌

}

void main()

{

int j;

for(j=0; j<N; j=j+1) // 처음 interested값을 0으로 초기화 함.

{

interested[j] = 0;

}

cobegin

{

process(0); // 두 개의 프로세스를 병행적으로 수행하기 위하여 cobegin을 사용하여

process(1); // 프로세스 두 개를 생성.

}

}

소스 해석

프로세스를 병행 실행을 할 수 있도록 cobegin 함수를 사용하여 일꾼에 해당하는 프로세스를 2개 생성합니다.

그리고 각각의 프로세스는 일을 수행하기 전에 enter_region에 들어가서 각 조건을 확인하고 while문안의 조건 값이 FALSE 가 될 때 연산을 실행합니다. 한 프로세스가 진입을 한 후에는 다른 프로세스는 진입을 할 수 없게 되며, 앞의 프로세스가 연산을 완전히 완료한 후 leave_region 함수를 통하여 끝을 알려주면, 연산을 할 수 있도록 하여, 공용 변수 사용함에 있어서 병행으로 수행되는 두 프로세스가 연산함에 있어 서로의 간섭으로 인해 결과 값이 틀어지는 것을 방지 하게 됩니다. 각각 수행되는 상세 부분은 주석으로 설명을 달아놓았습니다.

실행화면