[운영체제] Deadlock

Junseo Kim·2020년 10월 23일
0

운영체제 공부

목록 보기
10/10

Deadlock(교착 상태)

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태이다.
즉, 각 프로세스가 일부 자원을 가지고 있으면서 상대방이 가진 자원이 필요한 경우 영원히 행동을 할 수 없는 상태가 되는데 이걸 deadlock이라고 한다. 양보하는 프로세스가 없다면 진행할 수 없다.

자원은 하드웨어 자원일수도 있고, 소프트웨어 자원일수도 있다.

프로세스가 자원을 사용 할 때는 아래의 절차를 가진다.
Request(요청) - Allocate(할당) - Use(사용) - Release(반납)

Deadlock 발생조건

deadlock이 발생하려면 아래 4가지 조건이 모두 만족되어야한다.

  1. Mutual exclusion(상호 배제)
    자원을 일단 얻었으면 독점적으로 사용한다. 즉 다른 프로세스가 동일한 자원을 동시에 사용할 수 없다.

  2. No preemption(비선점)
    자원을 가지고 있으면 강제로 빼앗길 수 없다.

  3. Hold and wait(보유 대기)
    이미 어떤 자원을 가지고 있으면서 다른 추가적인 자원을 기다릴 때 발생할 수 있다. 이때 가지고 있는 자원은 반납하지 않는다.

  4. Circular wait(순환 대기)
    자원을 기다리는 프로세스 간에 사이클이 형성되는 경우
    ex) P0은 P1이 가진 자원을 기다림
    P1은 P2가 가진 자원을 기다림
    P2는 P3이 가진 자원을 기다림
    ...
    Pn-1은 Pn이 가진 자원을 기다림
    Pn은 P0이 가진 자원을 기다림

Deadlock 해결 방법

  1. Deadlock Prevention
    데드락이 생기지 않게 미리 방지하는 방법. 가장 강력한 방법이다.
    데드락이 발생하는 4가지 조건 중 하나를 차단하는 방법이다.

    Hold & Wait

    1. 어떤 프로세스가 시작될 때 이 프로세스가 필요한 모든 자원을 할당 받게 하는 방법(중간에 추가로 필요한 자원을 없게 만드는 방법 -> 비효율성)
    2. 자원이 필요한 시점에 할당 받게 하지만, 프로세스가 어떤 자원을 가지고 있는 상태에서 다른 자원을 기다려야 한다면 이미 가지고 있는 자원도 모두 반납한 후에 기다리게 하는 방법.

    No preemption

    자원을 강제로 빼앗길 수 있게(preemption) 해준다. 자원의 현재 상태를 쉽게 save & restore 할 수 있는 상태일 때 사용하는 방법이다.(CPU, memory)

    Circular Wait

    자원마다 번호를 매겨서 낮은 번호 자원부터 획득해야지 높은 번호 자원을 획득할 수 있도록 한다.(싸이클이 생길 수 없게 만들기) -> 자원에 대한 이용률이 낮아지고, 시스템 성능 저하, starvation 등의 문제가 발생할 수 있다.(데드락이 생기지도 않을 수도 있는데 제약조건을 달아놓으면 비효율적이기 때문)

  2. Deadlock Avoidance
    데드락이 생기지 않게 미리 방지하는 방법. 자원 요청에 대한 부가 정보를 활용해서 deadlock 가능성이 없는 경우에만 자원을 할당해주는 방법이다.

    프로세스가 시작되서 종료될 때까지 그때 그때 상황마다 사용될 자원의 수나 종류가 다른데 Deadlock Avoidance는 프로세스가 시작될 때 이 프로세스가 평생 쓸 자원의 최대량을 미리 알고 있다고 가정하고 deadlock을 피해가는 방법이다. deadlock이 발생할 것 같으면 여분이 있어도 자원을 할당해주지 않는다.

    <자원의 instance가 하나씩인 경우>
    Resource Allocation Graph Algorithm 사용

    <자원의 instance가 여러개인 경우>
    Banker's Algorithm 사용(각 자원의 최대량과 현재 할당된 자원량을 이용하여 가용 자원량을 계산하고 가용 자원량과 각 프로세스의 요청 가능한 최대량을 비교하여 가용 자원량으로만 자원 공급이 가능할 겨우만 자원 공급)

  3. Deadlock Detection and recovery
    시스템에 문제가 있을 때 데드락이 있는 지 확인해보고 고쳐주는 방법.

    <자원의 instance가 하나씩인 경우>
    Resource Allocation Graph Algorithm 사용

    <자원의 instance가 여러개인 경우>
    표를 그려 확인(현재 할당된 자원 | 실제 요청한 자원 | 사용 가능한 자원)
    사용 가능 자원으로 해결할 수 있는 프로세스 있는지 확인
    -> 요청 자원이 없는 프로세스부터 자원을 반납한다고 가정
    -> 나머지 프로세스들의 요청을 받아들일 수 있는 지 확인

    데드락이 발견되면 recovery작업

    1. 데드락에 연루된 모든 프로세스 사살
    2. 데드락이 없어질 때까지 데드락에 연루된 프로세스를 하나씩 사살해본다
  4. Deadlock Ignorance
    데드락에 대해 아무 일도 하지 않는 방법(현대 운영체제가 대부분 이 방법이다. 데드락은 잘 발생하지 않는데 미연에 방지하려고 오버헤드를 들이는 것이 비효율적이기 때문)

    -> 사용자가 알아서 처리하도록 함

0개의 댓글