Deadlock

개념

Blocked/Asleep state

• 프로세스가 특정 이벤트, 필요한 자원을 기다리는 상태

Deadlock state

• 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
• 시스템 내에 deadlock에 빠진 프로세스가 있는 경우
• 기아상태 = ready상태에서 processor를 기다리는 경우(우선순위가 밀려서, 단순히 운인 경우도 있음) ↔ deadlock = 발생 가능성이 없는 이벤트(자원)를 기다림
• 서로 원하는 자원이 상대방에 할당 되어 있어서 무한 wait 상태일 경우

Deadlock 발생 분류

?
할당 단위에 따른 분류
동시사용 가능
재사용 가능 여부

Deadlock 발생 자원

• Deadlock을 발생시킬 수 있는 자원의 형태
  • Non-preemptible 선점불가능 자원
  • Exclusive allocation 혼자쓰는 자원
  • 할당 단위는 영향 ❌
  • 재사용이 가능한 경우만 고려(자원이 소비되는 경우는 너무 복잡)

Deadlock 발생 조건

1. 상호배재 (한번에 한 프로세스만 사용)
2. 점유대기(Hold and wait, 최소 하나의 자원을 점유한 상태에서 다른 프로세스에 할당되어있는 자원을 점유하기 위해 대기하는 상태)
3. 비선점 (강제로 뺐을 수 없음)
4. 순환 대기(cycle(순환) 형태)

• 4가지 전부다 해당 되는 경우

Deadlock Prevention (교착상태 예방)

4개의 deadlock 발생 필요 조건 중 하나를 제거

• 모든 자원을 공유 허용
  • 상호배제를 안함 ➡ 현실적으로 불가능
• 모든 자원에 대해 선점 허용
  • 작업 중에 선점 당할 수 있음 ➡ 현실적으로 불가능
  • 유사한 방법
    • 할당 받을 수 없는 자원을 요청한 경유, 기존에 가지고 있던 모두 반납하고 작업 취소 (처음 부터 다시 시작)
    • 심각한 자원 낭비 발생 ➡ 현실적으로 불가능
• 필요 자원 한번에 모두 할당 (Total allocation과 유사, 점유 대기 부정)
  • Hold and wait 조건 제거
  • 자원 낭비 발생
    • 필요하지 않은 순간에도 가지고 있음
  • 무한 대기 현상 발생
• Circular wait 조건 제거
  • Totally allocation을 일반화 한 방법
  • 자원들에게 순서 부여
  • 프로세스는 순서의 증가 방향으로만 자원 요청 가능
  • 자원 낭비 발생 (앞 번호의 자원을 먼저 받아야 하기 때문a)

Deadlock Avoidance(회피)

스템의 상태를 계속 감시
시스템이 deadlock 상태가 될 가능성이 있으면 할당 요청 보류
시스템을 항상 safe state로 유지

Safe state
모든 프로세스가 정상적으로 종료 가능한 상태
safe sequence가 존재 (deadlock 상태가 되지 않을 수 있음을 보장)

banker's algorithm

• Deadlock avoidance를 위한 간단한 이론적 기법
• 한 종류의 자원이 여러개 있다고 가정
• 시스템을 항상 safe state로 유지
• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함

실행 종료가 가능한 순서가 있으면 Safe sequence가 있음
자원을 할당했다고 가정했을 때 Unsafe state면 할당 안함.

프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피

Habermann's algorithm

• banker's algorithm의 확장
• 여러 종류 자원 고류
• High Overhead 항상 시스템을 감시해야함
• 자원 활용 효율이 낮음
• 현실적으로 활용하기 힘듬

Deadlock Detection(해결)

Deadlock detection(탐지)

• 주기적으로 데드락 발생 확인, 자원 할당 그래프(프로세스-자원)를 이용

• 유향 이분 그래프 (프로세스-자원)로 확인

• Graph reduction(Deadlock아닌 상태)

  • unblocked process (필요한 자원을 모두 할당받을 수 있는 프로세스)

• High overhead

Deadlock recovery(해결)

Deadlock을 감지하고 해결하는 과정
**Deadlock recovery mehtods

• Process termination
  • Deadlock 상태인 프로세스 중 일부 종료
  • 프로세스 종료할 cost model
    • 우선순위, 종류, 수행시간, 남은시간, 종료비용 등
• Resource preemption
  • Deadlock 상태 해결을 위해 선점할 자원 선택
  • 해당 자원을 가지고 있는 프로세스를 종료 시킴
    • deadlock 상태가 아닌 프로세스가 종료될 수 있음
    • 해당 프로세스는 이후 재시작 함
    • 우선순위가 낮은 프로세스 위주
• Checkpoint-restart method
  • 프로세스의 수행 중 특정 지점(check point)마다 context를 저장
  • Rollback을 위해 사용

---

https://youtu.be/EdTtGv9w2sA [Course] Operating System (CPA310) - 운영체제 강의. HPC Lab. KOREATECH