HPC Lab) Deadlock

Blocked / Asleep 상태

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

Deadlock 과 Starvation 은 다른것이고 다른 process state 에서 일어난다.

Starvation 은 발생 가능할 수 있는 이벤트인데 priority 나 운이 없어서 계속 기다리게 되는 상태 , CPU를 기다리고 있음

Deadlock 은 발생이 불가능한 이벤트이고 CPU가 아닌 다른 자원을 기다리고 있는 중이다.

 

 

자원의 분류

 

선점가능 여부에 따른 분류

Preemptible resource = 선점 당한후 돌아와도 문제가 발생하지 않는다.  CPU, Memory (Swap device)

Deadlock // Non preemptible resources = 선점 당하면 , 이후 진행에 문제가 발생하는 자원 , Rollback , restart가 필요 , disk drive 

 

할당 단위에 따른 분류

total allocation resources = 자원 전체를 프로세스에게 할당 해준다. Processor , disk drive 등

Partitioned allocation resources = 하나의 자원을 여러 조작으로 나누어 , 여러 프로세스들에게 할당. Memory

 

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

Deadlock // Exclusive allocation resources = 한 순간에 한 프로세스만 사용 가능한 자원. Processor , memory , disk drive

Shared allocation resource = 여러 프로세스가 동시에 사용 가능한 자원. Program(SW, Source code) , shared data

 

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

Deadlock // SR(serially -reusable resources) = 시스템 내에 항상 존재하는 자원 , 사용이 끝나면 다른 프로세스가 사용가능. Processor, memory, disk drive, program 등

CR(consumable resources) = 한 프로세스가 사용한후에 사라지는 자원. singal , messages 등

 

Deadlock 발생 필요 조건

• Exclusive use of resources
• Non preemptible resources
• Hold and wait (partial allocation) = 자원을 하나 hold하고 또 다른 자원 요청
• Circular wait

예방하기위해선 4가지 조건이 안나타게 하면 되지만 비현실적이고 , 자원의 낭비가 심해진다.

 

Deadlock Avoidance

Safe state 유지 = 모든 프로세스가 정상적 종료가 가능한 상태 , Safe sequence 가 존재하여 deadlock 상태가 되지 않을 수 있음을 보장

Unsafe state = Deadlock 상태가 도리 가능성이 존재 

이론 설명을 위한 가정 

• 프로세스의 수 고정
• 자원의 종류와 수 고정
• 프로세스가 요구하는 자원 및 최대수량 정해짐 

 

Dijkstram's banker's algorithm = safe sequence 가 한 개 이상만 존재해도 Deadlock 걸리지 않음

safe sequence 를 만드는 과정에서 요청이 들어왔을 때 그 자원을 할당했다 가정해보고 다음 sequence를 찾아본다. 없으면 reject 있으면 okay 한다. 

habermann's algorithm = 동일하지만 이번에는 여러개의 자원을 고려함 , safe sequence 만들 수 있는 여부에 따라 reject or ok 해준다.

prevention 단점

1. 이렇게 지속적으로 모니터링 해야하기에 overhead가 존재한다. 
2. safe state 유지를 위해 여분의 자원을 남겨두기에 , utilization 이 낮아진다.
3. not practical 가정들이 현실에서 알기 힘들다.

 

Deadlock Dection

Resource allocation Graph (RAG) = Deadlock 검출을 위해 사용 , bipartite Graph

Graph reduction = 주어진 RAG 에서 edge를 하나씩 지워가는 방법

Unblocked process = 팔요한 자원을 모두 할당 받을 수 있는 프로세스

현재 프로세스가 필요한 특정자원의 갯수가 특정 자원의 남은 수 보다 큰가? 

해당 unblocked process들의 edge들을 모두 지워버린다.

요청 edge를 따라가서 해당 resource들중 남은거들을 받아올게 있으면 okay 인거다. 해당 프로세스의 edge를 다 지우면 됨.

Completely reduced = 모든 edge가 제거됨 , Deadlock 에 빠진 프로세스가 없음

Irreducible = 지울수 없는 edge존재 , 하나 이상의 프로세스가 deadlock 상태

 

Deadlock Recovery

Process termination = deadlock 상태인 프로세스 중 일부 종료

우선순위 , 종류 , 총 수행시간 , 남은 수행시간 ,종료 비용 등을 고려하여 종료시켜준다.

Resource preemption = deadlock 상태 해결을 위해 선점할 자원 선택 , 해당 자원을 가지고 있는 프로세스를 종료시킴

deadlock 이 아닌 애가 종료 될 수 있다. 

Checkpoint restart method = 프로세스의 수행중 특정 지점마다 context를 저장 , rollback을 위해 사용 , checkpoint 에서 재시작.