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);
}
}
}