CPU wait signal mutex 큐 준비 큐 … wait(mutex) 임계구역 signal(mutex) …

Presentation on theme: "CPU wait signal mutex 큐 준비 큐 … wait(mutex) 임계구역 signal(mutex) …"— Presentation transcript:

1 CPU wait signal mutex 큐 준비 큐 … wait(mutex) 임계구역 signal(mutex) …
프로세스 1 … wait(mutex) 임계구역 signal(mutex) 프로세스 2 … wait(mutex) 임계구역 signal(mutex) 프로세스 3 … wait(mutex) 임계구역 signal(mutex) …... 프로세스 n … wait(mutex) 임계구역 signal(mutex) wait 프로그램 계수기 signal CPU mutex 큐 준비 큐

2 6.7 모니터 (Monitor) 모니터 type : 또 하나의 고수준 동기화 구조체 프로그래머가 정의하는 type 표현 방법:
변수(어떤 순간에 한 instance의 상태를 나타냄) 선언 프로시져: 해당 모니터 type에 적용 가능한 연산들 한 순간에 한 P만 모니터 안에서 활동 보장 (그림 6.19) 조건 변수 : type이 condition인 변수 특별한 동기화가 필요한 경우 (예: 젓가락 문제) var x, y: condition; x.wait; y.signal; (그림 6.20) 세마포의 경우와 다름 : 대기 중인 P가 없으면 signal 효과 없음 signal했다고 모니터를 떠난 것은 아님

3 변수 선언 프로시져 초기화 코드 type dining-philosophers = monitor
var state: array [0..4] of (thinking, hungry, eating); if state[i]  eating then self[i].wait; and state[k+1 mod 5]  eating procedure entry putdown (i: 0..4); type dining-philosophers = monitor var self: array [0..4] of condition; procedure entry pickup (i: 0..4); if state[k+4 mod 5]  eating state[k] := eating; and state[k] = hungry self[k].signal; do state[i] := thinking; procedure test (k: 0..4); state[i] := thinking; state[i] := hungry; test (i+4 mod 5); test (i+1 mod 5); then begin for i := 0 to 4 test (i); begin end; end. 조건 구조체 변수 선언 프로시져 초기화 코드

4 철학자 만찬 문제의 해결 (그림 6.21) 모니터의 구현(세마포의 사용) 교착상태도 해결, 그러나 기아는 가능
모니터의 호출 dp.pickup(i); … eat dp.putdown(i); 모니터의 구현(세마포의 사용) wait(mutex); ... 프로시져 몸체(pickup, …) if next-count > 0 then signal(next) else signal(mutex);

5 x.wait x.signal 조건 변수(x)의 구현 x-count := x-count +1; if x-count > 0
if next-count > then begin then signal(next) next-count := next-count + 1; else signal(mutex); signal(x-sem); wait(x-sem); wait(next) x-count := x-count - 1; next-count := next-count - 1; end; x.wait x.signal

6 조건부 대기 구조체 모니터 안에서의 프로세스의 재개 순서를 제어 예) x.wait(c) 순서가 보장되려면,
모든 프로세스가 아래 순서를 준수해야 한다 R.acquire(t) … 자원접근 R.release; 협조 관계에 있지 않은 프로세스들까지도 감시해야 한다. Type resource-allocation = monitor var busy: boolean; x: condition; procedure entry acquire(time: integer); begin if busy then x.wait(time); busy := true; end; procedure entry release; busy := false; x.signal; end 자원 사용 예정 시간 프로그래머가 실수/고의로 위반 가능

7 6.9 원자성 트랜잭션 (Atomic Transactions)
데이터 일관성(data consistency) 원자적 실행 병행수행 결과=임의 순서 실행 결과 서로 방해하지 않음 (임계구역 상호배제) 논리적 단위 : all or nothing (자동이체의 차변-대변) DB기법 원용(예:파일 처리) 6.9.1 시스템 모델 트랜잭션(transaction) : 하나의 논리적 기능을 수행하는 명령 (동작)들의 집합, 원자성(atomicity) 유지가 중요 T: 디스크상 파일의 자료 항목들을 접근/갱신하는 P 일련의 read/write연산, commit(완성)/abort(취소)로 종료 취소 시 복귀(rollback): 원자성 보장

8 6.9.2 로그 기반 회복 (Log Based Recovery)
단일 T(병행 T)의 관점 기록 우선 로깅(write-ahead logging) 항상 안정(stable) 기억장치에 먼저 기록 Undo(Ti)/Redo(Ti) 시스템 실패 시 <Ti commits>가 없는 T는 모두 Undo(Ti) 6.9.3 검사점 (Checkpoint) 주기적으로 안정 장치에 저장(로그, 갱신된 자료값) 후 <checkpoint>라는 로그를 추가로 저장 탐색/회복 시간 절약

9 6.9.4.1 직렬성 (Serializability)의 판별
6.9.4 병행 원자 트랜잭션 직렬성(serializability) 병행 수행한 결과가 각 T를 순차 실행한 결과와 동일 세마포로 보장 가능, 그러나 지나친 제한 실행 중첩이 필요=>병행성 제어 알고리즘 직렬성 (Serializability)의 판별 직렬 스케쥴: 각 T를 원자적으로 실행 => n!가지 충돌연산(conflicting operation) Oi, Oj가 동일 자료를 접근하고 최소 하나가 write 충돌 직렬화 가능(conflict serializable) 스케쥴 비충돌 연산들끼리의 교체로 직렬 스케쥴로 변형 가능 (그림6-23, 6-24) 중첩 허용  항상 틀림

10 T0 T1 read(A) write(A) read(B) write(B) read(A) write(A) read(B)
-직렬 스케쥴 -충돌이 있지만 직렬화 가능한 스케쥴 T T1 read(A) write(A) read(B) write(B) T T1 read(A) write(A) read(B) write(B) 종속 그래프 T0 T1 A, B

11 6.9.4.2 로킹 프로토콜 (Locking Protocol)
(사전 스케쥴 없이) 직렬성을 보장하기 위한 하나의 수단 자료 항목마다 잠김(lock)을 획득/해제 공유(shared) 모드 잠금: read 가능/write불가 배타(exclusive) 모드 잠금: read/write 모두 가능 직렬성(무결성)을 보장하려면 => 2단계 로킹 프로토콜 성장(growing) 단계: 잠김을 얻기만 하고 해제하지 않음 위축(shrinking) 단계: 해제만 하고 얻지는 않음 직렬성 보장하지만 교착 상태는 해결 못함

12 T0 T1 T1, T2의 스케쥴 T1(2단계가 아닌 록킹) T'1(2단계 록킹) T11 Lock A T12 A 변경
T Unlock A T Lock A T A 변경 T Lock B T Unlock A T B 변경 T Unlock B T Lock B T B 변경 T Unlock B T1(2단계가 아닌 록킹) T LOCK A T A := A + 100 T UNLOCK A T LOCK B T B := B + 100 T UNLOCK B T'1(2단계 록킹) T' LOCK A T' A := A + 100 T' LOCK B T' UNLOCK A T' B := B + 100 T' UNLOCK B 직렬화 불가 => 무결성 깨짐 A T0 T1 B

13 6.9.4.3 타임스탬프(Timestamp) 기반 프로토콜
clock이나 counter로 T의 입장 시간을 기록: TS(Ti) W-타임스탬프: write(Q)를 성공한 T의 최대TS값 R-타임스탬프: read(Q)를 성공한 T의 최대TS값 프로토콜 Ti가 read(Q) 수행 시 TS(Ti) < W-타임스탬프 : 거절, Ti는 roll back TS(Ti)  W-타임스탬프 : 수행, W-타임스탬프 조정 Ti가 write(Q) 수행 시 TS(Ti) < R-타임스탬프 : 거절, roll back TS(Ti) < W-타임스탬프 : 거절, roll back 나머지 경우: 수행

14 로킹이나 TS기법 중 한 가지로만 가능한 경우가 있음
복귀한 T는 새 TS를 가지고 처음부터 재시작 cf. 로킹에서는 새로 시작하지는 않고 기다림 충돌 직렬성 보장, 교착 상태 없음 로킹이나 TS기법 중 한 가지로만 가능한 경우가 있음 T T3 read(B) read(B) write(B) read(A) [그림 6.25] TS 프로토콜로 가능한 스케쥴의 예 로킹으로도 가능

15 wait문 각 P의 모든 compiler가 생성 & 임계구역의 각 P에는 없음 ” . signal문 앞뒤로 분산됨
기존 세마포 임계영역 모니터 병행 트랜잭션 wait문 각 P의 모든 compiler가 생성 & 임계구역의 각 P에는 없음 ” signal문 앞뒤로 분산됨 배타적인 임계구역 region문 모니터 내의 자료 항목 범위 전체 전체 wait ~ signal 하나