[운영체제 공룡책] 8. Deadlock
반응형
데드락의 이해
8.1 System Model
deadlock
: 동일 집합 내에 프로세스들이 wait 상태에서 빠져나가지 못하는 상태 (해당 스레드가 요청한 리소스가 다른 프로세스나 스레드에 의해 자원이 점유되었기 때문에 wait 상태에서 다시 상태가 변하지 않음)
3.2 Deadlock in Multithreaded Applications
- 스레드가 자원을 사용하는 과정 : Request - use - Release
- use 단계가 크리티컬 섹션으로 볼 수 있음
- use 섹션에 여러 개의 자원, 인스턴스가 들어갈 수 있음
3.2 Deadlock Characterization
- Deadlock 발생의 네 가지 조건
- Mutual Exclusion 상호 배제 : 한 번에 여러 개의 스레드가 자원을 점유할 수 있다면 데드락이 발생하 지 않겠지. 자원 획득을 위해 기다릴 이유가 없어지니꽈!
- Hold and Wait 점유 대기
- No preemption 선점 불가 : 중간에 다른 스레드가 자원을 강제로 빼앗을 수 있다면 데드락이 발생하지 않겠지
- Circular Wait 순환 대기
- Resource-Allocation Graph : 실제로 구현이 어려우니 데드락 상황을 잘 이해하기 위해 만드는 그래프
- 데드락 발생
- 순환이 되지만 데드락 발생안함
- 중요한 관찰
- Resource-allocation 그래프를 보니까 싸이클이 없으면 절대 데드락 상황에 빠지지 않는 다는걸 깨달음!
- RAG를 통해 싸이클을 어떻게 활용하느냐는 나중에 ㄱㄱ
- 그래서 데드락 어떻게 다뤄야해?
- 그냥 무시하자
- 어떤 방법을 쓰던지 아예 방지(prevent, 근데 거의 불가능)하거나 avoid(비싸지만
Banker’s Algorithm
으로 이용 가능) - 데드락 내버려두고 detect(모니터링)와 recover 진행
8.5 Deadlock Preventiom
- Deadlock Prevention (데드락 방지)
- 네 가지 조건이 모두 충족되어야 데드락이 발생하니까, 적어도 한 개의 조건이 발생하지 않도록 막아보면 되지 않을까? 라는 관점으로 접근
- Mutual Exclusion 상호배제를 막아보자 : 모든 자원을 공유 가능하게 하면 어떨까? 불가능데스요
- Hold and Wait : 쓰레드가 자원을 요청할 때 다른 스레드가 점유하고 있으니 문제가 되는 거니까, 이 부분을 막아보면 어떨까? 내가 어떤 자원에 점유하고 싶을 때에는 갖고 있는 자원을 모두 내려놓는방식으로! 근데 너무 번거롭고 현실적이지 못하다요
- No preemption 선점불가 : 어떤 스레드가 어떤 리소스 점유하고 있는데 다른 스레드가 강제로 선점 가능하게 만든다면 어떨까? 더 심한 문제가 발생할 수 있어서 현실적으로 좋은 방법이 아님
- Circular Wait 순환대기 : 떄떄로 practical한 솔루션. 하지만 위 세 개 보다는 현실적이고 실현가능한 아이디어로 순환대기를 막아서 데드락을 방지할 수 있다!
- 자원에게 순서를 부여하고, 자원 접근에 요청할 때 내가 점유하고 있는 리소스들보다 번호가 높은 것만 요청하도록 함
- 대신 starvation의 위험은 높아짐
- 근데 이렇게 grand lock(?)을 사용 데드락을 완전히 방어할 수는 없다
- Transaction 원자
여튼 Deadlock 을 방지하는 것은 비싸고 비효율적이다. 우리는 피하자! Avoid 하는 유우명 알고리즘 Banker’s 알고리즘에 대해 배우자.
데드락과 뱅커 알고리즘
8.6 Deadlock Avoidance
- 데드락 방지(prevention)은 단점이 더 많았고(사이드 이팩트, CPU 사용률 저하), 그나마 조치 가능한 조건은 순환 대기였음
- Deadlock Avoidance
- future deadlock : 미래에 발생 가능한 데드락에 대해 생각해보자
- 각 스레드(프로세스) 어떻게 요청할 지 안다면 그 요청이 데드락 발생 가능성이 있는지 없는지 알 수 있겠지. 만약 데드락 발생 가능성이 있다면 요청을 거절하면 된다
- 선행 지식
- 어떤 알고리즘으로 데드락 상태에 들어가지 못하게 아예 막아버리자!
- maximum number of resources : 스레드가 요청할 수 있는 최대의 자원 개수?
- state of resource allocation
- number of available resource : 가용한 리소스의 수
- numbe of allocated resource : 점유되고 있는 리소스의 수
- maximum demands of the threads : 스레드가 앞으로 요구할 리소스의 최대 수
- Safe State 안전상태
- 어떤 시스템, 상태가 안전하다는 것(=deadlock free)은 자원을 각 스레드에게 멕시멈까지 제공해줄 수 있다는 것임
- 안전 상태에 놓일 수 있는 스레드의 실행 순서가 존재함. 그걸 safe sequence라고 칭함
- Basic facts
- unsafe 상태라 하더라도 데드락이 발생할 수도 있고, 안할 수도 있음
- 근데 모든 unsafe가 데드락 발생 가능성이 있기 때문에 아예 safe state에만 머무리게 하자!는게 avoidance의 컨셉임
- safe state라면 요청을 granted 해주고, 아니라면 rejected
- 스레드 입장에서는 자원에 접근 요청하기 전에 커널에게 안전한 상태인지 항상 물어보는 거임
- RAG(Resource-allocation graph)
- 좌측 그래프는 T1, T2가 R2에 자원을 접근해도 되는지 요청한 상태이고, 아직 R2 자원을 할당한 애가 한명도 없기 때문에 T2은 R2에 접근하게 된다.
- T2가 R2에 접근 허락을 얻어 할당한 모습이 우측 그래프이다. 이 때에는 R2가 T2에게 할당되어 있기 때문에, T1이 R2 자원 요청 시 대기하게 되고 T2가 자원을 릴리즈 하게 되면 그 이후 재요청하여 접근이 허락되게 된다.
- Banker’s Algorihm
- RAG는 multiple instances일 때에는 사용할 수 없기 때문에 은행원 알고리즘을 사용함
- 은행원 알고리즘은 RAG보다 효율이 떨어지고 복잡하다
- 알잘딱 설명 블로그
- 은행원 알고리즘의 데이터 구조
- n : 스레드의 개수
- m : 리소스의 타입의 수
- available : 가용한 리소스 타입의 개수를 가지고 있는 벡터
- max : 각 스레드가 앞으로 요청할 리소스 인스턴스의 최대 개수
- allocation : 각 스레드에게 할당된 리소스의 수
- need : 각 스레드가 앞으로 요청할 리소스의 수
- 데이터 구조의 예시
- Available[m] : 만약 Available[j] == k 라면, Rj 리소스의 K 개의 인스턴스가 가용하다는 뜻
- Max[ n x m] : Max[i][j] == k라면, Ti 스레드가 최대 Rj 리소스의 k개의 인스턴스를 요청할 것이라는 뜻
- Allocation[n x m] : Allocation[i][j] == k라면, Ti 스레드가 현재 Rj 리소스의 k개의 인스턴스를 점유하고 있다는 뜻
- Need[n x m] : Need[i][j] == k, Ti가 Rj 리소스에게 k개의 인스턴스만큼 더 요청할 수도 있다는 뜻
- 각 알고리즘은 이해하기 어려우니까 문제를 풀면서 공식을 확인해보면서 공부해라
- Safety Algorithm(== 뱅커스 알고리즘) : 이 시스템 스냅샷이 세이프하냐 안하냐! (2) 할당할 수 있는 조건이 존재하는지 확인, 그리고 (3) 존재한다면 할당하고 (4) 할당이 되었으면 종료 가능하다고 뜨루함! 할당한 그 순서가 safe sequence가 되는 거임
- Resource-Request Alhorithm : (1) 요청이 주어졌을 때, 내가 필요하는 것 보다 같거나 작아야하고 (2)가용한 자원보다 같거나 작아야함! (3) 충족한다면 다시 safety 알고리즘 돌려보고 충족하면 허락해주고 아니면 리젝시킴
8.7 Deadlock Detection
- prevent나 avoid를 해주지 않으면 데드락이 발생할 수 있음
- 근데 리소스 접근 요청때마다 검증해야함. 그리고 멀쩡한 요청도 거절될 수 있어서 시스템에게 부하가 될 수 있음! 데드락이 걸리면 크리티컬한 시스템일 경우에만 이렇게 방어나 방지를 함
- 실생활에서는 그냥 데드락을 허용해주고 데드락 상태가 되었는 지를 감시 determine하고, 만약 데드락이 발생했으면 알고리즘을 이용하여 데드락 상태를 recover 해주자!
- 데드락 모니터링 및 회복 - 싱글 인스턴스
- Signle Instance 일 때에는 wait-for graph(RAG랑 똑같은데 약간 변형된거) : 주기적으로 어떤 알고리즘을 돌려서 싸이클이 생겼는지 확인
- wait-for graph
왼쪽 RAP 처럼 자원이 필요없음. 어떤 스레드가 어떤 스레드에게 의존적인지 그리는 것임!
그래서 싱글인스턴스에서 사이클 이펙션을 그리는 것은 wait for graph를 그리는 것과 똑같다
- 데드락 모니터링 및 회복 - 여러 개의 인스턴스
- 이 때에는 은행원 알고리즘과 유사한 것을 적용한다!
- 은행원 알고리즘 때에는 이 요청이 데드락을 유발하냐 안하냐를 봤었는데, 지금은 그냥 내버려두기로 한거잖아! 요청을 그대로 받아들여서 은행원 알고리즘을 돌리면 됨. 그리고 초기화 부분과 판단 부분이 조금 다르다.
- 이 때에는 은행원 알고리즘과 유사한 것을 적용한다!
8.8 Recovery from Deadlock
- 일단 detection이 prevention, avoidance보다 훨씬 효율적인 것은 알게 됐다
- 얼마나 자주 데드락이 일어나느냐에 따라서 detection algorithm을 자주 수행시킴. 근데 굉장히 자주 일어나면 시스템 호출이 잘못된거라 의심해봐야함
- 스레드의 개수에 따라서 데드락 발생 확률이 높아질 수 있음.
- 모든 요청에 detection 알고리즘을 돌린다면 오버헤드가 발생함. 적절한 주기로 돌려야함. 만약 1년에 한번 정도 데드락이 발생할 거 같으면 하루에 한번이나, 1개월애 한 번 정도 돌려서 데드락 싸이클을 발견해주는게 좋다
- 만약 데드락이 발생하면 알람을 오게 하거나 바로 회복 시켜서 시스템이 문제없이 돌아가게 할 수 있따. 아래처럼 두 가지 방법이 있겠다
- Deadlock Recovery
- Process and Thread Termination : 데드락을 발생시킨 스레드 집합을 재실행 시키거나 혹은 한 두 개 씩 죽여보고 데드락 싸이클이 해소되는 지 봄
- Resource Preemption
- selecting a victim : 제일 최근에 시작된, 저렴한 리소스를 강제로 빼앗아서 요청한 스레드에게 줘버림
- Rollback : 그리고 프로세스 롤백시켜서 safe state로 오는 걸 확인한 다음에 restart 시킴
- Starvation : 대신 기아 상태가 발생할 수 있다
교수님 정리
- Deadlock
- prevention 데드락 발생 4가지 조건 중 하나를 막자. 순환대기를 막음
- avoidance
- 싱글인스턴스일 때 : RAG
- 멀티인스턴스일 때 : 뱅커스 알고리즘
- Detection
- 싱글인스턴스일 때 : RAG 변형하여 자원 제거하고 스레드 간의 의존성을 확인함
- 멀티인스턴스일 때 : 뱅커스 알고리즘 적용(조금 변형)
반응형
'엔지니어링 > 개발배움터' 카테고리의 다른 글
[운영체제 공룡책] 10. Virtual Memory (0) | 2022.09.05 |
---|---|
[운영체제 공룡책] 9. Main Memory (0) | 2022.08.29 |
[운영체제 공룡책] 7. Synchronization Examples (0) | 2022.08.15 |
[운영체제 공룡책] 6. Synchronization Tools (0) | 2022.07.30 |
[운영체제 공룡책] 5. CPU Scheduling (0) | 2022.07.24 |
댓글
이 글 공유하기
다른 글
-
[운영체제 공룡책] 10. Virtual Memory
[운영체제 공룡책] 10. Virtual Memory
2022.09.05 -
[운영체제 공룡책] 9. Main Memory
[운영체제 공룡책] 9. Main Memory
2022.08.29 -
[운영체제 공룡책] 7. Synchronization Examples
[운영체제 공룡책] 7. Synchronization Examples
2022.08.15 -
[운영체제 공룡책] 6. Synchronization Tools
[운영체제 공룡책] 6. Synchronization Tools
2022.07.30