6. 데드락

데드락 : 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태. 자원, 공유 변수, 프로그램 등을 사용할 때 발생

 

자원 할당 그래프 : 프로세스가 어떤 자원을 사용 중이고, 기다리고 있는지 방향성이 있는 그래프

 

데드락 발생조건 : 4가지를 모두 충족해야 데드락이 발생

• 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적 자원이여야 함
• 비선점 : 한 프로세스가 사용하는 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이여야 함
• 점유와 대기 : 프로세스가 자원을 할당받은 상태에서 다른 자원을 기다리는 상태이여야 함
• 원형 대기 : 점유와 대기를 하는 프로세스들이 원을 이루어야 함

배타적 자원을 여러 프로세스가 사용하며, 뺏을 수 없는 비선점 자원이여야 하고, 각자의 자원을 가진 채로 다른 프로세스가 가진 자원을 기다리고, 이러한 프로세스들이 원을 이루면 데드락이 발생한다.

 

데드락 해결방법 : 발생조건 중 1개라도 막는다면 데드락은 발생하지 않음

• 상호 배제 예방 : 모든 자원을 배타적 자원이 아닌 공유가 가능해지면 발생하지 않음 → 현실적으로 어려움. 동시에 자원에 접근을 하면 원치않은 결과가 발생됨
• 비선점 예방 : 모든 자원을 빼앗을 수 있게 만드는 방법이지만, 현실적으로 임계구역 보호에 어긋나며 뺏는 것 자체가 starvation을 초래할 수 있음
• 점유와 대기 예방 : 전부 할당하거나, 아예 자원을 모두 반납함 → 현실적으로 어려움. 추가로 필요한 자원이 생길 지에 대한 여부를 알 기 어렵고, 미리 자원들을 선점해버리면 당장 사용하지 않을 자원들에 대한 낭비가 있고, 많은 자원을 필요로 하는 프로세스가 유리하며, 이러한 과정은 결국 일괄 작업처럼 작동됨
• 원형 대기 예방 : 모든 자원에 숫자를 부여하고, 큰 방향으로만 자원을 할당하는 방식으로 자원을 한 방향으로만 사용 가능하게 하여 원형을 만들지 않게 함 → 프로세스 작업 유연성이 떨어짐, 자원의 번호를 어떤식으로 부여할 지에 대한 문제 발생

자원을 보호하기 위해 상호배제 예방과 비선점 예방은 어렵고, 점유와 대기 예방과 원형 대기 예방은 프로세스 작업 방식을 제한하고, 자원을 낭비함

 

회피 : 프로세스에 자원을 할당할 때 어느 수준이상의 자원을 나누었을 때 데드락이 발생하는 지 파악하여 그 수준이하로 나누는 방식. 할당된 자원이 클 수록 불안정 상태가 커지지만, 확률일 뿐 데드락이 무조건 발생하는 건 아님. 안정 상태를 유지하는 범위에서 자원을 할당하여 데드락을 피함

 

전체 자원 : 시스템 내 전체 자원의 수

가용 자원 : 전체 자원 - 모든 프로세스들에 할당된 자원 (쓸 수 있는 자원)

최대 자원 : 각 프로세스가 필요하다고 운영체제에 선언한 자원의 수

할당 자원 : 할당 받은 자원

기대 자원 : 최대 자원 - 할당 자원(앞으로 사용할 자원의 수) 

 

은행원(뱅커) 알고리즘 : 가용 자원이 프로세스들이 필요로 하는 기대 자원들 중 크거나 같은 경우가 한 번 이상인 경우를 안정 상태라고 하는데 안정 상태의 경우의 프로세스에게만 자원을 빌려주는 알고리즘. 프로세스가 자신이 필요로 하는 자원을 미리 선언해야 하고, 전체 자원 수가 고정적이여하며, 자원이 낭비됨

 

(가벼운) 검출 : 예방은 구현하기 어렵고, 회피는 구현가능하나 자원 낭비 → 현실적으론 프로세스의 작업을 관찰하며 데드락 발생 여부를 확인하여 발생 시 회복단계 진행 → 일정시간 작업되지 않은 프로세스를 데드락으로 판단하여 처리함. 하지만 2가지 문제점이 발생

• 데드락이 발생하여 데드락인지 단순히 오래 걸리는 것 때문인지 알 수 없어 엉뚱한 프로세스가 종료될 수 있음
• 분산 시스템 경우 네트워크를 통한 단순 처리 지연이 발생될 수 있음

 (무거운) 검출 : 자원할당 그래프를 이용한 방법. 사이클이 존재하면 데드락이 발생함을 확인할 수 있음

 

회복 : 데드락을 푸는 작업

• 데드락을 발생시킨 모든 프로세스 종료 : 다시 시작하면 데드락 발생확률 높음 → 재 실행시 순차적 실행 + 어떤 프로세스 부터 실행할 지에 대한 기준
• 데드락을 발생시킨 프로세스 중 하나를 골라 종료 : 우선순위 낮은 프로세스 먼저 종료 → 같으면 짧은 프로세스 → 자원을 많이 쓰는 순으로 정리함

다중 자원을 지원하는 경우 사이클이 발생하더라도 끝날 가능성이 있는 그래프의 화살표를 지웠을 때의 상황을 보고 여기서 사이클이 존재하면 데드락이라고 판단할 수 있음