4.2. 동기화 & 상호배제 (HW Solution, OS Supported Solution, Monitor)

김민우·2022년 5월 10일

운영체제

목록 보기

7/14

📌 Mutual Exclusion Solution (HW Solution)

1.1 TestAndSet(TAS) instruction (Synchronization HW)

Test와 Set을 한 번에 수행하는 기계어
Machine instruction
- Atomicity, Indivisible
- 실행 중 Interrupt를 받지 않음 (preemption이 되지 않음)
Busy waiting
- Inefficient

- ME with TAS instruction
- 3개 이상의 프로세스의 경우, Bounded waiting 조건 위배
- N-Process mutual exclusion

1.2 HW Solution의 장단점

장점
- 구현이 간단
단점
- Busy waiting -> Inefficient
Busy waiting 문제를 해소한 상호배제 기법
- Semaphore : 대부분의 OS들이 사용하는 기법

📌 Mutual Exclusion Solution (OS supported SW solution)

2.1. Spinlock
2.2. Semaphore
2.3. Eventcount / Sequencer

2.1. Spinlock

정수형 변수(S)
초기화, P(), V() 연산으로만 접근 가능
- 위 연산들은 indivisible (or atomic) 연산
- OS support
- 전체가 한 instruction cycle에 수행 됨

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

※ Spinlock

active = 1 : 임계 지역을 실행중인 프로세스 없음

active = 0 : 임계 지역을 실행중인 프로세스 있음

2.2. Semaphore

Busy waiting 문제 해결 (1965년 Dijkstra가 제안)
음이 아닌 정수형 변수(S)
- 초기화 연산, P(), V()로만 접근 가능
- P: Probern(검사), V: Verhoegn(증가)
  - 초기화 연산 : S 변수에 초기 값을 부여하는 연산
  - P(), V() 연산
  - 모두 Indivisible 연산
    - OS support
    - 전체가 한 instruction cycle에 수행 됨
임의의 S 변수 하나에 Ready Queue 하나가 할당 됨

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

상호배제 문제 (Mutual exclusion)

active = 1 : 임계 지역을 실행중인 프로세스 없음

active = 2 : 임계 지역을 실행중인 프로세스 없음

프로세스 동기화 문제 (Process synchronization problem)
- 프로세스들의 실행 순서 맞추기
  - 프로세스들은 병행적이며, 비동기적으로 수행

3. 생산자-소비자 문제 (Producer-Consumer problem)

생산자(Producer) 프로세스 : 메시지를 생성하는 프로세스 그룹
소비자(Consumer) 프로세스 : 메시지를 전달받는 프로세스 그룹

생산자-소비자 문제 with single buffer

생산자-소비자 문제 with N-buffers

4. Reader-Writer 문제

Reader : 데이터에 대해 읽기 연산만 수행
Write : 데이터에 대해 갱신 연산을 수행
데이터 무결성 보장 필요
- Reader들은 동시에 데이터 접근 가능
- Writer들(또는 reader와 write)이 동시 데이터 접근 시 , 상호배제(동기화) 필요

해결법
- Reader/Writer에 대한 우선권 부여
- reader preference solution
- writer preference solution

Reader preference solution

- 세마포어의 가장 큰 특징

No busy waiting -> pro
- 기다려야 하는 프로세스는 block(asleep) 상태가 됨
Semaphore queue에 대한 wake-up 순서는 비결정적 -> con
- Starvation problem

2.2.1 - Binary Semaphore

S가 0과 1 두 종류의 값만 갖는 경우
상호배제나 프로세스 동기화의 목적으로 사용

2.2.2 - Counting Semaphore

S가 0이상의 정수 값을 가질 수 있는 경우
Producer-Consumer 문제 등을 해결하기 위해 사용

2.3. 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

Producer-Consumer problem

- Eventcount/Sequencer의 특징

No busy waiting
No starvation
- FIFO scheduling for Qe
Semaphore 보다 더 low-level control이 가능

📌Language-Level solution(Monitor)

- High-level Mechanism

Monitor
- Language-level constructs
- Object-Oriented concept과 유사
- 사용이 쉬움
~~Path expressions~~
~~Serializers~~
~~Critical region, conditional critical region~~

- Monitor

공유 데이터와 Critical section의 집합
Conditional variable
- wait(), signal() operations

- 모니터의 구조

Entry queue (진입 큐)
- 모니터 내의 procedure 수만큼 존재

Mutual exclusion
- 모니터 내에는 항상 하나의 프로세스만 진입 가능
- 랭귀지가 보장해줌

Information hiding (정보 은폐)
- 공유 데이터는 모니터 내의 프로세스만 접근 가능

Condition queue (조건 큐)
- 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기

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

- 모니터 : 자원 할당 문제

- 모니터 : 자원 할당 시나리오

자원 R 사용 가능

모니터안에 프로세스 없음

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

자원 R이 Pj에가 할당 됨

프로세스 Pk가 R 요청, Pm 또한 R 요청

Pj가 R 반환

R_Fee.signal() 호출에 의해 Pk가 wake up

자원 R이 Pk에게 할당 됨

Pj가 모니터 안으로 돌아와서, 남은 작업 수행

- 모니터 : Producer-Consumer Problem

- 모니터 : Reader-Writer Problem

reader/writer 프로세스들간의 데이터 무결성 보장 기법
writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함
모니터 구성
- 변수 2개
-> 현재 읽기 작업을 진행하고 있는 reader 프로세스의 수
->현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시
- 조건 큐 2개 : reader/writer 프로세스가 대기해야 할 경우에 사용
- 프로시져 4개 : reader(wirter) 프로세스가 읽기(쓰기) 작업을 원할 경우에 호출, 읽기(쓰기) 작업을 마쳤을 때 호출