Concurrency: Deadlock and Starvation

Slides:



Advertisements
Similar presentations
Chapter 11. Windows Server 2000 & 2003 Windows NT 기반의 NOS 인 Windows Server 2003 에 대해서 일반 사용자가 아닌 관리자 입장에서 알아두 어야 할 몇가지 기능들에 대해서 설명하고 있다.
Advertisements

강백준 ( 정자초 4 학년 ) “3D 프린터 ” 가 세상을 바꿀 것이라고 합니다. 무궁무진한 가능성 : 뭐든지 만들 수 있다 ! 원하는 물건을 돈주고 산다  내가 만든다 !! 미래산업을 바꿀 7 대 파괴적 혁신기술 !!! ( 삼성경제연구소 ) 21 세기 기술혁명 !!
단체교섭 보고 ※ 본교섭 ※ 실무교섭 구 분 날 짜 비 고 상견례 1월19일 단협 시작 본교섭
OS 소개 Introduction 설계목표 기본 용어 Resource Management History.
Flash SSD (Solid State Disk)
Mar OSEK/VDK Woo Dong Kyun.
Chapter 13 전송층 개요.
제 4 장 프로세스 Section 1 프로세스의 개념 Section 2 프로세스 스케줄링
제 2장 컴퓨터 구조.
Concurrency: Deadlock and Starvation
성과보상 인사관리 2561 신 승 환 구 선 예 박 지 영 이 민 주
사용자 메뉴얼 차량용 4CH 블랙박스 매뉴얼 버전 : Version 1.1 Hardware Version : 1.0
강좌 개요 2009년 1학기 컴퓨터의 개념 및 실습.
Operating Systems Overview
AWR DB 보고서 분석.
REINFORCEMENT LEARNING
(ДаТС компьютерийн нэгдсэн сургалтын төв)
Uniprocessor Scheduling
제 7 장 교착 상태 (Deadlocks) 7.1 시스템 모델 (System Model)
제 7 장 교착 상태 7.1 개요 개념 교착 상태란 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태 집합 내의 한 프로세스가 특정 사건의 발생을 기다리며 대기하고 있고, 이 사건이 집합 내의 다른 블록 된 프로세스에 의해 발생될 수 있을.
Concurrency: Deadlock and Starvation
프로세스 관리.
컴퓨터 과학 개론 √ 원리를 알면 IT가 맛있다 컴퓨터 과학도를 위한 첫 전공서 ehanbit.net.
Department of Computer Engineering
Ch 14. System Thread.
4장 병행 프로세스 병행성의 원리를 이해한다 병행 프로세스 수행과 관련된 상호 배 제 해결방안을 알아본다
On the computation of multidimensional Aggregates
운영체제와 Windows XP 초등 ICT 교육 방법론 2013년 1학기.
Numerical Analysis - preliminaries -
Ch. 8 교착상태 (Deadlocks) 29-Nov-18.
트랜잭션과 잠금 트랜잭션 처리 메커니즘을 자세히 이해한다. 트랜잭션의 종류를 파악한다.
Department of Computer Engineering
PPP (Point-to-Point Protocol)
2장 운영 체제의 개요 운영체제의 개념 운영체제의 유형 운영체제의 발전 과정 운영체제의 구성 운영체제 서비스 시스템 구조
Java의 정석 제 12 장 쓰레드(thread) Java 정석 남궁성 강의
관리비부과, 수납관리, 연체관리, 회계관리, 인사관리, 급여관리, 자동검침관리 언제라도 궁금한 사항이 있으시면 문의 바랍니다.
Lecture #3 프로세스(Process).
교착상태(Deadlocks) 시스템 모델(System Model) 프로세스는 자원을 요구 -> 사용 -> 해제
Xen and the Art of Virtualization
Chapter 10. 파일 시스템 인터페이스(File System Interface)
교육수료증 재발급 사유서 SK하이닉스 이천안전팀 업체 명 : 담당자 (인) 업 체 명 : 이 름 : 서명
4 병행 프로세스와 상호배제.
제2장 프로세스 이나현.
2018년 착수 포스코 연구과제 연구비 편성 기준 ■ 2018년 국내 대학 / 연구기관 요율 기준 : 전년과 동일
제5장 CPU스케줄링(CPU Scheduling)
제6장 교착상태 OS 컴퓨터 운영체제 Operating Systems
운영체제(Operating System)
3장 운영체제 2C 김주성.
Operating System Concepts
Introduction to Programming Language
Transmission Control Protocol (TCP)
2. 상호배제와 동기화 01 program versionone; // 첫 번째 버전
10 장 데이터 링크 제어(Data Link Control)
2. 교착상태 해결 기법 실행 과정 - t0 시간에 시스템은 안정상태이며, 순서는 안정 조건을 만족함. - 프로세스 P1은 사용 가능한 자원을 2개 할당 받아 실행한 후 반납 가능하므로 시스템의 여분 자원은 5 개임. - P0은 사용 가능한 자원.
Department of Computer Engineering
제 2장 프로세스 관리와 CPU 스케줄링 2.1 프로세스의 개념 2.2 CPU 스케줄링의 목적과 유형
제4장 CPU 스케줄링 이나현.
이산수학(Discrete Mathematics)
점화와 응용 (Recurrence and Its Applications)
1. 관계 데이터 모델 (1) 관계 데이터 모델 정의 ① 논리적인 데이터 모델에서 데이터간의 관계를 기본키(primary key) 와 이를 참조하는 외래키(foreign key)로 표현하는 데이터 모델 ② 개체 집합에 대한 속성 관계를 표현하기 위해 개체를 테이블(table)
화 일 구 조 Chapter 3 화일의 입출력 제어.
성경퀴즈 여호수아1장 3장 복습게임.
5장 교착 상태 교착상태의 원리를 이해한다. 교착상태의 해결을 위한 예방, 회피, 탐지 그리고 회복에 대하여 알아본다.
데이터 베이스의 내부 구조.
I/O Management and Disk Scheduling
HDD Error시 교체 -> Windows 재 설치 Check to data base Error
운영체제 (Operating Systems)
[CPA340] Algorithms and Practice Youn-Hee Han
Chapter 7: Deadlocks.
3장 – 병행 프로세스 A 김정문.
Presentation transcript:

Concurrency: Deadlock and Starvation Lecture #7 Concurrency: Deadlock and Starvation 신라대학교 컴퓨터공학과 운영체제

자원(Resources) (1) 컴퓨터 자원의 예 printers tape drives Tables, etc. 동일한 종류의 자원이 여러 개 존재 가능 프로세스는 운영체제에게 필요한 자원을 적절한 방법으로 요구하여 할당 받은 후에 그 자원을 사용할 수 있다 하나의 자원은 한 순간에 한 프로세스만 사용할 수 있다 프로세스의 경쟁적 자원 요청이 교착 상태를 유발 한 프로세스가 자원 A을 할당 받은 상태에서 자원 B를 요청 동시에 다른 프로세스가 자원 B를 할당 받은 상태에서 자원 A를 요청 두 개의 프로세스는 모두 블록된 상태를 유지(교착 상태) 신라대학교 컴퓨터공학과 운영체제

자원(Resources) (2) 선점형 자원(Preemptable resources) can be taken away from a process with no ill effects 예: CPU, HDD, etc. 비선점형 자원(Nonpreemptable resources) will cause the process to fail if taken away 예: tape driver, printer, etc. 신라대학교 컴퓨터공학과 운영체제

자원(Resources) (3) Sequence of events required to use a resource 자원 할당 요구(request the resource) 자원 사용(use the resource) 자원 해제(release the resource) 자원 할당 요구가 만족하지 못하면 프로세스는 자원을 사용할 수 있을 때까지 자원 요청, 휴면, 재요청 과정을 반복한다 requesting process may be blocked may fail with error code 신라대학교 컴퓨터공학과 운영체제

교착 상태(Deadlocks) 시스템 자원에 대해 경쟁하거나 상호 통신하는 프로세스 집합의 영구적인 대기 상태 두개 이상의 프로세스가 시스템 자원을 경쟁적으로 요구하는 상황에서 발생한다 일반적으로 최적의 해결책은 없다 신라대학교 컴퓨터공학과 운영체제

교착 상태 발생 예제 신라대학교 컴퓨터공학과 운영체제

교착 상태가 발생하지 않는 예 신라대학교 컴퓨터공학과 운영체제

교착 상태 발생 조건 (1) 다음 3 가지 조건이 성립하면 교착 상태가 발생할 수 있다: 1: 상호 배제(Mutual exclusion) 단지 한번에 하나의 프로세스 만이 자원을 사용할 수 있다 2: 점유와 대기(Hold-and-wait) 하나의 프로세스가 다른 프로세스가 요구하는 자원을 할당 받은 상태에서 다른 자원의 할당을 요구한다 3: 비선점(No preemption) 자원을 강제적으로 선점할 수 없고 소유 프로세스가 작업을 종료한 후에 해제할 수 있다 신라대학교 컴퓨터공학과 운영체제

교착 상태 발생 조건 (2) 다음 조건이 존재하면 교착 상태가 발생한다: 4: 순환 대기(Circular wait) 하나의 프로세스가 다음 프로세스가 요구하는 자원을 가지는 경우가 반복되어 닫힌 체인(chain)을 구성하는 경우 신라대학교 컴퓨터공학과 운영체제

교착 상태 발생 조건 (3) 순환 대기 조건이 해결되지 않으면 교착 상태가 발생한다 앞의 3 가지 조건이 존재하면 순환 대기 조건을 해결되지 않는다 위의 4 가지 조건은 교착 상태에 대한 필요 충분 조건이 된다 신라대학교 컴퓨터공학과 운영체제

교착 상태 처리 방법 교착 상태 무시(Deadlock ignoring) 교착 상태 예방(Deadlock prevention) 가능성이 희박한 사건으로 간주하여 무시하는 방법 교착 상태 예방(Deadlock prevention) 교착 상태 발생의 4 가지 조건 중에 하나를 허용하지 않는 방법 교착 상태 회피(Deadlock avoidance) 자원 할당이 교착 상태를 발생시키는 자원에 대한 요청을 인정하지 않는 방법 교착 상태 탐지(Deadlock detection) 항상 가능하면 자원 요청을 인정한다 주기적으로 교착 상태 발생을 탐지하고 발생한 경우 회복하도록 한다 신라대학교 컴퓨터공학과 운영체제

교착 상태 무시 타조 알고리즘 다음과 같은 조건에서는 적절한 접근법 일반적으로 UNIX와 Windows에서 채용 머리를 땅 속에 파묻고 아무런 문제가 없는 것처럼 대처 가장 단순한 접근법 다음과 같은 조건에서는 적절한 접근법 교착 상태가 아주 드물게 발생하는 경우 교착 상태 예방 비용이 매우 클 경우 일반적으로 UNIX와 Windows에서 채용 다음과 같은 측면에서의 trade-off가 존재 편리함(Convenience) 정확성(Correctness) 신라대학교 컴퓨터공학과 운영체제

교착 상태 예방(Deadlock Prevention) 운영체제가 교착 상태 발생 가능성을 사전에 배제하도록 한다 간접적인 방법 상호배제, 점유와 대기, 비선점 조건 중에 하나를 허용하지 않는 방법 직접적인 방법 순환 대기 발생을 막는 방법 신라대학교 컴퓨터공학과 운영체제

간접 교착 상태 예방(1) 상호 배제(Mutual Exclusion) 점유와 대기(Hold-and-Wait) 이 조건의 해제를 허용할 수 없다 예: 한번에 단지 하나의 프로세스 만이 파일에 기록할 수 있다 점유와 대기(Hold-and-Wait) 프로세스가 한번에 필요한 모든 자원을 요청하도록 한다 모든 자원이 사용할 수 있을 때까지 프로세스는 대기 상태로 기다려야 한다 프로세스는 상당히 오랜 기간 동안 기다릴 수 있다 자원의 효율성이 떨어진다 신라대학교 컴퓨터공학과 운영체제

간접 교착 상태 예방(2) 비선점(No preemption) 자원의 상태를 쉽게 저장하고 복구할 수 있는 경우에 적절하게 지원할 수 있는 방법 예: CPU(processor) 등 신라대학교 컴퓨터공학과 운영체제

직접 교착 상태 예방(1) 순환 대기를 예방하는 프로토콜을 사용: 자원 타입별로 순서를 정의한다 예: R1: tape drives: O(R1) = 2 R2: disk drives: O(R2) = 4 R3: printers: O(R3) = 7 프로세스가 자원별 순서를 고려하여 자원을 요청하도록 한다 이전에 자원 R1을 요구하였으면 다음에는 R1 보다 순서가 높은 자원만을 요청하도록 한다 신라대학교 컴퓨터공학과 운영체제

직접 교착 상태 예방(2) 자원 순서 프로토콜에서는 순환 대기가 발생하지 않는다 Processes {P0, P1,…,Pn} are involved in circular wait iff Pi is waiting for Ri which is held by Pi+1 and Pn is waiting for Rn held which is held by P0 (circular waiting) under this protocol, this means: O(R0) < O(R1) < .. < O(Rn) < O(R0) impossible! 이 방법은 교착 상태를 예방할 수 있지만 자원을 비효율적으로 사용하게 된다 신라대학교 컴퓨터공학과 운영체제

교착 상태 회피(Deadlock Avoidance) 운영체제가 교착 상태가 발생하지 않는다고 판단될 때에 3 가지 발생 조건을 허용하도록 한다 예방 방법보다는 더 많은 병행성을 허용할 수 있다 두 가지 접근법: 자원 요청이 교착 상태를 유도하는 프로세스는 실행하지 않는 방법 자원 할당이 교착 상태를 유도하는 경우 추가적인 자원 요청을 인정하지 않는 방법 위의 접근법의 경우: 각 자원에 대한 최대 요청이 미리 정의되어야 한다 신라대학교 컴퓨터공학과 운영체제

자원 타입(Resource Types) 시스템 내의 자원을 자원 타입(resources types) 별로 구분하여 관리한다 각 타입별 자원은 일정한 양의 자원이 시스템에 존재한다 R(i) : 자원 타입 i 의 전체 자원 양 R(main memory) = 128 MB R(disk drives) = 8 R(printers) = 5 신라대학교 컴퓨터공학과 운영체제

Process initiation denial C(k,i) : 프로세스 k의 자원 타입 i에 대한 요청 자원 수 프로세스 k는 실행을 인정 받기 위해 모든 자원 타입 i 에 대한 C(k,i)을 사전에 정의하여야 한다 V(i) : 할당되지 않은 자원 타입 i의 총 자원 수 V(i) = R(i) - S_k C(k,i) 새로운 프로세스 n은 다음조건을 만족할 때에 인정된다: C(n,i) <= V(i) for all resource type i 프로세스의 모든 자원 요청이 만족될 때에 프로세스 실행이 인정되므로 항상 교착 상태를 피할 수 있다 신라대학교 컴퓨터공학과 운영체제

Resource allocation denial: the banker’s algorithm 프로세스에 대한 자원 할당은 은행에서의 대출 작업과 유사하다 은행에서는 모든 고객의 요구가 만족되지 않으면 대출할 수 없다 프로세스의 자원 요청에 대한 자원 할당이 교착 상태를 유발하는지를 검사하여 자원을 할당하도록 한다 신라대학교 컴퓨터공학과 운영체제

The banker’s algorithm(1) Banker 알고리즘은 프로세스의 자원 할당 요청에 대하여 요청 자원에 대한 할당이 안정 상태(Safe State)을 유도하는지를 검사한다: 안정 상태가 보장되면 자원을 할당한다 안정 상태가 보장되지 않으면 자원 요청을 거부한다 안정 상태(Safe State) 모든 프로세스가 교착상태에 발생시키지 않고 종료할 수 있도록 하는 자원 할당 순서가 존재하는 경우 신라대학교 컴퓨터공학과 운영체제

The banker’s algorithm(2) 시스템 상태: R(i) : 자원 타입 i의 총 자원 양 C(k,i) : 프로세스 k가 요청하는 자원 타입 i의 자원 양 A(k,i) : 프로세스 k가 할당된 자원 타입 i의 자원 양 V(i) : 현재 사용 가능한 자원 타입 i의 자원 양 i.e. V(i) = R(i) - S_k A(k,i) N(k,i) : 프로세스 k가 작업을 완료하기 위해 필요로 하는 자원 타입 i의 자원 양 i.e. N(k,i) = C(k,i) - A(k,i) 신라대학교 컴퓨터공학과 운영체제

The banker’s algorithm(3) Q(k,i) : 프로세스 k가 자원 타입 i에 대해 요구하는 자원 양 banker’s algorithm 다음 과정을 통해 자원 요청에 대해 자원을 할당한 것인지를 결정한다 모든 자원 타입 i에 대해 Q(j,i) <= N(j,i) 을 만족하는 지를 검사한다. 만족하지 않으면 자원 할당 요청을 거부한다 모든 자원 타입 i에 대해 Q(j,i) <= V(i) 을 만족하는지를 검사한다. 현재 자원이 사용할 수 있는 상태가 아니므로 자원 할당 요청을 거부한다 신라대학교 컴퓨터공학과 운영체제

The banker’s algorithm(4) banker’s algorithm cont’n 현재 자원 할당 요청에 대해 자원 할당을 가정하고 다음과 같이 새로운 자원 할당 상태를 계산한다 V(i) = V(i) - Q(j,i) for all i A(j,i) = A(j,i) + Q(j,i) for all i N(j,i) = N(j,i) - Q(j,i) for all i 새로운 자원 할당 상태가 안정 상태인지를 검사한다 안정 알고리즘(Safety Algorithm) 안정 상태가 되면 자원을 할당한다 그렇지 않으면 프로세스는 자원 할당이 가능할 때까지 기다려야 한다 신라대학교 컴퓨터공학과 운영체제

Banker’s algorithm 예제 (1) 다음과 같은 시스템 상태를 가정한다 : 3가지의 자원 타입 : R(1) = 9, R(2) = 3, R(3) = 6 아래의 초기 상태를 가지는 4개의 프로세스 Claimed Allocated Available 3 2 2 6 1 3 3 1 4 4 2 2 1 0 0 5 1 1 2 1 1 0 0 2 1 1 2 P1 P2 P3 P4 R1 R2 R3 프로세스 P2가 Q = (1,0,1) 자원 할당을 요청할 때에 자원을 할당할 것인가? 신라대학교 컴퓨터공학과 운영체제

Banker’s algorithm 예제 (2) 현재 사용 가능한 자원이 있으므로 자원 할당을 가정하면 다음과 같은 새로운 자원 할당 상태가 된다 Claimed Allocated Available 3 2 2 6 1 3 3 1 4 4 2 2 1 0 0 6 1 2 2 1 1 0 0 2 0 1 1 P1 P2 P3 P4 R1 R2 R3 새로운 상태가 안정상태가 되는지를 검사한다 안정 알고리즘 P2  P1  P3  P4 자원 할당 요청에 대하여 자원을 할당한다 신라대학교 컴퓨터공학과 운영체제

Banker’s algorithm 예제 (3) Claimed Allocated Available P1 P2 P3 P4 3 2 2 0 0 0 3 1 4 4 2 2 R1 R2 R3 1 0 0 2 1 1 0 0 2 6 2 3 프로세스 P2 실행 : Claimed Allocated Available P1 P2 P3 P4 0 0 0 3 1 4 4 2 2 R1 R2 R3 2 1 1 0 0 2 7 2 3 프로세스 P1실행 : Claimed Allocated Available P1 P2 P3 P4 0 0 0 4 2 2 R1 R2 R3 0 0 2 9 3 4 프로세스 P3 실행 : Claimed Allocated Available P1 P2 P3 P4 0 0 0 R1 R2 R3 9 3 6 프로세스 P4실행 : 신라대학교 컴퓨터공학과 운영체제

Banker’s algorithm 예제 (4) 만약 초기 상태에서 프로세스 P1가 Q = (1,0,1) 자원할당을 요청하면 자원 할당을 가정하는 경우 다음과 같은 새로운 상태가 된다 Claimed Allocated Available 3 2 2 6 1 3 3 1 4 4 2 2 2 0 1 5 1 1 2 1 1 0 0 2 0 1 1 P1 P2 P3 P4 R1 R2 R3 새로운 상태는 안정 상태가 되지 않는다 따라서 프로세스 P1의 자원 할당 요청을 거부한다 신라대학교 컴퓨터공학과 운영체제

Banker’s algorithm: 요약 안정 상태는 교착 상태가 되지 않는다 불안정 상태가 반드시 교착 상태가 되는 것은 아니다 예: 앞의 예제에서 프로세스 P1가 자원 타입 1과 3 의 자원을 잠시 해제하게 되면 안정 상태로 돌아간다 몇몇 프로세스가 불필요하게 기다리게 된다 최적으로 자원을 활용할 수 없다 교착 상태 회피 알고리즘은 프로세스들이 독립적이라고 가정한다 신라대학교 컴퓨터공학과 운영체제

교착 상태 탐지(Deadlock Detection) 자원 할당 요청에 대해 가능하면 자원을 할당한다 운영체제는 다음과 같은 작업을 수행한다 교착 상태가 발생하는지 검사한다 교착 상태가 발생하면 회복 작업을 수행한다 자원 할당 요청이 발생할 때마다 교착 상태 발생 여부를 검사한다 빈번한 교착 상태 검사는 CPU 시간을 낭비하게 된다 신라대학교 컴퓨터공학과 운영체제

교착 상태 탐지 알고리즘 은행가 알고리즘(Banker’s Algorithm)과 유사 각 프로세스가 교착 상태가 아니라고 가정하고 모든 프로세스을 실행 가능 여부를 표시하지 않는다 다음 과정을 수행한다 Mark each process j s.t A(j,i) = 0 for all resource type i. (since these are not deadlocked) Initialize work vector : W(i) = V(i) for all i REPEAT: Find a unmarked process j such that Q(j,i) <= W(i) for all i. Stop if such j does not exists If such j exists: mark process j and set W(i) = W(i) + A(j,i) for all i. Goto REPEAT At the end: each unmarked process is deadlocked 신라대학교 컴퓨터공학과 운영체제

Request Allocated Available 교착 상태 탐지 예제 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 R1 R2 R3 R4 R5 P1 P2 P3 P4 Request Allocated Available 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 Mark P4 since it has no allocated resources Set W = (0,0,0,0,1) P3’s request <= W. So mark P3 and set W = W + (0,0,0,1,0) = (0,0,0,1,1) Algorithm terminates. P1 and P2 are deadlocked 신라대학교 컴퓨터공학과 운영체제

교착 상태 회복(Deadlock Recovery)(1) 교착 상태가 발생하였을 때 다음과 같은 회복 방법을 사용할 수 있다 교착 상태가 된 모든 프로세스 중지한다 운영체제에서 적용하는 일반적인 방법 교착 상태가 된 프로세스의 를 이전의 검사 시점으로 되돌리고 다시 실행한다 원래의 교착 상태가 발생할 가능성 있다 교착 상태가 존재하지 않을 때까지 교착 상태가 된 프로세스를 계속적으로 중지시켜 나간다 매번 교착 상태 탐지 알고리즘을 실행하여야 한다 교착 상태가 존재하지 않을 때까지 하나의 프로세스에서 자원을 선점하여 다른 프로세스에게 할당한다 자원을 선점 당하는 프로세스는 자원 할당 이전의 상태로 되돌려 놓아야 한다 신라대학교 컴퓨터공학과 운영체제

교착 상태 회복(Deadlock Recovery)(2) 교착 상태 회복 기법에서 희생 프로세스를 선택하는 방법: 현재까지 CPU 시간을 적게 사용한 프로세스 현재까지 할당된 자원의 양이 적은 프로세스 현재까지 수행한 작업이 적은 프로세스 등 신라대학교 컴퓨터공학과 운영체제

통합 교착 상태 전략 일반적으로 여러가지 접근법을 통합하여 교착 상태를 관리한다 자원을 종류별로 그룹을 구성하고 순서를 할당한다. 예를 들면, Swappable space (secondary memory) Process resources (I/O devices, files...) Main memory... 자원 그룹 간에 교착 상태를 방지하기 위하여 순환 대기 예방 접근법을 사용한다 자원 그룹 내의 교착 상태는 각 그룹 별로 가장 적절한 접근법을 사용한다 신라대학교 컴퓨터공학과 운영체제