Previous | Next --- Slide 11 of 29
Back to Lecture Thumbnails

Processor 1 issues test-and-set. This triggers an exclusive access transaction on the bus to obtain exclusive access to this cache line. Processor 1 then sets the lock, and all other processors have invalidated their cache line.

All other processors are continually requesting exclusive access. This takes the cache line from Processor 1.

Problems: -Releasing lock requires a cache invalidation -False sharing: The cache line in the critical section unrelated to the lock is likely on the same cache line as the lock -Highly loaded bus


Question: If all the other processors keep taking cache line away from Processor 1 before it can do anything, is it a livelock?


slide 29 of snooping implementation mentioned that a write can finish before lose cache line, I think this is the answer.


@TeBoring: you are correct. This aspect of a coherence implementation is important to prevent livelock.


Would test-and-set be bad if the logic proceeded to deschedule the waiting process which was unable to obtain the lock?


@markwongsk. The situation you state isn't much of a problem. The thread holding the lock is not affected if a waiting thread is descheduled. Note that it is a much bigger problem if the thread holding the lock is descheduled. This thread is not making progress (until it gets rescheduled) and the other threads are waiting for it to release the lock. Even worse, the threads spinning for the lock hog the processor, potentially preventing the lock-holding thread from being rescheduled. This is an example of priority inversion.

On a modern parallel system, the potential performance problems causes by swapping out a thread (or process) at an inopportune time (e.g., when it's holding an important lock) are the primary motivation for lock-free solutions that are discussed in the fine-grained synchronization lecture in the course.


In test&set; lock, every processor is trying to write to a "shared" lock variable. Since it is test and "set", based on cache-coherence protocol every processing node will send a Read-Exclusive bus transaction for the "shared" lock variable, which invalidates everyone else cache line.