Process Synchronization 2.

게시: February 03, 2022
수정: February 04, 2022

본 포스팅은 프로세스 동기화(Process synchronization) 시 공유 데이터(Shared data)를 다룰 때 Race condition을 발생시키지 않기 위하여 필요한 중요한 개념인 Critical section에 대한 내용과 Critical section에서 발생할 수 있는 문제를 해결하는 소프트웨어적인 접근과 하드웨어적인 접근에 대한 내용을 다룬다.

Critical-Section이란?

공유 데이터에 접근하는 코드를 말하며 임계 구역이라고도 한다. 공유 데이터(Shared data) 부분이 Critical section이 아니라 공유 데이터에 접근하는 코드가 Critical section이라는 점에 주의한다.

Critical-Section Problem

프로세스가 공유 데이터에 접근하는 코드인 Critical section에 들어가 있는 상태라면 CPU를 빼앗기더라도 다른 프로세스가 공유 데이터를 수정할 수 없도록 Critical section 접근을 차단해야 한다.

반드시 Critical section에 먼저 진입한 프로세스가 빠져나왔을 때 다른 프로세스가 공유 데이터에 접근할 수 있도록 해야한다. 이를 해결하기 위한 프로그램적 해결법의 충족 조건은 다음과 같다.^[1]

1. Mutual Exclusion (상호 배제)

베타적으로 운영되야 한다. 예를 들어 프로세스 Pi 가 Critical section 부분을 수행 중이면 다른 모든 프로세스들은 자신들의 Critical section에 들어가면 안된다.

2. Progress (진행)

진행시켜야 한다. 아무도 Critical section에 있지 않은 상태에서 만약 Critical section에 들어가고자 하는 프로세스가 있으면 반드시 Critical section에 들어가게 해주어야 한다.

코드를 잘못 짜면 이 조건이 만족되지 않을 수도 있다. 예를 들어 2개의 프로세스가 동시에 들어가고자 할 때 Critical section에는 아무도 진입하지 않았음에도 불구하고 동시에 들어가려고 하는 상황 때문에 아무도 못 들어가는 상황이 발생할 수 있다.

3. Bounded Waiting (한정 대기)

기다리는 시간은 유한해야 한다. 프로세스가 Critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때 까지 다른 프로세스들이 Critical section에 들어가는 횟수에 한계가 있어야 한다.

특정 프로세스 입장에서 지나치게 오래 기다리는 Starvation 문제가 생기지 않아야 한다. 예를 들어 Critical section에 들어가려는 프로세스가 P₁, P₂, P₃ 가 있을 때 P₁, P₂ 만 Critical section에 번갈아서 들어가고 P₃ 는 계속 기다리는 상황이 발생하면 안된다.

다음은 Process synchronization 문제를 위의 조건을 만족하면서 해결하는 방법에 다가가기 위한 점진적인 시도들이다. 크게 소프트웨어적인 방법, 하드웨어적인 방법 그리고 세마포어(Semaphore)를 통한 방법이 있는데 세마포어에 대한 내용은 이번 포스팅에서 다루지 않는다.

Initial Attempt To Solve Problem

일반적인 프로세스는 Critical section인 부분과 Critical section이 아닌 부분이 반복되며 구성되어 있다고 볼 수 있다. 이를 추상화하여 표현하면 다음 코드와 같다.

do {
    entry section
    critical section
    exit section
    remainder section
} while (1);

Critical section 이전에 entry section을 두어 Lock하여 여러 프로세스가 동시에 Critical section에 접근하는 것을 차단한다. Critical section 이후에는 exit section을 두어 Critical section을 벗어나면 다른 프로세스가 Critical section에 들어갈 수 있도록 한다. 이 틀을 기본으로 한다.

Synchronization Software

Algorithm 1

Integer 타입의 동기화 변수 turn을 사용하는 모델이다. 변수 turn을 공유하고 프로세스가 자기 차례가 되면 Critical section에 들어간다. 예를 들어 turn = 0이면 P₀ 가 들어가게 되고 turn = 1이면 P₁ 이 들어간다.

즉, turn은 어느 프로세스의 차례인지 나타내는 변수이다.

다음은 프로세스 P₀ 와 P₁ 이 있을 때 P₀ 의 코드이다.

do {
    while (turn != 0); /* My turn? */
    critical section
    turn = 1;          /* Now it's your turn */
    remainder section
} while (1);

자기 차례가 아닌 P₀ 는 Critical section에 들어가기 전 while문을 계속 돌며 turn을 검사하다가 turn이 turn = 0로 바뀌면 Critical section으로 들어간다. 이 때 turn = 0은 먼저 Critical section에 들어갔다가 빠져나온 P₁ 이 변경한 것이다. 이후 P₀ 도 Critical section에서 빠져나오면 turn을 turn = 1으로 바꾸고 P₁ 이 Critical section으로 들어간다. 이 과정을 반복한다.

이 알고리즘에서는 동시에 프로세스들이 Critical section에 들아갈 수 없기 때문에 Critical section problem 해결법의 3가지 충족 조건 중 첫 번째 조건인 Mutual exclusion은 만족하지만 Critical section에 아무도 없는데도 불구하고 Critical section에 들어가지 못하는 문제가 발생한다.

예를 들어 P₀, P₁ 이 있고 P₀ 는 Critical section에 빈번히 들어가야 하지만 P₁ 은 Critical section에 단 한 번만 들어가도 된다고 가정하자.

먼저 P₀ 가 Critical section에서 작업을 하고 변수 turn을 turn = 1로 변경한다. P₁ 도 Critical section에 들어갔다 빠져나온 뒤 변수 turn을 turn = 0으로 변경한다. 이후 P₀ 가 다시 Critical section에 들어갔다가 빠져나오고 또다시 turn을 turn = 1로 바꾼다.

그런데 P₁ 은 더이상 Critical section에 들어갈 일이 없기 때문에 turn은 더이상 조작되지 않게 되며, P₀ 는 다시는 Critical section에 들어가지 못하고 계속해서 while문을 돌며 기다리게 된다.

이 알고리즘은 반드시 교대로 들어가고 나와야지만 Critical section에 들어갈 수 있는 알고리즘이기 때문에 프로세스간 Critical section 진입 빈도가 차이나는 상황에서는 Progress 조건을 만족하지 못하는 결함이 있다.

Algorithm 2

boolean 타입의 동기화 변수 flag를 사용하는 모델이다. flag는 Critical section에 들어가고 싶다는 의사를 나타내는 깃발로 각 프로세스는 flag를 갖고 있으며 처음에는 false로 초기화된다.

이 방법은 Critical section에 들어가고 싶으면 깃발을 들어서 의사를 표시하고 혹시 상대방도 깃발을 들었는지 확인한 뒤 깃발 든 프로세스가 없으면 Critical section에 들어가는 방식이다. 따라서 상대방이 깃발을 들고 있지만 않는다면 Critical section에 진입하는 빈도가 극단적으로 차이가 나더라도 얼마든지 Critical section에 들어가게 할 수 있는 알고리즘이다.

다음은 프로세스 P_i 와 P_j 가 있을 때 P_i 의 코드이다.

do {
    flag[i] = true;    /* Pretend I'm in */
    while (flag[j]);   /* Is he also in? then wait */
    critical section
    flag[i] = false;   /* I'm out now */
    remainder section
} while (1);

먼저 P_i 가 Critical section에 들어가기 위해 flag를 flag = true로 세팅한다. 그리고 상대방도 flag를 세팅했는지 확인한다. 만약 상대방 flag가 세팅되었다면 while문을 돌며 대기하고, 그렇지 않으면 Critical section에 들어간다.

Critical section에서 빠져나올 때는 flag를 flag = false로 변경하여 상대방이 기다리고 있으면 Critical section에 들어갈 수 있도록 한다.

이 방법은 Algorithm 1과 같이 Mutual exclusion 조건은 만족하지만 역시 Progress 결함이 있다.

만약 P_i 가 flag = true를 세팅하자마자 마침 CPU 할당시간이 끝났다고 가정해보자. CPU는 P_j 에게 넘어갔고 P_j 도 flag = true를 세팅하게 된다. 이러면 서로 깃발만 들고 Critical section에는 아무도 들어가지 않은 상태가 된다.

이어서 P_j 가 while문에 들어가보니 상대방도 깃발을 들고 있는 상태임을 확인하게 된다. 이렇게 되면 P_j 도 Critical section에 못 들어가고 계속 기다리다가 CPU 할당시간이 끝나게 된다.

이후 P_i 도 while문에 들어가보니 상대방이 깃발을 들고 있는 상태임을 확인하게 되고, 결국 CPU 할당 시간만 소진하면서 계속 기다리다가 CPU를 다시 빼앗기게 된다.

flag는 Critical section에 들어갔다가 빠져나올 때 flag=false로 바꾸는 것인데 두 개의 프로세스 모두 Critical section에 들어가기도 전에 깃발만 들고 CPU를 빼앗겼기 때문에 아무도 Critical section에 들어가지 못하는 문제가 발생하는 것이다.^[2]

Algorithm 3 (Peterson’s Algorithm)

turn과 flag 변수 두 가지를 모두 사용하는 알고리즘이다.
결론을 먼저 말하면 영원히 Critical section에 들어가지 못하는 문제를 해결한 알고리즘이다.

다음은 프로세스 P_i 와 P_j 가 있을 때 P_i 의 코드이다.

do {
    flag[i] = true;                /* My intention is to enter... */
    turn = j;                      /* Set to his turn */
    while (flag[j] && turn == j);  /* Wait only if... */
    critical section
    flag[i] = false
    remainder section
} while (1);

먼저 P_i 가 flag=true 세팅으로 Critical section에 들어갈 의사를 표현한 뒤 변수 turn은 상대방 turn으로 변경한다. 이후 Critical section에 들어가기 전에 상대방이 flag=true를 세팅하였는지, turn이 상대방 turn인지 검사한다. 만약 이 두 조건을 모두 만족하면 while문을 돌며 대기하고 한 조건이라도 만족하지 않으면 Critical section에 들어갈 수 있다.

즉, 상대방 차례이더라도 깃발을 들지 않았거나, 상대방이 깃발을 들고 있더라도 내 차례인 경우에는 Critical section에 들어갈 수 있다. 만약 둘 다 깃발을 들고 있더라도 네 차례인지 내 차례인지 따져서 교대로 들어갈 수 있고, 아무도 들어가 있지 않으면 그냥 차례에 관계없이 들어가면 되는 것이다.

앞선 알고리즘과 마찬가지로 Critical section에서 빠져나올 때는 다른 프로세스가 Critical section에 들어가려고 할 수 있으므로 flag를 flag=false로 변경한다.

이 알고리즘은 중간 어딘가에서 CPU를 빼앗긴다고 하더라도 Critical section problem 해결방법의 3가지 충족 조건(Mutual exclusion, Progress, Bounded waiting)을 모두 만족하는 방법이다.

그러나 이 알고리즘에도 단점은 존재한다.

Busy Waiting (또는 Spin Lock)

만약 어떤 프로세스가 이미 Critical section에 들어가 있는 상태에서 다른 프로세스가 CPU를 빼앗았다고 가정하자. 이 경우 자원을 빼앗은 프로세스는 자기 차례에서 while문을 돌며 상태를 검사한다. 하지만 이미 다른 프로세스가 Critical section에 들어가 있던 상태에서 CPU를 받은 것이기 때문에 당연히 while문을 빠져나가지 못한다.

while문에서 빠져나갈 수 있는 조건은 다시 상대방이 CPU를 잡아서 Critical section에서 빠져나가 변수를 바꿔주는 수 밖에 없다. 조건을 계속 검사한다고 상황이 바뀔리 만무하기 때문에 CPU를 빼앗았던 프로세스는 쓸데없이 while문을 돌며(Spin) CPU 할당시간만 소진하고 CPU를 반납하게 된다. 즉, 자원을 비효율적으로 쓰는 것이다.

이러한 현상을 Busy waiting(Spin lock)이라고 하며, 이 알고리즘은 Busy waiting 문제가 있다.

Synchronizaion Hardware

하나의 인스트럭션은 끝나면 언제든지 CPU 인터럽트(Interrupt)가 가능하기 때문에 중간중간 빼앗길 수 있는데, 앞선 문제들은 고급어가 여러 개의 인스트럭션(Instruction)으로 구성되기 때문에 생기는 문제들이다.

단일 인스트럭션은 실행되는 도중에 CPU가 빼앗기는 일이 발생하지 않기 때문에 만약 읽고 쓰는 것을 하드웨어적으로 하나의 인스트럭션으로 수행할 수 있으면 이러한 문제는 쉽게 극복 가능하다.

이를 지원하는 인스트럭션으로 Test & Set이 있다. Test & Set은 데이터의 현재 값을 읽어내고 값을 바꾸는 것을 하드웨어적으로 Atomic하게 처리하는 Indivisible한 인스트럭션이다.

예를 들어 a = 0이라고 가정하자. 이 때 Test_and_Set(a)를 하면 a를 읽고 값을 a = 1으로 바꾼다. 반대로 a = 1일 때 Test_and_Set(a)를 하면 a를 읽고 값은 a = 1으로 다시 세팅한다.

Test & Set은 이와 같이 원래 값을 읽어내고 그 값을 1(true)로 세팅하는 작업을 Atomic하게 처리하는 단일 인스트럭션이다. 따라서 Test & Set을 활용하면 앞선 소프트웨어적인 방법들과 같이 같이 코드를 복잡하게 구성할 필요없다. 단지 Critical section에 들어가기 전에 Test & Set으로 Lock을 걸고 빠져나올 때 Lock을 해제하는 식으로 간결하게 코드를 만들 수 있다.

boolean lock = false;

do {
    while (Test_and_Set(lock));
    critical section
    lock = false;
    remainder section
}

먼저 위의 코드와 같이 lock이라는 동기화 변수를 두고 lock = 0(false)으로 초기화한다.

이미 다른 프로세스가 Critical section에 들어가 있을 수 있으므로 들어가기 전에 lock을 체크하고 만약 Lock이 이미 걸려있으면 계속 체크한다. 비어있으면 자신이 Lock을 걸고(lock = 1(true)) 들어간다. 이때 lock을 읽고 세팅하는 작업을 Test & Set 으로 동시에 Atomic하게 실행한다.

마지막으로 Critical section에서 빠져나올 때에는 lock을 lock = false로 변경하여 다른 프로세스가 Critical section에 들어갈 수 있도록 한다.

각주

1 : 조건이 다음과 같다고 가정한다.
1) 모든 프로세스의 수행 속도는 0보다 크다.
2) 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
2 : 기계어가 아닌 고급어는 여러 개의 인스트럭션(Instruction)으로 구성되는데 하나의 인스트럭션이 끝나면 인터럽트(Interrupt)가 가능하기 때문에 이러한 문제가 발생한다.

Reference

반효경 “반효경 [운영체제] 12. Process Synchronization 1” KOCW. 2014년 4월 4일. video, http://www.kocw.net/home/cview.do?lid=5cf910642999f4a5

OS 시리즈 모두보기 (펼치기)

Twitter Facebook LinkedIn

Seungho Jeong