Futex

A futex (short for "fast userspace mutex") is a Linux construct that can be used to implement basic locking, or as a building block for higher-level locking abstractions such as semaphores and POSIX mutexes or condition variables.

A futex consists of a kernelspace wait queue that is attached to an aligned integer in userspace. Multiple processes or threads operate on the integer entirely in user space (using atomic operations to avoid interfering with one another), and only resort to relatively expensive system calls to request operations on the wait queue (for example to wake up waiting processes, or to put the current process on the wait queue). A properly programmed futex-based lock will not use system calls except when the lock is contended; since most operations do not require arbitration between processes, this will not happen in most cases.

The Futex is similar in purpose and implementation to the CRITICAL_SECTION in Microsoft Windows.

History

Futexes were created by Hubertus Franke (IBM Thomas J. Watson Research Center), Matthew Kirkwood, Ingo Molnár (Red Hat) and Rusty Russell (IBM Linux Technology Center). They first appeared in the development kernel version 2.5.7; the semantics stabilized as of version 2.5.40, and they are present since the 2.6.x stable kernel series.

In 2002, there were discussions to make futexes accessible via the file system, i.e. create a special node in /dev or /proc. However, Linus Torvalds was heavily opposed to this idea and rejected any related patches.

Operations

The basic operations of futexes are based on only two central operations WAIT and WAKE, though futexes depending on the exact Linux version have a few more operations for more specialized cases .

• WAIT (addr, val)

Checks if the value stored at the address addr is val, and if it is puts the current thread to sleep.

• WAKE (addr, val)

Wakes up val number of threads waiting on the address addr.

See also

• Synchronization
• Fetch-and-add
• Compare and swap
• Benaphores: the same principle was used on BeOS as early as 1996.

References

• futex(2) - futex() system call
• futex(7) - futex semantics and usage
• Hubertus Franke, Rusty Russell, Matthew Kirkwood, Fuss, futexes and furwocks: Fast Userlevel Locking in Linux, Ottawa Linux Symposium 2002.
• Futex manpages
• Ingo Molnar, "Robust Futexes", Linux Kernel Documentation
• "Priority Inheritance Futexes", Linux Kernel Documentation
• Critical Section Objects, Microsoft Developer Network