교착 상태(deadlock) 해결

 

교착 상태 회피 (Deadlock Avoidance)

: 프로세스에게 자원을 할당할 때, 자원을 어느 수준까지 할당하면 교착 상태가 발생하는지 파악해서 그 수준을 넘지 않도록 조절해서 할당함

• 교착 상태 회피는 전체 자원의 수와 현재 할당된 자원의 수를 기준으로 시스템의 상태를 두 가지로 나눔
  
  • 안전 상태(Safe State)
    : 모든 프로세스가 정상적으로 종료될 수 있는 상태
  • 불안전 상태(Unsafe State)
    : 당장은 문제가 없지만, 교착 상태로 이어질 가능성이 있는 상태
    
    • 불안전 상태라고 해서 무조건 교착 상태에 빠지는 건 아니지만 위험성이 커지므로 피하는 게 좋음

 

 

 

교착 상태 검출 방법

1. 가벼운 검출: 타이머 사용

• 프로세스가 일정 시간동안 작업을 진행하지 않으면 교착 상태가 발생했다고 간주하고 교착 상태를 해결함
• 교착 상태 해결 방법: 일정 시점마다 체크 포인트를 만들어서 작업을 저장하고, 타임 아웃으로 교착 상태가 발생하면 마지막으로 저장했던 체크 포인트로 롤백함

 

2. 무거운 검출: 자원 할당 그래프 사용

• 운영체제가 자원의 할당 상태를 그래프 형태로 실시간 추적함
• 교착 상태 해결 방법: 그래프에 사이클이 생기면 교착 상태로 판단
  

  

• 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착 상태가 발생하면 해결함
• 교착 상태를 일으킨 프로세스를 강제 종료시킴 →재실행 시킬 때 체크 포인트로 롤백함
  
  
• 장점
  
  • 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 해서 오버헤드가 발생함
• 단점
  
  • 가벼운 교착 상태 검출에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않음

 

 

 

은행원 알고리즘 (Banker’s Algorithm)

• 교착 상태 회피를 표현한 대표적인 알고리즘
• 은행이 고객에게 대출해줄 때, 회수 가능한 범위 내에서만 대출해주는 방식에서 착안함
• 비용이 비싸고 비효율적임

 

예시

• 은행에 총 자금 1,000만 원이 있음
• 사업가 A가 500만 원, B가 400만 원을 빌림
  → 은행에 남은 자금은 100만 원
• 두 사람 모두 "200만 원만 더 빌려주면 갚을 수 있다"고 함
• 하지만 은행은 100만 원밖에 없어서 아무에게도 빌려줄 수 없고 빌려준 돈을 받지도 못함
  → 교착 상태 발생
• 이런 상황을 피하기 위해, 은행은 고객에게 돈을 빌려줄 때, 은행의 여유 자금과 사업가들의 대출 상환 가능성을 확인하고 빌려주기로 함

 

 

 

운영체제에서 은행원 알고리즘을 구현하는 방법

• 운영체제가 은행원 알고리즘을 사용해서 자원을 할당할 때, "지금 자원을 이렇게 나눠줘도 안전할까?" 라는 걸 판단함
  
  • 안전 상태
    : 지금 이대로 자원을 할당해도, 모든 프로세스가 언젠가는 꼭 작업을 마치고 자원을 반납할 수 있음
    → 교착 상태에 빠질 일이 없으니 자원을 할당해도 괜찮음⭕
  • 불안전 상태
    : 자원을 지금 이대로 나눠줬을 때, 어떤 프로세스는 끝까지 자원을 못 받아서 영원히 대기할 수도 있음
    → 꼭 교착 상태로 이어지는 건 아니지만, 가능성이 높아지므로 위험함❌
• 운영체제가 은행원 알고리즘을 적용하려면 두 가지 정보가 필요함
  
  • 시스템의 총 자원 수
    ⇒ 운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 갖고 있는 전체 자원의 수를 알고 있어야 함
  • 각 프로세스의 최대 요구 자원 수
    ⇒ 프로세스들은 각자 자기가 필요한 자원의 최대 숫자를 운영체제에 알려줘야 함

 

 

 

✅ 안전 상태 예시

• 시스템의 총 자원 수 = 14
• 현재 사용 가능한 자원 = 2 (14 - 12)
  → P2의 작업이 끝나서 6개로 늘어남

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	5	4
P2	6	4 → 0	2 → 6
P3	4	3	1

 

과정

1. 사용 가능한 자원 2개 → P1은 4개 필요 → 요청 거절
2. P2는 2개만 필요 → 사용 가능한 자원 할당 → P2는 작업을 완료한 후 자원 6개 반납
3. 사용 가능한 자원이 6개로 증가 → P1(4개), P3(1개) 요청 모두 수락 가능
   ⇒ 모든 프로세스가 완료될 수 있는 안정 상태임

 

 

 

❌ 불안전 상태 예시

• 시스템의 총 자원 수 = 14
• 현재 사용 가능한 자원 = 1

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	4	2
P2	6	4	2
P3	4	2	2

• 현재 자원이 1개밖에 없어서 어떤 프로세스도 요청을 만족할 수 없음
  ⇒ 불안전 상태에 해당함