[Go] 식사하는 철학자들 문제

티스토리 뷰

Go/코딩 하기

[Go] 식사하는 철학자들 문제

piatoss 2023. 9. 29. 16:45

🍝 식사하는 철학자들 문제란?

'식사하는 철학자들 문제'는 병렬 컴퓨터 시스템에서 발생하는 공유 자원 접근 문제를 직관적으로 설명하기 위한 문제입니다.

식사하는 철학자들 문제는 다음과 같이 정의됩니다.

철학자들: 다섯 명의 철학자가 동그란 식탁 주위에 둘러앉습니다.
포크: 각 철학자들 사이에 포크가 하나씩, 총 다섯 개의 포크가 식탁 위에 있습니다.
생각과 식사: 철학자들은 생각하는 시간과 식사하는 시간을 번갈아 가며 보냅니다. 생각 중에는 포크를 사용하지 않고, 식사 중에는 왼쪽과 오른쪽에 놓여 있는 두 개의 포크를 사용해야 합니다.
문제: 철학자가 식사를 하기 위해서는 자신의 왼쪽과 오른쪽에 있는 두 개의 포크가 필요하지만, 포크는 공유 자원이기 때문에 만약 모든 철학자가 동시에 식사를 시작하려고 하면 데드락(Deadlock) 상태에 빠질 수 있습니다.

출처: https://ko.wikipedia.org/wiki/식사하는_철학자들_문제

🔗 데드락이란?

데드락(Deadlock)은 다수의 프로세스나 스레드가 서로가 필요로 하는 자원을 얻을 수 없어 무한히 기다리거나 진행할 수 없는 상태를 의미합니다. 데드락이 발생하면 프로그램이 다운되거나 운영체제가 멈출 수 있습니다.

데드락이 발생하려면 다음 네 가지 조건을 만족해야 합니다.

상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스나 스레드에 의해서만 사용될 수 있어야 합니다. 다른 프로세스나 스레드는 해당 자원을 사용할 수 없어야 합니다.
점유 및 대기(Hold and Wait): 프로세스나 스레드는 최소한 하나의 자원을 점유한 상태에서 다른 자원을 얻기 위해 대기합니다. 이때, 이미 점유한 자원을 반납하지 않고 대기하게 되는 것이 문제입니다.
비선점(No Preemption): 다른 프로세스나 스레드가 이미 점유한 자원을 강제로 빼앗을 수 없어야 합니다. 자원을 반납할 때까지 기다려야 합니다.
순환 대기(Circular Wait): 프로세스나 스레드 간에 자원을 점유하고 대기하는 순환 형태의 사이클이 형성되어야 합니다. 예를 들어, 프로세스 A가 프로세스 B가 점유한 자원을 기다리고, 프로세스 B는 프로세스 C가 점유한 자원을 기다리며, 프로세스 C는 프로세스 A가 점유한 자원을 기다리는 식입니다.

모든 철학자들이 생각하고 식사하는 것을 제외한 어떠한 말과 행동도 할 수 없는 상태에서 동시에 자신의 왼쪽에 있는 포크를 집어드는 상황을 가정해 봅시다. 이러한 상황에 데드락이 발생하는 조건을 대입해 보면 다음과 같이 설명할 수 있습니다.

상호 배제(Mutual Exclusion): 철학자들은 자신이 집어든 포크를 다른 철학자와 공유할 수 없습니다.
점유 및 대기(Hold and Wait): 철학자들은 왼쪽 포크를 집어든 상태에서 자신의 오른쪽에 있는 포크를 오른쪽에 앉은 철학자가 내려놓을 때까지 무한정 대기합니다.
비선점(No Preemption): 철학자들은 다른 철학자가 집어든 포크를 강제로 빼앗을 수 없습니다.
순환 대기(Circular Wait): 모든 철학자들은 자신의 오른쪽에 있는 포크를 기다리면서 순환 사이클을 형성합니다.

데드락이 발생하여 어떤 철학자도 식사를 하지 못하게 되면 결국 모든 철학자들이 굶어 죽게 될 것입니다. 즉, 모든 프로세스 또는 스레드가 필요한 자원을 영원히 얻지 못하여 무한정 대기하는 기아 현상(Starvation)이 발생하는 것입니다.

📝 문제 풀이

각 철학자는 다음의 연속된 과정을 통해 식사를 합니다.

일정 시간 생각을 한다.
왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
오른쪽 포크를 내려놓는다.
왼쪽 포크를 내려놓는다.
식사를 마치지 않았다면 1번으로 돌아간다.

이때 모든 철학자가 동시에 왼쪽 포크를 집어 들게 된다면, 앞서 살펴본 바와 같이 데드락이 발생하기 때문에 데이크스트라의 해결책을 통해 문제를 풀어보겠습니다.

데이크스트라의 해결책: 각각의 철학자를 P₁, P₂, P₃, P₄, P₅라고 하고, 각 철학자의 왼쪽 포크를 f₁, f₂, f₃, f₄, f₅라고 했을 때, P₅를 제외한 네 명은 먼저 f_n을 집은 후 f_n+1을 집는 방식을 취합니다. 그리고 P₅는 이와 반대로 f₁을 먼저 집은 후 f₅를 집습니다.

1. 포크 (공유 자원)

type Fork struct{ sync.Mutex } // 포크는 뮤텍스로 구현

포크는 sync.Mutex 구조체를 임베딩한 Fork 구조체로 정의하였습니다. 포크를 집어 들어 사용할 때는 Lock 메서드를 호출하여 다른 철학자가 포크에 접근하는 것을 제한하고, 사용을 마치고 나면 Unlock 메서드를 호출하여 다른 철학자가 포크에 접근하는 것을 허용할 수 있습니다.

2. 철학자 (프로세스)

const HUNGER = 3 // 철학자들이 식사를 하는 횟수

var (
	ThinkTime = time.Second     // 철학자들이 생각하는 시간
	EatTime   = time.Second * 2 // 철학자들이 식사하는 시간
	EtcTime   = time.Second     // 기타 시간
)

type Philosopher struct {
	name                string // 철학자의 이름
	leftFork, rightFork *Fork  // 철학자가 사용하는 포크 (왼쪽, 오른쪽)
}

func (p *Philosopher) Eat() {
	fmt.Printf("%s가 자리에 앉음\n", p.name)
	time.Sleep(EtcTime)

	// 식사를 hunger번 반복
	for i := HUNGER; i > 0; i-- {
		// 1. 일정 시간 생각을 한다.
		fmt.Printf("%s(이)가 생각 중\n", p.name)
		time.Sleep(ThinkTime)

		// 2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
		p.leftFork.Lock()
		fmt.Printf("%s(이)가 왼쪽 포크를 들었음\n", p.name)

		// 3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
		p.rightFork.Lock()
		fmt.Printf("%s(이)가 오른쪽 포크를 들었음\n", p.name)

		// 4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
		fmt.Printf("%s(이)가 식사 중\n", p.name)
		time.Sleep(EatTime)

		// 5. 오른쪽 포크를 내려놓는다.
		p.rightFork.Unlock()
		fmt.Printf("%s(이)가 오른쪽 포크를 내려놓음\n", p.name)

		// 6. 왼쪽 포크를 내려놓는다.
		p.leftFork.Unlock()
		fmt.Printf("%s(이)가 왼쪽 포크를 내려놓음\n", p.name)

		// 7. 식사를 마치지 않았다면 1번으로 돌아간다.
		time.Sleep(EtcTime)
	}

	fmt.Println(p.name, "식사 완료!")
	time.Sleep(time.Second)

	fmt.Printf("%s(이)가 자리에서 일어남\n", p.name)
}

철학자는 이름과 왼쪽, 오른쪽 포크를 필드로 가지는 Philosopher 구조체로 정의하였습니다. 철학자는 HUNGER 만큼 식사를 반복합니다. 이때 공유 자원인 포크는 식사를 마치고 나면 Unlock 메서드를 호출하여 식탁에 내려놓아야 다른 철학자가 식사를 마칠 수 있습니다.

3. 식탁 (스케줄러)

type RoundTable struct{ sync.WaitGroup } // 원형 테이블은 WaitGroup으로 구현

func (t *RoundTable) Serve(philosopher *Philosopher) {
	t.Add(1) // 철학자 한 명을 추가
	go func() {
		// 철학자가 식사를 마치면 Done()을 호출
		philosopher.Eat()
		t.Done()
	}()
}

식탁은 sync.WaitGroup 구조체를 임베딩한 RoundTable 구조체로 정의하였습니다. 철학자들이 식사하는 과정이 goroutine으로 실행되므로 철학자들이 식사하는 와중에 main 함수가 종료되면서 프로그램이 종료되는 상황이 발생할 수 있습니다. 이를 방지하기 위해 sync.WaitGroup의 Wait 메서드를 사용하여 모든 철학자들이 식사를 마칠 때까지 기다리게 하는 로직을 추가하였습니다.

4. DiningPhilosophers 함수

func DiningPhilosophers() {
	table := RoundTable{
		WaitGroup: sync.WaitGroup{},
	} // 원탁을 만든다.

	names := []string{"플라톤", "아리스토텔레스", "칸트", "헤겔", "라이프니츠"} // 철학자들의 이름

	count := len(names)

	forks := make([]*Fork, count)

	// 포크를 만든다.
	for i := 0; i < count; i++ {
		forks[i] = new(Fork)
	}

	for i := 0; i < count-1; i++ {
		philosopher := Philosopher{names[i], forks[i], forks[i+1]} // i번째 철학자는 i번 포크와 i+1번 포크를 사용하며 왼쪽 포크를 먼저 집어듬

		table.Serve(&philosopher) // i번째 철학자가 식사를 시작
	}

	philosopher := Philosopher{names[count-1], forks[0], forks[count-1]} // 마지막 철학자는 오른쪽 포크를 먼저 집어듬
	table.Serve(&philosopher)                                            // 마지막 철학자가 식사를 시작

	table.Wait() // 모든 철학자들이 식사를 마칠 때까지 대기
}

식사하는 철학자들 문제를 해결하는 핵심 함수입니다. 먼저 원탁과 5명의 철학자의 이름, 5개의 포크를 준비합니다. 그리고 데이크스트라의 해결책에 따라 4명의 철학자는 왼쪽 포크를 먼저 집어 들고 마지막 철학자는 오른쪽 포크를 먼저 집어 들게 합니다.

5. main 함수

func main() {
	start := time.Now()
	fmt.Println("식사하는 철학자들 문제")
	fmt.Println("==================================================")

	DiningPhilosophers()

	fmt.Println("테이블 위의 모든 철학자들이 식사를 마쳤습니다.")
	fmt.Println("==================================================")
	fmt.Println("실행 시간:", time.Since(start))
}

main 함수는 DiningPhilosophers 함수를 호출하고 실행 시간을 출력합니다.

6. main 함수 실행 결과

$ go run -race .
식사하는 철학자들 문제
==================================================
아리스토텔레스가 자리에 앉음
헤겔가 자리에 앉음
칸트가 자리에 앉음
플라톤가 자리에 앉음
라이프니츠가 자리에 앉음
라이프니츠(이)가 생각 중
아리스토텔레스(이)가 생각 중
헤겔(이)가 생각 중
칸트(이)가 생각 중
플라톤(이)가 생각 중
라이프니츠(이)가 왼쪽 포크를 들었음
칸트(이)가 왼쪽 포크를 들었음
라이프니츠(이)가 오른쪽 포크를 들었음
라이프니츠(이)가 식사 중
헤겔(이)가 왼쪽 포크를 들었음
아리스토텔레스(이)가 왼쪽 포크를 들었음
라이프니츠(이)가 오른쪽 포크를 내려놓음
라이프니츠(이)가 왼쪽 포크를 내려놓음
플라톤(이)가 왼쪽 포크를 들었음
헤겔(이)가 오른쪽 포크를 들었음
헤겔(이)가 식사 중
라이프니츠(이)가 생각 중
헤겔(이)가 오른쪽 포크를 내려놓음
헤겔(이)가 왼쪽 포크를 내려놓음
칸트(이)가 오른쪽 포크를 들었음
칸트(이)가 식사 중
헤겔(이)가 생각 중
칸트(이)가 오른쪽 포크를 내려놓음
헤겔(이)가 왼쪽 포크를 들었음
칸트(이)가 왼쪽 포크를 내려놓음
헤겔(이)가 오른쪽 포크를 들었음
헤겔(이)가 식사 중
아리스토텔레스(이)가 오른쪽 포크를 들었음
아리스토텔레스(이)가 식사 중
칸트(이)가 생각 중
아리스토텔레스(이)가 오른쪽 포크를 내려놓음
아리스토텔레스(이)가 왼쪽 포크를 내려놓음
칸트(이)가 왼쪽 포크를 들었음
헤겔(이)가 오른쪽 포크를 내려놓음
헤겔(이)가 왼쪽 포크를 내려놓음
칸트(이)가 오른쪽 포크를 들었음
칸트(이)가 식사 중
플라톤(이)가 오른쪽 포크를 들었음
플라톤(이)가 식사 중
헤겔(이)가 생각 중
아리스토텔레스(이)가 생각 중
플라톤(이)가 오른쪽 포크를 내려놓음
플라톤(이)가 왼쪽 포크를 내려놓음
칸트(이)가 오른쪽 포크를 내려놓음
칸트(이)가 왼쪽 포크를 내려놓음
라이프니츠(이)가 왼쪽 포크를 들었음
라이프니츠(이)가 오른쪽 포크를 들었음
라이프니츠(이)가 식사 중
아리스토텔레스(이)가 왼쪽 포크를 들었음
아리스토텔레스(이)가 오른쪽 포크를 들었음
아리스토텔레스(이)가 식사 중
헤겔(이)가 왼쪽 포크를 들었음
칸트(이)가 생각 중
플라톤(이)가 생각 중
라이프니츠(이)가 오른쪽 포크를 내려놓음
라이프니츠(이)가 왼쪽 포크를 내려놓음
플라톤(이)가 왼쪽 포크를 들었음
아리스토텔레스(이)가 오른쪽 포크를 내려놓음
아리스토텔레스(이)가 왼쪽 포크를 내려놓음
헤겔(이)가 오른쪽 포크를 들었음
플라톤(이)가 오른쪽 포크를 들었음
플라톤(이)가 식사 중
칸트(이)가 왼쪽 포크를 들었음
헤겔(이)가 식사 중
아리스토텔레스(이)가 생각 중
라이프니츠(이)가 생각 중
헤겔(이)가 오른쪽 포크를 내려놓음
헤겔(이)가 왼쪽 포크를 내려놓음
플라톤(이)가 오른쪽 포크를 내려놓음
칸트(이)가 오른쪽 포크를 들었음
라이프니츠(이)가 왼쪽 포크를 들었음
라이프니츠(이)가 오른쪽 포크를 들었음
칸트(이)가 식사 중
아리스토텔레스(이)가 왼쪽 포크를 들었음
라이프니츠(이)가 식사 중
플라톤(이)가 왼쪽 포크를 내려놓음
헤겔 식사 완료!
플라톤(이)가 생각 중
칸트(이)가 오른쪽 포크를 내려놓음
칸트(이)가 왼쪽 포크를 내려놓음
아리스토텔레스(이)가 오른쪽 포크를 들었음
아리스토텔레스(이)가 식사 중
헤겔(이)가 자리에서 일어남
라이프니츠(이)가 오른쪽 포크를 내려놓음
라이프니츠(이)가 왼쪽 포크를 내려놓음
플라톤(이)가 왼쪽 포크를 들었음
라이프니츠 식사 완료!
칸트 식사 완료!
라이프니츠(이)가 자리에서 일어남
아리스토텔레스(이)가 오른쪽 포크를 내려놓음
아리스토텔레스(이)가 왼쪽 포크를 내려놓음
칸트(이)가 자리에서 일어남
플라톤(이)가 오른쪽 포크를 들었음
플라톤(이)가 식사 중
아리스토텔레스 식사 완료!
아리스토텔레스(이)가 자리에서 일어남
플라톤(이)가 오른쪽 포크를 내려놓음
플라톤(이)가 왼쪽 포크를 내려놓음
플라톤 식사 완료!
플라톤(이)가 자리에서 일어남
테이블 위의 모든 철학자들이 식사를 마쳤습니다.
==================================================
실행 시간: 24.012129417s

main 함수를 실행해 본 결과, 모든 철학자들이 정상적으로 식사를 마쳤습니다. -race 플래그를 사용하여 race condition이 존재하는지도 검사를 해보았는데 별다른 출력이 없는 것을 보면 없는 것을 알 수 있습니다.

7. 테스트

package main

import (
	"os"
	"sync"
	"testing"
)

func TestMain(m *testing.M) {
	main()           // main 함수 실행
	os.Exit(m.Run()) // 테스트 실행
}

func TestDiningPhilosophers(t *testing.T) {
	cnt := 1000 // 테스트 횟수

	oldOut := os.Stdout // 원래의 표준 출력

	_, w, _ := os.Pipe() // 표준 출력을 감추기 위해 파이프를 생성

	os.Stdout = w // 표준 출력을 파이프로 변경

	wg := sync.WaitGroup{} // 테스트를 goroutine으로 병렬 실행하기 위해 WaitGroup을 사용

	ThinkTime = 0
	EatTime = 0
	EtcTime = 0

	for i := 0; i < cnt; i++ {
		wg.Add(1)

		go func() {
			defer wg.Done()
			DiningPhilosophers() // 테스트할 함수 실행
		}()
	}

	wg.Wait() // 모든 테스트가 끝날 때까지 대기

	// 표준 출력을 원래대로 복구
	_ = w.Close()

	os.Stdout = oldOut
}

생각하는 시간, 먹는 시간, 그 외의 시간 등을 0으로 조정해놓고 DiningPhilosophers 함수를 1000번 병렬 실행해 보았습니다. 이 때 표준 출력으로 너무 많은 양의 문자열이 출력되는 것을 방지하기 위해 임시로 표준 출력을 파이프로 변경했습니다.

테스트 실행 결과는 다음과 같습니다.

$ go test -v -race -cover .
...
=== RUN   TestDiningPhilosophers
--- PASS: TestDiningPhilosophers (1.86s)
PASS
coverage: 100.0% of statements
ok      dining-philosophers     26.889s coverage: 100.0% of statements

main 함수 실행 결과와 마찬가지로 병렬로 1000번 실행한 DiningPhilosophers 함수가 정상적으로 실행되며, race condition도 감지되지 않은 것을 확인할 수 있습니다.

🙏 마치며

go의 goroutine, sync.Mutex 그리고 sync.WaitGroup을 사용해 모든 철학자들이 포크를 적절하게 주고 받으며 식사를 마칠 수 있었습니다. 다음 게시물에서는 go의 채널을 활용하여 '잠자는 이발사 문제'를 해결해 보겠습니다.

🐱‍👤 전체 코드

GitHub - piatoss3612/practical-go

Contribute to piatoss3612/practical-go development by creating an account on GitHub.

github.com

📖 참고자료

식사하는 철학자들 문제 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전. 원탁에 둘러앉은 다섯 명의 철학자와 다섯 접시의 스파게티, 그리고 다섯 개의 포크 식사하는 철학자들 문제는 전산학에서 동시성과 교착 상태를 설명하는 예

ko.wikipedia.org

식사하는 철학자 문제 - 나무위키

예를 들어, 각 철학자들이 다음의 연속된 과정을 통해 식사를 한다고 생각해보자. 일정 시간 생각을 한다.왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.오른쪽

namu.wiki

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!

'Go > 코딩 하기' 카테고리의 다른 글

[Go] gRPC 파헤치기 - gRPC란? (0)	2023.10.11
[Go] 문자열과 바이트 슬라이스를 상호 변환하는 여러가지 방법 (0)	2023.10.01
[Go] 잠자는 이발사 문제 (0)	2023.09.30
[Go] 깃허브 프로필 최신 블로그 글 목록 자동으로 업데이트하기 (0)	2023.09.06
타입스크립트로 블록체인 만들기 in Go (0)	2023.08.21

최근에 올라온 글

최근에 달린 댓글

« 2025/01 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Total

Today

Yesterday

글 보관함

TAG more

개발 코어 강화 일지

티스토리 뷰