7. 교착 상태 (Deadlock)

1. 교착 상태 (Deadlock)

 

일련의 프로세스들이 서로가 가진 자원을 기다리며 Blocked 된 상태

• 자원 (Resource) : 프로그램 실행에 마땅히 필요한 요소
  → 하드웨어, 소프트웨어 등을 포함

 

2. 교착 상태 발생 4조건

1. 상호 배제 (Mutual Exclusion)

• 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어갈 수 없음
  → 임계 구역 문제 해결 3원칙에도 포함됨
  

 

2. 점유와 대기 (Hold and Wait)

• 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다림

 

3. 비선점 (Non-preemptive)

• 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗을 수 없음

 

4. 원형 대기 (Circular Wait)

• 자원을 기다리는 프로세스 간 사이클이 형성됨

 

위 조건이 모두 만족될 때 교착 상태가 발생할 수 있음

 

3. 자원 할당 그래프

 

규칙

• 1. 프로세스는 원으로, 자원의 종류는 사각형으로 표시
• 2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
• 3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 "자원 → 프로세스"
• 4. 프로세스가 어떤 자원을 기다리고 있다면 "프로세스 → 자원"

 

사이클

• 사이클이 없다면?
  → 교착 상태 X
  
• 사이클이 있다면?
  → 교착 상태가 발생할 수 있음
  
• 위 그림에서 좌측 자원 할당 그래프는 교착 상태지만, 우측 자원 할당 그래프는 교착 상태가 아님

 

4. 교착상태 해결법

예방

• 교착 상태 발생 4조건 중 하나를 충족하지 못하게 하는 방법 (비효율적)
• 상호 배제 ☞ 동시에 여러 프로세스가 자원에 접근할 수 있도록 함
• 점유와 대기 ☞ 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
  → 필요한 자원을 한 번에 할당받거나, 자원이 필요할 경우 보유 자원을 모두 반납 후 재요청하도록 구현
• 비선점 ☞ 프로세스가 이미 보유 중인 자원에 대한 선점을 허용해야 함
  → 선점당할 때 모든 작업 진행 상황이 날아감
  → 따라서 CPU나 메모리처럼 상태를 쉽게 저장 및 복구할 수 있는 자원에서 주로 사용
• 원형 대기 ☞ 모든 자원 유형에 할당 순서를 정해야 함
  → 예) 5번 자원을 보유 중인 프로세스는 1번 자원을 할당받을 수 없음

 

회피

• 안전 상태일 경우에만 자원을 할당하는 방법
• Banker's Algorithm
  → 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  → 안전 상태 : 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태
  → 불안전 상태 : 안전 순서열이 없는 상태 (교착 상태가 발생할 수 있음)
• 예) 

  

  
  → Available로 모든 Need를 만족시킬 수 있는 순서가 곧 안전 순서열 (P1 → P3 → P0 → P2 → P4 등)

 

검출 후 회복

• 교착 상태를 발생을 인정하고 사후에 조치하는 방법
• 검출 (Banker's Algorithm과 유사한 방법을 통해)
  

  

  위의 경우 안전 순서열 (P0 -> P2 -> P1 -> P3 -> P4)가 존재하지만,

  

  위의 경우 안전 순서열이 존재하지 않는 불안전 상태임과 동시에 교착 상태이다.

• 선점을 통한 회복
  → 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 위한 회복
  → 교착 상태에 놓인 모든 프로세스를 강제 종료하는 방식
  → 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료하는 방식
  

 

무시

• 교착 상태 자체가 매우 드물게 발생하므로 교착 상태에 대한 조치 자체가 더 큰 오버헤드일 수 있음
• 교착 상태가 발생 시 운영체제는 이를 무시, 사용자가 직접 대처
• 현대 대부분의 운영체제가 채택

 

이화여자대학교 반효경 교수님의 운영체제 강의를 정리한 글입니다.

http://www.kocw.net/home/cview.do?cid=3646706b4347ef09

운영체제

 

또한 반효경 교수님의 "운영체제와 정보기술의 원리" 책을 참고하였습니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=238716482

운영체제와 정보기술의 원리