1Lecture 4: Directory Protocols and TM• Topics: corner cases in directory protocols, lazy TM2Handling Reads• When the home receives a read request, it looks upmemory (speculative read) and directory in parallel• Actions taken for each directory state: shared or unowned: memory copy is clean, datais returned to requestor, state is changed to excl ifthere are no other sharers busy: a NACK is sent to the requestor exclusive: home is not the owner, request is fwdedto owner, owner sends data to requestor and home3Inner Details of Handling the Read• The block is in exclusive state – memory may or may nothave a clean copy – it is speculatively read anyway• The directory state is set to busy-exclusive and thepresence vector is updated• In addition to fwding the request to the owner, the memorycopy is speculatively forwarded to the requestor Case 1: excl-dirty: owner sends block to requestorand home, the speculatively sent data is over-written Case 2: excl-clean: owner sends an ack (without data)to requestor and home, requestor waits for this ackbefore it moves on with speculatively sent data4Inner Details II• Why did we send the block speculatively to the requestorif it does not save traffic or latency? the R10K cache controller is programmed to notrespond with data if it has a block in excl-clean state when an excl-clean block is replaced from the cache,the directory need not be updated – hence, directorycannot rely on the owner to provide data andspeculatively provides data on its own5Handling Write Requests• The home node must invalidate all sharers and allinvalidations must be acked (to the requestor), the requestor is informed of the number of invalidates to expect• Actions taken for each state: shared: invalidates are sent, state is changed toexcl, data and num-sharers are sent to requestor,the requestor cannot continue until it receives all acks(Note: the directory does not maintain busy state,subsequent requests will be fwded to new ownerand they must be buffered until the previous writehas completed)6Handling Writes II• Actions taken for each state: unowned: if the request was an upgrade and not aread-exclusive, is there a problem? exclusive: is there a problem if the request was anupgrade? In case of a read-exclusive: directory isset to busy, speculative reply is sent to requestor,invalidate is sent to owner, owner sends data torequestor (if dirty), and a “transfer of ownership”message (no data) to home to change out of busy busy: the request is NACKed and the requestormust try again7Handling Write-Back• When a dirty block is replaced, a writeback is generatedand the home sends back an ack • Can the directory state be shared when a writeback isreceived by the directory?• Actions taken for each directory state: exclusive: change directory state to unowned andsend an ack busy: a request and the writeback have crossedpaths: the writeback changes directory state toshared or excl (depending on the busy state),memory is updated, and home sends data torequestor, the intervention request is dropped8Writeback CasesP1 P2D3E: P1WbackThis is the “normal” caseD3 sends back an AckAck9Writeback CasesP1 P2D3E: P1 busyWbackIf someone else has the block in exclusive, D3 moves to busyIf Wback is received, D3 serves the requesterIf we didn’t use busy state when transitioning from E:P1 to E:P2, D3 may not have known who to service(since ownership may have been passed on to P3 and P4…)(although, this problem can be solved by NACKing the Wbackand having P1 buffer its “strange” intervention requests…this could lead to other corner cases… )FwdRd or Wr10Writeback CasesP1 P2D3E: P1 busyTransferownershipIf Wback is from new requester, D3 sends back a NACKFloating unresolved messages are a problemAlternatively, can accept the Wback and put D3 in some new busy stateConclusion: could have got rid of busy state between E:P1  E:P2, butwith Wback ACK/NACK and other bufferingcould have kept the busy state between E:P1  E:P2, couldhave got rid of ACK/NACK, but need one new busy stateFwdWbackData11Transactions• Access to shared variables is encapsulated withintransactions – the system gives the illusion that thetransaction executes atomically – hence, the programmerneed not reason about other threads that may be runningin parallel with the transactionConventional model: TM model:… …lock(L1); trans_begin();access shared vars access shared varsunlock(L1); trans_end();… …12Transactions• Transactional semantics: when a transaction executes, it is as if the rest of thesystem is suspended and the transaction is in isolation the reads and writes of a transaction happen as if theyare all a single atomic operation if the above conditions are not met, the transactionfails to commit (abort) and tries againtransaction beginread shared variablesarithmeticwrite shared variablestransaction end13Why are Transactions Better?• High performance with little programming effort Transactions proceed in parallel most of the timeif the probability of conflict is low (programmers neednot precisely identify such conflicts and findwork-arounds with say fine-grained locks) No resources being acquired on transaction start;lesser fear of deadlocks in code Composability14ExampleProducer-consumer relationships – producers place tasks at the tail ofa work-queue and consumers pull tasks out of the headEnqueue Dequeuetransaction begin transaction beginif (tail == NULL) if (head->next == NULL)update head and tail update head and tailelse elseupdate tail update headtransaction end transaction endWith locks, neither thread can proceed in parallel since head/tail may beupdated – with transactions, enqueue and dequeue can proceed inparallel – transactions will be aborted only if the queue is nearly empty15ExampleIs it possible to have a transactional program that deadlocks,but the program does not deadlock when using locks?flagA = flagB = false;thr-1 thr-2lock(L1) lock(L2)while (!flagA) {}; flagA = true;flagB = true; while (!flagB) {};* *unlock(L1) unlock(L2)• Somewhat contrived• The code implements a barrier before getting to *• Note that we are using different lock variables16Atomicity• Blindly replacing locks-unlocks