신규 블로그를 만들었습니다!

2020년 이후부터는 아래 블로그에서 활동합니다.

댓글로 질문 주셔도 확인하기 어려울 수 있습니다.

>> https://bluemiv.tistory.com/

다중프로그래밍 환경에서는 여러 프로세스들이 한정된 자원을 사용하려고 경쟁을 합니다.

특정한 한 프로세스가 자원을 요청했을때, 그 자원을 다른 프로세스가 사용중이라면,

자원을 요청한 프로세스는 대기상태에 빠지게 됩니다.



이때 무한히 대기상태에 빠져있는 상태를 DeadLock(교착상태)이라고 합니다.



    Deaclock 교착상태 



Deadlock에대해 알아보기 전에 용어에 대한 정리를 하고 가겠습니다.


  • resource (자원) : 메모리 공간, CPU 주기, 파일, 입/출력 장치 (프린터, DVD 등등)
  • instance (인스턴스) : 각 자원의 유형, 만약 시스템의 CPU가 2개라면, 자원유형의 인스턴스는 2개를 가짐
  • request : 프로세스가 자원을 요청
  • use : 프로세스가 시스템으로부터 자원을 할당받아 사용
  • release : 자원을 반납

(참고 : 자원의 요청과 방출은 장치의 request(), release(), 파일의 open(), close(), 메모리의 allocate(), free() 등의 시스템 호출이 있습니다.)


예를들어, 프로세스가 시스템한테 request를 통해 자원을 요청합니다. 그리고 시스템은 프로세스에게 자원을 할당해 프로세스는 자원을 use 합니다. 작업을 끝낸 프로세스는 시스템에게 다시 자원을 release 합니다.


프로세스는 자원을 사용하기 전에 반드시 요청해야하고, 사용후에는 자원을 시스템한테 반납해야합니다.



교착상태는 동기화 도구 (mutex lock, semaphore) 등 에서 주로 발생합니다. 


교착상태에 빠지는 조건은 총 4가지가 있습니다. 이 4가지 조건을 모두 만족할때 Deadlock에 빠지게 됩니다.

  • Mutual exclusion (상호배제) : 한번에 오직 하나의 프로세스가 하나의 자원만 사용
  • Hold and Wait (점유하고 대기) : 자원을 할당받은 상태에서 다른 프로세스가 사용중인 자원을 추가로 얻기위해 기다리는 경우
  • No preemption (비선점) : 자원이 강제적으로 반납될 수 없고, 작업중인 프로세스가 끝난뒤에야 자원을 반납 받음
  • Circular wait (순환대기) : 여러프로세스가 있을때 P0, P1, P2, ... , Pn 가 있을때 P0은 P1의 사용중인 자원을 요구하고, P1은 P2의 사용중인 자원을 요구, Pn은 P0의 사용중인 자원을 요구하는 경우, 즉 순환형태의 꼬리를 물면서 요구하는 경우
위와같이 4가지 조건이 동시에 만족되는 경우 교착상태에 빠집니다.



교착상태를 표현하는 방법중에는 자원할당 그래프 (Resource-Allocation Graph) 가 있습니다.


    Resource-Allocation Graph



자원 할당 그래프을 표현하기 위해 필요한 요소는

  • 정점 V(vertex)
  • 간선 E(Edge)
  • P = {P1, P2, ... , Pn}  >> 프로세스들의 집합
  • R = {R1, R2, ... , Rm}  >> 자원타입들의 집합

4가지가 있습니다.



Pi가 Rj를 요청할때는 request edge 표현을 이용해서

  • Pi → Rj

처럼 표현합니다.



Rj가 Pi에게 할당 되었다고 표현할때는

  • Rj → Pi

처럼 표현합니다.




교착상태에 빠지지 않은 정상적인 자원 할당 그래프의 한 예를 보겠습니다.

P1은 R1 자원을 요청하고 R1은 P2에게 할당되어 있습니다. P2는 R3 자원을 요청하고 있고 R3는 P3에게 할당되어 있습니다.

P3의 작업이 끝나면 R3를 반납 할테고, P2는 R3 자원을 할당 받을 수 있게됩니다. P2또한 작업을 마치면 P1은 P2가 반납한 R1 자원을 사용하면서 일을 마무리 할 수 있습니다.



교착상태에 빠진 자원 할당 그래프를 보겠습니다.


P1은 R1을 요청하고, R1은 P2에게 할당 되었습니다. P2는 R3를 요청하고 R3는 P3에게 할당 되어있습니다. P3는 P2에게 할당된 R2자원을 요청하고 있습니다. 이렇게 서로 필요한 자원을 할당 받지 못하고 그저 자원을 할당받을때까지 기다리기만 합니다. 교착상태에 빠지게 됐습니다.


그래프를 보시면 파란색 Cycle과 빨간색 Cycle이 있습니다. 이러한 Cycle이 만들어지는경우 Deadlock에 빠지기 쉽습니다.



Cycle이 있지만 교착상태에 빠질수도 있고, 빠지지 않을 수 도 있는 경우를 보겠습니다.


빨간색 Cycle이 있지만 파란색으로 표시된 프로세스 P2와 P4에 의해서 위 그래프는 Deadlock에 빠지거나 빠지지 않거나 할 수 있습니다. 만약 P2나 P4중 하나라도 남는 자원을 할당받아 일을 마무리하게 된다면 자신이 쓰고있던 자원을 반납하게 됩니다. 그로인해 P1이나 P3가 사용할 수 있는 자원이 늘어나게 될테고 교착상태에 빠지지 않게 됩니다.



다음에는 교착상태를 해결하는 방법에 대해서 알아보겠습니다.



  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 카카오스토리 공유하기