Part 5 of 8 · 3 min read
Giving back
In plain words: No preemption means that nobody can take a resource from its holder. A thread cannot take a mutex from another thread, and the kernel does not do it either. A program can, however, preempt itself: it can decide to give back what it holds if the next request fails.
POSIX offers pthread_mutex_trylock, which takes the lock if it is free and otherwise returns EBUSY at once, without waiting. A transfer can use it like this:
for (;;) {
pthread_mutex_lock(&acc[a].m);
if (pthread_mutex_trylock(&acc[b].m) == 0) { /* got both */
acc[a].bal--; acc[b].bal++;
pthread_mutex_unlock(&acc[b].m); pthread_mutex_unlock(&acc[a].m);
return;
}
pthread_mutex_unlock(&acc[a].m); /* give the first one back */
nap_random_microseconds(); /* back off 1 to 10 us */
}
The thread never waits while it holds a lock, because the second request does not wait. So there is no hold and wait with blocking, and the cycle cannot close. The measured results (three runs each, 2 s per run):
| Threads | Transfers per second | Failed second locks in 2 s |
|---|---|---|
| 2 | 18.7 to 19.1 million | about 31,700 |
| 4 | 15.6 to 15.9 million | 68,000 to 69,000 |
Putting the three methods side by side on this machine gives a mixed picture. With 2 threads, trylock was the fastest (18.7 to 19.1 million per second), the big lock came next (7.1 to 7.4 million), and lock ordering was the slowest (4.7 to 4.9 million). With 4 threads, lock ordering was the fastest (17.5 to 18.1 million), trylock came next (15.6 to 15.9 million), and the big lock was the slowest (8.5 to 11.2 million). Why lock ordering was so much slower at 2 threads was not investigated. The numbers show only that results of such comparisons depend on the load and the machine, so they should be measured and not assumed.
The pause is not optional. If two threads fail, give back, and retry at the same instant, they can repeat the same collision forever. Each thread keeps working, yet neither makes progress. This is a livelock, and page 6 measures it. A short random pause breaks the symmetry.
Preemption is also hard for resources that cannot simply be given back. A thread in the middle of writing a file cannot lose its lock without leaving half-written data. The give-back rule works when the thread has not yet changed anything, as in the transfer above, where the balances change only after both locks are held.
Resource preemption
Resource preemption is the taking back of a resource from a thread that holds it, before the thread has finished using it; in a program it is done by the thread itself, which releases what it holds when a further request cannot be met.
Example: a thread that fails to get its second lock unlocks the first, waits a random moment, and starts again.
Check yourself:
1. Why does pthread_mutex_trylock remove the waiting while holding a lock?
2. Why must the thread pause for a random time before it retries?
3. Why is it safe to give back the first lock in the transfer code?