Concurrency: Deadlock and Starvation

Slides:



Advertisements
Similar presentations
컴퓨터와 인터넷.
Advertisements

운영체제 Chapter 3 병형 프로세스 박요안.
제 4 장 프로세스 Section 1 프로세스의 개념 Section 2 프로세스 스케줄링
Concurrency: Deadlock and Starvation
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
Java로 배우는 디자인패턴 입문 Chapter 5. Singleton 단 하나의 인스턴스
제 12 장 직교배열표에 의한 실험계획(1).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
CUDA Setting : Install & Compile
- 1변수 방정식의 solution 프로그램 (Bisection method, Newton-Raphson method)
제 7 장 교착 상태 (Deadlocks) 7.1 시스템 모델 (System Model)
제 7 장 교착 상태 7.1 개요 개념 교착 상태란 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태 집합 내의 한 프로세스가 특정 사건의 발생을 기다리며 대기하고 있고, 이 사건이 집합 내의 다른 블록 된 프로세스에 의해 발생될 수 있을.
운영체제 4장 요약정리(CPU 스케줄링) 2A 박훈.
Windows Server 장. 사고를 대비한 데이터 백업.
Ch. 8 교착상태 (Deadlocks) 29-Nov-18.
Chapter 02 순환 (Recursion).
SAP GUI 설치 가이드 프로세스 혁신 TFT.
Linux서버를 이용한 채팅프로그램 지도 교수님 : 이형원 교수님 이 름 : 이 은 영 학 번 :
Chapter 06 프로세스와 예약작업 관리 Solaris 1. 프로세스 관리
질의 사항 Yield Criteria (1) 소재가 평면응력상태에 놓였을 때(σ3=0), 최대전단응력조건과 전단변형에너지 조건은σ1 – σ2 평면에서 각각 어떤 식으로 표시되는가? (2) σ1 =σ2인 등이축인장에서 σ = Kεn로 주어지는 재료의 네킹시 변형율을 구하라.
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
기억 장치 관리 (Memory Management)
26. 매크로와 전처리기.
교착상태(Deadlocks) 시스템 모델(System Model) 프로세스는 자원을 요구 -> 사용 -> 해제
10 장 데이터 링크 제어(Data Link Control)
Sungkyunkwan University OS Project Dongkun Shin
보조저장장치 구조(Secondary Storage Structure)
제 22 장 TCP Persist Timer.
03. 병행 프로세스 (Parallel Process)
자바 5.0 프로그래밍.
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
제6장 교착상태 OS 컴퓨터 운영체제 Operating Systems
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
29강 JAVA 스레드 - 스레드란? - 멀티스레드 문법 - synchronized Lecturer Kim Myoung-Ho
메모리 관리 & 동적 할당.
뇌를 자극하는 Windows Server 2012 R2
Operating System Concepts
Metal Forming CAE Lab., Gyeongsang National University
Choi Seong Yun 컴퓨터 프로그래밍 기초 #06 : 반복문 Choi Seong Yun
메모리 타입 분석을 통한 안전하고 효율적인 메모리 재사용
10 장 데이터 링크 제어(Data Link Control)
3강. 컴퓨터와의 기본적인 소통수단 - I 연산자란? 컴퓨터와 소통하기 위한 다양한 방법들
10 장 데이터 링크 제어(Data Link Control)
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
5 교착상태와 기아상태.
운영체제 (Operating Systems)
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
( Windows Service Application Debugging )
알고리즘 알고리즘이란 무엇인가?.
Lecture #3 프로세스(Process) 신라대학교 컴퓨터공학과 - 운영체제.
약식 진리표를 이용한 타당성 증명 진리표 그리기 방법의 한계
클러스터 시스템에서 효과적인 미디어 트랜스코딩 부하분산 정책
Chapter 27 Mobile IP.
Homework #5 (1/3) 다음을 수행한 후, 결과 파일들을 출력하여 제출한다.
Homework #3 (1/3) 다음을 수행한 후, 결과 파일들을 출력하여 제출한다.
System Security Operating System.
컴퓨터공학과 손민정 Computer Graphics Lab 이승용 교수님
워드프로세서 스프레드시트 문서 관리 인터넷 활용
수치해석 ch3 환경공학과 김지숙.
운영체제 (Operating Systems)
Concurrency: Deadlock and Starvation
(Permutations and Combinations)
교착 상태 해결 : 교착 상태 탐지 교착 상태 탐지(Deadlock Detection)
운영체제보안 SELinux 실습 박민재
2학기 2학기 7월 26일(금) 14시에 덕성포탈에 로그인 하시면 합격/불합격/대기 여부를 확인하실 수 있습니다. 2학기
병행 프로세스(Parallel Process)
2. 프로세스 B 안우진 - 운영체제 -.
Chapter 7: Deadlocks.
Presentation transcript:

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

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

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

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

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

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

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

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

교착 상태 예방(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)을 사전에 정의하여야 한다 U(i) : 할당되지 않은 자원 타입 i의 총 자원 수 U(i) = R(i) - S_k C(k,i) 새로운 프로세스 n은 다음조건을 만족할 때에 인정된다: C(n,i) <= U(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... 자원 그룹 간에 교착 상태를 방지하기 위하여 순환 대기 예방 접근법을 사용한다 자원 그룹 내의 교착 상태는 각 그룹 별로 가장 적절한 접근법을 사용한다 신라대학교 컴퓨터공학과 운영체제