Sleeping barber problem is a classic synchronization problem proposed by Dijkstra that goes as follows:
A barbershop consists of a waiting room with n chairs, and the
barber room containing the barber chair. If there are no customers
to be served, the barber goes to sleep. If a customer enters the
barbershop and all chairs are occupied, then the customer leaves
the shop. If the barber is busy, but chairs are available, then the
customer sits in one of the free chairs. If the barber is asleep, the
customer wakes up the barber. Write a program to coordinate the
barber and the customers.
Back in the days when Dijkstra proposed this problem (it was in 1965) probably rhythm of life was hasteless and barbers had chance to sleep at work and customers could wait until he woke up.
Most of the solutions use some sort of WaitHandle to do the trick. For example, classic solution is based on semaphores. Waiting on wait handles is not free.
But now let’s assume that analogy for this problem a barber that desperately needs customers so he is running around in circles while waiting impatiently when there are no customers. Customers are also quite busy so if the waiting queue is empty they want to be served immediately otherwise they go from corner to corner while waiting.
I call this problem “crazy barber”. From the problem statement it follows that we should avoid using any “sleeping” mechanisms to do the synchronization.
Haircut we represent through an Action that barber must execute and thus it cannot be null.
Number of chairs in the waiting room is known in advance and never changes. Waiting queue can not overflow because any customer that sees no free chairs turns around and leaves barbershop. So we can represent waiting queue as circular array of fixed size. Two indices are used to represent it. Head points to next request to be serviced if not null. Tail points to next free slot where request can be put.
Barber waits next in line (the one head index points to) non null request to get serviced. To mark slot as free for itself it nullifies it once obtained reference to request. Next head index is advanced to make this slot available for use by customers. Once it completed with execution it notifies waiting customer that it is free to go by changing done flag.
Customer first checks if there are free slots. Then it competes with other customers for a free slot (the one tail index points to). If successful it puts request that combines action and done flag into waiting queue array with the index value of just advanced tail. Once successfully queued request customer waits until value in the done flag is not changed.
Here goes “crazy barber”.
class CrazyBarber
{
private readonly int m_capacity;
// Circular array that holds queued items
private volatile Request[] m_queue;
// Points to next free slot
private volatile int m_tail;
// Points to a slot where next item to be executed
// is expected
private volatile int m_head;
public CrazyBarber(int capacity)
{
m_capacity = capacity;
m_queue = new Request[m_capacity];
}
// Queues action for execution if there is free slot and
// waits for its execution completion
public bool TryGetExecuted(Action action)
{
if (action == null)
throw new ArgumentException();
var waitToEnq = new SpinWait();
while (true)
{
// Load tail first as if it will change compare and
// swap below will fail anyway
var tail = m_tail;
// Now load head and this is the linearization point
// of full queue case which results in unsuccessful
// attempt
var head = m_head;
// Check if queue has some free slots
if (tail - head >= m_capacity)
// The queue is full, no luck
return false;
// Create request before interlocked operation as
// it implies full barrier and thus will prevent
// partially initialized request to be visible to
// worker loop
var request = new Request { m_action = action };
// Compete for the tail slot
if (Interlocked.CompareExchange(ref m_tail, tail + 1, tail) != tail)
{
// We lost due to contention, spin briefly and
// retry
waitToEnq.SpinOnce();
continue;
}
var index = tail % m_capacity;
// Here is the linearization point of successfull
// attempt
m_queue[index] = request;
var waitToExe = new SpinWait();
// Wait until enqueued action is not executed
while (!request.m_done)
waitToExe.SpinOnce();
return true;
}
}
// Runs single worker loop that does the execution and
// must not be called from multiple threads
public void Run(CancellationToken cancellationToken)
{
var waitToDeq = new SpinWait();
while (true)
{
var head = m_head;
var index = head % m_capacity;
waitToDeq.Reset();
// Though array field is marked as volatile access
// to its elements are not treated as volatile
// however its enough to make sure loop condition
// is not optimized
// Wait until new item is available or cancellation
// is requested
while (m_queue[index] == null)
{
if (cancellationToken.IsCancellationRequested)
return;
waitToDeq.SpinOnce();
}
// Get request to be serviced and nullify it to
// mark slot as free for yourself
var request = m_queue[index];
m_queue[index] = null;
// As there is only one worker advance head without
// interlocked and here is the linearization point
// of making free slot
m_head = head + 1;
// Do not call TryGetExecuted from action or it will
// deadlock
request.m_action();
// Make sure ready notification is not made visible
// through reordering before action is completed
// and store release guarantees that here
request.m_done = true;
}
}
class Request
{
internal Action m_action;
internal volatile bool m_done;
}
}
Although tail index at some point will overflow let’s assume “crazy” barber won’t try to make around 2 billion haircuts =).
No comments:
Post a Comment