오퍼레이팅시스템 12주차 / 14. Priority Inversion and Deadlocks

Priority Inversion(우선순위반전)

낮은 우선순위 작업이 자원을 점유한 상태에서, 높은 우선순위 작업이 같은 자원을 사용하려고 할 때 발생하는 문제

높은 우선순위 작업이 대기하게 되는 상황.

무한 우선순위 반전 : 예측 불가능한 다른 태스크들에 의해 결정됨., 실시간 제약조건이 위반 될 수 있음.

우선순위 반전을 위한 해결방법

Priority Inheritance(우선순위 상속)

자원을 점유한 낮은 우선순위 테스크가, 그 자원을 필요로 하는 높은 우선순위 테스크의 우선순위를 '일시적으로 상속받는' 기법

Priority Ceiling(우선순위 상한)

미리정해진 우선순위를 부여하여, 자원을 사용하는 테스크가 자동으로 해당 우선순위로 상승하도록 하여 우선순위 반전을 방지하는 기법

장점 : 단순하고 예측가능 

Deadlock

서로 자원을 기다리며 무한히 멈춰있는 상태, 상호 의존 상태

Resource allocation graphs

1. 일반적으로 비선점 자원에서 발생한다. 

2. 재사용 자원 : 사용해서 사라지지않고 한번에 한 프로세스만 사용될 수 있다.

자원 이용 과정 : 1)요청 -> 2)Lock(할당) -> 3)사용-> 4)Unlock(release)

3. 소비되는 자원 : 생성되고 사라진다.

 

 - Resource Allocation Graphs  

유향그래프.

Vertices : P는 프로세스(동그라미로 표시), R은 리소스(사각형으로 표시)

Edges : 프로세스에서 리소스로 향하는 edge는 요청한다는 의미, 리소스에서 자원으로 향하는 edge는 점유한다는 의미

 

cycle 없으면 데드락 X

cycle 있는데 one instance면 데드락 0, multi instances면 데드락 있을 수도 없을 수도(보통 없다)

 

 

Dining Philosophers Problem

다익스트라에 의해 소개된 개념, 보통 5명의 철학자(프로세스)와 5개의 음식(자원). 각 철학자는 음식을 먹기위해 2개의 포크가 필요하다. 동시에 포크 사용불가하며 자신의 왼쪽 포크와 오른쪽포크를 사용한다. 

목표 : 데드락을 예방하고 포크는 상호배제 해준다. getforks() -> eat() -> putforks() -> think()

The Conditions for Deadlock

 - 상호 배제 Mutual Exclusion 

(필요조건) 한번에 한 프로세스만 자원 사용 보장

 

 - 비선점 No preemption 

(필요조건) 프로세스가 작업 완료한 뒤, 리소스는 프로세스에 의해서만 자발적으로 풀어질 수 있다.

 

 - 점유한 상태에서 대기 Hold and Wait  

(필요조건) 하나 이상의 리소스를 점유한 프로세스가 다른 프로세스에 의해 점유된 다른 리소스를 획득하기 위해 대기 중인 상태

 

 - 순환 대기 Circular Wait  

(필요충분조건) 프로세스0이 프로세스1에 의해 점유된 자원을 기다리고, 프로세스1이 프로세스2에 의해 점유된 자원을 기다리고 ... 프로세스n이 프로세스0에 의해 점유된 자원을 기다리는 서로가 다른 서로의 자원을 기다리는 cycle

Dining Philosophers Solution

 

Handling Deadlocks

1) 데드락 예방 : 데드락 발생 조건 4가지 안가지도록 제약, concurrency, utilization이 희생 될 가능성 존재

2) 데드락 회피 : 데드락 발생 가능성 있으면 자원 사용을 회피 (추가적인 미래 정보가 필요)

3) 데드락 탐지와 회복 : 데드락 가정하고 주기적으로 데드락을 체크, 프로세스 종료 또는 자원 회수로 회복시킨다.

4) 그냥 무시 : 위의 3가지 방법 cost 커서 아무것도 안하는게 성능 좋을 수도. 데드락은 어차피 잘 안일어나는 일이니 그냥 무시하는  방법

Deadlock Prevention

데드락 발생 조건 4가지 중 하나에 제약을 걸자.상호 배제와 비선점은 상대적으로 제약 걸기 어렵다.

 

- 점유 대기 제약 : 프로세스가 모든 요청된 자원을 한번에 요청하고, 모든 요청이 동시에 승인될 수 있을 때까지 프로세스를 블로킹한다.

점유 대기 제약 단점 : 비효율적, 프로세스 속도 저하 및 불필요하게 리소스 접근 거부. 점유 상태에서 대기 불가

 

- 순환 대기 제약 : 리소스에 번호매김으로써 순서화(linear ordering) 각  프로세스는 오름차순으로 자원 요청. 

순환 대기 제약 단점 : 편리하지 않고 복잡하고 자원 요청 오름차순으로밖에 못하는 제약

Deadlock Avoidance

 

1. Resource allocation graph Algorithm

 

2. Banker's algorithm

교착상태를 사전에 방지하기 위해 고안된 안전성 검사알고리즘. 안전상태를 유지하는지 판단

자원요청이 들어왔을 때, 그 요청을 승인 했을 때에도 시스템이 안전 상태라면 >>요청승인

 

Deadlock Detection and Recovery