✅ 데드락(Deadlock)
데드락이란 일련의 프로세스들이 서로 가진 자원을 기다리며 block 되어 더 이상 진행될 수 없는 상태를 의미한다.
(앞서 세마포어에서 발생할 수 있던 문제)
✔️ 프로세스의 자원 사용 절차
- Request : 자원을 요청하고, 만약 다른 프로세스가 자원을 사용하고 있어 받을 수 없다면 대기
- Allocate : 자원을 받는다.
- Use : 프로세스가 받은 자원을 사용한다.
- Release : 프로세스가 자원을 놓아준다.
데드락은 모든 프로세스가 Request 상태가 되어있는 상황
✅ Deadlock Characterization
✔️ Deadlock 발생 조건
Deadlock이 발생하기 위해선 다음 4가지 조건을 만족해야 한다.
- Mutual exclusion (상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
- Hold and wait (보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유하고 있는 자원을 놓지 않고 계속 가지고 있다.
- No preemption (비선점)
- 프로세스는 OS에 의해 강제로 자원을 빼앗기지 않는다.
- Circular wait (순환 대기)
- 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.
✔️ 프로세스의 사이클
Resource-Allocation Graph로 자원이 어느 프로세스에 할당되고 어느 자원을 얻으려하는지 나타냄
- R은 자원이고 P는 프로세스일 때, 자원 내 동그라미는 자원의 개수
- 자원 → 프로세스로 향하는 간선은 해당 자원을 프로세스가 보유중이라는 의미
- 프로세스 → 자원으로 향하는 간선은 프로세스가 해당 자원을 요청했다는 의미
💡 그래프에 사이클(Cycle)이 없다면 Deadlock이 아니다. 반면 사이클이 있다면 Deadlock이 발생할 '수' 있다.
- 정확히 말하면,
자원 당 하나의 인스턴스만 있는 경우엔 Deadlock이고, 여러 인스턴스가 존재하는 경우엔 Deadlock일 수도 있고 아닐 수도 있다.- 자원당 하나의 인스턴스만 있는 경우에는 데드락
- 여러 인스턴스가 있는 경우에는 데드릭일 수도 있고 아닐 수도 있음
- 위 그림에서 왼쪽은 데드락이지만, 오른쪽은 데드락이 아님
✔️ Deadlock문제를 해결하기 위한 방법
- 예방하는 방법(Prevention)
- Deadlock이 발생하지 않도록 피하는 방법(Avoidance),
- 발생했을 때 처리하는 방법(Detection and Recovery)
- 무시하는 방법(Ignorance)
이 각각의 방법에 대해서는 아래에서 자세히 설명하겠다.
✅ Deadlock Prevention
자원을 할당할 때 데드락의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 방식이다.
✔️ Mutual Exclusion
공유 가능한 파일은 Mutual Exclusion이 필요가 없다.
예를 들어, Read-Only 파일은 언제나 공유가 가능한 자원이다.
하지만 모든 자원이 공유 가능한 상황은 불가능하다. 어떠한 자원들은 그 자체로 공유가 불가능하다.
예를 들어, Mutex Lock은 여러 스레드가 동시에 공유할 수 없다.
✔️ Hold and Wait
Hold and Wait를 방지하려면 스레드가 특정 자원을 요구할 때, 다른 자원을 점유하고 있지 않음을 보장해야 한다.
이를 해결하기 위해 두 가지 방식을 생각해볼 수 있다.
- 스레드가 필요한 모든 자원을 점유할 수 있을 때만 자원을 점유한다.
- 스레드가 다른 자원을 요청하려면 점유 중인 자원을 모두 놓아야 한다.
위 방식은 자원 사용 효율성이 낮고 Starvation 확률이 커진다.
따라서 현실성이 낮다.
✔️ No Preemption
Preemption을 보장하기 위해 아래와 같은 프로토콜을 사용할 수 있다.
- 한 스레드가 특정 자원들을 점유하고 있고, 다른 자원을 요청할 때 해당 자원을 바로 점유할 수 없다면 해당 스레드는 이미 점유하고 있는 자원들에 대한 소유권을 잃는다.
- 즉, 다른 스레드가 바로 해당 스레드가 점유하고 있던 자원들을 사용할 수 있게 된다.
- 자원을 뺏긴 스레드는 다시 작업에 필요한 모든 자원을 점유할 수 있을 때 다시 시작된다.
이러한 프로토콜은 CPU의 레지스터나 데이터베이스의 트랜잭션처럼 자원의 저장과 복구가 용이할 때 많이 사용된다.
하지만 데드락이 자주 발생하는 뮤텍스 락이나 세마포어가 많이 사용되는 환경에는 적합하지 않다.
✔️ Circular Wait
4가지 방식 중 가장 실용적이다.
- Total Ordering on lock acquisition
- 모든 리소스에 번호를 부여한 후, 프로세스들이 오름차순으로 자원을 요구한다면 데드락은 발생하지 않는다.
- Partial Ordering on lock acquisition
- 실제 시스템에선 굉장히 많은 자원과 락의 종류가 존재하고, 모든 락에 대해 Total Ordering을 하는 것은 쉽지 않다.
- 리눅스의 메모리 맵핑이 이와 같은 방식을 사용한다.
하지만 Total Ordering과 Partial Ordering 방식 모두 복잡한 시스템에서 우선 순위를 매기는 것이 쉽지 않고, 조건이 추가되는 경우 전부 새로 번호를 다시 지정해야 한다.
💡 미리 데드락을 방지하는 방법은 효율성과 처리량을 감소시키고 Starvation이 발생할 수 있음
✅ Deadlock Avoidance
스케줄링을 이용하여 데드락을 방지하는 방법으로, 데드락이 발생할 가능성이 있는 경우에 아예 자원을 할당하지 않는 방식이다.
- 단순하게는 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
✔️ 데드락 회피의 전제
데드락의 발생 가능성 알기 위해서 세 가지 정보와 한 가지 가정을 전제로 해야함
가정
프로세스는 필요한 자원을 모두 사용하고 한 번에 해제한다*
정보
1. 각 자원의 가용 인스턴스 개수
2. 모든 프로세스마다 보유하고 있는 자원 개수
3. 모든 프로세스마다 필요한 자원의 총 개수
예를 들어 프로세스 A가 현재 세 개의 자원을 사용하고 있고 필요한 자원의 개수가 5개라면, 두 개의 자원을 추가로 할당받아야 다섯 개의 자원을 해제할 수 있다는 것
위 가정을 바탕으로 Safe State와 Unsafe State라는 개념이 사용됨
💡 Safe state
- 시스템 내의 프로세스들에 대한 Safe Sequence가 존재하는 상태
- 데드락이 발생하지 않는 경우가 단 하나라도 없는 상태
💡 Safe Sequence
- 프로세스의 sequence <P1, P2, …, Pn>이 있을 때, Pi의 자원 요청이 가용 자원 +모든 Pj의 보유자원에 의해 충족되는 경우 sequence를 safe하다고 말함.
- 데드락이 없는 프로세스 실행 순서
시스템이 Safe state에 있으면 데드락이 발생하지 않고 Unsafe state에 잇으면 데드락이 발생할 수 있어 시스템이
Unsafe state에 들어가지 않는 것을 보장하는 것이 Avoidance의 핵심이다
회피 알고리즘
자원의 필요한 인스턴스의 개수에 따라 두 경우의 Avoidance 알고리즘이 존재
- 각 자원 타입마다 하나의 인스턴스가 존재하는 경우 자원 할당 그래프 알고리즘을 사용
- 여러 인스턴스가 존재하는 경우 Banker’s 알고리즘(앞서 배움)
✔️ 자원할당그래프(Resource Allocation Graph Algorithm)
- 점선으로 표시된 간선은 프로세스가 자원을 미래에 요청할 수 있음을 의미
- 그리고 해당 자원을 요청하는 경우 실선(Request edge)으로 바뀌게 된다.
- 자원을 할당받으면 방향이 반대인 간선(Assignment edge)이 된다.
- 만약 자원을 다 쓰고 반납하게 되면 다시 Claim edge로 바뀐다.
Deadlock를 피하는 방법은, Request edge가 Assignment edge로 변경될 때 점선을 포함하여 사이클이 생기지 않는 경우에만 요청된 자원을 할당한다.
💡 사이클이 없으면 데드락도 없음이 보장된다. 하지만 사이클이 있으면, 데드락은 있을 수도 있고 없을 수도 있다.
✔️ 은행원 알고리즘(Banker's Algorithm)
모든 프로세스가 필요로 하는 자원의 최대치를 미리 파악하고, 이를 고려하여 자원 할당한다.
- 여러 인스턴스가 존재하는 경우엔 사이클만으로 판단할 수는 없다.
Banker's Algorithm은 dijkstra가 고안한 알고리즘이며, 이는 프로세스가 자원을 요청할 때마다 수행한다.
이때, Safe state를 유지할 수 있는 요구만을 구락하고 불안정한 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 거절한다.
가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 자원들을 다시 반납한다.
기본적인 개념은, 자원을 요청할 때 safe 상태를 유지하는 경우에만 할당
- 즉, 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스만 선택하여 수행한다. 만약 그런 프로세스가 없다면 unsafe 상태인 것
- 할당받은 프로세스가 종료되면 모든 자원을 반납하고, 모든 프로세스가 종료될 때까지 이 과정을 반복
단점
- 할당할 수 있는 자원의 수가 일정해야 함
- 사용자 수가 일정해야 함
- 항상 불안정 상태를 방지해야 하므로 자원 이용도가 낮음
- 최대 자원 요구량을 미리 알아야 함
- 프로세스들은 유한한 시간 안에 자원을 반납
✅ Deadlock Detection and Recovery
데드락 Detection을 통해서 데드락을 감지하고 Recovery 알고리즘으로 데드락을 회복하는 방식이다.
- Deadlock이 발생했는지는 Deadlock을 미리 회피하는 방법과 유사하게 확인할 수 있다.
- 그래프를 통해서 사이클이 생겼는지를 확인하거나, 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스가 존재하지 않는다는 것을 이용하여 확인할 수 있다.
✔️ Detection
Wait-for-Graph
- 자원의 인스턴스가 하나일 때는 Wait-for-Graph를 사용
- 프로세스끼리 자원을 반납하는 것을 기다리는 상황만 표현
- 단일 인스턴스이기 때문에 싸이클이 형성되어 있으면 데드락으로 판단한다.
✔️ Recovery
데드락을 회복하는 방법은 다음과 같다.
1. 프로세스를 강제로 종료시키는 방법
1. 데드락에 걸린 프로세스를 모두 종료한다.
- 데드락을 확실히 없앨 수 있지만 손실이 크다.2.데드락 사이클이 깨질 때까지 프로세스를 하나씩 종료한다.
- 프로세스를 하나씩 종료할 때마다 데드락 검사 알고리즘을 수행하므로 오버헤드가 크다.
- 프로세스를 하나씩 종료하는 경우, 어떤 프로세스를 먼저 종료해야 하는지 고려할 사항이 많기 때문에 정하기가 어렵다. 아래와 같은 사항들을 고려해야 한다.
- 프로세스가 파일을 수정 중이었다면 파일의 온전함을 보장할 수 없다.
- 또한 프로세스가 뮤텍스 락을 획득하고 공유 자원을 점유한 상태라면 시스템은 락을 해제해야 하며 공유 자원의 무결성을 보장할 수 없다.
💡 프로세스 종료시 고려 사항
- 프로세스의 중요도
- 프로세스가 얼마나 오래 실행됐는가
- 얼마나 많은 자원을 사용했는가
- 프로세스가 작업을 마치기 위해 얼마나 많은 자원이 필요한가
- 프로세스가 종료되기 위해 얼마나 많은 자원이 필요한가
- 프로세스가 batch인가 interactive인가
- 프로세스가 작업을 완료하기 위해 자원을 얼마나 더 사용해야하는지
- 얼마나 더 많은 프로세스가 종료되어야 하는지
2. 우선순위 선점(Resource Preemption)
프로세스의 자원을 뺏어 선점하는 방식으로 세가지 이슈가 있음
- 희생 프로세스 선정
- 희생 비용을 최소화하기 위해 어느 프로세스의 자원을 뺏을지 결정
- 위에서 설명한 어떤 프로세스를 종료할 것인지와 마찬가지로 여러 사항들을 고려해야 한다.
- 롤백
- 어떤 프로세스로부터 자원을 뺏어오면 자원을 뺏긴 프로세스는 나중에 safe state로 롤백하고 다시 재실행하거나 처음상태로 되돌림
- 기아 현상
- 우선순위의 기준에 따라 기아 현상이 발생할 수 있어 가중치를 부여하여 우선권을 부여하도록 해야 함
- 롤백된 횟수를 저장함으로써 해결할 수 있음
- 따라서 프로세스별로 자원을 빼앗길 수 있는 횟수에 제한을 두어야 한다.
💡 기아현상(Starvation situation)
우선순위 기반의 스케줄링에서 특정 프로세스가 계속해서 낮은 우선순위로 스케줄되어 실행 기회를 얻지 못하고 기아 상태에 빠지는 상황이다.
✅ Deadlock Ignorance
Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식이다.
- 그 이유는, Deadlock이 매우 드물게 발생하기 때문에 Deadlock에 대한 조치 자체가 더 큰 오버헤드일 수 있기 때문이다.
따라서 만약 시스템에 Deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처한다.
이 방식은 UNIX, Windows 등 대부분의 범용 운영체제가 채택하는 방식이다.
💡Volatile 키워드
- 동시성 프로그래밍에서 발생할 수 있는 문제 중 하나인 가시성 문제를 해결하기 위해 사용되는 키워드이다. 가시성 문제는 여러 개의 스레드가 사용됨에 따라, CPU Cache Memory와 RAM의 데이터가 서로 일치하지 않아 생기는 문제를 의미한다.
- volatile 키워드를 붙인 공유 자원은 RAM에 직접 읽고 쓰는 작업을 수행할 수 있도록 해준다
💡라이브락(Livelock)
- 라이브락은 두 스레드가 락의 해제와 획득을 무한 반복하는 상태이다.
- 라이브락은 데드락을 피하려는 의도에서 수정한 코드가 불완전할 때 발생하곤 한다
- 라이브락 vs 데드락
- 라이브락은 모든 프로세스가 계속해서 작업을 수행하지만 전체적으로는 진행이 멈추어 있는 상황이고, 데드락은 모든 프로세스가 작업을 수행하지 못하고 멈춰있는 상황
