운영체제 8장 정리 데드락 DeadLock 교착상태

Dead Lock 교착상태

교착 상태란 다른 프로세스가 자원을 계속 해서 점유하고 기다리는 프로세스가 자원을 요구하는 과정에서 무한정으로 대기하는 것을 말합니다.

 

데드락 충족 조건

1. 상호 배제

• 자원을 여러 프로세스가 이용하려 할 때

2. 점유 대기

• 프로세스가 하나의 자원을 점유하면서도 다른 프로세스에 할당된 자원을 점유하려 할 때 대기를 안 할때

3. 비선점

• 다른 프로세스가 자원을 선점해서 빼았지 않을 때

4. 순환 대기

• 점유 대기 상태의 프로세스가 서로가 될 때

데드락의 해결 방법

1. 데드락 예방

• 상호 배제 - 하나의 자원은 하나의 프로세스만 이용하게 한다.
• 점유 대기 - 선점 스케줄링 방식의 프로세스가 자원 할당을 요청할 때 어떤 것이라도 자원을 놓을 수 있어야 한다.
• 비선점 - 공유 자원을 프로세스가 있더라도 선점이 가능하게 해야 한다.
• 환형 대기 - 자원마다 번호를 매겨 시간이 지날수록 우선순위를 높어 자원 요청을 하게 한다.

2. 데드락 회피

이론상의 가정으로는 4개의 조건을 만족해야 한다.

• 프로세스의 개수 고정
• 자원의 종류, 수가 고정
• 프로세스의 요구 자원 수 알아야 한다.
• 프로세스는 자원 사용 후 반드시 반납해야 한다.

그러나 실시간 환경에서 적용하기는 절대적으로 어렵다. 다른 알고리즘을 적용해야 한다.

1. Safe State 알고리즘
   1. • safe한 상태가 존재해 모든 프로세스가 교착상태 없이 안전하게 종료할 수 있는 상태를 말한다.
      • unsafe 상태에는 데드락 발생 확률이 있기 때문에 안전하게 종료를 할 수 없다
2. 자원 할당 그래프 알고리즘 - 자원 유형에 인스턴스가 하나만 있는 경우 그래프 알고리즘으로 교착상태를 회피한다.
3. 은행원 알고리즘 - 자원 유형에 인스턴스가 많을 경우 적용하는 방법

3. 데드락 탐지

1. 대기 그래프 - 자원 할당 그래프를 변형한 그래프로 사이클이 존재하게 되면 교착 상태로 판단한다.
2. 은행원 알고리즘 - 각 자원의 요청 개수를 받고 safe state 인지 확인 후 불안정 상태일 때 데드락이라고 판단한다.

4. 데드락 복구

1. 프로세스 종료
   1. • 교착 상태의 프로세스 모두 중지
      • 교착 상태 제거될 때까지만 하나씩 중지
2. 자원 선점 - 교착 상태의 점유된 자원을 다른 프로세스가 할당 받아 교착 상태의 프로세스를 일시 정지 시킨다.
   1. • 희생자 선택 - 최소 피해 프로세스를 선택
      • 롤백 - 선점 프로세스를 문제 없던 상태로 롤백
      • 기아 - Aging 방식으로 우선 순위를 높이는 방법으로 복구