Dining Philosophers problem

dpp.go

package main

import (
	"context"
	"fmt"
	"sync"

	"github.com/vedhavyas/queue"
)

type fork struct {
	inUse bool
}

type forkSet struct {
	pid   int
	forks []*fork
}

func newForkSet(count int) []*forkSet {
	if count == 0 {
		panic("need at least one philosopher")
	}

	fc := count
	if count <= 2 {
		fc = 2
	}

	var forks []*fork
	for i := 0; i < fc; i++ {
		forks = append(forks, &fork{})
	}

	var sets []*forkSet
	for i := 0; i < count; i++ {
		set := new(forkSet)
		set.pid = i
		f1 := forks[i]
		f2 := forks[0]
		if i+1 < fc {
			f2 = forks[i+1]
		}
		set.forks = append(set.forks, f1, f2)
		sets = append(sets, set)
	}

	return sets
}

type waiter struct {
	forks map[int]*forkSet
	queue *queue.Queue
}

func newWaiter(count int) *waiter {
	fs := newForkSet(count)
	forks := make(map[int]*forkSet)
	for _, f := range fs {
		forks[f.pid] = f
	}

	return &waiter{
		forks: forks,
		queue: new(queue.Queue),
	}
}

func (w *waiter) assignFork(id int) bool {
	set := w.forks[id]
	if set.forks[0].inUse || set.forks[1].inUse {
		fmt.Printf("%d: thinking\n", id)
		return false
	}

	fmt.Printf("%d: eating\n", id)
	set.forks[0].inUse = true
	set.forks[1].inUse = true
	return true
}

func (w *waiter) unAssignFork(id int) {
	set := w.forks[id]
	set.forks[0].inUse = false
	set.forks[1].inUse = false
}

func (w *waiter) Listen(ctx context.Context, assign <-chan assignRequest, unAssign <-chan int) {
	for {
		select {
		case <-ctx.Done():
			fmt.Println("waiter done listening....")
			return

		case req := <-assign:
			got := w.assignFork(req.id)
			if !got {
				w.queue.Enqueue(req)
			}
			go func() { req.resp <- got }()

		case id := <-unAssign:
			w.unAssignFork(id)
			if w.queue.Len() < 1 {
				continue
			}

			w.queue.ResetRange()
			for {
				r := w.queue.Next()
				if r == nil {
					break
				}

				req := r.(assignRequest)
				got := w.assignFork(req.id)
				if got {
					w.queue.CutRangeItem()
					go func() { req.resp <- got }()
				}
			}
		}
	}
}

type assignRequest struct {
	id   int
	resp chan bool
}

type philosopher struct {
	id       int
	eatCount int
}

func (p *philosopher) StartDining(wg *sync.WaitGroup, assign chan<- assignRequest, unAssign chan<- int) {
	defer wg.Done()
	var count int
	req := assignRequest{
		id:   p.id,
		resp: make(chan bool),
	}

	assign <- req
	for got := range req.resp {
		if !got {
			continue
		}

		count++
		unAssign <- p.id
		if count >= p.eatCount {
			return
		}

		assign <- req
	}
}

func getPhils(count, maxEats int) []*philosopher {
	var phils []*philosopher
	for i := 0; i < count; i++ {
		phils = append(phils, &philosopher{id: i, eatCount: maxEats})
	}

	return phils
}

func main() {
	pcount := 5
	maxCount := 5

	phills := getPhils(pcount, maxCount)
	waiter := newWaiter(pcount)
	ctx, cancel := context.WithCancel(context.Background())

	assign := make(chan assignRequest, pcount)
	unAssign := make(chan int, pcount)
	go waiter.Listen(ctx, assign, unAssign)

	wg := new(sync.WaitGroup)
	wg.Add(len(phills))
	for _, p := range phills {
		go p.StartDining(wg, assign, unAssign)
	}

	wg.Wait()
	cancel()
}