교착상태(Deadlock)
교착상태(Deadlock)은 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태를 말한다. 여기서 자원은 하드웨어(cpu, memory..)가 될 수도 있고, 소프트웨어가 될 수도 있다.
교착상태 발생에는 4가지 조건이 존재한다. 이것들이 전부 동시 만족해야 교착상태가 발생한다.
Mutual exclusin(상호배제)
매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
No preemption(비선점)
프로세스는 자원을 스스로 내려놓을 수 있지만 강제로 빼앗기지 않는다.
Hold and wait(점유 대기)
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있는다.
Circular wait(순환 대기)
자원을 기다리는 프로세스간에 사이클이 형성되어야 한다.
교착상태 처리방법
Prevention(예방)
자원 할당 시에 교착상태의 4가지 필요 조건중 어느 하나가 만족되지 않도록 하는 기법이다.
- 상호배제
동시에 여러 프로세스가 자원을 접근할 수 있게 한다. 다만 공유해서는 안되는 자원의 경우에는 불가능하다.
- 비선점
다른 프로세스가 자원을 선점할 수 있게 허용한다. 따라서 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점당한다. 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다. 다만 선점당할 때 모든 작업이 날아가므로 상태를 저장하고 다시 복구할 수 있는 cpu나 memory같은 자원에서 주로 사용한다.
- 점유 대기
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않게 한다. 이를 구현하기 위한 방법으론 두 가지가 존재한다.
- 프로세스 시작시 모든 필요한 자원을 할당 받게 한다. 그러나 매 시점마다 모든 필요한 자원을 보유하게 되면 자원에 대한 비효율성이 생길 수 있다.
- 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다.
- 순환 대기
자원마다 할당 순서를 정해서 정해진 순서대로만 자원을 할당받을 수 있게 한다.
Avoidance(회피)
자원 요청에 대한 부가적인 정보를 이용해서 교착상태의 가능성이 없는 경우에만 자원을 할당한다. 프로세스가 시작될 때 필요로 하는 각 자원별 최대 사용량을 미리 선언해서, 현재의 가용자원만 가지고 최대 자원 요청을 처리할 수 있는 프로세스의 요청만 받아들인다. 이렇게 해서 unsafe 상태에 가지 않게 하는 것이 회피의 목표이다.(unsafe 상태라고 교착상태인것은 아니다.)
자원을 할당받는 프로세스가 한개라면 자원 할당 그래프를 이용하여 회피하고, 자원을 할당받는 프로세스가 여러 개라면 banker's 알고리즘을 사용하여 회피한다.
Detection and Recovery(발견과 회복)
교착상태를 발생하도록 내버려두다가, 만약 교착상태를 발견하면 그것을 회복시키는 방법이다.
자원을 할당받는 프로세스가 한개라면 자원 할당 그래프의 변형인 wait-for 그래프를 이용해서 교착상태 사이클이 존재하는지 주기적으로 조사한다. 자원을 할당받는 프로세스가 여러 개라면 banker's 알고리즘과 유사한 방법을 사용하여 사이클을 발견한다.
회복하는 방법은 2가지가 있다.
- 프로세스 종료
교착상태에 걸린 모든 프로세스를 종료시킨다. 또는 교착상태에 걸린 프로세스를 하나씩 죽이면서 교착상태가 해결되는지 확인한다.
- 자원 선점
종료시켰을 때 비용이 최소화되는 프로세스를 선정한다. 그리고 그 프로세스를 safe한 상태로 롤백하여 restart시킨다. 이 때 계속 동일한 프로세스가 선정되는 경우 기아 상태에 빠질 수 있으므로 롤백 횟수도 같이 고려해서 선정해야 한다.
Ignorance(무시)
교착상태가 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다. 교착상태는 매우 드물게 발생하므로 교착상태에 대한 조치가 교착상태에 걸린 것보다 훨씬 큰 오버헤드일 수 있다. 따라서 만약 시스템에 교착상태가 발생한 경우, 시스템이 비정상적으로 동작하는 것을 사람이 느낀 후 직접 프로세스를 종료하는 방법 등으로 대처한다. 현대의 대부분의 범용 OS가 채택하는 방식이다.
반효경 교수님의 운영체제 강의를 바탕으로 작성했습니다
