Sunday, October 30, 2011

Go solution for the Dining philosophers problem

I spent part of the sunday solving the Dining Philosophers using Go. The given solution is based in the description for the problem present in The Little Book of Semaphores:

The Dining Philosophers Problem was proposed by Dijkstra in 1965, when dinosaurs ruled the earth. It appears in a number of variations, but the standard features are a table with five plates, five forks (or chopsticks) and a big bowl of spaghetti.

There are some constraints:
  • Only one philosopher can hold a fork at a time
  • It must be impossible for a deadlock to occur
  • It must be impossible for a philosopher to starve waiting for a fork
  • It must be possible for more than one philosopher to eat at the same time
No more talk, here is my solution for the problem:
package main

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

type Fork struct {
    sync.Mutex
}

type Table struct {
    philosophers chan Philosopher
    forks []*Fork
}

func NewTable(forks int) *Table {
    t := new(Table)
    t.philosophers = make(chan Philosopher, forks - 1)
    t.forks = make([]*Fork, forks)
    for i := 0; i < forks; i++ {
        t.forks[i] = new(Fork)
    }
    return t
}

func (t *Table) PushPhilosopher(p Philosopher) {
    p.table = t
    t.philosophers <- data-blogger-escaped-0="" data-blogger-escaped-1="" data-blogger-escaped-2="" data-blogger-escaped-3="" data-blogger-escaped-4="" data-blogger-escaped-:="range" data-blogger-escaped-_="" data-blogger-escaped-able="" data-blogger-escaped-anscombe="" data-blogger-escaped-artin="" data-blogger-escaped-chan="" data-blogger-escaped-e9="" data-blogger-escaped-eat="" data-blogger-escaped-eating...="" data-blogger-escaped-eter="" data-blogger-escaped-f="" data-blogger-escaped-fed.="" data-blogger-escaped-fed="" data-blogger-escaped-fmt.printf="" data-blogger-escaped-for="" data-blogger-escaped-func="" data-blogger-escaped-getforks="" data-blogger-escaped-go="" data-blogger-escaped-heidegger="" data-blogger-escaped-homas="" data-blogger-escaped-index="" data-blogger-escaped-int="" data-blogger-escaped-is="" data-blogger-escaped-leftfork.lock="" data-blogger-escaped-leftfork.unlock="" data-blogger-escaped-leftfork="" data-blogger-escaped-leibniz="" data-blogger-escaped-len="" data-blogger-escaped-lizabeth="" data-blogger-escaped-lombard="" data-blogger-escaped-main="" data-blogger-escaped-make="" data-blogger-escaped-n="" data-blogger-escaped-nagel="" data-blogger-escaped-name="" data-blogger-escaped-ork="" data-blogger-escaped-ottfried="" data-blogger-escaped-p.eat="" data-blogger-escaped-p.fed="" data-blogger-escaped-p.getforks="" data-blogger-escaped-p.name="" data-blogger-escaped-p.putforks="" data-blogger-escaped-p.table.popphilosopher="" data-blogger-escaped-p.table.pushphilosopher="" data-blogger-escaped-p.table="nil" data-blogger-escaped-p.think="" data-blogger-escaped-p="" data-blogger-escaped-philosopher="" data-blogger-escaped-philosopherindex="" data-blogger-escaped-philosophers="" data-blogger-escaped-popphilosopher="" data-blogger-escaped-pre="" data-blogger-escaped-putforks="" data-blogger-escaped-return="" data-blogger-escaped-rightfork.lock="" data-blogger-escaped-rightfork.unlock="" data-blogger-escaped-rightfork="" data-blogger-escaped-s="" data-blogger-escaped-string="" data-blogger-escaped-struct="" data-blogger-escaped-t.forks="" data-blogger-escaped-t="" data-blogger-escaped-table="" data-blogger-escaped-think="" data-blogger-escaped-thinking...="" data-blogger-escaped-time.sleep="" data-blogger-escaped-type="" data-blogger-escaped-was="">
Any feedback is very welcome.