운영체제_Chap6. 교착상태 Deadlock

시스템 내에 임계구역이 존재 하면, 프로세스 간 상호 배제를 보장해야 한다.

<복습> 상호 배제? 프로세스가 임계구역에 들어와있으면, 다른 프로세스가 들어올 수 없는 것.

교착상태란? 운영체제가 상호 배제를 보장하기 위해, 잠금을 사용할 때 더이상 작업이 진행되지 않는 상태.

01. 교착 상태의 개요

교착상태? 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리면서, 작업을 더 이상 진행하지 못하는 상태.

아사현상? 운영체제가 잘못된 정책을 사용해서, 특정 프로세스의 작업이 지연되는 문제

교착 상태는 언제 발생하는 가?

1. "시스템 자원" 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생. ( 프린터와 CD레코더 )

2. "공유 변수" 한 변수를 할당받은 상태에서, 다른 변수를 기다리는 경우.

3. "데이터의 일관성"

4. "자원 할당 그래프" 자원을 요구하는 방향이 원을 이루면, 양보하지 않아서 교착상태가 발생

02. 교착 상태 필요조건 4가지는?

상보배제, 비선점, 점유와 대기, 원형 대기

상호 배제: 한 프로세스가 사용하는 자원은, 다른 프로세스랑 공유할 수 없는 배타적인 자원. 배타적인 자원을 여러 프로세스가 사용해야하는 경우.

비선점: 한 프로세스가 사용하는 자원은, 중간에 다른 프로세스가 뺏을 수 없는 비선점 자원.

점유와 대기: 프로세스가 자원을 할당받은 상태에서, 다른 자원을 기다리는 상태.

원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이룬다. => 서로 양보하지 않는다.

03. 교착 상태 해결 방법

1. 교착 상태 해결 방법은?

예방: 상보 배제, 비선점, 점유와 대기, 원형대기 조건이 발생하지 않도록 무력화.

회비: 자원 할당량을 조절해서 교착 상태를 해결

검출: 어떤 제약을 가하지 않고, 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴본다.

회복: 교착 상태가 발생시, 교착 상태 회복 단계가 진행

2. 교착 상태 예방?

1. 상호배제 예방? 시스템 내에 있는 상호 배타적인 모든 자원, 독점적으로 사용할 수 있는 자원을 없애버리는 것. 현실적으로 적용 X

2. 비선점 예방? 모든 자원을 뺴앗을 수 있도록 만드는 방법이지만, 비선점 조건을 무력화하기 어려움.

3. 점유와 대기 예방? 프로세스가 자원을 점유한 상태에서, 다른 자원을 기다리지 못하게 하는 방법으로 all or nothing. 데이터의 일관성과 같은 개념으로, 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납한다.

* 점유와 대기 예방의 단점은?

1. 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.

2. 프로세스가 아픙로 사용할 자원까지 미리 선점해버려서, 그 자원이 필요한 다른 프로세스의 작업이 진행안된다.

3. 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리.

4. 점유와 대기 예방을 실제로 구현하면, 실제로 거의 모든 프로세스가 일괄 작업 방식으로 처리됨.

4. 원형 대기 예방?

자원에 우선순위숫자를 부여해서, 자원이 한 방향으로만 사용하도록 설정하여 예방한다.

3. 교착 상태 회피?

교착 상태 회피는 어떤 방법인가?

프로세스에 자원을 할당할 때, 교착 상태가 발생하는 자원의 개수를 파악하고, 그 수준이하로 자원을 나누어준다.

즉, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.

할당되는 자원의 수를 조절하여 교착상태를 피하는데, 자원을 많이 할당할 수록 교착 상태가 발생할 확률이 커진다.

은행원 알고리즘의 원리를 설명하라

각 프로세스는 자신이 사용할 자원의 최대수를 운영체제에 알린다 

-> 기대 자원(프로세스가 앞으로 사용할 자원) = 프로세스의 최대 자원 - 현재 할당된 자원의 수

-> 가용 자원 = 시스템 내 현재 사용할 수 있는 자원의 수 = 전체 자원 - 모든 프로세스의 할당 자원

안정상태의 은행원 알고리즘

결론: 프로세스 P2에 자원을 할당해야만, 안정 상태를 계속 유지할 수 있다.

Total 자원 개수 = 14 , Available 가용 자원 (전체 자원 개수14 - 프로세스별할당자원합12) = 2

Process   Max   Allocation  Expect 

P1          5        2            3

P2          6        4            2    = > P2에 자원을 할당해야지, 안정적인 상태유지.

P3          10      6            4

반대로, 기대 자원의 수 > 가용자원이면, (모든 프로세스가) 불안정 상태이다.

교착 상태 회피를 사용하지 않는 이유? 

원칙은 교착 상태가 발생하지 않는 수준까지만 자원을 나누어주는 것이다.

그 수준은?

1. 프로세스가 자신이 사용할 모든 자원을 미리 선언

2. 시스템의 전체 자원 수가 고정적이여야 하지만, 일시적인 고장이나 새로운 자원이 추가되는 일이 빈번해서, 시스템 자원 수는 유동적이다.

3. 자원이 낭비

4. 교착 상태 검출

교착 상태 검출이란? 

운영체제가 프로세스의 작업을 직접 관찰하면서, 교착 상태 발생 여부를 계속 주시 -> 교착 상태 발견시, 교착 상태 회복 단계

검출 방법: 타임아웃이용방법, 자원 할당 그래프 이용 방법

타임아웃을 고려한 교착 상태 검출이란?

일정 시간 동안 작업이 진행되지 않은 프로세스 => 교착 상태가 발생한 것으로 간주하여 처리.

But, 이런 방식의 문제는?

엉뚱한 프로세스가 강제 종료 

모든 시스템에 적용할 수 없음.

* 타임아웃을 이용하는 방법의 예

윈도우에서 '프로그램 응답이 없어 종료합니다' => 타임아웃을 이용하는 방법의 대표적인 예

* DB의 교착 상태 처리

DB에서는 특히 데이터의 일관성이 깨지면 안된다. DB를 조작할 때는 반드시 잠금을 얻은 후 작업을 시작.

여러 개의 잠금을 얻어 작업을 하던 중, 타임아웃으로 프로세스가 종료되면 일부 데이터에 문제 발생.

* 타임아웃으로 발생하는 DB의 일관성 문제 해결하기 위해서는?

체크포인트, 롤백을 사용!

체크포인트? 

작업을 하다가 문제가 발생하면, 저장된 상태로 되돌아오기위한 표시. 스냅숏은 현재의 시스템 상태가 하드디스크에 저장되는 것

롤백? 작업을 하다 문제가 발생해서, 과거의 체크포인트로 되돌아가는 것.

롤백이 일어나면, 저장된 스냅숏을 복원해서, 시스템을 체크포인트 시점으로 되돌림.

* 운영체제의 롤백?

윈도우에서 특정 시점으로 복원은, 스냅숏과 롤백을 이용하여 운영체제를 복원시키는 작업

시스템 속성 - 시스템 보호로, 불필요한 시스템 변경을 실행 취소.

* 자원 할당 그래프를 이용한 교착 상태 검출

교착 상태 검출하는 또 다른 방법

자원할당그래프에서 알 수 있는 것?

시스템 내의 프로세스가 어떤 자원을 사용하고 있는지, 기다리고 있는지 알 수 있음.

* 교착 상태가 있는 자원 할당 그래프

이때 사이클이 발생하면, 교착 상태가 검출된 것으로 판단.

5. 교착 상태 회복 

교착 상태가 검출되면, 교착 상태를 푸는 후속 작업을 하는데, 교착 상태 회복이라고 함.

교착 상태를 유발한 프로세스를 강제로 종료함.

강제 종료된 프로세스가 실행되기 전에, 시스템을 복구.

=> 시스템 복구 - 명령어가 실행될 때, 체크포인트를 만들어, 가장 최근의 검사 시점으로 돌아감. 단점은, 시스템에 부하를 줌.

1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료

2. 교착 상태 일으킨 프로세스 중 하나를 골라, 순서대로 종료하면서 나머지 프로세스의 상태 파악.

    1) 우선순위 낮은 프로세스 종료

    2) 우선순위가 같은 경우, 작업 시간이 짧은 프로세스를 먼저 종료

    3) 위의 의 두 조건이 같으면, 자원을 많이 사용하는 프로세스 종료.