CSE Roadmap

Common tier · about 5 hours · 8 parts

Part 6 of 8 · 3 min read

Timeout recovery

In plain words: A program can do its own recovery. A thread asks for its second lock with a limit on the wait. If the limit expires, the thread assumes a deadlock may exist, gives back the first lock (its own rollback, since it has changed nothing yet), waits a short random time, and starts again:

for (;;) {
    pthread_mutex_lock(&acc[a].m);                       /* no lock order at all */
    struct timespec dl;  /* now + wait_ms */
    clock_gettime(CLOCK_REALTIME, &dl);
    dl.tv_nsec += wait_ms * 1000000L; dl.tv_sec += dl.tv_nsec / 1000000000L; dl.tv_nsec %= 1000000000L;
    if (pthread_mutex_timedlock(&acc[b].m, &dl) == 0) {  /* got both: do the work */
        acc[a].bal--; acc[b].bal++;
        pthread_mutex_unlock(&acc[b].m); pthread_mutex_unlock(&acc[a].m);
        break;
    }
    pthread_mutex_unlock(&acc[a].m);                     /* recovery: give back */
    rollbacks++;  nap_random_1_to_5_ms();                /* then retry */
}

This is the bank-transfer program of page 1 with no lock order, so it can deadlock. The difference is the recovery. Four threads moved money among four accounts for 5 s, with different timeouts:

Timeout Transfers done in 5 s Rollbacks Total money
1 ms 16,347,298 3,255 4,000
10 ms 1,115,655 682 4,000
100 ms 104,232 79 4,000
1,000 ms 1,531 7 4,000

The total money was right every time, and the program never stayed stuck. But the throughput fell by a factor of about 10,000 from the shortest to the longest timeout. A deadlock costs the full timeout before it is broken, and during that time the stuck threads do nothing. A likely reason for the steep fall is that, with only four accounts, the other threads soon run into the stuck locks as well. This was not measured separately. A short timeout recovers quickly, but it has a price: on a busy lock it also gives up when no deadlock exists. The program did not tell apart the rollbacks caused by real deadlocks from those caused by slow waits, so the 3,255 rollbacks at 1 ms may include both.

The choice of the timeout is thus a choice of how long a deadlock may last, against how often a wrong alarm may cost work. For a transfer that takes a microsecond, 1 ms is generous. For a database transaction of 200 ms, 1 ms would abort most of them. The timeout should be longer than a normal wait, and shorter than a deadlock a user would tolerate.

A random pause before the retry matters. Without it, two threads that roll back together may retry together and meet again (page 6, livelock).

Rollback

A rollback is the undoing of a thread's partial work and the release of the resources it holds, so that it can be restarted from a state in which it holds nothing.

Example: a transfer thread that times out on its second lock unlocks the first one and retries the whole transfer.

Common mistake

A timeout is a guess, not a proof. If the holder is only slow, the waiter gives up, rolls back and retries for nothing. Choose the timeout from measured normal waits, and count the rollbacks, so that a rise in the count shows a problem.

Check yourself: 1. Why is it safe for the thread to give back its first lock when the second times out? 2. In the table, what happens to the throughput as the timeout grows, and why? 3. Why can a very short timeout also hurt?