[운영체제] 6. 교착 상태 (Deadlock)

본 게시물은 운영체제 과목의 강의영상과 강의자료를 바탕으로 작성한 학습용 게시물입니다.

---

교착상태 문제

# 교착상태

• 한 프로세스가 자원을 요청하였으나, 그 자원을 필요로 하는 시간에 사용할 수 없다면 대기 상태로 진입하고, 그 필요 자원이 또 다른 자원의 할당을 위해 대기 중인 다른 프로세스에 의해 점유되어 있고 이런 형태의 대기가 꼬리에 꼬리를 물어 환형을 이루게 되면, 대기에 참여한 프로세스들은 영원히 대기 상태에서 벗어날 수 없다. 
  → 교착 상태 발생 

---

교착상태 특징

• 다음의 4가지 조건이 동시에 만족될 때 교착상태 발생 
  1. 상호 배제  : 할당 후 반환까지 한 프로세스만 사용하는 자원이어야 함
  2. 점유하며 대기  : 적어도 각 프로세스가 하나의 자원을 보유하고 현재 다른 프로세스에게 점유된 자원을 추가로 얻기 위해 반드시 대기해야함 
  3. 비선점 : 자발적으로만 방출될 수 있다. 
  4. 환형 대기 

# 자원 할당 그래프 

• 정점 : 프로세스와 자원의 집합으로 분할 
• 유향 에지 
  - P -> R : 요청 
  - R -> P : 할당 
• 사이클 없다면 교착상태 x
• 사이클 있을 경우 
  - 각 자원 유형마다 하나씩의 자원밖에 없으면 반드시 교착상태 발생 
  - 각 자원 유형마다 여러 개의 자원이 있으면, 교착상태 발생할 가능성 o 

---

교착상태 예방

1. 상호배제 조건을 부정
   -일반적으로 상호 배제를 부인하여 교착 상태를 방지하는 것은 불가능 
2. 점유하며 대기 조건을 부정 
   - 대기없음 : 자원의 활용도 낮음
   - 점유없음 : 기아 상태의 발생 가능성 증가 
3. 비선점 조건을 부정 
   - 대기상태로 돌아가면서 현재 할당 받은 것을 강제로 반환토록 함 
4. 환형대기 조건을 부정 
   - 번호가 증가하는 순서대로만 자원을 요청하도록 강제 

# 식사하는 철학자 문제 

• 포크의 번호가 증가하는 순으로만 포크를 집도록 함 

---

교착상태 회피

• 안정 순열 
• 안정 상태 
• 회피 : 자원 할당 시 시스템이 항상 안정상태에 있도록 유지하는 것 
• Banker's 알고리즘 
• safty 알고리즘 

---

교착상태 탐지 

• 교착상태를 검사하는 알고리즘을 주기적으로 수행 

---

교착상태 복구 

• 프로세스를 종료하고 자원을 회수 
  - 교착상태 프로세스를 모두 중지 또는 교착상태가 제거될 때까지 한 프로세스씩 중지 
• 교착상태에 있는 하나 이상의 프로세스들로부터 자원을 선점 
  - 교착상태에 있는 프로세스가 갖고 있는 자원을 계속적으로 선점하여 다른 프로세스에게 주는 방식 
  - 후퇴 필요 
  - 기아 발생 고려