Blocking and Unblocking

Introduction

Usually, when a thread attempts to get access to a resource which is unavailable, such as a semaphore, mutex, critical section, or synchronization object, the thread stops running while waiting for the resource to become available. This is called blocking. Unless a thread happens to block at exactly the time its time-slice quantum has expired, blocking prevents the thread from completing a full time slice. When the resource waited on becomes available, the blocked thread is unblocked and runs the next time it is scheduled.

Unblock Boosting

If, before completing a time slice, a thread blocks and unblocks but is left at the same priority, it will effectively have its time slice reduced to the time it uses between the unblock and block operations. This is because the scheduler does not have any reason to schedule the newly unblocked thread before any other threads running at the same priority. This gives threads that do not need to block on resources a great advantage when competing for processor time.

To allow threads which block and unblock to compete effectively for processor time, the time slicer dynamically boosts the priority of a thread when it blocks.

Monopolization of Processor by Blocking

A system that boosts priorities when threads block can have problems with threads that monopolize the system by blocking and unblocking very quickly. Without checks in place to prevent this, a thread could block and unblock so quickly that it essentially maintains the priority of its boosted state.

To prevent this kind of monopolization, the elapsed time since a thread was scheduled to run is totaled whenever the thread blocks. When the total reaches or exceeds the quantum period, the total is reset and the thread is blocked with an unboosted priority. Effectively, the thread is back in the runnable queue at its base priority.

Priority Inversion Boosting

A synchronization problem that can occur in a system with preemptive priorities is that threads that own system resources may not be able to run when other, higher priority threads are executing. This can cause a situation in which a thread remains blocked on a resource owned by a thread that is unable to run. If threads at a higher priority than the resource owning thread do not block, the resource may never be freed. To prevent this problem, the system uses a technique called priority inversion prevention in which the system boosts the priority of the thread that owns a resource to at least the priority of any thread that blocks on the resource.

The Windows 95 time slicer's algorithm for priority-inversion-prevention is associative. This means that, once a priority inversion boost is in place, the boosted thread maintains the same priority as the boosting thread.

When threads are suspended by events not related to blocking on resources, they will simply lose their current time slice, and will not be block boosted.