1# Atomic Condition Variables for Thread Synchronization 2`sched_cond_*` (see `sched_prim.h`) provides a means of optimized wake/sleep 3synchronization on kernel threads. Specifically, it provides a wrapper for 4`assert_wait`/`thread_block` & `thread_wake` patterns with fast paths. 5 6## Interfaces 7* `sched_cond_t` / `sched_cond_atomic_t` - Atomic condition variable type to synchronize on 8* `sched_cond_init(sched_cond_t *cond)` - Initialize the atomic condition var 9* `sched_cond_wait(sched_cond_t *cond, ...)` - Set state to inactive and wait for a wakeup on cond 10* `sched_cond_signal(sched_cond_t *cond, ...)` - Issue a wakeup on cond for the specified thread 11* `sched_cond_ack(sched_cond_t *cond)` - Acknowledge the wakeup on cond and set state to active 12 13## Limitations of Existing Interfaces 14 15Consider the following example of a producer-consumer relationship. 16 17### Producer Thread 18```c 19while(1) { 20 ... 21 thread_wake_thread(..., consumer_thread); // (A) 22} 23``` 24### Consumer Thread 25```c 26void work_loop_continuation() 27{ 28 // (B) 29 ... 30 assert_wait(...); // (C) 31 thread_block(..., work_loop_continuation); // (D) 32} 33``` 34 35This scheme has two key inefficiences: 361. Multiple calls to wake the consumer thread (A) may be made before the consumer_thread has awoken. 37 This results in precious CPU cycles being spent in (A) to wake the thread despite the fact that 38 it has already been queued. 392. If in the time since waking (B) and blocking (D), the consumer thread has been sent a wakeup (A), 40 the thread will still yield (D), thus spending precious CPU cycles setting itself up to block only 41 to be immediately queued once more. 42 43 44## Example Usage 45 46`sched_cond_t` and its functions provide fast paths for (1) and (2) by wrapping `thread_wake_thread` and 47`assert_wait/thread_block` with atomic bit operations. 48 49Using these enhancements, the previous example can be revised to: 50 51### Producer Thread 52```c 53while(1) { 54 ... 55 sched_cond_signal(&my_cond, ..., consumer_thread); // (E) 56} 57``` 58### Consumer Thread 59```c 60void work_loop_continuation() 61{ 62 sched_cond_ack(&my_cond); // (F) 63 while (1) { 64 ... 65 sched_cond_wait(&my_cond, ..., work_loop_continuation); // (G) 66 } 67} 68``` 69 70In this example, the producer thread signals the consumer (E), resulting in an explicit wake (A) iff the consumer is 71not awake and has not already been issued an un-acked wakeup. Conversely, the consumer acks the wakeup (F) once awake, 72signalling that it is active and clearing the queued wakeup. Once done with its consumption it attempts to wait on the 73cond (G), signalling that it is inactive and checking for any wakeups that have been issued since the last ack (F). 74If a wakeup has been issued, the consumer immediately acks the wakeup and returns to re-enter the work loop. Else, 75it will block as in (D). 76 77### On acknowledging wakeups 78 79One may note that the adoption of `sched_cond_*` involves adding an additional step (ack) to the consumers work loop. This 80step is critical for two reasons. 81 821. Wakeups can be coalesced without potential loss of data. By ack-ing the wakeup *prior* to doing work, wakeups 83 that are issued while the thread is active are guaranteed to be observed because the consumer will check for wakeups since the 84 last ack before giong to sleep. 852. Wakeups need not explicitly `thread_wake` the consumer thread if it is already awake. This is because the consumer thread will not 86 block if it observes a wakeup has been issued while it was awake. 87 88