Types of Synchronization Synchronization Mutual Exclusion Todd C Mowry CS 740 November 1 2000 Locks Event Synchronization Global or group based barriers Point to point Topics Locks Barriers Hardware primitives 2 Busy Waiting vs Blocking A Simple Lock Busy waiting is preferable when lock scheduling overhead is larger than expected wait time processor resources are not needed for other tasks schedule based blocking is inappropriate e g in OS kernel 3 CS 740 F 00 unlock CS 740 F 00 4 Page 1 ld cmp bnz st ret st ret register location register 0 lock location 1 location 0 CS 740 F 00 Need Atomic Primitive Test Set based lock Test Set Swap Fetch Op lock unlock Fetch Incr Fetch Decr t s bnz ret st ret register location lock location 0 Compare Swap 5 CS 740 F 00 6 T S Lock Performance Test and Test and Set Code lock delay c unlock Same total no of lock calls as p increases measure time per transfer n A while lock free if test set lock free critical section else goto A u spinning happens in cache can still generate a lot of traffic when many processors go to do test set 20 s l 18 n u l s Test set c 0 Test set exponential backof f c 3 64 Test set exponential backof f c 0 Ideal s n s 16 s s 14 Time s s l n l 6 n s l l n l n l s 8 n n n l n 4 s n u l 0s l s s s 10 2 l s s 12 l s U l n l U n 3 u n l l n n u 5 u u 7 u u u 9 CS 740 F 00 u 11 u u 13 u u 15 Number of processors 7 CS 740 F 00 8 Page 2 CS 740 F 00 Test and Set with Backoff Test and Set with Update Upon failure delay for a while before retrying Test and Set sends updates to processors that cache the lock Tradeoffs either constant delay or exponential backoff Tradeoffs good for bus based machines still lots of traffic on distributed networks much less network traffic exponential backoff can cause starvation for high contention locks new requestors back off for shorter times Main problem with test set based schemes is that a lock release causes all waiters to try to get the lock using a test set to try to get it But exponential found to work best in practice 9 CS 740 F 00 10 Ticket Lock fetch incr based CS 740 F 00 Ticket Lock Tradeoffs Two counters guaranteed FIFO order no starvation possible latency can be low if fetch incr is cacheable traffic can be quite low but traffic is not guaranteed to be O 1 per lock acquire next ticket number of requestors now serving number of releases that have happened Algorithm First do a fetch incr on next ticket not test set When release happens poll the value of now serving if my ticket then I win Use delay but how much 11 CS 740 F 00 12 Page 3 CS 740 F 00 Array Based Queueing Locks List Base Queueing Locks MCS Every process spins on a unique location rather than on a single now serving counter fetch incr gives a process the address on which to spin Tradeoffs All other good things O 1 traffic even without coherent caches spin locally Uses compare swap to build linked lists in software Locally allocated flag per list node to spin on Can work with fetch store but loses FIFO guarantee Tradeoffs guarantees FIFO order like ticket lock O 1 traffic with coherence caches unlike ticket lock requires space per lock proportional to P 13 less storage than array based locks O 1 traffic even without coherent caches compare swap not easy to implement CS 740 F 00 14 Implementing Fetch Op Barriers Load Linked Store Conditional We will discuss five barriers reg1 location LL location to reg1 bnz reg1 lock check if location locked sc location reg2 SC reg2 into location lock ll beqz reg2 lock CS 740 F 00 centralized software combining tree dissemination barrier tournament barrier MCS tree based barrier if failed start again ret unlock st location 0 write 0 to location ret 15 CS 740 F 00 16 Page 4 CS 740 F 00 Centralized Barrier Software Combining Tree Barrier Basic idea Contention Little contention notify a single shared counter when you arrive poll that shared location until all have arrived Simple implementation require polling spinning twice Flat first to ensure that all procs have left previous barrier second to ensure that all procs have arrived at current barrier Solution to get one spin sense reversal 17 CS 740 F 00 18 Dissemination Barrier CS 740 F 00 Tournament Barrier Binary combining tree Representative processor at a node is statically chosen log P rounds of synchronization In round k proc i synchronizes with proc i 2k mod P Advantage no fetch op needed In round k proc i 2k sets a flag for proc j i 2k Can statically allocate flags to avoid remote spinning 19 Tree structured Writes into one tree for barrier arrival Reads from another tree to allow procs to continue Sense reversal to distinguish consecutive barriers i then drops out of tournament and j proceeds in next round i waits for global flag signalling completion of barrier to be set could use combining wakeup tree CS 740 F 00 20 Page 5 CS 740 F 00 MCS Software Barrier Barrier Recommendations Modifies tournament barrier to allow static allocation in wakeup tree and to use sense reversal Every processor is a node in two P node trees Criteria length of critical path number of network transactions space requirements atomic operation requirements has pointers to its parent building a fanin 4 arrival tree has pointers to its children to build a fanout 2 wakeup tree 21 CS 740 F 00 22 Space Requirements CS 740 F 00 Network Transactions Centralized Centralized combining tree constant O P if broadcast and coherent caches unbounded otherwise MCS combining tree Dissemination O P O PlogP Dissemination Tournament Tournament MCS O PlogP O P 23 CS 740 F 00 24 Page 6 CS 740 F 00 Critical Path Length Primitives Needed If independent parallel network paths available Centralized and combining tree atomic increment atomic decrement all are O logP except centralized which is O P Otherwise e g shared bus Others linear factors dominate 25 atomic read atomic write CS 740 F 00 26 Barrier Recommendations Without broadcast on distributed memory Dissemination MCS is good only critical path length is about 1 5X longer MCS has somewhat better network load and space requirements Cache coherence with broadcast e g a bus MCS with flag wakeup centralized is best for modest numbers of processors Big advantage of centralized barrier adapts to changing number of processors across barrier calls 27 CS 740 F 00 Page 7 CS 740 F 00
View Full Document
Unlocking...