Deadlock

Deadlock?

여러 개의 프로세스나 스레드가 서로 상대방의 자원을 점유하고 있어 더 이상 진행할 수 없는 상태입니다. 말 그대로 교착상태!

일어나지 않을 사건을 기다리며 무한정 진행이 멈춰 버리는 상황은 왜 발생하는 걸까요?

발생 이유

원형 식탁에서 식사를 하려는 철학자 5명이 있습니다.
이때, 아래의 순서에 따라 음식을 먹게됩니다.

1. 계속 생각을 하다나 왼쪽 포크가 사용 가능하면 집어 들기
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어 들기
3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사하기
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓기
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓기
6. 1번부터 반복하기

한 두명만 하고 있을땐, 별 문제 없이 진행되겠지만, 5명이 모두 다같이 진행할 경우... 2번에서 막히게 됩니다.
5명이 모두 왼손에 포크를 집고 존재하지 않는 오른쪽 포크를 무한정 기다리는 겁니다.

이때 이러한 무한 대기가 발생하는 원인으로 여러가지를 생각 해볼 수 있습니다.

1. 상호 배제: 포크를 한번에 한 명의 철학자만 이용하게 함
   -> 두명의 철학자가 같이 포크를 이용한다면 해결 될 수 있습니다.

2. 점유 및 대기: 왼쪽 포크를 들고 오른쪽 포크를 기다림
   -> 왼쪽 포크 이용 완료 후 제자리에 돌려놓고 오른쪽 포크를 이용하게 된다면 해결 될 수 있습니다.

3. 비선점: 한 철학자가 가진 포크를 뺏지 못합니다.
   -> 예의 없는 철학자가 다른 철학자의 포크를 뺏어 음식을 먹으면 해결 할 수 있습니다.

4. 원형 대기: 포크를 점유하고 다른 포크를 기다리는 형태가 원의 형태로 그려집니다.
   -> 모든 포크에 1번 부터 5번까지 번호를 붙이고, 철학자들이 번호가 낮은 포크에서 높은 포크 순으로 집어들게 한다면 원형 대기는 발생하지 않습니다.

직접 해결해보기

철학자 문제를 코드로 직접 작성하여 해결해보겠습니다.
먼저 철학자가 테이블에 둘러 앉아있는 경우입니다.

다음과 같이 구현을 진행합니다.

• 포크를 Semaphore객체로 생성해 각각의 포크를 하나의 스레드만 사용할 수 있도록 제한합니다.
• 객체 생성시 철학자의 인덱스 번호와, 왼쪽 포크와 오른쪽 포크를 가리키는 Semaphore객체를 인자로 전달합니다.
• 객체 생성 후, start함수를 호출하여 각 철학자 객체를 스레드로 실행시킵니다.

import threading
import time


class Philosopher(threading.Thread):
    def __init__(
        self,
        index: int,
        left_fork: threading.Semaphore,
        right_fork: threading.Semaphore,
    ):
        threading.Thread.__init__(self)
        self.index = index
        self.left_fork = left_fork
        self.right_fork = right_fork

    def run(
        self,
    ) -> None:  # Thread를 실행할때 start() 함수를 호출하면, Thread 클래스 내부의 run() 함수가 호출됩니다.
        print(f"철학자 {self.index}: 배가 고프다")
        self.dine()

    def dine(self) -> None:
        # 왼쪽 포크를 집는다
        print(f"철학자 {self.index}: 왼쪽 포크를 집으려고 대기중")
        self.left_fork.acquire()
        print(f"철학자 {self.index}: 왼쪽 포크를 집음")
        time.sleep(1)
        # 오른쪽 포크를 집고
        print(f"철학자 {self.index}: 오른쪽 포크를 집으려고 대기중")
        self.right_fork.acquire()
        print(f"철학자 {self.index}: 오른쪽 포크를 집음")
        time.sleep(1)

        # 식사
        print(f"철학자 {self.index}: 식사중")
        time.sleep(2)

        # 오른쪽 포크를 놓고
        self.right_fork.release()
        print(f"철학자 {self.index}: 오른쪽 포크를 놓음")
        time.sleep(1)
        # 왼쪽 포크를 놓음
        self.left_fork.release()
        print(f"철학자 {self.index}: 왼쪽 포크를 놓음")
        time.sleep(1)

        print(f"철학자 {self.index}: 식사 완료! 배부르다")


if __name__ == "__main__":
    number_of_philosophers = 5
    forks = [threading.Semaphore() for n in range(number_of_philosophers)]
    philosophers = [
        Philosopher(
            i,
            forks[i % number_of_philosophers],
            forks[(i + 1) % number_of_philosophers],
        )
        for i in range(number_of_philosophers)
    ]
    for philosopher in philosophers:
        philosopher.start()
    for philosopher in philosophers:
        philosopher.join()

해결 방법

1. 한명의 철학자만 오른쪽 포크부터 집고 먹기
   만약 첫번째 철학자가 오른쪽 포크를 선점 후 왼쪽 포크를 선점하려 할 때, 해당 왼쪽 포크는 마지막 철학자의 오른쪽 포크로 순서가 되지 않았기에 아무도 선점하지 않아 문제 없이 두 자원 모두 선점이 가능합니다.
   그렇기 때문에 첫번째 철학자가 먼저 식사를 하고 난 후 마지막 철학자부터 두번째 철학자까지 역순으로 식사를 완료하게 됩니다.

if self.index == 0:
            # 오른쪽 포크를 집고
            print(f"철학자 {self.index}: 오른쪽 포크를 집으려고 대기중")
            self.right_fork.acquire()
            print(f"철학자 {self.index}: 오른쪽 포크를 집음")
            time.sleep(1)
            # 왼쪽 포크를 집는다
            print(f"철학자 {self.index}: 왼쪽 포크를 집으려고 대기중")
            self.left_fork.acquire()
            print(f"철학자 {self.index}: 왼쪽 포크를 집음")
            time.sleep(1)

        else:
            # 왼쪽 포크를 집는다
            print(f"철학자 {self.index}: 왼쪽 포크를 집으려고 대기중")
            self.left_fork.acquire()
            print(f"철학자 {self.index}: 왼쪽 포크를 집음")
            time.sleep(1)
            # 오른쪽 포크를 집고
            print(f"철학자 {self.index}: 오른쪽 포크를 집으려고 대기중")
            self.right_fork.acquire()
            print(f"철학자 {self.index}: 오른쪽 포크를 집음")
            time.sleep(1)

2. 오른쪽 선점에 실패할 경우 왼쪽 까지 놓고 다시 시도해 보기
   오른쪽 포크를 다른 철학자가 선점하고 있을 경우 왼쪽까지 모두 놓고 기다렸다가 다시 시도한다면 식사를 마친 철학자의 포크를 선점할 가능성이 있어 해결이 가능합니다.

    def dine(self) -> None:
        # 왼쪽 포크를 집는다
        print(f"철학자 {self.index}: 왼쪽 포크를 집으려고 대기중")
        self.left_fork.acquire()
        print(f"철학자 {self.index}: 왼쪽 포크를 집음")
        time.sleep(1)
        # 오른쪽 포크를 집고
        print(f"철학자 {self.index}: 오른쪽 포크를 집으려고 대기중")

        if not self.right_fork.acquire(timeout=1):
            self.left_fork.release()
            print(f"철학자 {self.index}: 왼쪽 포크를 놓음")
            time.sleep(1)
            self.left_fork.acquire()
            print(f"철학자 {self.index}: 왼쪽 포크를 집음")
            self.right_fork.acquire()
            print(f"철학자 {self.index}: 오른쪽 포크를 집음")

그러면 또 다른 해결방법에는 어떤 것이 있을까요?

해결 방법

1. 교착 상태 회피

• 교착 상태가 발생하지 않을 정도로만 조심 조심 할당하는 방식 입니다.
• 교착 상태는 할당 할 수 있는 자원이 충분한 상태에서 프로세스가 한 두개의 적은 자원만을 요구할 경우 발생하지 않습니다.
• 그렇기 때문에 안전 상태를 유지할 수 있도록 자원을 할당해야 합니다.

  안전 상태: 모든 프로세스가 정상적을 자원을 할당 받고 종료 될 수 있는 상태
  불안전 상태: 교착 상태가 발생 가능한 상황
  안전 순서열: 교착 없이 안전하게 프로세스들에 자원을 할당 할 수 있는 순서

위와 같은 상황에서 안전 상태로 할당을 위해서는 P2->P1->P3순서로 진행이 필요합니다.

먼저 P2에 남은 자원을 모두 할당하고, P2에 할당했던 자원들을 모두 회수 후 P1에 할당하고, 마지막으로 P3에 할당함으로써 교착 상태를 회피하며 모든 프로세스를 실행합니다.

2. 교착 상태 검출 후 회복
   회피를 하였음에도 교착 상태가 발생하였을 경우, 결국 상태 발생을 인정하고, 사후 조치를 실행해야 합니다.
   1) 선점을 통한 회복
   : 교착 상태가 해결 될때까지 한 프로세스 씩 자원을 몰아줍니다.
   2) 프로세스 강제 종료
   : 교착 상태가 해결 될 때까지 프로세스를 하나씩 죽입니다.