9
$\begingroup$

I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to me, as well as Lemma 2.8.1.

Definition 2.8.1. A Lock object state s is inconsistent in any global state where some thread is in the critical section, but the lock state is compatible with a global state in which no thread is in the critical section or is trying to enter.

Lemma 2.8.1 No deadlock-free Lock implementation can enter an inconsistent state.

Proof:

Suppose the Lock object is in an inconsistent state s, where no thread is in the critical section or trying to enter. If thread B tries to enter the critical section, it must eventually succeed, because the implementation is deadlock-free.

Suppose the Lock object is in an inconsistent state s, where A is in the critical section. If thread B tries to enter the critical section, it must block until A leaves. We have a contradiction, because B cannot determine whether A is in the critical section.

What I don't understand:

  • Does being inconsistent just mean that if a thread is in a critical section, there's no way other threads can know about it?
  • What's the contradiction in a lemma proof? Say thread A is in a critical section, and the lock is in an inconsistent state. What stops another thread from overwriting the lock's state and acquiring it?
Improve this question
$\endgroup$
1
  • $\begingroup$ can you state their defn of "deadlock free"? $\endgroup$
    – vzn
    Commented Jul 1, 2014 at 20:18

1 Answer 1

Reset to default
1
$\begingroup$

  • "inconsistent" here means basically the internal implementation is not reflecting the reality of thread activation and lock availability. aka "defective". ie its not functioning correctly as a thread lock. eg the lock may indicate "active" but no thread has acquired the lock or the lock indicates "inactive" but some thread acquired a lock.

  • the contradiction is that according to "deadlock free", a lock will eventually be acquired by at least some thread that requests it. but if its in an inconsistent state then some thread is running but the lock indicates that nothing is locked. but then any new thread cannot succeed in obtaining the lock (without running at the same time as A).

note a wrinkle/subtlety from an online ref[1] that closely matches the book exposition (same authors):

Note that a program can still deadlock even if each of the locks it uses satisfies the no-deadlock property. For example, consider threads A and B that share locks 0 and 1. First, A acquires 0 and B acquires 1. Next, A tries to acquire 1 and B tries to acquire 0. The threads will deadlock because each one waits for the other to release its lock

[1] Multiprocessor Synchronization and Concurrent Data Structures Maurice Herlihy / Nir Shavit

Improve this answer
$\endgroup$
2
  • $\begingroup$ "(without running at the same time as A)": which part of the definitions rules this out? As the Q suggests: Give B the lock, let them run concurrently. No reason this must result in deadlock. $\endgroup$
    – Patrick
    Commented Jul 3, 2014 at 13:18
  • $\begingroup$ candidly, on closer inspection their proof does sound somewhat circular to me but it could work for some definitions of "deadlock free" (but maybe not theirs in particular which seems somewhat imprecise/ ambiguous). $\endgroup$
    – vzn
    Commented Jul 3, 2014 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.