Posted Updated OS

Deadlock

출처 : 이화여자대학교 반효경 (http://www.kocw.net/home/search/kemView.do?kemId=1046323)

Deadlock

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

  • 자원
    • 하드웨어, 소프트웨어 등을 포함하느 개념
    • ex) I/O device, CPU cycle, memory space, semaphore 등
  • 예시
    • 시스템 2개의 tape drive가 있다
    • 프로세스 P1과 P2 각각이 하나의 tape drive 를 보유한 채 다른 하나를 기다리고 있음

Deadlock 발생의 4가지 조건

  • Mutual Exlusioin
    • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  • No Preemption
    • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 뺏기지 않음
  • Hold and wiat
    • 자원을 가진 프로세스가 다른 자원을 기달리때 보유 자원을 놓지 않고 계속 가지고 있음
  • Circular wait
    • 자워을 기다리는 프로세스 간에 사이클이 형성되어야 함
    • P0은 P1이 가진 자원을 기다림
    • P1은 P2가 가진 자원을 기다림 ..

자원 할당 그래프

  • 자원에서 프로세스쪽으로 나가는 화살표

  • 이 프로세스가 이 자원을 가지고 있다.

  • 프로세스에서 자원쪽으로 나가는 화살표

    • 이 프로세스가 이 자원을 요청

  • 자원 안에 동그라미

    • 자원 개수

  • 그래프 안에 cycle이 없으면 deadlock이 아니다

  • cycle이 있으면

    • 자원당 인스턴스가 하나밖에 없으면, 데드락
    • 자원의 인스턴스가 여러개면, 데드락수도 있고 아닐수도 있고

  • 왼쪽은 데드락, 오른쪽은 데드락이 아님

Deadlock Prevention

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

  • Mutual Exclusion
    • 공유해서는 안되는 자원의 경우 반드시 성립해야함
  • Hold and wait
    • 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
    • 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
  • No preemption
    • 빼앗아 올수 있게 하면 됨
    • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
  • Circular Wait
    • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로 자원 할당

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원 할당.

데드락으로부터 항상 safe한 상태를 유지.

자원 요청에 대한 부가정보를 이용해서 자원 할당이 데드락으로부터 safe한지를 동적으로 조사해서 안전한 경우에만 할당.

프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언

  • Single instance per resouce types
    • Resource Allocation Graph algorithm
  • Multiple instance per resouce types
    • Banker’s Algorithm

Resource Allocation Graph algorithm

자원 당 인스턴스 하나

데드락의 위험성이 있으면 애초부터 자원을 내주지 않음.

점선 화살표 : 이 프로세스가 평생 적어도 한번 이 자원을 사용할 것이다.

Banker’s Algorithm

자원 당 인스턴스 여러개

5개의 프로세스 : P0 P1 P2 P3 P4

A자원 인스턴스 10개

B자원 인스턴스 5개

C자원 인스턴스 7개

  • Allocation

    • 0번 프로세스는 현재 A 0개 / B 1개 / C 0개 할당되어 있음

  • Available

    • 현재 가용 자원
    • 아무도 사용하지 않고 남아 있는 자원

  • Max

    • 이 프로세스가 시작될 때, 이 프로세스가 평생 최대로 사용할 자원 개수를 선언했음

  • Need

    • 추가로 요청 할 수 있는 양

이 알고리즘은 프로세스가 자원을 요청했을 때, 이 요청을 받아들일것인지 결정하는 것임

프로세스가 최대(Need)로 요청할 것을 가정한다. 그리고 이게 가용 자원으로 가능한지 체크. 가용자원으로 가능하지 않으면 요청을 거절.

P0는 7 4 3 으로 요청할것이다. 이게 3 3 2 로 커버 가능? NO. 요청 거절.

Deadlock Detection and recovery

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

  • Single instance per resouce types

    • Resource Allocation Graph algorithm
    • cycle이 곧 데드락

  • Multiple instance per resouce types

    • Banker’s Algorithm과 유사한 방법 활용

  • Recovery

    • Process Termination

      • abort all deadlocked processes(한꺼번에)
      • 데드락에 연루된 프로세스드을 하나씩 죽여봄. 여전히 데드락이면 또 하나의 다른 프로세스 죽여봄.

    • Resource Preemption

      • 데드락에 연루된 프로세스로부터 자원을 뺏음
      • safe state로 roolback하여 prcess를 restart

Deadlock Ignorance

Deadlock을 시스템이 책임지지 않음

UNIX를 포함한 대부분의 OS가 채택

데드락이 일어나지 않는다고 생각하고 아무런 조치 취하지 않음

Comments

Follow

Recents

Categories

×