5주차 ((1/29 ~ 2/4)
chapter. 12 : 프로세스 동기화
chapter. 13 : 교착 상태
chapter 13. 교착 상태
13-1. 교착상태란
식사하는 철학자 문제
- 가정
동그란 원탁에 다섯명의 철학자가 앉아 있다. 철학자들 사이에는 식사에 필요한 포크가 있다. 그리고 철학자들 앞에 있는 식사는 두 개의 포크로 먹을 수 있는 음식이라 가정
- 식사 순서
- 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
- 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
- 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
- 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
- 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
- 다시 1번부터 반복한다.
- 과연 이 철학자들은 식사를 무사히 마칠 수 있을까?
모든 철학자가 동시에 포크를 집어들어 식사를 하면 어떤 철학자도 식사를 할 수 없고, 영원히 생각만 하는 상황이 발생할 수 있다. 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어들수 없기 때문이다. 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다립니다.`
철학자 = 프로세스 혹은 스레드
포크 = 자원(임계구역)
생각하는 행위 = 자원을 기다리는 것
📌 이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착상태(deadlock)라고 한다.
자원 할당 그래프
: 교착상태 표현하는 그래프
- 원 : 프로세스, 사각형 : 자원
- 사각형 내부의 점 : 사용할 수 있는 자원의 개수
- 자원에서 프로세스로 화살표 : 프로세스가 어떤 자원 할당받아 사용 중
- 프로세스에서 자원으로 화살표 : 프로세스가 자원 기다리는 중
📌 교칙상태가 일어나는 상황은 자원 할당 그래프가 원의 형태 띈다.
교착 상태 발생 조건
-
상호 배제
한번에 하나의 프로세스만 자원에 접근할 수 있다. 다시 말해, 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없다. -
점유와 대기
자원을 할당받은 상태(= 점유)에서 다른 자원을 할당받기를 기다린다(= 대기) -
비선점
프로세스가 자원을 비선점(nonpreemptive) 한다. 즉, 하나의 프로세스가 어떤 자원을 사용하고 있으면 다른 프로세스는 그 자원을 뺏지 못하고 작업이 끝나야만 이요할 수 있다. -
원형 대기
자원 할당 그래프가 원으로, 프로세스들이 원의 형태로 대기하는 것을 말한다.
🫠 자원할당 그래프가 원의 형태로 그려지면 교착 상태가
발생할 수 있다.
자원할당 그래프가 원의 형태 띄지 않으면 교착 상태 발생하지 않지만, 원의 형태 띈다고 해서 반드시 교착 상태가 발생하는 것은 아님
13-2. 교착상태 해결 방법
📌 운영체제는 교착 상태가 일어나지 않도록 자원으 분배하여 교착상태 예방 할 수도 있고, 교착 상태의 위험이 있으면 자원을 할당하지 않는 회피를 할 수도 있다. 그리고 교착 상태가 검출되면 교착 상태를 회복하는 방법 취할 수 있다.
✔️ 교착 상태 예방
: 교착상태 발생 조건 네 가지 중 하나를 미충족 시키는 방법
-
상호 배제 없애기
: 모든 자원 공유 가능하게
-> 현실 적용에 무리 -
점유와 대기 없애기
: 특정 프로세스에 자원을 모두 할당 하거나 아예 할당하지 않음
-> 자원 활용률 낮아져, 기아현상 발생할 수 있음 -
비선점 없애기
: 자원을 이용 중인 프로세스로부터 해당 자원 뺏을 수 있음
-> 모든 자원이 선점 가능한 것은 아님 -
원형 대기 없애기
: 원형을 직사각형으로 만들기 : 모든 자원에 번호 붙이고, 오른차순으로 자원을 할당
-> 앞의 세 방식에 비해 현실적이나, 모든 컴퓨터 내 자원에 번호 붙이는 것이 간단하지는 않음
예방 방식은 교착 상태 발생하지 않음 보장할 수 있지만 여러 부작용 따름
✔️ 교착 상태 회피
: 한정된 자원을 고려하여 교착 상태 발생하지 않을 정도로만 조심히 자원 할당하는 방식
-
안전 순서열
: 교착 상태없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서를 의미 -
안전 상태
: 안전 순서열이 있는 상태
: 교착 상태 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태 -
불안전 상태
: 안전 순서열이 없는 상태
: 교착 상태가 발생할 수도 있는 상태
✔️ 교착 상태 검출 후 회복
: 교착상태 발생을 인정하고 사후에 조치하는 방식
- 선점을 통한 회복
: 교착상태가 해결될때가지 다른 프로세스로부터 자원 강제로 빼앗고 한 프로세스에 할당 - 프로세스 강제 종료를 통한 회복
- 표착상태 놓인 프로세스를 모두 강제 종료
: 확실하지만 그만큼 많은 프로세스들이 작업 내역 잃게 될 가능성 있음 - 표착상태 놓인 프로세스를 하나씩 강제 종료
: 작업 내역을 잃는 프로세스는 최대한 줄일 수 있지만 교착상태 없어졌는지 확인하는 과정에서 오버헤드 발생 가능서 있음
- 표착상태 놓인 프로세스를 모두 강제 종료
