Intro

I would like to share classical problem with philosophers. This classic problem shows the various elements of parallelism. The complexity of the implementation of the task lies in the fact that a simple implementation can go into a hopeless state. The problem is defined like this:

In ancient times, wealthy philanthropists invited five eminent philosophers to visit. Each of them was given a room in which they could engage in their professional activity—thinking. There was also a common dining room, where there was a large round table, and five chairs around it. Each chair had a plaque with the name of the philosopher who was supposed to sit on it. To the left of each philosopher was a golden fork, and in the center of the table was a large bowl of spaghetti, which was constantly replenished. As befits philosophers, they spent most of their time in thought. But one day they felt hungry and went to the dining room. Everyone sat down on their chair, took a fork and stuck it into the bowl of spaghetti. But the nature of tangled spaghetti is such that a second fork is needed to push the spaghetti into the mouth. That is, the philosopher also needed a fork to his right. The philosophers put down their forks and got up from the table, continuing to think. After all, the fork can only be used by one philosopher at a time. If another philosopher wants to take it, then he will have to wait until she is released.

Solution

Let’s look at a simple example of solving this problem:

The philosopher takes the fork in his left hand. Then he takes the fork in his right hand. Eating. Puts the forks in place. Now imagine this as a sequence of actions of philosophers:

Philosopher 1 begins to execute the algorithm, takes the fork in his left hand. Philosopher 2 begins to execute the algorithm, takes the fork in his left hand. Philosopher 3 begins to execute the algorithm, takes the fork in his left hand. Philosopher 4 begins to execute the algorithm, takes the fork in his left hand. Philosopher 5 begins to execute the algorithm, takes the fork in his left hand. …?

All forks are busy and no one can start eating! Hopeless state (deadlock). There are various ways to solve this problem.

Rust example

use std::thread;
use std::sync::{Mutex, Arc};

struct Table {
    forks: Vec<Mutex<()>>,
}

struct Philosopher {
    name: String,
    left: usize,
    right: usize,
}

impl Philosopher {
    fn new(name: &str, left: usize, right: usize) -> Philosopher {
        Philosopher {
            name: name.to_string(),
            left: left,
            right: right,
        }
    }

    fn eat(&self, table: &Table) {
        let _left = table.forks[self.left].lock().unwrap();
        thread::sleep_ms(1000); // Applies a 'simultaneity fudge factor'
        let _right = table.forks[self.right].lock().unwrap();

        println!("{} is eating.", self.name);

        thread::sleep_ms(1000);

        println!("{} is done eating.", self.name);
    }
}

fn main() {
    let table = Arc::new(Table { forks: vec![
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
        Mutex::new(()),
    ]});

    let philosophers = vec![
        Philosopher::new("Judith Butler", 0, 1),
        Philosopher::new("Gilles Deleuze", 1, 2),
        Philosopher::new("Karl Marx", 2, 3),
        Philosopher::new("John Locke", 3, 4),
        Philosopher::new("Michel Foucault", 0, 4),
    ];

    let handles: Vec<_> = philosophers.into_iter().map( |philosopher| {
        let table = table.clone();

        thread::spawn(move || {
            philosopher.eat(&table);
        })
    }).collect();

    for handle in handles {
        handle.join().unwrap();
    }
}

Golang example

package main

import (
	"fmt"
	"time"
	"sync"
	"os"
	"bufio"
	"math/rand"
)


type diner struct {
	thinkTimeSecs int
	eatTimeSecs int
	free []chan bool
	done []chan bool
	n int
 	c  *sync.Cond
	started chan int
	randomize bool
}

func newDiner(n int,eatTime int,thinkTime int,randomize bool) *diner {

	d := new(diner)
	d.n = n
	// first create n fork channels and philo channels as communication between forks and philosophers
	d.free = make([]chan bool,n)
	d.done = make([]chan bool,n)

	d.c = sync.NewCond(&sync.Mutex {} )

	d.thinkTimeSecs = thinkTime
	d.eatTimeSecs = eatTime
	d.randomize = randomize

	// make a buffered channel
	d.started = make(chan int,n)
	
	for i:=0;i<n;i++{
		d.free[i] = make(chan bool)
		d.done[i] = make(chan bool)
	}
	return d
}


func (d *diner) start() {

	for i:=0;i<d.n;i++ {
		think := d.getTime(d.thinkTimeSecs)
		eat := d.getTime(d.eatTimeSecs)
		go d.fork(i)
		go d.philo(i,think,eat)
	}
	

	
}

func (d *diner) getTime(tSec int) time.Duration {
	
	//return a random time between 0 to t

	if(d.randomize) {
		return  time.Millisecond * time.Duration(rand.Intn(tSec * 1000))
	}
	return  time.Millisecond * time.Duration(tSec * 1000)
}


func (d *diner) philo(p int,think time.Duration,eat time.Duration) {

	
	for {
		// think time
		//fmt.Printf("%d,think\n",p)
		time.Sleep(think)
		fmt.Printf("%d,hungry\n",p)


		
		left := false
		right := false
		// check if we can left fork
		select {
		case left = <- d.free[p]:
			break
		default:
			left = false
			break
		}

		if !left {
			fmt.Printf("%d,missed\n",p)
			continue
		}
		
		//try and get right one
		select {
		case right = <- d.free[((p+1)%d.n)]:
			break
		default:
			right = false
			break
		}

		if !right {
			// then free left as well
			d.done[p] <- true
			fmt.Printf("%d,missed\n",p)
			continue
		}

		if left && right {
			// eat and then release
			fmt.Printf("%d,eat\n",p)
			time.Sleep(eat)
			// indicate done
			d.done[p] <- true
			d.done[((p+1)%d.n)] <- true
		}

	}

}

func (d *diner) fork(f int) {

	for {

	// indicate that the fork is free
	d.free[f] <- true

	
	//fmt.Printf("Waiting for fork %d to be done\n",f)
	//wait for it to be used and then released
	select {
	case <- d.done[f]:
		break
	}
	}
	
}

func main() {

d := newDiner(10,2,1,true)
	d.start()

	reader := bufio.NewReader(os.Stdin)
	//fmt.Print("Enter text: ")
	text, _ := reader.ReadString('\n')
	fmt.Println(text)
}

Waiter (Dispatcher)

A relatively simple solution to the problem is achieved by adding a waiter near the table. Philosophers must wait for the waiter’s permission before taking the fork. Since the waiter knows how many forks are currently in use, he can make decisions about the distribution of the forks and thus prevent philosophers from deadlocking. If four of the five forks are already in use, then the next philosopher to request a fork will have to wait for the waiter’s permission - which will not be received until the fork is released. It is assumed that the philosopher always tries to take the left fork first, and then the right one (or vice versa), which simplifies the logic. The waiter works like a semaphore, a concept introduced by Dijkstra in 1965.

To show how this solution works, let’s assume that the philosophers are labeled A through D in a clockwise direction. If philosophers A and B are eating, then four forks are occupied. Philosopher B sits between A and C, so that neither of the forks is available to him. At the same time, philosophers D and D have access to one unused fork between them. Let us suppose that philosopher G is hungry. If he immediately takes a free fork, then mutual blocking of philosophers becomes possible. If instead he asks permission from the waiter, he asks him to wait - and you can be sure that as soon as a pair of forks is free, then at least one philosopher will be able to take two forks. Thus, deadlock becomes impossible.

Resource Hierarchy

Another simple solution is achieved by assigning a partial order to the resources (in this case, the forks) and making the convention that the resources are requested in that order and returned in the reverse order. Also, there should not be two resources out of order used by the same unit of work.

Let the resources (forks) be numbered from 1 to 5, and each worker unit (philosopher) always takes the lowest-numbered fork first, and then the highest-numbered fork of the two available. Next, the philosopher puts down the fork with the higher number first, then the one with the smaller one. In this case, if four out of five philosophers take the lowest numbered fork at the same time, the highest possible numbered fork will remain on the table. Thus, the fifth philosopher will not be able to take a single fork. Moreover, only one philosopher will have access to the highest numbered fork, so he can eat with two forks. When he has finished using the forks, he will first place the higher numbered fork on the table, then the smaller one, thus allowing the other philosopher to pick up the missing fork and start eating.

While the resource hierarchy avoids deadlocks, this solution is not always practical, especially when the list of required resources is not known in advance. For example, if a work unit holds resource 3 and 5 and decides it needs resource 2, then it must release resource 5, then 3, then take possession of resource 2 and take resource 3 and 5 again. records in the database would not work efficiently if they needed to release all superscripted records before taking possession of the new record. This makes this method impractical.

Monitor based solution

The monitor algorithm implements a check, take, and put scheme and shares mutually exclusive locking. Note that philosophers who want to eat will not have forks.

If the monitor allows the eating philosopher to act, then the philosopher again takes possession of the first fork before taking the already free second one.

At the end of the current meal, the philosopher notifies the monitor that both forks are free.

It is worth noting that this monitor algorithm does not solve the problem of starvation. For example, philosopher B can wait indefinitely for his turn if philosophers A and B have overlapping eating periods all the time. To also ensure that no philosopher goes hungry, you can keep track of how many times a hungry philosopher hasn’t eaten when his neighbors put their forks on the table. If the number of times exceeds a certain limit, such a philosopher will go into the Starvation state and the monitor algorithm will force the fork acquisition procedure, fulfilling the condition of preventing starvation of any of the neighbors.

The philosopher, unable to take the forks because his neighbor is starving, is in a useful mode of waiting for his neighbor’s neighbor to finish eating. This additional dependency reduces concurrency. Increasing the Starvation threshold value reduces this effect.