Linux provides a sys_futex() system call to assist in implementing hybrid user- level/kernel-level locks and condition variables.

A call to long sys_futex(void *addr1, FUTEX_WAIT, int val1, NULL, NULL, 0) checks to see if the memory at address addr1 has the same value as val1. If so, the calling thread is suspended. If not, the calling thread returns immediately with the error return value EWOULDBLOCK. In addition, the system call returns with the value EINTR if the thread receives a signal.

A call to long sys_futex(void *addr1, FUTEX_WAKE, 1, NULL, NULL, 0) causes one thread waiting on addr1 to return.

Consider the following simple implementation of a hybrid user-level/kernel- level lock.

 class TooSimpleFutexLock { private: 

int val;

 public: TooSimpleMutex() : val (0) { } // Constructor 

 void acquire () { int c; 

 // atomic_inc returns *old* value while ((c = atomic_inc (val)) != 0) { 

 futex_wait (&val, c + 1); } 

}

 void release () { val = 0; 

 futex_wake (&val, 1); } 

};

There are three problems with this code.

a. Performance. The goal of this code is to avoid making expensive system calls in the uncontested case of an acquire on a FREE lock or a release of a lock with no other waiting threads. This code fails to meet this goal. Why?

b. Performance. A subtle corner case occurs when multiple threads try to acquire the lock at the same time. It can show up as occasional slowdowns and bursts of CPU usage. What is the problem?

c. Correctness. A corner case can cause the mutual exclusion correctness condition to be violated, allowing two threads to both believe they hold the lock. What is the problem?