두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
무한히 다음 자원을 기다리게 되는 상태를 말한다.
시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.
현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐 → DeadLock
- 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
- 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 이때 프로세스는 대기 상태로 들어감
- 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태' 발생
데드락(DeadLock) 발생 조건
4가지 모두 성립해야 데드락 발생
-
상호 배제(Mutual exclusion)
자원은 한번에 한 프로세스만 사용할 수 있음 -
점유 대기(Hold and wait)
최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함 -
비선점(No preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음 -
순환 대기(Circular wait)
프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
데드락(DeadLock) 처리
- 예방 & 회피
- 예방(prevention) : 교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)
상호배제 부정 : 여러 프로세스가 공유 자원 사용
점유대기 부정 : 프로세스 실행전 모든 자원을 할당
비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구
- 회피(avoidance) : 교착 상태 발생 시 피해나가는 방법
은행원 알고리즘(Banker's Algorithm)
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
프로세스가 자원을 요구할 때,
시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)
자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 교착 상태를 회피하는 알고리즘
프로세스가 자원을 요구 시 요청 간선을 할당 간선으로 변경 했을 시 사이클이 생성 되는지 확인한다
사이클이 생성된다 하여 무조건 교착상태인 것은 아니다
자원에 하나의 인스턴스만 존재 시 교착 상태로 판별한다
자원에 여러 인스턴스가 존재 시 교착 상태 가능성으로 판별한다
사이클을 생성하지 않으면 자원을 할당한다- 탐지 & 회복
- 탐지(Detection)
자원 할당 그래프를 통해 교착 상태를 탐지함 - 회복(Recovery)
교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
면접 질문
DeadLock(교착상태)에 대해 설명하고, 해결 방법에 대해 설명해주세요.
- DeadLock(교착상태)는, 두 개 이상의 프로세스나 쓰레드가 서로 자원을 기다리면서 무한히 대기하는 상태를 의미합니다.
- 상호 배제, 점유 대기, 비선점, 순환 대기 중 하나라도 제거하여 교착 상태를 예방합니다.
'식사하는 철학자 문제'에서, DeadLock이 어떨 때 발생하는지 설명하고, 이를 해결하기 위한 방법을 제시해주세요.
"식사하는 철학자 문제"
다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 스파게티가 있고 양옆에 포크가 하나씩 있다.
그리고 각각의 철학자는 다른 철학자에게 말을 할 수 없다.
이때 철학자가 스파게티를 먹기 위해서는 양 옆의 포크를 동시에 들어야 한다.모든 철학자가 방에 입장한 후, 각자의 왼쪽포크를 5명이 모두 드는 경우에 DeadLock이 발생합니다.
1) 5명 모두 자신의 왼쪽 포크를 들고 있으므로 '점유대기'
2) 남이 포크를 뺏어주지 않음 '비선점'
3) 서로 오른쪽 포크를 놓기만을 기다림 '순환대기'
4) 각 포크에 대해 한 사람만 들 수 있음 '상호배제'
- 이 문제를 해결하기 위해서, 카운팅 세마포어를 사용합니다.
방에 대한 입장 정원을 카운팅 세마포어로 설계해, 최대 4명만 들어온다면 방 안의 모든 사람들이 왼쪽 포크를 든다 하더라도 DeadLock이 일어나지 않습니다.
회피 기법인 은행원 알고리즘이 뭔지 설명해주세요.
- 은행원 알고리즘은 은행에서 현금을 할당하는 것에서 유래한 알고리즘입니다.
프로세스가 자원을 요구할때 자원을 할당한 후에도 안정 상태이면 자원을 할당하고, 그렇지 않으면 다른 자원이 해제될때까지 대기했다가 자원을 할당합니다.
은행원 알고리즘의 단점에 대해 설명해주세요.
- 할당할 수 있는 자원수가 일정 해야한다.
- 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다.
- 최대 자원 요구량을 미리 알아야 한다.
- 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.
Think big 🌏