6강. 교착상태 (1)

1. 프로세스의 자원 사용 절차

• 요구 → 사용 → 해제
• 요구과정에서 가용한 자원이 없으면 자원을 획득할 때까지 대기

2. 교착상태 ( Deadlock )

• 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느 쪽도 영원히 진행하지 못하는 상태

3. 교착상태와 기아상태의 차이

• 교착상태 : 누구도 어느쪽으로도 진행하지 못하는 상태
• 기아상태 : 현재는 진행하지 못하지만, 언젠가는 진행할 수 있는 가능성이 있는 상태

4. 교착상태의 필요조건

• 아래의 네 가지 조건이 동시에 만족될 때 교착상태 발생 가능 ( 무조건 발생하는건 X )
  • 상호배제
  • 점유대기
  • 비선점
  • 환형대기

5. 상호배제( Mutual Exclusion ) 조건

• 프로세스가 자원에 대한 배타적인 통제권을 요구
• 적어도 하나 이상의 자원은 여러 프로세스에 의해 동시에 사용될 수 없음
• 다른 프로세스가 점유한 자원이 필요하면 반드시 대기

6. 점유대기( Hold and wait ) 조건

• 프로세스가 이미 한 자원을 할당받아 점유하고 있는 상황에서 다른 프로세스가 점유하고 있는 또 다른 자원을 요구하여 해제되기를 기다리는 상황

7. 비선점( No Preemption ) 조건

• 프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에는 해제되지 않음
• 할당된 자원은 타의에 의해서는 해제되지 않음

8. 환형대기( Circular wait ) 조건

• 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기하는 상황
  • 서로 상대방의 자원을 요구하면서 무한히 대기하는 상태

9. 자원할당 그래프 G=(V, E)

• V : 정점의 집합 V = PU R
  • P = {p1, p2, …, pn} : n개의 프로세스
  • R = {r1, r2, …, rm} : m개의 자원
• E : 방향 있는 간선의 집합 E = Q U S
  • Q = {(pi, rj): pi E P, rj E R } : 프로세스 Pi가 자원 rj를 요구 ( 요구 간선 )
  • S = {(rj, pi): rj E R, pi E P} : 자원 rj가 프로세스 pi에 할당 ( 할당 간선 )
• rj : 자원의 유형을 의미
• k : 단위자원의 개수를 의미

10. 자원할당 그래프 예

• 정점의 집합 V = P U R
  • 프로세스 집합 P = {p1, p2, p3}
  • 자원 집합 R = {r1, r2, r3}
• 방향 있는 간선의 집합 E = Q U S
  • 요구간선 집합 Q = {(p1, r2)}
    • 의미 : p1 프로세스가 r2자원을 요구
  • 할당간선 집합 S = {(r1, p1), (r2, p2), (r3, p3)}
    • 의미 : r1 자원이 p1에 할당, r2 자원이 p2에 할당, r3 자원이 p3에 할당

11. 자원할당 그래프의 변화

• p2가 r3을 요구하는 경우
  • 요구간선 (p2, r3) 추가
  • 가용한 단위자원이 존재하면 요구간선(p2, r3)에서 할당간선 (r3, p2)로 바꿈

12. 자원할당 그래프 : 교착상태의 필요조건 표현

• 상호배제 : 하나의 할당간선
• 점유대기 : 한 프로세스에 할당간선과 요구간선 연결
• 비선점 : 요구간선
• 환형대기 : 사이클( Cycle )

13. 자원할당 그래프 : 교착상태 판단

• 사이클 없음 → 교착상태 없음
• 사이클 있음 → 교착상태 발생 가능
  • 교착상태 예시
    • 사이클이 해소될 가능성이 없는 경우
  • 교착상태 아닌 예시
    • 시간이 지난 후, 할당되었던 단위자원이 반환되면서 사이클이 해소될 가능성이 있는 경우

14. 교착상태의 처리기법

• 교착상태 예방
  • 교착상태의 네 가지 필요조건이 동시에 만족되는 것을 피하여 교착상태가 발생하지 않도록 하는 방법
• 교착상태 회피
  • 프로세스에 필요한 자원의 최대량에 대한 정보를 이용하여 교착상태가 발생하지 않도록 하는 방법
• 교착상태 탐지 및 복구
  • 교착상태의 발생 여부를 조사하여 발생한 경우에는 적절한 조치를 취해 정상상태로 복구하는 방법

15. 교착상태 예방 : 상호배제 조건 제거

• 공유할 수 있는 자원 : 상호배제 필요 없음
  • 예시 : 읽기 전용 파일
• 공유할 수 없는 자원 : 반드시 상호배제 필요
  • 예시 : 프린터
  • 상호배제 조건 제거로 교착상태 예방은 불가능

16. 교착상태 예방 : 점유대기 조건 제거

• 자원을 점유했을 때 대기하지 않아야 함
  • 프로세스가 앞으로 필요한 모든 자원을 처음에 한꺼번에 요구하여 할당받음
    • 자원이용률 낮아짐, 기아상태 가능
• 대기할 때 자원을 점유하고 있지 않아야 함
  • 새로운 자원을 요구할 때 할당받았던 자원을 모두 해제
    • 점유 도중 해제할 수 없는 자원에는 적용 불가

17. 교착상태 예방 : 비선점 조건 제거

• 선점이 가능하도록 해야 함
  • 자원의 특성에 따라 불가능한 경우 존재
  • 예 : 프린터
• 다른 프로세스가 대기할 가능성 줄이기
  • 점유대기 상황이 발생하면 할당받았던 자원을 모두 해제
  • 프린터 같은 자원에는 적용 불가

18. 교착상태 예방 : 환형대기 조건 제거

• 모든 자원에 일련번호를 지정
  • 함수 f : R→ N ( R : 자원 집합, N : 자연수 집합)
  • ri ≠ rj이면 f(ri) ≠f(rj)
• 방법 1
  • 프로세스는 자원을 요구할 때 일련번호 기준으로 항상 오름차순이 되도록 요구
  • 가장 최근에 할당받은 자원이 ri이면 다음에 요구할 자원 rj는 f(ri) < f(rj) 만족
• 방법 2
  • 프로세스가 자원을 요구할 때 그보다 일련번호가 작은 자원만 점유하도록 함
  • 자원 rj요구하려면 점유 중인 자원 중 f(rj) ≤ f(ri)인 자원 는 모두 해제
• 점유대기 중인 프로세스는 점유 중인 자원의 일련번호보다 대기 중인 자원의 일련번호가 큼
  • 환형대기 발생 불가능
• 프로세스마다 요구순서가 다를 수 있어 자원의 일련번호 설정 어려움
• 요구순서가 일련번호 오름차순을 못지키면 점유자원 해제 필요하나 적용 불가한 자원 존재