식사하는 철학자 문제
- 철학자 - 프로세스 or 스레드
- 포크 - 실행에 필요한 자원
- 식사 - 실행
- 위 상황이라면 아무도 식사를 할 수 없게 됨 => 교착 상태
교착 상태
- 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상
- 서로 가지고 있는 자원이 할당 해제될 때까지 무작정 기다려야 함 => 결국 실행 못함 => 교착 상태
교착 상태가 발생하면?
- 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
- 교착 상태가 일어나는 근본적인 이유 이해하기
교착 상태의 상황 표현 - 자원 할당 그래프
- 교착 상태 발생 조건 파악 가능
- 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
- 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능
그리는 법
1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
자원 할당 그래프 예시
- SSD는 프로세스 A에 할당
- CPU는 프로세스 B와 C에 할당
- 프린터는 프로세스 D에 할당
- 프로세스 E는 프린터의 사용 대기
- 프로세스 F는 CPU의 사용 대기
식사하는 철학자 문제의 자원 할당 그래프
게임/웹브라우저 문제의 자원 할당 그래프
교착 상태가 일어난 그래프의 특징?
자원 할당 그래프가 원의 형태를 띄고 있음!
교착 상태가 발생하는 근본적인 이유
교착 상태의 발생 조건
- 상호 배제(Mutual Exclusion)
- 점유와 대기(Hold and Wait)
- 비선점 (Non-Preemption)
- 원형 대기 (Circular Wait)
위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음
위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음
- 상호 배제
: 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태 - 점유와 대기
: 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태 (식사하는 철학자) - 비선점
: 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태 - 원형 대기
: 프로세스들이 원의 형태로 자원을 대기하는 상태
: 원의 형태라고 무조건 교착 상태는 아님, 하지만 교착 상태에서는 모두 원의 형태로 자원을 대기하고 있음(네 가지 조건을 모두 충족해야지만 교착 상태)
교착 상태 해결 방법
- 예방, 회피, 검출 후 회복
교착 상태 예방
- 애초에 교착 상태가 발생하지 않도록
- 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기
- 교착 상태가 발생하지 않도록 보장할 수 있으나 부작용이 따르는 방식
상호 배제를 없애면?
- 모든 자원을 공유하게 만든다
- 이론적으로는 가능하지만 현실적으로는 불가능
점유와 대기를 없애면?
- 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
- 자원의 활용률을 낮추는 부작용 발생
- 지금 당장 자원이 필요한데 활용되지 못하는 프로세서, 할당을 받지 못해 오랫동안 대기해야 하는 프로세스, 한 프로세스에 모든 자원을 할당했지만 많이 사용하지 않아 낭비되는 자원 등등...
비선점 조건을 없애면?
- 선점이 가능한 자원(ex. CPU)에 한해 효과적
- 하지만 모든 자원이 선점 가능한 것은 아님 (ex. 프린터)
원형 대기 조건을 없애면?
- 모든 자원에 번호를 붙이고, 오름차순으로 할당하면 원형 대기는 발생하지 않음
- 철학자들에게 낮은 포크에서 높은 포크로만 집도록 요구
- 원형 테이블이 아닌, 일렬로 앉은 것처럼 동작시킴
- 5번 포크에서 1번 포크를 집는 것은 불가능하므로 원형 대기 조건이 발생하지 않음
- 앞선 방식들 보단 현실적이고 실용적이지만 단점도 있음
- 자원에 번호를 붙이는 것은 어려운 작업
- 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라짐
- 많이 써야하는 자원임에도 붙은 번호가 낮아서 많이 쓰지 못하거나, 많이 쓰지 않는데도 번호가 높아 많이 활용될 수 있는 경우 등.. 활용률이 떨어질 수 있음
교착 상태 회피
- 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
- 교착 상태가 발생하지 않을 만큼 조심조심 할당하기
- 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분
- 안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
- ex. A → B → C 교착상태 발생 ,
B → C → A 교착상태 발생X 라면
B → C → A가 안전 순서열
- ex. A → B → C 교착상태 발생 ,
- 안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태 (=안전 순서열이 있는 상태)
- 불안전 상태 : 교착 상태가 발생할 수도 있는 상태 (= 안전 순서열이 없는 상태)
- 교착 상태 회피는 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
- 항시 안전 상태를 유지하도록 자원을 할당하는 방식
- ex. 은행원 알고리즘
예시
- 컴퓨터 시스템에 총 12개의 자원
- 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당 받아 실행 중
- 운영 체제가 배분할 수 있는 자원의 개수는? 12 - 5 - 2 - 2 = 3개
- 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정
- 안전 순서열이 존재 : P2 → P1 → P3
아까와 같이 P1,P2,P3이 모두 최대로 자원을 요구하는 최악의 상황을 가정
(각각 5개, 2개, 6개)
교착 상태 검출 후 회복
- 교착 상태의 발생을 인정하고 사후에 조치하는 방식
- 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
- 선점을 통한 회복
- 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
- 프로세스 강제 종료를 통한 회복
- 교착 상태에 놓인 프로세스 모두 강제 종료 (=> 작업 내용을 잃을 위험)
- 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(=> 오버 헤드)
교착 상태 무시
- 타조 알고리즘
- 문제가 생기면 문제를 해결하려고 하지 않고 땅에 머리를 묻고 숨어버리는 것 때문에 유래함
- 문제의 발생 빈도수나 심각성에 따라 최대 효율을 추구해야 하는 엔지니어 입장에서 때로는 이 방법이 더 적합할 때도 있음
출처 : 혼자 공부하는 컴퓨터구조 + 운영체제 (저자 강민철)
'취업역량강화 > 컴퓨터공학' 카테고리의 다른 글
| [운영체제] 가상메모리(쓰기 시 복사, 계층적 페이징, 페이지 교체, 스레싱, 프레임 할당) (0) | 2026.02.25 |
|---|---|
| [운영체제] 가상 메모리 (연속 메모리 할당, 페이징을 통한 가상 메모리 관리) (0) | 2026.02.23 |
| [운영체제] 프로세스 동기화(뮤텍스 락, 세마포, 모니터) (0) | 2026.02.19 |
| [운영체제] CPU 스케줄링과 스케줄링 알고리즘 (0) | 2026.02.17 |
| [운영체제] 파이썬으로 프로세스와 스레드 다루기 (0) | 2026.02.15 |