교착상태(Deadlock)의 개요와 처리

• Deadlock(교착상태)의 정의

-Deadlock

두 개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태

도로 사거리, 교차로가 있는 상황
왼쪽에서 오른쪽 차 때문에 아래에서 위로 가는 차가 방해를 받는다. 이런식으로 4군데가 다 막혀있다. 이걸 교착 상태라한다.

 

프린터와 CD가 있고, p1 p2 프로세스가 있다. 두 프로세스는 프린터와 cd가 둘다 필요하다. 그러면 운영체제로 부터 자원을 할당 받아야한다. p1은 프린터에서 할당, p2는 cd에 할당 이러면 둘다 다른것은 할당을 받지 못해서 무한 대기

 

두 개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태 -> 성능 하락
제한된 자원에 대해 이용률이 늘어나게 되고, 이용률이 늘어 나기 때문에 경쟁이 치열하고 결국 deadlock가 발생

 

중요

운영체제는 요청 자원을 빨리 요청하길 원하고 바로 주길 원한다.
반납을 안하면 계속 사용해서 deadlock이 발생할 수 있음

 

해결방법
1. 프로세스 종료/교체: 프린터 cd 사진, p1 p2중 하나를 종료시키면된다.
2. 외부에서 강제해제: 프로세스는 죽이지 않고 자원만 강제로 뺏을 수 있다.
=> Deadlock 왜 시스템에 문제가 되느냐? 프로세스가 실행되지 않고 무한정 대기만 하기 때문에,  CPU 사용률 -> 0이 되어 문제가 발생

 

-Deadlock의 발생 사례

1. 파일을 요청할 때 발생

p1, p2가 있다. 두 프로세스는 재고 파일, 공급자 파일 둘 다 필요하다. 공급자 파일 p1 할당, p2 재고 파일 할당이라면 프로세스 둘 다 다른 파일이 확보될 때 까지 기다려야함 -> 데드락

 

2. 전용장치를 할당할 때 발생(ex, CD복사)

위에 사례 있음

 

3. 공유변수를 사용할 때 발생

공유변수 사용시 발생
lock1, lock2를 이용해 임계구역을 통제하려한다. 2개 중 하나가 먼저 임계영역에 들어가면 다른 하나는 기다려야한다. 이렇게 만들고 싶지만 양쪽에서 기다리게 되면 양쪽 다 임계 영역에 못들어가서 데드락이 발생 할 수 있다.

 

4. 스풀링 시스템에서 발생

 

5. 디스크를 공유할 때 발생

p1, p2가 있고 원판인 디스크가 있다. 하드 디스크를 사용하려면 특정지역에 파일을 저장한다. a.txt를 실린더 245에 저장했다. b.txt는 실린더 300에 저장했다. 특정 섹터에 저장을 할 수 있다. 원형 부분을 트랙이라고 한다. 하드 디스크는 디스크를 겹쳐서 만든다. 실린더로 주소를 매기고 파일을 저장한다.
사용자, 운영체제 부분으로 구분한다. 디스크 헤드를 통해서 파일을 읽고 쓴다. 
p1이 a.txt에 abc라는 값을 저장하라고 운영체제에 요청한다. 운영체제는 디스크제어기한테 명령해서 a.txt 위치를 찾는다. 헤드를 움직여 a.txt위치를 찾는다. 직접 움직여서 cpu 입장에선 오래걸린다. 디스패처가 잠시 나가있으라고 한다.
그러면 p2가 실행되고 b.txt에 zzz라는 값을 저장하라고 요청하게된다. 운영체제는 이걸 받아서 명령을 내린다. 하드디스크 입장에선 겨우 a.txt 위치에 왔는데 이번엔 p2에 의해서 b.txt 부분으로 움직이라한다. 그러면 또 다시 헤드를 움직이고 디스크를 돌려서 찾아간다. 디스패쳐 입장에선 p2가 오래걸리니 내쫒고 다시 p1에게 선택권을 준다. 디스크는 계속 돌아가게되고 이런 경우 데드락이 발생이 가능하다.

 

6. 네트워크에서 발생

컴퓨터 a b c가 있다. b의 왼쪽 검정색이 수신 queue, 오른쪽 검정색이 송신 queue이다. 외부에서 데이터가 들어오면 수신 queue에 쌓인다. 데이터를 보낼게 있으면 송신 queue에서 나가게된다. 
a b c가 연결되어 있고 a->b, b->c, c->a이렇게 데이터를 보내면 
수신->송신->다른 컴퓨터 수신 이렇게 데이터가 돌고 도는 것을 반복
만약 b의 수신 queue이 꽉차면 a의 송신 queue 꽉 차고 수신 queue 꽉차고 그러면 c도 송신 queue 꽉 차고 수신 queue 꽉 차고 b에서도 송신 queue가 꽉 찬다 그러면 결국 데드락이 발생

 

데드락 발생 필요충분조건(중요) 
상호배제(3번)+점유와대기(1번)+비선점(자원을 강제로 뺏지 못한다)+원형대기(순환대기, 1, 6번)
4가지 상황이 만들어지면 데드락 발생

 

-자원할당 그래프(Resource Allocation Graph)

집합, P는 프로세스, R은 자원, E는 프로세스와 자원의 관계를 표현해주는 선

 

P는 동그라미, R은 사각형으로 표현
자원이 할당되는 경우 프로세스 방향으로 화살표
요청은 반대로 자원에 화살표

 

P1은 R1을 할당받았다. P1은 R2를 요청했다. R2는 P2에게 할당됐다. 상호배제를 하지 않아서 데드락이 발생할 수 있다.  사이클이 생기고 점유와 대기가 있고 자원을 강제로 뺏지 않으니 비선점이다. 그리고 2개가 같이 사용되지 않아서 상호배제가 있어서 Deadlock이 걸린다.

 

한 종류의 자원이 여러개 있는 경우
ex) use 포트에다가 use를 꽂으면 use 메모리가 공유자원이 된다. use 포트가 여러개 있다. 그러면 자원의 종류는 1개지만 같은 종류의 개수가 여러 개인 경우(여러 개의 인스턴스가 있는 경우)는 점으로 표현한다.
사각형 보면 1개의 리소스이지만 인스턴스가 4개 있다. Pk는 4개의 인스턴스 중 1개를 할당 받았다. 

 

집합 P, R, E:

P = {P1, P2, P3}, R = {R1, R2, R3, R4}, E = {P1->R1, P2->R3, R1->P2, R2->P2, R2->P1, R3->P3, P3->R2}

 

이런 그림 보고 Deadlock이 있는지 없는지 알아야하고 집합 보고 그림을 그릴 수 있어야 함

이 그림은 Deadlock인가?

 

 

 

 

 

 

p1이 r1에게 자원을 요청했다. r1 인스턴스가 1개
r2는 인스턴스가 2개, r4는 인스턴스가 3개
r2는 p1, p2에 인스턴스를 1개씩 줬다.

데드락인지 알기 위해선 사이클이 도는지 확인해야한다. 
사이클이 존재하지 않는다.
p3 입장에서 자원 할당을 받고 다른 자원을 요청하지 않았다. p3는 자원을 사용하고 r3 반납, 그러면 p2에게 자원할당 가능
p2 입장에서는 자원 다 r1, r3 사용하고 반납가능
p1은 필요한거 2개 자원을 할당 받고 종료가능
=> 즉 사이클이 없어서 데드락이 없다. 만약 p2가 r2를 가리키면 사이클이 생긴다.

 

P1->R1->P3->R2->P1 이지만 프로세스 P4가 R2를 해제하여 P3에 할당되면 주기가 사라짐

p2, p4가 종료가 가능해서 자원을 반납하면 p1, p3가 요청한 자원을 할당을 할 수 있다. 그러면 p1, p3도 종료가 가능하고 데드락이 없다.

 

데드락이다.

 

• 교착상태(Deadlock) 처리

-Deadlock 처리기법

Deadlock Prevention(예방): Deadlock이 아예 일어나지 못하도록 막아야한다.

Deadlock Avoidance(회피): 데드락 조짐이 보일 때 회피

Deadlock Detection(탐지): 데드락이 일어났는지 안일어났는지를 검사

Deadlock Recovery(복구): 데드락이 발생했으면 복구해야한다.

 

-Deadlock Prevention(4가지 필요충분 조건이 발생하지 않도록 예방)

1. 상호배제: 자원에 따라 다르므로 상호배제는 유지

어떤 하드디스크에 read-only file가 있고 P, Q 프로세스가 공유를 한다. P, Q에서 읽어 간다. 프로세스에서 read-only file을 변경할 수 없다면 굳이 배제하지 않아도 된다.

 

프린터고 P, Q가 공유한다.
P가 프린터를 이용해 출력
Q도 프린터를 이용하고 싶다. 
만약 P, Q의 내용이 섞여서 출력되면 안된다. 그래서 P가 프린터를 사용할 때 Q를 막는 상호배제가 필요하다!

 

2. 점유와 대기조건(Hold and Wait) 방지

step1에서 자원을 요청한다. P는 요청, Q는 자원 할당을 받음, 이런 경우는 인스턴스가 남아 있어서 step2 가능하다

 

오른쪽 위 Q1, 오른쪽 아래 Q2

P, Q1이 자원을 할당 받음, Q2가 R2, R3 요청

R3는 운영체제가 할당 가능(점유), R2는 이미 사용중이라 할당 불가능(대기) => 이것을 방지하는 방법은 R3를 할당하지 않고 R2가 할당될 때 까지 대기하다 같이 할당해주는 방법 => 비효율적 이지만 가능은하다. 할당전까지 R3가 놀고 있어서 효율이 떨어진다.

 

3. 비선점(No Preemption) 방지

P는 R2을 할당 받았고 R1은 요청한 상태 -> 점유와 대기이런 상태에서 비선점이 가능한지?

 

오른쪽은 시간의 흐름

T1, T2에서 자원 할당 및 요청이 이루어짐

근데 T3에서 P는 R1를 기다려야된다. 그래서 점유와 대기조건 방지를 위해 P에 할당된 R2를 강제로 회수 

T4에선 P가 자원을 뺏겨서 Q에 자원이 할당되었다는 메시지만 남음 

그러다 Q가 종료되면 T8에서 Q가 R1을 해제

비로소 T9에서 P에 R1, R2를 할당 요청을 할 수 있다.

T10에서 할당이 된다.

 

=>이것은 가능하다. 그치만 이것도 R2가 아무도 안쓰는건데 뺏어가서 비효율적이다.

 

4. 원형대기(Cricular Wait) 방지

Deadlock이 발생되는거 보면 원형으로 wating되는 것이 보인다.

 

이것을 방지하는 법?

운영체제에서 각각의 자원에 대해 순서, 번호를 매긴다. ex) R1는 10번, R2는 12번

그리고 프로세스가 자원을 요청하면 운영체제는 자원을 할당

 

이전엔 그냥 자원 할당을 해줬다. 하지만 원형 대기를 방지하기 위해서는 자원할당 전에 자원 번호를 비교한다. 

ex) 어떤 프로세스가 하드디스크를 요청하면 하드디스크가 몇 번인지 보고 요청을 해주게된다.  만약 자원의 번호가 이전에 요청된 자원 번호보다 더 큰 번호로 요청하면 할당을 해준다. 즉 P1 프로세스가 전에 마우스를 할당 받았는데 이번엔 하드디스크를 요청하면 마우스 1번, 하드디스크 2번이라 할당을 해준다. 이런식으로 하면 지금 내가 자원 3개가 필요하면 이 요청을 한 방향으로만 해줄 수 있다. 만약 5번, 7번을 할당 받았는데 다시 1번을 요청하면 안해준다. 왜냐하면 원형이 생길 수 있기 때문이다. 오름차순, 내림차순으로 요청하면 할당을 해준다.

=> 가능하다

 

결론

4가지 조건중 3가지를 방지하면 교착상태(Deadlock)이 발생되지 않음 -> 교착상태 예방됨!

이 3가지를 못하게하면 교착상태는 막을 수 있지만 비효율적이다. 즉 성능저하가 된다.

 

-Deadlock Avoidance (회피)

예방은 deadlock이 일어나지도 않았는데 점유대기, 비선점, 순환대기의 조건을 제거해서 장치의 비효율적 사용, 시스템 성능 저하가 발생한다. 그래서 현존하는 운영체제는 예방을 사용하지 않는다.
그래서 데드락이 생길거 같은 조짐이 보이면 피하자 라는게 회피

 

어떤 시스템에 safe, unsafe가 있다. deadlock는 unsafe 상태에서만 일어난다. 데드락을 피할수 있는 방법은 safe에서 unsafe로 갈거같으면 더 이상 자원을 할당해주지 않는다.

 

회피하는 방법
1. 프로세스 시작거부

최대 요구량(현재프로세스) + 최대요구량(새로 시작할 프로세스) > 최대값
현재 운영체제의 자원은 10개고 프로세스가 6개를 쓰고 있다. 근데 앞으로 시작하는 프로세스는 5개를 요구할거 같다. 11개가 필요한데 10개밖에 없다. 이러면 아예 프로세스 시작을 하지 않겠다.
하지만 이것은 말이 안된다.

2. 자원할당의 거부
그래서 나온게 자원할당의 거부이고, 일단 프로세스 실행은 시키는데 자원을 많이 요구하면 거부하자 이게 banker's 알고리즘

회피 알고리즘에는 2가지가 있다.
1.자원할당그래프
2. 은행가 알고리즘

 

-Safe State

3개의 프로세스와 12개의 자원이 있다.
p0에 5개, p1 p2에 각각 2개씩 할당된 것을 알 수 있다.
오른쪽 그림보면 정리되어있다. p0은 5개의 자원이 더 필요하다. p1은 2개가 더 필요하다. p2는 7개가 더 필요하다.
남은 자원 3개

 

t0: 3개 남음
t1: p1에 자원할당 가능
t3: p1종료되고 4개 반납해서 자원이 5개 남음
t4: p0가 5개를 요청->할당 가능하다
t6: 실행하고 종료되면 10개 반납해서 자원개수 10개
t7: p2가 7개 요청하면 할당 가능

프로세스 요청의 순서를 safe sequence라고 한다.
따라서 모든 프로세스가 종료가능 => safe state이다.

 

-Unsafe State

위에 보면 프로세스3개, 자원 12개있다.
p0는 2개가 더 필요하다, p1도 2개 더 필요, p2는 8개 더 필요
남은 자원 1개

p0가 2개를 요청하면 할당할 수 없다.
p1도 할당할 수 없다.
p2도 할당할 수 없다.
3개가 다 요청했는데 할당을 기다려야한다 => 데드락, unsafe state라고 한다.
하지만 unsafe state라고해서 전부다 데드락은 아니다.

 

safe였는데 할당하다보니 unsafe로 바뀌는 경우
표에 상태 나타남

왼쪽 
t0에서 잔여 2개
t1에서 p2가 1개 요청하면 할당해줄 수 있다.
그러면 잔여자원 1개고 p0, p1, p5모두 요청에 할당을 못해준다. unsafe 상태

가운데
t1에서 p1이 2개 요청하면 할당가능
그러면 p1은 종료가 가능하고 4개의 자원을 반납가능
p0에는 할당이 불가능, p2도 6개 필요로해서 할당해줄 수 없다,
따라서 p1만 종료 p0, p2는 unsafe이다. safe->unsafe 상태가 되었다.

 

-교착상태 회피 알고리즘

1. 자원할당그래프(Resource Allocation Graoh Algorithm)

이것은 only one instance일 때만 사용 인스턴스 개수가 1개일 때만 사용한다. 

P1한테 R1 할당되어있고 P2는 R1한테 요청을 했었다.(과거형)

 

사진보면 실선은 했었던거 과거, 점선(claim edge)은 미래

점선은 P1이 R2를 요청 할 것이다. P2도 R2를 요청 할 것이다.라고 하면 어떻게 회피를 할 수 있는지? 

점선중 하나를 실선으로 바꿔본다. 그리고 사이클이 만들어지는지 체크한다. 만약 사이클이 만들어지면 unsafe상태가 됨

 

오른쪽 알고리즘

1. 점선을 실선으로 바꾼다.
2. 사이클이 존재하는가?
존재하지 않으면 safe상태, 존재하면 unsafe상태

safe 상태면 아직 할당하지 않고 체크만 한 것이라 자원을 할당해주면 된다. 

 

2. Banker's Algorithm

멀티 인스트턴스일때 사용
available: 잔여량

max: 최대요구량

allocation: 할당량

need: 필요량

4가지 데이터가 필요하다.

 

3명의 클라이언트가 있다. 대출을 받으려한다.
그리고 은행직원이 있다.

1번 500, 2번 500, 3번 200을 대출 받고 싶은데 은행 잔고는 1000밖에 없다. 이 사람들에게 finish라는 걸 두고 끝나면 true이다 그래서 지금은 false이다.
첫번째 여자가 500중에서 400을 신청하면 가능하다. 그러면 은행 잔고는 600이 남은, 고객 need는 100
두번째 남자가 500중에서 300을 신청하면 가능하다. 그러면 은행 잔고 300이 남음, 아직 200을 더 대출해야해서 finish가 false

 

 

 

 

첫번째 여자가 100 더 달라고 요청, 가능하다. 500 다 대출 받음, 은행잔고 200 남음, 여자는 다 대출받고나서 나중에 빚을 갚았다. 그래서 finish가 true가 되고 은행 잔고 700이된다.

 

 

 

 

 

available=잔여량, finish[i]는 i번째 프로세스의 상태, false 설정
i번째 프로세스가 안끝났고 내가 필요한 자원이 잔여량보다 작는지 물어봄
작으면 할당해줄 수 있다. 실행하고 종료되면 finish는 true 그리고 자원 반납 
이 과정을 모든 프로세스에서 반복한다. 계속 반복하다가 2번째에서 없음이되면 모든 프로세스가 끝났냐고 물어본다. 

다 true면 safe상태이다. 만약 여전히 끝나지 않은 프로세스가 있으면 unsafe

 

-Banker's 알고리즘 예제

resource 타입이 A B C 총 3개 이다. <p1, p3, p4, p2, p0> 순으로 실행하고 allocation 할당 받은 개수, max는 최대 필요 개수, need 필요한 개수, available는 남아있는 잔여량

p1, p3, p4, p2, p0순으로 실행하면?

p1: 현재 잔여량은 332, p1의 need는 122 따라서 할당 가능
할당하면 잔여량 210이다.
p1이 실행하고 종료되고 finish변수 true로 세팅, 반납해서 잔여량 532가 된다.

p3: 011을 요구하면 할당이 가능하다. 그리고 잔여량 521이다. p3도 실행하고 종료하면 finish변수 true되고 자원 반납되면 743이다. 결국 프로세스 종료 뒤에 잔여량을 알고싶으면 실행전 잔여량과 프로세스 allocation을 더하면된다.

p4: p4의 need는 431이다. 할당가능 실행하고 끝나면 잔여량은 745이다. 

p2: need는 600이고 할당가능, 종료되면 1047이 남는다.

p0: need 743이고 할당가능, 남은양은 1057

따라서 모든 프로세스 종료 및 회수되어서 safe상태이다.
따라서 p1, p3, p4, p2, p0를 safe secequence라고 부른다.

 

오른쪽 아래 표를 보면

p1이 request1=>(1, 0, 2)로 한다고 치자. 그러면 102를 할당 받아서 allocation 302, need 020이 된다. available이 332라서 할당이 가능하다. 잔여량은 332에서 230이 되었다.

이 상황에서 p0가 request0=>(0, 2, 0)을 하게된다면 어떻게 되는가? 

우선 020은 할당이 가능하다. 그래서 p0가 need가 723, allocation이 030이된다. available은 210이 된다.

 

이 상태에서 5개의 프로세스가 필요하는걸 할당해 줄 수 있는지?

P0 need가 723이다. 할당 불가능

P1 need가 020이다. 할당 불가능

P2 need가 600이다. 할당 불가능

p3 need가 011이다. 할당 불가능

p4 need가 431이다. 할당 불가능

=> 5개 모두 할당을 못해줘서 종료를 시키지 못한다. 따라서 unsafe상태이다. 따라서 Request0는 거부된다.

 

-Deadlock Detection(교착상태 탐지)

회피는 미리 계산해보고 unsafe가 될거같으면 실행하지 않는 것이다. 사실 이거도 비효율적이다. unsafe가 무조건 Deadlock으로 가는 것은 아니다.

 

교착상태 탐지
1. detection
2. recovery 
이 2개를 요즘에 사용한다.
교착상태를 내비두고 탐지가되면 복구하자라는 개념이다. 따라서 복구를 하기 위해선 탐지가 선행되어야한다.

 

교착상태 탐지 알고리즘

1. 멀티플 인스턴스

banker's 알고리즘을 거의 그대로 사용, need를 request로 바꿔서 사용

 

알고리즘이 banker's와 거의 같다.

2. 싱글 인스턴스

그래프에서 자원을 없애고 프로세스간의 사이클을 본다. 이것을 wait-for graph라고 부른다. 사이클이 존재하면 Deadlock이 발생되었음(과거형), 사이클이 존재하지 않으면 Deadlock이 발생되지 않음

 

-멀티플 알고리즘

available: 남은 자원이 0이다.
이런 상황에서 p0, p2, p3, p1, p4로 요청하면?

p0는 원하는게 없어서 종료가 가능, 남은 자원 010
p2도 원하는게 없어서 종료가능, 남은자원 313
p3는 원하는게 100은 할당가능, 종료되면 남은자원 524가된다.
p1은 원하는게 202도 할당가능, 종료되면 남은자원 724가 된다.
p4는 원하는게 002도 할당가능, 종료되면 남은자원 726이 된다.

모든 프로세스 종료되고 726자원 회수 = > 데드락이 발생되지 않았다.

 

표1상태를 기준으로 진행
p2가 001을 요청하면 p0 입장에서 할당이 가능하다. p0가 종료되고 자원을 반납하면 남은 자원 010이다.
p1은 할당을 할 수 없다.
p2도 할당이 불가능
p3도 할당이 불가능
p4도 할당이 불가능

따라서 p0만 종료되고 나머지 프로세스는 자원을 기다린다. 데드락이 발생 p1,p2,p3,p4가 데드락이다. 이렇게 데드락을 탐지한다.

 

-교착상태 복구

 

데드락을 탐지하면 이것을 풀어줘야하는데 이게 복구이다.

p1, p2, p3, p4, p5가 있다. 사이클을 형성해 데드락이 결렸다. 탐지을 했다. 

1. 프로세스 중지
1)데드락에 관련된 모든 프로세스를 싹 다 죽인다. 근데 이건 너무 출혈이 크다.
2) 다 죽이지말고 1개씩 죽여보자 p1부터 죽이고 데드락 탐지 알고리즘을 돌려본다. 안풀리면 p2 죽이고 탐지 알고리즘 돌린다. 이런식으로 하나씩 죽이는 방법이 있다. 
1개 죽였는데 풀리면 좋지만 다 죽이게되면 의미가 없다. 그래서 첫번째로 죽일 프로세스를 선택하는 것이 중요하다. 

기준
1.우선순위에 따라 죽인다. 우선순위를 낮은거부터 죽이는 것이 맞다.
2. 수행된시간, 수행될 시간, p1 p2가 있으면 p1은 10초 실행, p2는 1초 실행되어왔다. 그러면 p2를 죽이는 것이 낫다.
p1은 앞으로 10초 더 실행, p2는 1초 남았을 땐, p2을 죽이는 것이 낫다. 1초만 실행하면 프로세스를 끝낼 수 있다. 
3. 프로세스가 사용된 자원의 수, p1 10개, p2 1개 사용중이면 p2를 죽이는 것이 맞다. 왜냐면 나중에 이 프로세스를 죽이면 나중에 또 다시 실행해줘야한다. 근데 다시 시작할 때 또 10개를 확보해야한다. 그래서 p2를 선택하는 것이 맞다.


2. 자원선점(강제회수) 자원을 뺏는다.
프로세스를 죽이는거 대신 자원을 뺏는 방법
문제: starvation 기아가 발생할 수 있다. 프로세스의 자원을 뺏었는데도 데드락이 발생 근데 또 같은 프로세스 때문이다. 그렇게 1개의 프로세스 자원을 강제로 계속 회수하면 결국 프로세스 종료가 되지않는다.
이것을 해결하기 위해서 나온 방법이 자원을 뺏을 때 roll back을 구현
뺏겼지만 다시 실행하기 위해 운영체제에게 다시 자원을 요청해야한다. 근데 이전에 자원을 달라했던 요청 기록이 남아 있다. 내가 지금 몇번 재개하는 것인지 count를 기록한다. 그래서 운영체제가 count가 높은 것을 보면 프로세스 뺏는것을 면제해준다.