Wikipedia

Test and test-and-set: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Arthurp (talk | contribs)
13 edits
→Caveat: Be more specific about why double-checked locking is an anti-pattern and link to solution.
Rob* (talk | contribs)
185 edits
https://en.wikipedia.org/w/index.php?title=Test_and_test-and-set&oldid=869387971 seems to have misunderstood that the pseudocode in https://en.wikipedia.org/wiki/Test-and-set#Software_implementation_of_test-and-set is only pseudocode and is _missing_ "actual atomic locking". The yield() doesn't help. As such, i think previous versions of the text of this section are clearer. Really, this article should maybe just be a section in the test-and-set article.
Line 2:
[[mutual exclusion]] in [[multiprocessor]] environments. Although a correct [[lock (computer science)|lock]] can be implemented with test-and-set, it can lead to [[resource contention]] in busy lock (caused by bus locking and cache invalidation when test-and-set operation needs to access memory [[atomic (computer science)|atomically]]).
 
To lower the overhead a more elaborate locking protocol '''test and test-and-set''' is used.
To lower the overhead a more elaborate locking protocol '''test and test-and-set''' is used. The main idea is to reduce [[writeback]] that can create [[resource contention]] when two separate threads want the same lock. If ''n'' threads are competing for the lock, they will attempt to acquire it as soon as it is released if only using [[test and set]], causing each thread to invalidate the lock flag, meaning it must be propagated through the cache of the remaining processors ''n'' times, before any one thread may safely read it. By adding the ''check-yield'' step, only the first thread of execution to notice the lock is free will attempt to obtain it, eliminating the writeback.
 
Given a lock:
''boolean'' locked := false ''// shared lock variable''
 
Entry protocol is:
'''procedure''' EnterCritical() {
'''do''' {
'''while''' ( locked == true) yield(); '''skip''' ''// lockspin looksuntil busythe solock yield to'''''seems''''' schedulerfree''
} '''while''' ( ''TestAndSet''(locked) == true ) ''// attempt actual atomic locking using the [[test-and-set]] instruction''
}
'''procedure''' TestAndSet(lock) {
boolean initial = lock;
lock = true;
return initial;
}
 
Exit protocol is:
Line 21 ⟶ 19:
}
 
The entry protocol uses normal memory reads to spin, waitingwait for the lock to become free. Test-and-set is only used to try to get the lock when normal memory read says it's free. Thus the expensive atomic memory operations happen less often than in a simple [[Busy waiting|spin]] around test-and-set.
 
If the [[programming language]] used supports [[short-circuit evaluation]], the entry protocol could be implemented as:
Retrieved from "https://en.wikipedia.org/wiki/Test_and_test-and-set"