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