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 waitLeaving 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 onesWaiting 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. Read more: Chasing state of the art
QR:
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 waitLeaving 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 onesWaiting 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. Read more: Chasing state of the art
QR:
Posts
0 comments:
Post a Comment