I have been grinding Go for a while. I find the Tour of Go is a good resource to start knowing Go. But I notice only going through this is not enough to conquer this language. So I start to find some problems or side project to implement. Dining philosopher problem simulation is my first implementation using Go. As my first implementation in Go, I learned a lot from other github source code. Before I go into the implementation, I would like to cover my understanding of Go concurrency model.
Go Concurrency Model
Go has its own concurrency model as one of its advantages, which is easily understood and implemented.
In stead of using some resource variable like mutex or semaphore to manage concurrent processes,
Go introduces the concepts of Go routines and channels. Go routines can be thought of as lightweight
threads but not really depend on hardware. Simply using go func demonstrates func will execute on
Go routines concurrently. And channels are used for the communication among Go routines. A Go routine
can send and receive information from others via channels. With such design, we can implement
solutions with concurrency easily.
Dining Philosopher Problem
Problem
Dining Philosopher Problem is an interesting problem reflecting concurrency and resource management in programming. Suppose we have five philosophers around a table and each of them holds only one fork. But each one requires two forks in hands simultaneously to eat. If each philosopher is competitive, they are not happy to borrow their forks to their neighbors. The dining will not finished, which can be treated as a deadlock in programming. There is an another situation where each philosophers is willing to lend their forks to others. But if they give up their own forks and pick up their neighbors’ forks at exactly same time, they still cannot eat, which is treated as a live lock in programming. The solution to finish this meal is allowing each philosophers to hold their own forks for a random length of time. After timing out, if they still cannot borrow their neighbors’ forks, they have to give up their own forks letting their neighbors to use. Under this way, these philosophers can finish this meal finally.
Implementation
The idea using Go implementation is making dining behavior as Go routines and using channels to demonstrate the availability of each philosopher’s fork.
First, we define a Philosopher struct and a function to make Philosopher struct.
type Philosopher struct {
name string
fork chan bool
neighbor *Philosopher
}
func makePhilosopher(name string, neighbor *Philosopher) *Philosopher {
phil := &Philosopher{name, make(chan bool, 1), neighbor}
phil.fork <- true
return phil
}
Next, we define a think and eat function to simulate thinking and eating. They just let
program sleep for a random period of time.
func (phil *Philosopher) think() {
fmt.Printf("%v is thinking.\n", phil.name)
time.Sleep(time.Duration(rand.Int63n(1e9)))
}
func (phil *Philosopher) eat() {
fmt.Printf("%v is eating. \n", phil.name)
time.Sleep(time.Duration(rand.Int63n(1e9)))
}
Then, we define a getForks function and this is the core one to include how each philosopher gets
forks from their neighbors.
func (phil *Philosopher) getForks() {
// Declare a channal indicating timeout
timeout := make(chan bool, 1)
go func() { time.Sleep(1e9); timeout <- true }()
// taking the fork; fork is not available
<-phil.fork
fmt.Printf("%v got his fork. \n", phil.name)
select {
// if the neighbor's fork is availble, return, ready to eat
case <-phil.neighbor.fork:
fmt.Printf("%v got %v's fork.\n", phil.name, phil.neighbor.name)
fmt.Printf("%v has two fork.\n", phil.name)
return
// after amount of time the philosopher taking up his own fork, the
// philosopher has to put the fork down letting others to use
// then think for a while and try get fork operation again
case <-timeout:
phil.fork <- true
phil.think()
phil.getForks()
}
}
And we have to have a returnForks function.
func (phil *Philosopher) returnForks() {
// after a philosopher finish eating, making his fork channel
// and his neighbor's fork channel demeonstrate available again
phil.fork <- true
phil.neighbor.fork <- true
}
Finally we combine all above function together as a dine function.
func (phil *Philosopher) dine(announce chan *Philosopher) {
// the whole procedure of dining
phil.think()
phil.getForks()
phil.eat()
phil.returnForks()
announce <- phil
}
In main function, the most special line is go phil.dine(anncounce). This line of code allows
philosophers start dining concurrently.
func main() {
names := []string{"Phil 1", "Phil 2", "Phil 3", "Phil 4",
"Phil 5", "Phil 6", "Phil 7", "Phil 8"}
philosophers := make([]*Philosopher, len(names))
var phil *Philosopher
// link all philosophers together
for i, name := range names {
phil = makePhilosopher(name, phil)
philosophers[i] = phil
}
// let the first philosopher to be the neighbor of the last philosopher
philosophers[0].neighbor = phil
fmt.Printf("There are %v philosophers sitting at a table.\n", len(names))
fmt.Println("They each have one fork, and must borrow from their neighbor to eat.")
announce := make(chan *Philosopher)
for _, phil := range philosophers {
// dine occur concurrently
go phil.dine(announce)
}
// the announce channel will get the philosophers who finish dining sequentially in concurrent dine()
// print out them concurrently
for i := 0; i < len(names); i++ {
phil := <-announce
fmt.Printf("%v is done dining. \n", phil.name)
}
}
When we run go run main.go, the result is like the following.
For the whole version of code, check here