DeadLock(교착 상태)

2022. 6. 23. 23 : 42 복습을 위한 리팩토링 시작!

DeadLock

두 개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태가 교착 상태, DeadLock이다.

제한된 자원의 이용률을 높이고 시스템의 효율성을 높이고자 했을 때 발생하는 부작용이 교착 상태다.

교착상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램을 사용할 때 발생할 수 있다.

CPU를 안 쓰고 무한 대기 상태면 CPU 사용률이 0이 된다. OS입장에서는 너무나도 별로인 상태다.

해결방안으로는 프로세스를 종료, 교체하고 외부에서 강제로 해제시키는 방법이 있다.

DeadLock를 설명하는 아주 좋은 예시는 식사하는 철학자들 문제다. 아래 링크에서 확인할 수 있다.

https://ko.wikipedia.org/wiki/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94_%EC%B2%A0%ED%95%99%EC%9E%90%EB%93%A4_%EB%AC%B8%EC%A0%9C

식사하는 철학자들 문제 - 위키백과, 우리 모두의 백과사전

프로세스의 자원 이용 순서

1. 요청 : 자원 요청 -> 자원 할당
2. 사용 : 할당된 자원의 사용
3. 해제 : 할당 자원을 반납 후 종료

DeadLock의 발생 사례

1. 파일을 요청할 때 발생
2. 전용장치를 할당할 때 발생 (예 CD 복사)
3. 공유 변수를 사용할 때 발생
4. 스풀링 시스템에서 발생
5. 디스크를 공유할 때 발생
6. 네트워크에서 발생

DeadLock 필요조건

1. 상호 배제
2. 점유와 대기
3. 비선점
4. 원형 대기(순환 대기)

상호 배제

• 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
• 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다.
• 따라서 배타적인 자원을 사용하면 데드락이 발생한다.

비선점

• 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
• 어떤 자원을 빼앗을 수 있다면 시간 간격을 두고 자원을 공유할 수 있다.
• 하지만 자원을 빼앗을 수 없다면 공유할 수도 없으므로 데드락이 발생한다.

점유와 대기

• 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
• 다른 프로세스의 작업 진행을 방해하는 데드락이 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서,
  또 다른 자원을 기다리는 상태가 되어야 한다.

원형 대기

• 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
• 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아니다.
• 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면  프로세스들이 서로 양보하지 않기 때문에 데드락에 빠진다.

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 사이클이 나타나면 교착 상태이다. 타원은 프로세스 사각형은 자원을 나타낸다.

DeadLock 해결 방법

데드락 해결 방법은 예방, 회피, 탐지(검출), 복구(회복)가 있다.

데드락 예방

• 상호 배제 예방 - 자원에 따라 다르므로 상호 배제는 유지한다. 자원을 공유하지 못하게 하는 것은 쉽게 예를 들어 프린터를 공유하지 못하게 하는 것인데 말이 안 된다.
• 점유와 대기 예방 - 필요한 자원을 한꺼번에 요청하고 동시에 허용될 때까지 프로세스를 보류하는 방법이 있지만 비효율적이다. 전부 할당하거나 아니면 아예 할당하지 않는 방법을 적용하는 것이다. 점유와 대기 예방도 사실은 조금 어려운 부분이 있다.
• 비선점 예방 - 모든 자원을 강제로 회수할 수 있게 만든다. 그러나 우선순위에 따라 결정되므로 매 순간마다 높은 우선순위의 프로세스가 들어오면 계속 회수당한다. 따라서 비선점 조건을 예방하기는 어렵다.
• 원형 대기 예방 - 모든 자원에 순서를 부여하고, 순서 순으로만 자원을 할당하는 예방법이 있다. 그러나 프로세스 작업 진행에 유연성이 떨어지며 자원의 번호를 어떻게 부여할 것인지가 문제이다.

자원을 보호하기 위해 상호 배제와 비선점을 예방하기는 어렵다.
점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다. 

데드락 회피

데드락을 인정하고 회피 대책을 생각해보자. 먼저 프로세스의 시작 거부이다.

최대 요구량(현재 프로세스) + 최대 요구량(새로 시작할 프로세스) > 총 프로세스. 왼쪽 식이 성립되면 시작을 하지 않는다.
그러나 아예 시작을 하지 않는 것은 말이 안 된다.
따라서 자원 할당의 거부가 존재한다. 자원을 할당할 시 데드락 가능성이 높으면 할당을 거부한다.

교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고
시스템이 안정 상태를 유지하도록 자원을 할당한다.

예시로는 은행원 알고리즘이 존재한다. 이 은행원 알고리즘이 중요하다.

 

교착상태 회피의 원칙은 교착 상태가 발생하지 않을 수준까지만 자원을 나누어주는 것이다.

하지만 다음과 같은 문제가 있으므로 사용하지 않는다.

1. 프로세스가 자신이 사용할 모든 자원을 선언해야 한다. 이는 사실 불가능하다.
2. 시스템의 전체 자원 수가 고정적이어야 한다. 그러나 일시적인 고장이나 자원이 추가되는  일은 빈번하다.
3. 자원이 낭비된다.

데드락 탐지

회피와 예방은 쓸 수 없어 검출과 복구를 많이 사용한다.

교착상태가 발생하도록 허용하되, 교착상태의 발생을 탐지(검출)하고 복구(회복)한다.

교착 상태 검출 방법은 타임 아웃과 자원 할당 그래프를 이용하는 방법이 있다.

• 타임아웃
  타임아웃을 이용한 데드락 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 데드락이 발생한 것으로 간주하여 처리한다.
  데드락이 자주 발생하지 않을 것이라는 가정하에 사용한다. 다음과 같은 문제가 있다.
  1. 엉뚱한 프로세스가 종료될 수 있다. 타임아웃을 사용하면 다른 이유로 작업을 못하는 프로세스가 종료될 수 있기 때문이다.
  2. 모든 시스템에 적용할 수 없다. 분산 데이터베이스나 네트워크 경우에는 원인 파악이 어렵기 때문이다. 그러므로 타임아웃 방법을 적용하여 데드락을 파악하기는 어렵다. 그래도 타임아웃을 많이 사용한다고 한다.
  
  
• 자원 할당 그래프
  싸이클이 발생하면 교착 상태가 발생한 것으로 간주한다.
  그러나 다중 자원을 사용하는 경우에는 사이클이 있다고 해서 모두 데드락은 아니다.
  장점은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것이다.
  단점은 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 오버헤드가 발생한다는 것이다.
  그래서 자원이 추가 될 때마다 검사를 하는 것이 아니라, 일정 시간마다 하는 방법도 있다.

데드락 복구

데드락을 탐지하면 데드락을 푸는 후속 작업을 하는데, 이것이 데드락 회복이다.

데드락이 발생하면 프로세스를 종료하는데 이는 2가지 방법이 있다.

1. 데드락을 일으킨 모든 프로세스를 동시에 종료한다.
   그러나 이 방법은 종료된 프로세스들이 동시에 작업을 다시 시작하면 다시 데드락에 빠질 수 있다.
   그러므로 모든 프로세스를 강제로 종료한 후 다시 실행할 때는 순차적으로 실행해야 하며,
   이때 어떤 프로세스를 먼저 실행할 것인지 기준이 필요하다.
2. 데드락을 일으킨 프로세스 중 하나를 골라 순서대로 종료한다.
   데드락을 일으킨 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법이다.
   프로세스를 종료할 때 어떤 프로세스부터 종료할 것인지 다음과 같은 기준이 필요하다.
   • 우선순위가 낮은 프로세스를 먼저 종료한다.
   • 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료한다.
   • 위의  두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다.

데드락 복구 단계에서는 프로세스 강제 종료 뿐만 아니라, 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 한다.

시스템 복구는 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점으로 돌아가는 식으로 한다.

그러나 너무 무분별하게 하면 시스템에 부하가 가므로 선택적으로 사용해야 한다.

이상으로 포스팅을 마치겠습니다!

 

2022. 6. 24. 00 : 30 수정 완료

복습 완료!

 

참고 자료

쉽게 배우는 운영체제 (저자 : 조성호)

https://www.kyobobook.co.kr/product/detailViewKor.laf?barcode=9791156644071 

운영체제 - 교보문고