[OS/운영체제] 프로세스 동기화 (Process Synchronization) - (2)

Peterson's Soultion

Critical-Section Problem을 소프트웨어 기반의 간단한 구조로 해결하는 Peterson's Solution을 알아보자.

현대의 하드웨어에서는 동작할 확신을 가질 수 없지만, Critical-Section Problem 해결의 알고리즘적 기초를 제공했다는 것에 그 의의가 있다.

 

Peterson's Solution은 Critical Section과 Remainder Section을 실행하는 두 프로세스에 한해 동작한다.

두 프로세스를 P0, P1이라 하자.

 

Peterson's Solution은 두 프로세스들이 다음 데이터를 공유하도록 한다.

turn 변수는 Critical Section에 들어갈 프로세스가 현재 누구 차례인지를 나타낸다. 만약 turn이 i라면, Pi가 Critical Section에 들어갈 수 있다는 의미이다.

flag 배열은 프로세스가 Critical Section에 들어갈 준비가 되었는지를 나타낸다. 만약 flag[i] 가 true라면, Pi는 Critical Section에 들어갈 준비가 되었다는 의미이다.

 

Peterson's Soultion이 동작하는 과정 (Pi)

(그림에서 j = 1 - i 이다.)

프로세스 Pi는 Entry Section에서 turn의 값을 j로 바꿔줌으로써 만약 Pj가 Critical Section의 진입을 시도할 때 Pj가 진입을 할 수 있도록 해 준다. 이는 Pj도 마찬가지이므로, 결국 turn이 가리키는 프로세스가 Critical Section에 진입하게 된다.

 

 - Mutual Exclusion : turn이 i이면서 동시에 j일 수 없으므로, Pi, Pj 가 Critical Section에 동시에 진입할 수 없다. 따라서, Mutual Exclusion이 보장된다. (turn이 Pi를 가리킨다면, Pj는 while문에 걸려 대기하게 된다.)

 - Progress : Exit Section에서 각 프로세스들은 자신의 flag값을 false로 바꿔주어, while문에서 대기하던 프로세스는 그 즉시 Critical Section에 진입할 수 있다. 따라서 Progress를 만족한다.

 - Bounded-Waiting : 자신 외의 다른 프로세스가 종료되면 반드시 자신은 Critical Section에 진입할 수 있으므로, Bounded-Waiting을 만족한다.

 

Synchronization Hardware

Peterson's Solution은 소프트웨어 기반의 Critical Section Problem 해결법이다. 하지만, 이는 현대의 컴퓨터 구조에서의 동작을 확신할 수 없다. 대신, Critical Section Problem을 해결하기 위해선 Lock 이라는 도구가 필요하다고는 말할 수 있을 것이다.

Critical Section Problem은 단일 프로세서 환경에서는 공유 변수의 조작에서 발생하는  interrupt를 차단함으로써 간단하게 해결될 수 있다.  하지만 멀티 프로세서 환경에서는 시간 효율이 떨어져 사용하기 어렵다.

따라서 대부분의 현대 컴퓨터 시스템에서는 내용을 원자적으로 (Atomically) 수정 또는 교환할 수 있도록 별도의 연산을 제공한다. (이는 un-interruptible한 단위이다.) 이 특별한 연산을 사용해 우리는 Critical Section Problem을 해결할 수 있다.

 

TestAndSet()

TestAndSet() 연산의 정의

TestAndSet() 의 가장 중요한 특징은 실행의 원자성으로, 만약 두 개의 TestAndSet() 연산이 동시에 실행된다면 연산들은 임의의 순서에 의해 순차적으로 실행된다.

따라서, TestAndSet() 연산과 초기값이 false인 변수 lock을 통해 우리는 다음과 같이 Mutual Exclusion을 구현할 수 있다.

lock과 TestAndSet()을 사용

 

Swap()

Swap() 연산의 정의

Swap() 연산도 TestAndSet() 연산과 마찬가지로 실행의 원자성을 가진다. 따라서 key라는 지역 bool 변수와 전역 bool 변수 lock을 통해 다음과 같이 Mutual Exclusion을 구현할 수 있다. (두 변수 모두 초기값은 false이다.)

key와 Swap() 사용

이 경우 Mutual Exclusion은 만족하지만, Bounded-Waiting은 만족할 수 없다. 프로세스가 lock을 얻는 순서는 임의의 순서이기 때문이다.

따라서, 다음과 같은 요소를 추가해 Bounded-Waiting을 만족하도록 한다.

 

Mutex Locks & Semaphores

하드웨어 기반의 locking 기법은 복잡하고, 응용 프로그램의 개발자에게는 접근성이 떨어진다. 이러한 단점을 극복하기 위해, Semaphore(이하 세마포어)라는 도구를 사용할 수 있다.

 

세마포어 S는 원자성을 가진 연산 wait()과 signal()에 의해서만 접근할 수 있는 정수형 변수이다.

wait()의 정의

signal()의 정의

wait() 연산은 S의 값이 1 이상인 경우 S의 값을 1 감소시키는 연산이며, signal() 연산은 S의 값을 1 증가시키는 연산이다.

 

세마포어는 Counting Semaphore와 Binary Semaphore로 나뉜다. 일반적으로 세마포어의 값이 0, 1 만 가능하다면 Binary Semaphore라 하고, 2 이상의 값을 가질 수 있다면 Counting Semaphore라 한다.

Binary Semaphore를 Mutex Locks라고 부르는데, 여러 프로세스들에게 Critical Section Problem을 처리할 수 있다.

Counting Semaphore는 유한한 갯수의 자원에 대한 접근을 제한하는 데 사용할 수 있다. k개의 어떤 자원에 대해 Counting Semaphore S를 사용하면, 한 프로세스가 자원을 차지할 때마다 wait()을 통해 S의 값이 줄어들어 모든 자원이 사용 중이라면 S의 값은 0이 된다. 이 때 프로세스들은 더 이상 자원에 접근할 수 없다. 한 프로세스가 자원의 사용을 마치면, signal() 을 통해 S의 값을 증가시켜 다른 프로세스가 접근할 수 있게 된다.

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.