2024. 1. 24. 20:35ㆍ프로그래밍 공부/OS
Process Synchronization (동기화)
다중 프로그래밍 시스템
- 여러 개의 프로세스들이 존재
- 프로세스들은 서로 독립적으로 동작 동시
- 공유 자원 또는 데이터가 있을 때, 문제 발생 가능
동기화 (Synchronization)
- 프로세스들이 서로 동작을 맞추는 것
- 프로세스들이 서로 정보를 공유하는 것
Asynchronous and Concurrent P's
비동기적(Asunchronous) PA PB
- 프로세스들이 서로에 대해 모름
병행적 (Concurrent)
- 여러 개의 프로세스들이 동시에 시스템에 존재
병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있음
Terminologies
Shared data (공유 데이터) or Critical data
- 여러 프로세스들이 공유하는 데이터
Critical section (임계 영역)
- 공유 데이터를 접근하는 코드 영역(code segment)
Mutual exclusion (상호배제)
- 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것
Critical Section (example)
process-Pi process-Pj
+1 +1
sdata ← sdata + 1; → 0 2 ← sdata ← sdata + 1;
sdata
sband
memory
Note
기계어 명령(machine instruction)의 특성
- Atomicity(원자성), Indivisible (분리불가능)
- 한 기계어 명령의 실행 도중에 인터럽트 받지 않음
기계어로 번역한 결과
process - Pi process - Pj
Assembly s = s + 1
① Load Ri, sdata ↘ 2 ↙ Load Rj, sdata Ⓐ
② Add Ri, 1 1 0 1 Add Rj, 1 Ⓑ
③ Store Ri, sdata ↗ sdata ↖ Store Rj, sdata Ⓒ
-CPU->
ready. running
<-prepare-
명령 수행 과정(1)
- ① → ② → ③ → Ⓐ → Ⓑ → Ⓒ 또는 Ⓐ → Ⓑ → Ⓒ → ① → ② → ③
- 결과 sdata = 2
명령 수행 과정(2)
- ① → ② → Ⓐ → Ⓑ → Ⓒ → ③
- 결과 sdata = 1
Race condition
Mutual Exclusion (상호배제)
1단계 2단계
P1 P1 P2
P2 | P1 임계 영역 진입 |
프로세스 | ↓
↓ X
P1 P1
공유 메모리 공유 메모리
(임계 영역) (임계 영역)
상호배제의 개념
Mutual Exclusion Methods
Mutual exclusion primitives
- enterCS() primitive
* Critical section 진입 전 검사
* 다른 프로세스가 critical section 안에 있는지 검사
- exitCS() primitive
* Critical section을 벗어날 때의 후처리 과정
* Critical section을 벗어남을 시스템이 알림
Pa Pb
enterCS(CSk) enterCS(CSk)
Critical Section CSk
exitCS(CSk) exitCS(CSk)
Requirements for ME primitives
Mutual exclusion (상호배제)
- Critical section (CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지
Progress (진행)
- CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해하면 안됨
Bounded waiting (한정대기)
- 프로세스의 CS 진입은 유한시간 내에 허용되어야 함
Two Process Mutual Exclusion
ME Primitives version 1
P0 P1
repeat turn repeat
...... 0 ......
while (turn = 1) do while (turn = 0) do
endwhile; endwhile;
Critical Section
turn ← 1; turn ← 0;
....... .......
until(false); until(false);
Progress 조건 위배
- Why?
* P0이 critical section에 진입하지 않는 경우
* 한 Process가 두 번 연속 CS에 진입 불가
ME Primitives version 2
P0 P1
repeat repeat
...... ......
while (flag[1]) do flag[0] flag[1] while (flag[0]) do
endwhile; false false endwhile;
flag[0] ← true; flag[1] ← true;
Critical Section
flag[0] ← false; flag[1] ← false;
....... .......
until(false); until(false);
Mutual exclusion 조건 위배
- Why?
ME Primitives version 3
P0 P1
repeat repeat
...... ......
flag[0] ← true; flag[0] flag[1] flag[1] ← true;
while (flag[1]) do false false while (flag[0]) do
endwhile; endwhile;
Critical Section
flag[0] ← false; flag[1] ← false;
....... .......
until(false); until(false);
Progress, Bounded waiting 조건 위배
- Why?
Mutual Exclusion Solutions
SW solutions
- Dekker's algorithm (Peterson's algorithm)
- Dijkstra's algorithm, Knuth's algorithm, Eisenberg and
McGuire's algorithm, Lamport's algorithm
HW solution
- TestAndSet (TAS) instruction
OS supported SW solution
- Spinlock
- Semaphore
- Eventcount/sequencer
Language-Level solution
- Monitor
Dekker's Algorithm
Two process ME을 보장하는 최초의 알고리즘
P0 P1
repeat repeat
...... ......
flag[0] ← true; ¶ flag[0] flag[1] flag[1] ← true; ¶
while (flag[1]) do false false while (flag[0]) do
if (turn = 1) then 0 if (turn = 0) then
begin turn. begin
flag[0] ← false; ¶ flag[0] ← false;
while (turn = 1) do while (turn = 0) do
endwhile; endwhile;
flag[0] ← true; ¶ flag[0] ← true;
end; end;
endwhile; endwhile;
①↓ Critical Section
turn ← 1; turn ← 0;
flag[0] ← false; flag[1] ← false;
....... .......
until(false); until(false);
Peterson's Algorithm
Dekker's algorithm보다 간단하게 구현
P0 P1
repeat repeat
...... flag[0] flag[1] ......
flag[0] ← true; false false flag[1] ← true;
turn ← 1; turn ← 0;
while (flag[1] and 0 while (flag[0] and
turn = 1) do turn turn = 0) do
endwhile; endwhile;
Critical Section
flag[0] ← false; flag[1] ← false;
....... .......
until(false); until(false);
②
N-Process Mutual Exclusion
다익스트라 Dijkstra
- 최초로 프로세스 n개의 상호배제 문제를 소프트웨적으로 해결
- 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법, 가장 짧은 평균 대기시간 제공
크누스 knuth
- 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당
- 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야 함
램포트 lamport
- 사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘 (Bakery algorithm)
- 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그 중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당함
핸슨 brinch Hansen
- 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것
- 대기시간과 실행시간을 이용하는 모니터 방법
- 분산 처리 프로세서 간의 병행성 제어 많이 발표
Dijkstra's Algorithm
Dijkstra 알고리즘의 flag[] 변수
| flag[] 값 | 의미 |
| idle | 프로세스가 임계 지역 진입을 시도하지 않고 있을 때 |
| want-in | 프로세스의 임계 지역 진입 시도 1단계일 때 |
| in-CS | 프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때 |
프로세스 Pi
repeat
......
repeat
/* 임계 지역 진입 시도 1단계 */
flag[i] ← want-in;
while (turn ≠ i) do 내가 아니면 flag[1] flag[n]
if (flag[turn] = idle) then idle ··· idle
turn ← 1;
endwhile;
/* 임계 지역 진입 시도 2단계 */
flag[i] ← in-CS; 0
j ← 0; turn
while ((j < n) and (j = i or flag[j] ≠ in-CS)) do
j ← j + 1;
endwhile;
until (j ≥ n); (j < n이면 위의 내용을 반복한다)
Critical Section
flag[i] ← idle;
.......
until(false);
SW Solutions
SW solution들의 문제점
- 속도가 느림
- 구현이 복잡한
- ME primitive 실행 중 preemption 될 수 있음
* 공유 데이터 수정 중은 interrupt를 억제함으로써 해결가능
Overhead 발생
- Buisy waiting
* Inefficient
Mutual Exclusion Solutions
SW solutions
- Dekker's algorithm (Peterson's algorithm)
- Dijkstra's algorithm, Knuth's algorithm, Eisenberg and
McGuire's algorithm, Lamport's algorithm
HW solution
- TestAndSet (TAS) instruction
OS supported SW solution
- Spinlock
- Semaphore
- Eventcount/sequencer
Language-Level solution
- Monitor
Synchronization Hardware
TestAndSet (TAS) instruction
- Test와 Set을 한번에 수행하는 기계어
- Machine instruction
* Atomicity, Indivisible
* 실행 중 interrupt를 받지 않음 (preemption 되지 않음)
- Busy waiting
* Inefficient
TAS Instruction
TestAndSet 명령어
// target을 검사하고, target 값을 true로 설정
boolean TestAndSet (boolean *target) {
boolean temp = *target; // 이전 값 기록
*target = true; // true로 설정 한번에 수행
return temp; // 값 반환 (Machine instruction)
}
target
← A ← true
temp
← A
ME with TAS Instruction
Initially
lock = false;
Pi
repeat
......
while (TAS(lock)) do
endwhile
Critical Section
lock ← false;
......
until (false);
3개 이상의 프로세스의 경우, Bounded waiting 조건 위배
- Why?
N-Process mutual exclusion
do // 프로세스 Pi의 진입 영역
{
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = TestAndSet(&lock);
waiting[i] = false;
// 임계 영역
// 탈출 영역
j = (i + 1) % n;
while ((j != i) && !waiting[j]) // 대기 중인 프로세스를 찾음
j = (j + 1) % n;
if (j == i) // 대기 중인 프로세스가 없으면
lock = false; // 다른 프로세스의 진입 허용
else // 대기 프로세스가 있으면 다른 순서로 임계 영역에 진입
waiting[j] = false; // Pj가 임계 영역에 진입할 수 있도록
// 나머지 영역
} while (true);
HW solution
장점
- 구현이 간단
단점
- Buisy waiting
* Inefficient
Busy waiting 문제를 해소한 상호배제 기법
- Semaphore
* 대부분의 OS들이 사용하는 기법
Mutual Exclusion Solutions
SW solutions
- Dekker's algorithm (Peterson's algorithm)
- Dijkstra's algorithm, Knuth's algorithm, Eisenberg and
McGuire's algorithm, Lamport's algorithm
HW solution
- TestAndSet (TAS) instruction Busy waiting!
OS supported SW solution
- Spinlock
- Semaphore
- Eventcount/sequencer
Language-Level solution
- Monitor
Spinlock
정수 변수 S = A + 1
초기화, P() V() 연산으로만 접근 가능
- 위 연산들은 indivisible (or atomic) 연산
* OS support 보장
* 전체가 한 instruction cycle에 수행됨
물건 꺼낸 개수 (Lock)
P(S) { 없다면
while (S ≤ 0) do
endwhile;
S ← S - 1;
}
물건 집어넣은 개수 (Unlock)
V(S) {
S ← S + 1;
}
Spinlock
Pi Pj
repeat active repeat
...... 1→0→1 ......
P(active); P(active);
Critical Section
V(active); V(active);
...... ......
until (false); until (false);
active = 1 : 임계 지역을 실행중인 프로세스가 없음
active = 0 : 임계 지역을 실행중인 프로세스가 있음
CPU
Pj
Pi
멀티 프로세서 시스템에서만 사용가능
Busy waiting!
Mutual Exclusion Solutions
SW solutions
- Dekker's algorithm (Peterson's algorithm)
- Dijkstra's algorithm, Knuth's algorithm, Eisenberg and
McGuire's algorithm, Lamport's algorithm
HW solution
- TestAndSet (TAS) instruction
OS supported SW solution
- Spinlock P.V 보장 Busy waiting!
- Semaphore
- Eventcount/sequencer
Language-Level solution
- Monitor
Semaphore
1965년 Dijkstra가 제안
Busy waiting 문제 해결
음이 아닌 정수형 변수 (S)
- 초기화 연산, P(), V() 로만 접근 가능
* P: Probern (검사)
* V: Verhogen (증가)
임의의 S 변수 하나에 ready queue 하나가 할당됨
Semaphore
0 or 1
Binary semaphore
- S가 0과 1 두 종류의 값만 갖는 경우
- 상호배제나 프로세스 동기화의 목적으로 사용
s ≥ 0
Counting semaphore
- S가 0 이상의 정수값을 가질 수 있는 경우
- Producer-Consumer 문제 등을 해결하기 위해 사용
* 생산자- 소비자 문제
Semaphore
초기화 연산
* S 변수에 초기값을 부여하는 연산
P() 연산, V() 연산
S: 물건수
P(S) 연산 LOCK
if (S > 0)
then S ← S - 1; ↓
else wait on the queue Qs;
물건이 X 대기실 Pi Block
V(S) 연산 UNLOCK
어떤
if (∃ waiting processes on Qs)
then wakeup one of them;
else S ← S + 1;
모두 indivisual 연산
- OS support 보장!
- 전체가 한 instruction cycle에 수행됨
Semaphore in OS
Windows
- MSDN: https://msdn.microsoft.com/en-us/library/windows/desktop/ms685129(v=vs.85).aspx
세마포 개체 - Win32 apps
세마포 개체는 0과 지정된 최대값 사이의 개수를 유지하는 동기화 개체입니다.
learn.microsoft.com
HANDLE WINAPI CreateSemaphore(
_In_opt_ LPSECURITY_ATTRIBUTES lpSemaphoreAttributes,
_In_ LONG lInitialCount,
_In_ LONG lMaximumCount,
_In_opt_ LPCTSTR lpName
);
Unix/Linux
- System V: https://docs.oracle.com/cd/E19683-01/8165042/auto32/index.html
Solaris 9 Operating System Product Library Documentation
Sun Enterprise 6x00, 5x00, 4x00, and 3x00 Systems Dynamic Reconfiguration User's Guide PDF
docs.oracle.com
Semaphore
Semahore로 해결 가능한 동기화 문제들
- 상호배제 문제
* Mutual exclusion
- 프로세스 동기화 문제
* process synchronization problem
- 생산자-소비자 문제
* producer-consumer problem
- Reader-writer 문제
- Dining philosopher problem
- 기타
Mutual exclusion
Pi Pj
repeat active repeat
...... 1→0→1 ......
P(active); Pi P(active);
Critical Section
V(active); V(active);
...... ......
until (false); until (false);
active = 1 : 임계 지역을 실행중인 프로세스가 없음
active = 0 : 임계 지역을 실행중인 프로세스가 있음
Process synchronization
- Process들의 실행 순서 맞추기
* 프로세스들은 병행적이며, 비동기적으로 수행
process-Pi process-Pj
... 프로세스 Pi는 ...
프포세스 Pj가
Li: ==== Lj 지점을 통과할 때까지 Lj: ======
... ...
process-Pi process-Pj
... → 대기 ← wakeup ...
↓ 물건이 x
Li: P(sync); ↔ 0 ↔ Lj: V(sync) ↓ 반납
sync
... ...
Producer-Consumer problem
- 생산자(Producer) 프로세스
* 메시지를 생성하는 프로세스 그룹
- 소비자(Consumer) 프로세스
* 메세지 전달받는 프로세스 그룹
라인 프린터 드라이버 -생산→ 문자 -소비→ 라인 프린터
컴파일러 -생산→ 어셈블리 코드 -소비→ 어셈블러
어셈블러 -생산→ 적재 모듈 -소비→ 로더
Producer Shared memory buffer Consumer
process process
Semaphore
Producer-Consumer problem with single buffer
| (shared variables) var consumed 소비? : semaphore ← 1, → 0 → 1 produced 생산? : semaphore ← 0, →1 →0 buffer : message; |
|
| Producer Pi -------> buffer repeat ... create a new message M; P(consumed); 비었나? buffer ← M; V(produced); 내 생산? ... until(false); |
------> Consumer Cj repeat ... P(produced); 생산 ok? -> 대기실 m ← buffer; V(consumed); create a new message m; ... until(false); |
Producer-Consumer problem with N-buffers
포인터 이동 방향 buffer[0] out
↗ buffer[n-1] ● ← 다음 여기에서 받음(제거 포인터)
buffer[1]
생산자 -버퍼로 보냄→ ● -버퍼에서 받음→ 소비자
buffer[2]
다음에 여기로 보냄(삽입 포인터)→ ● ↙
in ● ● 포인터 이동 방향
↗↙↓→ ● 데이터 버퍼에 저장
Producer-Consumer problem with N-buffers
| (shared variables) = N (아래 둘의 합은 항상 N이다) var nrfull : semaphore ← 0, // 채워진 buffer 수 nrempty : semaphore ← N, // 비워 있는 buffer 수 mutexP (producer) : semaphore ← 1, mutexC (consumer) : semaphore ← 1, buffer : array[0..N-1] of message; in, out : 0..N-1 ← 0, 0; |
|
| 여러명 Producer Pi -------> buffers repeat ↗ ... 공간?? create a new message M; ↙ P(mutexP); //Critical Section P(nrempty); >0 ↓ Qe 대기 (공간 확인) buffer[in] ← M; in ← (in + 1) mod N; circular Q V(nrfull); →+1 V(mutexP); →wakeup→ ... until(false); |
여러명 ------> Consumer Cj repeat ... P(mutexC); ↓ //Critical Section P(nrfull); 물건?? > 0 대기 (물건 확인) m ← buffer[out]; in ← (in + 1) mod N; V(nrempty); 공간 + 1 V(mutexC); ... until(false); |
Semaphore
Reader-Writer problem
- Reader
* 데이터에 대해 읽기 연산만 수행
- Writer
* 데이터에 대해 갱신 연산을 수행
데이터 무결성 보장 필요
- Reader들은 동시에 데이터 접근 가능
- Writer들(또는 reader와 write)이 동시 데이터 접근 시,
상호배제(동기화) 필요
해결법
- reader / writer 에 대한 우선권 부여
* reader preference solution
* writer preference solution
writer solution?
Reader-Writer problem (reader preference solution)
| (shared variables) var wmutex, rmutex : semaphore := 1, 1, nreaders : integer := 0. //reader의 수 |
|
| Reader Ri repeat ... //1: enbrace read CS P(rmutex); if (nreaders = 0) then P(wmutex); 읽을→wx endif; nreaders ← nreader + 1; V(rmutex); Perform read operations; // ←0 //2 exit. CS P(rmutex); nreaders ← nreader - 1; if (nreaders = 0) then V(wmutex); ←X endif; V(rmutex); ... until(false); |
Writer Wj repeat ... P(wmutex); Perform write operations; V(wmutex); ... until(false); |
Semaphore
○→대기열
No busy waiting
- 기다려야 하는 프로세스는 block(asleep) 상태가 됨
Semaphore queue에 대한 wake-up 순서는 비결정적
- Starvation problem
V(S)
∃wait
→wake up one of them
Eventcount/Sequencer
BW ok!
∃wait
→wake up one of them
은행의 번호표와 비슷한 개념
Sequencer A → A + 1
- 정수형 변수
- 생성시 0으로 초기화, 감소하지 않음
- 발생 사건들의 순서 유지
- ticket() 연산으로만 접근 가능
ticket(S)
- 현재까지 ticket() 연산이 호출 된 횟수를 반환
- Indivisible operation
0 → 1
대기번호
0078
ticket
Eventcount/Sequencer
687 띵동
Eventcount
- 정수형 변수
- 생성시 0으로 초기화, 감소하지 않음
- 특정 사건의 발생 횟수를 기록
- read(E), advance(E), await(E, v) 연산으로만 접근 가능
read(E)
- 현재 Eventcount 값 반환
advance(E)
- E ← E + 1
- E를 기다리고 있는 프로세스를 깨움 (wake-up)
await(E, v)
- V는 정수형 변수 10 15 기다린다
번호표
- if (E < v) 이면 E에 연결된 Qe에 프로세스 전달(push)
및 CPU scheduler 호출 대기열
Eventcount/Sequencer
Mutual exclusion
Pi
repeat
......
1. 2. 3
↓↓P2 ↓ ↓
// P(S)
0 v ← ticket(S); S: 0 → 1 → 2 v: 0
await(E, v); E: 0. v: 0 → 1 Qe 대기열 1번
P1 ○ ↓ P2○ Critical Section
↓
// V(S)
advance(E); 띵동!
......
until(false);
SP:
E |S
Producer-Consumer problem
| (shared variables) var Pticket, Cticket : sequencer, In, Out : eventcount, Circular buffer : array[0..N-1] of message; |
|
| Producer Pi 0 | 1 | ... | N-1 var t : integer; repeat ... create a new message M; // P t ← ticket(Pticket); // P 생산자를 위한 번호표 await(In, t); ↓1 // CS await(Out, t - N + 1); ←공간이 있니? buffer[t mod N] ← M; // V advance(In); ↓ ... until(false); |
Consumer Cj var u : integer; repeat ... // P u ← ticket(Cticket); await(Out, t); ↓1 // CS await(In, u + 1);←물건이 있니? m ← buffer[u mod N]; // V advance(Out); → 꺼내간 수 Consume the message m; ↓ ... until(false); |
공간 ≥ 1
N - t + out
out ≥ t - N + 1
↔ out ≤ t - N + 1
→await(out)
공간이 있니?
물건수 ≥ 1
↔ 물건수 < 1
IN - U < 1
IN < U + 1
await( , )
m
꺼내간 수
↓
Eventcount/Sequencer
No busy waiting
No starvation
- FIFO scheduling for Qe "순선 control"
Semaphore보다 더 low-level control이 가능
Mutual Exclusion Solutions
SW solutions
- Dekker's algorithm (Peterson's algorithm)
- Dijkstra's algorithm, Knuth's algorithm, Eisenberg and
McGuire's algorithm, Lamport's algorithm
HW solution
- TestAndSet (TAS) instruction
OS supported SW solution
- Spinlock
- Semaphore
- Eventcount/sequencer
low-level mechanisms
Flexible
Difficult to use
- Error-prone logical error↑
High level
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
1명
==ㅁㅁ ------→책방 ←----→ ㅁㅁ==
==ㅁㅁ ------→ MAX1명 ←----→ ㅁㅁ==
Monitor entry Critical data 책 Condition
queues & queues
Critical sections
←----→ ㅁㅁ==
Waiting signaler
queue
Monitor의 구조
Entry queue (진입 큐)
- 모니터 내의 procedure 수만큼 존재
특성
Mutual exclusion → Language가 보장!!
- 모니터 내에는 항상 하나의 프로세스만 진입 가능
Informaiton hiding (정보 은폐)
- 공유 데이터는 모니터 내의 프로세스만 접근 가능
Condition queue (조건 큐) 조건을 기다리는 큐
- 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기 실
Signal queue (신호제공자 큐) 전화부스
- 모니터에 항상 하나의 신호제공자 큐가 존재
- signal() 명령을 실행한 프로세스가 임시 대기
Monitor in Languages
language support
Monitor Class
C# C++ F# VB
Class Monitor
Java
Monitor
자원 할당 문제
Semaphore
E/S 시험문제
Computer
책방
책
R 4개 대기실
==ㅁㅁ ------ -| ㅁ ←----→ ㅁㅁ==
entry queues for | R_Available condition queue
releaseR() | R_Free 책을 빌릴 수 있어?
반납 ---------------|
==ㅁㅁ |
entry queues for-----| |
requestR() ㅁ ㅁ ←----→ ㅁㅁ==
대출 signaler queue
requestR() releaseR() 1개
코드
monitor resourceRiAllocator;
var RilsAvailable : boolean,
RilsFree : condition;
procedure requestR(); 대출
begin
if (-R_Available) then
R_Free.wait(); → 기다리기
R_Available ← false;
end;
procedure releaseR(); 반납
begin
R_Available ← true;
R_Free.wait();
end;
begin
RilsAvailable ← true;
end;
자원 할당 시나리오
- 자원 R 사용 가능
- Monitor 안에 프로세스 없음
Initial monitor state
==ㅁㅁ ------ -| 1 ←----→ ㅁㅁ==
entry queues for | R_Available T/F condition queue
releaseR() | R_Free
---------------|
==ㅁㅁ |
entry queues for-----| |
requestR() ㅁ ㅁ ←----→ ㅁㅁ==
signaler queue
requestR() releaseR()
R
자원 할당 시나리오
- 프로세스 Pj가 모니터 안에서 자원 R을 요청
Monitor state 1
책방
MAX
1명 대기실
==ㅁㅁ ------ -| 1→ 0 ←----→ Pk Pm==
entry queues for | R_Available T/F condition queue
releaseR() | R_Free 책을 빌릴 수 있어?
반납 ---------------|
==Pj Pk |
entry queues for-----| |
requestR() Pk ㅁ ←----→ ㅁㅁ==
대출 Pj signaler queue
requestR() releaseR() 1개
Pj → R
자원 할당 시나리오
- 자원 R이 Pj에게 할당 됨
- 프로세스 Pk가 R 요청, Pm 또한 R 요청
Monitor state 2
책방
MAX
1명 대기실
==ㅁPj ------ -| 0 → 1→0 ←----→ Pk Pm==
entry queues for | R_Available condition queue
releaseR() | R_Free 책을 빌릴 수 있어?
반납 ---------------|
==ㅁㅁ |
entry queues for-----| |
requestR() ㅁ ㅁ ←----→ Pj ㅁ==
대출 Pk Pj signaler queue
requestR() releaseR() 1개
Pj ← R
Pk
자원 할당 시나리오
- Pj가 R 반환
- R_free.signal() 호출에 의해 Pk가 wakeup
Monitor state 3
책방
MAX
1명 대기실
==ㅁㅁ ------ -| 0→ 1→0 ←----→ Pmㅁ==
entry queues for | R_Available condition queue
releaseR() | R_Free 책을 빌릴 수 있어?
반납 ---------------|
==ㅁㅁ |
entry queues for-----| |
requestR() ㅁ ㅁ ←----→ Pj ㅁ==
대출 Pk signaler queue
requestR() releaseR() 1개
R
자원 할당 시나리오
- 자원 R이 Pk에게 할당 됨
- Pj가 모니터 안으로 돌아와서, 남은 작업 수행
Monitor state 4
language 보장
==ㅁㅁ ------ -| 0 ←----→ Pmㅁ==
entry queues for | R_Available condition queue
releaseR() | R_Free 책을 빌릴 수 있어?
반납 ---------------|
==ㅁㅁ |
entry queues for-----| |
requestR() ㅁ ㅁ ←----→ Pj ㅁ==
대출 Pj 남은일 signaler queue
requestR() releaseR()
Pk ← R
Monitor
Producer consumer Problem
CircularQ N CQ
P entry queue buffer[0]
for fillBuf() buffer[1] C bufHasData
=ㅁㅁㅁ ㅁ buffer[2] ㅁㅁㅁ=
=ㅁㅁㅁ ㅁ buffer[3] ㅁㅁㅁ=
C entry queue buffer[4] P bufHasSpace ?
for emptyBuf() buffer[5]
....
buffer[N-1]
(shared) 위치
critcal 0 0 0
data P→in C→out validBufs 물건수
fillBuf() emptyBuf() signaler queue
ㅁ ㅁ ㅁㅁㅁ=
Monitor (Producer-Consumer Problem)
코드
monitor ringbuffer;
var buffer : array[0..N-1] of message,
validBufs : 0..N,
in : 0..N-1,
out : 0..N-1,
vufHasData, bufHasSpace : condition;
P
procedure fillBuf(data : message);
begin 물건수 = N → full!
if (validBufs = N) then bufHasSpace.wait(); 공간?
buffer[in] ← data; ↓
validBufs ← validBufs + 1;
in ← (in + 1) mod N; Circular Q
vufHasData.signal(); ↑
end;
procedure emptyBuf(var data : message); Consumer
begin
if (validBufs = 0) then bufHasData.wait(); 물건?
data ← buffer[out]; ↓
validBufs ← validBufs - 1;
out ← (out + 1) mod N;
bufHasSpace.signal(); ↓
end;
begin
validBufs ← 0;
in ← 0;
out ← 0;
end;
Monitor
여러명 1명
Reader-Writer Problem
- reader/writer 프로세스들간의 데이터 무결성 보장 기법
- writer 프로세스에 의한 데이터 접근 시에만 상호 배제 및 동기화 필요함
Hint → 숙제
- 모니터 구성
* 변수 2개
현재 읽기 작업을 진행하고 있는 reader 프로세스의 수
현재 writer 프로세스가 쓰기 작업을 진행 중인지 표시
* 조건 큐 2개
reader/writer 프로세스가 대기해야 할 경우에 사용
* 프로시져 4개
reader(writer) 프로세스가 읽기(쓰기) 작업을 원할 경우에 호출,
읽기(쓰기) 작업을 마쳤을 때 호출
코드
monitor readers_and_writers;
var numReaders : integer,
writing : boolean,
readingAllowed, writingAllowed : condition;
procedure beginReading;
begin
if (writing or queue(writingAllowed)) then readingAllowed.wait();
numReaders ← numReaders + 1;
if (queue(readingAllowed)) then readingAllowed.signal();
end;
procedure finishReading:
begin
numReaders ← numReaders - 1;
if (numReaders = 0) then writingAllowed.signal();
end;
procedure beginWriting;
begin
if (numReaders > 0 or writing) then writingAllowed.wait();
writing ← true;
end;
procedure finishWriting:
begin
writing ← false;
if (queue(readingAllowed)) then readingAllowed.signal();
else writingAllowed.signal();
end;
begin
numReaders ← 0;
writing ← false;
end;
Monitor
Dining philosopher problem 생각 ↔ 먹기
- 5명의 철학자
- 철학자들은 생각하는 일, 스파게티 먹는 일만 반복함
- 공유 자원: 스파게티, 포크
- 스파게티를 먹기 위해서는 좌우 포크 2개 모두 들어야 함
철학자5명
Process
Shared data
P3 P4
-∈
-∈ spaghetti -∈
P2 P5
-∈ -∈
↖ P1 ↗
Dining philosopher problem
Pi
do forever
pickup(i);
eating;
putdown(i);
thinking;
end
코드
monitor dining_philosophers;
var numForks : array[0..4] of integer,
ready. : array[0..4] of boolean,
i : integer;
procedure pickup(me); -∈ -∈ 포크 집는다 MAX 1명
var ↓
me : integer; Monitor
begin
if (numForks[me] ≠ 2) then ready[me].wait();
numForks[right(me)] ← numForks[right(me)] - 1;
numForks[left(me)] ← numForks[left(me)] - 1;
end;
procedure putdown(me); 포크 내려놓는다
var
me : integer;
begin
numForks[right(me)] ← numForks[right(me)] + 1;
numForks[left(me)] ← numForks[left(me)] + 1;
if (numForks[right(me)] = 2) then ready[right(me)].signal();
if (numForks[left(me)] = 2) then ready[left(me)].signal();
end;
begin
for i ← 0 to 4 do
numForks[i] ← 2;
end.
Dining philosohper problem. Semaphore =>
현재 사용가능 포크수
P1P2P3P4P5 ready
==ㅁㅁ ------ -| 2 2 2 2 2 ←----→ 방 P0ㅁ== P0
entry queues for | numForks 방 ㅁㅁ== P1
pickup(i) | ...
---------------| 방 ㅁㅁ== P5
==ㅁㅁ | condition queue
entry queues for-----| |
putdown(i) ㅁ ㅁ ←----→ ㅁㅁ==
signaler queue
pickup(i) putdown(i)
Monitor
장점
- 사용이 쉽다 (Software Solution, Semaphore, Event count/Sequencer 보다)
- Deadlock 등 error 발생 가능성이 낮음 실수↓
단점
language ㅁ -Compiler→ Machine Language→ System
- 지원하는 언어에서만 사용 가능 → OpenMP → ML
- 컴파일러가 OS를 이해하고 있어야 함
* Critical section 접근을 위한 코드 생성
'프로그래밍 공부 > OS' 카테고리의 다른 글
| 8 메모리(주기억장치) 관리 (0) | 2024.02.02 |
|---|---|
| 7 Deadlock (0) | 2024.01.31 |
| 5 프로세스 스케줄링 (0) | 2024.01.22 |
| 4 스레드 관리 (0) | 2024.01.21 |
| 3 프로세스 관리 (0) | 2024.01.19 |