await()

The explanation describes how an await(cond) operation works within a shared-variable synchronization system, where tasks wait for a specific condition to become true before proceeding. Here is a detailed breakdown:

• When a task encounters an await(cond), it check if the condition cond is true. If cond is false, the task is moved from an entry queue (for tasks waiting to enter the critical region) to a conditional queue (for tasks that entered but cannot proceed due to a condition being false).
• Tasks remain on the conditional queue until they are allowed to recheck the condition. When a task’s condition becomes true, it will be allowed to proceed.

Recheck and blocking:

• Once a task is on the conditional queue, it periodically wakes up and re-evaluates cond inside a do-while loop. If cond remains false, it blocks again on the conditional queue; if cond is true, it proceeds with execution.
• This ensures that a task waiting on a condition does not unnecessarily cycle between the entry and conditional queues. Instead, the task remains in a blocking state, rechecking its condition without leaving the queue.

Queue Management:

• When a task exits the region (either after completing its work or because of a false condition), it may change the shared variable’s state. This state change could potentially satisfy the conditions for tasks in the conditional queue.
• All tasks on the conditional queue are moved back to the entry queue when any task leaves the region. This movement allows those tasks to reattempt entering the critical region and evaluating their conditions.

Key behaviour

A task waiting on an await only moves from the conditional queue to the entry queue once initially. Once in the entry queue, it performs a recheck loop, where it either proceeds or returns to the conditional queue. This design avoids endless cycling between queues, preventing excessive task movements and reducing unnecessary overhead.

Warning

An alternative implementation, involving cooperation, has the task blocking or leaving the region reevaluate the conditional expressions on behalf of the waiting tasks on the conditional queue to see if any task can enter the region. While this latter approach seems reasonable, it imposes limitations on the form of the conditional expression; in particular, the conditional may only involve the shared variable and constants, otherwise the state of the waiting tasks has to be accessed. for local variables.

This particular implementation restriction is discussed further in this chapter.

They are not busy waiting!