Process Synchronization - Critical Section Problem

Critical Section Problem, 임계 구역 문제

     

Critical Section이란 Process 또는 Thread들이 공통 변수들을 변경하고, 테이블을 갱신하며,

     

파일의 쓰기 작업들을 수행하는 구역을 말한다.

     

이전 포스트에서 말한 Race Condition이 일어 날 수 있는 구역을 말하는 것이다.

     

(이제부터 포스팅의 편의를 위해 Thread를 중점으로 설명하겠다.)

     

사실 상 이런 Race Condition문제의 경우 한 Thread가 Critical Section에 들어갔을 경우 다른 Thread들은 해당 구역으로의

     

접근을 배제해야 한다. 하지만 무조건적으로 접근을 배제 할 수는 없기 때문에 해결 방법에는 몇 가지 요구 사항이 존재한다.

     

1. Mutual Exclusion, 상호배제 : 어떤 Thread가 Critical Section에서 수행되고 있다면

     

다른 Thread들은 해당 Critical Section에 접근 할 수 없다.

     

2. Progress, 진행 : Critical Section에서 수행되는 Thread가 없으며 해당 Critical Section에

     

접근 하려는 Thread가 존재 할 경우 접근이 가능해야 한다.

     

Bounded Waiting, 한정대기 : Thread의 Starvation상태를 막기 위해 Thread가 Critical Section에 대한

     

접근 대기 시간은 한정되어야 한다.

     

몇 가지 알고리즘들을 확인해보자. 여기의 두 개의 Thread i와 j가 존재한다.

     

첫 번째 알고리즘은 아래와 같다. 이때 turn은 i로 초기화 되어 있다.

     

 

 

     

위의 코드는 Thread i의 코드이다. Entry Section에서 만일 turn이 i가 아니하면 대기하게 되고

     

i가 되면 Critical Section으로 접근하게 된다. 그리고 마지막에 turn을 j로 변경시킨다. 이로써 한번에 하나의

     

Thread만이 접근이 가능하기 때문에 mutual Exclusion은 성립되었다.

     

하지만 만일 turn 이 i이고 Thread i가 Critical Section에 들어가지 않는다고 가정하자.

     

이때 j가 Critical Section에 들어가려고 한다면 turn이 I로 되어 있기 때문에 Critical Section으로 접근 할 수 없다.

     

때문에 Progress가 성립하지 못한다.

     

그렇다면 두 번째 알고리즘을 보자. 이때 flag[i], flag[j]는 false로 초기화되어 있다.

     

 

     

위 코드에서 flag는 각각의 Thread가 Critical Section에 들어갈 준비가 되어 있나를 확인하는 것이다.

     

Thread i는 Critical Section에 들어가지 전에 자신의 flag를 true로 바꾸고 j의 flag가 false이여야만 접근 할 수 있다

     

. 따라서 한번의 하나의 Thread만이 Critical Section에 접근이 가능하다. 그러므로 mutual Exclusion은 성립되었다.

     

하지만 이전 포스트에서도 언급했듯이 flag를 변경시키고 Check하는 코드가 분리되어

     

있기 때문에 만일 순서가 섞이게 되면 두 개의 flag가 true로 변경 될 수도 있다. 이 때는 Check하는 코드에서

     

두 개의 Thread가 걸려 있기 때문에 Progress가 성립하지 못한다.

     

마지막으로 세 번째 알고리즘을 확인해 보자. 세 번째 알고리즘은 첫 번째와 두 번째 알고리즘의 주요 개념들을 결합한 것이다.

     

 

     

위 코드에서 flag의 값은 false로, turn의 값은 상관없다. Thread i는 Critical Section에 접근하기 전에

     

 flag를 자신으로 변경시켜놓고 turn을 상대방으로 바꾸어 놓는다. 그리고 나서 상대방의 flag와turn을 확인하여서

     

둘 다 만족하는 동안에는 계속 대기를 하게 된다. 만일 첫 번째 알고리즘의 문제 상황이 일어날 경우 어차피 처음에 flag를

     

자신의 변경시키기 때문에 Check문을 문제없이 빠져 나간다. 두 번째 알고리즘의 문제 상황의 경우 순서가 뒤섞인다고

     

 해도 결국 하나의 Thread는 돌아가게 된다. 이는 turn을 상대방 위주로 해놓기 때문인데 만일

     

turn을 자신 위주로 설정을 하게 되면 순서가 뒤섞이면 Check문에서 계속 대기하게 되어서 Bounded Waiting이 불성립한다.

     

위와 같이 첫 번째, 두 번째 알고리즘의 문제 상황을 확인해 보아도 문제점이 보이지 않는다.

     

그 뿐만이 아니라 다른 어떤 예외적인 상황에도 세 번째 알고리즘의 경우

     

Critical Section Problem 해결법의 3가지 조건을 모두 만족시킨다.