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
This comment was marked helpful 0 times.
TeBoring
Question: If all the other processors keep taking cache line away from Processor 1 before it can do anything, is it a livelock?
@TeBoring: you are correct. This aspect of a coherence implementation is important to prevent livelock.
This comment was marked helpful 0 times.
markwongsk
Would test-and-set be bad if the logic proceeded to deschedule the waiting process which was unable to obtain the lock?
This comment was marked helpful 0 times.
kayvonf
@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.
This comment was marked helpful 0 times.
yingchal
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.
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
This comment was marked helpful 0 times.
Question: If all the other processors keep taking cache line away from Processor 1 before it can do anything, is it a livelock?
This comment was marked helpful 1 times.
slide 29 of snooping implementation mentioned that a write can finish before lose cache line, I think this is the answer.
This comment was marked helpful 0 times.
@TeBoring: you are correct. This aspect of a coherence implementation is important to prevent livelock.
This comment was marked helpful 0 times.
Would test-and-set be bad if the logic proceeded to deschedule the waiting process which was unable to obtain the lock?
This comment was marked helpful 0 times.
@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.
This comment was marked helpful 0 times.
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.
This comment was marked helpful 0 times.