_Accept

The _Accept statement is a synchronization construct that precisely controls which monitor member function can be executed next, based on the state of the shared resource.

The _Accept statement indicates which call is acceptable given the current state of the Monitor.

If the buffer is full, the only acceptable call is to remove, which frees a buffer slot; all calls to insert, including the insert call executing the _Accept statement, are held (blocked) until a call to remove occurs. Similarly, if the buffer is empty, the only acceptable call is to insert, which fills a buffer slot; all calls to remove, including the remove call executing the _Accept statement, are held (blocked) until a call to insert occurs.

Cooperation

Unlike the conditional critical-region, when a task in a monitor knows it cannot execute, it does not passively wait for its condition to become true, it actively indicates that its condition can only become true after a call occurs to a particular mutex member, which is a very precise statement about what should happen next in the monitor, and hence, a very precise form of cooperation.

Notice

• The _Accept statement does not specify the next task to enter the monitor, only the next mutex member to execute when calls occur.
  • Indirectly selected a task through the mutex member it calls
• The _Accept statement allows tasks to use the monitor in non-FIFO order, like the conditional of the conditional critical-region.
  • That is, the entry queue may have several producer tasks blocked on it because the buffer is full, but when a consumer arrives its call to remove is accepted ahead of the waiting producers. In the case where a consumer is already waiting on the entry queue when a producer accepts remove, the waiting consumer is immediately removed from the entry queue (regardless of its position in the queue) and allowed direct entry to the monitor. Hence, when the buffer is full, a waiting consumer is processed immediately or a delay occurs until a consumer calls the monitor.
  • Therefore, the monitor implementation for _Accept must check if there is any task waiting on the entry queue for the accepted member, which may require a linear search of the entry queue

Because linear search is slow, the monitor implementation usually puts a calling task on two queues: the entry queue, in order of arrival, and a mutex queue for the called member, also in order of arrival.

• Each task appears on two queues (duplicates are shaded)
• mutex queues are optional; only enhancing the efficiency of the implementation over searching the entry queue for an accepted caller.

The task executing the _Accept blocks, which implicitly releases mutual exclusion on the monitor so a call can proceed to the accepted mutex member.

Where does the accepting task block?

• In the case of a condition critical-region, a task executing an await statement with a false condition blocks on the shared-variable’s implicit conditional queue.
• In the case of a task executing a _Accept statement, the task blocks on an implicit stack associated with the monitor, called the acceptor/signalled stack
  • It’s a stack because accepts can be nested! To manage the blocked accepting tasks.
  • In the case of the accept call sequence, the calls are performed by different tasks.

Quick Summary (External Scheduling)

1. Role of _Accept in Synchronization
   • The _Acccept statement specifies which call is permissible given the state of the monitor. For example - If a buffer is full, only remove calls can proceed, blocking insert calls until there is space. - If the buffer is empty, only insert calls are permitted, and remove calls are blocked until a buffer slot is filled.
2. Active Cooperation
   • Unlike conditional critical regions, where tasks passively wait, tasks in a monitor using _Accept actively indicate their conditions and what must change to proceed, making it a precise synchronization mechanism.
3. Task Selection and Execution
   • The _Accept statement does not directly choose which task will proceed; rather, it specifies the next mutex function that can execute when a call is made.
   • This results in a non-FIFO execution order, as demonstrated by producer-consumer scenarios where a consumer may “jump the queue” of waiting producers if the buffer is full.
4. Efficiency Considerations
   • Since linear searches of entry queues can be slow, a monitor implementation may use two queues:
     • An entry queue (tasks in order of arrival)
     • A mutex queue (asks waiting for a specific member function), which enhances efficiency.

• Tasks appear in both queues to optimize the acceptance process.

1. Blocking Mechanism
   • When a task executes _Accept, it releases mutual exclusion on the monitor, allowing another task to proceed. The accepting task itself block on a specialized data structure called the acceptor/signalled stack (a sack structure to support nested accepts).
2. Code Organization
   • The mutually recursive nature of insert and remove calls necessitates defining their bodies outside the monitor type due to C++‘s definition-before-use rule.