티스토리 뷰

프로그래밍/OS

Process Synchronization

국윤창 2018. 5. 22. 03:15

협력적(cooperating) process는 시스템 내에서 실행 중인 다른 process의 실행에 영향을 주거나 영향을 받는 process이다. 공유 데이터를 사용하는 process(예를 들면 thread)들이 공유 데이터에 동시에 접근한다면, 공유 데이터는 일관성을 유지할 수 없을 것이다. 이를 해결하기 위한 다양한 메커니즘이 있다.


1. Background

동기화가 필요한 상황을 살펴보기 위해 생산자-소비자 문제를 예로 들자. 생산자와 소비자 코드는 아래와 같다.


* Producer code

item nextProduced;

while( true ) 
{
    /* Produce an item and store it in nextProduced */
    nextProduced = makeNewItem( . . . ); 

    /* Wait for space to become available */ 
    while(counter == BUFFER_SIZE)
        ; /* Do nothing */
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}


* Consumer code

item nextConsumed;

while( true ) 
{
    /* Wait for an item to become available */ 
    while(counter == 0)
        ; /* Do nothing */

    /* Get the next available item */ 
    nextConsumed = buffer[ out ];
    out = ( out + 1 ) % BUFFER_SIZE;
    counter--;

    /* Consume the item in nextConsumed
        ( Do something with it ) */
}

위 코드는 개별적으로는 문제될 것이 없지만, 동시에 실행되면 데이터에 비일관성이 생긴다. 왜냐하면 생산자, 소비자 모두 counter 변수의 값을 조정하고 있기 때문이다. 왜 이것이 문제가 되는지 아래의 기계어를 보자. 생산자의 counter++와 소비자의 counter--는 아래 그림 1과 같은 기계어로 구현될 수 있다.

[그림 1] Instructions


register1, register2는 CPU의 local register이다. 두 process(또는 thread)가 각각 counter++, counter-- 코드를 병행하여 실행할 때, 많은 경우 중 아래 그림 2와 같은 순서를 가질 수 있다.

[그림 2] Interleaving


counter가 5인 상태에서 counter++와 counter-- 한 번씩 실행하면 다시 5가 돼야 하지만, counter == 4로 부정확한 결과가 나왔다. 이처럼 여러 개의 process가 동일한 데이터에 접근하여 조작할 때, 그 결과가 접근이 발생한 특정 순서에 의존하는 상황을 race condition이라고 한다.

race condition은 디버깅 하기가 아주 까다로운데, 그 이유는 race condition이 드문 경우에만 발생하고 재현하기가 매우 어렵기 때문이다. race condition으로부터 데이터를 보호하기 위해선 한 번에 하나의 process만 공유 데이터에 접근하도록 해야한다.


2. The Critical-Section Problem

위에서 설명한 생산자-소비자 문제는 process가 critical section problem을 해결해야 한다. critical section은 아래와 같은 특징을 가진다.


* 하나의 process만 critical section 안에서 실행할 수 있다. 만약 process A가 이미 critical section에서 실행되고 있고 process B가 critical section 내에서 실행되길 원할 경우, process B는 process A가 critical section 작업을 완료할 때까지 기다려야 한다.


* process가 critical section에 진입하려면 진입허가를 요청해야 한다. 진입허가 요청을 구현하는 코드 부분을 entry section이라 부르고, critical section에 접근하는 것을 제어(lock)한다.


* critical section 뒤에는 exit section이 있다. lock을 해제하는 등, 더 이상 critical section에 존재하지 않을 때 알리는 역할을 한다.


* critical section, entry section, exit section에 포함되지 않는 나머지 코드는 remainder section이라 부른다.


이 구조를 그림으로 표현하면 아래 그림 3과 같다.

[그림 3] General structure of a typical process Pi



critical section problem에 대한 해결 방안은 아래의 세 가지 요구조건을 충족해야 한다.


* Mutual Exclusion: 한 번에 하나의 process만 critical section에서 실행될 수 있다.


* Progress: critical section에 들어가지 않은 process가 다른 process가 critical section에 진입하려는 것을 막아선 안된다. (mutual blocking)


* Bounded Waiting: critical section에 진입하려는 요청을 하면, 중간에 순서를 뺏기는 횟수를 제한해야 한다.(process의 실행이 무한히 연기되면 안된다.) (not starvation)


열린 파일 리스트를 업데이트하거나 가상 메모리를 다루는 등, 두 개 이상의 kernel process가 동시에 공유 kernel data에 접근할 때 race condition이 발생할 수 있다. OS는 두 종류의 kernel을 사용하며, 사용하는 kernel에 따라 critical section을 다루기 위한 접근법이 다르다.


* Preemptive Kernel: process가 interrupt 처리를 위해 kernel mode에서 실행되는 동안 선점되는 것을 허용한다. 응답성이 좋기 때문에 real-time system에 적합하다. 하지만 race condition을 해결해야 하므로 신중하게 설계되어야 한다. SMP 시스템은 서로 다른 처리기의 두 프로세스가 동시에 kernel mode에 있을 수 있으므로, preemptive kernel을 설계하는 것이 특히 어렵다.


* Non-Preemptive Kernel: process가 kernel mode에서 실행되는 동안 중단되지 않는다. kernel mode에서 race condition의 가능성을 없애지만, 응답성이 낮을 수 있다. 따라서 real-time systme에 적합하지 않다.


Linux는 2.6 버전 이전까진 Non-Preemptive Kernel을 사용했으나, 2.6 버전부터 Preemptive Kernel을 사용한다.


3. S/W Solution for Ciritical Section

Critical Section에 대한 S/W 해결책이 몇 가지 있다.


3.1 Dekker's Solution

공유 메모리를 사용하여 두 process(또는 thread)가 하나의 자원을 일관성 있게 다룰 수 있다. Dekker's Algorithm은 atomic한 명령어가 없더라도 사용할 수 있으며, busy waiting 알고리즘에 속한다. 

Dekker's Algorithm은 두 개의 process Pi, Pj 한정이며, 아래 두 개의 데이터 항목을 공유하여 해결한다.


* int turn: critical section에 진입할 순번을 나타낸다. turn == i이면 프로세스 Pi가 critical section로 진입할 수 있다.


* boolean flag[2]: 어떤 process가 critical section으로 진입을 원하는지 나타낸다.


아래 코드는 Dekker's Algorithm에서 process Pi의 구조이다.

while(true) {
    flag[i] = true;  // critical section 진입 표시
    while(flag[j]) {  // Pj가 critical section에 있는지 확인
        if(turn == j) {  // Pj가 critical section을 사용 중이면,
            flag[i] = false;  // Pi 진입 취소
            while (turn == j);  // Pj가 critical section에서 나오기를 기다림
            flag[i] = true;  // Pi 진입 다시 표시
        }
    }

    /* Critical Section */

    turn = j;  // 사용 후 Pj에게 양보
    flag[i] = false;  // critical section 사용 완료

    /* Remainder Section */
}

Solution이 올바른지 확인하려면, critical section problem 해결의 세 가지 조건을 만족해야 한다.


* Mutual Exclusion: Pi, Pj가 동시에 critical section에 진입을 원하더라도 turn의 값은 하나이므로, 하나의 process만 진입이 허용된다. 


* Progress: critical section에 진입했던 process가 exit section에서 자신의 flag를 false로 바꿈으로써 다른 process의 critical section 진입을 허용한다. (Pi가 critical section에서 나오면서 flag[i]를 false로 만드므로, Pj가 while문에서 탈출하고 critical section에 진입) 그리고 turn이 다른 process 차례라면 자신의 flag를 false로 만듦으로써 다른 process를 막지 않는다.


* Bounded Waiting: 다른 process에게 양보(turn 변수를 다른 프로세스의 값으로 설정)하므로, 한 process가 critical section에 진입했다면 다른 process가 그 다음번에 critical section에 진입하는 것이 보장된다. (Pi 진입 후에, Pj의 진입이 보장된다.)


3.2 Peterson's Solution

현대 컴퓨터 구조는 기계어를 실행하는 방식이기 때문에, 이런 구조에서 올바르게 실행된다는 보장은 없다. 하지만, critical section problem을 해결하기 위한 세 가지 조건 mutual exclusion, progress, bounded waiting을 해결하기 위한 좋은 알고리즘을 제시하므로 다룬다.

Peterson's Solution은 두 개의 process Pi, Pj 한정이며, 아래 두 개의 데이터 항목을 공유하여 해결한다. 


* int turn: critical section에 진입할 순번을 나타낸다. turn == i이면 프로세스 Pi가 critical section로 진입할 수 있다.


* boolean flag[2]: 어떤 process가 critical section으로 진입을 원하는지 나타낸다.


아래 코드는 Perterson's Solution에서 process Pi의 구조이다.

while(true) {
    flag[i] = true;  // critical section 진입 표시
    turn = j;  // Pj에게 진입 기회 양보
    while(flag[i] && turn==j);  // Pj가 진입을 시도하면 대기 아니면 진입

    /* Critical Section */

    flag[i] = false;  // critical section 사용 완료

    /* Remainder Section */
}

Pi가 critical section으로 진입하기 위해 flag[i]를 true로 만든다. 그 후 turn을 j로 지정한다. turn이 궁극적으로 어떤 process가 critical section에 진입할 지 나타내는데, Peterson's Solution은 우선 다른 process에게 순서를 양보하는 특징이 있다. Pi, Pj가 동시에 진입을 원하더라도 turn은 i, j 둘 중 하나의 값만 가질 것이다.


Solution이 올바른지 확인하려면, critical section problem 해결의 세 가지 조건을 만족해야 한다.


* Mutual Exclusion: Pi, Pj가 동시에 critical section에 진입을 원하더라도 turn의 값은 하나이므로, 하나의 process만 진입이 허용된다. 


* Progress: critical section에 진입했던 process가 exit section에서 자신의 flag를 false로 바꿈으로써 다른 process의 critical section 진입을 허용한다. (Pi가 critical section에서 나오면서 flag[i]를 FALSE로 만드므로, Pj가 while문에서 탈출하고 critical section에 진입)


* Bounded Waiting: 다른 process에게 양보(turn 변수를 다른 프로세스의 값으로 설정)하므로, 한 process가 critical section에 진입했다면 다른 process가 그 다음번에 critical section에 진입하는 것이 보장된다. (Pi 진입 후에, Pj의 진입이 보장된다.)


이때, turn 변수를 설정하는 명령어(turn = j)는 atomic 해야한다. 즉 중간에 선점되지 않는 단일 기계 명령어이다.


3.3 Lamport Bakery Solution

Dekker's Solution과 Peterson's Solution과 다르게 n개의 process(또는 thread)에 대한 처리가 가능하다. 번호를 부여받고 가장 낮은 수의 번호를 가지고 있는 process가 critical section에 진입한다. (은행 번호표) 또한, process의 고유번호가 낮을수록 먼저 도착한 process이다. 

Lamport Bakery Solution은 아래 두 개의 데이터 항목을 공유하여 해결한다. 


* isReady: process가 번호를 받았는지


* number: process의 번호 저장


아래 코드는 Lamport Bakery Solution에서 process Pi의 구조이다.

while(1) {
    isReady[i] = true;  // 번호 받을 준비
    number[i] = max(number[0~n-1]) +1  // 현재 실행 중인 프로세스 중 가장 큰 번호로 배정
    isReady[i] = false;  // 번호 발급 완료
 
    for( j =0; j < n; j++ ) {  // 모든 프로세스에 대해 번호표를 비교한다.
        while( isReady[j] );  // 비교할 프로세스가 번호표를 받을 때까지 대기
        while(number[j] && (number[j] < number[i] || j < i));
        // 프로세스 j가 번호표를 가지고 있고,
        // 프로세스 j의 번호표가 프로세스i의 번호표보다 작거나 같을 경우
        // j가 i보다 작다면(프로세스 j가 i보다 먼저 온 프로세스이면)
        // 프로세스 j의 종료(number[j]=0)까지 대기
    }

    /* Critical Section */

    number[i] = 0;  // 임계영역 사용 완료

    /* Remainder Section */
}

Solution이 올바른지 확인하려면, critical section problem 해결의 세 가지 조건을 만족해야 한다.


* Mutual Exclusion: process 중 가장 낮은 번호를 가지고 있는 것이 critical section에 진입하며, 만약 번호가 같더라도 process 고유 번호가 낮은 것이 진입한다. 따라서 하나의 process만 critical section에 진입이 허용된다.


* Progress: number가 0이면 critical section에 진입할 의사가 없다는 표시이다. 따라서 critical section이 끝나고 number를 0으로 만듦으로써 다른 process가 critical section에 진입할 수 있게 하는 것을 보장한다.


* Bounded Waiting: 먼저 번호를 발급받을수록 critical section에 먼저 진입하므로, process는 무한정 대기하지 않는다.



* 참고

Process Synchronization

https://www2.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_Synchronization.html


S/W Solution for Critical Section

http://preamtree.tistory.com/26


Dekker's Algorithm

http://itance.tistory.com/entry/%EC%83%81%ED%98%B8-%EB%B0%B0%EC%A0%9Cmutual-exclusion%EC%99%80-%EB%8D%B0%EC%BB%A4%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98


Lamport Bakery Algorithm

https://prezi.com/uil805cc777z/presentation/


'프로그래밍 > OS' 카테고리의 다른 글

Process Synchronization (mutex, semaphore)  (1) 2019.05.29
Real-Time CPU Scheduling  (0) 2018.05.20
Thread Scheduling & Multiple-Processor Scheduling  (0) 2018.05.20
Scheduling Algorithms  (0) 2018.05.16
CPU Scheduling  (0) 2018.05.15
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함