Skip to content
Beside the Wheel

임계영역과 상호배제

OS
process

임계 영역(Critical Section)

  • 공유자원에 접근하는 프로세스 내부의 코드 영역으로 어떤 한 프로세스가 한 영역의 데이터를 사용하고 있을 때, 다른 프로세스가 그 영역의 데이터를 같이 사용한다면 코드상에서 문제가 발생할 수 있다.

  • 따라서 문제가 발생하지 않도록 특정 영역 내의 한번에 하나의 프로세스만 이용하게끔 보장해야해한다. 그러한 영역을 임계영역이라고 부든다.

  • 임계 영역의 문제를 해결하기 위해서는 아래 3가지 조건을 충족해야 한다.

  • 상호배제

    • 하나의 프로세스가 임계 영역에 들어가있다면 다른 프로세스는 들어갈 수 없어야 한다.

  • 진행

    • 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러개라면 어느 것이 들어갈지 결정해주어야 한다.

  • 한정 대기

    • 다른 프로세스의 기아를 방지하기 위해, 한 번 임계 영역에 들어간 프로세스는 다음번 임계 영역에 들어갈 때 제한을 두어야 한다.

  • 임계 영역의 동시접근을 해결하기 위한 방법으로 뮤텍스 (Mutex), 세마포어(semaphore), 모니터(monitor)등이 있다.

뮤텍스 (Mutex, 상호배제)

  • 다른 프로세스 간 동기화에 사용된다.
  • 임계 구역에 단 하나의 스레드만 접근 가능하다.
  • 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 사용한다. 한 스레드가 임계영역에 들어가기 위해서 lock을 하고, 나올 땐 unlock을 한다.
  • priority inheritence의 특성을 가진다. (mutex를 가진, 즉 잠금을 건 프로세스를 우선적으로 실행하여 락을 빨리 풀 수 있도록 함)

뮤텍스 알고리즘

1. 데커(Dekker) 알고리즘

flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식이다.

  • flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
  • turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수
while (true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while (flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}


// ------- 임계 구역 ---------


turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

2. 피터슨(Peterson) 알고리즘

데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있다.

while (true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while (flag[j] && turn == j) { } // 다른 프로세스가 진입 시도하면 대기
}


// ------- 임계 구역 ---------


flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

3. Lamport’s bakery algorithm

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘.

가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while (true) {


    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의 번호표
    }
}


// ------- 임계 구역 ---------


number[i] = 0; // 임계 구역 사용 종료

세마포어 (Semaphore)

  • 뮤텍스가 임계 영역에 들어가는 스레드가 하나라면, 세마포어는 복수개가 가능하다.
  • wait과 signal을 통해 구현된다.
  • wait이 먼저 호출되어 임계영역에 들어갈 수 있는지 확인 or 먼저 실행되어야 하는 프로세스가 실행되는지 확인
  • 조건에 만족하면 wait을 빠져나와 임계영역으로 들어간다.
  • 이후 signal이 호출되어 임계영역에서 빠져나왔음을 알린다.

뮤텍스와 세마포어의 차이

  • 세마포어는 자원의 상태를 나타내는 일종의 ‘변수’로써 소유 개념이 아니지만, 뮤텍스는 자원을 점유한 프로세스나 쓰레드가 잠시 소유하였다가 작업이 끝나면 반환하는 개념이다.
  • 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
  • 세마포어는 시스템 범위에 걸쳐있고 파일 시스템 상의 파일 형태로 존재한다. 반면, 뮤텍스는 프로세스 범위를 가지고, 프로그램이 종료될 때 자동으로 지워진다.
  • 세마포어는 동기화 대상이 여러개일 때, 뮤텍스는 동기화 대상이 오로지 하나일때 사용된다.

모니터 (Monitor)

  • 하나의 프로세스 내의 다른 스레드 간 동기화에 사용된다. (뮤텍스는 다른 프로세스간의 동기화)

  • 모니터 큐에 작업을 쌓아놓고 한번에 하나의 프로세스만 임계영역에 접근할 수 있도록 한다.

    • 모니터만을 통해 데이터에 접근할 수 있는 것이다.

  • 다른 방법들보다 구현체가 더 자세히 정의되어있다.

    • wait: 자기 자신 큐에 넣고 대기
    • signal: 대기중인 스레드 하나를 깨움
    • brodcast: 모두를 깨움

  • Java에는 모니터를 사용한 일련의 동기화 작업들이 캡슐화되어 있어서 synchronized, wait(), notify()등의 키워드와 함수를 통해 편하게 사용할 수 있다. 함수 앞에 synchronized를 붙여주기만 하면 함수의 작업을 상호배제하며 수행한다.

구현

  • 모니터는 세마포어를 활용해 구현할 수 있다.

  • x.wait()은 아래와 같이 구현할 수 있다.

    semaphore x_sem; // (initially = 0)
    int x_count = 0; // number of process waiting on condition (x)
    

    /*
    * This is used to indicate that some process is issuing a wait on the
    * condition x, so in case some process has sent a signal x.signal()
    * without no process is waiting on condition x the signal will be lost signal (has no effect).
    */
    x_count++;
    

    /*
    *  if there is some process waiting on the ready queue,
    *  signal(next) will increase the semaphore internal counter so other processes can take the monitor.
    */
    if (next_count > 0)
        signal(next);
    /*
    *  Otherwise, no process is waiting.
    *  signal(mutex) will release the mutex.
    */
    else
        signal(mutex);
    /*
    * now the process that called x.wait() will be blocked until other process will release (signal) the
    * x_sem semaphore: signal(x_sem)
    */
    wait(x_sem);
    // process is back from blocking.
    // we are done, decrease x_count.
    x_count--;

  • x.signal()은 아래와 같이 구현할 수 있다.

    // if there are processes waiting on condition x.
    if (x_count > 0) {
        // increase the next count as new blocked process has entered the queue (the one who called x.wait()). remember (wait(x_sem))
        next_count++;
        // release x_sem so the process waiting on x condition resume.
        signal(x_sem);
        // wait until next process is done.
        wait(next);
        // we are done.
        next_count--;
    }

참고

관련글
processTASprocess교착상태와 스케줄링process생산자 소비자 문제process프로세스의 개념process프로세스의 관리vmVMware Fusion NAT config