교착상태

※ 전남대학교 박태준 교수님의 운영체제 강의를 듣고, 정리한 내용입니다.

교착상태의 정의

자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기중인 상태를 교착상태라고 합니다.

식사하는 철학자 문제 ( Dining Philosophers Problem )

식사를 하기 위한 조건은 다음과 같습니다.

• 5명의 철학자가 원탁에서 식사, 식사 시간은 서로 다를 수 있음

• 자리마다 스파게티 1개와 양 옆에 포크가 있음

• 각 철학자는 옆의 철학자에게 말할 수 없음

• 식사를 하기 위해서는 양 옆의 포크가 동시에 들려 있어야 함

• 왼쪽 포크를 먼저 들고, 다음 오른쪽 포크를 드는 순서

• 포크가 사용 중이면 대기

다음과 같은 조건에서 모두가 이상 없이 식사를 잘 할수 있을지에 대한 경우의 수는 다음과 같습니다.

모든 철학자가 동시에 왼쪽 포크를 든 경우, 오른쪽 포크를 들려고 하는 순간 모든 철학자의 무한 대기가 발생하게 됩니다.

이 경우를 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 환형 고리가 발생한다 라고 하고, 이를 환형 요청 / 대기 ( circular wait ) 라고 합니다.

이를 해결하기 위해선, 원형 상태로 요청이 생기지 않도록 해줘야 합니다.

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

컴퓨터의 경우, 자원을 소유한 쓰레드 ( 혹은 프로세스 ) 들 사이에서, 각 쓰레드는 다른 쓰레드가 소유한 자원을 요청하며 무한정 대기하고 있는 상황을 교착상태라고 볼 수 있습니다.

기아와 교착의 차이

• 기아 ( Starvation ) : 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

• 교착 ( Deadlock ) : 교착 상태는 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제

교착상태의 잠재적 요인들

• 자원

  • 교착상태의 발생지
  • 교착상태는 멀티쓰레드가 자원을 동시에 사용하려는 것이 충돌 요인

• 자원과 쓰레드

  • 한 쓰레드가 여러 자원을 동시에 필요로 하는 상황

• 자원과 운영체제

  • 한 번에 하나씩 자원을 할당하는 운영체제 정책

• 자원 비선점

  • 할당된 자원을 쓰레드가 자발적으로 내놓기 전에 강제로 빼앗지 못하도록 하는 정책
  • 운영체제는 쓰레드가 가진 자원을 강제로 뺏지 못함

교착상태 모델링 : 자원 할당 그래프 ( Resource Allocation Graph, RAG )

• 그래프의 요소

  • Vertex : 프로세스 / 쓰레드 ( 원 ) , 자원 ( 사각형 )
  • Edge : 소유 / 요청 관게, 할당 간선과 요청 간선

• 자원에 대한 시스템의 상태를 나타내는 방향성 그래프

• 자원할당그래프를 통해 교착상태 판단