교착상태 (Deadlock)
정의
- 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하면 무한정 기다리는 현상
조건
- 상호배제
- 한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야함
- 점유대기
- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함
- 비선점
- 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야함
- 순환 대기
- 공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야합니다
해결방법
- 예방 기법
- 교착상태 발생 조건 네가지중 하나를 미리 무력화 하는 방법
- 자원낭비가 가장 심한 기법
- 회피 기법
- 교착 상태를 발생할 가능성을 배제하지 않고, 교착상태가 발생하면 적절히 피해나가는 방법
- 은행원 알고리즘
- 발견 기법
- 시스템에 교착상태가 발생했는지 점검하여 교착상태에 있는 프로세스와 자원을 발견하는 것을 의미
- 타임아웃 : 특정 프로세스가 일정시간동안 작업이 진행 되지 않으면 교착상태가 발생했다고 판단
- 자원할당 그래프 : 그래프를 보고 단일 자원일때 사이클이 생기면 교착상태로 판단
- 회복 기법
- 교착상태를 일으킨 프로세스를 종료하거나 교착상태의 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복하는 것을 의미
식사하는 철학자 문제
- 일정 시간 생각을 한다
- 왼쪽 포크가 사용 가능해질 때까지 대기. 만약 사용 가능하다면 집어든다
- 오른쪽 포크가 사용 가능해질 때까지 대기. 만약 사용 가능하다면 집어든다
- 양쪽의 포크를 잡으면 일정 시간동안 식사를 한다
- 오른쪽 포크를 내려 놓는다
- 왼쪽 포크를 내려 놓는다
- 다시 1번으로 돌아간다.
교착상태 조건
- 상호배제 : 철학자들은 서로 포크를 공유할 수 없다.
- 점유대기 : 철학자들은 왼쪽 포크를 집은 채 오른쪽 포크를 기다린다.
- 비선점 : 철학자들은 다른 철학자들의 포크를 강제로 빼앗을수 없다.
- 순환대기 : 철학자들은 원형 테이블에 앉아있다.
해결방법
- 교착상태 예방
- 상호배제 : 철학자들의 포크를 서로 공유할 수 있도록한다.
- 점유대기 : 두 포크를 모두 잡지 못한 철학자는 포크를 놓도록 한다
- 비선점 : 철학자들이 다른 철학자의 포크를 빼앗을 수 있도록한다
- 순환대기 : 한 철학자는 왼쪽이 아닌 오른쪽 포크를 먼저 잡도록 한다