Chapter7. 교착상태

유튜브에 있는 김덕수 교수님의 Operating System 강의를 듣고 정리한 내용입니다.
중간에 등장하는 ppt 내용들은 모두 강의자료를 캡처한 것입니다.

🔧 교착상태 (Deadlock)

Deadlock State

• 프로세스가 발생 가능성이 없는 이벤트를 기다리는 상태
  • 프로세스가 deadlock 상태에 있음
• 시스템 내에 deadlock에 빠져있는 프로세스가 있는 경우
  • 시스템이 deadlock 상태에 있음

Deadlock vs Starvation

• deadlock 상태에 빠진 프로세스가 기다리는 이벤트는 발생 가능성이 없음
• starvation 상태에 빠진 프로세스는 순서가 계속 밀리는 상황 (언젠가는 발생)

🔧 Types of Resources (자원의 분류)

일반적으로는 HW resources & SW resources

선점 가능 여부에 따른 분류

• Preemptible resources
  • 중간에 선점 당한 후(뺏긴 후) 돌아와도 문제가 발생하지 않는 자원
  • ex) Processor, Memory, …

• Non-preemptible resources
  • 선점 당하면 이후 진행에 문제가 발생하는 자원
    • Rollback이 필요하다거나, restart가 필요하다거나, …
  • ex) Disk, Drive, …

할당 단위에 따른 분류

• Total allocation resources
  • 자원 전첸를 프로세스에 할당
  • ex) Processor, Disk, Drive, …

• Partitioned allocation resources
  • 하나의 자원을 여러 부분으로 나누어 여러 프로세스들에게 할당
  • ex) Memory, …

동시 사용 가능 여부에 따른 분류

• Exclusive allocation resources
  • 동시에 한 프로세스만 사용 가능한 자원
  • ex) Processor, Memory, Disk, Drivve, …

• Shared allocation resources
  • 여러 프로세스가 동시에 사용 가능한 자원
  • ex) Program(SW), shared data, …

재사용 가능 여부에 따른 분류

• Serially-reusable resources (SR)
  • 시스템 내에 항상 존재하는 자원
  • 사용이 끝나면 다른 프로세스가 사용 가능
  • ex) Processor, Memory, Disk, Program, …

• Consumable resources (CR)
  • 프로세스가 사용한 후에 사라지는 자원
  • ex) signal, message, …

Deadlock 과 Resource type

• Deadlock을 발생시킬 가능성이 있는 자원의 형태
  • Non-preemptible resources
  • Exclusive allocation resources
  • Serially reusable resources
  • (할당 단위는 영향을 미치지 않음)

• 이때 CR을 대상으로 하는 Deadlock 모델은 너무 복잡해서 다루지 않음

🔧 Deadlock 발생 필요 조건

4 가지 조건이 모주 만족되어야 deadlock 발생

🔧 Deadlock 해결 방법

• Deadlock prevention methods (예방)
• Deadlock avoidance methods (회피)
• Deadlock detection and deadlock recovery methods (탐지 및 복구)

Deadlock prevention

• 4개의 deadlock 발생 필요 조건 중 하나를 제거
  • Exclusive use of resources
  • Non-preemptible resources
  • Hold and wait (Partial allocation)
  • Circular wait
• Deadlock 절대 발생하지 않음
• 심각한 자원 낭비 발생
• 비현실적

Deadlock avoidance

• 시스템의 상태를 계속 감시
  • 시스템을 항상 safe state로 유지
  • 모든 프로세스가 정상적 종료가 가능한지
  • deadlock 발생 가능성이 있는 자원은 시스템이 할당 요청을 보류

• Deadlock 발생을 막을 수 있음
• High overhead
  • 시스템을 항상 감시하고 있어야 함
• Low resource utilizatioon
  • safe state 유지를 위해 사용되지 않는 자원이 존재
• 여러가지 가정이 필요함 (비현실적)
  • 프로세스 수, 자원 수 고정
  • 필요한 최대 자원 수를 알고있음
  • 등…

🔧 Deadlock detection and recovery

Deadlock datection

• Deadlock 방지를 위한 사전 작을 하지 않음
• 주기적으로 deadlock 발생 여부 확인
  • 시스템이 deadlock 상태인가?
  • 어떤 프로세스가 deadlock 상태인가?
• Resource Allocation Graph (RAG) 사용
• High overhead
  • 검사 주기에 영향을 받음
  • Node의 수가 많은 경우

Resource Allocation Graph (RAG)

• Graph reduction
  • 하나의 프로세스가 요청한 자원을 모두 할당 받을 수 있으면 해당 프로세스와 연결된 모든 edge 제거
  • 반복
• Completely reduced
  • 모든 edge가 제거됨
  • deadlock에 빠진 프로세스가 없음
• Irreducible
  • 지울 수 없는 edge가 존재
  • deadlock에 빠진 프로세스가 하나 이상 존재

Completely reduced	Irreducible

Deadlock recovery

• Deadlock recovery methods
  • Process termination
    • Deadlock 상태에 있는 프로세스 강제 종료
    • 종료된 프로세스는 이후 재시작
  • Resource preemption
    • Deadlock 상태 해결을 위해 선점할 저원 선택
    • 선정 된 자원을 가지고 있는 프로세스를 강제 종료시키고 자원을 빼앗음

Process termination

• Termination cost model
  • Process priority (우선순위)
  • Process type (종류)
  • Accumulated execution time of the process (총 수행 시간)
  • Remaining time of the process (남은 수행 시간)
  • Accounting cost (종료 비용)
  • Etc…

• Lowest-termination cost process first
  • cost 제일 낮은 놈 선택해서 종료
  • simple / low overhead
  • 불필요한 프로세스들이 종료 될 가능성이 높음
  • (굳이 끌 필요 없는)
• Minimum cost recovery
  • 모든 경우의 수 고려 / O(2^n)
  • 최소 비용으로 deadlock 상태를 해소할 수 있는 프로세스 선택
  • complex / high overhead

Resource preemption

• Process termination과 마찬가지로
  • Preemption cost model 정의
  • Minimum cost recovery method 사용

Checkpoint-restart method

• 종료된 프로세스를 다시 실행할 때 Rollback을 위해 사용
• 프로세스의 수행 중 특정 지점(checkpoint) 마다 context 저장
• 가장 최근의 checkpoint에서 재시작

맨 위로 이동하기

OS 카테고리 내 다른 글 보러가기