An async approach to resource contention (dining philosophers)

The dining philosophers problem by Dijkstra is a good test of technique. There are plenty of implementations out there and one of them adopted the active agents model as a starting point. Which led to the following implementation;

import ansar.connect as ar

class INITIAL: pass
class READY: pass
class WAITING: pass
class EATING: pass
class THINKING: pass

# The shared resource.
class Fork(object):
	def __init__(self):
		pass

ar.bind(Fork)

# Resource at rest.
class Holder(ar.Point, ar.StateMachine):
	def __init__(self):
		ar.Point.__init__(self)
		ar.StateMachine.__init__(self, INITIAL)
		self.fork = None
		self.enquired = ar.deque()

def Holder_INITIAL_Start(self, message):
	# Start with the fork down.
	self.fork = Fork()
	return READY

def Holder_READY_Enquiry(self, message):
	# Someone is hungry. Add them to the tail of the queue.
	self.enquired.append(self.return_address)
	if self.fork:
		a = self.enquired.popleft()		# Waiting the longest.
		self.send(self.fork, a)
		self.fork = None
	return READY

def Holder_READY_Fork(self, message):
	# Fork is being returned. Is someone waiting?
	if self.enquired:
		a = self.enquired.pop()
		self.send(message, a)
		return READY
	self.fork = message
	return READY

HOLDER_DISPATCH = {
	INITIAL: (
		(ar.Start,), ()
	),
	READY: (
		(Fork, ar.Enquiry), ()
	),
}

ar.bind(Holder, HOLDER_DISPATCH)

#
#
class Philosopher(ar.Threaded, ar.StateMachine):
	def __init__(self, name, left_holder, right_holder):
		ar.Threaded.__init__(self)
		ar.StateMachine.__init__(self, INITIAL)
		self.name = name
		self.left_holder = left_holder
		self.right_holder = right_holder
		# Start with no forks.
		self.holding = ar.deque()
		self.retry = None
		self.mark = None

	def next(self):
		# Introduce variation in eating/thinking times.
		if self.retry is None:
			intervals = ar.RetryIntervals(regular_steps=2.0, randomized=0.25, truncated=0.5)
			self.retry = ar.smart_intervals(intervals)
		p = next(self.retry)
		return p

def Philosopher_INITIAL_Start(self, message):
	# Hungry. Wait for both forks.
	self.send(ar.Enquiry(), self.left_holder)
	self.send(ar.Enquiry(), self.right_holder)
	self.mark = ar.clock_now()
	self.console(f'"{self.name}" is WAITING')
	return WAITING

def Philosopher_WAITING_Fork(self, message):
	# A fork has been relinquished. Got a pair?
	self.holding.append(message)
	if len(self.holding) == 2:
		span = ar.clock_now() - self.mark
		d = ar.span_to_text(span)
		self.console(f'"{self.name}" is EATING (waited {d})')
		self.start(ar.T1, self.next())
		return EATING
	return WAITING

def Philosopher_EATING_T1(self, message):
	# Enough for a while. Put forks down.
	self.send(self.holding.pop(), self.left_holder)
	self.send(self.holding.pop(), self.right_holder)
	self.start(ar.T2, self.next())
	self.console(f'"{self.name}" is THINKING')
	return THINKING

def Philosopher_THINKING_T2(self, message):
	# Hungry again.
	self.send(ar.Enquiry(), self.left_holder)
	self.send(ar.Enquiry(), self.right_holder)
	self.mark = ar.clock_now()
	self.console(f'"{self.name}" is WAITING')
	return WAITING

PHILOSOPHER_DISPATCH = {
	INITIAL: (
		(ar.Start,), ()
	),
	WAITING: (
		(Fork,), ()
	),
	EATING: (
		(ar.T1,), ()
	),
	THINKING: (
		(ar.T2,), ()
	),
}

ar.bind(Philosopher, PHILOSOPHER_DISPATCH)

#
#
philosopher = [
	"Socrates",
	"Descartes",
	"Aristotle",
	"Nietzsche",
	"Sartre",
	"Amdahl",
	"Seneca",
	"Epicurus",
	"Aurelius",
	"Confucius",
	"Dante",
	"Pascale",
	"Voltaire",
	"Schopenhauer",
]

def main(self):
	# Set the table. One holder/fork between each
	# seated philosopher.
	holder = [self.create(Holder) for p in philosopher]

	# Seat the 1st, 3rd, ... etc.
	i = 0
	left_holder = holder[-1]				# Wrap back to the last holder/fork.
	for h, p in zip(holder, philosopher):
		if i % 2 == 0:
			a = self.create(Philosopher, p, left_holder, h)
		left_holder = h
		i += 1

	# Seat the 2nd, 4th, ... etc.
	i = 0
	left_holder = holder[-1]
	for h, p in zip(holder, philosopher):
		if i % 2 == 1:
			a = self.create(Philosopher, p, left_holder, h)
		left_holder = h
		i += 1

	# Wait for control-c.
	self.select(ar.Stop)

ar.bind(main)

#
#
if __name__ == '__main__':
	ar.create_object(main)

To run it, put it in a file called dining-philosophers.py and use the following commands;

$ python3 -m venv .env
$ source .env/bin/activate
$ pip3 install ansar-connect
$ python3 dining-philosophers.py --debug-level=CONSOLE

Control-c will exit. You will get a stream of output like this (some header columns omitted);

<00000023>Philosopher[WAITING] - "Descartes" is EATING (waited 1.002952s)
<00000020>Philosopher[THINKING] - "Aurelius" is WAITING
<00000026>Philosopher[EATING] - "Epicurus" is THINKING
<0000001e>Philosopher[THINKING] - "Sartre" is WAITING
<00000025>Philosopher[EATING] - "Amdahl" is THINKING
<0000001f>Philosopher[WAITING] - "Seneca" is EATING (waited 1.003555s)
<0000001c>Philosopher[THINKING] - "Socrates" is WAITING
<00000021>Philosopher[THINKING] - "Dante" is WAITING
<00000029>Philosopher[EATING] - "Schopenhauer" is THINKING
<0000001d>Philosopher[THINKING] - "Aristotle" is WAITING
<00000027>Philosopher[EATING] - "Confucius" is THINKING
<00000020>Philosopher[WAITING] - "Aurelius" is EATING (waited 1.753754s)
<00000022>Philosopher[THINKING] - "Voltaire" is WAITING
<00000024>Philosopher[EATING] - "Nietzsche" is THINKING
<00000023>Philosopher[EATING] - "Descartes" is THINKING
<00000028>Philosopher[EATING] - "Pascale" is THINKING
<0000001d>Philosopher[WAITING] - "Aristotle" is EATING (waited 0.503175s)
<0000001c>Philosopher[WAITING] - "Socrates" is EATING (waited 1.25492s)
<00000021>Philosopher[WAITING] - "Dante" is EATING (waited 0.754599s)
<00000022>Philosopher[WAITING] - "Voltaire" is EATING (waited 0.003821s)
<0000001e>Philosopher[WAITING] - "Sartre" is EATING (waited 1.506818s)
<00000026>Philosopher[THINKING] - "Epicurus" is WAITING

Implementation is smaller and clearer than others. After hours of running it still seems to give everyone a turn at the trough. Hardly conclusive analysis but agent model seems like a good base. It does include an “optimization” (initially seats the odd philosophers to get them started with 2 forks each) but its simple enough to revert to un-optimized and it still does the job.