빽 투더 기본기 [OS 4편]. 동기화와 Peterson' 알고리즘

이 글에서는 운영체제의 기초가 되는, Synchronization(동기화) 에 대해 정리해본다.

1. 동기화(Synchronization) 의 필요성

1.1. Shared data 와 Data inconsistency

먼저 동기화(Synchronization) 는 멀티 프로세스 혹은 멀티 쓰레드 상황에서의 이슈이다.
여러 개의 프로세스, 혹은 쓰레드가 공유된 자원, 데이터를 사용하는 경우, 스케쥴링 시스템에 의해 데이터의 일관성(Data Consistency) 를 지키지 못하는 경우가 생기는데, 이게 바로 문제다.

예를 들어, 내가 내 계좌에 1000원이 있다고 하자.
내가 500원을 출금하려고 하는 동시에, 친구가 내 계좌로 500원을 송금했다면, 내 잔고는 당연히 1000원이 있어야 맞다. 이 때 출금과 송금은 각각 독립된 다른 프로세스 혹은 쓰레드고, 이 두 개의 순서가 혼동된다면 잔고는 500원 혹은 1500원과 같은 결과를 내게 된다.
위와 같이, 공유 자원, 데이터에 대해 여러 개의 프로세스, 혹은 쓰레드가 동시에 접근해 문제를 야기할 수 있는 상황을 경쟁 상황(Race Condition) 이라한다.

즉, 데이터의 일관성을 위해, 멀티 프로세스 & 쓰레드 환경에서 접근체계를 조정해서 프로그램을 짜야하는데, 이를 동기화라고 한다.

1.2. 용어 정리

동기화를 위해, 하나의 프로세스 혹은 쓰레드가 공유 자원에 대한 작업이 완료될 때까지, 다른 프로세스, 쓰레드의 방해없이 완전하게 완료가 되어야 하는데, 이렇게 진행되는 원칙을 상호배재(Mutual Exclusion) 라고 하고, 이렇게 수행되는 연산들을 Atomic Operation 이라 한다. 또, 이렇게 공유자원에 대해 동기화해야하는 코드 부분을 임계 영역(Critical Section) 이라고 한다.

1.3. Critical Section 의 속성

임계 영역의 문제를 해결하기 위해서는 다음을 만족해야 한다.

1. 상호배재 (Mutual Exclusion)
   어떤 프로세스가 임계 영역을 실행하고 있을 때, 다른 프로세스는 임계 영역을 실행할 수 없다.
   즉, 어떤 프로세스가 임계 영역을 실행할 때, 다른 프로세스는 코드 실행을 못하게 처리해줘야 한다.

2. 진행 (Progress)
   임계 영역에 실행되고 있는 프로세스가 없을 경우, 임계 영역을 실행하고자 기다리는 프로세스는 즉각적으로 임계 영역을 실행할 수 있어야 한다. 즉, 기다리고 있는 프로세스들에 대한 처리를 해줘야 한다.

3. 한정 대기 (Bounded Waiting)
   임계 영역을 실행하고자 하는 프로세스가 무한정으로 대기하면 안된다. 즉, 제한된 대기시간을 가져야 한다.

2. 동기화 방법

2.1. Peterson's Algorithm

2가지 프로세스 P0, P1 가 공유 자원을 사용하는 상황을 가정하고, 알고리즘을 진행한다.
먼저 코드만 보면 다음과 같다. (파이썬식 수도코드로 작성)

전역변수 flag, turn 설정

flag = [False, False]
turn = 0

프로세스 P0

P0:
flag[0] = True
turn = 1

  while flag[1] and turn == 1:
    pass
    
  # 임계구역

  flag[0] = False

프로세스 P1

P1:
flag[1] = True
turn = 0

  while flag[0] and turn == 0:
    pass
    
  # 임계구역
    
  flag[1] = False

먼저, 이 알고리즘에서는 flag 와 turn 이라는 전역변수를 사용해서, 3가지 조건(상호 배제, 진행, 한정 대기) 를 만족시킨다.

flag[i] 의 의미는, i 번째 프로세스가 임계영역을 사용하겠다고 알리는 것이다. 즉, 임계 영역을 사용할 프로세스들은 모두 flag[i] = True 가 된다.

turn 은 어떤 프로세스를 실행시킬건지 가르키는 변수다. 코드를 보면, turn 은 가장 나중에 임계 영역에 들어가기 전, 가장 나중에 실행되는 프로세스에 의해 값이 결정된다. 즉 flag 를 통해서 둘 다 동시에 임계 영역 직전까지 오더라도, turn 값을 어떤 프로세스가 최종적으로 바꾸느냐에 따라서, 실행순서가 결정된다.

조금 많이 헷갈릴 수 있는데, 위 같은 발상은 사실 아래의 2가지 더 단순한 알고리즘(솔루션1, 솔루션2) 을 합친 것이다.

출처 : Two Process Solution 3 Different Solutions (Turn, Flag, Peterson’s Solution) with Explanation

위 그림을 하나씩 살펴보자.

솔루션 1은

• turn 만 사용한다.
  이 때 turn 값은, 실행되는 순서인데, turn = 0 이면, P0 부터 실행된다는 의미다.
• P0 이 임계 영역을 점유하는 동안 turn = 0 기 때문에, 다른 프로세스들은 임계 영역 직전 무한루프를 돈다.
• 그러다, 임계 영역을 빠져나오면, 해당 프로세스는 turn 값을 다음에 실행될 프로세스 번호 (1) 로 바꾼다.
  이제, P1 은 turn = 1이 되었기 때문에 무한루프를 나오고, 임계 영역에 들어갈 수 있게 된다.
• 하지만, P0 이 임계 영역을 나왔음에도, P1 이 바로 임계 영역을 들어갈 수가 없는 코드이므로, 진행(Progress) 조건에 부합하지 못한 알고리즘이다. (사실 나는 이게 아직 무슨 말인지 잘 모르겠다.)

솔루션 2는,

• flag[i] 만 사용한다.

  flag[i] 는 모두 False 로 초기화해둔다.
  마찬가지로, flag[0] = True 이면, P0 이 임계 영역을 점유하겠음을 알리는 것이다.

• P1 입장에서는 flag[0] 이 True 인지 검사하고, 이 값에 따라 다른 프로세스가 점유 중인지 아닌지 알 수 있다.

• 임계 영역을 나온 P0 은 flag[0] = False 로 바꿔, 임계 영역을 나왔음을 알린다.

• 하지만, 이 알고리즘은 flag[0] 과 flag[1] 이 동시에 True 가 되는 경우, deadlock 문제가 발생하므로, 치명적인 문제가 있다.

Peterson' s Algorithm 은 위 두 솔루션을 믹스한 알고리즘인 셈이다.
직관적으로 이해가 가지 않는다면, 하나씩 하나씩 발생할 수 있는 상황을 대입해보면 된다.
놀랍게도, 문제가 발생하지 않는다.

하지만 이 알고리즘도 역시 또다른 문제점을 가지고 있는데, 바로 다음 부분이다.

while flag[0] and turn == 0:
  pass

CPU 스케쥴링에 의해, 각 프로세스가 진행된다. 이 때, 임계 영역에 들어가기 위해 기다리고 있는 프로세스는 위 코드에 의해 무한루프를 돌며 임계 영역 직전에 머무르게 되는데, 이 무한 루프에 CPU 자원을 쓰고 있는 것이다. 운영체제의 목표는 CPU를 효율적으로 활용하는 것이므로, 이러한 현상도 문제라고 본다. 이러한 문제를 Busy waiting 이라고 한다.

참고

• https://thinkpro.tistory.com/124

• 피터슨의 풀이(Peterson's Solution)http://blog.naver.com/lighting12)

• Two Process Solution | 3 Different Solutions (Turn, Flag, Peterson’s Solution) with Explanation

• Part 5.6 Peterson Solution Operating System in HINDI | Dekker's Algorithm in OS Critical Section

• https://ko.wikipedia.org/wiki/피터슨의_알고리즘