Dining Philosophers Golang


(FistOfJustice) #1

Hello,

I am working on the dining philosophers program from the Coursera Golang course from Univ. California Irvine.

I am running into a few problems with deadlocking (despite using Mutexes). There appears to be some issue with synchronization. The problem statement calls for the following:

Implement the dining philosopher’s problem with the following constraints/modifications.

  1. There should be 5 philosophers sharing chopsticks, with one chopstick between each adjacent pair of philosophers.
  2. Each philosopher should eat only 3 times (not in an infinite loop as we did in lecture)
  3. The philosophers pick up the chopsticks in any order, not lowest-numbered first (which we did in lecture).
  4. In order to eat, a philosopher must get permission from a host which executes in its own goroutine.
  5. The host allows no more than 2 philosophers to eat concurrently.
  6. Each philosopher is numbered, 1 through 5.
  7. When a philosopher starts eating (after it has obtained necessary locks) it prints “starting to eat <number>” on a line by itself, where <number> is the number of the philosopher.
  8. When a philosopher finishes eating (before it has released its locks) it prints “finishing eating <number>” on a line by itself, where <number> is the number of the philosopher.

Here is my code thus far:

package main

import (
	"fmt"
	"math/rand"

	"sync"
	"time"
)

var ch = make(chan int, 3)

type fork struct{ sync.Mutex }

type philosopher struct {
	id                  int
	leftFork, rightFork *fork
}

// Goes from thinking to hungry to eating and done eating then starts over.
// Adapt the pause values to increased or decrease contentions
// around the forks.
func (p philosopher) eat(n int) {

	say("thinking", p.id)
	randomPause(2)

	say("hungry", p.id)
	p.leftFork.Lock()
	p.rightFork.Lock()
	randomPause(5)

	say("eating", p.id)

	p.rightFork.Unlock()
	p.leftFork.Unlock()

	say("done eating", p.id)

	ch <- n

}

func randomPause(max int) {
	time.Sleep(time.Millisecond * time.Duration(rand.Intn(max*1000)))
}

func say(action string, id int) {
	fmt.Printf("Philosopher #%d is %s\n", id+1, action)
}

func init() {
	// Random seed
	rand.Seed(time.Now().UTC().UnixNano())
}

func main() {
	// How many philosophers and forks
	count := 5

	// Create forks
	forks := make([]*fork, count)
	for i := 0; i < count; i++ {
		forks[i] = new(fork)
	}

	// Create philospoher, assign them 2 forks and send them to the dining table
	philosophers := make([]*philosopher, count)
	for i := 0; i < count; i++ {
		philosophers[i] = &philosopher{
			id: i, leftFork: forks[i], rightFork: forks[(i+1)%count]}
		for j := 0; j < 3; j++ {
			go philosophers[i].eat(j)
		}
	}

	philoEat := make(chan int, 3)
	<-philoEat

}

I would appreciate any guidance. Thanks!


(FistOfJustice) #2

Update:

I have made some modifications to my code. However, it is not running concurrently. It seems to be running one goroutine or thread at a time. In this problem, typically two philosophers can be eating at the same whilst others are waiting to eat. Here is the modified code:

package main

import (
	"fmt"
	"math/rand"
	"os"

	"sync"
	"time"
)

type fork struct{ sync.Mutex }

type philosopher struct {
	id                  int
	leftFork, rightFork *fork
}

// Goes from thinking to hungry to eating and done eating then starts over.
// Adapt the pause values to increased or decrease contentions
// around the forks.
func (p philosopher) eat() {
	for j := 0; j < 3; j++ {
		p.leftFork.Lock()
		p.rightFork.Lock()
		randomPause(5)

		say("eating", p.id)

		p.rightFork.Unlock()
		p.leftFork.Unlock()

		say("finished eating", p.id)
	}

	os.Exit(0)

}

func randomPause(max int) {
	time.Sleep(time.Millisecond * time.Duration(rand.Intn(max*1000)))
}

func say(action string, id int) {
	fmt.Printf("Philosopher #%d is %s\n", id+1, action)
}

func init() {
	// Random seed
	rand.Seed(time.Now().UTC().UnixNano())
}

func main() {
	// How many philosophers and forks
	count := 5

	// Create forks
	forks := make([]*fork, count)
	for i := 0; i < count; i++ {
		forks[i] = new(fork)
	}

	// Create philospoher, assign them 2 forks and send them to the dining table
	philosophers := make([]*philosopher, count)
	for i := 0; i < count; i++ {
		philosophers[i] = &philosopher{
			id: i, leftFork: forks[i], rightFork: forks[(i+1)%count]}

		go philosophers[i].eat()

	}

	philoEat := make(chan int)
	<-philoEat

}

Here is the Output:

        $ go run diningphilosophers.go
        Philosopher #5 is eating
        Philosopher #5 is finished eating
        Philosopher #4 is eating
        Philosopher #4 is finished eating
        Philosopher #2 is eating
        Philosopher #2 is finished eating
        Philosopher #1 is eating
        Philosopher #1 is finished eating
        Philosopher #5 is eating
        Philosopher #5 is finished eating
        Philosopher #4 is eating
        Philosopher #4 is finished eating
        Philosopher #3 is eating
        Philosopher #3 is finished eating
        Philosopher #2 is eating
        Philosopher #2 is finished eating
        Philosopher #1 is eating
        Philosopher #1 is finished eating
        Philosopher #5 is eating
        Philosopher #5 is finished eating


    $ go run diningphilosophers.go
    Philosopher #3 is eating
    Philosopher #3 is finished eating
    Philosopher #1 is eating
    Philosopher #1 is finished eating
    Philosopher #5 is eating
    Philosopher #5 is finished eating
    Philosopher #4 is eating
    Philosopher #4 is finished eating
    Philosopher #3 is eating
    Philosopher #3 is finished eating
    Philosopher #2 is eating
    Philosopher #2 is finished eating
    Philosopher #1 is eating
    Philosopher #1 is finished eating
    Philosopher #5 is eating
    Philosopher #5 is finished eating
    Philosopher #4 is eating
    Philosopher #4 is finished eating
    Philosopher #3 is eating
    Philosopher #3 is finished eating

It is definitely not working properly as not all philosophers are eating 3 times.


(Johan Dahl) #3

This exit is run as soon as the first philosopher has eaten three times. And the program exits no matter how many times other has eaten.


(FistOfJustice) #4

@johandalabacka thanks for following up with me. When I remove the os.Exit(0), the program becomes deadlocked after the go routines are run have a look:

$ go run diningphilosophers.go
Philosopher #1 is eating
Philosopher #1 is finished eating
Philosopher #3 is eating
Philosopher #3 is finished eating
Philosopher #5 is eating
Philosopher #5 is finished eating
Philosopher #2 is eating
Philosopher #2 is finished eating
Philosopher #4 is eating
Philosopher #4 is finished eating
Philosopher #1 is eating
Philosopher #1 is finished eating
Philosopher #3 is eating
Philosopher #3 is finished eating
Philosopher #5 is eating
Philosopher #5 is finished eating
Philosopher #2 is eating
Philosopher #2 is finished eating
Philosopher #4 is eating
Philosopher #4 is finished eating
Philosopher #1 is eating
Philosopher #1 is finished eating
Philosopher #3 is eating
Philosopher #3 is finished eating
Philosopher #5 is eating
Philosopher #5 is finished eating
Philosopher #2 is eating
Philosopher #2 is finished eating
Philosopher #4 is eating
Philosopher #4 is finished eating
fatal error: all goroutines are asleep - deadlock!

goroutine 1 [chan receive]:
main.main()
        C:/Users/iokhamaf/Documents/Coursera/Course 3/Module 4/diningphilosophers.go:85 +0x2d4
exit status 2 

Here is the modification made (new code), 2 philosophers are still not eating at the same time:

package main

import (
	"fmt"

	"sync"
)

type fork struct{ sync.Mutex }

type philosopher struct {
	id                  int
	leftFork, rightFork *fork
}

// Goes from thinking to hungry to eating and done eating then starts over.
// Adapt the pause values to increased or decrease contentions
// around the forks.
func (p philosopher) eat() {
	for j := 0; j < 3; j++ {
		p.leftFork.Lock()
		p.rightFork.Lock()

		say("eating", p.id)

		p.rightFork.Unlock()
		p.leftFork.Unlock()

		say("finished eating", p.id)
	}

}

func say(action string, id int) {
	fmt.Printf("Philosopher #%d is %s\n", id+1, action)
}

func main() {
	// How many philosophers and forks
	var eatWgroup sync.WaitGroup
	count := 5

	// Create forks
	forks := make([]*fork, count)
	for i := 0; i < count; i++ {
		forks[i] = new(fork)
	}

	// Create philospoher, assign them 2 forks and send them to the dining table
	philosophers := make([]*philosopher, count)
	for i := 0; i < count; i++ {
		philosophers[i] = &philosopher{
			id: i, leftFork: forks[i], rightFork: forks[(i+1)%count]}
		eatWgroup.Add(1)
		go philosophers[i].eat()
		eatWgroup.Done()

	}
	eatWgroup.Wait()
	philoEat := make(chan int)
	<-philoEat

}

(Johan Dahl) #5

You must put the Done inside the go-routine otherwise it will be called just after the go-routine launches. So the waitgroup must be in a global variable, sent as parameter or you go on an anonymous function which first calls eat() and then Done()

package main

import (
	"fmt"
	"sync"
	"time"
)

type fork struct{ sync.Mutex }

type philosopher struct {
	id                  int
	leftFork, rightFork *fork
}

// Goes from thinking to hungry to eating and done eating then starts over.
// Adapt the pause values to increased or decrease contentions
// around the forks.
func (p philosopher) eat() {
	for j := 0; j < 3; j++ {
		p.leftFork.Lock()
		p.rightFork.Lock()

		say("eating", p.id)
		time.Sleep(time.Second)

		p.rightFork.Unlock()
		p.leftFork.Unlock()

		say("finished eating", p.id)
		time.Sleep(time.Second)
	}
	eatWgroup.Done()
}

func say(action string, id int) {
	fmt.Printf("Philosopher #%d is %s\n", id+1, action)
}

var eatWgroup sync.WaitGroup

func main() {
	// How many philosophers and forks

	count := 5

	// Create forks
	forks := make([]*fork, count)
	for i := 0; i < count; i++ {
		forks[i] = new(fork)
	}

	// Create philospoher, assign them 2 forks and send them to the dining table
	philosophers := make([]*philosopher, count)
	for i := 0; i < count; i++ {
		philosophers[i] = &philosopher{
			id: i, leftFork: forks[i], rightFork: forks[(i+1)%count]}
		eatWgroup.Add(1)
		go philosophers[i].eat()

	}
	eatWgroup.Wait()

}

The problem why your version doesn’t work is because go-routines runs until it encounters a blocking call like waiting for disk, network and similar. So running a go routine inside a tight loop will not give any time to other go routines unless you have more than one core so they can run in parallell. I moved the waitgroup to a global variable so it is easily accessible inside the functions and put in some sleep (both eating and contemplating takes time) so other go-routines has a chance to run.

Read more here https://codeburst.io/why-goroutines-are-not-lightweight-threads-7c460c1f155

Don’t interrupt!

The go runtime scheduler does cooperative scheduling, which means another goroutine will only be scheduled if the current one is blocking or done. Some of these cases are:

  • Channel send and receive operations, if those operations would block.
  • The Go statement, although there is no guarantee that new goroutine will be scheduled immediately.
  • Blocking syscalls like file and network operations.
  • After being stopped for a garbage collection cycle.