[운영체제] 프로세스 동기화, Race Condition, Critical Section

 

 

여러 프로세스, 스레드가 동작하다 보면 충돌이 발생할 수밖에 없다. 운영체제에서는 이러한 충돌에 대해서 해결할 수 있는 시스템을 구축해 놓았다. 

 

 

먼저 동기화를 이해하기 위한 중요한 용어부터 살펴보자.

 

 

Some Key Terms in Concurrency

 

• Race Condition
  • 멀티 프로세스나 스레드가 동시에 같은 공유 자원에 접근하는 상황
• Mutual exclusion
  • 하나의 프로세스가 공유자원을 차지하고 있으면 다른 프로세스는 접근할 수 없는 것
• Critical section
  • 공유하는 리소스에 접근하는 코드 영역이다. 따라서 다른 프로세스와 충돌이 일어날 수 있다.
  • Critical Section이 상호 배타적(mutually exclusively)이게 실행되지 않는다면, Race Condition이 발생할 수 있다.
• Starvation
  • 사전적인 의미로 굶주림이라는 뜻인데, 컴퓨터에서는 CPU가 자원을 배정해 달라고 요청했지만, 그 자원이 바로 배정되지 못하는 상황을 의미한다.
  • 이때, 기다리는 기간은 따로 지정돼있지 않지만, 보통 상황보다 오래 걸리면 Starvation이라고 한다.
• DeadLock
  • 영원히 Starvation인 상황, 즉 자원이 영원히 배정되지 않는다.
  • 이런 상황에서는 프로세스끼리는 해결할 수 없으며 컴퓨터 관리자가 해결해주어야 한다.

 

 

 

 

 

 

Difficulties of Concurrency

 

 

void echo() {
    chin = getchar();
    chout = chin; 
    putchar(chout); 
}

 

 

위와 같은 코드에서 _chin_과 _chout_이 공유 자원이라고 가정해 보자. 그리고 멀티 프로세서인 상황에서 각 CPU가 각자 하나의 프로세스를 담당한다고 생각하자.

 

 

이때, 두 프로세스 같은 코드를 실행한다. 이제 어떤 과정으로 Race Condition이 일어나는지 살펴보자.

 

 

1. 1번 프로세스가 _chin_의 상태를 1로 변경시킨다.
2. 이때 2번 프로세스가 _chin_의 상태를 2로 변경한다. 따라서 1이었던 상태가 2로 변한다.
3. 1번 프로세스가 _chout_에 _chin_의 상태를 저장한다. 이 경우 2가 저장된다.
4. 1번 프로세스는 1을 저장할 것으로 예상했으나 2가 저장된다.(Race Condition 발생)

 

 

 

 

 

 

 

Example of Race Condition

 

 

앞선 살펴보았던 예제는 여러 개의 프로세서가 있을 때의 Race Condition이 발생한 상황이다. 하지만, 프로세서가 하나여도 Race Condition은 충분히 발생할 수 있다.

 

 

Producer/Consumer 관계에서도 Race Condition이 발생하는 데 우선 어떤 방식으로 동작하는지 먼저 살펴보자.

 

 

 

 

 

 

 

 

 

 

Producer/Consumer 상황 이해

 

 

• Producer/Consumer Problem
  • 여러 개의 Producer 프로세스들과 하나의 Consumer 프로세스가 하나의 프로세서에서 돌아간다
  • Producer가 생성한 데이터를 전달하기 위해 IPC에서 Shared Memory를 사용한다고 가정하자.
  • Producer는 버퍼에 데이터를 저장하고, Consumer 프로세스가 해당 버퍼로부터 데이터를 꺼내 처리한다.

 

#define BUFFER_SIZE 10
typedef struct {
...
} item;

item b[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;

 

 

_in_은 Producer가 데이터를 집어넣을 자리이고, _out_은 Consumer가 데이터를 빼어낼 자리이다. 초기 값은 0으로 둘 다 세팅되어 있다.

 

 

버퍼는 위와 같은 방식으로 저장되어 있다. in으로 데이터가 들어오고 인덱스가 하나씩 증가하고, out으로 데이터가 빼어내지며 먼저 들어온 데이터를 먼저 처리하는 큐 방식으로 진행된다.

 

 

 

그리고 해당 버퍼를 circular방식으로 구현한다.

 

 

이때의 Producer 코드 구현은 다음과 같다.

 

item v;

while(1) {
    while(counter == BUFFER_SIZE);
    
    b[in] = v;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

 

 

_counter == BUFFER_SIZE_는 버퍼에 값이 모두 꽉 찬 경우이므로 Busy Wating 기법을 적용해 버퍼에 자리가 있을 때까지 기다리는 코드이다.

 

 

이렇게 Producer 코드가 진행되다가 Time Slice에 의해 어느 순간 Consumer의 코드로 넘어갈 것이다. Consumer 코드는 아래와 같이 구현된다.

 

item w;

while(1) {
    while(counter == 0);
    w = b[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
    /* consume item */
}

 

 

한 가지 염두해야 할 점은 counter가 감소한다고 해서 앞서 살펴본 Producer 코드의 Busy Wating이 바로 풀리는 것이 아니라는 것이다. CPU가 하나라는 것에 주목하자. 이미 Producer 프로세스에서 Consumer 프로세스로 옮겨 왔다. 따라서 Producer 프로세스는 Running상태가 아니라 Ready상태이기 때문에 이미 멈춰있다.

 

 

 

 

 

 

Producer/Consumer Race Condition

 

 

문제가 되는 Ciritical Section은 어디일까? 앞선 가정에서 Producer/Consumer가 IPC 통신으로 Shared Memory 방식을 사용함을 가정하였다. 추측할 수 있는 것은 _counter_변수이다. Producer와 Consumer 코드 모두에서 사용하기 때문이다.

 

 

실제로 Race Condition이 발생하는 곳도 _counter_변수가 쓰이는 구간이다. 따라서 해당 구간은 atomicaly mutual exclusion 하도록 만들어야 한다. 여기서 말하는 atomic 하다는 것은 하나의 operation이 다른 operation이 실행되는 동안 중단(interrupt)되지 않음을 말한다.

 

 

※ Interrupt

하드웨어가 CPU로 이벤트가 발생했음을 알리는 것이다. 여러 종류의 Interrupt가 있으나 Clock Interrupt에 대해서 알아보자.

Clock Interrupt는 1 millisecond마다 발생하며 CPU는 Clock Interrupt가 발생할 때마다 커널로 Context Switch를 해야 하는지 물어본다. 물어보는 이유는 100 millisecond마다 Time Slice에 의해서 Context Switch가 일어나야 하는데 이러한 과정을 Clock의 Interrupt를 통해 확인하기 때문이다.


기본적으로 Intterupt는 전기적인 신호이며 Interrupt가 발생하는 와중에는 정상적인 명령어의 진행이 불가능하다.

 

 

_counter_변수가 race condition이 발생하여 각 프로세스마다 예상치 못한 결과를 가져오는 흐름을 살펴보자. 정상적인 흐름에서의 _counter++_의 명령어가 가지는 어셈블리어는 다음과 같다.

 

load register, counter (register <- counter)
increment register (register <- register + 1)
store register, counter (counter <- register)

 

메모리 내의 변수 값을 레지스터로 가져와 연산을 수행한 뒤 다시 메모리의 변수로 저장한다.

 

 

_counter--_의 정상적인 흐름은 다음과 같다.

 

load register, counter (register <- counter)
decrement register (register <- register -1)
store register, counter (counter <- register)

 

마찬가지로 동작함을 알 수 있다.

 

 

자 이제 비정상적인 흐름을 한 번에 살펴보자.

 

/* producer 프로세스 */
load register, counter (register <- counter = 5)
increment register (register = 6)

/* consumer 프로세스 */
load register, counter (register <- counter = 5)
decrement register (register = 4)
store register, counter (counter <- 4; register of consumer)

/* producer 프로세스 */
store register, counter (counter <- 6; register of producer)

 

 

producer 프로세스가 명령어를 진행하는 도중에 time slice에 의해 중단되었다. 다시 말해 _count++_하는 과정 중에 끊긴 것이다. register가 6인 상태였지만 중단되었기 때문에 PCB에 해당 레지스터 값을 저장만 해 둔 채 Context Switch 해야 한다.

 

 

consumer 프로세스에서는 _counter_라는 공유 변수는 아직 5라는 상태 그대로이다. 그리고 register를 통해 정상적으로 4로 decrement 하는 데 성공했다. 따라서 consumer까지는 정상적인 상태의 흐름이다.

 

 

다시 producer 프로세스로 Context Switch 했다. 여기서 예상치 못한 상황이 발생하는데, PCB로부터 레지스터 값을 복구할 때 이전에 저장한 register 정보 값인 6을 그대로 불러온다. 즉, consumer 프로세스로 인해 _counter_값이 변경되었으나, PCB에 저장된 레지스터 값으로 인해 _counter_값이 4에서 6으로 바뀌게 돼버린다. 이러한 현상은 _count++_이라는 명령어에 전혀 부합하지 못하는 상황이다.

 

 

그러나 처음에 5였기 때문에 6으로 변하는 것은 당연한 결과 아닌가 생각할 수 있다. 다만 _counter_가 전역적으로 다뤄지는 변수임을 고려해 보자. 결과적으로 중간에 consumer 프로세스가 끼었기 때문에 _counter_값은 4에서 6으로 바뀌어버린다. 따라서 다른 프로세스들의 입장에서는 4에서 5로 바뀔 줄 알았던 _counter_값이 예상할 수 없는 6이라는 값으로 바뀐다.

 

 

정리하자면 공유되는 _counter_변수가 있는 상황에서 연산의 중간에 다른 프로세스가 끼어들었기 때문에 예상치 못한 결과를 가져오는 Race Condition이 발생했다고 할 수 있다.

 

 

 

 

 

 

 

 

Race Condition in One Process

 

당연히 여러 스레드인 경우에도 Race Condition이 발생할 수 있다. 결국 프로세스 간의 Race Condition이 발생했던 근본적인 원인은 무엇인가? 바로 _counter_라는 공유되는 변수가 존재했기 때문이 아닌가.

 

 

스레드도 마찬가지로 공유하고 있는 data 영역이 있다. 따라서 당연히 Race Condition이 발생함을 예상할 수 있다.

 

 

 

 

 

 

 

 

 

 

Race Condition 예방하기

 

 

첫 번째 방법으로는 Critial Section을 Mutual Exclusion 하게 실행한다. 이를 위해 Atomic Operation으로 실행해야 한다.

 

※ non-atomic operation

CPU가 Inttrupt Line을 체크
load register, counter
CPU가 Inttrupt Line을 체크
increment register
CPU가 Inttrupt Line을 체크
store register, counter
CPU가 Inttrupt Line을 체크
next instruction


※ atomic operation

interrupt 비활성화
load register, counter
increment register
store register, counter
interrupt 활성화
CPU가 Inttrupt Line을 체크
next instruction

 

 

그러나 이렇게 atopmic operation은 그렇게 좋은 방법이 아니다. 만약 명령어가 많은 명령문을 처리해야 할 때는 성능적으로 문제가 있을 수 있으며, 사용자가 그 기간 동안 아무런 행동을 취할 수 없다.

 

 

두 번째 방법은 critical section에 fence를 두는 것이다. 이 fence안의 명령어들은 atomic하지는 않다. 하지만 결론적으로 mutual exclusion을 보장하는데, 이는 Context Switch 되면서 fence(담장)를 닫고 나오기 때문이다.

 

 

fence가 잠긴 상태에서 Context Switch 되면 바뀐 프로세스는 바뀌기 전의 프로세스가 진행하던 critical section에서의 전역 변수를 건드리지 못한다. 따라서 코드가 그대로 진행될 수 없고, 바뀌기 이전의 프로세스가 자신의 fence안에서의 일을 전부 마친 후에 fence를 열었을 때가 되어서야 가능해진다.

 

 

주로 두 번째 방법이 선호되는 편이다. 이에 대해 조금 더 자세히 알아보자.

 

 

 

 

 

 

 

The Critical Section Problem

 

 

결국, n개의 프로세스들이 공유 자원을 두고 경쟁하는 상황이 벌어진다. 이때 Race Condition이 발생하지 않아야 한다. 앞서 Mutual Exclusion이 보장되는 두 경우를 살펴보았다. 하지만 이는 Mutual Exclusion을 보장하기 위한 논리적인 방법일 뿐이지 실질적으로 추가적인 조건이 몇 가지 더 붙는다. 따라서 Critical Sectoin Ploblem이라는 용어를 통해 그러한 조건들을 지켜야 한다는 것을 풀어내었다. Critical Section Pleblem이란 공유 자원에 접근하는 코드 영역인 Critical Section 대해서 하나의 프로세스가 이미 해당 영역에 있다면 다른 프로세스가 자신의 Critical Section에 접근하지 못하도록 하는 것을 말한다.

 

 

Critical Section Ploblem을 만족시키기 위한 조건은 다음과 같다.

 

• Mutual Exclusion
  • 하나의 프로세스가 이미 Critical Section에 있다면 다른 프로세스는 자신만의 Critical Section에 접근할 수 없다.
• Progress
  • 만약 아무런 프로세스가 Critical Section에 없다면, 임의의 프로세스는 Critical Section에 들어갈 수 있어야 한다.
• Bounded Wating
  • 하나의 프로세스가 다른 프로세스들이 Critical Section을 계속 차지함으로 인해 무한정으로 대기하는 현상이 없어야 한다.
  • 사실 상 거의 발생하지 않는다.

 

 

 

 

 

 

Software Solution

 

 

코드 영역에서 Critical Section Ploblem을 해결하기 위한 방법은 크게 3가지가 있다. 미리 말해두지만, 이렇게 소프트웨어적인 영역에서 문제를 해결하는 것은 좋지 않으며 그 이유를 함께 살펴보자.

 

 

 

 

 

 

Software Solution 1

 

 

do {
    while (turn != i) ;
    // critical section
    turn = j;
    // remainder sectoin
} while (TRUE);

 

 

첫 번째 방법은 Entry Section에 while문을 두고, turn이라는 변수를 통해 현재 fence에 접근할 수 있는지 확인하는 방법이다. 이해하기 쉽고, mutual exclusion을 지킬 수 있으나, 두 번째 조건인 Progress를 지킬 수 없다.

 

 

 

 

 

 

Software Solution 2

 

do {
    flag[i] = true;
    turn = j;
    while (flag [j] and turn == j) ;
    // critical section
    flag[i] = false;
    // remainder section
} while (TRUE);

 

 

Peterson's Algorithm이라고도 불리는 위 방식은 3개의 조건을 모주 만족한다. turn과 flag라는 변수와 배열을 두어 처리한다. 하지만 이 방식은 오직 프로세스가 두 개인 경우에서만 조건을 만족하므로 역시나 쓰이지 않는다.

 

 

 

 

 

 

 

 

Software Solution 3

 

 

do {
    choosing[i] = true;
    number[i] = max(number[0], number[1], ..., number[n-1]) + 1;
    choosing[i] = false;
    for(j = 0; j < n; j++) {
        while(choosing[j]);
        while((number[j] != 0) && (number[j], j) < (number[i], i));
    }
    // critical section
    number[i] = 0;
    // remainder section
} while (TRUE);

 

 

Bakery Algorithm이라고 불리는 위 방법은 여러 프로세스가 있어도 세 가지 조건을 만족할 수 있다. 다만, 코드만 보아도 굉장히 많고, 간단한 critical section을 수행하는 데 너무나 많은 오버헤드가 소모된다. 따라서 해당 방법도 사용하지 않는다.

 

 

결국, 소프트웨어 영역에서 critical section ploblem을 해결하기란 무리가 있다. 그래서 하드웨어를 통해서 문제를 해결해야 하는 데 이는 다음 포스팅에서 살펴보겠다.