[운영체제] 교착상태(Deadlock)

 

1. 교착상태의 필요 조건

   아래 네가지 조건이 모두 충족 된다면 교착상태가 일어날 수 있다.

 

 

 1) Mutual exclusion(상호배타)
    어떤 자원을 한 프로세스가 사용하고 있다면 다른 프로세스가 사용할 수 없는 상태

   (한 철학자가 젓가락을 들었다면 그 젓가락은 다른 철학자가 사용할 수 없음)

 

 2) Hold and wait(보유 및 대기)

    한 자원을 보유하고 있는 상태로 나머지 자원이 충족되기를 기다리고 있는 상태

    (각 철학자가 모두 왼쪽 젓가락을 든 채로 오른쪽 젓가락을 기다리고 있음)

 

 3) No Preemption(비선점)

   다른 프로세스가 사용 중인 자원을 강제로 뺏을 수 없는 상태

   (다른 철학자가 들고 있는 젓가락을 강제로 가져올 수 없음)

 

 4) Circular wait(환형대기)

    자원과 자원을 사용하려는 프로세스들이 원형으로 물려있는 상태

    (각 철학자의 오른쪽 젓가락이 왼쪽 철학자의 왼쪽 젓가락임)

 

 

 

2. 교착상태 방지(Deadlock Prevention)

 

 

 교착상태는 위의 네가지 조건을 모두 만족해야 일어날 수 있으므로 한가지 이상의 조건을

 불만족 시킴으로써 교착상태를 방지할 수 있다.

 

 1) 상호배타

   자원을 공유 가능하게 만들면 해결할 수 있지만, 원천적으로 자원 공유가 불가능한 경우가 많음

   (cpu를 스위칭하면서 쓸수는 있어도 동시에는 사용불가)

 

 

 2) 보유 및 대기

   한 쪽을 보유 한 뒤 나머지를 대기하는 방식의 알고리즘 대신, 두 자원을 동시에 보유할 수 있는 상태에서만

   자원을 가져갈 수 있게 변경, 또는 나머지 자원을 즉시 가져갈 수 없다면 보유하고 있는 자원도 놓게 변경해서 해결 가능.

 

   

  3) 비선점

    다른 프로세스가 사용하고 있는 자원을 강제로 뺏어올 수 있게 변경한다면 발생할 수 있는 문제가 많아 불가능

   (다른 프로세스가 사용중인 프린터를 강제로 뺏어온다면 인쇄에 제대로 되지 않음)

 

 

  4) 환형대기

    자원에 번호를 부여하고, 자원을 요청할 때 오름차순으로 자원을 요청하는 알고리즘을 적용해서 해결 가능

    (마지막을 제외한 철학자들이 모두 왼쪽, 오른쪽의 순서로 젓가락을 요청하게 되고 마지막 철학자는 오른쪽, 왼쪽의 순서로

     젓가락을 요청하게 되서 원이 만들어지지 않음)

 

 

3. 교착상태 회피(Deadlock Avoidance)

 

 

  교착상태를 자원 요청에 대한 잘못된 승인이라고 해석

  운영체제는 자원을 할당할 때, 선 할당 후 남은 자원으로 프로세스의 작업을 끝내지 못하는 상태(불완전 할당)를

  만들지 않도록 해야한다.(Banker's algorithm)

 

 

 

4. 교착상태 검출 및 복구(Deadlock Detection & Recovery)

 

 

 프로세스가 요청하는대로 자원을 모두 나누어 주고 일정시간 마다  O/S가 교착상태를 검사하여 교착상태가 발견됐다면

 프로세스를 일부 강제종료 시키거나, 자원을 빼앗아 다른 프로세스에게 할당하여 해결하는 방식.

 

 복구를 위한 이전 상태 기억과, 교착상태 검사로 인한 오버헤드가 발생하는 문제점이 있음.

 

 

 

 

5. 교착상태 무시

 

 

 개인 pc에서는 교착상태가 잘 일어나지 않으므로 무시하는 방식.