[교착 상태] 1. 교착 상태의 정의와 필요조건
1. 교착상태의 개요
교착 상태(데드 락)의 정의
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리며 작업을 더 이상 진행하지 못하는 상태
프로세스 내에 임계 구역이 존재하면 프로세스 간 상호 배제를 보장해야하는데, 운영체제가 상호 배제를 보장하기 위해 잠금을 사용하다 보면 교착상태에 빠지는 경우가 있다.
교착 상태의 발생
교착 상태는 시스템 자원, 공유 변수, 응용 프로그램 등을 사용 할 때 발생할 수 있다.
자원 할당 그래프
자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 자원 할당 그래프를 사용하면 어떤 프로세스에 자원이 할당되어 있는지, 어떤 프로세스가 자원을 기다리고 있는지 한눈에 파악할 수 있다.
프로세스는 원으로, 자원은 사각형으로 표현
자원을 사용하고 있는 경우는 자원으로 프로세스로 향하는 화살표로 표시
자원을 기다리고 있는 경우는 프로세스로부터 자원으로 향하는 화살표로 표시
여러 프로세스가 하나의 자원을 동시에 사용하는 다중 자원의 경우, 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표시
2. 교착 상태 필요조건
교착 상태 필요조건
교착 상태는 아래 4가지 조건들을 모두 충족해야 발생하기 때문에 필요조건이라고 한다.
- 상호 배제(mutual exclusion)
: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다.
- 비선점(non-preemption)
: 한 프로세스가 사용 중인 다른 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
- 점유와 대기(hold and wait)
: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
- 원형 대기(circular wait)
: 점유와 대기를 하는 프로세스 간의 관계가 원을 이뤄야한다.
식사하는 철학자 문제
철학자 4명이 둥근 식탁에 앉아 식사를 하고, 식탁에는 포크 4개가 놓여져 있다.
왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있다.
철학자들이 왼쪽 포크를 잡은 뒤, 오른쪽 포크를 잡으려고 하면 이미 옆자리의 철학자가 사용중이다.
따라서 철학자들은 오른쪽 포크를 잡지 못해서 모두 굶어 죽는다.
교착 상태가 발생하는 조건
- 철학자들은 서로 포크를 공유할 수 없다. > 상호 배제
- 각 철학자는 다른 철학자의 포크를 빼앗을 수 없다. > 비선점
- 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다려야 한다. > 점유와 대기
- 자원 할당 그래프가 원형이다. > 원형 대기
교착 상태와 기아 상태는 다르다.
기아 상태는 잘못된 정책이나 오류로 인해 특정 프로세스의 작업이 이뤄지지 않는것을 의미한다.
기아 상태의 경우 에이징(우선순위 조정) 방법 등으로 해결이 가능하다.
교착 상태의 경우 오류가 없어도 자연적으로 발생할 수 있고 기아 상태보다 처리가 복잡하다.
출처: 쉽게 배우는 운영체제