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> |