It's Actors All The Way Down

The “Dining Philosophers” problem is a classic example used to illustrate various challenges with concurrency. We will approach this problem by incrementally designing the actors which model the problem and its solution in Humus. Through this example we will explore the avoidance of deadlock and starvation in the design of actor-based systems.

Basic Thinking/Eating Cycle

We will model each philosopher as an actor. Each philosopher alternates between two major states, “thinking” and “eating”. In the “thinking” state, a philosopher that receives an #eat message becomes hungry and wants to eat. In the “eating” state, a philosopher that receives a #think message will stop eating and begin thinking. We can model this much of a philosopher’s behavior with the following behavior definitions.

LET thinking_philosopher_beh = \msg.[
	CASE msg OF
	#eat : [
		BECOME eating_philosopher_beh
		SEND SELF TO eating_timer
	]
	END
]
LET eating_philosopher_beh = \msg.[
	CASE msg OF
	#think : [
		BECOME thinking_philosopher_beh
		SEND SELF TO thinking_timer
	]
	END
]

We need a few infrastructure definitions to support the simulation. The eating_timer actor will send a #think message after some eating delay time has passed. The thinking_timer actor will send an #eat message after some thinking delay time has passed. Both timers are defined using delay_timer_beh, which uses the global timer service.

LET eating_time = 2000  # 2 seconds
LET thinking_time = 5000  # 5 seconds
LET delay_timer_beh(delay, msg) = \cust.[
	SEND (delay, msg, cust) TO timer
]
CREATE eating_timer WITH delay_timer_beh(eating_time, #think)
CREATE thinking_timer WITH delay_timer_beh(thinking_time, #eat)

With these actors and behaviors available, we can create a sample philosopher and start his thinking/eating cycle as follows:

CREATE plato WITH thinking_philosopher_beh
SEND plato TO thinking_timer

Adding Chopsticks

Now we add another constraint to our system. Before a philosopher can eat, he must obtain a pair of chopsticks. We will model each chopstick as an actor. For now we will assume that a chopstick is always available. Contention for available chopsticks (the interesting problem) will be handled later.

Figure 1 - Philosophers may be "hungry".

In order to understand the protocol required of our chopsticks, we modify the philosopher’s behavior to include a state transition through “hungry”, where chopsticks are obtained before eating. Figure 1 illustrates the philosopher’s state space augmented with the “hungry” sub-state.

LET thinking_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	#eat : [
		SEND (SELF, #take) TO left
		SEND (SELF, #take) TO right
		BECOME hungry_philosopher_beh(left, right)
	]
	END
]

Now our thinking philosopher has references to left and right chopsticks. When a philosopher wants to eat, he sends #take messages to each chopstick, and transitions to “hungry” while waiting for the chopsticks to be taken.

Of course, the #taken responses from each chopstick arrive asynchronously, so we must keep track of which responses the philosopher has received. The chopsticks send their own identity as part of the #taken message, so that we know which chopstick was taken.

LET hungry_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	($left, #taken) : [
		BECOME right_waiting_philosopher_beh(left, right)
	]
	($right, #taken) : [
		BECOME left_waiting_philosopher_beh(left, right)
	]
	END
]

As soon as one #taken message is received, we know that we are waiting for the remaining chopstick. Once both chopsticks have been obtained, the philosopher can begin eating.

LET right_waiting_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	($right, #taken) : [
		BECOME eating_philosopher_beh(left, right)
		SEND SELF TO eating_timer
	]
	END
]
LET left_waiting_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	($left, #taken) : [
		BECOME eating_philosopher_beh(left, right)
		SEND SELF TO eating_timer
	]
	END
]

When an “eating” philosopher receives a #think request, he puts down his chopsticks and begins thinking.

LET eating_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	#think : [
		SEND (SELF, #put) TO left
		SEND (SELF, #put) TO right
		BECOME thinking_philosopher_beh(left, right)
		SEND SELF TO thinking_timer
	]
	END
]

Eventually, the thinking_timer will tell the “thinking” philosopher that it is time to eat, starting the cycle over again.

Based on the protocol expected by the philosopher, we can model our chopsticks with this behavior:

LET available_chopstick_beh = \(cust, req).[
	CASE req OF
	#take : [ SEND (SELF, #taken) TO cust ]
	#put : []
	END
]

When a chopstick receives a #take request, it responds with a #taken message tagged with the chopstick’s identity. When a chopstick receives a #put request, there is no action taken because chopsticks are always available.

With these actors and behaviors available, we can re-create our sample philosopher and start his thinking/eating cycle as follows:

CREATE chopstick_1 WITH available_chopstick_beh
CREATE chopstick_2 WITH available_chopstick_beh
CREATE plato WITH thinking_philosopher_beh(chopstick_1, chopstick_2)
SEND plato TO thinking_timer

Sharing Chopsticks

If chopsticks are going to be shared, we need to keep track of which are “idle” and which are “busy”. An “idle” chopstick is available to be #taken by a philosopher. A “busy” chopstick will refuse to be #taken until it receives a #put request.

LET idle_chopstick_beh = \(cust, req).[
	CASE req OF
	#take : [
		SEND (SELF, #taken) TO cust
		BECOME busy_chopstick_beh
	]
	END
]
LET busy_chopstick_beh = \(cust, req).[
	CASE req OF
	#take : [ SEND (SELF, #busy) TO cust ]
	#put : [ BECOME idle_chopstick_beh ]
	END
]

When a chopstick receives a #take request, it can now respond with either #taken or #busy. We need to adjust the philisopher’s behaviors to account for this possibility. Figure 2 illustrates the extended state-space needed to account for a #busy response.

Figure 2 - Philosophers may be "denied"

Each of the behaviors involved in waiting to take chopsticks must be changed to handle a #busy chopstick. The required changes are highlighted here:

LET hungry_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	($left, #taken) : [
		BECOME right_waiting_philosopher_beh(left, right)
	]
	($right, #taken) : [
		BECOME left_waiting_philosopher_beh(left, right)
	]
	(_, #busy) : [
		BECOME denied_philosopher_beh(left, right)
	]
	END
]
LET right_waiting_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	($right, #taken) : [
		BECOME eating_philosopher_beh(left, right)
		SEND SELF TO eating_timer
	]
	(_, #busy) : [
		SEND (SELF, #put) TO left
		BECOME thinking_philosopher_beh(left, right)
		SEND #eat TO SELF
	]
	END
]
LET left_waiting_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	($left, #taken) : [
		BECOME eating_philosopher_beh(left, right)
		SEND SELF TO eating_timer
	]
	(_, #busy) : [
		SEND (SELF, #put) TO right
		BECOME thinking_philosopher_beh(left, right)
		SEND #eat TO SELF
	]
	END
]

In the new “denied” state, the philosopher has received a #busy response from one chopstick, but needs to wait for a response from the other chopstick.

LET denied_philosopher_beh(left, right) = \msg.[
	CASE msg OF
	(other, #taken) : [
		SEND (SELF, #put) TO other
		BECOME thinking_philosopher_beh(left, right)
		SEND #eat TO SELF
	]
	(_, #busy) : [
		BECOME thinking_philosopher_beh(left, right)
		SEND #eat TO SELF
	]
	END
]

If the other chopstick is #taken, the philosopher immediately sends it a #put request, since both chopsticks could not be #taken. Regardless of whether the other chopstick is #taken or #busy, the philosopher resumes “thinking” (since he cannot eat right now). But he also sends himself an #eat request, so that he will try to eat again as soon as possible.

Now we can create the traditional ring of five philosophers, sharing adjacent chopsticks, alternately thinking and eating as follows:

CREATE chopstick_1 WITH idle_chopstick_beh
CREATE chopstick_2 WITH idle_chopstick_beh
CREATE chopstick_3 WITH idle_chopstick_beh
CREATE chopstick_4 WITH idle_chopstick_beh
CREATE chopstick_5 WITH idle_chopstick_beh
CREATE descartes WITH thinking_philosopher_beh(chopstick_1, chopstick_2)
CREATE nietzsche WITH thinking_philosopher_beh(chopstick_2, chopstick_3)
CREATE kant WITH thinking_philosopher_beh(chopstick_3, chopstick_4)
CREATE hume WITH thinking_philosopher_beh(chopstick_4, chopstick_5)
CREATE plato WITH thinking_philosopher_beh(chopstick_5, chopstick_1)
SEND descartes TO thinking_timer
SEND nietzsche TO thinking_timer
SEND kant TO thinking_timer
SEND hume TO thinking_timer
SEND plato TO thinking_timer

The philosophers in the ring all begin thinking. After some time passes, they become hungry and try to eat. If they can obtain a pair of chopsticks, they eat for a while then resume thinking. If they cannot obtain a pair of chopsticks, they put down any chopsticks they have obtained and keep retrying until they can eat.

Conclusion

The key to this actor-based solution to the “Dining Philosophers” problem is the active state-dependent behavior of the chopsticks. Each chopstick manages contention between philosophers trying to use it. The philosophers operate concurrently with each other, and with the chopsticks. There are no blocking operations. And eventually, every philosopher gets a chance to eat, avoiding starvation.