Deadlock

Deadlock

두 개 이상의 프로세스가 한정된 자원을 요청하며 서로 자원을 획득하지 못해 Race Condition 이 발생하여 아무런 작업을 하지 못하는 상태

Race Condition ?

Memory를 공유하는 CPU가 여럿 있거나 Address Space를 공유하는 프로세스들이 여럿 있는 경우 접근하는 순서에 따라서 결과값이 달라지는 현상

• 커널 내부 데이터를 접근하는 루틴들 간에 발생

Race Condition이 발생하지 않는다는 관점

• Process는 자신의 메모리 공간에 있는 변수에만 접근하면 안생긴다?
• 사실은 CPU가 단 하나만 있어도 문제가 생길 수 있음, 즉 OS가 발생시키는 문제

Race Condition이 발생한다는 관점

• CPU가 하나만 있어도 Race Condition이 발생할 수 있음
• Process는 System Call을 통해 user mode에서 자기가 직접하지 못하는 일을 OS에게 요청하는 경우가 있음 -> 이 때 문제가 발생
  • Process가 kernel mode로 커널 내부 데이터를 사용하다가 Context Switch 일어난 경우
    • 해결법 : kernel mode에서 수행중일 때는 CPU를 선점하지 못하게 함
  • Process가 kernel mode로 커널 내부 데이터를 사용하다가 Interrupt가 CPU로 들어온 경우
    • 해결법 : 커널모드 중에는 인터럽트를 disable 시킴 -> 작업이 끝난 후 인터럽트 enable
  • 여러개의 CPU 에서 커널에 있는 Shared memory 를 사용하는 경우 (interrupt 를 disable 시키는 방법도 안통함)
    • 해결법 : 한번에 하나의 CPU만 들어가게 함(오버헤드 심함) / 커널 내부에 있는 공유 데이터에 접근할 때마다 사용중인 데이터에 대한 lock/unlock을 하는 방법(다른 데이터는 사용 가능 -> 오버헤드 줄임)

발생조건

아래 4가지 조건이 동시에 성립되어야 Deadlock이 발생한다.

1. 상호 배제 (Mutual Exclusion)
   Critical Section 에 한번에 하나의 프로세스 또는 스레드만 진입 가능하다.

2. 점유 대기 (Hold and wait)
   프로세스 또는 스레드가 자원을 최소한 하나를 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 자원을 할당받을 때 까지 대기한다.

3. 비선점 (No preemption)
   프로세스 또는 스레드가 다른 프로세스 또는 스레드의 점유 자원을 선점(preemption)하지 않는다. (이미 할당된 자원을 강제로 빼앗지 않는다.)

4. 순환 대기 (Circular wait)
   두 개 이상의 프로세스 또는 스레드가 순환 형태로 자원을 대기하고 있어야 한다.

Deadlock 해결방법

1) 교착상태 예방

Deadlock 의 발생 필요 조건 4 가지 중 하나를 성립하지 않도록 하는 방법이다.
교착상태 예방의 문제점은 시스템의 처리량이나 효율성이 감소한다는 점이다.

• 상호 배제 부정
  한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있게 한다. 하지만 일반적으로 어떤 자원들은 근본적으로 공유가 불가능하기 때문에 이 방법을 사용하기는 힘들다.
• 점유 대기 부정
  프로세스 실행에 필요한 모든 자원을 프로세스 실행 전에 한번에 할당한다. 하지만 두 가지 문제점이 있다. 첫째는 많은 자원이 할당되고 나서 오랫동안 사용되지 않아 자원의 이용률이 낮다는 것이고, 두번째는 필요로 하는 자원이 이미 다른 프로세스에게 할당되어 있을 수 있기 때문에 발생하는 기아상태이다.
• 비선점 부정
  프로세스가 자원을 요청했을 때 다른 프로세스가 자원을 할당해 점유할 수 없는 상태일 때, 해당 자원을 선점할 수 있도록 한다.
• 순환 대기 부정
  자원을 순환 형태로 대기하지 않도록 한 방향으로만 자원을 요구할 수 있도록 한다. 고유한 번호를 할당해 순서대로 자원을 요구하도록 할 수 있다.

2) 교착상태 회피

각 자원마다 최대 자원 개수를 자원을 할당하기 전에 파악해서 Deadlock 발생 가능성을 검사하고 발생할 가능성이 없을 때 자원을 할당하는 방법이다. 대표적으로 Banker's Algorithm 을 많이 사용한다.

3) 교착상태 탐지 및 회복

• 교착상태 탐지
  • Allocation, Request, Available 등으로 시스템에 교착 상태가 발생했는지를 탐색한다. 자원 할당 그래프를 통해 탐지하기도 한다.
• 교착상태 회복
  • 프로세스 종료
    교착상태의 프로세스를 모두 중지시키거나, 교착상태가 제거될 때 까지 프로세스를 하나씩 중지시키는 방법이 있다. 하지만, 프로세스를 중지 시키는 것은 무조건적인 해결을 보장하지 않는다. 예를 들어 파일을 갱신하는 도중에 중지되면 해당 파일은 부정확한 상태로 남는다. 따라서 중지 시 유발되는 비용이 최소인 프로세스를 중지시켜야 한다.
  • 자원 선점
    교착상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당하고 해당 프로세스를 일시정지 시키는 방법이다.