Deadlock
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더이상 진행하지 못하는 상태를 말한다.
starvation과 비슷하지만 starvation은 운영체제가 잘못된 정책을 사용해 특정 프로세스의 작업이 지연되는 문제이고, deadlock은 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제이다.
교착상태의 발생
시스템 자원, 공유 변수/파일(무한대기), 데이터베이스(일관성 유지로 인한 잠금)등 사용할 때 발생할 수 있는 문제이다.
식사하는 철학자 문제
- 일정 시간 생각을 한다.
- 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
- 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
- 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
- 오른쪽 포크를 내려놓는다.
- 왼쪽 포크를 내려놓는다.
- 다시 1번으로 돌아간다.
- 서로 포크를 공유할 수 없고, 다른 철학자의 포크를 빼앗을 수 없으며 왼쪽 포크를 잡은 채 오른쪽 포크를 기다릴 경우 교착상태가 발생하게 된다.
- 해결책 : 타임아웃, 인터럽트 무시, 하드웨어적으로 양쪽 포크를 동시에 잡게하는 명령어 사용(쪼갤 수 없는 명령어, Atomic instruction)
교착상태 필요 조건
아래 4개의 조건은 모두 만족해야 교착상태가 발생한다.
1. 상호배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적 자원이어야 한다.
2. 비선점 : 한 프로세스가 사용중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
3. 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다. 다른 프로세스가 필요로 하는 자원을 점유하면서 또 다른 자원을 기다리는 상태가 되어야 한다.
4. 원형 대기 : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 서로 양보를 할 수 없기 때문에 교착 상태에 빠지게 된다.
교착상태 해결 방법
예방 : 교착 상태를 유발하는 네가지 조건을 무력화, 자원 낭비가 심함
회피 : 교착 상태를 발생하지 않는 수준으로 자원 할당, 은행원 알고리즘
탐지 : 자원 할당 그래프를 사용해 교착상태 발견,
회복 : 교착상태를 탐지 후 해결
Banker's algorithm
은행이 대출 해주는 방식, 대출 금액이 대출 가능한 범위 내이면 허용되나 그렇지 않으면 거부되는 것과 유사하여 은행원 알고리즘이라고 한다.
교착 상태 회피를 구현하는 방법으로, 자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
- 안정상태 : 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.
사용하는 변수
- 전체 자원(Total)
- 가용 자원(Available) : 현재 사용할 수 있는 자원의 수
- 최대 자원(Max)
- 할당 자원(Allocation) : 현재 할당된 자원의 수
- 기대 자원(Expect) : 앞으로 사용할 자원의 수, (최대자원 - 할당자원)
