운영체제 코드 (임계구역 문제)

■Peterson's Solution (임계구역 문제)

int turn;

boolean flag[2];

do{

flag[i] = TRUE;

turn = j;

while(flag[j] && turn == j);

//임계구역

flag[i] = FALSE;

//나머지 구역

} while(TRUE);

1. 상호배제

2. Progress ( 임계구역에 다른 프로세스가 없으면 들어갈 수 있다. )

flag[i]를 FALSE로 바꾸고 나오기 때문에 기다리고 있던 프로세스는 임계구역을 들어갈 수 있다.

3. Bounded Waiting ( 다른 프로세스가 못들어오게 막아서는 안된다. )

자신이 다시 임계구역에 들어가기 위해서는 turn을 다른 프로세스에게 넘기므로 보장된다.

 

■Dekker's Solution (임계구역 문제)

int turn;

boolean flag[2];

do{

flag[i] = TRUE;

while(flag[j]){

if(turn==j)
{

flag[i] = FALSE;

while(turn==j)

; // do nothing

flag[i] = TRUE;

}

}

// critical section

turn = j;

flag[i] = FALSE;

// remainder section

}while(TRUE);

1. 상호배제

2. Progress : 만약 두 프로세스가 동시에 들어가길 원할 경우 turn 의 값에 따라 선택된 프로세스가 임계구역을 수행 하계된다. 수행후 빠져나올때 자신의 flag를 false로 하고 trun을 다른 프로세스에게 주기 때문에 기다리고 있던 프로세스는 진행할 수 있게 된다.

3. Bounded-Waiting : 임계구역에서 나올 때 turn 을 다른 프로세스에게 넘겨주기 때문에 기다리고 있는 프로세스가 있다면 최소한 한번은 진입할 수 있게 된다. 즉 다른 프로세스가 기다리고 있다면 자신이 연속으로 두번 들어갈 수가 없게 된다.

 

■임계구역 문제 하드웨어적 해결 (TestAndSet)

do{

while(TestAndSet(&lock))

; // 아무 일도 하지 않음

// 임계 구역

lock = FALSE;

// 나머지 구역

}while(TRUE);

 

■상호배제 문제 하드웨어적 해결 (Swap)

do{

key = TRUE;

while(key)

swap(&lock, &key);

// 임계 구역

lock = FALSE;

// 나머지 구역

}while(TRUE);

 

■위의 하드웨어적 해결들은 Bounded-Waiting 을 보장하지 못한다.

do{

waiting[i] = TRUE;

key = TRUE;

while(waiting[i] && key)

key = TestAndSet(&lock);

waiting[i] = FALSE;

//임계구역

j = (i+1) % n;

while(j != i && !waiting[j])

j = (j+1) % n;

if(j==i)

lock = FALSE;

else

waiting[j] = FALSE;

//나머지 구역

}while(TRUE);

 

■Critical Section이 만족해야 하는 3가지 문제

1) 상호배제 : 임계구역에는 오직 한 프로세스만이 들어가야 한다.

2) 진행 : 대기하고 있는 프로세스를 while문에서 벗어나게 해줄수 있는 조치를 하고 임계구역을 나와야 한다.

3) 한정된 대기 : 대기하고 있는 프로세스가 있다면 내가 연속적으로 두번 임계구역을 접근 할 수 없다.