/* * 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) }