Java程序辅导

Overview: Transactions (II)
Assignment 2 Q&A
l assign (node) ids to processes, pass parent’s listen port to child: see Lab7 answers
l listen ports for each process: fixed (potential pitfal!), parent creates list of port
numbers via setsockopt( sock, SOL SOCKET, SO REUSEADDR, ...) , others?
l building routing table: base on node id, use getMinLinks() in netAux.h (netAux.c)
Ref: [Coulouris&al Ch 16.5–7, 17.1–3]
l concurrency control
n optimistic: backward validation, comparison to locking
n timestamp ordering: write and read rules, example
l comparison of concurrency control methods
l distributed transactions
n two-phase commit protocol
n performance and recovery issues
(diagrams and most examples from Ch 16-17 of Coulouris et al. Distributed Systems)
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 1
Optimistic Concurrency Control
l motivations: problems with lock-based methods
n locking has considerable overheads: required even on read-only transactions
which cannot possibly affect data integrity
u if conflict is unlikely, this is wasteful
n can lead to deadlock; prevention reduces concurrency, detection has overhead
l consists of three phases:
n working phase: updates create a tentative version of object
u subsequent reads by same transaction see this; others see original version
(dirty reads thus cannot occur!)
u a read set & write set of objects accessed by each transaction is maintained
n validation phase: upon a closeTrans(), determine whether the operations of
this transaction conflict with those of others (if so, abort)
n update phase: the tentative version of the updated objects are made
permanent (and visible to future transactions)
l when entering the validation phase, a transaction number (timestamp) Tv is
allocated to the transaction
n this must be produced non-concurrently, i.e. in a critical section
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 2
Optimistic Concurrency Control: Backward Validation
l backward validation: check consistency with previous overlapping transactions
l Tv is valid iff all for each T :Tw. .Tv−1, the read set of Tv and the write set of T do
not overlap
n Tw is timestamp when current transaction Tv entered its working phase(earliest timestamp in its read/write sets)
l e.g. ([Coulouris&al Fig 16.28]) Tv must be compared with T2 and T3 only
n issue: write sets of T1, T1, T3 and Tv must be maintained till active1 completes

**

'" 9 5

6

&"+

(
4+

+

+

l can also have forward validation: check write set of Tv does not overlap with read
sets of active1 and active2
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 3
Optimistic Concurrency Control: Analysis
l √deadlock free, permits maximum concurrency
n concurrency good even if validate and update stages done in a critical section
(simplest scheme)
l ×may require many tentative copies of objects at any time
l ×with many overlapping and conflicting transactions, this scheme breaks down
rapidly
n leads to possible starvation and livelocks
n starvation can be dealt with by granting previously aborted transactions
exclusive access to its required objects
l generally:
n locking methods better for update-intensive transactions
n optimistic method better for read-intensive transactions
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 4
Concurrency Control by Timestamp Ordering
l idea: each operation in a transaction is validated when it is carried out
l assign a unique timestamp Tc to each transaction when it starts
n this also serves as the transaction id
l every object has a set of tentative versions
n each with read and write timestamps > the timestamp for the committed version
n these timestamps are those of the accessing transaction
l rules: for each newer transaction Ti (Ti > Tc):
1. Tc must not write to object read by Ti (Tc ≥ max. read stamp of object)
2. Tc must not read or write to object written by Ti (Tc > committed write
timestamp of object)
l if these rules fail, Tc is aborted (too late!)
l upon a read, if there are uncommitted writes by earlier transactions, Tc is made to
wait until the oldest commits (then re-evaluates the rule 2 (for read))
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 5
Timestamp Ordering: Write Rules

.	
 

 . 
8





*








9'&
'

*:
.


.
*%@*#@*.@*/
*
7


 (
*
7


 (


*
7



)
( )
*

&
7

)
)
+
**


A
([Coulouris&al Fig 16.30])
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 6
Timestamp Ordering: Read Rules
9:
*.

*




*



 )
*
0

 
*

&
)
A
+
**


8





*


9'&
'

*:


*%
@
*#
@

*.
@

*/
9:
*.

9:
*.

9
:
*.

([Coulouris&al Fig 16.31])
COMP2310 Lecture 28: Transactions (II) 2013 JJ J • I II × 7
Timestamp Ordering: Example
l ([Coulouris&al Fig 16.32]) transaction order S < T