The term futex is short for "Fast
User space muTEX" where a
mutex is a
MUTual EXclusion primitive.
Mutexes are used to control access to shared resources. If you always access your shared resource like this :
Acquire_Mutex();
Mess_With_Shared_Thing();
Release_Mutex();
then you are
guaranteed that only one
thread of execution will mess with your shared resource at a time. An attempt to
acquire a mutex which someone else has already acquired causes your thread of execution to wait until it has been
released.
In traditional mutex implementations, a system call is required for every acquisition and release of a mutex. A system call is a voyage from user space to kernel space and back again, and as a result can be just a little bit slow, especially if you're doing millions of them. This performance penalty is especially annoying, because nine time out of ten, no other thread was trying to use that resource anyway, so you did all that work for nothing. The tenth time, of course, it totally saved your bacon, which is why you used it.
Futexes are a creation of Rusty Russell, and an addition to the Linux kernel in 2.5.7, with patches available for various 2.4.x releases thereof. With a futex, acquiring a mutex that is already free, and freeing a mutex for which no one is waiting, does not use a system call; that is, it stays in user space. Thus, nine times out of ten you're way ahead, and the tenth time you're no worse off.
There are extra things that an implementor of futexes needs to worry about. For example, if a thread acquires a mutex and then dies, the kernel doesn't know that anything happened, and the mutex may never be released. Luckily, users of mutexes don't need to know, and just get faster programs.
Next Generation POSIX Threads (NGPT) from http://oss.software.ibm.com/pthreads/ is among the threading packages that require futexes in one form or another.
Just as with regular mutexes, one can use futexes to build higher level constructs, such as furwocks which are Fast User Space Read/Write Locks. (A read/write lock allows multiple readers or a single writer).
An example implementation can be found at http://www.kernel.org/pub/linux/kernel/people/rusty/futex-2.0.tar.gz