/*
 * CMPU-377
 * 
 * Go implementation of Dining Philosophers
 * This and more example Go programs found at: 
 * https://godoc.org/github.com/thomas11/csp
 * (last accessed: 4/1/2019)
 */

package main

import (
  "fmt"
  "time"
)

// 5.3 Dining Philosophers (Problem due to E.W. Dijkstra)
//
// > "Problem: Five philosophers spend their lives thinking and eating. The
// philosophers share a common dining room where there is a circular table
// surrounded by five chairs, each belonging to one philosopher. In the
// center of the table there is a large bowl of spaghetti, and the table is
// laid with five forks (see Figure 1). On feeling hungry, a philosopher
// enters the dining room, sits in his own chair, and picks up the fork on
// the left of his place. Unfortunately, the spaghetti is so tangled that
// he needs to pick up and use the fork on his right as well. When he has
// finished, he puts down both forks, and leaves the room. The room should
// keep a count of the number of philosophers in it."
//
// The dining philosophers are famous in Computer Science because they
// illustrate the problem of deadlock. As Hoare explains, "The solution
// given above does not prevent all five philosophers from entering the
// room, each picking up his left fork, and starving to death because he
// cannot pick up his right fork."

func S53_DiningPhilosophers(runFor time.Duration) {

	// The room is a goroutine that listens on a channel to signal "enter"
	// and one to signal "exit".
	enterRoom := make(chan int)
	exitRoom := make(chan int)
	room := func() {
		occupancy := 0
		for {
			select {
			case i := <-enterRoom:
				if occupancy < 4 {
					occupancy++
				} else {
					// If all philosophers sit down to eat, they starve.
					// Wait for someone to leave.
					fmt.Printf("%v wants to enter, but must wait.\n", i)
					<-exitRoom
					// Enter the room, occupancy stays the same.
					fmt.Printf("%v can finally enter!\n", i)
				}
			case <-exitRoom:
				occupancy--
			}
		}
	}

	// The forks are goroutines listening to pickup and putdown channels
	// like the room, but we need one channel per philosopher to
	// distinguish them so that we can match pickup and putdown of a fork.
	pickup := make([]chan int, 5)
	putdown := make([]chan int, 5)
	for i := 0; i < 5; i++ {
		pickup[i] = make(chan int)
		putdown[i] = make(chan int)
	}
	fork := func(i int) {
		for {
			select {
			case <-pickup[i]:
				<-putdown[i]
			case <-pickup[abs(i-1)%5]:
				<-putdown[abs(i-1)%5]
			}
		}
	}

	// Thinking and eating are sleeps followed by a log message so we know
	// what's going on.
	think := func(i int) {
		time.Sleep(2 * time.Second)
		fmt.Printf("%v thought.\n", i)
	}
	eat := func(i int) {
		time.Sleep(1 * time.Second)
		fmt.Printf("%v ate.\n", i)
	}

	// A philosopher leads a simple life.
	philosopher := func(i int) {
		for {
			think(i)
			enterRoom <- i
			pickup[i] <- i
			pickup[(i+1)%5] <- i
			eat(i)
			putdown[i] <- i
			putdown[(i+1)%5] <- i
			exitRoom <- i
		}
	}

	// Launch the scenario.
	go room()
	for i := 0; i < 5; i++ {
		go fork(i)
	}
	for i := 0; i < 5; i++ {
		go philosopher(i)
	}

	time.Sleep(runFor)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func main() {
  S53_DiningPhilosophers(time.Minute)
}