운영체제 - Process Synchronization and Mutual Exclusion

프로세스 동기화

동기화

★ 다중 프로그래밍 시스템

• 여러 개의 프로세스들이 존재
• 프로세스들은 서로 독립적으로 동작
• 공유 자원 또는 데이터가 있을 때, 문제 발생 가능

★ 동기화

• 프로세스들이 서로 동작을 맞추는 것
• 프로세스들이 서로 정보를 공유하는 것

Asynchronous and Concurrent P’s

★ 비동기적

• 프로세스들이 서로에 대해 모름

★ 병행적

• 여러 개의 프로세스들이 동시에 시스템에 존재

★ 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근 할 때 문제가 발생할 수 있음

Terminologies

★ Shared data (공유 데이터) or Critical Data

• 여러 프로세스들이 공유하는 데이터

★ Critical section (임계 영역)

• 공유 데이터를 접근하는 코드 영역(code segment)

★ Mutual exclusion (상호배제)

• 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것

Critical Section (example)

✓ Note

기계어 명령의 특성

• Atomicity (원자성), Indivisible (분리불가능)
• 한 기계어 명령의 실행 도중에 인터럽트 받지 않음

중간에 preemption 발생에 따른 기대한 동작이 진행되지 않을 수 있음 (명령 수행 과정에 따라)

→ “Race condition”

 

Mutual Exclusion (상호배제)

Mutual Exclusion Methods

★ Mutual exclusion primitives

• enterCS() primitive

✓ Critical section 진입 전 검사

✓ 다른 프로세스가 critical section 안에 있는지 검사

• exitCS() primitive

✓ Critical section을 벗어날 때의 후처리 과정

✓ Critical section을 벗어남을 시스템이 알림

✓ primitives : 기본연산을 뜻함

Requirements for ME primitives

★ Mutual exclusion (상호배제)

• Critical section (CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지

★ Progress (진행)

• CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해 하면 안됨

★ Bounded waiting (한정대기)

• 프로세스의 CS 진입은 유한시간 내에 허용되어야 함

Two Process Mutual Exclusion

★ Progress 조건 위배

• Why?

✓ P0이 critical section에 진입 하지 않는 경우

✓ 한 Process가 두 번 연속 cs에 진입 불가

 

★ Mutual exclusion 조건 위배

★ Progress, Bounded waiting 조건 위배

Mutual Exclusion Solutions

SW solutions

Dekker’s Algorithm

★ Two process ME를 보장하는 최초의 알고리즘

Peterson’s Algorithm

★ Dekker’s algorithm 보다 간단하게 구현

★ Progress, Bounded waiting 조건 위배

 

N-Process Mutual Exclusion

★ 다익스트라

• 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결
• 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법, 가장 짧은 평균 대기시간 제공

Dijkstra’s Algorithm

SW Solutions

★ SW solution들의 문제점

• 속도가 느림
• 구현이 복잡함
• ME primitive 실행 중 preemption 될 수 있음

✓ 공유 데이터 수정 중에는 interrupt를 억제 함으로서 해결 가능

✓ Overhead 발생

• Busy waiting : 기다리는데 계속 도는 것

✓ Inefficient

HW solution

Synchronization Hardware

★ TestAndSet (TAS) instruction

• Test와 Set을 한번에 수행하는 기계어
• Machine instruction

✓ Atomicity, Indivisible

✓ 실행 중 interrupt를 받지 않음 (preemption 되지 않음)

• Busy waiting

✓ inefficient

TAS Instrcution

ME with TAS Instruction

★ 3개 이상의 프로세스의 경우, Bounded waiting 조건 위배

N-Process mutual exclusion

★ 장점

• 구현이 간단

★ 단점

• Busy waiting

✓ inefficient

★ Busy waiting 문제를 해소한 상호배제 기법

• Semaphore

✓ 대부분의 OS들이 사용하는 기법

 

OS supported SW solution

★ Spinlock

★ Semaphore

★ Eventcount/sequencer

Spinlock

★ 정수 변수

★ 초기화, P(), V() 연산으로만 접근 가능

• 위 연산들은 indivisible (or atomic) 연산

✓ OS support

✓ 전체가 한 instruction cycle에 수행 됨

P : 문을 잠금 / S : 문을 염

★ 멀티 프로세서 시스템에서만 사용 가능

★ Busy waiting

Semaphore

• 1965년 Dijkstra가 제안
• Busy waiting 문제 해결
• 음이 아닌 정수형 변수(S)

✓ 초기화 연산, P(), V()로만 접근 가능

✓ P : Probern (검사)

✓ V : Verhogen (증가)

• 임의의 S 변수 하나에 ready queue 하나가 할당 됨

• Binary semaphore

✓ S가 0과 1 두 종류의 값만 갖는 경우

✓ 상호배제나 프로세스 동기화의 목적으로 사용

• Counting semaphore

✓ S가 0이상의 정수값을 가질 수 있는 경우

✓ Producer-Consumer 문제 등을 해결하기 위해 사용

✓ 생산자 - 소비자 문제

• 초기화 연산

★ S 변수에 초기값을 부여하는 연산

• P() 연산, V() 연산

• 모두 indivisible 연산

✓ OS support

✓ 전체가 한 instruction cycle에 수행 됨

Semaphore in OSs

Semaphore로 해결 가능한 동기화 문제들

• 상호배제 문제

✓ Mutual exclusion

• 프로세스 동기화 문제

✓ process synchronization problem

• 생산자-소비자 문제

✓ producer-consumer problem

• Reader-writer 문제
• Dining philosopher problem
• 기타

★ Mutual exclusion

★ Process synchronization

• Process들의 실행 순서 맞추기

✓ 프로세스들은 병행적이며, 비동기적으로 수행

★ Producer-Consumer problem

• 생산자(Producer) 프로세스

✓ 메시지를 생성하는 프로세스 그룹

• 소비자(Consumer) 프로세스

✓ 메시지 전달받는 프로세스 그룹

★ Producer-Consumer problem with single buffer

★ Producer-Consumer problem with N-buffers

★ Reader-Writer problem

• Reader

✓ 데이터에 대해 읽기 연산만 수행

• Writer

✓ 데이터에 대해 갱신 연산을 수행

• 데이터 무결성 보장 필요

✓ Reader들은 동시에 데이터 접근 가능

✓ Writer들(또는 reader와 write)이 동시 데이터 접근 시, 상호배제(동기화) 필요

• 해결법

✓ reader / writer에 대한 우선권 부여

✓ reader preference solution

✓ writer preference solution

• No busy waiting

✓ 기다려야 하는 프로세스는 block(asleep)상태가 됨

• Semaphore queue에 대한 wake-up 순서는 비결정적

✓ Starvation problem

Eventcount / Sequencer

★ 은행의 번호표와 비슷한 개념

 

★ Sequencer

• 정수형 변수
• 생성시 0으로 초기화, 감소하지 않음
• 발생 사건들의 순서 유지
• ticket() 연산으로만 접근 가능

★ ticket(S)

• 현재까지 ticket() 연산이 호출 된 횟수를 반환
• Indivisible operation

★ Eventcount

• 정수형 변수
• 생성시 0으로 초기화, 감소하지 않음
• 특정 사건의 발생 횟수를 기록
• read(E), advance(E), await(E, v) 연산으로만 접근 가능

★ read(E)

• 현재 Eventcount 값 반환

★ advance (E)

• E ← E + 1
• E를 기다리고 있는 프로세스를 깨움 (wake-up)

★ await(E, v)

• V는 정수형 변수
• if (E < v) 이면 E에 연결된 Qe에 프로세스 전달(push) 및 CPU scheduler 호출

★ Mutual exclusion

→ Starvation problem 해결

 

★ Producer-Consumer problem

 

Eventcount / Sequencer

★ No busy waiting

★ No starvation

• FIFO scheduling for Qe

★ Semaphore 보다 더 low-level control이 가능

 

기존 SW solutions, HW solution, OS supported SW solution

→ flexible

→ Difficult to use

✓ Error-prone

✓ Low-level mechanisms

Language-Level solution

• Monitor

High-level Mechanism

★ Monitor

★ Path expressions

★ Serializers

★ Critical region, conditional critical region

★ Language-level constructs

★ Object-Oriented concept과 유사

★ 사용이 쉬움

Monitor

★ 공유 데이터와 Critical section의 집합

★ Conditional variable

• wait(), signal() operations

Monitor의 구조

★ Entry queue (진입 큐)

• 모니터 내의 procedure(function) 수만큼 존재

★ Mutual exclusion

• 모니터 내에는 항상 하나의 프로세스만 진입 가능

★ Information hiding (정보 은폐)

• 공유 데이터는 모니터 내의 프로세스만 접근 가능

★ Condition queue (조건 큐)

• 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기하는 대기실

★ Signaler queue (신호제공자 큐)

• 모니터에 항상 하나의 신호제공자 큐가 존재
• signal() 명령을 실행한 프로세스가 임시 대기

Monitor in Languages

★ 자원 할당 문제

★ 자원 할당 시나리오

• 자원 R 사용 가능
• Monitor 안에 프로세스 없음

• 프로세스 Pj가 모니터 안에서 자원 R을 요청

• 자원 R이 Pj에게 할당 됨
• 프로세스 Pk가 R 요청, Pm 또한 R 요청

• Pj가 R반환
• R_Free.signal() 호출에 의해 Pk가 wakeup

• 자원 R이 Pk에게 할당 됨
• Pj가 모니터 안으로 돌아와서, 남은 작업 수행

• 자원 R이 Pk에게 할당 됨
• Pj가 모니터 안으로 돌아와서, 남은 작업 수행

Producer-Consumer Problem

 

Reader-Writer Problem

• reader/writer 프로세스들간의 데이터 무결성 보장 기법
• wirter 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함

• 모니터 구성

✓ 변수 2개

  ✓ 현재 읽기 작업을 진행하고 있는 reader 프로세스의 수

  ✓ 현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시

✓ 조건 큐 2개

  ✓ reader/writer 프로세스가 대기해야 할 경우에 사용

✓ 프로시져 4개

  ✓ reader(writer) 프로세스가 읽기(쓰기) 작업을 원할 경우에 호출, 읽기(쓰기) 작업을 마쳤을 때 호출

Dining philosopher problem

• 5명의 철학자
• 철학자들은 생각하는 일, 스파게티 먹는 일만 반복함
• 공유 자원 : 스파게티, 포크
• 스파게티를 먹기 위해서는 좌우 포크 2개 모두 들어야 함

Monitor

★ 장점

• 사용이 쉽다
• Deadlock 등 error 발생 가능성이 낮음

★ 단점

• 지원하는 언어에서만 사용 가능
• 컴파일러가 OS를 이해하고 있어야 함

✓ Critical section 접근을 위한 코드 생성