교착상태 Deadlock Resolution

deadlock

 

Blocked/Asleep state

- 프로세스가 특정 이벤트를 기다리는 상태

- 프로세스가 필요한 자원을 기다리는 상태

 

Deadlock state

- 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우

 - 프로세스가 deadlock 상태에 있음

- 시스템 내에 deadlock에 빠진 프로세스가 있는 경우

 - 시스템이 deadlock 상태에 있음

 

 

자원의 분류

Hadware resources vs Software resources

 

 

선점 가능 여부에 따른 분류

 

Preemptible resources

- 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원

- Processor, memory 등

 

Non-preemptible resources

- 선점 당하면, 이후 진행에 문제가 발생하는 자원

- disk, drive 등

 

 

할당 단위에 따른 분류

 

Total allocatoin resources

- 자원 자체를 프로세스에게 할당

- Processor, disk drive 등

 

Partitioned allocatoin resources

- 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당

- Memory

 

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

 

Exclusive allocation resources

- 한 순간에 한 프로세스만 사용 가능한 자원

- Processor, momory, dis drive

 

Shared allocation resource

- 여러 프로세스가 동시에 사용 가능한 자원

- Program, shared data 등

 

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

 

SR ( Serially-reusable Resources)

- 시스템 내에 항상 존재 하는 자원

- 사용이 끝나면, 다른 프로세스가 사용 가능

- Processor, memory, disk drive, program

 

CR(Consumalbe Resources)

- 한 프로세스가 사용한 후에 사라지는 자원

- signal, message 등

 

Deadlock을 발생시킬 수 있는 자원의 형태

 

Non - preemptible resources

Exclusie allocation resources

Serially resuable resources

 

 

Deadlock 발생의 예

 

 

Deadlock 발생 필요 조건

 

Exclusive use of resources

Non-preemptible resources

 

 

Hold and wait

 

Circular wait

Deadock Prevention

 

1. 모든 자원을 공유 허용 - > 불가능

 

2. 모든 자원에 대해 선점 허용 -> 불가능

유사방법

- 프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소

- 심각한 자원 낭비 발생 -> 비현실적

 

3. 필요 자원 한번에 모두 핟랑 (Total allcation)

- Hold and wait 조건 제거

- 자원 낭비 발생

 - 필요하지 않은 수간에도 가지고 있음

- 무한 대기 현상 발생 가능

 

4. Circular wait 조건 제거

- 자원들에게 순서를 부여

- 프로세스는 순서의 증가 방ㅇ향으로만 자원 요청 가능 

- 자원 낭비 발생

 

 

 

Deadock Avoidance

- 시스템의 상태를 계속 감시

- 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류

- System을 항상 safe state 로 유지

 

 

Safe state

- 모든 프로세스가 정상적 종료 가능한 상태

- Safe sequence가 존재

 

Unsafe state

-Deadlock 상태가 될 가능성이 있음

- 반드시 발생한다는 의미는 아님

 

 

가정

- 프로세스의 수가 고정됨

- 자원의 종류와 수가 고정됨

- 프로세스가 요구하는 자원 및 최대 수량을 알고 있음

- 프로세스는 자원을 사용 후 반드시 반납한다.

 

 

Banker's algorithm

 

- Deadlock avoidance를 위한 간단한 이론적 기법

 

 

 

 

위의 상태를 Unsafe 상태라고한다.

 

 

 

p1이 1을 빌려주라고 햇을때 줫다고 가정하면 위의상태에서 다시 자원을 세개가 동시에 요청햇을때 가능한가를 따져보면된다. 위에 결과는 safe

 

이 경우는 unsafe

 

 

Deadlock 해결 방법

 

Deadlock Detction

 

Deadlock 방지를 위한 사전 작업을 하지 않음

 

 

 

위에 그림은 데드락인가 ?

데드락 판단 방법

- 주어진 RAG에서 edge를 하나씩 지워 나가다보면 다지워지면 데드락이아님 안지워지면 데드락

 

 

 

이런식으로 지을 수 있다.

 

 

 

Deadlock avoidance

- 최악의 경우를 생각

- Deadlock 이 발생 하지 않음

 

Deadlock detction

- 최선의 경우를 생각

- Deadlock 발생 시 Recovery 과정이 필요

 

 

Termination cost model

- 종료 시킬 deadlock 상태의 프로세스 선택

 - 우선순위 / Process priority

 - 종류 / Process type

 - 총 수행 시간

 - 남은 수행 시간

 - 종료 비용

 

종료 프로세스 선택

 

- Lowerst-termination cost process first

 - Simple

 - Low overhead

 - 불필요한 프로세스들이 종료 될 가능성이 높음

 

- Minimum cost recovery

 - 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택

  - 모든 경우의 수를 고려 해야 함

  - complex

  - High overhead

 

Resource preemption

- Deadlock 상태 해결을 위해 선점할 자원 선택

- 해당 자원을 가지고 있는 프로세스를 종료 시킴

 - 데드락이 아닌 프로세스가 종료 될수 있음

 

checkpoint-restart method

- 프로세스의 수행 중 특정 지점 마다 context를 저장

- Rollback을 위해 사용

 - 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작