[운영체제] 7. 교착상태 Deadlock

KOCW에서 제공하는 경성대학교  양희재 교수 운영체제 강의를 듣고 정리한 글 입니다.

 

---

1. 교착 상태

1) 교착 상태란?

: 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태.

 

2) 교착상태 필요 조건 4

• Mutual exclusion (상호배타) : 자원 동시에 사용 불가
• Hold and wait (보유 및 대기) : 한 자원을 잡고있고, 다른 자원 대기하고 있을 떄
• No Preemption (비선점) : 자원 할당 받으면 스스로 반납할 때 까지 자원 사용하도록 허용 (뺏지 않음)
• Circular wait (환형대기) (자원 할당도 상에 원이 만들어짐)
• -> 이 네 조건을 다 만족하면 교착상태가 발생할 수도있다.

 

3) 자원 할당도 Resource Allocation Graph

(1) 자원 할당도란?

• 아래 두가지를 나타낼 수 있는 방법
• 어떤 자원이 어떤 프로세스에게 할당되었는가?
• 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는가?
• 자원: 사각형, 프로세스: 원, 할당: 화살표

 

 

• 자원할당도에서 알 수 있는것
  • R1에 점 : 리소스 1개이다.
  • R1->P2 : P2가 R1 사용중이다.
  • P2가 R1 사용하려고 요청중이다.

 

(2) 교착 상태가 일어났을 때 자원 할당도 

 

데드락이 일어났을 때 자원 할당도

 

4) 교착상태가 일어나지 않게 하는 방법

: 교착상태 필요조건 중 하나라도 만족시키지 않으면 된다.

(1) 환형 대기를 깨는 방법

짝수번 프로세스는 왼, 오른쪽 들기, 홀수번 프로세스는 오, 왼쪽 들기

이렇게 바꾸면 환형 대기가 생기지 않는다. 

 

5) 교착 상태 처리

• (1) 교착 상태 방지
• (2) 교착 상태 회피
• (3) 교착 상태 검출 및 복구
• (4) 교착 상태 무시

 

(1) 교착 상태 방지

교착 상태 4가지 필요조건 중 하나라도 만족하지 않게 한다.

• ① 상호 배타 -> 자원을 공유 가능하게 해야하는데. 대부분의 경우 불가. (일부만 가능. ex) 파일 읽기 )
• ② 보유 및 대기 -> 자원을 가지고 있으면서 다른 자원 기다리지 않게 한다
  (전부 가지지 못하면 잡지 않게 / 다른 자원 대기해하는 경우 잡고있는 자원 놓게)
  -> 단점 : 자원 활용 저하, 기아 상태 발생 가능
• ③ 비선점 -> 자원을 선점 가능하게 한다. ->  대부분 경우 불가 (ex) 프린터)
• ④ 환형 대기 -> 예) 자원에 번호 부여, 번호 오름차순으로 자원 요청 -> 단점 : 자원 활용률 저하

 

(2) 교착 상태 회피

OS 프로세스 관리자가 자원을 분배하는데, 자원 요청에 대한 잘못된 승인 으로 인식

 

안전한 할당과 불안전한 할당 예시 : Banker's Algorithm

: 위험한 대출을 해주지 않아 파산 방지하기

 

자원 총 12개, 프로세스 3개에 할당하기

안전한 할당

Process	Max Needs	Current Needs
P0	10	5
P1	4	2
P2	9	2

• 5, 2, 2로 할당 -> 3개 남음
• P0 나중에 리소스 5개 추가 요청할 것. 3개남아서 할당 못해줌. 곧 프로세스 중지됨
• P1 2개 더 요청할 것. 2개 할당할 수 있고, 할당해주면 사용후 프로세스 종료 및 자원 반환할 것 -> 1개남음 + 4개 반환 = 5개 -> P0에게 할당 가능
• P0이 끝나고 자원 반환 -> 잔여 0개 + 10개 반환 -> P2에게 7개 할당 가능
• -> P0, P1, P2 다 완료 가능

 

불안전한 할당

Process	Max Needs	Current Needs
P0	10	5
P1	4	2
P2	9	3

• 5, 2, 3으로 할당 -> 2개 남음
• P0 나중에 리소스 5개 추가 요청할 것. 2개 남아서 할당 못해줌. 곧 프로세스 중지됨
• P1 2개 더 요청할 것. 2개 할당할 수 있고, 할당해주면 사용후 프로세스 종료 및 자원 반환할 것 -> 0개남음 + 4개 반환 = 4개 -> 여전히 P0에게 할당 불가 
• P2 6개 더 필요, 4개 남음 실행 불가.
• -> P1만 완료 가능하고, P0, P2 계속 대기. 완료 불가

 

 

(3) 교착 상태 방지

• 교착 상태가 일어나는 것을 허용
• 주기적 검사하여 발생 시 복구
• 검출 : 검사에 따른 추가 부담(overhead) : 계산, 메모리(정상 상태 기억해야함)
• 복구 : 프로세스 일부 강제 종료, 자원 선점하여 일부 프로세스에게 할당

 

(4) 교착 상태 방지

실제로 교착 상태는 잘 발생하지 않으므로 아무런 조치 하지 않는다.

 

 

---

요약

OS 주요 기능중 하나 : CPU 자원관리

프로세스 매니지먼트가 주요 역할 : CPU 스케줄링, 프로세스 동기화(+데드락)