교착 상태란?

• 식사하는 철학자 문제 -> 철학자들이 모두 동시에 식사를 하려고 하면 식사를 할 수 없게 됨
• 이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 상태를 교착 상태(Deadlock)로 부름
• 교착 상태를 해결하기 위해서는 교착 상태의 상황을 정확히 표현하고, 교착 상태가 일어난 근본적인 이유를 이해해야함
• 교착 상태가 발생하는 조건으로는 상호 배제, 점유와 대기, 비선점, 원형 대기가 있고, 이 4개를 모두 만족하면 교착 상태가 발생할 수 있음
  상호 배제: 한 프로세스가 쓰는 자원을 다른 프로세스가 사용할 수 없는 상태
  점유와 대기: 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
  비선점: 어떤 프로세스도 다른 프로세스의 자원을 강제로 못빼앗는 상태
  원형 대기: 프로세스들이 원의 형태로 자원을 대기하는 상태

자원 할당 그래프

• 교착 상태의 발생 조건을 파악하기 위한 그래프
• 어떤 프로세스가 어떤 자원을 할당 받아 사용중인가, 어떤 자원을 기다리는가 확인 가능
  
• 프로세스는 원으로, 자원의 종류는 사각형으로 표현함
• 사용 가능한 자원의 개수는 자원 사각형 내에 점으로 표현함
• 어떤 프로세스가 자원을 할당 받아 사용 중이면 자원에서 프로세스를 향해 화살표를 표시
• 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
  
• 교착 상태가 일어나게 된 경우 자원 할당 그래프는 원의 형태를 띄게 됨

교착 상태 예방

• 교착 상태가 발생하지 않도록 교착 상태 발생 조건 중 하나를 없에버리는 방법
• 교착 상태가 발생하지 않음을 보장할 수 있지만 부작용이 발생함
• 상호 배제x -> 모든 자원을 공유 가능하게 만든다 -> 현실적으로 불가능
• 점유와 대기x -> 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않음 -> 자원의 활용도가 너무 떨어지게 됨
• 비선점x -> 선점이 가능한 자원들에서는 효과적이만 모든 자원이 선점 가능한 것은 아님
• 원형 대기x -> 자원에 번호를 붙이고 오름차순으로 할당 -> 가장 현실적이지만 자원에 번호를 붙이는 것은 어려운 작업이고, 어떤 자원에 어떤 번호를 붙이는가에 따라 활용률이 달라짐

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
• 배분 가능한 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원을 배분함
• 안전 상태에서 안전 상태로 움직이는 경우만 자원을 할당하게 됨
  안전 상태: 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태, 즉 안전 순서열이 있는 상태
  불안전 상태: 교착 상태가 발생할 수도 있는 상태, 즉 안전 순서열이 없는 상태
  안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당하고, 교착 상태가 검출되면 회복
• 선점, 프로세스 강제 종료를 통해 교착 상태를 벗어남
  선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아줌
  프로세스 강제 종료를 통한 회복은 교착 상태에 놓인 프로세스를 모두 강제 종료하거나, 교착 상태가 해결될 때까지 한 프로세스씩 강제로 종료함. 단 이 때 모두 강제종료하면 작업 내역을 한번에 잃게 되고, 하나씩 종료하면 오버헤드가 발생하게 됨

출처:
https://www.youtube.com/watch?v=Kcv0_Yb8Rqw&list=PLVsNizTWUw7FCS83JhC1vflK8OcLRG0Hl&index=37
혼자 공부하는 컴퓨터 구조+운영체제, 강민철, 한빛미디어