본 글은 인프런 강의를 바탕으로 정리한 개인 학습 기록입니다.
출처: <그림으로 쉽게 배우는 운영체제>

목차

1. 데드락이란?
2. 데드락 해결

1. 데드락이란?

---

1) 교착상태란

• 여러 프로세스가 서로 자원을 기다리며 멈춰 있는 상태
• 누구도 작업을 끝내지 못하고 계속 기다리게 됨

2) 왜 발생하는가

• 여러 프로세스가 공유자원을 함께 사용하려고 하기 때문
• 공유자원이 없다면 교착상태도 발생하지 않음

3) 예시

도로 정체

• 차들이 서로 길이 열리길 기다리며 멈춤
• 이때 공유자원은 도로

식사하는 철학자 문제

• 철학자들이 포크를 하나씩 집고
• 나머지 포크를 기다리면
• 모두가 서로를 기다리게 되어 교착상태가 생김

4) 교착상태 발생 조건 4가지

1. 상호배제

• 어떤 자원은 한 번에 한 프로세스만 사용 가능
• 예: 포크 하나를 두 사람이 동시에 사용할 수 없음

2. 비선점

• 이미 다른 프로세스가 가진 자원을 강제로 빼앗을 수 없음

3. 점유와 대기

• 한 자원을 가진 상태에서 다른 자원을 추가로 기다리는 것

4. 원형 대기

• 자원을 기다리는 관계가 원형 구조를 이루는 것
• 서로가 서로를 기다리는 상태가 됨

5) 의미

• 위 4가지 조건이 모두 만족될 때만 교착상태가 발생함
• 따라서 이 중 하나라도 깨지면 교착상태는 발생하지 않음

2. 데드락 해결

---

1) 교착상태 회피

• 자원을 할당하기 전에 이 요청을 받아도 시스템이 안전한지 검사하는 방식
• 목표는 항상 안전 상태를 유지하는 것임

2) 안전 상태와 불안전 상태

• 안전 상태

  • 적절한 실행 순서가 존재해서
  • 모든 프로세스가 결국 필요한 자원을 받고 종료할 수 있는 상태

• 불안전 상태

  • 당장 교착상태는 아닐 수 있지만
  • 교착상태에 빠질 위험이 큰 상태

3) 은행원 알고리즘

• 프로세스에 자원을 주기 전에 앞으로도 모든 프로세스를 끝낼 수 있는지 확인하는 방식
• 은행이 대출을 해주기 전에 파산하지 않을지 계산하는 것과 비슷함

4) 은행원 알고리즘에 필요한 정보

• 전체 자원 수
• 각 프로세스의 최대 필요 자원
• 현재 각 프로세스에 할당된 자원 수
• 현재 사용 가능한 자원 수
• 그리고
  Need = Max - Allocated 를 계산함

5) 동작 방식

• 현재 사용 가능한 자원으로 어떤 프로세스의 남은 필요량을 충족할 수 있는지 확인함
• 가능하면 그 프로세스가 끝난다고 가정하고 자원을 반납받아 다음 프로세스를 검사함
• 이런 순서가 끝까지 가능하면 안전 상태
• 중간에 더 이상 진행할 수 없으면 불안전 상태

6) 은행원 알고리즘의 한계

• 매번 안전성 검사를 해야 해서 비용이 큼
• 프로세스의 최대 자원 요구량을 미리 알아야 함
• 그래서 실제로는 비효율적인 경우가 많음

교착상태 검출 방식

7) 가벼운 검출 방식: 타이머 기반

• 프로세스가 오랫동안 진행되지 않으면 교착상태로 간주하는 방식
• 일정 시점의 작업 상태를 체크포인트로 저장해 둠
• 문제가 생기면 롤백해서 다시 시작함

단점

• 실제 교착상태가 아닌데도 단순히 오래 걸렸다는 이유로 잘못 판단할 수 있음

8) 무거운 검출 방식: 자원할당 그래프 기반

• 운영체제가 자원할당 그래프를 유지함
• 어떤 프로세스가 어떤 자원을 가지고 있고, 또 어떤 자원을 기다리는지 추적함
• 그래프에 순환(cycle) 이 생기면 교착상태로 판단함

특징

• 더 정확하게 교착상태를 찾을 수 있음
• 대신 그래프를 계속 관리하고 검사해야 해서 오버헤드가 큼

9) 검출 후 해결

• 교착상태를 일으킨 프로세스를 강제 종료할 수 있음
• 또는 체크포인트로 롤백해서 복구할 수 있음