Synchronization viaTransactions1Concurrency QuizIf two threads execute this program concurrently, how many different final values of X are there?Initially, X == 0.void increment() {int temp = X;temp = temp + 1;X = temp;}void increment() {int temp = X;temp = temp + 1;X = temp;}Thread 1 Thread 22Answer:A. 0B. 1C. 2D. More than 2Schedules/InterleavingsModel of concurrent executionInterleave statements from each thread into a single threadIf any interleaving yields incorrect results, some synchronization is neededtmp1 = X;tmp1 = tmp1 + 1;X = tmp1;tmp2 = X;tmp2 = tmp2 + 1;X = tmp2; Thread 1Thread 2tmp1 = X;tmp2 = X;tmp2 = tmp2 + 1;tmp1 = tmp1 + 1;3pp;X = tmp1;X = tmp2;If X==0 initially, X == 1 at the end. WRONG result!Locks fix this with Mutual Exclusionvoid increment() {lock.acquire();int temp = X;temp=temp + 1;Is mutual exclusion really what we want? Don’t we just want the correct result?temp temp + 1;X = temp;lock.release();}4jSome interleavings may give the correct result. Why can’t we keep these?Providing atomicity and isolation directlyCritical regions need atomicity and isolationDefinition: An atomic operation’s effects either allDefinition: An atomic operation s effects either all happen or none happen.¾ Money transfer either debits one acct and credits the other, or no money is transferredDefinition: An isolated operation is not affected by concurrent operations.¾Partial results are not visible5¾Partial results are not visible¾ This allows isolated operations to be put in a single, global orderProviding atomicity and isolation directlyImplementing atomicity and isolation¾ Changes to memory are buffered (isolation)¾ Other processors see old values (isolation)p()¾ If something goes wrong (e.g., exception), system rolls back state to start of critical section (atomicity)¾ When critical region ends, changes become visible all at once (atomicity)Hardware¾ Processor support for buffering and committing values6Software¾ Runtime system buffers and commits valuesTransactionsTransaction begin (xbegin)¾ Start of critical regionTtid(d)Transaction end (xend)¾ End of critical regionxbegin/xend can be implicit with atomic{}Transaction restart (or abort)¾ User decides to abort transaction¾ In Java throwing an exception aborts the transaction7atomic {acctA -= 100;acctB += 100;}Transaction to transfer$100 from acctA toacctB.Atomicity and IsolationAcctA starts with $150Different blocks to update balance¾ Overnight batch process to read/process/write accounts Debit $100¾ Telephone transaction to read/process/write quickly Debit $90Isolation guarantees that phone update is not lost¾ It is allowed by atomicity¾ In fact, both transactions (in either order) should result in overdraft8overdraft AcctA = -$40Atomicity and IsolationAcctA starts with $150Different blocks to update balance¾ Overnight batch process to read/process/write accounts Debit $100¾ Telephone transaction to read/process/write quickly Debit $90Isolation guarantees that phone update is not lost¾ This is a lost updateatomic{9atomic{Read AcctA (150)Decrement AcctAby 100Write AcctA (50)atomic{AcctA -= 90} time AcctA == 200 initially. After these two concurrent transactions AcctA==350. What property does that violate?¾ A. No property is violated¾ B. Atomicity ¾ C. Isolation¾ D. Durabilityatomic{10AcctA += 150}atomic{AcctA -= 90}Atomicity and IsolationAtomicity is hard because¾ Programs make many small changes. Most operations are not atomic, like x++;¾ System must be able to restore state at start of atomic operation What about actions like dispensing money or firing missles?Isolation is hard because¾ More concurrency == more performance¾ …but system must disallow certain interleavings¾ System usually does not allow visibility of isolated state (hence the term isolated)¾ Data structures have multiple invariants that dictate tit it t dt11constraints on a consistent updateMutual exclusion provides isolation¾ Most popular parallel programming techniqueParallel programming: how to provide isolation (and possibly atomicity)Concrete Syntax for TransactionsThe concrete syntax of JDASTM.Transaction tx= new Transaction(id);Transaction tx= new Transaction(id);boolean done = false;while(!done) {try {tx.BeginTransaction();// party on my data structure!done = tx.CommitTransaction();} th(Ab tE ti) {12} catch(AbortExceptione) {tx.AbortTransaction();done = false;}}Transaction’s System BookkeepingTransaction A’s read set is RA¾ Set of objects (addresses) read by transaction ATtiB’ittiWTransaction B’s write set is WB¾ Set of objects (addresses) written by transaction BTransaction A’s address set is RAUNION WA¾ Set of objects (addresses) read or written by transaction Aatomic {13atomic {acctA -= 100;acctB = acctA;}Read: acctAWrite: acctA, acctBTransactional SafetyConflict serializability – If one transaction writes data read or written by another transaction, then abort one transaction.transaction.Recoverability – No transaction that has read data from an uncommitted transaction may commit.atomic {x++;}atomic {load t0, [x]add t0, 114}add t0, 1store t0, [x]}Safe if abort transaction A or B wheneverWA∩ (RBUNION WB) ≠ EMPTYSETSafety examplesTransaction 0Transaction 1atomic {load t0 [x]atomic {ldt0[]load t0, [x]add t0, 1store t0, [x]}load t0, [x]add t0, 115Read:Write:xRead:Write:xxConflict: Transaction 1 should restartHow Isolation Could Be ViolatedDirty readsNon-repeatable readsLost updates16Restarting + I/O = ConfusionTransactions can restart!¾ What kind of output should I expect?Transaction tx new Transaction(id);Transaction tx= new Transaction(id);boolean done = false;while(!done) {try {tx.BeginTransaction();…System.out.println(“Deja vu all over again”);done = tx CommitTransaction();17done = tx.CommitTransaction();} catch(AbortException e) {tx.AbortTransaction();done = false;}}Reading Uncommitted StateWhat about transactional data read outside a transaction?¾Hd t t i lti f ll d¾Hardware support: strong isolation for all reads¾ Software: Uncommitted state is visibleIn your lab, a lane can go from colored to white when a transaction rolls back¾ The GUI updating thread reads uncommitted state outside of a transactionWhy would we want to read data outside of a18Why would we want to read data outside of a transaction?¾ PerformanceTransactional CommunicationConflict serializability is good for keeping transactions out of each other’s address setsSometimes