Think Positive!

운영체제 수업시간에 공부했었던 빵집알고리즘(Bakery Algoritm) 에 관한 설명이다.

내용

앞서 했던 피터슨 알고리즘 은 두 프로세스간의 상호 배제 가 가능하게 하였고 이번 bakery 알고리즘 에서는 N개 이상의 프로세스의 상호 베제 가 되도록 구현하는 방법이다. 간단하게 빵집 알고리즘을 설명을 하면 프로세스에 먼저 온 순서대로 번호표를 부여하고, 그 번호표가 우선인 프로세스부터 작업을 시켜주는 것이다. 만약 두 프로세스가 동시에 접근을 하여 번호표가 같아진다면, 프로세스 번호가 낮은 순서로 우선순위를 정하여, 상호간에 연산에 있어서 간섭이 일어나지 않도록 하는 방법이다.

다음은 알고리즘이다.

Jbaci를 이용해서 구현해본 소스코드이다.

const int TRUE = 1; // TRUE변수를 1로 상수화

const int FALSE = 0; // FALSE변수를 0으로 상수화

const int PNUM = 10; // 프로세스의 생성 개수를 상수화 하여 프로세스의 개수가 늘고 줆에 있어 이수치만 //수정하면 된다.

const int N = 5; //연산의 계산을 하기위한 상수

int n; //공용 변수

int number[PNUM]; //프로세스의 티켓의 값을 저장할 배열

int choosing[PNUM]; //프로세스가 번호표를 뽑았는지 아닌지를 기억하는지를 저장할 배열

int MAX() //티켓을 나눠주는 함수. 티켓 이 저장되어있는 number배열의 값들을 조사하여서 가장

{ //큰 값을 반환하여 주는 역할을 합니다.

int i; // for문을 사용하기위한 변수

int j; // for문을 사용하기위한 변수

int MAXNUM = 0; //가장 큰 번호표를 담을 변수 초기값을 0으로 설정해준다. 아무도 번호표가

for(i=0; i<PNUM; i=i+1) // 없을시 0을 반환하기 위해.

{ // 프로세스의 개수만큼을 비교한다.

for(j=0; j<PNUM; j=j+1)

{

if(number[i]<number[j]) //2중 for문을 이용하여 각자리를 비교 하고,

{

MAXNUM = number[j]; //가장 큰값을 MAXNUM변수에 저장한다.

}

}

}

return MAXNUM; //MAXNUM 변수를 반환해준다.

}

int NUM(int j, int i) //각 프로세스의 티켓번호를 비교하여 결과값을 돌려주는 함수.

{

if(number[j] < number[i]) // i프로세스가 현제 실행하는 프로세스 이므로 i 프로세스의 티켓이

{ // 더 낮을 때 루프를 탈출해야 하므로 number[j]<number[i]조건에서 참

return 1; // 일때는 1을 리턴 해주어 대기하게 만든다.

}

else if(number[j] > number[i]) // 위와 반대로 i프로세스의 티켓이 더 작을 때는 while루프를 빠져나갈

{ //수 있도록 0을 리턴해준다.

return 0;

}

else // 그리고 나머지경우는 두 프로세스간 티켓번호가 같을때 인데,

{ //이렇게 번호가 같을때는 두프로세스의 번호를 비교를 한다.

if(j<i) // 역시 i 프로세스가 현제 실행하는 프로세스이므로 i 프로세스의

return 1; //번호가 더 높을 때는 대기 상태를 가져야 하므로 1을 반환해주고,

else if(j>i) // 번호가 더 낮을 때는 0을 반환해주어 while루프를 빠져나가도록

return 0; // 해준다.

}

}

void enter_bakery(int i) //빵집알고리즘의 시작

{

int j; // 현제프로세스와 비교할 다른 프로세스들의 번호를 지정할 변수.

int k; // 조건을 통과하여 프로세스가 일을 수행 할 때 계산연산 for문을 위한 변수

choosing[i] = TRUE; // 티켓을 받기 전 의 상태를 저장.

number[i] = MAX()+1; // MAX함수를 통해서 이미 발부된 티켓 중 가장 높은 값의 다음값을 받는다.

choosing[i] = FALSE; // 티켓을 받은 후 의 상태를 저장.

for(j=0; j<PNUM; j=j+1) //이for문으로 모든 프로세스 티켓 과 프로세스번호로 통과 가능한지를 검사함

{

while(choosing[j]) //이 while 문에서 프로세스가 티켓을 받았는지를 검사함.

{ // 티켓을 받지 않았으면 대기상태로 빠짐.

// cout<<j<<" Process is Waiting until get a ticket"<<endl;

} //출력문은 출력 할 때 출력창이 너무 지저분해져서 주석처리 하였습니다.

while( (number[j] != 0) && (NUM(j, i)) ) // 이 while 문에서 티켓의 번호를 비교 검사함.

{ // 혹시 티켓의 번호가 같다면 NUM 함수 안에서 프로세스 번호를 비교함.

// cout<<j<<" Process is Busy Waiting"<<endl;

} //이 출력문 역시 출력창이 너무 지저분해져서 주석처리하고 출력하였습니다.

}

cout<<i<<"process's tiket"<<number[i]<<endl; //현제 수행하고 있는 프로세스의 티켓번호를 출력

n = 0;

cout<<i<<" process is calculating.."<<endl; //1을 5번 더하는 연산을 함

for(k=1; k<=N; k=k+1)

{

n = n+1;

}

cout<<i<<" process's calculate result is "<<n<<endl; // 완료된 결과를 보여줌.

}

void leave_bakery(int i) //프로세스가 연산을 하고나면 Busy Waiting중인 프로세스를 풀어주는 함수

{

cout<<i<<" process is calculate complete"<<endl;

number[i] = 0; //연산을 다 한 프로세스의 티켓을 0으로 바꾸어주면 while문의 number[j] !=0

} // 조건에서 false가 되므로 Busy Waiting상태가 풀리게 됨.

void process(int process) //일꾼의 역할을 하는 스레드

{

enter_bakery(process);

leave_bakery(process);

}

void main() //메인 함수

{

int i;

for(i=0; i<PNUM; i=i+1) // 처음의 number[i]배열과 choosing배열을 초기화 합니다.

{

number[i] = 0;

choosing[i] = TRUE;

}

cobegin

{

process(3); //10개의 프로세스를 병행 수행합니다.

process(2);

process(1);

process(0);

process(4);

process(5);

process(6);

process(7);

process(8);

process(9);

}

}