ch6. Deadlock(데드락) #운영체제OS #데드락의조건

Concurrency : Deadlock  🐇¸.•*¨*•¸.•*¨*•¸.•*¨*•¸.•*¨*•

해당 자료는 강의 학습자료입니다.

---

아래의 세 프로세스는 현재 데드락(deadlock) 상황이다. process 1은 자원 1을 가지고 자원 2를 요청하는 중인데 이때 요청이 받아들여지지 않으면 다음 단계로 넘어갈 수 없다. 즉, P1은 다음의 요청을 기다리고 대기하고 있다. P2, P3도 동시에 요청을 기다리고 있을 때 모든 프로세스가 다음 단계로 도저히 넘어가지 못하여 멈춰있는 상황, state에 변화가 없는 상황을 데드락이라고 한다.

 운영체제와 프로세서 간의 레벨 차이 때문에 직접적으로 일어나지 않겠지만 deadlock 이 발생하기 전에 조치를 취해야 한다.

 

System models

두 가지의 Model로 현재 상황을 표현할 수 있다. P-R Model 과 S-T Model인데 둘 의 차이를 잘 이해해야 한다.

Process-Resource Model

: 프로세스와 리소스의 집합으로 구성 P, R

: Cj: number of units of Rj in the system (리소스의 개수)

: ㅁ와 O로 이루어진 모형으로 그린다. 까만 동그라미가 resource

 

 

 

 

 

 

State_Transition Model : 상태 전이 모델

: S : 현재 상태, 프로세스들이 동작하면 상태가 바뀌는데 이 상태들의 집합

: 프로세스와 리소스의 상세를 자세히 보지 않지만, 상태들의 집합으로 표현한다.

: state changes when processes take action

: This allows us to indentfy a deadlock situation in the operating system.

 

 

 

 

 

 

 

 

 

상태 전이는 process의 action에 의해 system 변할 수 있음을 의미하고 3가지의 행동(방법)이 있다.

 

상태를 변화하는 action에는 3 가지가 있다.

- request : request one or more units of a resource : 리소스를 요청

- allocation : All outstanding requests from a process for a given resource are satisfied. : 리소를 할당

- deallocation : the process release units of a resoucre. : 리소르를 돌려줌(내놓기)

 

 

P2 에 의해 변경되는 상태가 없다면 p2는 block되었다고 말한다.

 

상태 전이 모델로 deadlock 확인하기

 

 

 

deadlock 을 막는 방법 : deadlock이 발생하는 조건 4가지 중에 하나라도 불만족하면 된다.

- Prevention : 예방 , deadlock이 발생하지않도록 시스템을 설계 -> deadlock의 조건을 알아야함 (4가지)

- Avoidance : 회피 , deadlock까지 진행하지 않는 모델을 설계하고 전략을 설정 -> 예측하기 위해서 action 정보와 시뮬레이션이 필요하다.

- Detection & Recovery : 감지, 회복 : 주기적으로 모니터링 하는 함수(백그라운드)

- Manual intervention :  정안되면 껐다 켜기(Reboot)

 

 

deadlock의 조건 4가지

- mutual exclusion : 한 번에 CS는 하나만 실행한다. 반드시 지켜야할 조건이다.

- hold and wait : 리소스를 가지고 기다린다.  

- circular waiting : 원형의 모양을 유지한다.

- No preemption : 선점 또는 취소를 하지 않는다. -> 요청을 계속 기다린다. 우선적으로 변경하면 block을 피할 수 있다.

Hold and Wait :Need to be sure a process does not hold one resource while requesting another

필요한게 있으면 한꺼번에 요청하기

 

아래를 향한 화살표처럼 다른 프로세스의 action에도 상황이 바뀔 수도 있지만 모든 리소스의 요청을 한 번에 진행하면 데드락은 방지할 수 있다.

 

Approach 1: Force process to request all resources it needs at one time.

한 번에 모든 리소스를 할당 받는다.

Approach 2: If a process needs to acquire a new resource, it must first release all resources it holds, then reacquire all it needs.

새로운 리소스가 필요하면 모든 리소스를 내려놓고 다시 요청한다.

 

이런 모델은 만든 이유는 시스템을 정의해야 하기 때문이다. 데드락이 발생하지 않는 설계를 만들기 위해서 먼저 개념적인 정의가 필요하다.

 

프로세스가 리소스를 가지고 있으면서 다른 것을 요구하여 발생하는 꼬이고 꼬인 모양의 데드락을 사전에 방지할 수 있다.

 

Circular wait : Have a situation in which there are N processes holding units of N resources

모든 프로세스를 순서를 매긴다. 그리고 각 프로세스는 자신의 숫자보다 높은 프로세스에게 요청할 수 있다.

 

O가  process, ㅁ가 Resources

R -> P : Hold : 실선

P -> R : request : 점선

 

철학자들의 저녁식사에 적용하면 : 원의 형태의 요청의 방식 때문에 발생함.

-> 마지막 숫자인 4의 발생 순서말 잘 배치하면 된다.

 

Circular wait (cont')

 

There is a cycle in the graph of processes and resources

choose a resource request strategy by which no cycle will be introduced

일종의 전략을 취한다.

 

Total order on all resources, then can only ask for Rj if Ri < Rj for all Ri the process is currently holding.

 

 

Allow Preemption

Allow a process to time-out on a blockes request - withdrawing(Wu) the request if it fails

 

request 전으로 취소하는 것을 추가하였다. -> Si로 다시 돌아온다. 내가 취소하면 다른 프로세스도 상태를 변화할 수 있다. -> 이정도의 우선순위 변화도 충분하다.

 

deadlock은 아닌데 deadlock 처럼 보이는 현상 : 머물러있는 것처럼 보이지만, 계속 왔다갔다 양보하면서 리소스를 사용하지 못하는 상황이다.

Livelock :서로양보하기 : two or more processes continually repeat the ame interaction in response to changes in the other processes without doing any useful work

- These processes are not in the waiting state, and they are running concurrently.

- This is different from a deadlock because in a deadlock all processes are in the waiting state.

 

 

 

 

Deadlock Avoidance : 데드락 회피  

deadlock까지 진행하지 않는 모델을 설계하고 전략을 설정 -> 예측하기 위해서 action 정보와 시뮬레이션이 필요하다.

 

Define a model of system states , then choose a strategy that will guarantee that the system will not go to a deadlock state

 

Requires extra inforamation, e.g., the maximum claim for each process

최대 요구량을 계산한다.

 

Allows resouce manager to see the worst case that could happen, then to allow transitions based on that knowledge.

리소스관리자(OS)가 worst case가 일어나는지 항상 감시하고 있다. 

- the resource is available :리소스는 사용 가능하다.

- Even if all processes use ther maximun reosources, : 모든 프로세스가 최대 리소스를 사용한다.

- Finally, when a state transition that can complete the execution of all processes in the system is possible : 모든 프로세스가 수행중에 최대의 리소스를 사용하는 상황을 사용하더라도 안전한 상태라면 이를 허용한다.

 

상태를 구분할 수 있어야하는데 2가지로 나눈다.

 

Safe vs UnSafe states

safe state: one in which the system can assure that any sequence of subsequent transitions leads back to the initial state : init으로 돌아갈 수 있는 상황

- Even if all exercies their maximun claim, there is an allocation strategy by which all claims can be met.

 

Unsafe state: one in which the system cannot gurantee that the system will transition block to the initial state.

- unsafe stste can lead to a dead lock state if too many processes exercise their maximum claim at once.

 

초기 상태로 돌아가는걸 보장을 못하고

dead lock 이 발생할 수 있는 (직전) 상태

 

 

최대치로 사용하는걸 비권장하는 이유 : 여러 프로세스가 동작하기 때문에 제 때 release 하면 다행이지만 사용하는 경우  deadlock이 발생할 수 있다. 보수적으로 안전하게 사용하는걸 보장한다.

 

대표적인 알고리즘으로 Banker Algorithm이 있다.

대출 시스템과 비슷한데 고객마다 대출 한도가 다르고 반납해야 하는게 비슷해서 이 개념을 적용한 알고리즘이다. 이는 시뮬레이션이다.

 

필요한 조건 3가지

maxc[i,j] : 최대 요청가능한 리소스 개수이다. Maximun Claim

alloc[i,j] : 현 상태에서 프로세스가 가진 리소스 개수이다. :Allocated Resources 

C : 할당 자원의 합

avail[j] 계산 값을 통해 safe인지 unsafe인지 확인한다.

 

현 시점에서 각각 프로세스에게 몇개씩 할당 되어있는지 copy한다.

지금 리소스의 최대 이용량을 이용하여 avail을 계산한다. (일종의 여유분)

이 조건에 만족하는 프로세스를 찾는다.

남아있는 avail 보다 큰 조건을 요구하면 unsafe

모든 process가 다 0이되면 safe 상태이다.

 

 

프로세스 p0를 볼 때 R0의 리소스를 사용하는 것을 보면 최대 3개를 요청할 수 있으나 현재 2개(allocated)를 사용하고 있다. 따라서 1개만 더 할당 받을 수 있다.

 

total allocated 값을 구하여

C - total alloc = avail 값을 구한다.

 

maxc - alloc 이 avail값(최대치까지 다 쓴경우)보다 작다면 동작가능한 안전한 상태이다.

 

자원을 해제했다고 생각하고 자원 회수를 한다. avail + alloc

 

 

avail 상태가 바뀐 이후를 본다면 시스템의 자원이 5225로 증가하였다.

 

최대로 더 호출할 수 있는 경우가 2003 으로 avail보다 작아 safe상태인지 확인한다.

 

사용하고 할당 해체한다.

5225 + 1030 = 6255

 

 

 

unsafe 로 잘못 필기 하였다.

 

할당을 해제해서 값을 돌려주면 C에 다시 더해지는데 모두 해제가 가능하면 다시 8597로 돌아간다.

 

 

 

gray로 된것은 반환한 상태

 

 

 

 

 

Unsafe 상황을 알아보자.

 

일단 C에 allocated sum 을 뺀다.

8597 - 8375 = 0222

 

내가 요구할 수 있는 최대량을 요구해본다.

P3 max-allo = 1530-1210

0320 < 0222

p3의 자원 R1 에서 unsafe 상황이 발견되었다.

 

 

 

 

Deadlock Detection & Recovery : 데드락 감지와 회복 <-> avoidance 할당x 회피하는데

 

check for deadlock , then recovery

can be far more aggressive with allcoation

no maximum claim, no safe/ unsafe states

 

Differentiate between

- Serially reusable resources : 재사용 가능한 자원, 소비하고 반환하여 다시 채워지는 자원

- consumable resources : 반환하지 않고 사용 후 없어지는 자원. 생산자와 소비자가 있다.

이는 파일포인터, 문자입력, 마우스 클릭 ,이벤트 시그널 : 모두 리소스이다.

 

 

Reusable Resoucre Graph RRG : Micro model, C가 총 합이다. 완전 소거

Micro model : 하나의 single state를 조금 더 자세하게 설명한다.

Nodes 가 두가지가 있는데 p(o), R(ㅁ) 이다.

p,R 인 경우 request edge : 요청 상황

R,p 인 경우 assighment edge : 할당 상황

화살표를 해제하면 자원을 반납한 것이다.

 

 

 

 

 

상태 변화(전이)가 일어날 수 있다.

 

 

 

 

 

 

 

reusable resource를 상태전이그래프로 본 경우이다.

 

 

 

 

 

 

 

 

 

Graph Reduction 그래프축소 : 제거가 불가능하면 deadlock이다. 모두 제거하면 아니다.

Deaklock state if there is no sequence of transitions unblocking every process

모든 프로세스를 unblock하는 경우가 있으면 괜찮지만,

A RRG represents a state; can analyze the RRG to determine if there is a sequence 

 

제거 : 그 행동이 일어난 상황을 가정하고 삭제

 

제거가 가능한 상황

- block 상태가 아니다. (다음 상태전이가 가능하다.)

- request edges 를 가지고 있지 않고 assign edge는 있을 때

 

 

RRG 그래프 축소 방법 정리

 

1. 일단 process 를 찾는다.

2. 요청중인지 확인한다.

2.1. 요청이 가능하면 없앤다.

2.2. 요청이 불가능하면 현재 block이다.

 

 

다른 프로세스를 찾고 계속 진행해서 선이 남아있으면 deadlock이다.

 

 

 

Consumable Resource Graph (CRGs)

consumable resource 같은 경우

p,R request egde : 요청 상황

R,p producer edge : 생산 상황 , 만들어내고 선을 지워버린다.

따라서 producer가 살아있으면 얼마든지 만들어 낼 수 있기 때문에 선이 있어도 producer가 살아있으면 deadlock 이 아니다

 

 

 

 

 

 

 

 

따라서 위는 아래에 선이 남아 있어도 deadlock 이 아니다. (P1를 제거하고 싶지만 R0에 리소스가 없어서 제거가 안됨) 그렇지만 원형의 모양이라 이게 왜 deadlcok이 아닌진 모르겠다. 하나라도 producer 가 살아있으면 되는건지 싶다. 데드락의 기준이 다르다고 하는데 생산자체만 되면 -> 일단 상태가 변화되니까 정지된 상태는 아니다?? 로 이해했다. 

 

General Resource Graph : 일반적인 리소스 그래프

 

 

reusable : 완전소거

consumable : unblock

 

 

 

 

 

 

 

 

 

Recovery : 복구 (회복)

No magic here

-choose a blocked resource

- preempt it (releasing its resources) / 선점하여 가지고 있는 리소스를 반환

- Run the detection algorithm

- Iterate if until the state is not a deadlock state

 

checkpoint / rollback (시스템 리부팅시 어떻게 기억을 하는 걸까? -> 현재 running state를 저장)

- Process periodically saves (checkpoints) the current running state.

- If the OS determines that there is a deadlock, the OS removes the process -> Another process uses the resource.

- After then, restart by resetting the process state based on checkpoint info.

이전 동작으로 리부트