교착상태란?
1950년대 말부터 1960년 초반, 다중프로그래밍의 도입과 함께 노출된 여러 문제점들 중 하나로, 스레드들(혹은 프로세스들)이 상대가 가진 자원을 서로 요청하면서 실행을 중지한 채 대기하는 경우를 의미한다.
스레드 사이에서 발생하는 공유 자원에 대한 동기화 문제 중 하나이다.
즉, 자원을 소유한 스레드들 사이에서, 각 스레드는 다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무한정 대기하는 현상을 말한다.
교착상태는 단일 CPU, 다중 CPU든 상관X, '락'이나 자원에 대한 멀티스레드의 경쟁이 있는 한 발생할 수 있다.
하지만, 교착상태는 커널 코드 내에서는 거의 발생하지 않고, 사용자 응용프로그램 내에서 주로 발생한다.
커널 코드 내에서 발생하지 않는 이유?
- 커널은 교착상태를 고려하여 매우 정교하게 잘 작성되어 있기 때문이다.
- (<>사용자 응용프로그램은 정교하지 못함.)
교착 상태의 예시
CPU가 1개가 있는 시스템에서 교착상태에 빠지는 경우이다.
- CPU가 스레드 T1을 실행한다.
- T1이 작업을 수행하는 도중 '파일A'에 락을 걸어 소유한다.
- 이후 다른 작업 중, T2로 컨텍스트 스위칭 된다.
- CPU가 스레드 T2를 실행한다.
- T2가 작업을 수행하는 도중, '파일B'에 락을 걸어 소유한다.
- 이후 다른 작업 중, T3로 컨텍스트 스위칭 된다.
- CPU가 스레드 T3를 실행한다.
- T3가 작업을 수행하는 도중, '프린터'를 소유한다.
- 이후 다른 작업 중, T4로 컨텍스트 스위칭 된다.
- CPU가 스레드 T4를 실행한다.
- T4가 작업을 수행하는 도중, '뮤텍스'에 락을 걸어 소유한다.
- 이후 다른 작업 중, T1로 컨텍스트 스위칭 된다
- CPU가 다시 스레드 T1을 실행한다.
- T1은 '파일A'를 소유한 채, '파일B'에 락을 걸려고 시도한다.
- 하지만 '파일B'는 T2에 의해 락이 걸려 있기 때문에, T1은 대기한다.
- CPU가 스레드 T2를 스케줄하여 실행한다.
- T2가 '파일B'를 소유한 채, '프린터' 사용을 요청한다.
- 하지만 '프린터'는 T3가 사용 중이므로 T2는 대기한다.
- T3, T4도 위와 동일하게 대기하게 되어, 결국 교착상태에 빠진다.
교착상태 유발 잠재적 요인
공유자원
- 소프트웨어 자원 : 뮤텍스, 스핀락, 세마포어, 파일락 등
- 하드웨어 자원 : 메모리, 프린터, 프로세서 등
한 스레드가 여러 자원을 동시에 필요로 할 때
- 다수의 스레드가 자원을 동시에 사용하려 할 때
한 번에 하나씩 자원을 할당하는 OS의 정책.
자원의 비선점.
교착상태 발생 필요충분 조건 : 코프만 조건
다음의 네 조건이 동시에 성립되면 교착 상태가 발생할 수 있다.
따라서 운영체제에서 이 네가지의 조건 중 하나 이상을 깨트리는 방식으로 교착상태를 예방하거나 회피할 수 있다.
- 상호 배제 (Mutual Exclusion)
- 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
- 예: 프린터, 파일 등 공유 불가능한 자원.
- 점유와 대기 (Hold and Wait)
- 자원을 가진 프로세스가 다른 자원을 기다리며 블록 상태에 있을 수 있다.
- 즉, 자원을 하나 점유한 상태로, 다른 자원을 기다리는 것.
- 비선점 (No Preemption)
- 이미 할당된 자원은 강제로 빼앗을 수 없고 자원이 해제되기 전까지는 기다려야 한다.
- 예: CPU나 프린터 같은 자원을 중간에 뺏을 수는 없음.
- 순환 대기 (Circular Wait)
- 프로세스들이 원형으로 자원을 기다리는 상태를 의미한다.
- 예: P1 → P2 → P3 → ... → P1 이런 식으로 서로 자원을 기다리는 구조.