교착상태(Deadlocks)

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
경성대학교 양희재 교수님 수업 영상을 듣고 정리하였습니다.

교착상태: Deadlocks

간혹 동기화를 하다보면 Deadlock에 빠지는 경우가 있다. (프로세스 관리에서 해결해야하는 문제중 하나!)

프로세스는 실행을 위해 여러 자원을 필요로 한다. (CPU, 메모리, 파일, 프린터 등..) 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할때(다른 프로세스가 이미 사용중일때) 나머지는 대기를 해야한다. 그리고 다른 프로세스 역시 다른 자원을 가지려고 대기할 때 교착상태 가능성 > 이를 os가 잘못 나누어주면 교착상태에 빠진다.

• 교착상태 필요조건(Necessary Conditions)
  • Mutual exclusive(상호배타): 하나가 사용하면 나머지는 기다려야한다.
  • Hold and wait(보유 및 대기): 하나 가지고 있으면서 나머지가꺼도 기다린다.
  • No Preemption(비선점): 순서를 강제할 수 없고 순서대로 이루어진다.
  • Circular wait(환형대기): 하나의 원을 만들어놓고 있다.

자원(Resource)

Deadlock이 일어나는 이유는 결국 자원 때문이다. 자원(=하드웨어 자원) 자원을 할당받기 위해서는 os에 요청을 하고 요청이 올바르면 자원을 할당해주는데, 이를 다 사용하면 다시 os에게 반납을 하게 되는데, 이런식으로 자원을 사용하게 된다. 이 똑같은 자원이 여러개 있을 수도 있다.(여러개의 자원 = instance)

• 동일 자원
  • 동일 형식(type)자원이 여러개 있을 수 있다.
  • 예) 동일 CPU 2개, 동일 프린터 3개 등
• 자원의 사용
  • 요청(request) -> 사용(use) -> 반납(release)

- 자원 할당도(Resource Allocation Graph)

• 어떤 자원이 어떤 프로세스에게 할당되었는가?
• 어떤 프로세스가 어떤 자원을 할당받으려고 기다리고 있었는가?
• 자원: 사각형, 프로세스: 원, 할당: 화살표
• 교착상태가 되려면 이 그림이 원을 만들고 있어야 한다.

• 교착상태의 필요조건
  • 자원 할당도 상에 원이 만들어져야 한다(환형조건): 충분조건은 아님!
  • 피하려면: 짝수(오->왼), 홀수(왼->오)

교착상태를 처리하는 방법

교착상태 방지(Deadlock Prevention)

교착상태의 4가지 필요조검 중 한 가지 이상을 불만족시킨다.

• 상호배타(Mutual exclusive): 자원을 공유 가능하게 -> 원천적으로는 실현이 불가능하다.
• 보유 및 대기(Hold & Wait): 자원을 가지고 있으면서 다른 자원을 기다리지 않게 -> 일부는 가능하다.
  • 예) 자원이 없는 상태에서 모든 자원 대기, 일부 자원만 가용하면 보유자원을 모두 놓아주기(혹은 가지고 있다면 두개를 동시에 가지도록!)
  • 단점: 자원 활용률 저하, 기아 (starvation)
• 비선점(NonPreemptive): 자원을 선점가능하게 -> 원천적으로는 실현이 불가능하다. (예; 프린터)
• 환형대기(Circular wait)
  • 예) 자원에 번호부여하여 번호 오름차순으로 자원 요청
  • 단점: 자원 활용률 저하

교착상태 회피(Deadlock Avoidance)

교착상태 자체를 자원 요청에 대해 os에서의 잘못된 승인이 이루어져 발생한 것으로 생각한다.

첫번째 예제 - 안전한 할당(Safe Allocation)

• 12개의 magnetic tape 및 3개의 process

두번째 예제 - 불안전한 할당(Unsafe Allocation)

• 12개의 magnetic tape 및 3개의 process

운영체제는 자원을 할당할 때 불안전 할당이 되지 않도록 해야한다. (불안전할당 -> 교착상태, 대출전문 은행과 유사:Banker’s algorithm)
자원을 할당할때 위험한 불안전할당을 하지 않도록 하는 방법

교착상태 검출 및 복수(Deadlock Detection & Recovery)

위의 두가지 방법은 애초에 교착상태가 일어나지 않게 하는 방법이었다면 이는 교착상태는 일어나도록 허용은 하되, 발생하면 복구하도록 하는 방법이다.

• 교착상태가 일어나는 것을 허용
• 주기적 검사: 검사에 따른 추가 부담(overhead)
• 교착상태 발생 시 복수: 프로세스 일부 강제 종료, 자원 선정하여 일부 프로세스에게 할당

이 방법은 os로 하여금 교착상태가 일어나지 않도록 유의하세요. 라고 알려주는게 아니라 프로세스가 필요한대로 자원을 일단 다 나눠주는데, 나눠주다보면 잘 일어나지 않지만 어쩌다가 교착상태가 발생할 수 있다. 이렇게 교착상태가 나타나면 시스템은 동작을 멈추게 되고 이때 이를 해결해줘야 한다.

os의 프로세스 관리부서에서 프로그램이 돌면서 계속적으로 컴퓨터 내부를 교착상태가 일어났는지를 주기적으로 확인한다. 그런데 주기적 검사에서 주기적이라는 단어가 상당히 모호한데, 자주하면 할수록 교착상태를 빨리 알아챌 수 있기 때문에 좋지만 우리가 사용할 수 있는 자원은 한정적이기 때문에 오버헤드의 문제점이 존재한다. 그리고 더 나아가 이렇게 검사를 통해 교착상태를 발견하게 되면 이를 복구해줘야 하는데, 이를 복구해주기 위해서는 주기적으로 현재 상태를 기억을 해야한다. (그러면 또 메모리가 들게 된다) -> 이렇듯 비용이 많이 발생하게 된다.

교착상태가 발생하면 한 프로세스를 강제로 종료를 시키던가, 그게 불가능하다면 자원을 강제로 뺏어서 다른 프로세스에게 할당을 해주면 된다.

이 방법은 말그대로 교착상태 자체가 잘 일어나는 것이 아니기 때문에 자원을 그때그때 그냥 할당을 해주는것을 허용해주는 것인데, 사실 현실적으로 이 방법을 사용하기에는 추가적으로 드는 비용적인 부분들이 많이 들게된다.

교착상태 무시 (Don’t Care)

방법이라고 하기도 그렇지만 이런 교착상태 자체를 무시하는 것이다. 실제로 교착상태가 자주 일어나기도 힘들고(4가지의 필수조건을 충족시키기가 힘들다) pc는 일반적으로 우리가 혼자 쓰고 있기때문에 아예 무시하는 방법을 적용하기도 한다.