프로세스 동기화 & 상호배제

동기화

다중 프로그래밍 시스템 상에서 여러 개의 프로세스들은서로 독립적으로 동시에 동작한다. 그런데 프로세스들이 함께 사용하는 공유 자원 또는 데이터가 있을 때, 이를 동시에 사용하고자 한다면 문제가 발생할 수 있다. 이를 방지하기 위하여 프로세스들이 서로 동작을 맞추는 것,

서로의 상태 정보를 공유하는 것을 동기화라고 부른다.

동기화를 위한 개념

공유 데이터(Shared Data or Critical Data) : 여러 프로세스들이 공유하는 데이터

임계 영역(Critical Section) : 공유 데이터를 접근하는 코드 영역

상호 배제(Mutual Exclusion) : 둘 이상의 프로세스가 동시에 임계 영역에 진입하는 것을 막는 것

 

상호 배제 기본 연산(Mutual Exclusion Primitives)

EnterCS Primitive : 임계 영역 진입 전 다른 프로세스가 임계 영역 안에 있는지 검사한다.

ExitCS Primitive : 임계 영역을 벗어날 때의 후처리 과정으로 임계 영역을 벗어 낫음을 시스템에 알린다. 

상호 배제 기본 연산을 위한 요구 사항(Requirements for ME Primitives)

상호 배제(Mutual Exclusion) : 임계 영역에 프로세스가 있으면 다른 프로세스의 진입을 금지한다.

진행(Progress) : 임계 영역 안에 있는 프로세스 외에는 다른 프로세스가 임계 영역에 진입하는 것을 방해하면 안 된다.

한정 대기(Bounded Waiting) : 프로세스의 임계 영역 진입은 유한 시간 내에 허용되어야 한다.

상호 배제 솔루션(Mutual Exclusion Solutions)

소프트웨어 솔루션

속도가 느리고 구현이 복잡하다. 상호 배제 기본 연산 실행 중 Preemption 될 수 있다. Busy Waiting의 문제가 있다.

 

하드웨어 솔루션

구현이 간단하나 Busy Waiting 문제가 있다.

 

운영체제 지원 소프트웨어 솔루션

1) Spinlock

P( ), V( ) 연산으로만 접근 가능한 임의의 정수 변수(S)를 이용하는 방법이다. 운영체제가 P( ), V( ) 연산이 하나의 Instruction Cycle에

수행되도록 즉, Indivisible(or atomic)하게 수행될 수 있도록 보장한다. 멀티 프로세서 시스템에서만 사용 가능하며 여전히 Busy Waitig

문제가 있다.

2) Semaphore

P( ), V( ) 연산으로만 접근 가능한 음이 아닌 정수 변수(S)를 이용하는 방법이다. 정수 변수 하나에 Ready Queue(Q) 하나가 할당된다.

정수 변수가 0과 1 두 종류의 값만 갖는 경우를 Binary Semaphore라고 하며 상호 배제나 프로세스 동기화의 목적으로 사용한다.

반면, 정수 변수가 0 이상의 값을 가질 수 있는 경우 Counting Semaphore라고 한다. Semaphore의 연산은 모두 Indivisible

연산이며 연산이 한 Instruction Cycle에 수행되도록 운영체제가 보장한다. 기다려야 하는 프로세스는 Block(Asleep) 상태가 되기에

Busy Waiting 문제가 해결된다. 다만, Semaphore Queue에 대한 Wake Up 순서는 비 결정적이다. 따라서 Starvation 문제가 

있을 수 있다.

Producer-Consumer Problem(Single Buffer, N Buffer), Reader-Writer Problem

3) Eventcount/Sequencer

은행의 번호표와 비슷한 개념으로, 감소하지 않는 정수형 변수 Sequencer를 0으로 초기화하고 ticket( ) 연산으로만 접근 가능하도록

한다. 이를 통해 발생 사건들의 순서를 유지한다. 감소하지 않는 정수형 변수 Eventcount를 0으로 초기화하고 read(E), advance(E),

await(E, v) 연산으로만 접근 가능하도록 한다. 이를 통해 특정 사건의 발생 횟수를 기록한다. read(E)는 현재 Eventcount 값을 반환한다.

advance(E)는 E를 E + 1로 변환하고, E를 기다리고 있는 프로세스를 깨운다. await(E, v)는 if (E < v)이면 E에 연결된 Q에 프로세스를

전달하고 CPU Scheduler를 호출한다. 이때 v는 정수형 변수이다. Busy Waiting이 없고, FIFO Scheduling으로 Starvation 역시 없다.