Shared rooms synchronization problem

Recently I came across another interesting synchronization problem. Assume there are n rooms. Threads can enter and leave rooms. A room can hold arbitrary number of threads. If a room holds at least one thread it is considered occupied. Only one room can be occupied at a time. With each room exit action is associated that must be executed when the last thread left it. No threads are allowed to enter any room before exit action is executed to the end. Threads that are waiting to enter a room must eventually enter it. It is assumed that threads also at some point leave the room.

There are several cases for a thread attempting to enter a room:

• If no room is occupied thread can enter required room
• If occupied room is the same as required room it is not empty (otherwise it may be the case when the action is being executed at the moment and it is not allowed to enter) and there no other threads waiting for other rooms (otherwise others may starve as continuous stream of coming threads to currently occupied room can prevent it to be set free) thread can enter it
• Otherwise thread must wait

Leaving room requires careful thought as well:

• If the thread is not the last one it is free to go
• Otherwise it must leave the room and execute exit action while keeping the room occupied to prevent others from entering any room
  • Once exit action is executed if no other thread is waiting the last one is free to go
  • Otherwise it must wakeup waiting ones

Waiting and waking part can be done using Monitor.Wait and Monitor.PulseAll. Doing so using single sync object is simple but quite inefficient as every pulse all will wakeup all waiting threads (potentially waiting for different rooms) to see that they are not allowed to enter yet as only single room can be occupied at a time. Instead each room will have its own local sync object to wait and pulse on. This will allow to wake up only threads that are now allowed to enter the room they've been waiting on.

But this is where difficulties come. The decision to be made by entering thread spans across rooms. So the decision is still needs to made using global lock. Now the tricky part is that once the decision is made to wait how not to miss wakeup. Attempting to do it like

lock (global)
{
    // Make decision to wait or return
    bool wait = ...;
    if (!wait)
        return;
}
// Somewhere here wakeup may be missed
lock (local)
{
    // Wait on local based on the decision made above
    Monitor.Wait(local);
}

is doomed to suffer from missed wakeups as in between global lock is released and local is acquired the last leaving room thread may try to wakeup waiters. So instead local lock will be acquired while still holding global lock and releasing it only after that.

var locked = false;
try
{
    Monitor.Enter(global, ref locked);
    // Make decision to wait or return
    bool wait = ...;
    if (!wait)
        return;
    
    // Acquifre local hiwle holding global
    lock (local)
    {
        // Release global
        Monitor.Exit(global);
        locked = false;
        // Wait on local based on the decision made above
        Monitor.Wait(local);
    }
}
finally
{
    if (locked)
        Monitor.Exit(global);
}

Threads indicate that are willing to enter the room by maintaining wait count for each room. It also used to allow threads enter the room in bulk. When the last leaving thread picks up a room to get occupied next, adjusts the count and wakes up waiting threads by pulsing room local sync object.

In order to make sure that waiting threads enter a room eventually (guaranteeing starvation freedom) the following mechanism is used:

• If some room is occupied a thread can enter that room only if no other threads are waiting to enter.
• Last leaving thread runs through other rooms in circles starting from the room right next to currently occupied one to see if any thread is waiting and if such room is found it lets waiting threads to enter in bulk.

Here goes the thing.

public class SharedRoomsLock
{
    // Holds room local locks
    private readonly object[] m_locks;
    // Holds number of threads waiting on to 
    // enter indexed by room numbers
    private readonly int[] m_waiting;
    // Holds actions to be excuted for each room 
    // upon exit
    private readonly Action[] m_actions;
    // Holds number of threads currently in the 
    // occupied room
    private int m_count;
    // Holds index of the room currently occupied
    private int m_occupied = -1;

    public SharedRoomsLock(IEnumerable<Action> actions)
    {
        m_actions = actions.ToArray();

        var count = m_actions.Length;

        m_waiting = new int[count];
        m_locks = Enumerable.Range(0, count)
            .Select(_ => new object()).ToArray();
    }

    // Lock ownership is omitted for clarity however
    // can be added using ThreadLocal<T>
    public void Enter(int i)
    {
        var locked = false;
        try
        {
            Monitor.Enter(m_locks, ref locked);

            if (
                // If no room is occupied or
                m_occupied < 0 ||
                (
                // Occupied room that thread is trying 
                // to enter
                    m_occupied == i &&
                // and there is still someone in there
                    m_count > 0 &&
                // and no one waiting to enter other rooms
                    !m_waiting.Any(w => w > 0)))
            {
                m_occupied = i;
                m_count++;
                return;
            }
            // Otherwise indicate desire to enter the room
            m_waiting[i]++;
            // Acquire room local lock before releasing main
            // to avoid missed or incorrect wakeups
            lock (m_locks[i])
            {
                // Release main lock to allow others to 
                // proceed including waking thread
                Monitor.Exit(m_locks);
                locked = false;
                // Wait to be woken up by some last to leave
                // room thread, not necessarily immediately
                Monitor.Wait(m_locks[i]);
                // Once woken up thread can safely enter 
                // the room as count already adjusted 
            }
        }
        finally
        {
            if (locked)
                Monitor.Exit(m_locks);
        }
    }

    public void Exit(int i)
    {
        lock (m_locks)
        {
            // Indicate that thread left the room 
            if (--m_count > 0)
                // And leave it if not last
                return;
        }
        // If last execute exit action however not under 
        // the lock as it quite dangerous due to reentracy 
        m_actions[i]();
        // At this point room is still treated as 
        // occupied as only once exit action is executed 
        // it can be set free
        var locked = false;
        try
        {
            Monitor.Enter(m_locks, ref locked);
            // By default set room as not occupied
            m_occupied = -1;
            // Run through other rooms in circles to see if any 
            // thread is waiting thus ensuring some sort of 
            // fairness or at least starvation freedom
            for (var j = 1; j <= m_waiting.Length; j++)
            {
                var next = (i + j) % m_waiting.Length;
                var w = m_waiting[next];
                if (w > 0)
                {
                    // Found room with waiting threads so it 
                    // will be occupied next
                    m_occupied = next;
                    break;
                }
            }
            // If no one is waiting 
            if (m_occupied < 0)
                // There is nothing that can done
                return;
            // At this there are threads waiting to enter
            // the room so they are allowed to enter in one
            // shot 
            m_count = m_waiting[m_occupied];
            // Closing the doors right after them
            m_waiting[m_occupied] = 0;
            // Acquire room local lock before releasing main
            // to avoid missed or incorrect wakeups
            lock (m_locks[m_occupied])
            {
                // Releasing main lock is safe because the 
                // decision made under main lock will still be 
                // true as no other thread except for those 
                // already wating will be able to wait on room
                // local lock that is currently held
                Monitor.Exit(m_locks);
                locked = false;
                // Wake up waiting to enter threads
                Monitor.PulseAll(m_locks[m_occupied]);
            }
        }
        finally
        {
            if (locked)
                Monitor.Exit(m_locks);
        }
    }
}

Sleeping barber synchronization problem

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 =).