Hello Michael, I apologize if you're receiving this email a second time. I accidentally kept HTML formatting enabled the first time I sent it, causing it to be rejected as spam. I am teaching the Operating Systems Organization course at Washington University in St. Louis, and to supplement a series of lectures on locking and synchronization, I assigned students to read the futex(7) manual page. One student, Alex Baker <mailto:alexbaker@xxxxxxxxx>, pointed out a race condition in the description of how to "down" a futex, i.e. wait for or acquire a lock, under the Semantics section. Say we have two threads, T0 and T1, which execute as follows: 1. T0 acquires the lock, decrements the futex to 0 2. T1 switches in, attempts to acquire the lock, decrements the futex to -1 3. T0 switches in, completes its critical section 4. T0 unlocks the lock, increments the futex to 0 5. Because the futex is 0, T0 assumes threads are waiting on the futex, but no threads have yet called FUTEX_WAIT 6. T0 sets the futex to 1 7. T0 uses the FUTEX_WAKE operation 8. T1 switches in, and believing it should still wait for the futex, it sets the futex to -1 9. T1 now uses the FUTEX_WAIT operation Because, in step 8, T1 has set the futex to -1, its call to FUTEX_WAIT in 9 will succeed, as the futex holds the expected value in the call (-1). But since T0 has already completed its execution and has called FUTEX_WAKE, T1 may never be woken. The fwait and fpost (i.e. lock and release, or down and up) functions in the Examples section on the futex(2) page seem to be race free, but use atomic compare exchange functions, instead of the atomic increment and decrement semantics described in futex(7). I've attached a patch for the futex(7) man page, which modifies the Semantics section to describe a correct, race-free use of a futex for lock acquisition using atomic increment and decrement operations. I've also added a code sample to help illustrate this. I hope the addition of the code sample does not, in your opinion, add unnecessary length to this manual page, given that the futex(2) page is already so thorough. I have copied Bert Hubert, whom I believe to be the original author of the futex(7) man page. Thank you, Marion Sudvarg PhD Student, Computer Science Washington University in St. Louis
Attachment:
futex.7.patch
Description: futex.7.patch
