Process Synchronization

데이터의 접근

Race Condition

S-Box(= Memory Address Space)를 공유하는 E-Box(= CPU Process)가 여럿 있는 경우(= Multi-Processor System), Race Condition의 가능성이 있음

• 공유 메모리를 사용하는 프로세스들

• 커널 내부 데이터를 접근하는 루틴들(Kernel 모드 수행 중 Interrupt로 Kernel 모드 다른 루틴 수행 시) 간

OS에서 Race Condition은 언제 발생하는가?

1. Kernel 수행 중 Interrupt 발생 시

2. Process가 System Call을 하여 Kernel Mode로 수행 중인데, Context Switch가 일어나는 경우

3. Multi-Processor에서 Shared Memory 내의 Kernel Data

Interrupt Handler VS Kernel

• Kernel Mode Running 중 Interrupt가 발생하여 Interrupt 처리 루틴이 수행됨
• 양쪽 다 Kernel 코드이므로 Kernel Address Space 공유

Preempt a process running in kernel

• 두 프로세스의 Address Space 간에는 Data Sharing이 없음

• 그러나 System Call을 하는 동안에, Kernel Address Space의 Data를 Access하게 됨(Share)

• 이 작업 중간에 CPU를 빼앗아가면 Race Condition 발생

Multi-Processor

• 어떤 CPU가 마지막으로 count를 store 했는가? → Race Condition

• Multi-Processor의 경우 Interrupt Enable/Disable로 해결 불가

Process Synchronization

• 공유 데이터(Shared Data)의 동시 접근(Concurrent Access)은 데이터의 불일치 문제(Inconsistency)를 발생시킬 수 있다.

• 일관성(Consistency) 유지를 위해 협력 프로세스(Cooperating Process)간의 실행 순서(Orderly Execution)를 정해주는 메커니즘 필요

• Race Condition
• 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
• 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

• Race Condition을 막기 위해서는 Concurrent Process는 동기화(Synchronize)되어야 한다.

The Critical-Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

• 각 프로세스의 Code Segment에는 공유 데이터를 접근하는 코드인 Critical Section이 존재

• 문제
• 하나의 프로세스가 Critical Section에 있을 때, 다른 모든 프로세스는 Critical Section에 들어갈 수 없어야 한다.

프로그램적 해결법의 충족 조건

• Mutual Exclusion(상호 배제)
• 프로세스 Pi가 Critical Section 부분을 수행 중이면, 다른 모든 프로세스들은 그들의 Critical Section에 들어가면 안된다.

• Progress
• 아무도 Critical Section에 있지 않은 상태에서 Critical Section에 들어가고자 하는 프로세스가 있으면, Critical Section에 들어가게 해주어야한다.

• Bounded Waiting(유한 대기)
• 프로세스가 Critical Section에 들어가려고 요청한 후부터, 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야 한다.
• Starvation이 발생하면 안된다.

• 가정
• 모든 프로세스의 수행 속도는 0보다 크다.
• 프로세스 간 상대적인 수행 속도는 가정하지 않는다.

Algorithm 1

Algorithm 2

Algorithm 3(Peterson’s Algorithm)

• 조건 모두 만족

• Busy Waiting(Spin Lock)

Synchronization Hardware

• 하드웨어적으로 Test & Modify를 Atomic하게 수행할 수 있도록 지원하는 경우, 앞의 문제는 간단히 해결

• Mutual Exclusion with Test & Set

Semaphores

• 앞의 방식을 추상화시킴

• Semaphore S
• integer variable
• 아래의 두가지 Atomic 연산에 의해서만 접근 가능



• P연산: 공유 데이터를 획득하는 과정, 락을 거는 과정
• V연산: 사용 후 반납하는 과정, 락을 푸는 과정

Critical Section of n Processes

• Busy-Wait는 효율적이지 못함(Spin Lock)

• Block & Wakeup 방식의 구현(Sleep Lock)

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

• Block과 Wakeup을 다음과 같이 가정
• Block
• 커널은 block을 호출한 프로세스를 suspend 시킴
• 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
• Wakeup(P)
• block된 프로세스 P를 wakeup함
• 이 프로세스의 PCB를 ready queue로 옮김

• Semaphore 연산이 이제 다음과 같이 정의됨

• S.value가
• 음수면, 누군가가 기다리고 있다.
• 양수면, 자원이 있다.

Busy-Wait VS Block/Wakeup

• 일반적으로 Block/Wakeup이 효율적

• Block/Wakeup Overhead VS Critical Section 길이
• Critical Section의 길이가 긴 경우, Block/Wakeup이 효율적
• Critical Section의 길이가 매우 짧은 경우, Block/Wakeup의 Overhead가 Busy-Wait Overhead보다 더 커질 수 있음

Two Types of Semaphores

• Counting semaphore
• 도메인이 0 이상인 임의의 정수 값
• 주로 Resource Counting에 사용

• Binary semaphore(Mutex)
• 0 또는 1값만 가질 수 있는 semaphore
• 주로 Mutual Exclusion(Lock/Unlock)에 사용

Deadlock & Starvation

• Deadlock
• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 Event를 무한히 기다리는 현상
• S와 Q가 1로 초기화된 semaphore라 하자.

• Starvation
• Indefinite Blocking
• 프로세스가 Suspend된 이유에 해당하는 semaphore queue에서 빠져나갈 수 없는 현상

Classical Problems of Synchronization

• Bounded-Buffer Problem(Producer-Consumer Problem)

• Readers and Writers Problem

• Dining-Philosophers Problem

Bounded-Buffer Problem(Producer-Consumer Problem)

• 생산자 여럿이 동시에 한 곳에 데이터를 집어넣으면 문제 발생

Readers-Writers Problem

• 한 Process가 DB에 Write중일 때, 다른 Process가 접근하면 안됨

• Read는 동시에 여럿이 해도 됨

• Solution
• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
• Writer가 DB에 접근 중이면, Reader들은 접근이 금지된다.
• Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

Dining-Philosophers Problem

• 문제점
• Deadlock 가능성 있음
• 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우

• 해결 방안
• 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
• 젓가락을 두개 모두 집어야 할 때에만 젓가락을 집을 수 있게 한다.
• 비대칭
• 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

Semaphore의 문제점

• 코딩하기 힘들다.

• 정확성(Correctness)의 입증이 어렵다.

• 자발접 협력(Voluntary Cooperation)이 필요하다.

• 한번의 실수가 모든 시스템에 치명적 영향

• 예

Monitor

• 동시 수행중인 프로세스 사이에서 Abstract Data Type의 안전한 공유를 보장하기 위한 High-Level Synchronization Construct

• Monitor에 대한 동시 접근을 허용하지 않음
• 개발자가 제어할 필요 없이 Monitor가 알아서 관리해줌

• Monitor 내에서는 한번에 하나의 프로세스만 활동 가능

• 개발자가 동기화 제약 조건을 명시적으로 코딩할 필요 없음

• 프로세스가 Monitor안에서 기다릴 수 있도록 하기 위해 Condition Variable 사용

• Condition Variable은 Wait와 Signal 연산에 의해서만 접근 가능
• x.wait();
• x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend 된다.
• x.signal();
• x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다.
• Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

• 장점
• Lock을 걸 필요가 없다.

Bounded-Buffer Problem(Producer-Consumer Problem)

출처