이전 글에서 OS가 공유 자원을 동기화하는 방법에 대해 알아보았다. 동기화 하기 위해 lock을 사용하는데 이때 발생하는 대표적인 문제점인 Deadlock에 대해서 알아보자.
Deadlock
Deadlock : 스레드들이 서로가 점유한 자원을 사용하기 위해 무한정 대기하는 상태
Deadlock 발생 조건
- 비선점 : 다른 스레드가 사용하고 있는 자원을 강제로 빼앗아올 수 없음
- 상호 배제 : 공유 자원에 하나의 스레드만 접근 가능
- 점유와 대기 : 자원을 추가적으로 얻으려고 할 때, 기존의 자원을 계속 들고 있는 것
- 원형 대기 : 스레드들이 원하는 자원이 서로 물리고 물려 원형 관계를 이루는 상태
이 네가지를 모두 충족해야 Deadlock이 발생한다.
Deadlock 해결 방법
Prevention
위의 네 가지 조건 중 하나라도 만족하지 않게 하여 Deadlock이 발생되지 않도록 하는 방법
1. 원형 대기 예방 : 모든 스레드에서 적용되는 락을 얻는 순서를 지정한다!
2. 점유와 대기 예방 : 필요한 모든 lock을 한번에 얻도록한다!
3. 비선점 예방 : 얻지 못하는 lock이 존재한다면, 오류를 발생시켜 나중에 시도하게 만든다
=> 문제점 : livelock : lock을 얻고 해제하는 일만 계속 반복하는 현상 => livelock은 작업 사이에 지연 시간을 줘서 해결한다
4. 상호 배제 예방 : 뭔가 말이 안맞는 느낌, lock을 쓰는게 결국 상호배제를 목적으로 하는 것이 아닌가?
=> 하드웨어 명령어를 통해서 원자적으로 실행되게 한다. => 상호 배제를 고려할 필요가 없게됨 (lock을 안써도됨)
=> 하지만 이렇게 될 경우, 자원 사용에 있어 효율이 굉장히 떨어져 잘 사용하지 않는 방법이다
Avoidance
- 서로 같은 공유 자원을 사용하는 스레드는 같은 CPU를 사용하도록 한다! => load balancing에 문제가 생긴다. => 특정 CPU에만 실행되어야할 스레드들이 몰릴 수가 있음!
- Bnker's Algorithm
- 최악의 경우를 기준으로 하여 Deadlock을 피한다
- 각 프로세스는 자신이 사용할 최대 자원의 수를 OS에게 알려준다 -> 이를 통해 safe/unsafe 판단
- 가용가능한 자원의 수보다 크거나 같은 프로세스의 기대 자원이 있다면 -> safe!!
Avoidance 문제점
1. Process가 사용할 모든 자원을 미리 선언해야한다. -> 미리 알고 있어야 avoidance가 가능
2. 시스템의 전체 자원 수가 고정되어야함
3. 자원 낭비
4. 자원을 요청할 때마다 확인하는 과정의 비용이 매우크다
Detect & Recover
-> 그냥 deadlock이 발생하는 스레드를 발견한다면 kill한다.
-> deadlock이 많이 발생하는 시스템에서 주로 채택
Ignore
-> Deadlock이 발생하지 않을 것처럼 동작한다.(무시한다)
-> 놀랍게도 대부분의 OS에서 사용한다.
-> Deadlock을 handling하는 것이 load가 너무 크기 떄문에!
