데드락이란?
운영체제에서 시스템 자원에 대한 요구가 뒤엉킨 상태
두 개 이상의 프로세스나 스레드가 서로 점유한 자원을 얻지 못해서 다음 처리를 하지 못하며 무한 대기에 빠진 상황
프로세스 1과 2 모두 자원 1, 2를 얻어야 할 때
-> 프로세스 1이 자원 1을 얻음 + 프로세스 2가 자원 2를 얻음
-> 프로세스 1은 자원 2를 기다림 + 프로세스 2는 자원 1을 기다림
=> 현재 서로 원하는 자원이 상대방에게 할당 되어 있어 두 프로세스가 무한 대기 상태에 빠짐
주로 발생하는 경우
멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황
한 프로세스가 자원을 요청했을 떄, 동시에 그 자원을 사용할 수 없는 상황
대기 상태로 들어간 프로세스 들이 실행상태로 변경될 수 없음
데드락 발생 조건
데드락은 다음 4가지 조건이 모두 성립해야 발생하며 하나라도 성립하지 않으면 문제 해결 가능
상호 배제
한번에 프로세스 하나만 해당 자원을 사용 가능
사용중인 다른 자원을 다른 프로세스가 사용하려면 요청할 자원이 해제될 때까지 대기
점유 대기
최소 하나의 자원을 점유하고 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스 존재
비선점
다른 프로세스에 할당된 자원을 강제로 빼앗을 수 없음
순환대기
대기 프로세스의 집합이 순환 형태로 자원 대기
데드락 처리
데드락의 발생 조건 4가지 중 하나라도 일어나지 않게 방지하여 교착 상태 가능성 차단
예방
시스템의 처리량, 효율성 감소 위험 있음
- 상호 배제 부정
- 한번에 여러 프로세스가 공유 자원을 사용할 수 있게 함
- 동기화 관련 문제 발생할 수 있음
- 점유 대기 부정
- 프로세스 실행에 필요한 모든 자원을 한번에 요구하고 허용 할때까지 작업 보류
- -> 프로세스 실행 전 모든 자원 할당
- -> 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않게 함
- 비선점 부정
- 우선순위가 높은 프로세스가 자원을 우선적으로 선점함
- -> 자원 점유 정인 프로세스가 선점권이 없을 때 요구 받을 때 자원 반남
- 순환대기 부정
- 자원에 고유 번호 할당 후 순서대로 자원을 요구
- 일정한 방향으로 자원 요구
회피
자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 수 있도록 할당 허용
- 안정 상태 : 시스템의 프로세스들이 요청한 모든 자원을 데드락을 방지하면서 모두에게 할당할 수 있음.
- 안전 순서 : 특정한 순서로 프로세스들에게 자원을 할당, 실행, 종료 등의 작업할 경우 데드락이 발생하지 않는 순서.
- 불안정 상태 : 데드락 발생 가능성이 있는 상황
- 불안정 상태 > 교착상태
은행원 알고리즘
회피의 특징을 살린 알고리즘
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사
교착 상태 회피안정 상태면 자원 할당
아닌 경우 다른 프로세스들이 자원 해지까지 대기
-> 미리 할당된 모든 자원들의 최대량을 시뮬레이션하여 안정상태에 들 수 있는지 여부 검사
-> 대기 중인 다른 프로세스들의 활동에 대한 교착 가능성 미리 조사
제약 조건
-> 최대 자원 요구량을 알고 있어야함
-> 할당할 수 잇는 자원수가 일정해야 함
탐지
데드락 발생 이후 교착상태가 되도록 허용한 다음 회복
- 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생으로 파악
- 자원 할당 그래프를 사용하여 교착 상태 탐지
회복
교착 상태가 발생한 프로세스를 종료하거나 할당된 자원을 해제시켜 회복시키는 방법
- 프로세스 종료 방법
- 교착 상태에 빠진 프로세스 모두 중지
- 모든 프로세스가 중단되어 부분 결과 폐기 부작용 발생 가능성
- 교착 상태가 제거 될때까지 하나씩 프로세스 중지하면서 탐지 알고리즘으로 회복
- 매번 탐지 알고리즘 호출 및 수행으로 부담이 될 수도
- 교착 상태에 빠진 프로세스 모두 중지
- 자원 선점 방법
- 해당 프로세스 일시 정지
- 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 자원 선점하여 그 자원을 다른 프로세스에 할당
