Think Positive!

앞서 했던 피터슨 알고리즘 은 두 프로세스간의 상호 배제 가 가능하게 하였고, bakery 알고리즘 에서는 N개 이상의 프로세스의 상호 배제를 티켓과 프로세스 번호를 이용하여 구현 하는 방법 이다. 이번 Test-and-set 을 이용한 상호 배제는 atomic function 을 사용해서 함수의 조건을 비교 할 때엔 한 프로세스가 점령을 하면 다른 프로세스가 개입을 할 수 없도록 선점해서 사용하는 개념으로 상호 배제를 하는 기법 이다.

알고리즘

Jbaci로 구현한 소스코드

const int TRUE = 1; //TRUE 를 1로 정의

const int FALSE = 0; //FALSE 를 0으로 정의

const int PCOUNT = 5; // process 의 개수 정의.

int lock = 0; // 공용 lock 변수.

int waiting[PCOUNT]; //프로세스 번호가 가까운 사람에게 자리를 주기위하여 waiting배열 선언.

int n; // 연산을 위한 공용 변수 n

atomic int Test_and_set(int& loc) // atomic 함수로 함수에 진입하고 나면 다른 프로세스가 간섭 할수 없다.

{ // 인자 값을 &를 써서 주소 값으로 받은 이유는 공용변수 lock 을 직접적으로

int TAS; // 호출 할 경우 함수 밖의 값을 불러 오는 것이기 때문에 다른 프로세스의 간섭

TAS = loc; // 이 일어날 수 있다.

loc = TRUE; // lock 변수의 값을 다른 TAS변수에 저장하고 lock변수 안의 값을 1로 세팅을 한 //다.

return TAS; // 그리고 초기의 lock변수 의 값인 TAS의 값을 반환을 한다.

}

void enter_region(int i) //임계구역의 진입을 조건에 의해서 각 프로세스가 상호 배제가 되도록 하는 함수

{

int j; // for 문을 위한 변수

// int key = FALSE; // 키 값을 선언하고 초기화를 해준다.

// 현제 key 값이랑 밑의 와일문을 주석 처리 해놓았는데 이유는 아래 소스분석

waiting[i] = TRUE; //에서 설명 하겠습니다. waiting[]배열에 자신의 프로세스번호에 해당하는 곳에

// key = TRUE; // 값을 참으로 설정 한다.

while( (waiting[i]) && Test_and_set(lock) ) // 여기서 waiting값은 참이므로 뒤의 Test_and_set함수

{ //에서 참이 나오면 대기상태가 되고 거짓이 나오면

} //while 문을 통과하여 임계구역에 진입하게 됩니다.

// while( (waiting[i]) && key ) // 주석문은 원 알고리즘을 보고 처음 코딩했던 소스입니다.

// {

// key = Test_and_set(lock); //Test_and_set의 함수의 리턴 값을 담아 다음 조건에서 비교를함.

// }

waiting[i] = FALSE; // 임계구역에 진입 했으므로 waiting변수를 0으로 해준다.

// 변수를 0으로 해주는 이유는 leave_region에서 인근 프로세스에게

//임계구역을 넘겨줄 때 쓰임.

cout<<i<<" process is enter_region"<<endl; //프로세스가 들어왔다는 문구 출력

n=0; // 공용변수 n의 초기화

cout<<i<<" process's calculate start!"<<endl; // 프로세스 계산 시작 문구 출력

for(j=0; j<5; j=j+1) //1씩 더하는 연산

{ //여기서 간섭이 생긴다면 n이 공용변수이므로

n = n+1; //n의 값이 5가 나오지 않을 것임.

}

cout<<i<<" process's calculate result is "<<n<<endl; // 계산 결과를 출력하는 문구.

}

void leave_region(int i) // 일을 다 하고 임계구역을 나간후에 연산하는 함수

{

int j; //다른 프로세스 아이디를 담을 변수

j = (i+1) % PCOUNT; // 현재 프로세스에서 +1을 하고 전체 프로세스 수로 나누어 남은 값. 즉

// 현재 계산 하고난 다음번호의 프로세스 번호를 담음. ex) 0->1

while( (j != i) && !(waiting[j]) ) //j와 i가 같다면, 주변 프로세스 한 바퀴 검사 한 것이므로 더 이상

{ // 검색하지 않는다. 그리고 waiting에 0이 있다면 이미 실행한 프로

j = (j+1) %PCOUNT; //세스 이므로 다음 프로세스로 넘긴다 .

} // while 문장 안은 다음의 뒷 프로세스를 검색하는 것임.

if( j==i ) // 한 바퀴다 돌아도 임계구역에 들어갈 프로세스가 없다면

{ //lock 공용변수를 풀어주고 끝낸다.

lock = FALSE;

}

else //누군가 인접한 프로세스가 대기하고있다면 그 프로세스에게 먼저 기회를 준다.

{

waiting[j] = FALSE;

}

cout<<i<<" process is leave_region"<<endl; // 임계구역을 탈출했다는 문구

}

void process(int i) // thread

{

{

enter_region(i);

leave_region(i);

}

}

void main()

{

int i;

for(i=0; i<PCOUNT; i=i+1) // waiting배열을 초기화 함.

{

waiting[i] = FALSE;

}

cobegin // 병행으로 프로세스 5개를 실행함.

{

process(0);

process(1);

process(2);

process(3);

process(4);

}

}

baci에서 실행화면

Jbaci에서 실행화면