Mutual Exclusion

May 1, 2019

1. Mutual Exclusion

병행(병렬) 프로세스에서 프로세스 하나가 공유 자원을 사용할 때, 다른 프로세스들이 해당 자원에 접근할 수 없게 하는 것 읽기 연산은 공유 데이터에 동시에 접근해도 문제되지 않으나, 변수나 파일 같은 경우 프로세스 별로 하나씩 차례로 읽거나 쓰도록 해야한다.

  • Synchronization (동기화) : 공유 자원을 동시에 사용하지 못하게 실행을 제어하는 방법
  • Critical Resource (임계 자원) : 프로세스들이 동시에 사용할 수 없는 공유 자원
  • Critical Section (임계 영역) : 임계 자원에 접근하고 실행하는 프로그램 코드 부분
  • ex) 프로세스가 공통 변수를 읽고, 테이블을 갱신하고, 파일을 수정하는 등 공유 데이터에 접근할 때 임계 영역에 있다고 한다.
  • 상호 배제의 조건
    1. 두 프로세스는 동시에 공유 자원에 진입할 수 없다.
    2. 프로세스의 속도나 프로세서 수에 영향을 받지 않는다.
    3. 공유 자원을 사용하는 프로세스만 다른 프로세스를 차단할 수 있다.
    4. 프로세스가 공유 자원을 사용하기 위해 너무 오래 기다려서는 안 된다.

(1) Critical Section

do {
    while (turn != i); // 진입 영역
    /* 임계 영역 */
    turn = j; // 탈출 영역
    /* 나머지 영역 */
}

위 코드처럼 어떤 프로세스가 임계 영역에 진입할 수 있는지 확인하기 위한 동작과 다른 프로세스의 사용을 금지하는 동작을 통해 임계 영역을 이용한 상호배제를 구현할 수 있다.

  • 단일 머신 사이클에서만 가능하다.
  • 임계 영역을 이용한 상호배제의 세 가지 조건
    1. 상호배제 : 어떤 프로세스가 임계 영역에서 작업 중이면 다른 프로세스는 임계 영역으로 들어갈 수 없다.
    2. 진행 : 임계 영역에 프로세스가 없는 상태에서 여러 프로세스가 들어가려고 할 때는 어떤 프로세스가 들어갈 지 적절히 결정해야 한다.
    3. 한정 대기 : 다른 프로세스가 임계 영역을 무한정 기다리는 상황을 방지하려면 임계 영역에 한번 들어갔던 프로세스는 다음에 임계 영역에 다시 들어갈 때 제한을 둔다.

(2) 생산자와 소비자 문제

운영체제에서 비동기적으로 수행하는 모델로, 생산자 프로세스가 생산한 정보를 소비자 프로세스가 소비하는 형태

  • 생산자는 소비자에게 데이터를 전송할 때, 소비자가 받을 준비가 되면 데이터를 전송하고 소비자가 계속 처리하지 못하면 대기해야 한다.
  • 이 때, 생산자와 소비자가 불필요하게 공회전하지 않도록 데이터를 전송하려면 임시 기억장소인 버퍼를 도입하여 해결할 수 있다.
  • 그러나, 버퍼에도 두 가지 문제점이 존재한다.
    • 버퍼의 크기가 유한할 때, 이미 가득찬 버퍼에 생산자가 데이터를 더 채우려 하는 경우
    • 빈 버퍼에서 소비자가 데이터를 꺼내려 하는 경우
  • 버퍼의 크기가 무한하다면, 소비자가 빈 버퍼에서 데이터를 꺼내려 하는 경우를 따로 처리해주면 된다.
  • 버퍼의 크기가 유한하다면, 아래 코드와 같이 논리적 포인터 2개로 버퍼를 순환 배열로 구현하여 해결할 수 있다. 
    • #define BUFFER_SIZE 10
typedef struct {
    DATA data;
} item;
item buffer[BUFFER_SIZE];
int in = 0, out = 0, counter = 0;
// 생산자 프로세스
item nextProduced;
while (true) {
    while (couter == BUFFER_SIZE);
    buffer[in] = nextProduced;
    in = (in + 1) % BUFFER_SIZE;
    counter++; // 임계 영역 설정 필요
}
// 소비자 프로세스
item nextConsumed;
while (true) {
    while (counter == 0);
    nextConsumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--; // 임계 영역 설정 필요
}

      그러나 위의 생산자 프로세스와 소비자 프로세스 코드를 동시에 수행하면 counter++과 counter–의 어셈블리어의 수행 순서에 따라 의도치 않은 결과를 낳을 수 있다.

  • 위의 예제처럼 여러 프로세스가 동시에 공유 데이터에 접근할 때 접근 순서에 따라 실행 결과가 달라지는 상황에 놓은 프로세스들을 경쟁 상태 (Race Condition)에 있다고 한다.
  • 때문에 프로세스들의 경쟁 상태를 예방하기 위해서는 병행 프로세스들을 동기화해야 한다.
  • 이 때, 임계 영역을 이용한 상호배제를 통해 동기화할 수 있다. -> 공유 변수 counter를 한 순간에 하나의 프로세스만 조작할 수 있도록 counter++과 counter– 부분을 임계영역으로 설정해야 한다.

! 상호배제의 방법에는 크게 두 가지가 있다.

  • 소프트웨어로 해결하는 방법
    • 알고리즘으로 해결
      • 데커의 알고리즘, 크누스의 알고리즘, 램포트의 베이커리 알고리즘, 핸슨의 알고리즘, 다익스트라의 알고리즘
    • 프로그래밍 언어와 운영체제 수준에서 제공 : 세마포, 모니터
  • 하드웨어로 해결(저급 수준의 원자 연산)하는 방법

자세한 내용을 다루기 위해 여러 개의 포스팅으로 나누어 올리도록 하겠습니다.