앞서 했던 피터슨 알고리즘 은 두 프로세스간의 상호 배제 가 가능하게 하였고, 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에서 실행화면
'Study > OS' 카테고리의 다른 글
Monitor 를 이용한 생산자-소비자 구현 (0) | 2012.05.04 |
---|---|
Semaphore 구현하기 (2) | 2012.05.04 |
Bakery 알고리즘 (1) | 2012.04.22 |
Peterson 알고리즘 (0) | 2012.04.22 |
jBACI 사용법 (0) | 2012.04.15 |