[OS] 데드락

RepDay1·2023년 3월 6일
CSOS
0

운영체제

목록 보기
8/8

Deadlock ?

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

  • Resource(=자원) : 하드웨어,소프트웨어 등을 포함하는 개념(ex: IO 디바이스, CPU, 메모리 공간, 세마포 등)

  • 프로세스가 자원을 사용하는 절차

    • Request(자원 요청)
    • Allocate(자원 할당)
    • Use
    • Release(자원 반납)

  • 데드락 예시

    • 시스템 2개에 tape drive가 있음
    • P1과 P2 각각이 하나의 tape drice를 보유한 채 다른 하나를 기다리고 있을 경우(서로가 자원을 쥔채 다른 하나를 기다림)
    • Binary 세마포의 경우
      image

  • 데드락이 생기는 조건

    • Mutual exclusion : 매순간 하나의 프로세스만 공유 자원에 접근 가능
    • No Preemption : 프로세스는 자원을 스스로 내놓을 뿐이고 다른 프로세스가 자원을 강제로 선점할 수 없음
    • Hold and Wait : 이미 가진 자원을 내놓지않고 다른 자원을 계속 기다림
    • Circular wait : 자원을 기다리는 프로세스간에 사이클이 형성되어야함 ( Pn-1은 Pn의 자원을 기다리고 Pn은 P0의 자원을 기다림)

  • 데드락을 해결하는 방법

    • Deadlock Prevention : 자원 할당 시 데드락의 4가지 필요 조건중 어느 하나가 만족되지 않도록 하는것
    • Deadlock Avoidance : 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원 할당
    • Deadlock Detection and recovery : 데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발견시 recover
    • Deadlock Ignorance : 데드락을 시스템이 책임지지 않음 (UNIX를 포함한 대부분의 OS가 채택하는 방식)

Deadlock Prevention

다음 4가지중 하나를 만족하지 않게하는 방법

  • Mutual exclusion을 만족하지 않게 한다면?
    공유해서는 안되는 자원의 경우 반드시 성립해야됨(Race condition) 고로 상호배제를 만족되지 않게 하긴 힘듦
  • No Preemption 을 만족하지 않게 한다면?
    • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
    • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨
    • state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU,메모리)
  • Hold and Wait 을 만족하지 않게 한다면?
    • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야됨
    • 방법 1: 프로세스 시작 시 모든 필요한 자원을 할당받게함
    • 방법 2: 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청함
  • Circural wait 을 만족하지 않게 한다면?
    • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
    • Utilization(이용률)이 저하되고, throughput(성능)이 감소, starvation(기아) 문제가 야기될 가능성이 있음

Deadlock Avoidance

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

  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록함

  • Safe state : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

  • safe sequence

    • 프로세스의 순서<P1,P2,...Pn>이 safe하려면 자원 요청이 가용 자원 + 모든 Pj(j<i)의 보유 자원에 의해 충족 되어야함
    • 조건을 만족하면 아래 방법으로 모든 프로세스의 수행을 보장
    1. Pi 의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<n)가 종료 될때 까지 기다림
    2. Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행함

    image

  • 시스템이 safe state에 있으면(=> 데드락이 발생x)

  • 시스템이 unsafe staet에 있으면 (=>데드락 가능성이 있음)

  • Deadlock Avoidance은 시스템이 unsafe에 들어가지 않도록 하는 걸 보장

  • 2가지의 경우의 Deadlock Avoidance알고리즘

    • Single instance per resource types : Resource Allocation Graph 알고리즘 사용
    • Multiple instance per resource types : Banker's 알고리즘 사용

    Resource Allocation Graph 알고리즘

  • 자원 당 인스턴스가 한 개인 자원에 대한 Deadlock Avoidance 알고리즘

    image

  • Claim edge

    • 점선으로 표시된 간선, P가 자원 R을 미래에 요청할 수 있음을 뜻함(현재 요청하는게아님)
    • 프로세스가 해당 자원을 요청시 request edge(실선)으로 바뀜
    • 자원이 릴리즈되면 assignment edge는 다시 claim edge로 바뀜

  • request edge의 assignment edge 변경 시 점선을 포함하여 cycle이 생기지 않는 경우에만 요청 자원을 할당함

  • cycle 생성 요부 조사시에는 프로세스의 수가 n일때 O(n2)의 시간복잡도를 가짐

    Banker's 알고리즘

  • 자원 당 인스턴스가 여러 개인 자원에 대한 Deadlock Avoidance 알고리즘

  • Ex

    image

    Allocation은 현재 할당받은 자원의 수, Max는 프로세스가 실행 중에 사용할 자원의 최댓값,
    Available은 현재 사용 가능한 자원의 인스턴스 갯수 (A자원은 5개의 프로세스가 총 7개의 인스턴스를 할당받아 사용중이므로, 10-7로 3임)
    Need는 추가로 요청할 수 있는 인스턴스의 갯수를 의미함

  • P1이 (1,0,2)를 요청 할 경우
    가용 자원 테이블을 보면 A가 3개 C가 2개있으므로, 할당할 자원은 있음,
    또 필요 자원이 1 2 2인데 할당 후 0 2 0에서도 가용 자원 B는 3개가 있으므로 요청을 수용해도 추후 어떤 요청이 와도 데드락이 생기지 않으므로 할당을 해줌

  • P0이 (0,2,0)을 요청 할 경우
    가용 자원 테이블을 보면 요청만큼의 자원은 B가 3이므로 있지만, Need테이블을 보면 할당 후에도 필요 자원을 가용 자원이 모두 충족 시켜줄 수 없으므로
    할당하지 않음(=요청 수용 후에 또 P0이 남은 Need자원만큼을 더 추가로 요청할 경우 현재 남은 가용 자원으로는 충족시켜줄수 없기 때문에 데드락이 발생함)

    ==> 이렇게 뱅커스 알고리즘은 요청이 올때, 항상 최악의 경우(요청을 수용 후 다음 요청이 필요자원 전체를 요청함)을 가정하여 요청을 수용할지 안할지를 결정함
    즉 위 T0에 상황에서 P1은 어떤 요청을 해도 모두 받아들여짐
    장점으로는 확실하게 데드락이 회피할 수 있지만,
    당장 수용가능한 요청도 추후 요청에따라 데드락이 발생할 수 있는 가능성이있으면 수용안하므로, 가용자원의 이용률이 떨어진다는 단점이 있음

    Deadlock Detection and recovery

  • Deadlock Detection : 데드락이 발생 여부를 신경쓰지않고 요청대로 자원을 할당해줌

  • Resource type 당 하나의 인스턴스인 경우 : 자원할당 그래프에서의 cycle이 곧 데드락을 의미
  • Resource type 당 여러개의 인스턴스인 경우 : 뱅커스 알고리즘과 유사한 방식 활용
  • Wait-for graph 알고리즘(=자원 할당 그래프에서 자원 노드를 제거해서 간략화한 그래프)

  • Resource type 당 하나의 인스턴스인 경우

    image

    => 자원의 최대 사용량을 미리 알 필요가 없음 즉, 그래프에 점선(=Claim edge)이 없음

  • Resource type 당 여러개의 인스턴스인 경우
    => Request는 추가요청가능량이아니라 현재 실제로 요청한 자원량을 의미함

  1. 현재 요청하는 자원이 없는 프로세스부터 처리하면 데드락이 발생안함

    image

  2. 현재 요청하는 자원이 없는 P0을 수행해도 B자원 1개로는 다른 프로세스의 요청을 수행할 수 없으므로 데드락이 발생함

    image

  • Recovery : 데드락 발생 시 데드락을 해결하는것
    • Process termination : 데드락에 연루된 프로세스를 kill하는것(전부 kill하거나, 데드락이 풀릴떄 까지 하나씩 kill하거나)
    • Resource Preemption : 자원을 뺏는 방법
      1. 비용을 최소화할 victim의 선정
      2. safe state로 롤백하여 프로세스를 재시작
      3. 동일한 프로세스가 계속 victim(희생)으로 선정되는 경우 starvation이 발생할 수 있음

Deadlock Ignorance

  • 데드락이 생기지 않는다고 낙관적으로 생각하고 아무 조치를 안하는것

  • 데드락은 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있음(가용 자원이있지만 할당을 안하는 등)

  • 만약 시스템에 데드락이 생기면 시스템이 비정상적으로 작동하는 걸 사람이 느낀 후 직접 프로세스를 죽이는 방법으로 대처

  • 대부분의 현재 OS가 채택하는 방식

    Reference
    반효경 교수님 KOCW 운영체제

profile
RepDay1
.
이전 포스트

[OS] 동기화 문제의 예시와 모니터

0개의 댓글