[운영체제] 교착상태

교착 상태란 ?
일어나지 않을 일을 무한정 기다리느라 진행이 멈춘 상태

🎈 식사하는 철학자 문제

철학자들이 모두 왼쪽 포크를 집어들고 생각을 하고 있다면, 오른쪽 포크를 사용할 수 있을 때까지 영원히 기다려야 한다.

import time
from multiprocessing import Process, Array


def phd(phd_id: int, forks: Array):
    while True:
        # 1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다
        left = phd_id
        while not forks[left]:
            continue
        forks[left] = False
        print(f"{phd_id} 번 철학자가 왼쪽 포크를 들었습니다")

        # 2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다
        time.sleep(3)
        right = (phd_id + 1) % len(forks)
        while not forks[right]:
            continue
        forks[right] = False
        print(f"{phd_id} 번 철학자가 오른쪽 포크를 들었습니다")

        # 3. 모두 집어들었으면 먹는다. 드세요 예...

        # 4. 오른쪽 포크를 내려놓는다.
        forks[right] = True
        print(f"{phd_id} 번 철학자가 오른쪽 포크를 내려놨습니다")

        # 5. 왼쪽 포크를 내려놓는다.
        forks[left] = True
        print(f"{phd_id} 번 철학자가 왼쪽 포크를 내려놨습니다")


if __name__ == '__main__':
    number_of_phd = 5
    shared_forks = Array("b", [True] * 5)

    processes = []
    for i in range(number_of_phd):
        process = Process(target=phd, args=(i, shared_forks))
        process.start()
        processes.append(process)

    for process in processes:
        process.join()

🎈 교착상태

프로그래밍에서 프로세스는 철학자, 공유 자원은 포크에 빗대어 볼 수 있다.

• 프로세스A: 자원A를 점유한 채 프로세스B가 자원B 사용을 끝낼 때까지 기다린다.
• 프로세스B: 자원B를 점유한 채 프로세스A가 자원A 사용을 끝낼 때까지 기다린다.

🎈 자원 할당 그래프

교착 상태 해결을 위해서는 먼저 상황을 정확히 표현해보아야 하는데, 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

사각형은 자원의 종류, 사각형 안의 점은 자원의 개수이다. 프로세스가 자원을 사용중이라면 자원 -> 프로세스 (검정) 화살표를 그리고, 자원을 기다리고 있으면 프로세스 -> 자원 (빨강) 화살표를 그린다.

교착 상태에서의 자원 할당 그래프는 위처럼 순환 구조를 가진다.

🎈 교착 상태 발생 조건

상호 배제, 점유와 대기, 비선점, 원형 대기
네가지 조건을 모두 만족할 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제 : 한 자원을 한 프로세스만 사용할 수 있을 때
• 점유와 대기 : 자원을 점유한 채 다른 자원을 기다리는 형태일 때
• 비선점 : 다른 프로세스의 자원을 강제로 빼앗지 못할 때
• 원형 대기 : 자원 할당 그래프가 원의 형태(순환 구조)를 가질 때