Think Positive!

Monitor 를 이용한 상호 배제의 문제를 생산자-소비자(한계 버퍼) 문제에 적용하여 baci툴을 이용하여 구현한 것.

목표 및 내용

수업 시간에 배웠던 Monitor를 이용 상호 배제가 되도록 구현을 하는것 입니다. Monitor는 세마포어를 이용한 정확한 프로그램의 작성이 어렵기 때문에 고안된 것입니다. 기능은 세마포어와 동일하나 세마포어보다 제어가 더 쉽습니다. baci툴에서는 Hoare 의 방법이 이용됩니다. Monitor 의 구성요소는 C 언어에서의 구조체와 비슷하고 객체 언어에서는 클래스의 개념과 유사합니다. 구성 순서는 지역변수와 하나이상의 procedure 그리고 초기화 하는 문장의 순서대로 작성이 됩니다.  

모니터는 한 번에 하나의 프로세스만 모니터 내에 존재하게 하고, 공유데이터 보호를 위해서 모니터 구조 내에다가 공용변수를 둠으로써 상호 배제를 보장합니다. 모니터는 조건 변수를 통해서 조건이 만족될때 까지 대기하고 조건이 만족하여 가용 상태가 되면 대기 프로세스가 일을 수행 할 수 있도록 재진입 하게 됩니다.

Semaphore 를 이용한 상호 배제의 문제를 생산사 - 소비자(한계 버퍼) 문제에 적용하여 baci 툴을 이용하여 구현을 한 것이다.

목표 및 내용

수업 시간에 배웠던 semaphore를 이용 상호 배제가 되도록 구현을 하는것 입니다. 우선 semaphore는 이 때 까지 의 busy waiting 이 계속 해서 cpu의 자원을 사용 하는 문제를 해결하기위하여 다른 프로세스가 임계 구역을 사용하고 있을 때, 진입을 하게 되면 블록 상태가 되고, 이미 임계구역에 들어가 있던 프로세스는 임계구역을 탈출 하면서, 신호를 보내주어 블록 되어있던 프로세스를 깨웁니다. 이러한 방법으로 cpu자원의 낭비도 없애고 상호배제 도 가능하게 할 수 있습니다.

semaphore wait signal 구조

2진 세마포어

세마포어 연산의 정의

알고리즘

앞서 했던 피터슨 알고리즘 은 두 프로세스간의 상호 배제 가 가능하게 하였고, 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에서 실행화면

운영체제 수업시간에 공부했었던 빵집알고리즘(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);

}

}

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

내용

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

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

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

이전에 올려둔 jBaci 툴을 사용하는 방법을 정리 ㅎ

이전에 올려둔 jbaci파일을 다운 받아서 압축을 풀면 run.bat파일이 있다. 그 파일을 실행하면 CMD 창과 함께 다음과 같은 화면이 나온다.

 최초 실행화면  

여기서 에디트에다 테스트 소스를 다음과 같이 입력해본다.

cobegin 문은 병렬로 프로세스들을 실행할때 사용하는 구문이다.

작성이 완료 되었으면 저장을 하는데 저장 할 때, 파일명.cm으로 저장을 한다

저장이 된후에 컴파일 을 눌러주면 소스가 이상이 없을시 다음과 같은 문구가 와 CMD창에도 변화가 생긴다. 그리고 .cm이 있는 폴더에 파일명.lst와 파일명.pco 파일이 생성이 된다.

제대로 완료가 되었으면 Run 탭을 눌르면 다음과 같은 창이 나온다.

Go 버튼을 눌르면 실행이 되는데 옆에 Processes 탭에서 각 프로세스를 더블클릭하면 다음과 같이 각 프로세스별 상황이 다 출력된다.

참고 ) 디버그 하는방법

1.  Run화면에서 Step Pcdoe 를 눌르면 한스텝씩 계속해서 진행이된다.

2. Go를 누른후 Pause를 눌르고 Step Source를 눌르면 한스텝씩 진행이된다.

jbaci1-4-5.zip

baci 툴을 더 쉽게 사용할수 있도록 만든

Jbaci 툴입니다.

badosxe-2005Nov09.zip

BACI 툴 입니다. 운영체제 교육 자료