운영체제 | 프로세스 동기화

컴퓨터의 프로세스 중에서 협력적 프로세스 는 실행 중인 다른 프로세스의 실행에 영향을 주거나 받는 프로세스입니다. 이러한 협력적 프로세스는 논리주소 공간을 직접 공유하거나, 파일 또는 메세지를 통해서만 데이터를 공유할 수 있습니다. 이 경우 두개 이상의 프로세스가 동시에 특정 데이터에 접근하면 데이터가 비일관성을 가지게 될 수 있습니다. 본 강의에서는 이렇한 논리주소 공간을 공유하는 협력적 프로세스의 질서있는 실행을 보장하여 데이터의 일관성을 유지 하는 다양한 메커니즘을 다루어 보겠습니다.

두개의 프로세스가 동일한 공유된 변수에 접근하는 프로그램을 동작시킨다면 어떤 프로세스가 어떤 순서로 동작함에 따라 결과가 달라지게 됩니다. 하지만 두 프로세스가 비동기적으로 실행되는 경우 실제로 변수가 어떻게 변화하게 되는지 부정확해지는 일이 생기게 됩니다. 이런 문제는 두개의 프로세스가 동시에 같은 변수에 접근 하기 때문입니다.

여러 개의 프로세스가 동일한 자료를 접근하여 조작하고 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 조건 이라고 합니다. 이를 해결하기 위해서는 한 순간에 하나의 프로세스만이 공유 변수를 조작하도록 보장해야 합니다.

임계영역 문제(The Critical Section Problem)

여러 개의 프로세스가 동작하는 처리기를 생각해 봅시다. 각 프로세스는 임계영역(Critical Section) 이라고 부르는 코드 부분을 가지고 있으며, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나, 테이블을 갱신하거나 파일을 쓰거나 하는 등의 작업을 실행합니다. 각 프로세스는 자신의 임계영역으로 진입하려면 진입허가를 요청해야 한다. 이러한 요청을 구현하는 코드 부분을 진입 영역(entry section) 이라고 부르며 임계영역 뒤를 퇴출영역(exit section) 이 따라올 수 있고, 코드의 나머지 부분을 통틀어 나머지 영역 이라고 부릅니다.

이러한 임계영역 문제를 해결하기 위해 서는 다음의 세 가지 요구 조건 을 충족해야 합니다.

1. 상호 배제(mutual exclusion)
   프로세스 P가 자신의 임계영역에서 실행되고 있다면, 다른 프로세스들은 그들 자신의 임계영역에서 실행될 수 없습니다.
   즉, A라는 프로세스가 자신의 임계영역에서 실행되고 있다면, 프로세스 B는 자신의 임계영역에서 실행될 수 없습니다.
2. 진행(Progress)
   자신의 임계영역에서 실행 중인 프로세스가 없는 상태에서 자신의 임계영역으로 진입하려고 하는 프로세스가 있다면, 나머지 영역에서 실행 중이지 않은 프로세스들만 임계영역으로 진입할 프로레스를 결정하는데 참여할 수 없으며, 이 선택은 무한정 연기될 수 없습니다.
   가령, A, B, C 라는 프로세스가 모두 자신의 임계영역에서 실행되고 있지 않은데 프로세스 A가 자신의 임계영역으로 진입하려고 한다면, 반드시 A는 나머지 영역 에서 실행중이지 않아야 하며, 유한한 시간 내에 임계영역으로 진입하고자 하는 프로세스를 선택해야 합니다.
3. 한정된 대기
   프로세스가 자기의 임계영역에 진입하려는 요청을 한 뒤 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계영역에 진입할 수 있는 횟수에 제한이 있어야 합니다.
   예를 들어, 프로세스 A, B, C 가 있을 때 프로세스 A가 자신의 임계영역으로 진입하려고 진입 영역 에서 요청을 한 뒤 실제로 임계영역에 진입하기 전까지는 프로세스 B, 프로세스 C 가 임계영역에서 무한히 많이 진입하도록 되어서는 안되고 몇번 진입 후에는 반드시 프로세스 A에게 진입 할 순차가 와서, 프로세스 A가 한정된 대기를 해야 합니다.

운영체제에서 임계영역을 다룰 때는 두가지 상황을 고려해야 합니다.
바로, 선점형 커널 인가 혹은 비선점형 커널 인가에 대한 문제입니다.

선점형 커널 은 프로세스가 커널 모드에서 실행되는 동안 선점되는 것을 허용하며, 비선점 커널 은 커널 모드에서 실행되는 프로세스의 선점을 허용하지 않고, 커널을 빠져나갈 때까지 또는 봉쇄될 때까지 또는 자발적으로 CPU의 제어를 양보할 때까지 계속 실행됩니다.
비선점형 커널 의 경우에는 커널 안에서 실행중인 프로세스가 명백하게 하나 밖에 없기 때문에 경쟁조건을 걱정하지 않아도 되지만, 선점형 커널 의 경우는 그렇지 않기 때문에 경쟁 조건이 발생하지 않는 것을 보장할 수 없습니다.

특히, SMP(Symmetric Multi-Processing) 구조에서는 서로 다른 처리기의 두 프로세스가 동시에 커널 모드에 있을 수 있기 때문에, 선점형 커널을 설계하는 것은 특히 어렵습니다.

피터슨의 해결방안

이러한 임계영역 문제 에 대한 고전적인 소프트웨어 기반 해결책인 피터슨의 해결안 에 대해 알아봅시다.

피터슨의 해결안은 임계영역과 나머지 영역을 번갈아 가며 실행하는 두 개의 프로세스로 한정됩니다.
쉽게 말하면 두 개의 프로세스를 구현할 때 특정 변수를 인덱스 값으로 놓아 해당 변수가 임계영역 에 대한 접근의 승낙여부를 공유하는 것입니다.
이를 위해서 다음과 같이 두개의 데이터 항목을 공유합니다.

int turn;
boolean flag[2]; //프로세스가 임계영역으로 진입할 준비가 됨을 나타냅니다.

위에서 turn 변수 는 임계영역으로 진입할 순번을 나타냅니다. 가령 turn이 i 이면 프로세스 i가 임계영역에서 실행되는 것을 나타냅니다.
flag 변수 는 프로세스가 임계영역으로 집입할 준비가 되었다는 것을 나타냅니다. 가령 flag[i]가 true 라면 프로세스 i가 임계영역으로 들어갈 준비가 되었다는 것을 나타냅니다.

이렇게 동일한 변수를 공유하면 turn에 동시에 접근이 되더라도 하나의 값만을 나타내기 때문에 바로 다음에 접근한 값에 의해 덮어 씌워지게 되어 둘 중 하나의 값만이 될 것입니다.

위의 공유변수를 이용한 피터슨의 해결방안을 코드로 보이면 다음과 같습니다.

while(true){
  flag[i] = TRUE;
  turn = j;
  while(flag[j] && turn ==j){
    임계영역 코드
  }

  flag[i] = FALSE;
  나머지 영역
}

위 코드는 프로세스 i가 임계영역에 접근하고자 하는 코드입니다. 위에서 flag[i]를 true로 지정함으로써 프로세스 i가 임계영역에 진입하고자 하는 것을 나타냅니다. 하지만 프로세스 i는 임계영역에 진입하기에 앞서 프로세스 j에게 먼저 입계영역에 접근하고 싶으면 접근하도록 turn을 돌려 줍니다. 만약 flag[j] 가 true 즉, 프로세스 j가 임계영역에 진입하고자 했다면 먼저 진입할 수 있습니다.

동기화 하드웨어

앞에서는 임계영역 문제에 대한 소프트웨어 기반의 해결책을 살펴보았다. 하지만 일반적으로 임계영역의 문제는 록(lock) 이라는 간단한 도구가 필요하다고 말할 수 있다. 경쟁 조건은 임계영역에서 록에 의해 보호함으로써 예방할 수 있습니다. 즉, 프로세스가 임계영역에 진입하기 전에 반드시 록 을 획득하도록 함으로써 임계영역 문제를 해결할 수 있습니다.

이를 간단히 코드로 표현하면 다음과 같습니다.

while(true){
  록 획득
    //임계영역
  록 방출
    //나머지 영역
}

위처럼 임계영역에 진입하기 전에 록을 획득 하고 임계영역을 나오면서 록을 방출 하는 방식을 잘 보여주고 있습니다.

이러한 임계영역의 문제에 대한 해결은 단일처리기 환경 혹은 다중 처리기 환경이냐에 따라 간단하거나 복잡할 수 있습니다.
만약 단일 처리기 환경 이라면 임계영역 문제는 쉽게 해결될 것입니다. 공유 변수가 변경되는 동안에는 하나의 프로세스가 진행되는 것을 막는 인터럽트 의 발생을 허용하지 않는 것이지요. 이렇게 하면 공유 변수가 변경되는 동안에는 인터럽트가 발생하지 않고 해당 프로세스는 방행 없이 자신의 코드를 실행시킬 것 입니다.
반면, 다중 처리기 환경 에서는 이것이 불가능 합니다. 다중 처리기에서 인터럽트를 막기 위해서는 모든 처리기에 인터럽트를 금지시키도록 해야 하는데 이것은 상당한 시간을 소비하기 때문이지요.

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

즉, swap을 통해 여러 처리기의 공유 변수를 원자적으로 변경시켜 록 을 획득하는 것 입니다.

세마포

위에서 제시한 하드웨어 기반의 해결방법은 응용 프로그래머가 사용하기에는 매우 복잡하기에 이를 극복하기 위해 세마포 라고 하는 동기화 도구를 이용할 수 있습니다. 세마포 S는 정수 변수를 포함하며 초기화를 제외하고는 오직 두개의 표준 연산 acquire(), release() 로만 접근이 가능합니다.

이러한 세마포의 간단한 구현은 다음과 같습니다.

acquire(){
  while(value<=0){
    아무런 작업 하지 않음
  }
  value--;
}

release(){
  value++
}

위 코드를 분석해 봅시다.
먼저 세마포는 임계 영역에 진입하기 위해 acquire() 를 호출합니다. 하지만 이 경우 누군가가 먼저 acquire를 호출하여 value의 값이 0보다 작다면 아무런 작업도 하지 않고 대기합니다. 그러다가 다른 세마포가 release()를 호출하여 value값을 증가시켜 주면 while 문에서 벗어나고 또 다른 acquire() 요청을 막기 위해 value를 줄여 줍니다.

하지만, 여기서는 치명적인 문제가 있습니다.
바로 while 문에서 value를 검사하면서 바쁜 대기(busy waiting) 을 하고 있는 것이죠. 한 프로세스가 임계영역에 있으면, 자신의 임계영역에 진입하려는 다른 프로세스는 진입 코드를 계속 반복 실행해야 합니다. 이러한 현상을 프로세스가 록 을 기다리면서 회전한다고 하여 spinlock이라고 부르기도 합니다.

어떻게 하면 이런 바쁜대기(busy waiting) 을 없앨 수 있을까요?
바로 바쁜 대기를 하는 대신에 자기 자신을 봉쇄시키는 방법이 있습니다. 봉쇄 연산은 프로세스를 세마포에 연관된 대기 큐 에 넣고, 프로세스를 대기상태로 전환 합니다. 그 후에 제어가 CPU로 넘어가게 되고 추후 다른 프로세스가 release()연산을 실행하면 wakeup() 연산을 통해 재시작 됩니다. 이런 wakeup() 명령은 프로세스의 상태를 대기상태에서 준비완료 상태로 변경합니다. 그 뒤 wakeup 된 프로세스는 준비완료 큐에 넣어지게 됩니다.

이러한 block, wakeup 을 구현하기 위해 우리는 세마포를 한 개의 정수 value와 프로세스 리스트로 정의합니다. 프로세스를 기다려야 한다면 이 프로세스는 그 세마포의 프로세스 리스트에 추가됩니다. release() 연산은 프로세스 리스트에서 한 프로세스를 제거하여 그 프로세스를 깨워줍니다.

이를 구현한 코드는 다음과 같습니다.

acquire(){
  value--;
  if(value<0){
    block();
  }
}

release(){
  value++;
  if(value<=0){
    wakeup(P);
  }
}

위 코드에서 block() 연산은 자기를 호출한 프로세스를 보류시키고, wakeup(P) 연산은 봉쇄된 프로세스 P의 실행을 재개시키며, 이들 두 연산은 운영체제의 기본적인 시스템 호출 로 제공됩니다.

---