[운영체제] 데드락

ryun·2023년 4월 12일

운영체제

목록 보기

10/16

교착상태

시스템 안의 자원들이 각각 자원을 가지고 있으면서 다른 자원을 기다리고 있기 때문에
진행이 불가능한 상태인 데드락

P0은 A를 얻고 빼앗기고 P1은 B를 얻고 빼앗긴다
(자원은 세마포어같은 소프트웨어 자원일수도 하드웨어 자원일 수도 있다)

1번 프로세스 A, 2번은 B 가지고 안내놓으면 영원히 진행 안되는 데드락이 발생한다
데드락 원인
자원 동시충족 못할때, 가진자원 내놓지 않을 때
자원이 사용되는 절차 (참고)
자원 요청, 실제 할당, 사용, 다 썼으면 릴리즈

데드락 발생조건 4가지

Mutual exclusion
가지고잇을 때 독점적, 내어놓을 때만 쓸 수 잇다
No preemption (빼앗기지 않는다)
자원을 빼앗기면 데드락 발생 X
자원 빼앗기지 않는다 (비선점)
hold and wait
내가 가진 자원은 내어놓지 않고 가지지 못한 것을 기다릴 때 생김
비선점과 다르다
2번은 필요없으면 내어놓는데 3번은 가진건 끝까지 내어놓지 않는다
Circular wait(환형 대기)
필요한 자원들끼리 사이클 형성되면 (서로 기다리고 있으면) 데드락 발생

4가지 모두 충족해야 데드락 생긴다

데드락 방지

자원과 프로세스 관계

동그라미가 프로세스
사각형이 자원
프로세스(동그라미) -> 자원(네모): 프로세스가 자원 기다림
자원(네모) -> 프로세스(동그라미): 프로세스가 자원 점유
내부 작은 동그라미는 인스턴스

1번 자원은 2번 프로세스 가지고 있고,
2번 프로세스는 2번 자원도 가지고 있고 3번 자원도 가지고 잇다
3번은 3번 프로세스가 가지고있다

위 그래프 보고 데드락 잇는지 없는지 확인 가능
왼쪽은 싸이클이 있어서 데드락 발생
싸이클이 없으면 데드락이 아님
싸이클 있으면 데드락일 가능성이 있다
- 자원에 인스턴스가 여러 개 있으면(왼쪽) 사이클이 생겻다고 꼭 데드락은 아니다
  자원 2 개니까 하나가 데드락에 기여하지 않았다면 데드락이 아니다
- 자원 2 개고 사이클이 2 번 형성되었으면 데드락 확실
오른쪽 따라가면 사이클 만들어졌는데
자원과 인스턴스가 2개씩 있기 때문에 데드락 가능성이 있다
하지만 데드락은 아니다. 하나는 무관하게 2번과 4번 프로세스가 가지고 있다
4번이 자원 쓰고 반남할 수 있다. 그러면 반납되는 자원을 3번한테 주면 화살표 바뀌면서 사이클 사라지게 된다
사이클과 무관한 자원이 있기 때문에 데드락 X

데드락 처리 방법 4가지

1, 2번은 미연에 데드락을 방지
3, 4는 방치

1. Deadlock Prevention (가장 강력한 방법)

뮤추얼 익스클루젼 (상호배제)
배타적으로 자원을 쓴다는 조건
CPU가 자원을 공유할 수 없다
(이걸 방지할 수는 없다)
Hold and Wait
내가 가진 자원을 내어놓지 않으면서 충족못한 자원을 기다리는 그런 방식으로 인해 데드락 발생한다고 본다
1. 필요한 자원이 모두 충족될 때 받는다
  wait 상황이 안생기도록한다 => 균일하게 자원을 쓰지 않기 때문에 자원낭비 발생
2. 자원이 필요할 때 보유 자원을 다 던지고 다시 요청한다
  자원 요청할 때 다른 자원 쥐고 있으면서 요청하는걸 허용 안함
  일단 가진거 다 내놓고 요청
No Preemption (비선점)
자원을 빼앗지 않는다
자원 중에서 빼앗을 수 있는 자원과 없는 자원이 잇다
CPU나 메모리는 빼앗을 수 있는 자원
CPU는 빼앗는 스케줄링이 있었다(타이머 등)
빼앗아도 괜찮은 이유는 수행하고 있던 문맥을 세이브 했다가 복원해서 쓰기 때문에 다음에 얻었을 때 이후 시점부터 일 할 수 있다
허용되지 않는 자원인 경우 빼앗을 수 없다
노프림션의 조건이 되는 자원은 한정되어 있다
Circular Wait (환형 대기)
하나를 얻어야 다른 하나를 얻을 수 있게 순서를 두어 데드락을 방지한다
(2번 얻어야 5번 얻을 수 있게한다)
원점을 기다리는 친구가 있어서 싸이클대로 돌아갔을 때 데드락이 발생

이런 방법은 자원 이용률 저하와 기아현상 발생시키고 비효율적 방식이다
가용자원 있지만 데드락 때문에 사용하지 않기 때문

2. Deadlock Avoidance

추가적인 정보 이용해서 데드락 막는 방법

추가적인 정보
프로세스마다 내 평생 자원 얼마나 쓸지 알려져있다고 가정했을 때,
평생 사용할 자원의 양(최대치)
요청 자원을 할당했을 때, 안전한지 판단 >
안전한 경우에 한해서 할당

자원을 요청햇는데 이 자원은 왼쪽 프로세스가 가지고 있다

점선 (프로세스로부터 자원쪽으로)
프로세스가 자원을 평생 요청하는 때가 있을 수 있다 (한번 이상 잇을 수 있다)
요청하면 점선이 실선으로 바뀐다

먼저 2번 프로세스는 어느 누구도 가지고 있지 않다
2번 프로세스가 자원을 요청했을 때, 2번한테 줄 수 있다 (그림 3)
2번 자원은 2번 프로세스한테 가고, 2번 프로세스가 1번 자원을 요청했는데 1번 프로세스가 가지고 있다
(충족못한 프로세스 2번, 1번은 다 가지고 있는 상태)
1번이 반납할 수 있다고 하면 사이클이 사라지고 데드락이 아니게 된다
그런데 점선을 지금 요청해버리면 싸이클이 생겨서 데드락 발생

(당장 데드락은 아니지만) 점선까지 고려해서 자원을 줘버리면 사이클 생김

비록 가용자원이지만 위험하기 때문에 보수적으로 주지 않는다
가만히 있으면 데드락이 안생긴다

평생 2번 프로세스 자원 못얻는 것은 아니다
두번째 그림에서 1번 프로세스가 자원을 내어놓으면 2번 프로세스한테 두 개 다 줘도 사이클 안생긴다
또는 점선이 실선으로 바뀌면 줘도 싸이클 안생긴다
2번 프로세스는 놀고있는 자원이지만 안전한 상황까지 기다리게 하고 1번 프로세스는 언제든지 자원을 써서 일을하고 언젠가 프로세스 종료(가진자원 내어놓음)한 그 다음에 2번한테 주면 된다

자원당 인스턴스가 하나밖에 없는 상황에서 데드락이 생길것같으면 아예 자원 안주는 (불완전한 상태 원천봉쇄)로 데드락 막는다

자원에 인스턴스 여러개 있는 상황에서는?

테이블 형태로 만들어서 자원 할당할지 할당하지 않을지 확인

5개 프로세스 P
자원 3종류 A, B, C
각각의 인스턴스는 A 10개 B 5개 C 7개

현재 5개의 프로세스에 A, B, C가 어떻게 할당되었는지 보여줌

가용자원
A는 10 - (2 + 3 + 2) = 7
평생 최대로 쓸 자원(Max)을 알고있다

그 중에 이미 할당된 자원은
7 5 3 에서 0 1 0을 빼서 7 4 3
평생 최대 요청할 양에서 현재 할당된 양을 빼면 추가로 요청할 수 있는 양이 표시(맨 오른쪽 Need)

만약 이 상황에서 0번 프로젝트가 C를 하나 요청한다면 C는 가용자원으로 2개 남아있음
C 요청햇을 때 자원이 여유 있더라도 불안정한 상황이 생길 수 있으면 주지 않는다

가용자원은 3 3 2인데
추가 요청은 7 4 3
만약 0번 프로세스가 평생 최대 요청 자원을 지금 요청해버리면 가용자원을 가지고 충족이 되지 않는다
최악의 경우를 가정해서 할당된 자원 내어놓으면 데드락 발생
최대로 요청했을 때 요청이 여유있는 가용자원으로 처리되지 않으면 요청이 받아들여지지 않음
0번 프로세스 요청은 아무것도 안받아들여진다

1번은?
가용자원 다 가져가더라도 추가요청을 할 일 없음
언젠가는 종료가되고 할당 자원은 다 가용자원으로 내어 놓을 것이다

2번은?
추가요청 A는 6개
여유분 3개밖에 없기 때문에 받아들여지지 않는다

가용자원 확인해서 안전한 상태를 유지
안전하다는 의미는 가용자원만 가지고 프로세스 존재할 수 있는 시퀀스 존재하면 안전
가용자원 내에서 줄 수 있다면 안전
3 3 2 인데 1 2 2 요청하면 다 줄 수 잇음
종료되면 반납됨
A 2개가 추가로 반납
5 3 2 로 최대요청 처리할 수 있는게 3번 요청 0 1 1 그러면 3번 요청 다 줘서 본인 원하는 최대자원받아서 종료
그럼 또 내어놔서 3 2 2 에서 3+2+2 3+1 2+1
7 4 3
가용자원으로 처리가 돼서 0번도 처리

프로세스 종료되면서 점점 안전해지는 시퀀스 존재
시스템 상태는 세이프하다 라고 말할 수 있다
언제나 안전할 수 있게 자원을 할당한다
그 기준은 추가 요청자원과 가용자원 고려

데드락은 생기지 않고 세이프한 상태만을 유지

자원이 있다고 그냥 주는게 아니라 추가요청이 자원으로 충족되면 받아들인다

4. Deadlock Detection and recovery (생기든 말든)

시스템 안에 데드락이 생겼는지 판단
- 자원당 인스턴스 1개 있으면 그래프 통해서 데드락 생겼는지 확인
- 자원당 인스턴스 여러개 있으면 뱅커스 알고리즘처럼 테이블 만들어서 지금 상황이 데드락 맞는지 판단

좌측 그래프
1번 프로세스가 자원을 기다리고 있고, 그 자원은 2번에게 할당되어 있고 2번은 3번, 4번 5번을 기다리고 있는 등의 상태
싸이클이 있기 때문에 100% 데드락 발생
싸이클이 두개이므로 데드락이 양쪽에서 발생

자원할당 그래프를 간단하게 하자면 자원을 빼고 프로세스만 가지고 그래프를 만들 수 있다
이 프로세스가 다른 프로세스를 기다린다고 만들어 버릴 수 있다

데드락 디텍션에서 wait-for 그래프를 만들어서 데드락이 생겼는지 빨리 찾을 수 있다

자원당 인스턴스 여러 개 있는 상황

예제
프로세스 5개
자원 3종류
(평생 최대자원 얼마나 쓸지 관심사가 아니다)
여유자원이 있으면 무조건 준다 => 데드락이 아니다
Allocation
프로세스한테 할당된 자원
모든 가용자원이 프로세스한테 할당되어 있다

1번 프로세스는 A 두개를 가지고 있다
A 2개, C 2개를 요청 > 가용자원이 없기 때문에 자원을 줄수 없다
하지만 가용자원이 생길 때 줄 수 있게 된다

자원이 생기는 시기
요청 안 받은 프로세스들이 자원 내어놓아서 가용자원이 되면 그걸 전달해줄 수 있다
시퀀스
아무것도 요청 안한 프로세스가 가진 자원을 모아서 요청된 자원을 줄 수 있는 방법
자원을 다 줘서 할당된 일을 하고 내어놓는다고 가정
모든 프로세스가 요청한 것들이 가용자원 만들어서 끝까지 처리가 되면 데드락 상태가 아니다
데드락 디텍션과 뱅커스 알고리즘의 비교
- 뱅커스 알고리즘
  - 프로세스에 대해 최악의 자원요청 한다고 가정
  - 자원 있어도 보수적
- 데드락 디텍션
  - 낙관적으로 생각
  - 자원 안준 친구들은 자원을 내어놓을 것이라고 생각
  - 꼭 내어놓는다는 보장은 없다
  - 요청에 없는 프로세스가 할당된 자원 내어놓는다고 일단 가정
    이 자원까지 포함해서 요청을 처리할 수 있는 시퀀스가 존재하면 데드락이 아니다

2번 프로세스가 C를 하나 요청해 버리면
자원 요청 안된 프로세스는 0번 뿐
B를 하나 내어놓는다고 해도 나머지 프로세스 중에서 처리할 수 있는 프로세스 한 개도 없다
이와 같은 상황이라면 데드락

세이프 시퀀스
각 프로세스를 가용자원만 가지고 처리할 수 있는 프로세스가 있는지 찾는다
현재 가용자원 가지고 프로세스의 최대 자원요청을 받아들일 수 있는 프로세스가 있으면 이를 찾는다
평생 필요한 것을 얻었으면 종료
남은 자원을 반환해서 가용자원에 추가한다
위가 반복되면서 점차 가용자원이 늘어난다
시퀀스가 찾아지면 지금 세이프 시퀀스가 있다 > 지금 상태는 세이프하다
세이프 시퀀스는 현재가 안전하다는 의미

뱅커스 알고리즘은 항상 세이프

데드락 리커버리

리커버리
- 데드락에 연루된 모든 프로세스를 종료
- 데드락에 연루된 프로세스를 하나씩 종료 사라지는 것을 확인하는 방법
  - 데드락이 안풀리면 하나씩 추가로 종료
죽이지 않으면서 자원 빼앗는 방법
- 데드락에 연루된 프로세스를 골라서 그 친구로부터 자원을 빼앗아버리면 데드락이 없어진다
- 희생양 정하는 방법
  비용이 적게드는 프로세스
  다시 리스타트 해봤더니 그 프로세스가 또 자원을 가져가서 또 생김
  또 뺏고 반복 동일한 프로세스 희생되고 데드락이 생기고 이것도 비효율적
  동일한 프로세스가 계속 희생되면서 데드락이 생기면 비효율적
  * 비용도 중요하지만 롤백 횟수도 중요 > 다른 프로세스 고려