데드락 (DeadLock, 교착 상태)
프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
무한히 다음 자원을 기다리게 되는 상태
두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
한정된 자원을 여러 곳에서 사용하려고 할 때 발생
주로 발생하는 경우
멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
A 프로세스가 자원A 요청 → 동시에 자원A 사용 불가 한 상태 → A프로세스가 대기 상태로 들어감
이때
대기상태로 들어간 프로세스들이실행상태로 변경될 수 없을 때 교착 상태 발생
데드락 발생 조건
4가지 모두 성립해야 발생 (하나라도 성립하지 않을 경우 데드락 해결 가능)
✔️ 상호 배제 (Mutual exclusion)
: 자원은 한번에 한 프로세스만 사용 가능
✔️ 점유 대기 (Hold and wait)
: 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스 존재
✔️ 비선점(No preemption)
: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없음
✔️ 순환 대기(Circular wait)
: 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
데드락 처리
✔️ 예방(prevention)
교착 상태 발생 조건 중 하나를 제거하면서 해결
방법
상호배제 부정: 여러 프로세스가 공유 자원 사용현실적으로 불가능
점유대기 부정: 프로세스 실행전 모든 자원을 할당자원 낭비 발생
필요하지 않은 순간에도 가지고 있음
무한대기 현상 발생 가능
비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납현실적으로 불가능
순환대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구자원들에게 순서 부여
프로세스는 순서의 증가 방향으로만 자원 요청 가능
자원 낭비 발생
특징
4개의 데드락 발생 필요 조건 중 하나를 제거한다면, 절대 발생하지 않음
심각한 자원 낭비 발생
비현실적
✔️ 회피(avoidance)
개념
시스템의 상태를 계속 감시
시스템이 데드락 상태가 될 가능성이 있는 자원 할당 요청 보류
시스템을 항상
Safe state로 유지Safe state: 모든 프로세스가 정상적으로 종료 가능한 상태
방법
은행원 알고리즘 (Banker's algorithm)다익스트라가 제안한 기법
어떤 자원의 할당의 할당허용 여부를 결정하기 전, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 진행하여
safe state에 들 수 있는 여부 검사은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
특징
데드락의 발생을 막을 수 있음
높은 오버헤드
항상 시스템을 감시하고 있어야 함
Safe state 유지를 위해 사용되지 않는 자원 존재
실용적이지 못함
가정이 필요함
프로세스, 자원 수 고정
필요한 최대 자원 수를 알고 있음
✔️ 탐지(detection)
개념
데드락 방지를 위한 사전 작업을 하지 않음
데드락 발생 가능
주기적으로 데드락 발생 확인
시스템이 데드락 상태인지 확인어떤
프로세스가 데드락 상태인지 확인
Resource Allocation Graph (RAG)사용
Resource Allocation Graph (RAG)
데드락 검출을 위해 사용
방향성(directed)을 가지고 이분 그래프(bipatite graph) 사용
Graph Reduction으로 데드락 판별주어진 RAG에서 edge를 하나씩 지워감
Complete reduced: 모든 edge가 제거 되었다면 데드락 XIrrducible: 지울 수 없는 edge가 존재한다면 데드락 O
RAG는 높은 오버헤드를 가짐
주기적인 검사 필요로, 검사 주기에 영향을 받음
노드 수가 많은 경우 오버헤드 증가
데드락 회피(avoidance)와 탐지(detection)
데드락 회피
최악의 경우를 생각
데드락이 일어날 경우를 고려하여 회피
데드락이 발생하지 않음
데드락 탐지
최선의 경우를 생각
현재 상태만 고려해 데드락이 발생하는가를 파악
데드락이 발생할 수 있음
데드락 발생 시 Recovery과정이 필요
✔️ 복구(recovery)
개념
데드락을 검출한 후 해결하는 과정
방법
Process terminate데드락 상태에 있는 프로세스를 종료시킴
강제 종료된 프로세스는 이후 재시작 됨
종료 방법
데드락의 원인이 되는 프로세스를 모두 종료
한번에 하나의 프로세스만 종료시키면서 데드락이 풀리는지 확인 (높은 오버헤드)
종료시킬 프로세스 선택 요인
프로세스 우선순위
프로세스 수행 시간, 일을 끝마치기까지 남은 시간
프로세스가 점유하고있는 자원 타입과 양 (회복하기 쉬운 자원인지)
프로세스가 종료하기까지 남은 자원의 수
얼마나 많은 수의 프로세스를 같이 종료시켜야하는지
프로세스가 interactive인지 bath형태인지
Resource preemption데드락 상태 해결을 위해 프로세스의 자원을 선점하는 방법
희생 프로세스 선정
희생 비용을 최소화하기위해 어느 프로세스의 어떤 자원을 뺏을지 결정
롤백
어떤 프로세스로부터 자원을 뺏어오면 자원을 뺏긴 프로세스는 나중에 safe state로 롤백하고 다시 재실행 해줘야함
혹은 처음 상태로 되돌림
Checkpoint-restart method프로세스의 수행 중 특정 지점(check point)마다 context 저장
롤백을 위해 사용
프로세스 강제 종료 후, 가장 최근의 check point에서 재시작
기아현상
선점횟수에 가중치를 부여해 선점이 많이된 프로세스에게 우선권을 줘 기아현상 방지
Wait free 와 Lock free
Wait-free와 Lock-free는 모두 멀티스레딩 환경에서 공유 자원에 대한 동시 접근을 처리하는 기술
Wait-free는 모든 스레드가 동시에 진행될 수 있는 것에 비해, Lock-free는 일부 스레드가 블로킹될 가능성이 있지만, 구현이 더 쉽고 성능이 높은 경우가 많음.
공통점
스레드가 락을 획득하거나 해제하는 데 소비되는 시간이 줄어듦
락 경쟁으로 인한 병목 현상이 줄어들어 여러 스레드가 효율적으로 동시에 실행될 수 있음
무한 대기 상황을 방지함으로써 데드락 문제 해결
Wait free
개념
모든 스레드가 동시에 진행
하나의 스레드가 멈춰도 다른 스레드는 계속 진행 가능
특징
어떤 스레드도 블로킹되지 않음
단점
구현이 복잡하고 어려움
복잡성으로 인해 정확성을 증명하는 것이 어려움
Lock-Free에 비해 더 많은 오버헤드 발생 가능
장점
모든 스레드가 한정된 시간 내에 진행 가능
Lock free
개념
항상 하나 이상의 스레드가 진행할 수 있음을 보장
특징
공유 자원에 대한 동시 접근을 락 없이 원자적 연산으로 처리
단점
일부 스레드가 블로킹될 가능성 있어 높은 지연시간 발생 가능
장점
비교적 쉬운 구현
하나 이상의 스레드가 진행 가능함을 보장
스레드 간 상호작용 없이 안전하게 공유 자원 사용 가능
Last updated