Solving the Dining Philosophers Problem with systemd - Part 3

This is part 3 of a 3-part series where we solve the Dining Philosophers concurrency problem using just UNIX, systemd and some bash scripting!

In part 2 we created multiple philosophers using separate user ids, got them to take their seat in the dining room and even pick up their initial forks¹.

Now we need to implement the core part of the dining philosopher’s problem - the conflict resolution layer - and that means we need an appropriate algorithm.

We’ll be using a variant of the Chandry/Misra “hygiene” solution. Our initial setup of the forks ensures that the graph between the philosopher nodes and the fork edges is acyclical. Each of the transformations from now on will maintain that acyclical form, avoiding a deadlock.

When a philosopher gets hungry (i.e. reaches the systemd hungry target), they check if they have both forks. If not, they need to ask their neighbouring philosophers for a fork.

For each request for a fork they receive, they make a simple decision:

• if they are thinking and they have the fork, they delete the fork and offer the fork to their neighbour by sending them a message
• otherwise, they ignore the request

For each fork offer received from a neighbour, a fork is created. Forks can only be acquired as a result of these offers and thereby with the permission of the neighbour. This both maintains the acyclical nature of the fork graph and avoids starvation (systemically and metaphorically).

Once a philosopher has two forks they enter the eating state and set a time in the future when they will start thinking again.

Before they enter the thinking state, the forks are deleted and they are transferred to neighbours by sending them a fork offer message.

Now to implement this in the Unix Programming Environment.

The veritable sendmail and mailutils

The philosophers will send messages to each other using Unix mail, provided by the sendmail daemon. This is how users communicated with each other on multi-user Unix machines back in the good old days before social media.

The sendmail daemon has a deserved reputation for being a devil to configure properly. Fortunately, we can use it out of the box because modern cloud servers are encased in system-level firewalls that prevent external access.

We’ll use sendmail’s rather useful ability to pipe received messages into a script. By placing a mail processor command in the .forward file for each philosopher we create a simple, but effective, event-driven message system.

The mail processor uses a bit of sed magic to strip out the subject and isolate who the messages are from. Then for each pair, it invokes a mail task and logs any output to the local0 syslog facility with a ‘mail-tasks’ identifier so we can isolate them later.

#!/bin/sh
set -e
sed -n '/^From: /s/^From: .* <\(.*\)@.*$/\1/p
/^Subject: /s/^Subject: \(.*\)$/"\1"/p' |
    xargs -r -n 2 -- /usr/local/bin/mail-tasks |
    logger -p local0.info -t mail-tasks

Sending messages is a simple wrapper around the standard mail command that gives us the ‘fork-request’ and ‘fork-response’ messages we need. First the ‘fork-request’

#!/bin/sh
# fork-request
if [ "$#" -eq 0 ]
then
    echo "Usage: ${0##*/} name..."
    exit 64
fi
for word
do
    echo "Asking ${word} for the shared fork"
    mail -E'unset nullbodymsg' -s 'Fork Request' "${word}" < /dev/null
done

and the ‘fork-response’:

#!/bin/sh
# fork-response
if [ "$#" -eq 0 ]
then
    echo "Usage: ${0##*/} name..."
    exit 64
fi
for word
do
    echo "Sending ${word} our shared fork"
    mail -E'unset nullbodymsg' -s 'Fork Response' "${word}" < /dev/null
done

Update the eating service

The first update we make is to the eating-food service. When it starts, we still run the consumption script but now we want to run the fork-release script when the service shuts down. This nicely wraps the eating timer without introducing any further systemd units.

[Unit]
Description=Eating Food
ConditionPathIsDirectory=/home/share/dining-room
PartOf=eating.target

[Service]
Type=oneshot
SyslogFacility=local0
RemainAfterExit=yes
ExecStart=/usr/local/bin/consumption
# Send forks to neighbours after eating
ExecStop=/usr/local/bin/fork-release

We add the RemainAfterExit setting to the unit so that it enters the active state and will be shut down (running the ExecStop command) when the timer triggers the transition to the thinking target.

The fork release script is very simple:

# fork-release
#!/bin/sh
set -e

echo "Releasing forks"
rm -f ${HOME}/forks/*
echo "Transferring forks"
neighbours | xargs -r response-fork

and it neatly cleans up the spare fork that was left over from the initialisation process, once that philosopher has completed their first meal.

The neighbours script finds out who is in the seats on either side of a philosopher, including from the head to the foot of the table. It does this using a count function that determines the number of seats dynamically within the shell.

# count fileglob
count() {
    case ${1##*/} in
        \*)
            echo 0
            ;;
        *)
            echo $#
            ;;
    esac
}

seat=$(my-dining-seat)
max=$(count ${diningroom}/seats/*)
max=$((max + base))
right_index=$((seat + 1))
if [ "${right_index}" -gt "${max}" ]
then
    right_index=$((base + 1))
fi
left_index=$((seat - 1))
if [ "${left_index}" -eq "${base}" ]
then
    left_index=${max}
fi

The fork check

The hungry timer is replaced by a fork-check service. The unit has a few interesting features:

[Unit]
Description=Fork Check
ConditionPathIsDirectory=/home/share/dining-room
CollectMode=inactive-or-failed
OnSuccess=eating.target
OnFailure=fork-request.service
After=hungry.target

[Service]
Type=oneshot
ExecStart=/usr/local/bin/fork-check
SyslogFacility=local0

This is a branch unit that triggers other processes depending on whether the check succeeds or fails. We update CollectMode so systemd garbage collects the unit even if it has failed.

When the check succeeds it transitions to the eating target, and on failure it requests the forks from neighbours.

fork-check looks for two forks in the philosopher’s fork area and returns a temporary failure if they are not there.

diningroom=/home/share/dining-room
forkarea=${HOME}/forks
base=10

lfork=$(my-dining-seat)
max=$(count ${diningroom}/seats/*)
max=$((max + base))
rfork=$((lfork + 1))
if [ "${rfork}" -gt "${max}" ]
then
    rfork=$((base + 1))
fi

if [ -w "${forkarea}/${lfork}" ] &&
   [ -w "${forkarea}/${rfork}" ]
then
    echo "I have two forks"
    exit 0
fi
# Return EX_TEMPFAIL
exit 75

The core of fork-request asks a neighbour for the fork if we don’t have it by sending them a request message:

# ask_for_fork fork_file fork_num neighbour_name
ask_for_fork() {
    if [ -w "${1}" ]
    then
        echo "I already have fork #${2}"
    else
        echo "I don't have fork #${2}"
        request-fork "${3}"
    fi
}

Processing the mail tasks

The mail-tasks script uses different branches based on the mail subject to manage specific types of messages. This allows for easy extension by assigning the task of handling a particular message to a specific script. Adding new message types in the future simply involves adding another branch in the case statement.

#!/bin/sh
set -e

if [ "$#" -ne 2 ]
then
    echo "Usage: ${0##*/} username subject"
    exit 64
fi

case "$2" in
Fork\ Request)
    exec mail-task-fork-request "$1"
    ;;
Fork\ Response)
    exec mail-task-fork-response "$1"
    ;;
*)
    echo "Unknown mail request ${2} from ${1}"
    echo "Discarding mail"
    exit 0
esac

Each message handler is a self-contained script for each particular task. A fork request is rejected if the philosopher is hungry or eating. We ask systemd what state it is in a manner that is as atomic as possible. If the philosopher is hungry, do a backup check to see if they have two forks and can start eating:

echo "Received fork request from $1"
# Try to be as atomic as possible
if systemctl --user --quiet is-active eating.target hungry.target
then
    if systemctl --user --quiet is-active hungry.target
    then
        echo "while hungry."
        echo "I have priority"
        try_to_eat
        exit 0
    else
        echo "while eating."
        echo "I'll respond when I've finished eating."
        exit 0
    fi
fi

otherwise, we’ll remove the fork and send it to their neighbour, after a last-second check that the philosopher is still thinking.

remove_fork() {
    if [ -w "${HOME}/forks/$1" ]
    then
        # Final check we're in the right state before removing forks
        if systemctl --user --quiet is-active eating.target hungry.target
        then
            echo "Transistioned away from thinking while processing"
            echo "Ignoring request"
            exit 0
        else
            rm "${HOME}/forks/$1"
            echo "Released fork #$1"
        fi
    else
        echo "I don't have fork #$1"
        echo "Ignoring request"
        exit 0
    fi
}

The fork response is a little more straightforward. First, grab the fork that has been sent through. Then, if the philosopher is hungry, see if they have both forks and can start eating:

echo "Received fork response from $1"
if [ "${other}" -eq "${left_index}" ]
then
    grab_fork "${seat}"
elif [ "${other}" -eq "${right_index}" ]
then
    grab_fork "${right_index}"
else
    echo "Fork Response error"
    echo "Unexpected seat ${other} for $1"
    echo "I'm seat ${seat}, left is ${left_index}, right is ${right_index}"
    echo "Discarding mail"
    exit 0
fi
if systemctl --user --quiet is-active hungry.target
then
        try_to_eat
fi
exit 0

Installation

Now we’re ready to run the full simulation. To try it yourself, install the code from the repo. Log in as an admin user on an Ubuntu server, clone the repo and run the setup script

ubuntu@srv-2q8eh:~$ git clone --depth 1 --branch part-3 git@github.com:brightbox/systemd-dining.git
Cloning into 'systemd-dining'...
...
ubuntu@srv-2q8eh:~$ cd systemd-dining/
ubuntu@srv-2q8eh:~/systemd-dining$ sudo ./setup.sh
Adding required packages
...
Installing simulation

Run the simulation

Create the philosophers:

ubuntu@srv-2q8eh:~/systemd-dining$ xargs -L 1 sudo /usr/local/sbin/create_philosopher < philosophers

Open the dining room:

ubuntu@srv-5o1ic:~/systemd-dining$ sudo open_dining_room

Stop the simulation

Close the dining room:

ubuntu@srv-5o1ic:~/systemd-dining$ sudo close_dining_room

Remove the philosophers:

ubuntu@srv-2q8eh:~/systemd-dining$ awk '{print $1}' philosophers | xargs sudo /usr/local/sbin/remove_philosopher

Interrogate the simulation

While running, all of the Unix process tools are available. Of particular use is the journalctl command and the convenience script npcjournal which allows you to look at a single philosopher by user name.

ubuntu@srv-4mujm:~$ npcjournal kant
Nov 27 18:49:31 fork-release[1531112]: Sending nietzsche our shared fork
Nov 27 18:49:31 contemplation[1531145]: Currently contemplating the perspective that time and space are not
Nov 27 18:49:31 contemplation[1531145]: external conditions but subjective forms of our intuition.
Nov 27 18:49:46 hunger[1531542]: Getting hungry...

Or follow their activity:

ubuntu@srv-4mujm:~$ npcjournal -f hegel
Nov 29 12:07:41 consumption[802905]: Eating...
Nov 29 12:07:49 mail-tasks[803067]: Received fork request from socrates
Nov 29 12:07:49 mail-tasks[803067]: while eating.
Nov 29 12:07:49 mail-tasks[803067]: I'll respond when I've finished eating.
Nov 29 12:07:52 fork-release[803154]: Releasing forks
Nov 29 12:07:52 fork-release[803154]: Transferring forks
Nov 29 12:07:52 fork-release[803163]: Sending socrates our shared fork
Nov 29 12:07:53 fork-release[803163]: Sending mill our shared fork

Perhaps you want to see what a philosopher has been thinking about:

ubuntu@srv-4mujm:~$ npcjournal --since=today --identifier=contemplation wittgenstein
Nov 29 00:01:14 contemplation[3981849]: Currently contemplating the view that philosophy is not a theory but
Nov 29 00:01:14 contemplation[3981849]: an activity, an approach to language that transforms our conceptual
Nov 29 00:01:14 contemplation[3981849]: framework.
Nov 29 00:02:11 contemplation[3983193]: Currently contemplating the belief that philosophy should be concerned
Nov 29 00:02:11 contemplation[3983193]: with clarifying language rather than solving metaphysical puzzles.
Nov 29 00:03:08 contemplation[3984372]: Currently contemplating the notion that the structure of language reflects
Nov 29 00:03:08 contemplation[3984372]: the structure of reality, and philosophical problems are linguistic
Nov 29 00:03:08 contemplation[3984372]: in nature.

Or maybe what messages have been sent by the mail system between the philosophers:

ubuntu@srv-4mujm:~$ journalctl --since=today --facility=mail
Nov 29 00:00:03 srv-4mujm sendmail[3980626]: 3AT003YC3980626: from=plato@srv-4mujm.gb1.brightbox.com, size=113, >
Nov 29 00:00:03 srv-4mujm sm-mta[3980627]: 3AT003KE3980627: from=<plato@srv-4mujm.gb1.brightbox.com>, size=399, >
Nov 29 00:00:03 srv-4mujm sendmail[3980626]: 3AT003YC3980626: to=schlegel, ctladdr=plato@srv-4mujm.gb1.brightbox>
Nov 29 00:00:03 srv-4mujm sendmail[3980635]: 3AT003BX3980635: from=plato@srv-4mujm.gb1.brightbox.com, size=113, >
Nov 29 00:00:03 srv-4mujm sm-mta[3980628]: 3AT003KE3980627: to=|/usr/local/bin/mail-processor, ctladdr=<schlegel>
Nov 29 00:00:03 srv-4mujm sm-mta[3980646]: 3AT003W33980646: from=<plato@srv-4mujm.gb1.brightbox.com>, size=399, >
Nov 29 00:00:03 srv-4mujm sendmail[3980635]: 3AT003BX3980635: to=socrates, ctladdr=plato@srv-4mujm.gb1.brightbox>
Nov 29 00:00:03 srv-4mujm sm-mta[3980649]: 3AT003W33980646: to=|/usr/local/bin/mail-processor, ctladdr=<socrates>o

And if you can’t remember their name, we can look that up:

ubuntu@srv-4mujm:~$ finger -p wittgenstein
Login: wittgenstein   			Name: Ludwig Wittgenstein
Directory: /home/wittgenstein       	Shell: /bin/bash
Last login Sun Nov 26 08:12 (UTC) on pts/2
Mail forwarded to |/usr/local/bin/mail-processor
No mail.

Gathering the statistics from the journal for how long each philosopher stays hungry is left as an exercise for the reader. Let me know how you get on.

Epilogue

And there we have it, a short run around some of the older, esoteric features of the Unix Programming Environment combined with some of the newer systemd features. With these tools, we have built a Dining Philosophers solution using little more than a few shell scripts. Not a compiler in sight.

If you come up with any potential improvements to the system, please drop an issue or a pull request on the repo. I’m sure it can be improved in many ways.