OS를 공부하면서 정리를 한 내용들 입니다.

데드락의 문제, 발생 조건, 처리방법 네 가지중 하나인 프리벤션에 대해 알아봅니다.

Deadlock Problem

Deadlock

• 일련의 프로세스들이 서로가 가진 자원을 기다리면 block된 상태

Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• ex) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차 (request, allocation, use, release)

Deadlock Example1

• 시스템에 2개의 tape drive가 있다.
• 프로세스 p1과 p2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.

Deadlock Example2

• Binary semaphores A and B

P0      P1
P(A);   P(B);
P(B);   P(A);

Deadlock 발생의 4가지 조건

Mutual exclusion

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있음.

  No preemption

• 프로세스는 자원을 스스로 내놓을 뿐 강제로 빼앗기지 않음.

  Hold and wait

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음.

  Circular wait

• 자원을 기다리는 프로세스 간에 사이클이 형성 되어야 함.

• 프로세스 P0,P1…Pn이 있을 때

  P0은 P1이 가진 자원을 기다림.
  P1은 P2가 가진 자원을 기다림.
  ...
  Pn-1은 Pn이 가진 자원을 기다림.
  Pn은 P0가 가진 자원을 기다림.
  

자원 할당 그래프

데드록의 개념을 알기 위해서 자원 할당의 과정이 어떤식인지 그림으로 간략히 표현한 그림 입니다.

출처 : basic it topic

프로세스(P)와 자원(R)이 각각 n, m개가 있고

간선 프로세스에서 자원으로 가는 선은 request, 자원에서 프로세스로 가는 선은 assignment입니다.

점은 자원에 있는 instance의 갯수입니다.

Deadlock의 처리 방법

Deadlock Prevention

• 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당

Deadlock Detection and recovery

• Daedlock 발생은 허용하되 그에 대한 detection루틴을 두어 deadlock발견시 recover

Deadlock Ignorance

• Deadlock을 시스템이 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention

Mutual exclusion

• 공유해서는 안되는 자원의 경우 반드시 성립해야함.

  No preemption

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
• 방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
• 방법2. 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청

Hold and wait

• process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
• 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
• State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용(CPU, memory)

  Circular wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당.
• 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release 해야한다.

그러나 이것은 Deadlock이 일어나는 것은 원천 봉쇄하지만 비효율적인 방법입니다.

Utilization 저하 , throughput 감소, starvation 문제

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의