운영체제 - 교착 상태(식사하는 철학자 문제,자원할당 그래프, 교착 상태 발생 조건)

식사하는 철학자 문제(Dining philosophers problem)

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

이 철학자들은 식사를 할 수 있을까? 

한 두명의 철학자들만 식사할 경우 아무문제 없을 수 있다. 하지만 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없다. 모든 철학자가 왼쪽 포크를 집어들면 모두가 오른쪽 포크를 집어들 수 없기 때문이다. 

그러므로 모든 철학자는 다른 철학자가 포크를 내려 놓을때까지 기다려야한다. 이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버러는 현상을 교착상태(DeadLock)라고 한다.

---

컴퓨터 관점에서의 경우

 

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

 

 

---

교착 상태 해결법

1. 교착 상태가 발생했을 때의 상황을 정확히 표현해보기

자원 할당 그래프(Resource-Allocation graph)

어떤 프로세스가 어떤 자원을 할당 받아 사용하고 있고 또 어떤 프로세스가 어떤 자원을 기다리고 있는지를 표현한 간단한 그래프이다.

자원 할당 그래프의 규칙

1) 프로세스는 원으로 자원의 종류는 사각형으로 표현한다. 

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

2) 사용할 수 있는 자원의 개수는 자원 사격형 내에 점으로 표현한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

3) 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

4) 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

교착 상태가 일어난 그래프의 특징은 무엇일까?

자원 할당 그래프가 원의 형태를 띄고 있다.

왼쪽에 있는 그래프는 식사하는 철학자의 문제이고 오른쪽에 있는 그래프는 컴퓨터 관점에서의 경우를 나타낸 것이다. 두개 다 원의 형태를 띄고 있는 것을 확인할 수 있다.

출처 : https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

---

2. 교착 상태가 일어나는 근복적인 이유 이해하기

교착 상태가 발생할 조건

1) 상호 배제 2) 점유와 대기 3) 비선점 4) 원형 대기

위 네가지 조건중 하나라도 만족하지 않으면 교착 상태가 발생하지 않고 모두 만족해야 교착상태가 발생한다.

---

01 상호 배제

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

02 점유와 대기

자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태

03 비선점

어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

04 원형대기

프로세스들이 원의 형태로 자원을 대기하는 상태

 

 

 

 

 

 

참고 :  본 내용은개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제강의를 수강하여 작성하였습니다. https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard