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.
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?