OS #6 DeadLock

김태준·2023년 3월 31일
0

CS & OS Study

목록 보기
9/12
post-thumbnail

✅ DeadLock

🎈 데드락이란 ?

: 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해 다음 처리해야할 사항을 진행하지 못하는 상황으로, 무한히 다음 자원을 기다리게 되는 상태를 의미한다.
< 위 그림과 같이 차량이 서로 지나가길 기다리고 있는 상황을 의미 >

앞서 학습한 semaphore를 예시로 들어보면, 변수 A, B가 있고 프로세스 P1이 P(A), P(B)를 순서대로 호출하고 P2가 P(B), P(A)를 호출한다고 하면 각 프로세스는 서로 변수를 기다리는 상태가 되어버리는데, 이를 데드락 상태라고 한다.

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

  • REQUEST: 자원 요청, 만일 타 프로세스가 해당 자원 사용 중인 경우 대기
  • ALLOCATE : 자원 할당 받음
  • USE : 프로세스가 받은 자원 사용
  • RELEASE : 프로세스가 자원 놓아줌
    이때, 데드락은 모든 프로세스가 REQUEST 상태가 되어있는 상황을 의미

💡 주로 발생하는 경우

  • 멀티 프로그래밍 환경에서의 한정된 자원 사용
  • 대기 상태로 들어간 프로세스들이 실행상태로 변경 불가능 할 때

🎈 DeadLock Characterization

데드락이 발생하기 위해선 다음 4가지 조건을 모두 만족해야 한다.

  1. Mutual Exclusion
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
  1. Hold and wait
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유한 자원을 release하지 않고 계속 보유
  1. No preemption
  • 프로세스는 OS에 의해 강제로 자원을 빼앗기지 않는다.
  1. Circular wait
  • 자원을 기다리는 프로세스 간 사이클이 형성되어야 함

🎈 Resource-Allocation Graph

: 프로세스 간 관계를 도식화한 그래프로, 데드락 발생여부를 확인할 수 있다.

  • R은 자원을 의미, P는 프로세스를 의미, 자원 내 검은 동그라미는 인스턴스를 의미한다.
  • 자원 -> 프로세스 edge : 해당 자원을 프로세스가 Allocation 중
  • 프로세스 -> 자원 edge : 프로세스가 해당 자원을 Request

자원 당 하나의 인스턴스만 존재하면 DeadLock이고 여러 인스턴스가 존재하는 경우 DeadLock 여부를 판단해야 한다. (프로세스 간 사이클이 왼쪽 그래프에만 존재하기 때문)

🎈 DeadLock Solution

앞서 DeadLock 용어 해석, 발생 조건을 살펴보았다. 그렇다면 어떻게 데드락을 피할 수 있을까?

💡 1. DeadLock Prevention

  • 용어 그대로 미리 예방하는 방법. 자원 할당 시 DeadLock 조건 4가지 중 어느 하나가 만족되지 못하도록 하는 방식
  • 효율성과 처리량을 감소시키고, starvation이 발생할 수 있음 (자원 낭비가 심함)

💡 2. DeadLock Avoidance

  • DeadLock이 발생할 가능성 있는 경우에 아예 자원 할당하지 않는 방식
    ex) 가장 단순한 방식으로, 프로세스들이 필요로 하는 자원 별 최대 사용량 미리 선언
  • 시스템이 unsafe state에 들어가지 않는 것을 보장하는 것
    safe sequence : 프로세스 내 순서 중 Pi의 자원 요청이 순차적으로 충족되는 경우
    safe state : 시스템 내 프로세스들에 대해 모두 safe sequence가 존재하는 경우
  • Avoidance 알고리즘 종류
    2-1) Resource Allocation Graph Algorithm

    : 프로세스에서 자원을 요청하는 (request edge)가 자원을 할당받는 순간 방향이 반대되는 (assignment edge)로 변경 될 때 모든 edge에 대해 사이클이 생기지 않는 경우에만 요청된 자원을 할당
    2-2) Banker's Algorithm
    다익스트라가 고안한 알고리즘으로, 프로세스가 자원을 요청할 때마다 수행된다.
    기본 개념으로, 자원 요청 시 safe 상태를 유지하는 경우에만 할당하며 총 요청 자원 수가 남은 자원 수보다 적은 프로세스만을 선택하며 수행하고 그런 프로세스가 없다면 unsafe 즉, 데드락이 발생할 수 있는 상태인 것으로 판단

💡 3. DeadLock Detection

  • 자원 할당 그래프를 통해 DeadLock 탐지
  • 자원 요청 시, detection algorithm을 실행시켜 그에 대한 오버헤드 발생

💡 4. DeadLock Recovery

  • DeadLock 일으킨 프로세스를 종료 or 할당 자원을 해제시켜 회복
  • < 프로세스 종료 방법 >
    DeadLock 상태의 프로세스 모두 중지
    DeadLock 상태 제거될 때까지 하나씩 프로세스 중지
  • < 자원 선점 방법 >
    DeadLock 상태의 프로세스가 점유하고 있는 자원 선점해 타 프로세스에 할당
    우선 순위 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
    +) deadlock 발생 이전으로 rollback 후 프로세스를 재시작하는데, 동일 프로세스가 지속적으로 선택되면 starvation이 발생할 수 있어 rollback된 횟수를 저장해 해결

💡 5. DeadLock Ignorance

  • DeadLock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식
    DeadLock 자체가 매우 드물게 발생하기에 이에 대해 조치를 취하는 행위 자체가 더 큰 overhead일 수 있다. 따라서 시스템이 비정상적으로 작동하는 것을 사람이 느끼고 프로세스를 수동적으로 직접 죽이는 방법으로 대처하는 방식
  • UNIX, Windows 등 대부분의 범용 OS가 채택하는 방식

참고 자료

링크텍스트

profile
To be a DataScientist

0개의 댓글