[운영체제] 5-3. Critical Section Problem-SW Solution

지난 시간에 다뤘던 Critical Section Problem을 해결하는 방법에 대해서 다뤄보고자 합니다. 그 중에서도 SW 적으로 해결할 수 있는 솔루션을 알아봅시다.

 

---

요구사항

우선, 우리는 항상 어떠한 문제를 해결하기 위해서는 아래와 같은 질문에 대한 답을 얻고 시작해야합니다.

• 문제를 해결하기 위해 무엇을 충족해야하는가?

 

이번에 소개한 Critical Section Problem(이하 csp)를 해결하기 위한 요구사항들은 다음과 같습니다.

 

Mutual Exclusion(상호 배제)

: 한 프로세스가 critical section을 수행하는 중이라면, 해당 critical section은 다른 프로세스가 실행할 수 없음을 의미합니다.

 

Progrss(실행 가능)

: 만약 어떤 critical section을 아무도 실행하지 않을 때, 할당된 프로세스가 critical section을 수행해야한다면, 꼭! 실행할 수 있어야합니다.

 

Bounded Waiting(유한 대기)

: 어떤 프로세스가 critical section을 실행하고 있을 때, 다른 프로세스들이 critical section을 실행해야한다면, 무한정 대기하는 것이 아닌, 정해진 시간동안 wait 해야하는 것을 의미합니다.

 

3번째 조건에 대해 의문 사항이 있을 수 있습니다!! 여기서 최악의 경우 예시를 들어 설명해보겠습니다.

 

우리는 P1, P2, P3의 프로세스를 갖고 있습니다. 이 프로세스들은 어떤 critical section을 수행해야합니다.

 

1. 그 critical section을 P2가 실행 중이고, 다 마치지 못한 상태로 P1으로 프로세스 스위치가 됐습니다.(Time Sharing에서!)

2. 그렇다면 P1은 critical section을 수행해야하지만, P2가 진행 중이므로 wait하게 됩니다.

3. P1의 time quantum이 끝나, P2로 프로세스 스위치가 됩니다.

4. P2는 나머지 critical section을 끝나고 P3로 프로세스 스위치가 일어납니다.

5. P3가 critical section을 수행하다가, 다 마치지 못하고 P1으로 프로세스 스위치가 됩니다.

6. P1은 P3가 critical section 내에 있으므로, 또 wait합니다.

7. P3로 프로세스 스위치 되고, critical section을 완료합니다.

8. P2로 프로세스 스위치 되고, critical section에 들어갑니다

.

.

.

 

이러한 과정을 거치게 되면 P1은 무한정 대기상태가 됩니다. 이러한 최악의 상황을 고려하여 생겨난 조건이라고 이해하시면 됩니다.

 

---

 

Software Solution

자! 이제, 정말로 이러한 문제를 해결하는 방법에 대해서 알아봅시다. 우리는 SW로 해결하는 부분에 대해 다뤄보겠습니다.

 

우선, 전 시간에 SW로 처리하는 방법이 2가지가 있었습니다. (기억 안난다면 여기!!) 그 중에서, fence에 대한 solution을 소개하겠습니다.

여기서 다루는 solution의 기본 원리는 아래와 같습니다.

 

이런 식의 흐름으로 critical section을 entry section와 exit section으로 감싸 fence를 만듭니다. entry와 exit의 자세한 코드 구현은 방식마다 다르므로, 아래에서 자세히 설명합니다.

 

위 코드처럼 entry section에서 만약 다른 프로세스가 이 critical section을 수행한다면, pass 시키고 while문을 반복하는 방식입니다. 만약 그렇지 않고 critical section을 아무도 실행하지 않는다면, critical section으로의 입장을 entry section이 허용합니다.

후에, critical section을 모두 처리하였다면, entry section에서 다른 프로세스가 들어올 수 있도록 exit section에서 작업을 해줍니다.

 

 

자, 그럼 이제 이 SW Solution의 구체적인 구현 방식들을 살펴봅시다.

 

Software Solution 1

각 프로세스 또는 쓰레드들이, 같은 데이터를 접근하는 critical section을 수행해야 한다면 공유하는 변수들이 존재해야합니다. 여기서의 공유변수는 turn입니다.

 

이 변수는, int 타입으로 초기에는 0을 가집니다. turn이 가르키는 숫자에 해당하는 프로세스가 critical section을 실행할 수 있음을 의미합니다. 아래의 코드를 보시죠.

do{ // P_i의 코드
	while(turn != i); // entry section
    
    /* critical section */
    
    turn = j; // exit ection
    
} while(true);

 

P_i는 자신의 턴이 아니라면 2번째 줄의 while문에 걸려 하단의 critical section을 실행할 수 없습니다. 하지만 turn == i일 때, critical section을 진행하고 turn을 j에게 줍니다. 즉, 다른 프로세스에게 주는 시스템이죠. 하지만 이 Solution은 프로세스가 2개일 때만 성립됩니다. (turn이 언제 누구에게 배정될 지 결정할 수 없을 뿐더러, 순차적으로 turn을 증가시키는 것은 옳지 못합니다.)

 

이러한 방식으로 csp를 방지할 수 있습니다.

 

하.지.만. 미리 눈치를 챌 수 있으셨겠지만 이 Solution은 위에서 소개해드린 요구사항을 모두 충족하지 못합니다. 또한 적절한 솔루션이라고도 할 수 없죠. 무엇을 충족하지 못할까요??

 

 

바로, Progress 성질입니다. 공유 변수 turn은 0으로 초기화됩니다. 따라서 만약 우리가 P_0가 먼저가 아닌 P_1을 먼저 자원을 할당해주면, P_1은 아무것도 하지 못하고 while문에 걸려 wait하게 됩니다. critical section을 아무도 실행하지 않는데 말이죠.

 

따라서 이 솔루션은 적절하지 못합니다.

 

 

Software Solution 2 (Peterson's Algorithm)

이 방법은, Solution 1에서 소개한 부분에서 Progress 성질을 만족하도록 수정한 것입니다. 다만, 2개의 프로세스라는 제한사항은 유지됩니다. 바로 코드로 확인해보겠습니다.

 

do{ // P_i의 코드

	// entry section
	flag[i] = true;
    turn = j;
	while(flag[j] && turn == j); 
    
    /* critical section */
    
    flag[i] = false; // exit ection
    
} while(true);

여기서는 turn보다 flag를 적극 활용합니다. 기존과 동일하지만 flag를 통해서 다른 프로세스에서 critical section을 확인하는 과정을 거칩니다. 만약 turn이 내가 아니라도, flag[j]가 false라면 while문에 걸리지 않아서 바로 critical section으로 들어갈 수 있게 되는 것입니다.

 

즉, turn이 부가적인 역할이 되며, 결정적으로 flag가 역할을 한다고 생각해도 무방합니다.

 

 

하지만, 우리는 언제나 2개의 프로세스 혹은 쓰레드만이 같은 데이터를 접근한다는 보장은 없습니다. 수많은 프로세스 혹은 쓰레드들이 데이터를 접근할 수 있게, 즉 critical section을 접근할 수 있게 하는 것이 일반적입니다.

 

 

Software Solution 3

그래서 프로세스가 2개 이상일 때도 가능하도록 설계했습니다.

do{
	// entry section
	choosing[i] = true;
    number[i] = max(number[0], number[1], ..., number[n-1])+1;
    choosing[i] = false;
    for(int j=0; j<n; j++){
    	while(choosing[j]);
        while( (number[j] != 0) && (number[i], j) < (number[i], [i]));
    }
    
    /* critical section */
    
    number[i] = 0; // exit section
} while(true);

보기만 해도, entry section에 너무 많은 시간을 쏟을 것 같다는 것이 느껴지시나요?? 이 방법은 여러개의 프로세스에도 적용이 된다는 장점이 있지만, entry section에 너무 많은 시간을 소비하게 됩니다.. 이것을 Overhead라고 부릅니다.

 

문제를 해결할 수 있는 것은 맞지만, overhead가 있으므로 우리는 사용하지 않습니다.

 

---

 

즉.. 우리는 SW로는 csp를 해결할 수 없습니다. 아니, 정확히는 이것보다 좋은 방법이 존재한다는 것이겠죠. 바로 하드웨어입니다. 하드웨어는 소프트웨어보다 훨씬 빠른 속도를 가지고 있으므로 이를 이용해 해결합니다. 다음 글에서는 하드웨어 측면에서 어떻게 해결할지를 알아봅시다.