1/* 2 * Copyright 2023 Haiku Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Adrien Destugues 7 */ 8 9 /*! 10 \page synchrnization_primitives Synchronization primitives 11 12 In userspace code, there are many way to synchronize threads with each other. Pthreads provide 13 mutexes and condition variables. The Be API provides BLocker. There are also atomic functions 14 and a few other options, on which many solutions can be built. 15 16 The kernel side is a bit more restricted, in particular when it comes to synchronizing between 17 interrupt handlers and other parts of the code. This is because of two reasons: first of all, 18 interrupt are a low level mechanism of the CPU, and while interrupt handling code is running, 19 the normal operations of the kernel are interrupted (as the name implies). So, normal 20 scheduling will not take place. Secondly, interrupts are not allowed to be blocked to wait on 21 anything. This rules out the use of critical sections in the traditional sense, where the 22 interrupt code may want to wait for an userspace thread to complete. 23 24 As a result, the way synchronization is handled in the kernel is a bit different. The basic 25 primitives available are: spinlocks, atomic operations, semaphores, and condition variables. 26 27 \section spinlocks Spinlocks 28 29 A spinlock is a busy wait: it will run a loop, testing over and over for a condition to become 30 true. On a single task system, that would not work, the CPU would be busy forever, and the 31 condition would never change. But, Haiku is a multitask system, and so the condition can be 32 changed, either because of code running on another CPU core, or code running in an interrupt 33 handler (which can interrupt the thread that's running the spinlock). 34 35 The downside of spinlocks is that they keep the CPU busy. Not only this increases power usage, 36 it also prevents using the CPU for something else (maybe another thread would like to run 37 while this one is waiting). As a result, they are used only for very short waits, and always 38 with a timeout to make sure they don't lock up a CPU core forever or even for an unreasonably 39 long time (that will result in a panic and a trip to the kernel debugger). 40 41 \section atomic_ops Atomic operations 42 43 Atomic operations are defined in the \ref support. However, they are actually implemented 44 using only CPU instructions, and no operating system support. This means they are available 45 for use in Kernel code as well. 46 47 They are used as a building block for higher level primitives, but are also occasionally useful 48 for simple synchronization needs or things like event counters. Since they are implemented 49 at the CPU level, they are quite fast. 50 51 Atomic operations are not blocking, but they guarantee that an operation will complete before 52 an interrupt happens or another CPU core accesses the same memory. 53 54 \section semaphores Semaphores 55 56 Semaphores are the historical way to signal events in BeOS and Haiku. A semaphore has a counter 57 that can be incremented (release_sem) and decremented (acquire_sem). The counter is not allowed 58 to go below 0, if a thread attempts to acquire an empty semaphore, it will be blocked until 59 someone else releases it. 60 61 Seaphores can be used to implement mutexes: by creating a semaphore with a count of 1, threads 62 can enter the critical section by acquiring, and exit it by releasing the semaphore. Additional 63 checks can be added to make sure that only threads in the critical section can release the 64 semaphore in this case. 65 66 But semaphores are also useful in other cases. For example, they can be used for an interupt 67 handler to wake up a thread. In that case, the interrupt handler always releases the semaphore 68 (when an interrupt happens) and the thread always acquires it. Releasing a semaphore is never 69 a blocking operation, so there is no risk of blocking an interrupt handler. This setup makes 70 sure the thread is waken up exactly one time per event the interrupt needs to handle. 71 72 Finally, semaphores are identified by an unique number, which can be shared between kernel 73 and userspace. As a result, they can be used to sycnhronize directly between userspace and 74 kernelspace threads, or even directly from interrupt handlers to userspace threads. The 75 downside of this is that there is a limited number of semaphores, and if too much code uses 76 them, or if there is a leak in some code creating and never destroing semaphores, this may 77 end up blocking the system completely. 78 79 \section condition_variables Condition Variables 80 81 A more recent addition to Haiku synchronization primitives is condition variables. They allow 82 a thread to wait for a specific condition, which is notified by another thread. This is 83 similar to the use of semaphores outlined above, but provides an easier way to handle race 84 conditions, spurious wakeups, and so on. 85