It's Actors All The Way Down

The “Sleeping Barber” problem is another classic concurrency example. As with our previous discussion of “Dining Philosophers”, actors allow a novel approaching to solving this problem. We will adjust a few of the details to enhance the metaphor and have a bit of fun with it.

Our metaphorical barber provides yak shaving services. Yaks arrive at the barber shop to be shaved. If the barber is busy, they wait in a queue. There is only room for two yaks in the waiting area, so if there are already two yaks waiting, a newly arriving yak will leave. When the barber is available, he takes the next waiting yak into the shaving room and begins the shaving process. When the yak is shaved, the barber sleeps until awakened by another yak arriving.

The essence of the problem lies in synchronizing the state of the barber with the state of the waiting room. A naive solution can easily get into a situation where the barber is sleeping and there is a yak waiting to be shaved. This often occurs because of an overlap in the timing of events which represent the barber checking for a waiting yak and the yak checking for a sleeping (thus available) barber.

To emphasize the synchronization issues, we will posit the existence of a receptionist that monitors the waiting room. The barber communicates with the receptionist via text messaging, representing the idea that messages are asynchronous and may be arbitrarily delayed. When the barber finishes shaving a yak, the yak leaves via the back door. The barber then sends a text message to the receptionist and goes to sleep while waiting for the next yak to arrive.

Barber State-Machine

The barber can be in only one of two states. Either the barber is “sleeping” or “shaving”. Initially the barber is “sleeping”. When a yak arrives needing a shave, the barber schedules a delayed event (representing the time taken to shave the yak) and transitions to “shaving” state.

LET shave_time = 3000  # 3 seconds
LET barber_sleep_beh = \msg.[
	CASE msg OF
	(yak, #shave) : [
		SEND (SELF, #shaving) TO yak
		SEND (shave_time, (yak, #done), SELF) TO timer
		BECOME barber_shave_beh(yak)
	]
	_ : [ THROW (#Unexpected, msg) ]
	END
]

When the barber has barber_sleep_beh and receives a #shave message, the barber sends a #shaving notice to the yak, asks the timer to send a #done message after shave_time has elapsed, and changes to barber_shave_beh behavior. All other messages throw an exception.

Figure 1 – Barber State Transitions

When the barber is in “shaving” state and the shaving process in completed, a #done message is received, tagged with identity of the shaved yak. The barber asks for the next yak to shave, and goes back to sleep while waiting for another yak to arrive. Figure 1 illustrates the barber’s state transitions.

LET barber_shave_beh(yak) = \msg.[
	CASE msg OF
	($yak, #done) : [
		SEND (SELF, #shaved) TO yak
		SEND (SELF, #next) TO receptionist
		BECOME barber_sleep_beh
	]
	_ : [ THROW (#Unexpected, msg) ]
	END
]

When the barber has barber_shave_beh and receives a #done message, a #shaved notice is sent to the yak, a request for the #next yak is sent to the waiting room receptionist, and the barber changes to barber_sleep_beh. All other messages throw an exception.

Waiting Room State-Machine

The receptionist maintains the state of the waiting room, responding to yak arrivals and text messages from the barber. The receptionist’s initial “sleep” state represents the knowledge that the barber is sleeping, and there are no yaks waiting to be shaved. When a yak arrives, the receptionist sends the yak on to the barber for shaving.

LET sleep_waiting_beh(barber) = \msg.[
	CASE msg OF
	(yak, #arrive) : [
		SEND (yak, #shave) TO barber
		BECOME zero_waiting_beh(barber)
	]
	_ : [ THROW (#Unexpected, msg) ]
	END
]

When the receptionist has sleep_waiting_beh and receives an #arrive message, a #shave message is sent to the barber, and the receptionist changes to zero_waiting_beh behavior. This indicates that there is a yak being shaved by the barber, but no yaks are waiting yet.

Figure 2 – Waiting Room State Transitions

The transitions between “sleep” and “zero” states are key to understanding how our actor-based solution avoids the pitfalls of a naive implementation. In “sleep” state, the receptionist knows that the barber is sleeping and there are no yaks on their way to the barber. In “zero” state, the barber is (or will be) busy shaving a yak, but no yaks are waiting yet. If another yak arrives, it must wait until the barber asks for the next yak. Figure 2 illustrates the receptionist’s state transitions.

LET zero_waiting_beh(barber) = \msg.[
	CASE msg OF
	(yak, #arrive) : [
		SEND (SELF, #waiting, 1) TO yak
		BECOME one_waiting_beh(barber, yak)
	]
	($barber, #next) : [
		BECOME sleep_waiting_beh(barber)
	]
	_ : [ THROW (#Unexpected, msg) ]
	END
]

When the receptionist has zero_waiting_beh and receives an #arrive message, a #waiting notice is sent to the yak, and the receptionist changes to one_waiting_beh behavior. If a #next message is received from the barber, the receptionist changes to sleep_waiting_beh behavior, since there are no yaks waiting to be shaved but we must remember that the barber is sleeping.

When there is a yak waiting to be shaved, newly arriving yaks must also wait. When the barber asks for the next yak, they will be served in order of arrival. The waiting room buffers the barber from handling arrivals while busy shaving. Instead the barber pulls from the waiting room when ready.

LET one_waiting_beh(barber, yak_1) = \msg.[
	CASE msg OF
	(yak, #arrive) : [
		SEND (SELF, #waiting, 2) TO yak
		BECOME two_waiting_beh(barber, yak_1, yak)
	]
	($barber, #next) : [
		SEND (yak_1, #shave) TO barber
		BECOME zero_waiting_beh(barber)
	]
	_ : [ THROW (#Unexpected, msg) ]
	END
]

When the receptionist has one_waiting_beh and receives an #arrive message, a #waiting notice is sent to the yak, and the receptionist changes to two_waiting_beh behavior. If a #next message is received from the barber, a #shave message is sent to the barber, and the receptionist changes to zero_waiting_beh behavior.

When there are two yaks waiting to be shaved, the waiting room is full and newly arriving yaks must leave. When the barber asks for the next yak, the one that has been waiting the longest will be served first. The waiting room operates as a bounded queue of waiting yaks.

LET two_waiting_beh(barber, yak_1, yak_2) = \msg.[
	CASE msg OF
	(yak, #arrive) : [
		SEND (SELF, #leave) TO yak
	]
	($barber, #next) : [
		SEND (yak_1, #shave) TO barber
		BECOME one_waiting_beh(barber, yak_2)
	]
	_ : [ THROW (#Unexpected, msg) ]
	END
]

When the receptionist has two_waiting_beh and receives an #arrive message, a #leave notice is sent to the yak. If a #next message is received from the barber, a #shave message is sent to the barber, and the receptionist changes to one_waiting_beh behavior.

Yak Arrival Model

Our yaks have a very simple behavior. Each is assigned a number, for identification purposes. When a yak receives a message, it labels the message with its identification number and sends it to the console.

LET yak_beh(n) = \(cust, req).[
	SEND (n, req) TO println
]

Our message protocol includes a sender (here bound to cust) which is ignored by the yak behavior. Only the request req is printed.

We need to generate a random sequence of arrival events to exercise our solution. For each event, we create a new numbered yak and send it to the receptionist. We also increment the yak numbering counter and schedule another event after a random delay.

LET arrival_beh(n) = \t.[
	CREATE yak WITH yak_beh(n)
	SEND (yak, #arrive) TO receptionist
	BECOME arrival_beh(add(n, 1))
	SEND (t, (SELF, 5000), random) TO timer
]

The message that triggers creation of an arrival event is simply the delay time t. The arrival event is sent immediately, but t is used to schedule a delayed message to the random service, which in turn feeds a new random number to the arrival generating process. This process continues indefinitely, generating an endless stream of randomly-arriving hairy yaks.

Finally, we create the barber, receptionist and arrival process. The arrival process is kicked off with an initial delay value generated at random.

CREATE barber WITH barber_sleep_beh
CREATE receptionist WITH sleep_waiting_beh(barber)
CREATE arrivals WITH arrival_beh(1)
SEND (arrivals, 5000) TO random

Summary

The “Sleeping Barber” problem is a restricted version of a concurrent producer/consumer system. The actor-based solution shown here establishes a bounded-buffer (the waiting room) where new work arrives randomly, and is pulled when the consumer (the barber) is ready. The critical issue is making sure the waiting room receptionist doesn’t lose track of the fact that the barber is sleeping in case there are no yaks waiting. This is precisely the distinction between the “zero” and “sleep” states described above. In the “zero” state, the barber is busy, but no yaks are waiting. In the “sleep” state, the barber is sleeping, waiting for a yak to arrive.