프로세스 동기화(Process synchronization)
프로세스 동기화(Process synchronization)란 말 그대로 프로세스 사이의 동기화를 말한다. 현재는 대부분 스레드 기준으로 문맥 교환(Context switching)이 일어나므로 스레드 동기화라고도 한다.
프로세스 동기화는 여러 프로세스가 공유하는 자원의 일관성을 유지하는 것이며, 이에 대해 이해하기 위해서는 '경쟁 상태'와 '임계 구역'의 개념을 먼저 이해해야 한다.
경쟁 상태(Race condition)
경쟁 상태는 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 데이터에 접근하는 순서에 따라 결괏값이 달라질 수 있는 상황을 말한다. 공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있으며, 이를 방지하기 위해 협력 프로세스 간의 실행 순서를 정해주는 매커니즘이 바로 동기화인 것이다.
경쟁 상태가 발생하는 경우는 크게 다음과 같은 세 가지 경우로 나눌 수 있다.
-
커널 모드로 수행 중에 인터럽트가 발생하는 경우
의도된 동작은 count--와 count++이 모두 반영되어 초깃값을 유지하는 것이지만, load 후에 인터럽트가 발생하는 경우 인터럽트의 결과는 반영되지 않고 count++만 반영된다.
이는 커널 모드의 수행이 끝나기 전에는 인터럽트가 발생하지 않도록 하는 방법으로 해결할 수 있다. -
프로세스가 시스템 콜을 호출해 커널 모드로 수행 중인데 문맥 교환이 발생하는 경우
두 프로세스의 주소 공간에서는 데이터를 공유하지 않지만, 시스템 콜을 수행하는 동안에는 두 프로세스 모두 커널 주소 공간의 데이터에 접근할 수 있다. 따라서 커널 주소 공간에서 작업을 수행하는 도중 CPU 자원을 빼앗기면 경쟁 상태가 발생하게 된다.
이는 커널 모드 수행 중에는 CPU가 preempt되지 않도록 하고, 커널 모드에서 유저 모드로 돌아갈 때 preempt되도록 하여 해결 가능하다.preempt는' 선점하다'라는 의미로, 말 그대로 다른 프로세스가 사용하고 있는 CPU를 빼앗는 것을 의미한다.
-
멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우
이 경우에는 어떤 CPU의 작업이 저장되었는지에 따라 결괏값이 달라진다. 싱글 프로세서와 달리 멀티 프로세서에서는 인터럽트를 disable하는 방법으로는 이를 해결할 수 없으며, 한 번에 하나의 CPI만 커널에 들어갈 수 있도록 하는 방법도 매우 비효율적이다(두 프로세스가 서로 다른 데이터에 접근하여 경쟁 상태의 가능성이 없는 경우도 있으므로).
따라서 이는 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대해서만 lock을 거는 방식으로 해결할 수 있다.
임계 구역(Critical Section)
임계 구역은 코드상에서 앞서 살펴본 경쟁 상태가 발생할 수 있는 특정 부분을 말한다. 즉, 공유 데이터에 접근하는 코드 부분을 지칭하는 말이다.
이러한 임계 구역으로 인해 발생하는 문제들을 해결하기 위한 조건들은 다음과 같이 정리할 수 있다.
- 상호 배제(Mutual exclusion)
하나의 프로세스가 임계 구역에서 작업 중인 경우 다른 모든 프로세스는 임계 구역에 진입해선 안 된다. - 진행(Progress)
임계 구역에서 작업 중인 프로세스가 없다면 여기에 진입하고자 하는 프로세스가 있을 경우 진입이 가능해야 한다. - 한정 대기(Bounded waiting)
프로세스가 임계 구역에 들어가기 위해 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 임계 구역에 들어가는 횟수에는 한계가 있어야 한다. 즉, 요청한 프로세스가 무한정 기다려서는 안 된다.
동기화 알고리즘(Synchronization algorithms)
Algorithm 1
- 현재 임계 구역에 들어갈 프로세스가 어떤 프로세스인지를 하나의 변수로 나타내어 일치하는 프로세스만 진입하도록 하는 단순한 방식
- 상호 배제는 만족하나 진행은 만족하지 못함
Algorithm 2
- 특정 프로세스가 임계 구역에 진입할 준비가 되었음을 나타내는 변수를 두어, 다른 프로세스가 임계 구역에 진입하려고 할 경우 현재의 프로세스는 기다리는 방식
- 상호 배제는 만족하나 진행은 만족하지 못함
Algorithm 3
- 알고리즘 1과 2를 합쳐 놓은 방식으로 피터슨 알고리즘(Peterson's algorithm)이라고도 함
- turn 변수와 flag 변수를 동시에 사용하는 방법
- 상호 배제, 진행, 한정 대기 모두 만족하나, 임계 구역에 대한 진입을 기다리면서 CPU와 메모리를 계속해서 사용하는 문제(Busy waiting)가 발생
뮤텍스 락(Mutex Locks)
- 임계 구역 문제를 해결하기 위한 소프트웨어 도구 중 가장 단순한 방법
- 이미 하나의 프로세스가 임계 구역에서 작업 중인 경우 다른 프로세스들이 임계 구역에 접근할 수 없도록 하는 방법
- 앞서 살펴본 피터슨 알고리즘과 동일하게 Busy waiting 문제가 발생(프로세스가 lock이 반환될 때까지 계속 확인하면서 기다리므로 Spin lock이라고도 함)
- 임계 구역에 진입하기 위한 대기 시간이 짧을 때(즉, 문맥 교환보다 기다리는 것이 더 효율적인 경우) 사용 가능
- 단일 CPU 시스템에서는 lock을 갖고 있는 스레드를 풀어주기 위해 문맥 교환이 발생하므로 의미가 없고, 멀티 프로세서 시스템에서 종종 사용됨
Mutex = Mutual Exclusion
세마포어(Semaphores)
개요
- Busy waiting이 필요 없는 동기화 도구로서, 여러 프로세스나 스레드가 임계 영역에 진입할 수 있는 Signaling 매커니즘
- 카운터(Counter)를 이용해 동시에 자원에 접근 가능한 프로세스를 제한
- 주로 S라는 정수형 변수로 나타내며, 이는 사용 가능한 자원의 개수를 의미함
- 한 프로세스가 세마포어 변수를 수정할 때는 다른 프로세스가 동시에 같은 세마포어 변수를 수정할 수 없음
세마포어의 종류
- Counting semaphore : 정수 값의 범위가 0 이상으로 제한이 없으며, 주로 자원의 개수를 세는 데 사용
- Binary semaphore : 정수 값이 0 또는 1로 Mutex lock과 동일한 역할을 수행
세마포어의 구현
-
일반적인 구현 방식
이 방식의 경우 Busy waiting이 발생하여 비효율적이다. 다만 임계 구역이 매우 짧은 경우 더 효율적일 수도 있다. -
Block & Wakeup 방식
임계 구역으로 진입하는 데 실패한 프로세스를 대기시키지 않고 Block한 뒤 임계 구역에 자리가 생기면 해당 프로세스를 다시 깨움으로써 Busy waiting의 CPU 낭비 문제를 해결한 방식이다.
이 방식에서 세마포어는 다음과 같이 정의한다.
이때 value는 세마포어 변수를, L은 block된 프로세스들이 기다리는 큐(queue)를 의미한다. 따라서 wait과 signal 함수도 다음과 같이 구현한다.
만약 Block을 수행하면 커널은 block을 호출한 프로세스를 정지시키고 해당 프로세스의 PCB를 wait queue에 넣는다.
Wakeup을 수행하면 block된 프로세스 P를 깨운 뒤 이 프로세스의 PCB를 Ready queue로 이동시킨다.
이때 wait나 signal 등의 함수는 같은 세마포어에 대해 두 프로세스가 동시에 실행하는 것이 불가능하다.
참고 자료
