Unformatted text preview:

Computer Science 425 Distributed SystemsWhy increase Concurrency?Lock Hierarchy for the Banking ExampleLock Hierarchy for a DiaryHierarchical LockingSo far…Optimistic Concurrency ControlSlide 8Optimistic Concurrency Control (2)Validation of TransactionValidation of TransactionsSlide 12Missing Pieces ExplainedTransaction AbortsTimestamp OrderingTimestamp OrderingOperation Conflicts for Timestamp OrderingWhen to accept a WriteWrite Operations and Timestamps (write-write rule 2 only, only write-TS’s shown)Timestamp Ordering Read RuleRead Operations and Timestamps (write-TS’s only shown)Slide 22 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 1Lecture 19- 1Computer Science 425Distributed SystemsComputer Science 425Distributed SystemsLectures 19Concurrency Control (2)Reading: Sections 13.5-13.7 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 2Lecture 19- 2Why increase Concurrency?Why increase Concurrency?•Applications care about concurrency because it improves performance •Applications are willing to tolerate temporary inconsistency and deadlocks in turn•These inconsistencies and deadlocks need to be prevented or detected•Driven and validated by actual application characteristics – mostly-read applications do not have too many conflicting operations anyway 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 3Lecture 19- 3Lock Hierarchy for the Banking ExampleLock Hierarchy for the Banking ExampleBranchAccountA B C•Deposit and withdrawal operations require locking at the granularity of an account.•branchTotal operation acquires a read lock on all of the accounts. 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 4Lecture 19- 4Lock Hierarchy for a DiaryLock Hierarchy for a DiaryWeekMonday Tuesday Wednesday Thursday Friday9:00–10:00time slots10:00–11:0011:00–12:00 12:00–13:00 13:00–14:00 14:00–15:00 15:00–16:00At each level, the setting of a parent lock has the sameeffect as setting all the equivalent child locks. 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 5Lecture 19- 5If objects are in a “part-of” hierarchy, a lock at a higher node implicitly applies to children objects. Before a child node (in the object hierarchy) gets a read/write lock, an intention lock (I-read/I-write) is set for all ancestor nodes. The intention lock is compatible with other intention locks but conflicts with read/write locks according to the usual rules. Lock set Lock requestedread write I-read I-writenone OK OK OK OKread OK WAIT OK WAITwrite WAIT WAIT WAIT WAITI-read OK WAIT OK OKI-write WAIT WAIT OK OKHierarchical Locking Hierarchical Locking 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 6Lecture 19- 6So far…So far…•Concurrency control through LockingDisadvantages of Locking•Overhead of locking and unlocking•Deadlocks may occur, causing delays •Aborts may occur•Strict 2P locking reduces concurrencyAlternative: don’t use locks! 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 7Lecture 19- 7Optimistic Concurrency ControlOptimistic Concurrency Control•Rationale: In most applications, the likelihood of two transactions accessing the same object (in a non read-read pair of ops) is low.•High-level description: Transactions are allowed to proceed optimistically (without any locking), until the closeTransaction request is issued,. At that time concurrency conflict is checked. In case of conflict, some transactions may be aborted.•Each transaction has three phases: working phase, validation phase, and update phase. 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 8Lecture 19- 8Optimistic Concurrency ControlOptimistic Concurrency Control•Each transaction has a tentative version of each object that it updates. The final version is a copy of the most recently committed version of the object.•The first read accesses the committed version, while subsequent reads are from the tentative version.•All writes are to the tentative version. 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 9Lecture 19- 9Optimistic Concurrency Control (2)Optimistic Concurrency Control (2)•Working phase–Each transaction keeps two records:»A read set: list of names of objects read by the transaction.»A write set: list of names of objects written by the transaction.•Validation phase–When the closeTransaction request is received, the transaction is validated to see if its operations conflict with those of other transactions.•Update phase–If a transaction is validated, all of the changes recorded in its tentative versions are made permanent.•Commit=Validation+Update•Trans. aborts can happen only at the commit point (due to conflicts), never during the transaction 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 10Lecture 19- 10Validation of TransactionValidation of Transaction•Each transaction is assigned a transaction number (different from trans. id), T, when it receives closeTransaction.–A transaction with Ti always precedes a transaction with Tv if i < v.•For a transaction Tv to be serializable w.r.t. an overlapping transaction Ti we can define these (conservative) rules:TvTiRulewrite read 1. Ti must not read objects written by Tvread write 2. Tv must not read objects written by Tiwrite write 3. Ti must not write objects written by Tv and Tv must not write objects written by Ti 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 11Lecture 19- 11Validation of TransactionsValidation of TransactionsEarlier committedtransactionsWorking Validation UpdateT1TvTransactionbeing validatedT2T3Later activetransactionsactive1active2NOW 2002 M. T. Harandi and J. Hou (modified: I. Gupta) Lecture 19- 12Lecture 19- 12Validation of TransactionsValidation of TransactionsTvTiRulewrite read 1. Ti must not read objects written by Tvread write 2. Tv must not read objects written by Tiwrite write 3. Ti must not write objects written by Tv and Tv must not write objects written by TiAt any time, at most 1 transaction maybe in the validation+update phases.Backward validation of transaction Tvboolean valid = true;for (int Ti = startTn+1; Ti <= finishTn; Ti++){if (read set of Tv intersects write set of Ti) valid = false;}Forward validation of transaction Tvboolean valid = true;for (int Tid = active1; Tid <= activeN;


View Full Document

ILLINOIS CS 425 - Concurrency Control

Documents in this Course
Load more
Download Concurrency Control
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Concurrency Control and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concurrency Control 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?