교착상태를 해결하는 것이 운영체제가 맡는 임무중 하나이다.
교착상태가 무엇인지 그리고 원인은 무엇인지 확인이 필요.

13-01 ) 교착 상태란?

프로세스가 실행하기 위해 자원이 필요한데, 두 개 이상의 프로세스가 각자 가지고 있는 자원을 무작정 기다린다면, 그 어떤 프로세스도 더 이상 진행할 수 없는 교착 상태가 된다.

식사하는 철학자문제

식사하는 철학자 문제는 교착상태를 설명하기 위한 아주 고전적이고 재미있는 문제 상황이다.

• 모든 철학자가 동시에 포크를 집어 식사를 시작한다면 어떤 철학자도 식사를 할 수 없게 된다. (양 옆의 포크를 잡아야지만 식사를 할 수 있기 때문)
• 결국 옆의 철학자가 포크를 내려놓기까지 기다려야되는데 사건이 일어나기를 기다리며 진행을 멈춰버리는 현상을 교착상태(deadlock)라고 한다.

• 만약 두 프로세스 모두 자원 A,B가 필요하다면,
• 서로가 가진 자원이 할당 해제 될때까지 기다릴 수 밖에 없다.

  뮤텍스락에서 교착상태의 예시
  -프로세스 A 는 임계구역 전 LOCK 1을 잠그고 프로세스 B 는 임계구역 진입전 LOCK 2를 잠근다고 가정
  -이 상태에서 프로세스A는 LOCK 2 가 FALSE 반대로, 프로세스 B는 LOCK 1이 FALSE가 되길 기다린다면 교착상태가 발생

교착 상태를 해결하기 위해선.

1. 교착 상태가 발생했을 때의 상황을 정확히 표현해 봐야된다.
2. 교착 상태가 일어나는 근본적인 이유를 이해해야한다.

그렇다면, 교착상태가 발생했을 때 상황을 한눈에 보기 쉽게 그래프로 표현하는 방법이 있다.

자원 할당 그래프

교착 상태 발생 조건 파악가능

• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능.

1. 프로세스는 원, 자원의 종류는 사각형

2. 사용할 수 있는 자원의 갯수는 자원 사각형 내의 점으로 표현

• 만약 하드디스크가 3개라면 하드디스크 자원은 하나지만, 자원의 갯수는 3개

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

• 프로세스가 자원을 사용하고 있다면 자원 쪽에서 화살표가 나간다

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

• 만약 프로세스가 어떤 자원을 기다리고 있다면 프로세스쪽에서 화살표가 나간다.

예시

• 프로세스 A 는 SSD 자원 사용
• 프로세스 B 는 CPU 자원 사용
• 프로세스 C 는 CPU 자원 사용
• 프로세스 D 는 프린터 자원 사용
• 프로세스 E 는 프린터 자원 대기중
• 프로세스 F 는 CPU 자원 대기 중

대략적인 프로세스 교착 상태를 눈으로 확인 가능 .

만약 식사하는 철학자의 자원 할당 그래프 라면?

• 포크 라는 자원에 철학자라는 프로세스..

예시 2

• 교착상태가 일어난 그래프의 특징은??
  마치 원의 형태를 띄고 있다. 순환적인모양이다.

교착 상태 발생 조건

교착 상태가 발생할 조건
1. 상호 배제
2. 점유와 대기
3. 비선점
4. 원형 대기

위 네가지 조건 하나라도 만족하지 안으면 발생하지 않음!
그러나 모두 만족하면 교착 상태가 발생할 수 있음 !

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

점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 대기하는 상태

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

• 비선점형 스케줄링

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

자원 할당 그래프가 원의 형태라고 해서 무조건 교착상태가 발생하는 것은 아니다. 발생할 수 도 있는 것이다.
그러나 만약 그래프가 원의 형태가 아니라면 교착상태는 발생하지 않는다.