프로세스 관리-3 : 프로세스 데드락(Deadlock) 문제 및 해결법

# 본 게시글은 작성자 본인의 스터디 목적으로 작성된 글입니다.

# 본 게시글에는 일부 잘못된 정보가 포함되어있을 수 있습니다.

# 이 글을 열람하는 것은 위 사항에 동의하는 것으로 간주합니다.

# 잘못된 정보에 대한 태클 및 지적질 적극 환영합니다.

1. 데드락(교착상태)이란?

    : 프로세스간 공유자원을 사용하는 과정에서 발생할 수 있는 "죽어있는 잠김상태"를 말한다. 

     차키를 차안에 두고 차문을 잠가본 사람은 이 죽어있는 잠김상태가 몬지 어렴풋하게나마 

     알수 있지 않을까???

     즉, 프로세스A가 자원1을 사용중이며, 자원2를 필요로 할때, 이 자원2는 프로세스B에 의해 사용중이며, 

     반대로 프로세스B는 프로세스A가 사용중인 자원1을 필요로 할때 두 프로세스가 대기상태로 접어들고, 

     서로 잡고 있는 자원을 놓아주기만을 기다리는 빼도박도 못하는 상황을 바로 

     교착상태(데드락:DeadLock)이라 한다. 

 

      c.f) 데드락 모델링

  

  

2. 데드락 해결법

   2.1 데드락 방지기법

        - 아래의 4가지 조건을 모두 만족하는 경우 데드락이 발생한다.

          따라서, 데드락 방지기법은 이 네가지 조건 중 하나라도 만족하지 않도록 하는 것이다. 

          그 방법은 각 조건의 아래에 표기했다.

• 상호배제(Mutual Exclusion) : 특정 자원은 특정 시점에 오직 하나의 프로세스만 사용 가능하다.
• 선점불가 : 자원은 먼저 확보한 프로세스가 해제를 해주어야만 다른 프로세스에 의해 사용이 가능하다.

               => 상호배제와 선점불가는 현실적으로 적용의 여지가 없다. 왜 적용하기 힘들까? 

                    나름 생각해보시길..

• 보유 및 대기 : 프로세스에 의해 할당된 자원이 사용가능한 상태가 되기만 기다리는 프로세스가 반드시 하나 이상 존재한다.

          => 프로세스가 필요로 하는 모든 자원이 사용 가능한 상태가 될 때까지 기다렸다가 이를 한방에

               싸그리 확보하고, 느긋하게 하나씩 사용한 후 해제하도록 하는 것이다. 

               사용하지도 않을 자원을 미리 확보하는 이기적인 방법이다.

               이는 곧 자원의 활용률 저하와 직결된다. 또한, 너무 욕심많은 놈일 경우 자원 확보가 어려워 

               영영 지 할일을 못하는 기아(starvation)상태를 초래할 수 있다. 

              이에 다른 방안을 생각할 수 있는데 일부 자원을 확보한 상태에서 다른 자원을 확보하려 했을때

              이 자원이 사용불가 상태라면 먼저 확보했던 자원들도 모두 놓아버렸다가 나중에 다시 

              확보하는 방식이다.

             하지만 이것 또한 미리 확보해서 사용중이던 자원을 작업을 완료하기전에 놓아주는 것이 

             무진장 어려워 현실적으로 적용이 어렵다고 한다.

• 원형대기 : 프로세스간 서로가 서로에게 사용중인 자원을 요구하는 원형대기 상태가 존재한다. 

            => 자원 확보 순서를 미리 셋팅!!! 프로세스 자신이 당장 필요한 자원이 있더라도 그보다 

               순위가 높은 자원을 먼저 확보한 후 필요한 자원을 요청해야 한다.

               자원의 활용률을 좀 더 올릴 수 있다는 장점이 있다.    

      

   2.2 데드락 회피기법

        - 기본적으로 프로세스가 필요로 하는 시점에 자원을 할당해주나, 데드락이 발생할 여지가 있으면 

          자원할당을 보류한다.

        - 데드락 방지기법보다 자원 활용률을 높일 수 있는 기법이다.

        - 하지만, 데드락이 발생할지, 안할지 그걸 어찌 아누? 간단히 생각하면 답은 나온다.

          프로세스가 자신이 사용할 자원과 언제 어떤 순서로 그 자원들을 사용할지에 대한 정보를 

          운영체제한테 귀뜸해주면 된다.

          그렇담 이제 운영체제가 바빠진다. 운영체제는 그 많은 프로세스들의 귀뜸을 듣고, 

          자원 할당 요청이 올 때마다 현재의 자원할당 상태를 확인하고, 앞으로 나올 자원 할당 요청을 

          보고, 이를 종합적으로 판단해 이걸 이놈한테 할당해주면 데드락이 발생할까? 안할까? 를 놓고 

         심각한 고민에 빠진다. 머리 뽀개지고, 졸라 귀찮겠지.. 결국 데드락 발생가능성 검사로 인해 

         오버헤드가 커진다는 문제가 발생한다..어쨋든, 데드락 발생가능성 검사를 위해서 운영체제가 

         사용하는 검사 방법이 있는데 아래 그림을 보라! 

           

             

                          <자원할당그래프(RAG:Resource Allocate Graph) + 클레임에지>

 

              (a)를 보면 자원 R1은 프로세스 P1에 할당되어 있고, P2와 P3는 R1에 대한 할당 요청이 된 

              상태이다. 그리고 P1,P2,P3는 다음에 R2를 사용할 예정으로 운영체제가 클레임 에지(점선부분)

              를 설정하였다. R2는 P4에 할당되어 있음을 알 수 있다.

              여기서 P4가 R2의 사용을 끝낸 후 R2를 해제하고, P3가 R2를 먼저 요청할 경우 그림(b)와 같이

              그림 (a)의 클레임에지 P3->R2는 할당에지 R2->P3 로 바뀌고, 사이클이 발생하게 된다. 

              즉, 데드락 발생 가능성이 있음을 보여준다. 따라서 운영체제는 R2에 대한 P3에 할당을 

              보류하고, 할당에지 R2->P3 대신 요구에지 P3->R2로 변경하며, P3는 대기상태로 전환시킨다. 

              이후에 P1이 R2를 요청하면 그림 (c)와 같이 사이클이 발생하지 않으므로 R2를 P1에 할당한다.

             

              c.f) 뱅커스 알고리즘(banker's algorithm) ???

 

   2.3 데드락 탐지 및 복구기법

        - 프로세스가 요청한 자원이 사용가능하면 무조건 할당하고 본다. 데드락이 발생하던~ 말던~ 

          그건 나중에 처리하고 보자는 "일단 저지르고 사고터지면 그때가서 생각하자" 의 귀차니즘 기법 중

          하나이다. 할당한 자원으로 인해 데드락이 발생하게 되면 운영체제는 이를 적절한 해결방법으로 

          복구한다. 따라서, 운영체제는 데드락이 발생했는지 적절한 시기에 순찰을

          돌아줘야 한다. 그렇다면 언제, 얼마나 자주 순찰을 해야할지와 순찰 중에 사고가 터졌을때 이를 

          어찌 해결해야 할지가 관건이다.

          

        - 데드락 발생 검사 빈도와 시점

• 프로세스들이 요청한 자원을 할당할 수 없을 때마다 실행 : 미친 짓이다. 오버헤드가 너무 크다.
• 주기적으로 실행 : 알맞은 주기 설정이 중요한데... 주기가 크면 데드락 발생시 프로세스들이 너무 많은 시간을 논다.

       

         - 데드락 복구 방법

• Check-Point & Rollback : 자원을 할당할때마다 체크포인트를 설정하고, 자원의 상태를 기록했다가 데드락 발생시 복구
• Kill  Process : 현실적인 방법,, 걍 문제 일으킨 놈을 죽이고, 그놈이 사용중이던 자원을 해제하여 데드락 해결

                                                   < 데드락 해결법 비교 >

항목	데드락 방지	데드락 회피	데드락 탐지, 복구	무대책
자원 활용률	낮음	중간	높음	높음
실행 오버헤드	낮음	높음	중간	없음
데드락 복구 주체	불필요	불필요	운영체제	시스템 관리자
데드락 유지 기간	없다	없다	짧다