4 February 2022 / OS

OS(7) - Deadlock

OS 관련 포스팅

Deadlock

OS는 자원(Resources)을 Application에 잘 나누어주는 역할을 함
자원: CPU, memory, file, printer…
자원을 잘 못 나누어주면 deadlock에 빠지게 됨
Necessary Conditions For Deadlock
→ 아래의 네 조건이 모두 만족되어야 deadlock 발생 가능성이 있음
1. Mutual exclution(상호배타)
2. Hold and wait(보유 및 점유)
3. No preemption(비선점)
4. Circular wait(환형대기)

Resources

동일 형식(type)의 자원이 여러 개 있을 수 있음 → instance
e.g.) 동일 CPU 2개, 동일 printer 3개 등
자원의 사용
[요청 → 사용 → 반납]
자원을 필요로하는 application이 OS에 해당 자원을 요청하면,
OS가 올바른 요청인지 확인 후 허용
application은 자원을 사용 후 OS에 반납
자원 할당도(Resource Allocation Graph)
→ 자원은 사각형, 인스턴스는 사각형 안의 점, 프로세스는 원,
할당은 화살표로 표현
자원(R) → 프로세스(P): assign(할당)
프로세스(P) → 자원(R): request(요청)
자원 할당도 상에 원이 만들어지면 환형 대기 상태가 됨

Deadlock 처리

Deadlock Prevention(교착상태 방지)
Deadlock Avoidance(교착상태 회피)
Deadlock Detection & Recovery(교착상태 검출 및 복구)
Don’t Care(교착상태 무시)

(1) 교착상태 방지

교착상태 필요조건 4가지 중 한 가지 이상 불만족
Mutual exclution(상호배타) 깨려면,
→ 자원을 공유
→ CPU의 경우 시간을 두고 switching은 가능하지만 동시에 사용 불가
→ 원천적으로 불가한 조건
Hold and wait(보유 및 점유) 깨려면,
→ 일부의 자원만 가지고 있을 경우, 다른 자원을 기다려야한다면 보유한 자원을 모두 포기
→ 단점: 자원 활용율 저하, starvation(process가 진행을 못 함)
No preemption(비선점) 깨려면,
→ 자원을 강제로 빼앗음
→ CPU는 context switching해서 사용이 가능하나, printer는 불가능함
→ 원천적으로 불가한 조건
Circular wait(환형대기) 깨려면,
→ e.g.) 자원에 번호를 부여해 순서대로 자원을 요청
→ 단점: 자원 활용율 저하

(2) 교착상태 회피

deadlock을 자원 요청에 대한 잘못된 승인으로 해석
대출 전문 은행(Banker’s Algorithm)의 파산과 같다고 생각해 더이상 거래가 불가능한 상태로 인식
OS는 자원을 할당할 때 불안전한 할당(Unsafe allocation)이 되지 않도록 해야 함

(3) 교착상태 검출 및 복구

hold and wait 되더라도 말리지 않고 원하는 대로 자원을 나눠주다보면 deadlock 발생할 수 있음
deadlock 발생을 허용하며 주기적으로 검사함
검사(detection)시 overhead 발생
→ CPU 계산, memory
→ 너무 자주하면 deadlock 발견은 빠르지만 overhead 발생 가능성 증가
복구(recovery)
→ process 일부 강제 종료
→ 자원 선점해 일부 process에 할당
→ deadlock 발생 전으로 되돌리려면 주기적으로 현상태를 기억해야 하기에 memory필요

(4) 교착상태 무시

deadlock은 실제로 잘 일어나지 않음
4개의 필요조건을 모두 만족하더라도 반드시 일어나는 것 아님
개인 PC의 경우 deadlock발생시 재부팅하면 해결됨
그래서 다른 방법을 시도하는 것 보다는 재부팅이 효율적일 수 있음

—

OS(7) - Deadlock