[혼공컴운] chapter.13 교착 상태

2023.08.13 - [컴퓨터 공학/운영체제] - [혼공컴운] chapter.12 프로세스 동기화

[혼공컴운] chapter.12 프로세스 동기화

 

 

13-1 교착 상태란

• 식사하는 철학자 문제
  : 교착 상태를 설명하는 대표적 문제 상황

식사하는 철학자 문제

1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1번 부터 반복한다.

→ 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없고 영원히 생각만 하는 상황 발생. 즉, 교착 상태(deadlock) 발생.

• 교착 상태(deadlock): 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상.
  교착 상태는 자원 할당 그래프를 통해 단순하게 표현 가능.
  
  
  
  
  
• 자원 할당 그래프(resource-allocation graph)
  • 프로세스는 원, 자원의 종류는 사각형으로 표현
  • 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현
  • 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표 표시
  • 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표 표시

자원 할당 그래프 예시

자원 할당 그래프로 표현한 식사하는 철학자 문제

* 교착 상태가 일어난 그래프는 원의 형태를 띄고 있다.

 

• 교착 상태 발생 조건
  • 상호 배제(mutual exclusion)
    : 어떤 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때 교착 상태 발생 가능.
  • 점유와 대기(hold and wait)
    : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태.
  • 비선점(nonpreemptive)
    : 다른 프로세스의 자원을 강제적으로 빼앗을 수 없는 상태.
  • 원형 대기(circular wait)
    : 프로세스들과 프로세스가 요창 및 할당받은 자원이 원의 형태를 이루어 대기하는 상태.
    
    

위 네 가지 조건에서 교착 상태 발생 가능.

 

 

 

 

 

 

---

 

 

13-2 교착 상태 해결 방법

• 교착 상태 예방
  • 자원의 상호 배제
    → 모든 자원 공유 가능 상태. 이론적으로 교착 상태를 없앨 수 있으나, 현실적으로 무리가 있는 방법
  • 점유와 대기
    → 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식. 이론적으로는 교착 상태 해결 가능하나, 자원의 활용률이 낮아질 우려가 있음.
  • 비선점 조건
    → 자원을 이용중인 프로세스로부터 자원을 빼앗을 수 있는 방식. 교착 상태 해결 가능.
    선점하여 사용할 수 있는 자원에 대해서는 유효하지만 선점이 불가능한 자원은 빼앗을 수 없으므로 범용성이 떨어짐. 
  • 원형 대기 조건
    → 모든 자원에 번호를 붙여 순서대로 자원 할당. 번호를 붙임에 따라 특정 자원의 활용률이 낮아지며, 수많은 자원들에 번호를 부여하는 것은 어려움이 있음.
    * 식사하는 철학자 문제에서 원형 테이블이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황.
    
    
    
• 교착 상태 회피
  - 안전 상태(safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태.
  - 불안전 상태(unsafe state): 교착 상태가 발생할 수도 있는 상태. 안전 순서열이 없는 상황.
  - 안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서.
  
  
  
• 안전 상태, 불안전 상태, 안전 순서열 예시

• 할당 가능 자원: 12
• 할당한 자원의 총합: 9
• 남은 자원: 3

이 상태는 안전 상태. 안전 순서열: P2->P1->P3

* 현재 사용량의 변화에 따른 교착 상태 발생 상황

• 할당 가능 자원: 12
• 할당한 자원의 총합: 10
• 남은 자원: 2

이 상태는 불안전 상태. 안전 순서열 없음. 교착 상태 발생할 가능성 존재.
* 각 프로세스들이 최대로 자원을 요구하였을 시 P2의 작업을 올바르게 마치더라도 P1과 P3은 서로의 자원을 무한정 대기. 교착 상태 발생.

 

 

 

• 교착 상태 검출 후 회복
  • 선점을 통한 회복
    : 교착 상태가 해결될 때 까지 한 프로세스씩 자원을 몰아주는 방식.
  • 프로세스 강제 종료를 통한 회복
    : 교착 상태에 놓인 프로세스를 모두 강제 종료 하거나, 교착 상태가 없어질 때 까지 한 프로세스씩 강제 종료.
  • 타조 알고리즘(ostrich algorithm)
    : 잠재적 문제를 무시로 대처하는 방식.
    
    
    
    
    

 

 

 

---

* 오류 지적은 환영입니다.^^ *