Deadlock(교착 상태)

이연중·2021년 11월 11일

OS

목록 보기

7/9

위 그림대로 차들이 무조건 진행방향으로만 나아가려고 한다면 진전이 없이 계속 막히게 될 것이다 이러한 상황을 Deadlock이라 한다.

Deadlock

일련의 프로세스들이 서로가 가진 자원(하드웨어, 소프트웨어 등을 포함하는 개념)을 기다리면 block된 상태

ex)

시스템에 2개의 tape drive가 있고, 프로세스1,2가 각각 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있음(하드웨어 자원)
프로세스 1이 세마포어 A를 획득하고, 프로세스 2가 세마포어 B를 획득한 상태에서 서로의 세마포어를 요구하는 상태(소프트웨어 자원)

Mutual Exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
No Preemption(비선점): 프로세스는 자원을 스스로 내어놓긴 해도 강제로 뺏기지는 않음
Hold And Wait(보유대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
Circular Wait(순환대기): 자원을 기다리는 프로세스간에 사이클이 형성
- 프로세스 1이 프로세스 2가 가진 자원을 기다림
- 프로세스 2가 프로세스 3이 가진 자원을 기다림
- 프로세스 3이 프로세스 1이 가진 자원을 기다림

=> 위 4가지 조건을 모두 만족해야 Deadlock이 발생

Deadlock이 발생했는지를 자원할당그래프를 통해서 알 수 있음

동그라미: 프로세스
사각형: 자원
동그라미로 들어오는 화살표: 프로세스가 해당 자원을 소유하고 있음
사각형으로 들어오는 화살표: 프로세스가 해당 자원을 요청(기다림)
사각형 안에 점들: 자원의 개수
위 그림을 Deadlock일까?
- 그래프에 cycle이 없으면 Deadlock이 아님
- cycle이 있으면
  - 자원당 점이 하나씩밖에 없으면 Deadlock
  - 자원당 점이 여러개 있으면 Deadlock일수도 아닐수도 있음(여러개 점을 모든 프로세스가 소유하고 있고, 그 프로세스들끼리 cycle이 형성되어 있으면 Deadlock)

Deadlock Prevention(예방)
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는것
Deadlock Avoidance(예방)
- 자원 요청에 대한 부가적인 정보를 이용해 deadlock의 가능성이 없는 경우에만 자원 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and recovery(데드락 발생하게 하고, 탐지 후 회복)
- Deadlock 발생은 허용, 그에 대한 탐지 루틴을 두고 발견 시 회복
Deadlock Ignorance(데드락 발생하게 하고, 무시)
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
- 사용자가 프로세스를 kill(만약 Deadlock이 발생하게 되면)

Mutual Exclusion: 사실상 배제할 수 있는 조건이 아님
Hold and Wait
- 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법(wait 할 일이 없음. 자원의 비효율성 초래)
- 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청(hold를 못하게)
No Preemption
- 자원을 선점할 수 있게함
- state를 쉽게 save하고 restore 할 수 있는 CPU나 Memory 자원에서 주로 사용
Circular Wait
- 모든 자원 유형에 할당 순서를 정해 정해진 순서대로만 자원 할당

=> 자원에 대한 이용율이 낮아지고, 시스템 성능 저하, starvation 문제 발생

=> 잘 생기지도 않을 데드락을 고려해 제약조건을 많이 달아놓기에 굉장히 비효율적인 방법

프로세스의 시작 단계에서 프로세스가 쓸 자원의 최대량을 알고 있다고 가정하고, 프로세스에게 자원을 할당할 때 Deadlock이 발생할거 같으면 할당 안함
자원의 인스턴스가 하나밖에 없는 상황

점선: 프로세스가 적어도 한번 해당 자원을 요청할 수 있는 가능성

프로세스 2가 자원을 실제로 요청(점선 -> 실선)

점선을 포함하면, 사이클이 형성됨(이런 경우에는 프로세스 2에게 자원을 할당하지 않음)

만약 1번 프로세스가 자원을 요청해서 얻었다면, 사이클은 형성되지 않음(이런 경우에는 할당)
자원의 인스턴스가 여러개 있는 경우(Banker's Algorithm을 이용)
- Allocation: 각 프로세스가 가지고 있는 자원 및 개수
- Max: 각 프로세스마다 각 자원을 평생의 생명주기동안 사용할 수 있는 최대 수
- Available: 가용자원
- Need: Max-Allocation
- Available로 충족할 수 있는 Need들만 받아들임(나머지는 자원을 할당해주지 않음)

=> 비효율적임(자원이 남아돌게 됨). unsafe로 판단됐다고 해서 무조건 Deadlock은 아님

Deadlock 탐지
- 자원당 인스턴스가 1개인 경우
  - 자원할당 그래프에서의 cycle이 deadlock
- 자원당 인스턴스가 여러개인 경우
  - Banker's algorithm과 유사한 방법
  Allocation: 프로세스 당 소유한 자원들
  
  Request: 프로세스가 각 자원들 요청 한 수(요청한 자원이 없으면, 반납한다고 가정)
  
  Available: 가용자원
  
  위 그림은 Deadlock이 없음
Dealock Recovery
- Deadlock에 연루된 프로세스들 Kill
  - 모든 프로세스들 한꺼번에 kill
  - Deadlock에 연루된 프로세스를 하나씩 kill(Deadlock이 없어질때까지)
- Deadlock에 연루된 프로세스들의 자원을 뺏는 것(자원을 뺏을 victim 프로세스 선정하고, 자원을 뺏어 Deadlock을 없앰 -> safe state로 rollback 후 프로세스 restart)
  
  => victime 프로세스 선정 방법을 매번 달리해야 하고, rollback 횟수도 고려