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

Slides:



Advertisements
Similar presentations
DB 후루룩 & ONE EYED JACK Collaboration_ ★. 다중 사용자 환경에서 둘 이상의 트랜잭션이 동시에 접속하여 해당 연산을 수행할 때, 문제 점이 전혀 발생하지 않도록 트랜잭션의 수행 을 적절히 제어해 주는 것을 말함. DBMS 예금 입출금 예금.
Advertisements

Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
A 장형태.  병행프로세스 개요  상호배제 (Mutual Exclusion)  상호배제 ( 세마포어 )  모니터 (monitor)  프로세스간 2 가지 통신방법.
컴퓨터와 인터넷.
프로세스 동기화(Process Synchronization)
운영체제 Chapter 3 병형 프로세스 박요안.
운영체제 3주차 정리 박 남 규.
인공지능실험실 석사 2학기 이희재 TCP/IP Socket Programming… 제 11장 프로세스간 통신 인공지능실험실 석사 2학기 이희재
제 6장 프로세스 간 동기화 및 통신 6.1 개요 6.2 병행 처리의 문제점
연결리스트(linked list).
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
제 7 장 교착 상태 (Deadlocks) 7.1 시스템 모델 (System Model)
Concurrency: Deadlock and Starvation
Linux System Programming
운영체제 4장 요약정리(CPU 스케줄링) 2A 박훈.
제 6 장 프로세스 동기화 (Process Synchronization)
4장 병행 프로세스 병행성의 원리를 이해한다 병행 프로세스 수행과 관련된 상호 배 제 해결방안을 알아본다
CPU wait signal mutex 큐 준비 큐 … wait(mutex) 임계구역 signal(mutex) …
Chapter 6. 프로세스 동기화(Process Synchronization)
UNIT 07 Memory Map 로봇 SW 교육원 조용수.
오브젝트 조합 회로 IT CookBook, VHDL을 이용한 디지털 회로 입문.
Fundamentals of Database Systems R. A. Elmasri and S. B. Navathe
07. 디바이스 드라이버의 초기화와 종료 김진홍
TCP/IP 응용 프로그램에 적용 가능한 다양한 소켓 옵션을 이해하고 활용한다.
제 6장 트랜잭션 트랙잭션 동시성 제어 복구.
                              데이터베이스 프로그래밍 (소프트웨어 개발 트랙)                               퍼스널 오라클 9i 인스톨.
23장. 구조체와 사용자 정의 자료형 2.
모바일 자바 프로그래밍 JDBC / WAP Ps lab 오민경.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
제 19 장 (Oracle) 오라클에서 동시성 제어 (MVCC)
트랜잭션 처리(Transaction Processing)
03. 병행 프로세스 (Parallel Process)
Chapter 6. 프로세스 동기화(Process Synchronization)
제6장 프로세스 동기화(Process Synchronization)
4 병행 프로세스와 상호배제.
C#.
운영체제 (Operating Systems) (Process Synchronization)
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
UNIT 07 Memory Map 로봇 SW 교육원 조용수.
27장. 모듈화 프로그래밍.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
제 6 장 프로세스 동기화 (Process Synchronization)
병행 프로세스 이나현.
HTTP 프로토콜의 요청과 응답 동작을 이해한다. 서블릿 및 JSP 를 알아보고 역할을 이해한다.
24장. 파일 입출력.
자바 5.0 프로그래밍.
2. 상호배제와 동기화 01 program versionone; // 첫 번째 버전
2장. 변수와 타입.
제 19 장 데이터베이스에서 동시성 제어를 위한 프로토콜에 대한 개요
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
Fucntion 요약.
병행프로세스의개요 주세호.
알고리즘 알고리즘이란 무엇인가?.
Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수
오라클 11g 보안.
.Net Web Application 2007 컴퓨터공학실험(Ⅰ)
제 8장. 클래스의 활용 학기 프로그래밍언어및실습 (C++).
14 뷰(View) 뷰의 개념 뷰 관리.
병행 프로세스 병행처리는 프로세스들이 서로 관계없이 독립적으 로 수행 가능하고 다른 프로세스들과 협력을 필요로 하면서 기능 수행 3.1 개요 parbegin/parend 제어문 : 순차적인 수행으로부터 여러 개의 동시 수행으로 갈라짐을 지시하는 명령어와 여러 개의 동시.
멀티미디어시스템 제 5 장. 멀티미디어 데이터베이스 개념 IT응용시스템공학과 김 형 진 교수.
System Security Operating System.
10주 MariaDB에서 트랜잭션 지원 및 동시성 제어 기능
06. 디바이스의 등록과 해제 김진홍
DataScience Lab. 박사과정 김희찬 (화)
File IO 정보물리.
 6장. SQL 쿼리.
임시테이블과 테이블변수 SQLWorld Study Group - 최명환 -.
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
병행 프로세스(Parallel Process)
2. 프로세스 B 안우진 - 운영체제 -.
Presentation transcript:

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 큐 준비 큐

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했다고 모니터를 떠난 것은 아님

변수 선언 프로시져 초기화 코드 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. 조건 구조체 변수 선언 프로시져 초기화 코드

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

x.wait x.signal 조건 변수(x)의 구현 x-count := x-count +1; if x-count > 0 if next-count > 0 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

조건부 대기 구조체 모니터 안에서의 프로세스의 재개 순서를 제어 예) 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 자원 사용 예정 시간 프로그래머가 실수/고의로 위반 가능

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

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>라는 로그를 추가로 저장 탐색/회복 시간 절약

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

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

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

T0 T1 T1, T2의 스케쥴 T1(2단계가 아닌 록킹) T'1(2단계 록킹) T11 Lock A T12 A 변경 T13 Unlock A T21 Lock A T22 A 변경 T23 Lock B T24 Unlock A T25 B 변경 T26 Unlock B T14 Lock B T15 B 변경 T16 Unlock B T1(2단계가 아닌 록킹) T11 LOCK A T12 A := A + 100 T13 UNLOCK A T14 LOCK B T15 B := B + 100 T16 UNLOCK B T'1(2단계 록킹) T'11 LOCK A T'12 A := A + 100 T'13 LOCK B T'14 UNLOCK A T'15 B := B + 100 T'16 UNLOCK B 직렬화 불가 => 무결성 깨짐 A T0 T1 B

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 나머지 경우: 수행

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

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