Ch06. 교착 상태_01)교착 상태의 개요

<쉽게 배우는 운영체제> 교재를 참고하였습니다.

교착 상태의 정의

교착 상태(dead lock)

• 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태
• 시스템 내에 임계구역이 존재하면 프로세스 간 상호배제를 보장해야 함
• 운영체제가 상호배제를 보장하기 위해 잠금을 사용하다 보면 작업이 더 이상 진행되지 않는 교착상태에 빠짐
• 교착상태란 무엇인가? 이를 해결하는 방법에 대해 학습

교착 상태

아사 상태와 차이점

• 아사 현상 : 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
• 교착 상태 : 여러 프로세스가 작업을 진행하다 자연 발생적으로 일어나는 문제
• 운영체제는 감시를 하다가 교착상태를 감지하면 강제적으로 해결해야 함

요리사의 자원 선점과 교착 상태

---

교착 상태의 발생

시스템에서 교착상태는 시스템 자원, 공유변수(파일), 응용 프로그램 등을 사용할 때 발생함

시스템 자원

• 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
• 어떤 프로세스가 임계 구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용할 수 없는 시스템 자원을 할당 받은 후 양보하지 않는 경우
• [그림 6-3]과 같이 P1은 프린터를 할당 받은 후 CD 레코더를 기다리고, P2는 CD 레코더를 할당 받은 후 프린터를 기다리면 교착 상태가 발생함.

시스템 자원 사용 도중 교착 상태 발생

공유 변수

• 교착 상태는 공유 변수를 사용할 때도 발생. [그림 6-4]는 임계 구역 문제를 해결하기 위한 코드로, 무한 대기가 발생해 교착 상태

교착 상태를 발생시키는 임계 구역 코드

☞ P1이 lock1 = true로 만든 다음에 P2가 lock2 = true로 만들었다고 가정
☞ 이후 P1은 while(lock2==true)가 실행되어 무한 반복을 하고, P2가 while(lock1==true)가 실행되어 무한 반복
☞ 이 경우 P1과 P2 둘 다 임계 구역에 들어가지 못하는 교착상태 발생
☞ 이처럼 한 변수를 할당 받은 상태에서 다른 변수를 기다리는 교착 상태 발생

응용 프로그램

• 데이터베이스같은 응용 프로그램에서도 교착 상태 발생
• 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착 상태가 발생할 수 있음
• 여러 프로세스가 DB에 저장된 데이터를 사용할 때 데이터의 일관성을 유지해야 함. 예금 5만원이 사라진 예시가 일관성이 깨진 경우

---

자원 할당 그래프

자원 할당 그래프 (resource allocation graph)

• 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있 는 그래프로 표현한 것
• 프로세스는 원으로, 자원은 사각형으로 표현. 자원을 사용하고 있는 경우는 자원으로부터 프로세스로 향하는 화살표를 표시하고, 프로세스가 자원을 기다리는 경우는 프로세스로부터 자원으로 화살표로 표시됨.

 

• [그림 6-7]은 두 요리사가 있고, 요리사는 프로세스, 믹서와 제빵기는 자원에 비유하고 할당 받은 자원과 기다리는 자원은 화살표로 표시함.

다중 자원

• 여러 프로세스가 하나의 자원을 동시에 사용하는 경우
• 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현
• 자원이 2개 이상의 프로세스를 동시에 허용하는 경우. 여러 프로세스가 하나의 자원을 동시에 사용하면 이를 다중 자원(multiple resource) 이라고 함

2개의 프로세스를 수용할 수 있는 자원

• [그림 6-6]에서 사각형 내에 작은 원 2개가 있으면 그 자원을 2개의 프로세스가 동시에 사용할 수 있다는 의미임.

식사하는 철학자 문제

• 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사 가능

식사하는 철학자 문제의 자원 할당 그래프

• 철학자들은 음식을 먹기 위해 왼쪽의 포크를 잡은 뒤 오른쪽 포크를 잡으려고 옆을 살피지만, 이미 왼손에 포크를 들고 있는 다른 철학자 앉아있음
• 식사하는 철학자 문제는 오른쪽 포크를 잡지 못해 모두 식사는 못함(교착 상태 예). [그림6-8] 오른쪽 그림은 식사하는 철학자 문제를 자원 할당 그래프로 표현
• 4명의 철학자 프로세스 P1~P4 원으로, 자원 R1~R4 사각형으로 표현

식사하는 철학자 문제에서 교착 상태가 발생하는 조건

• ① 철학자들은 서로 포크를 공유할 수 없음
  • 자원을 공유하지 못하면 교착 상태가 발생
• ② 각 철학자는 다른 철학자의 포크를 빼앗을 수 없음
  • 자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생
• ③ 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림
  • 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생
• ④ 자원 할당 그래프가 원형
  • 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생