| 466,7 → 466,87 |
|---|
| <secondary>- futex</secondary> |
| </indexterm> |
| |
| <para></para> |
| <para>In a multithreaded environment, userspace threads need an |
| efficient way to synchronize. HelenOS borrows an idea from Linux<xref |
| linkend="futex" /> to implement lightweight userspace synchronization |
| and mutual exclusion primitive called futex. The key idea behind futexes |
| is that non-contended synchronization is very fast and takes place only |
| in userspace without kernel's intervention. When more threads contend |
| for a futex, only one of them wins; other threads go to sleep via a |
| dedicated syscall.</para> |
| |
| <para>The userspace part of the futex is a mere integer variable, a |
| counter, that can be atomically incremented or decremented. The kernel |
| part is rather more complicated. For each userspace futex counter, there |
| is a kernel structure describing the futex. This structure |
| contains:</para> |
| |
| <itemizedlist> |
| <listitem> |
| <para>number of references,</para> |
| </listitem> |
| |
| <listitem> |
| <para>physical address of the userspace futex counter,</para> |
| </listitem> |
| |
| <listitem> |
| <para>hash table link and</para> |
| </listitem> |
| |
| <listitem> |
| <para>a wait queue.</para> |
| </listitem> |
| </itemizedlist> |
| |
| <para>The reference count helps to find out when the futex is no longer |
| needed and can be deallocated. The physical address is used as a key for |
| the global futex hash table. Note that the kernel has to use physical |
| address to identify the futex beacause one futex can be used for |
| synchronization among different address spaces and can have different |
| virtual addresses in each of them. Finally, the kernel futex structure |
| includes a wait queue. The wait queue is used to put threads that didn't |
| win the futex to sleep until the winner wakes one of them up.</para> |
| |
| <para>A futex should be initialized by setting its userspace counter to |
| one before it is used. When locking the futex via userspace library |
| function <code>futex_down_timeout</code>, the library code atomically |
| decrements the futex counter and tests if it droped below zero. If it |
| did, then the futex is locked by another thread and the library uses the |
| <constant>SYS_FUTEX_SLEEP</constant> syscall to put the thread asleep. |
| If the counter decreased to 0, then there was no contention and the |
| thread can enter the critical section protected by the futex. When the |
| thread later leaves that critical section, it, using library function |
| <code>futex_up</code>, atomically increments the counter. If the counter |
| value increased to one, then there again was no contention and no action |
| needs to be done. However, if it increased to zero or even a smaller |
| number, then there are sleeping threads waiting for the futex to become |
| available. In that case, the library has to use the |
| <constant>SYS_FUTEX_WAKEUP</constant> syscall to wake one sleeping |
| thread.</para> |
| |
| <para>So far, futexes are very elegant in that they don't interfere with |
| the kernel when there is no contention for them. Another nice aspect of |
| futexes is that they don't need to be registered anywhere prior to the |
| first kernel intervention.</para> |
| |
| <para>Both futex related syscalls, <constant>SYS_FUTEX_SLEEP</constant> |
| and <constant>SYS_FUTEX_WAKEUP</constant>, respectivelly, are mere |
| wrappers for <code>waitq_sleep_timeout</code> and |
| <code>waitq_sleep_wakeup</code>, respectively, with some housekeeping |
| functionality added. Both syscalls need to translate the userspace |
| virtual address of the futex counter to physical address in order to |
| support synchronization accross shared memory. Once the physical address |
| is known, the kernel checks whether the futexes are already known to it |
| by searching the global futex hash table for an item with the physical |
| address of the futex counter as a key. When the search is successful, it |
| returns an address of the kernel futex structure associated with the |
| counter. If the hash table does not contain the key, the kernel creates |
| it and inserts it into the hash table. At the same time, the the current |
| task's B+tree of known futexes is searched in order to find out if the |
| task already uses the futex. If it does, no action is taken. Otherwise |
| the reference count of the futex is incremented, provided that the futex |
| already existed.</para> |
| </section> |
| </section> |
| </chapter> |