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