교착상태(Deadlock)란

Critical Section(임계 영역)

멀티스레딩의 문제점에서 나오듯, 동일 자원(공유 변수 등)을 동시에 접근하는 작업을 실행하는 코드 영역을 Critical Section이라 칭한다.

데드락이란

데드락이란 두 개 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 얻기 위해 기다릴 때 무한 대기에 빠지는 현상을 일컫는다.
보통 멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 경쟁할 때 발생한다. 어떤 프로세스가 자원을 요청 했을 때 그 자원을 사용할 수 없는 상황이 발생할 수 있는데 그 때는 프로세스가 대기 상태로 들어가게 된다. 이렇게 대기 상태로 들어간 프로세스들이 실행 상태로 변경 될 수 없을 때 이러한 상황을 교착 상태라고 한다.

데드락의 발생조건

• 상호 배제(Mutual exclusion)

  • 한번에 프로세스 하나만 해당 자원을 사용할 수 있을 때.
    (프로세스들이 필요로 하는 자원에 대해서 배타적 통제권을 요구함)

• 점유 대기(Hold and wait)

  • 프로세스가 자원을 최소 하나 보유한 상태에서, 다른 프로세스의 자원을 점유하기 위해 대기함

• 비선점(No preemption)

  • 다른 프로세스에 이미 할당된 자원을 강제로 뺏을 수 없을 때
    (프로세스가 어떤 자원의 사용이 끝날 때까지 그 자원을 뺏을 수 없음)

• 순환 대기

  • 각 프로세스들이 순환형태로 다음 프로세스가 요구하는 자원을 갖고 있을때
  • 순환대기는 점유대기와 비선점을 만족해야만 성립함

4가지 조건 모두 만족해야함 교착상태가 발생함.

데드락 해결법

예방 / 회피 / 탐지 및 회복 이 존재한다.

데드락 예방

위에서 살펴본 데드락 발생조건 4가지 중 하나라도 발생하지 않게 하는 것.
자원의 낭비가 발생한다는 단점이 존재함.

• 상호 배제 부정

  • 한번에 여러 프로세스가 자원을 사용할 수 있게 함.(동기화 문제가 발생할 수 있음)

• 점유 대기 부정

  • 프로세스 실행전 필요한 자원을 모두 할당함.

• 비선점 부정

  • 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하게 함.

• 순환 대기 부정

  • 자원에 고유한 번호를 할당, 높은 우선순위의 프로세스가 해당 자원을 선점하게 함

데드락 예방법은 시스템 처리량과 효율성을 떨어트리는 단점이 발생할 수 있다.

데드락 회피

교착 상태가 발생하면 피해가는 방법.

은행원 알고리즘 (Banker’s Algorithm)

E,J,Dijkstra가 제안한 방법으로, 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법이다.

프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피한다.

시스템의 프로세스들이 데드락을 발생시키지 않으면서 자원을 모두에게 할당시켜 줄 수 있는 상태를 Safe sate = 안정상태 라고 말한다.
그리고 특정 순서로 작업할 때 데드락이 발생하지 않는 순서가 있다면 그것을 Safe sequence = 안전 순서라고 부른다.

안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함

자원 할당 그래프 알고리즘

점선으로 표시된 간선(Claim edge)은 프로세스가 자원을 미래에 요청할 수 있음을 의미.
그리고 해당 자원을 요청하는 경우 실선(Request edge)으로 바뀌게 된다.
자원을 할당받으면 방향이 반대인 간선(Assignment edge)이 된다.
만약 자원을 다 쓰고 반납하게 되면 다시 Claim edge로 바뀐다.

• Deadlock를 피하는 방법은, Request edge가 Assignment edge로 변경될 때 점선을 포함하여 사이클이 생기지 않는 경우에만 요청된 자원을 할당한다.

데드락 탐지 및 회복

예방이나 회피법을 사용하지 않을 때 사용

탐지 기법

자원할당 그래프를 통해서 사이클이 생겼는지를 확인하거나, 총 요청 자원의 수가 남은 자원의 수보다 적은 프로세스가 존재하지 않는다는 것을 이용하여 확인할 수 있다.

회복 기법

데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용합니다.

• 프로세스를 1개 이상 중단
  • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
  • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
• 자원 선점하기
  교착 상태의 프로세스를 일시정지 시키고 해당 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법

뮤텍스, 세마포어의 차이?

뮤텍스

여러 스레드를 사용하는 환경에서 자원에 대한 접근을 강제하기 위한 동기화 매커니즘
Boolean타입의 Lock변수를 사용하며, Lock을 건 스레드만이 해제할 수 있다.

• Sleep-Waiting 방식
  대기큐를 생성하여, 임계영역에 쓰레드가 이미 존재할 때 다른 스레드가 공유자원을 사용하려고 한다면 해당 쓰레드를 blocking하고 대기큐에 sleep시킨다.

SpinLock방식: 기다리고 있지만 끊임없이 물어보는 방식(busy-waiting)

Mutex-Nonblocking 모델로 볼 수 있다.

• 컨텍스트 스위칭(대기큐에 이동) 시간보다 예상 진입시간이 더 짧은가?
• 멀티코어 프로세스인가?
  위 두 사실에 해당한다면 Sleep-Waiting 방식보다 SpinLock사용이 더 좋을 수도 있다.

세마포어

멀티프로그래밍 환경에서 다수의 프로세스나 스레드의 여러 공유자원에 대한 접근을 제한하는 방법

• 세마포어 변수(0이상의 정수형 변수)를 통해 wait, signal을 관리한다.
• 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.