[운영체제] 교착상태와 은행원 알고리즘

교착상태 Dead Lock

프로세스들이 서로의 자원을 기다리며 무한히 기다리는 현상이다. 아래 4개 조건이 성립할 때 교착상태가 발생한다.

• 비선점 Non-Preemption : 자원을 선점하지 않음
• 환형대기 Circular Wait  : 원형으로 꼬리물기처럼 대기 중
• 상호배제 Mutual Exclusion : 자원은 하나의 프로세스만 점유 가능
• 점유 대기 Hold and Wait : 자원을 점유하고 있으면서 추가로 다른 자원을 기다리고 있는 상태

 

교착상태 처리하기

• 예방 Prevention
  
  • 상호배제 부정 : 여러 프로세스가 공유 자원 사용
  • 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
  • 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
  • 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

말 그대로 교착상태를 예방하는 것이다. 교착상태 조건 중 하나씩 제거한다. 하지만 자원낭비가 크다!

 

• 회피 Avoidance

운영체제가 교착상태가 일어날 수 있는지 검사를 하고 가능성이 없을 경우에만 자원을 할당한다. 주로 은행원 알고리즘이 사용된다.

 

• 탐지 후 회복 Detecttion and Recovery

운영체제가 교착상태가 일어났는지 주기적으로 탐색한다. 만약 교착상태가 발견(detect)되면 자원을 강제 종료시켜 교착상태를 회복한다. 자원 할당 그래프를 이용해 탐지 알고리즘을 수행한다.

 

은행원 알고리즘

은행에서 현금을 고객에게 할당하는 것에서 유래되었다. 대출금과 잔고를 비교해 일정 수준 이하까지 대출을 해주는 은행처럼 운영체제는 안정 상태까지만 프로세스에 자원을 할당한다. 불안정 상태 전까지 자원 분배 후, 프로세스가 자원을 반납할 때까지 할당을 하지 않는다.

 

은행원 알고리즘을 수행하기 위해 3가지가 필요하다

1. Max : 프로세스가 자원을 얼마나 요청하는지

2. Allocated : 현재 프로세스가 얼마나 자원을 점유 중인지

3. Available : 현재 시스템이 자원 할당을 얼마나 가능한지

 

*단점*

- 프로세스들이 요구하는 최대 자원량을 알아야 함

- 할당할 수 있는 자원량이 일정해야 함

- 항상 불안전 상태를 방지해야 하므로 자원 사용률이 낮아짐.

- 프로세스가 자원 반납을 유한 시간 내에 해야 함.

 

 

 

-> 어쨌든 알고리즘을 사용하여 먼가 하면 오버헤드가 발생함

 

https://jhnyang.tistory.com/102