교착 상태

교착 상태란?

교착상태: 일어나지 않을 사건을 기다리며 무한히 대기하는 현상

→ 식사하는 철학자문제는 교착 상태의 발생을 보여 주는 예시

• 자원 할당 그래프를 이용해 교착 상태를 표현할 수 있다.
  
• 교착 상태 발생 조건은 상호배제, 점유와 대기, 비선점, 원형 대기이다.
  • 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없다
  • 점유와 대기 : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
  • 비선점: 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗을 수 없다.
  • 원형 대기: 자원 할당 그래프가 사이클을 이루는 원의 형태로 그려짐 → 모든 조건을 만족해야 데드락 발생!

교착 상태 해결 방법

• 교착 상태 예방: 교착 상태의 발생 조건 중 하나를 충족하지 못하게 하는 방법
  • 상호 배제를 없애기 : 모든 자원을 공유 가능하게 만든다는 말 → 다소 무리
  • 점유와 대기 없애기: 특정 프로세스에 자원을 몰빵 or 아예 할당하지 않기
    • 당장 자원이 필요해도 기다릴수 밖에 없는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원이 생긴다. → 자원 활용률이 낮아진다.
    • 많은 자원을 필요로 하는 프로세스가 무한정 기다려야 할 수 있다. → 기아 현상 발생
  • 비선점 조건 없애기: 자원 이용중인 프로세스로부터 해당 자원을 뺏기
    • 선점 가능한 일부 자원한테는 효과적
    • 모든 자원이 선점 가능한 것은 아니다. (ex. 프린터기) → 범용성 떨어진다.
  • 원형 대기 조건을 없애기: 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하기
    • 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일은 어렵다. → 무리
    • 자원에 어떤 번호를 붙으는지에 따라 특정 자원의 활용률이 떨어진다.
• 교착 상태 회피: 안전 상태를 유지할 수 있는 경우에만 자원을 할당하는 방법
  • 안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
  • 안전 상태: 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 → 안전 순서열이 있는 상태
  • 불안전 상태: 교착 상태가 발생할 수도 있는 상황 → 안전 순서열이 없는 상태
• 교착 상태 검출 후 회복: 교착 상태 발생 여부를 주기적으로 검사하고, 교착 상태가 발생하면 그때그때 회복하는 방식
  • 선점을 통한 회복: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
  • 프로세스 강제 종료를 통한 회복: 교착 상태에 놓인 프로세스 모두 강제종료 → 많은 프로세스들이 작업 내역 잃을 수 있다. 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료 → 교착 상태가 없어졌는지 확인하는 과정에서 오버헤드 야기한다.
• 타조 알고리즘: 교착 상태를 아예 무시!