[운영체제] 7장 Deadlocks

Deadlock Problem

Deadlock – 교착상태, 결과적으로 아무것도 할 수 없는 상태, 서로 자원을 점유하기 위해 무한정 대기하는 상태

Deadlock 예시

프로세스 P1, P2가 서로 엉켜서(자원이 엉킴) 더 진행되지 못함

 

Deadlock Characterization

Deadlock이 걸리는 필요조건(이런 조건이 만족되면 Deadlock이 발생 할 수도 있다, 100퍼 발생x) 4가지 원인(해결이 필요함)

>Mutual exclusion(상호배제) : 한번에 오직 한 개의 작업만 자원에 접근할 수 있다.

>Hold and wait(점유대기) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림.

>No preemption(비선점) : 다른 프로세스가 수행이 완료될 때까지 기다림(사용 중인 자원을 뺏을 수 없음.)

>Circular wait(순환대기) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원(데이터)을 가지고 있다.

>>이 조건 중에서 한 가지라도 만족하지 않으면, 교착 상태는 발생하지 않는다.

 

Deadlock 해결

>Deadlock prevention (Deadlock 예방)

• Restrain how requests are made
• Ensure that at least one necessary condition cannot hold

>Deadlock avoidance (Deadlock을 피함, 요청이 들어올 때 마다 쉐어드 데이터의 상태를 판단해서 교착상태 발생을 방지함, 오버헤드가 큼)

• Require additional information about how resources are to be requested
• Decide to approve or disapprove requests on the fly

>Deadlock detection and recovery(발견과 회복, 최소비용으로 해결을 하는 것을 우선시) - 원하는 대로 자원을 주고 교착상태가 발생하면 이전상태로 돌려주는 것

• Allow the system to enter a deadlock state and then recover

>Just ignore the problem altogether!(운영체제에서 가장 제일 현실적인 방식 – 문제를 전적으로 무시해버림, 개발자가 스스로 해결하게 하는 것)

 

 

Deadlock Prevention

>Mutual Exclusion – 한 프로세스가 계속 점유하는 것을 방지, but 불가능함...

>Hold and Wait (한 번에 한 프로세스가 점유할 수 있게 해주는 것, but 굶주림 발생, 비효율)

 

>선점형으로 바꿔줌 해결이 가장 무난하긴함, but 굶주림 상태가 발생할 수 있음

원형(순환)대기 – 계속해서 우선순위를 부여... 번거롭다, 잘 사용x (사실상 방지가 어렵다)

 

 

Deadlock Avoidance(Deadlock 회피)

Deadlock이 일어날 것 같은 상황을 임의적으로 피함

 

Safe State

Safe State Sequence – 할당이 가능한 자원 or 할당이 불가능 하더라도 이전에 프로세스가 사용을 마친 자원 (deadlock이 발생하지 않음, 모든 프로세스가 끝날 때까지)

 

Unsafe한 상태를 피해서 진행하는 것

 

Unsafe상태이면 deadlock이 될 수 있는 것이지 교착상태인 것은 아님

따라서 Deadlock Avoidance는 unsafe한 상태가 되지 않게 보장을 해주는 것

 

safe와 unsafe 그림 예시

 

Resource-Allocation Graph Algorithm -> 회피 방법 중 하나

순서를 그래프로 그려서 해결 (크게 중요x) - 공유자원의 수가 적어야 가능

 

Banker’s Algorithm

Banker’s Algorithm - 공유자원의 수가 많을 때 사용이 좋음(deadlock 회피 알고리즘)

운영 상태에서 safe상태인 것만 받고 unsafe상태는 전적으로 거절하는 것

Banker’s Algorithm 그림 예시

-Multiple instances에서 사용

 

Banker’s Algorithm의 데이터 구조 -> safe sequence를 찾기 위한 계산 방법들

Available – 줄 수 있는 자원의 수, 1차원 배열, 각 리소스 타입 별로 남은 인스턴스 정보를 저장함, 현재 남아있는 자원

Max – 각 프로세스가 요청할 수 있는 최대 자원의 수, 이것을 채워야지 프로그램이 종료 가능

Allocation – 현재 할당된 자원의 수를 나타냄

Need – 앞으로 얼마나 더 요청가능한지, 얼마나 더 필요한지

=> Need[i, j] = Max[i, j] - Allocation[i, j]

>>safe state sequence를 확인할 때 Max랑 Has, Free랑 Available이랑 같은 의미를 지님.

뒤쪽 부분부터 위의 것들을 계산하는 방법이 나옴

 

 

Banker’s Algorithm 실전 예제

가장 먼저 구해야 하는 것이 Need임 -> 앞으로 필요한 요구량

 

Banker’s Algorithm 실전 예제 -> Need를 구함

Max값은 Allocation 값보다 작을 수 없다.

 

Available 리소스 부분과 Needed 리소스 부분을 비교하여 자원을 할당하여 가능한 프로세스가 있는지를 비교하고 그러한 경우가 모든 프로세스가 수행될 때까지 가능한 sequence가 있다면 그것을 safe sequence라고 하고 그러한 safe sequence가 하나라도 있는 경우를 safe하다라고 한다.

 

Banker’s Algorithm 사용 시 단점

최대 요구량을 사전에 파악하기가 어려움(SJF와 비슷)

또한 프로세스 수가 고정되어 있는 것이 아닌 계속적으로 동적으로 변함

순간적으로 I/O장치에 대한 요청이 들어와 현재 있는 가용자원의 수가 변할 수도 있음

-> 사용에 어려움이 있어 사실상 deadlock을 해결하는데 잘 사용하지 않음(아직까지 명확한 해결방법이 등장하지 않음)