프로세스 동기화

배경
임계영역 문제
피터슨의 해결안
동기화 하드웨어
Mutex Locks
세마포
모니터

배경

이번 챕터에선 프로세스가 병행 또는 병렬로 실행될 때 여러 프로세스가 공유하는 데이터의 무결성 에 대하여 설명한다.


생산자와 소비자 코드 예시

위 예시의 코드를 병행 실행하였을때, 문제가 발생한다. counter의 현재 값은 5이고 생산자와 소비자는 counter++와 couter–를 병행실행한다고 가정한다면, 이 두 명령을 수행하고나면 counter의 값은 4나 5나 6이 된다.


생산자와 소비자 프로세스의 명령 수행

동시에 여러 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상황(Race Condition) 이라고 한다. 이를 해결하기 위해, 한 순간에 하나의 프로세스만이 서로 공유하고 있는 자료를 조작하도록 보장하여야 한다. 즉, 코드가 원자성(Atomic) 하게 실행되도록 보장하여야 한다.

임계영역 문제

n개의 프로세스가 있는 시스템을 고려했을때, 각 프로세스는 임계구역(Critical Section) 이라고 불리는 코드부분을 포함하고있고, 그 안에서는 다른 프로세스와 공유하는 변수를 변경하거나, 테이블을 갱신하거나 파일을 쓰거나 하는등의 작업을 수행한다. 이 시스템의 중요한 특징은 “한 프로세스가 자신의 임계구역에서 작업을 수행하는 동안에는 다른 프로세스는 그들의 임계구역에 접근할수 없다” 라는 점이다. 즉, 동시에 두 프로세스는 그들의 임계구역 안에서 실행할 수 없다.

임계구역 문제(Critical Section Problem) 는 프로세스들이 협력할 때 사용할 수 있는 프로토콜을 설계하는 것이다.

각 프로세스는 자신의 임계구역으로 접근하려 할때, 진입 허가를 요청한다. 이러한 요청을 구현하는 코드 부분을 진입구역(Entry Section) 이라 하며, 이후 임계구역을 빠져나오는 코드 부분을 퇴장구역(Exit Section) 이라 한다. 나머지 코드 부분은 나머지구역(Remainder Section) 이라고 불린다.


전형적인 프로세스 P_i의 일반적인 구조

임계구역 문제에 대한 해결안은 아래 세가지 요구조건을 충족해야 한다.

상호 배제(Mutual Exclusion)
- 프로세스 P_i 가 자기의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될수 없다.
진행(Progress)
- 자시의 임계구역에서 실행되는 프로세스가 없고, 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음에 누가 그 임계구역으로 진입할 수 있는지를 결정하는데 참여할 수 있으며, 이 선택은 무기한 연장될수 있다.
- deadlock-free-condition
한정된 대기(Bounded Waiting)
- 프로세스가 자기의 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
- starvation-free-condition

피터슨의 해결안

임계구역 문제를 해결하기 위해 상호배제, 진행, 한정된 대기의 요구조건을 충족하는 SW를 설계하는데 필요한 복잡성을 잘 설명하기 때문에 이 해결책을 제시한다.

Peterson’s solution 에서는 두 프로세스가 두개의 데이터 항목을 공유하도록 하여 해결한다.

int turn
- 임계구역으로 진입할 순번
bool flag[2]
- 프로세스가 임계구역으로 진입할 준비가 되어있다는것을 나타내는 배열

한 프로세스 P_i가 임계구역으로 진입하기 위해서, 먼저 flag[i]를 참으로 만들고, turn을 j로 지정한다. 이렇게 함으로써 프로세스 j가 임계구역으로 진입하기를 원한다면 진입 가능하다는 것을 보장한다.


Peterson’s solution에서의 프로세스 P_i의 구조

동기화 하드웨어

이번 챕터에서 설명하는 해결책들은 락킹(Locking) 에 대한 가정, 즉 임계구역을 보호하기 위한 방법에 대해 분석한다.

임계구역 문제는 단일 처리기 환경에서는 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음으로써 간단히 해결할 수 있다.

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

Mutex Locks

임계구역을 보호하고, 경쟁조건을 방지하기 위해 mutex 락을 사용한다.

프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고, 임계구역을 빠져나올때 락을 반환해야 한다.


acquire(), release() 함수 예시


Mutex 락을 사용한 임계영역 문제 해결방안

락을 획득하고 반환하는 acquire(), release() 함수 호출은 반드시 원자적으로 수행되어야 한다.

mutex의 단점으로는 바쁜 대기(Busy Waiting) 혹은 Spinlock 을 해야 한다는 점이다. 프로세스가 임계구역에 들어가 있는동안 임계구역에 접근하고자 하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행하여야 한다. 즉 CPU 사이클을 낭비하게 된다. 하지만 락을 기다리는 동안 상당한 시간을 소모하는 문맥교환을 전혀 필요로 하질 않는다는 점이 있기 때문에, 프로세스들이 짧은 시간동안만 락을 소유할 것이라고 예상되면 유용하게 쓸수 있다.

세마포

세마포 S는 정수 변수로써, 초기화를 제외하고는, 단지 두개의 표준 원자적 연산 wait(), signal() 로만 접근이 가능하다.


wait()와 signal() 정의

wait()과 signal() 연산 시 세마포의 정수 값을 변경하는 연산은 반드시 분리되지 않고 수행되어야 한다. 즉, 한 스레드가 세마포 값을 변경하면, 다른 어떤 스레드도 동시에 동일한 세마포 값을 변경할 수 없다.

세마포 사용법

OS는 종종 카운팅(counting) 과 이진(binary) 세마포를 구분한다. 카운팅 세마포(Counting Semaphore) 의 값은 제한 없는 영역을 가지며, 이진 세마포(Binary Semaphore) 의 값은 0과 1사이의 값만 가능하다.

이진 세마포는 mutex 락과 유사하게 동작한다.


세마포를 이용한 상호 배제 구현

세마포는 가용한 자원의 개수로 초기화된다. 각 자원을 사용하려는 프로세스는 세모포의 wait() 연산을 수행하며, 이 때 세마포의 값은 감소된다. 세마포의 값이 0이 되면 모든 자원이 사용중임을 나타낸다. 이후 자원을 사용하려는 프로세스는 세마포의 값이 0보다 커질때 까지 block되어 대기한다.

구현


세마포, wait(), signal() 구현

block() 연산은 자기를 호출한 프로세스를 중지 시킨다. wakeup(P) 연산은 중지된 프로세스 P의 실행을 재개시킨다. 일련의 과정은 아래와 같다.

P1이 block() 호출
P1은 Waiting 상태가 되며 Waiting Queue에 넣어짐
다른 프로세스 P2에서 wakeup(P1) 호출
P1은 Ready 상태가 되며 Ready Queue에 넣어짐

세마포가 원자적으로 실행되어야 한다는 것은 매우 중요하다. 같은 세마포에 대하여 두 프로세스가 동시에 wait()와 signal() 연산을 실행 할 수 없도록 반드시 보장하여야 한다. 이를 보장하기위해 다중 처리기 환경에서는 모든 처리기에서 인터럽트를 금지하여야만 한다.

교착 상태와 기아

대기 큐를 가진 세마포를 구현하는 두 개 이상의 프로세스들이 대기 중인 프로세스들 중 하나에 의해서만 야기될 수 있는 사건을 무한정 기다리는 상황이 발생할 수 있다. 이러한 상황을 교착상태(Deadlock) 이라고 한다.


P0, P1간 세마포 동작

P0이 wait(S)를 실행하고, P1이 wait(Q)를 실행한다고 가정할때, P0이 wait(Q)를 실행 할때, P0는 P1이 signal(Q)를 실행할 때까지 기다려야 한다. 마찬가지로 P1이 wait(S)를 실행 할때, P1는 P0이 signal(S)를 실행할 때까지 기다려야 한다. 이들 signal() 연산들은 실행될 수 없기 때문에 P0와 P1은 교착상태가 된다.

한 집합내의 모든 프로세스들이 그 집합 내의 다른 프로세스만이 유발할 수 있는 사건을 기다릴때, 이 프로세스들의 집합이 교착상태에 있다고 한다.

교착상태와 연관된 다른 문제는 무한봉쇄(Indefinite Blocking) 와 기아상태(Starvation) 로서, 이들으 세마포에서 무한정 대기하는 것이다. 무한봉쇄는 우리가 세마포와 연관된 큐에서 프로세스들은 후입선출(LIFO) 순으로 제거할 경우 발생할 수 있다.

모니터

세마포의 경우, 세마포를 이용하여 임계구역 문제를 해결하고자 할떄, 프로그래머가 세마포를 잘못하용하면 다얀한 유형의 오류가 쉽게 발생될수 있다. 이러한 문제를 해결하기 위해 고급 언어 구조물들이 등장하게 되는데, 이러한 고급 언어 구조물중 하나가 모니터(Monitor) 이다.


monitor의 구문

모니터 사용법

모니터 구조물은 모니터 안에 항상 하나의 프로세스만이 활성화 되도록 보장한다. 이러한 동기화 기법은 condition 이라는 구조물로 제공된다.

condition 형 변수에 호출될 수 있는 연산은 오직 wait()과 signal() 연산 이다. 연산 x.wait()는, 이 연산을 호출한 프로세스가 다른 프로세스의 x.signal() 연산을 호출할 때까지 일시중단 되어야 한다는 것을 의미한다.


monitor의 구조

x.signal() 연산은 정확히 하나의 일시중단 프로세스를 재개한다. 만약 일지중단된 프로세스가 없다면 signal() 연산은 아무 소용이 없다.

x.signal() 연산이 프로세스 P에 의하여 호출될때, 조건 x와 연관되어 있는 일시중단된 프로세스 Q가 있다고 가정할때, 만일 일시중단된 스레드 Q가 실행을 재개하도록 허용된다면, signal을 보낸 스레드 P는 반드시 대기하여야 한다. 그렇지 않으면, P와 Q는 모니터 안에서 동시에 활성화 된다.

두 프로세스들은 개념적으로 그들의 실행을 계속할 수 있는데, 아래 두가지 가능성이 존재한다.

Signal and wait
- P는 Q가 모니터를 떠날 때까지 기다리거나 다른조건을 기다린다.
Signal and continue
- Q는 P가 모니터를 떠날 때까지 기다리거나 다른 조건을 기다린다.


조건변수를 가지는 monitor

세마포를 이용한 모니터의 구현

각 모니터마다 mutex라는 세마포가 정의되고 그 초기 값은 1이다. 프로세스는 모니터로 들어가기 전에 wait(mutex)를 호출하고 모니터를 나온 후에 signal(mutex)를 호출해야 한다.

signaling 프로세스는 자신을 중단시키기 위해 next라는 또다른 세마포를 사용할 수 있다. ㅅ


세마포를 이용한 모니터에서의 상호배제


조건변수를 가지는 세마포의 Wait(), Signal()

모니터 내에서 프로세스 수행재개


하나의 자원을 할당해주는 모니터

프로세스들이 올바른 순서로 동작하도록 순서를 보장하기 위해 두가지 조건을 검사하여야 한다.

프로세스들이 모니터를 정확한 순서에 맞추어 호출하는지 검사
비협조적인 프로세스가 액세스 제어 프로토콜을 사용하지 않아서 모니터가 정한 상호 배제 규칙 경로를 무시하여 공유 자원을 직접 액세스 하지 않는다는 것을 보장

OS - 프로세스 동기화