[운영체제] 교착 상태란?

식사하는 철학자 문제란?

에드거 다익스트라 교수가 동기화 이슈와 해결 방법을 설명하고자 시험 문제로 냈다.

 

문제의 내용은 다음과 같다. 5개의 의자가 놓여진 원탁 테이블이 있고 
이 원탁에서 5명의 철학자가 정해진 자리에서 식사를 하는데 식사 시간은 다를 수 있다.
 자리마다 스파게티 그릇이 있고 각 철학자의 왼쪽에 포크가 하나씩 있다. 
스파게티를 먹는데 철학자는 자신의 왼쪽 포크와 오른쪽 포크 즉 두개의 포크를 이용해야 한다.
포크를 드는 순서는 왼쪽포크 -> 오른쪽포크 순이며 포크가 사용 중이면 대기해야 한다. 
이때 철학자들이 식사를 할 때 어떤 문제가 생길 수 있는가에 대한 문제이다.

철학자들의 포크를 잡는 시간이 다르기만 하다면 모든 철학자는 식사를 할 수 있다 
하지만 모든 철학자가 동시에 포크를 들게 된다면 왼쪽 포크를 든 상태로 
오른쪽 포크를 무한정 기다리는 환형 고리를 이루게 되어 식사를 할 수 없다.

 

해결 방법: 한 철학자만 먼저 잡는 포크의 방향을 바꾸어 환형의 요청이 발생하지 않게 만드는 것이다.
오른쪽 포크를 먼저 잡을려고 할 때 다른 철학자가 그 포크를 이미 집은 상태라면 
왼쪽 포크 또한 잡을 수 없기 때문에 두개의 포크를 소유하는 철학자가 생기게 되어 
언제가는 식사를 할 수 있게 된다.

 

컴퓨터 시스템에서의 교착 상태?

교착상태란 자원을 가진 스레드들 사이에서 각 스레드가 다른 스레드가 소유한 자원을 요청하여

모든 스레드가 무한정 대기하는 상태이다.

교착상태를 발생시키는 잠재적 요인 4가지 

자원 - 독점 사용 

자원, 스레드 - 하나의 스레드가 여러 스레드를 필요로 함 

자원, 운영체제 - 운영체제는 한 번에 하나씩 자원 할당 (한번에 필요한 자원을 전부 할당해 주지 않는다)

자원 비선점 - 필요한 자원을 강제로 뺏을 수 있으면 교착상태 발생 x 

 

자원 할당 그래프가 무엇인지, 왜 쓰는지 

컴퓨터 시스템에서 교착 상태를 표현

이 그래프를 기반으로 교착상태 예방, 회파, 감지 등이 운용 

 

교착상태 팔요충분조건 4가지 (코프만 법칙) 

상호배제

소유하면서 대기

강제 자원 반환 불가 

환형 대기 

 

교착상태 해결방법 

교착상태 예방 

교착상태 회피 

교착상태 감지 및 복구 

교착상태 무시 

 

교착상태 예방

코프만 조건 중 최소 하나를 성립하지 않게 만들면 됨.

상호배제 x 

자원을 요청할 때 가진 자원을 전부 반환하고 요청, 스레드 실행 시작 필요한 자원들을 모두 할당 

자원의 선점 허용 

환형 대기 제거 

 

회피 

banker's 알고리즘 

 

감지 및 복구 

자원 강제 선점 

rollback 

스레드 강제 종료 kill process

 

교착상태 무시

과연 교착상태를 해결할 필요가 있을까?

타조 알고리즘