Solving the Dining Philosophers Problem with systemd - Part 2

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

In part 1, we created a simple state machine with systemd units and watched it do its thing by interrogating the journal. For part 2, we’ll use the multi-user capabilities of Linux and create a set of philosophers running independent processes.

Every process in Linux runs with a user identifier, plus a primary group and a list of secondary groups the user identifier is part of. Access control to resources within Linux is managed via this set of identifiers.

Creating a philosopher is a matter of adding a user ID, a group ID, and adding the user ID to a secondary group, philosophers, which we’ll use to control access to shared resources like dining seats and forks¹.

$ sudo -s
$ addgroup philosophers
$ adduser --disabled-password --shell /bin/bash --gecos "Immanuel Kant" kant 
Adding user `kant' ...
Adding new group `kant' (1002) ...
Adding new user `kant' (1001) with group `kant' ...
Creating home directory `/home/kant' ...
Copying files from `/etc/skel' ..
$ adduser kant philosophers
Adding user `kant' to group `philosophers' ...
Adding user kant to group philosophers
Done.
$ loginctl enable-linger kant

We can see the philosopher’s details using the finger command:

$ finger kant
Login: kant           			Name: Immanuel Kant
Directory: /home/kant               	Shell: /bin/bash
Never logged in.
No mail.
No Plan.

Now let’s add the units we created in part 1 to /etc/systemd/user, so they are available to everybody, and then we can start the new user thinking

$ sudo machinectl shell kant@ /usr/bin/systemctl --user start thinking.target
Connected to the local host. Press ^] three times within 1s to exit session.

Connection to the local host terminated.

With the system running, we can look at what the philosopher has done by interrogating the journal.

$ journalctl _UID=$(id -u kant)
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Queued start job for default target Main User Target.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Created slice User Application Slice.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Reached target Paths.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Reached target Timers.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Starting D-Bus User Message Bus Socket...
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on GnuPG network certificate management daemon.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on GnuPG cryptographic agent and passphrase cache (access for web browsers).
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on GnuPG cryptographic agent and passphrase cache (restricted).
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on GnuPG cryptographic agent (ssh-agent emulation).
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on GnuPG cryptographic agent and passphrase cache.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on debconf communication socket.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on REST API socket for snapd user session agent.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Listening on D-Bus User Message Bus Socket.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Reached target Sockets.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Reached target Basic System.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Reached target Main User Target.
Nov 24 07:09:21 srv-hy7z5 systemd[2995]: Startup finished in 142ms.
Nov 24 07:10:07 srv-hy7z5 systemd[2995]: Started Thinking Period.
Nov 24 07:10:07 srv-hy7z5 systemd[2995]: Starting Contemplation...
Nov 24 07:10:07 srv-hy7z5 contemplation[3018]: Currently contemplating the enigmatic nature of reality: the existential
Nov 24 07:10:07 srv-hy7z5 contemplation[3018]: grasp for an elusive fork, the categorical imperative of simulated
Nov 24 07:10:07 srv-hy7z5 contemplation[3018]: existence, and the irony in questioning the true essence of the held
Nov 24 07:10:07 srv-hy7z5 contemplation[3018]: object.
Nov 24 07:10:07 srv-hy7z5 systemd[2995]: Finished Contemplation.
Nov 24 07:10:07 srv-hy7z5 systemd[2995]: Reached target Thinking....

To stop the process, we can just get rid of the user

$ sudo -s
$ loginctl disable-linger kant
$ deluser kant philosophers
Removing user `kant' from group `philosophers' ...
Done.
$ deluser --remove-home kant
Looking for files to backup/remove ...
Removing user `kant' ...
Warning: group `kant' has no more members.
Done.

Customising the philosophers

Of course, we don’t want to create philosophers one at a time and manually start each one. We want the computer to take care of that. Plus we want them to think about different things. Otherwise, what’s the point of each of them having a unique identity?

To give them some individuality, we can use the .project file in their home directories and store the things we want the philosopher to think about there. Then we alter the contemplation script to select a random line from .project with the shuf command.

# /usr/local/bin/contemplation
#!/bin/sh
set -e

default_thought="the enigmatic nature of reality: the existential grasp
for an elusive fork, the categorical imperative of simulated existence,
and the irony in questioning the true essence of the held object."
{
    printf '%s' 'Currently contemplating '
    if [ -e "${HOME}/.project" ]
    then
        shuf -n 1 "${HOME}/.project"
    else
        printf '%s\n' "${default_thought}"
    fi
} | fmt
exit 0

Starting the simulation

Now we’re ready to create multiple philosophers each with a list of things to think about. To start the simulation, we need them to take their seat at the dining table and prepare to do battle over the forks when they get hungry.

We can signal that the simulation should start by creating a dining-room directory in a shared area. Once systemd sees this directory, the philosopher can run a script to select their seat.

Selecting seats is straightforward: we set the setgid bit on a seat directory in dining-room and make it writable by the group philosophers. This stops philosophers from overwriting each other’s files. As each philosopher accesses the dining room, they take the next seat available by trying to create a file in the shared area with the seat number and incrementing until they succeed.

echo "The Dining Room is open. Looking for a seat."
seat=${head}
until touch "${diningroom}/seats/${seat}" 2>/dev/null
do
    seat=$((seat+1))
done
echo "I have seat #${seat}"

Forks are allocated relative to the seat obtained. Each philosopher creates a file to represent the fork on their right-hand side, which is numbered one more than their seat number. The forks are created and maintained in the philosopher’s home directory.

grab_fork() {
    touch "${HOME}/forks/$1"
    echo "Acquired fork #$1"
}
...
echo "Creating my fork store"
rm -rf "${HOME}/forks"
mkdir "${HOME}/forks"
grab_fork $((seat+1))

The head of the table, the philosopher in the lowest seat position, also gets the fork on their left-hand side.

if [ "${seat}" -eq "${head}" ]
then
    grab_fork ${head}
fi

Before starting, the philosopher waits until all others have taken their seats.

echo "Waiting for everybody to take their seats"
fsnotifywait -q -q -e close_write -t "${WAIT_FOR_READY_SECS}" -m "${diningroom}/seats" || [ "$?" -eq 2 ]

echo "Starting..."

Those still awake at this point in the piece will have noticed that the philosopher at the foot of the table appears to have a fork that cannot be used or acquired by anybody else. The nature of this fork and whether it exists if it cannot be acquired is precisely what the philosophers contemplate when they are not thinking about something else. We deal with it in part 3.

A path systemd unit and the associated service unit allow us to start this selection process when the dining room is available.

# select-seat.path
[Unit]
Description=Watch Dining Room

[Path]
PathModified=/home/share/dining-room

[Install]
WantedBy=default.target

And the service:

# select-seat.service
[Unit]
Description=Seat Selection
ConditionPathIsDirectory=/home/share/dining-room
Conflicts=hungry.target eating.target
OnSuccess=thinking.target

[Service]
Type=oneshot
ExecStart=/usr/local/bin/select-seat
SyslogFacility=local0

[Install]
WantedBy=default.target

Here, we use an OnSuccess entry to trigger the start of the simulation by starting the thinking target after the select seat service has completed, and a Condition on the service to make sure it doesn’t try to start if the dining room is missing.

The path entry stays in place continuously so that it triggers whenever the dining room is created.

To get the user-level systemd to activate these units automatically, we need to tie it into the default target by having the relevant symbolic links in the systemd area. If we add these to the home directory skeleton then each new user will get those links straight away and systemd will read them.

$ sudo mkdir -p /etc/skel/.config/systemd/user/default.target.wants
$ sudo ln -sf /etc/systemd/user/select-seat.path \
    /etc/systemd/user/select-seat.service \
    /etc/skel/.config/systemd/user/default.target.wants

This is essentially what systemctl --user enable <unit> usually does.

Create the users and off we go

Now we’re ready to run the simulation.

First, we need a philosophers file containing the details of the users²:

kant "Immanuel Kant" "a real pissant" projects/kant
heidegger "Martin Heidegger" "boozy beggar" projects/heidegger
hegel "Wilhelm Friedrich Hegel" "lightweight" projects/hegel
hume "David Hume" "out-consumer" projects/hume
schlegel "Friedrich Schlegel" "schloshed" projects/schlegel
wittgenstein "Ludwig Wittgenstein" "beery swine" projects/wittgenstein
nietzsche "Friedrich Nietzsche" "teacher of the raising of the wrist" projects/nietzsche
socrates "Socrates" "permanently pissed" projects/socrates
mill "John Stuart Mill" "on half a pint of shandy was particularly ill" projects/mill
plato "Plato" "half a crate of whisky every day" projects/plato
aristotle "Aristotle" "bugger for the bottle" projects/aristotle
hobbes "Thomas Hobbes" "fond of his dram" projects/hobbes
descartes "Rene Descartes" "drunken fart" projects/descartes

along with all the setup scripts, project files and systemd units. Fortunately, I’ve done that for you and you can just clone the git repo onto a new Ubuntu LTS server:

$ git clone git@github.com:brightbox/systemd-dining.git

and switch to the part 2 tag:

$ git switch part-2

then run the setup to install the tools:

$ cd system-dining
$ sudo ./setup.sh

Once the files are in place we can create the philiosophers:

$ xargs -L 1 sudo /usr/local/sbin/create_philosopher < philosophers

and then open the dining room to start the simulation:

$ sudo open_dining_room

Then we can sit back and watch the simulation unfold by tailing the journal:

$ journalctl -f
Nov 24 12:13:43 srv-hy7z5 systemd[5124]: Finished Seat Selection.
Nov 24 12:13:43 srv-hy7z5 systemd[4635]: Finished Seat Selection.
Nov 24 12:13:43 srv-hy7z5 systemd[5124]: select-seat.service: Triggering OnSuccess= dependencies.
Nov 24 12:13:43 srv-hy7z5 systemd[4635]: select-seat.service: Triggering OnSuccess= dependencies.
Nov 24 12:13:43 srv-hy7z5 systemd[4635]: Started Thinking Period.
Nov 24 12:13:43 srv-hy7z5 contemplation[5313]: Currently contemplating the belief that the value of actions is determined
Nov 24 12:13:43 srv-hy7z5 contemplation[5313]: by their contribution to individual self-interest and preservation.
Nov 24 12:13:43 srv-hy7z5 systemd[5124]: Started Thinking Period.
Nov 24 12:13:43 srv-hy7z5 systemd[5058]: Finished Contemplation.
Nov 24 12:13:43 srv-hy7z5 systemd[5058]: Reached target Thinking....
Nov 24 12:13:43 srv-hy7z5 systemd[4635]: Starting Contemplation...
Nov 24 12:13:43 srv-hy7z5 systemd[5124]: Starting Contemplation...
Nov 24 12:13:43 srv-hy7z5 contemplation[5317]: Currently contemplating the understanding that what can be said at all
Nov 24 12:13:43 srv-hy7z5 contemplation[5317]: can be said clearly, and what we cannot talk about, we must pass over
Nov 24 12:13:43 srv-hy7z5 contemplation[5317]: in silence.
Nov 24 12:13:43 srv-hy7z5 systemd[4635]: Finished Contemplation.
Nov 24 12:13:43 srv-hy7z5 systemd[4635]: Reached target Thinking....
Nov 24 12:13:43 srv-hy7z5 contemplation[5319]: Currently contemplating the certainty that I exist as a thinking being:
Nov 24 12:13:43 srv-hy7z5 contemplation[5319]: 'Cogito, ergo sum' - I think, therefore I am.
Nov 24 12:13:43 srv-hy7z5 systemd[5124]: Finished Contemplation.
Nov 24 12:13:43 srv-hy7z5 systemd[5124]: Reached target Thinking....

If we just want to look at a particular philosopher there is a convenience script for that:

$ npcjournal -f kant
Nov 24 12:13:41 contemplation[5309]: Currently contemplating the moral imperative that demands action based
Nov 24 12:13:41 contemplation[5309]: on universal principles, irrespective of personal desires or consequences.
Nov 24 12:14:21 hunger[5339]: Getting hungry...
Nov 24 12:14:22 consumption[5341]: Eating...
Nov 24 12:14:28 contemplation[5350]: Currently contemplating how the mind shapes our experience, moulding
Nov 24 12:14:28 contemplation[5350]: reality as we perceive it.
Nov 24 12:14:59 hunger[5387]: Getting hungry...
Nov 24 12:15:02 consumption[5400]: Eating...
Nov 24 12:15:26 contemplation[5432]: Currently contemplating the perspective that time and space are not
Nov 24 12:15:26 contemplation[5432]: external conditions but subjective forms of our intuition.

Summary

In this part, we’ve looked at the multi-user capability of Linux and how we can use it to model multiple philosophers, each isolated from one another in their own process space.

We’ve created a shared area they all can access and used standard filesystem tools to allow them all to access that shared space fairly.

We’ve used the journal to see the entire simulation in action and filtered it down just to look at what an individual philosopher is doing.

Next, we need the philosophers to obtain the right number of forks to eat with, which will require the philosophers to talk to each other and negotiate. We’ll cover how to do that in Part 3.