신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

지난글에 이어서

(지난글 보기 >> 2017/12/13 - [OS] - OS :: 프로세스 동기화 (Process Synchronization) [첫번째] )

 

이번에는 Critical Section에 대해서 알아보겠습니다.

 

 

    Critical Section Problem

 

각 프로세스는 임계구역이라고 부르는 코드부분을 가지고 있습니다.

한 프로세스가 자신의 임계구역에서 수행하는 동안에는 다른 프로세스가 그들으 임계구역에 들어갈 수 없습니다.

즉, 동시에 여러 프로세스가 그들의 임계구역 안에서 실행할 수 없다는 것입니다.

 

이런 임계구역 문제는 지난글에서 얘기했던 "race condition"(경쟁 상황)을 막을 수 있는 해결책이 될 수 있습니다.

 

 

임계구역의 3가지 요구조건을 충족해야 합니다.

  • mutual exclusion (상호배제) : 특정한 프로세스가 임계구역에서 실행되는동안, 다른 프로세스가 접근 할 수 없다.
  • progress (진행) : 임계구역을 사용하지 않고 있다면, 다른 프로세스가 접근할 수 있도록 한다.
  • bounded waiting(한정된 대기) : 임계구역 진입 횟수에 한계가 있어서 같은프로세스가 계속 독점해서  사용하지 못하게 한다. 다른 프로세스들이 기아상태에 빠지지 않도록 한다.

이 3가지 모두 만족시켜야 유효한 알고리즘이 됩니다.

 

 

전형적으로 프로세스는 크게 4가지의 구역으로 나눠집니다.

do{
    /*********************
        entry section
        ...
    */
 
    
    /*********************
        critical section
        ...
    */
 
 
    /*********************
        exit section
        ...
    */
 
 
    /*********************
        remainder section
        ...
    */
} while(true)
 
  • entry section

  • critical section

  • exit section

  • remainder section

각 프로세스는 임계구역에 들어가기 위해서는 진입허가 요청을 해야합니다. 이런 요청하는 코드가 있는 부분을 Entry Section(진입 구역) 이라 합니다. 임계구역 뒤에는 Exit Section(퇴출 구역), 그리고 나머지 코드 부분은 Remainder Section(나머지 구역)으로 나눠집니다.

 

여기서 entry section 과 exit section은 중요한 코드이기 때문에 알아둘 필요가 있습니다.

 

 

    Peterson's Solution 

 

 

임계구역 문제를 소프트웨어 기반으로 해결하는 Peterson's solution(피터슨의 해결안)에 대해 알아보겠습니다.

 

피너슨의 해결안에서는 공유하는 2개의 데이터 항목을 가지고 해결합니다.

 

int turn;

boolean flag[2];

 

turn : 임계구역으로 진입할 프로세스의 순번을 나타냄 (예를들어, turn = i 이면 프로세스 Pi가 임계구역에서 실행)

flag : 특정한 프로세스가 임계구역으로 들어갈 준비가 되었다는 것을 나타냄 (예를들어, flag[i] = true 이면  프로세스 Pi는 임계구역에 진입할 준비가 되었다는것)

 

 

 

위 코드는 프로세스 i의 실행 구조 입니다.

 

위와 같이 flag[i] = true에 의해 프로세스 i 는 임계구역에 들어갈 준비가 됐다는 것을 알려줍니다.

그 밑에 turn = j 에 의해 프로세스 j가 실행될 차례라는것을 알 수 있습니다.

 

1. flag[j] == true (프로세스 j가 임계구역에 들어갈 준비가 됐다) 이고 turn == j 이면(프로세스 j가 임계구역에 들어갈 차례) 프로세스 j가 critical section에 들어갈 차례이므로, 무한루프에 들어가 기다리게 됩니다.

 

2. 그리고 프로세스 j가 임계구역 작업을 마치고 flag[j]의 값이 false가 되면, 프로세스 i 는 무한루프를 빠져나와 임계구역에 들어가게 됩니다. 

 

3. 프로세스 i가 작업을 완료후 flag[i] = false 로 설정하고, 다른 프로세스가 임계구역을 사용 할 수 있도록 해줍니다.

 

 

위 과정을 보면 mutual exclusion, progress, bounded  waiting 이 3가지 조건을 만족합니다.

 

위 방법이 소프트웨어적인 방법이라면,

이번엔 하드웨어에서부터 소프트웨어기반으로 해결하는 방법.

동기화 하드웨어(Synchronization Hardware)에 대해 알아보겠습니다.

 

 

    Synchronization Hardware

 

단일처리기 환경과 다중처리기 환경 2가지에서 볼때,

단일처리기 환경에서는 공유변수가 변경되는 동안에는 인터럽트가 일어나지 않게 해서 간단히 해결할 수 있습니다.

 

하지만, 다중처리기 환경에서는 이 방법을 적용시킬수 없습니다. 모든 처리기에 인터럽트를 하지 못하게 메시지를 전달하기엔 CPU의 이용률은 떨어뜨리기 때문입니다.

 

현대 많은 기계들은 한워드(word)의 내용을 검사하고 변경하거나, 두 워드의 내용을 원자적으로(Atomic) 교환할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공합니다.

 

여기서 중요한 포인트는 원자적(Atomic) = 인터럽트 되지 않는(non-interruptible) 이라는 부분입니다.

 

예를들어 test_and_set() 과 compare_and_swap() 이라는 명령어를 가지고 얘기 해보겠습니다.

 

1. test_and_set()

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

 

공유변수 lock을 설정해서 임계구역에서 작업할때는 true, 작업을 하지 않을때는 false라 하겠습니다.

do{
 
    while(test_and_set(&lock))
        /*do nothing*/
    ;
 
    /*********************
        critical section

    */
 
    lock = false;
 
    /*********************
        remainder section

    */
} while(true);

처음 lock의 값을 false (다른 프로세스가 임계구역을 사용하지 않고 있다)라 가정 하겠습니다.

test_ans_set() 명령어에 의해 false값을 반환하고 lock의 값은 true로 바뀝니다. (lock == true 즉, 임계구역을 사용한다는 뜻)

그리고 while문은 빠져나와 임계구역에 들어가게 됩니다.

임계구역에서의 작업을 마친뒤에 lock= false; 로 바꿔줘서 다른 프로세스가 임계구역을 이용할 수 있도록 해줍니다.

 

만약 어떤 프로세스가 임계구역을 사용하고 있을때는 공유 변수인 lock의 값은 true인 상태가 됩니다.

그러면 test_and_set() 명령어에서 true 값을 반환 하기때문에, 무한 루프에 들어가 "do nothing" 아무일도 하지 않게 됩니다. (다른프로세스의 임계구역 작업을 기다리는중)

 

 

2. compare_and_swap()

int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;
    if(*value = expected){
        *value = new_value;
    }
    return temp;
}

 

do {
 
    while(compare_and_swap(&lock, 0, 1) != 0)
        /* do nothing */
    ;
    
    /*********************
        critical section
    */
    
    lock = 0;
 
    /*********************
        remainder section
    */
} while(true);
 

test_and_set() 과는 조금 다르게 int 타입을 반화하고 인자로 3개가 들어갑니다. 공유변수인 lock의 주소, 예상하는 값, 새로운 값

 

처음 lock의 값을 0이라 가정하겠습니다. (임계구역을 사용할 수 있다.)

compare_and_swap 에 의해 0을 반환하고, lock을 새로운 값(1 즉, 임계구역을 사용할 것이다.)으로 설정 해줍니다.

 

그리고 critical section(임계구역) 작업을 실행하고 작업을 마친 뒤에 lock의 값을 다시 0으로 설정해, 다른 프로세스가 이용 할 수 있도록 해줍니다.

 

위 test_and_set() 과 compare_and_swap()은 조금 달라보여도, 결국은 lock이라는 공유변수를 이용해 임계구역을 사용할 수 있는지 없는지를 설정하고, 그 설정된 값을 이용해서 프로세스끼리 상호배제시키는 같은 역할을 합니다.

 

다음글 보러가기

>>  2017/12/13 - [OS] - OS :: 프로세스 동기화 - mutex lock, semaphore [세번째]

 

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기