[운영체제] Deadlock이란?

위 그림의 상황은 다음과 같다.

프로세스 A는 프린터를 요청하여 점유하고 있고, 프로세스 B는 디스크를 요청하여 점유하고 있다.

다음 프로세스 A는 디스크를 요청하여 대기하고 있고, 프로세스 B는 프린트를 요청하여 대기하고 있다.

프로세스 A, B는 서로 점유하고 있는 자원이 종료되는 signal를 보내지 않아 아직 점유하고 있는 것으로 보이며 서로의 자원을 점유한 채로 서로의 자원을 요청하고 있어 끝나지 않는 상황인 "Deadlock"이 발생한다.

 

• 두 개 이상의 프로세스가 각각이 다른 프로세스가 생성해야만 하는 이벤트를 기다리는 상황에서 발생함
• 데드락 상태는 시스템이 제대로 작동하지 않고, 리소스가 효율적으로 사용되지 않을 뿐만 아니라, 중대한 문제로 이어짐.
• 운영체제는 시스템 리소스를 경쟁하는 프로세스들 사이에서 분배해야 함
  • CPU 사이클(preemptable)
    • CPU사이클은 선점 가능한 자원으로 간주됨. 다른 프로세스가 CPU를 요청할 경우 현재 실행 중인 프로세스가 중단될 수 있음
  • 메모리 공간(preemptable)
    • 메모리 공간은 선점 가능한 자원으로 간주됨
    • 다른 프로세스가 메모리를 요청할 경우 운영체제는 메모리를 할당하고 현재 사용 중인 프로세스의 메모리 접근을 중단시킬 수 있음.
  • 파일(non-preemptable)
    • 파일은 선점할 수 없는 자원으로 간주됨. 한 번에 하나의 프로세스만 파일을 사용할 수 있으며, 선점되지 않음.
  • I/O장치(non-preemtable)
    • 한 번에 하나의 프로세스만 장치를 사용할 수 있으며, 다른 프로세스가 요청을 기다려야 함.

⇒ 프로세스는 리소스를 요청하고 사용한 후에는 해당 리소스를 반환한다. 여기서 포인트는 리소스가 재사용 가능하다는 것으로 리소스가 소모되지 않음. 만약 요청한 리소스가 현재 사용 중이라면, 대기 상태로 전환된다!!

 

 

Deadlock Conditional : 데드락 필요충분 조건

1. 상호 배제(Mutual Exclusion)
   • 만약 한 프로세스가 어떤 리소스를 보유하고 있다면, 다른 프로세스들은 해당 리소스를 사용하기 위해 그 프로세스가 해당 리소스를 반납할 때까지 기다려야 함.
2. 보유 및 대기(Hold and Wait)
   • 프로세스는 최소한 하나의 리소스를 보유한 상태로 추가적인 리소스를 얻기 위해 대기할 수 있음.
3. 선점 불가능(No Preemption)
   • 리소스는 프로세스나 운영체제가 강제로 반납할 수 없으며 해당 리소스를 가진 프로세스가 스스로 반납해야 함
4. 순환 대기(Circular Wait)
   • 대기 중인 프로세스들의 집합이 존재해야 하며, 이 집합에서 P0이 P1이 가진 리소스를 대기하고, P1이 P2가 가진 리소스를 대기하는 식으로 순환적으로 대기하는 상황이어야 함. 즉 사이클을 가지고 있어야 함

 

Interpreting a RAG With Single Resource Instances

• 만약 그래프가 사이클을 포함하지 않으면, 데드락이 존재하지 않음

위 RAG그래프는 "p1(프로세스1)이 r3(자원3)을 소유하고 있고, r1을 요청하고 있다" 라고 해석해야 함.

 

 

• 만약 그래프가 사이클을 포함하면, 데드락이 존재함.