Transcript Document

9
Chapter 9_B
Concurrency Control
Database Systems:
Design, Implementation, and Management,
Rob and Coronel
1
In this chapter, you will learn:
9
• What a database transaction is and what its properties
are
• What concurrency control is and what role it plays in
maintaining the database’s integrity
• What locking methods are and how they work
• How stamping methods are used for concurrency control
• How optimistic methods are used for concurrency control
• How database recovery management is used to maintain
database integrity
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
2
9
Concurrency Control
• Coordination of simultaneous transaction
execution in a multiprocessing database
system
• Objective is to ensure serializability of
transactions in a multiuser database
environment
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
3
9
Concurrency Control (continued)
• Simultaneous execution of transactions over
a shared database can create several data
integrity and consistency problems:
– Lost updates
– Uncommitted data
– Inconsistent retrievals
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
4
Lost Updates
9
Assume that you have a product whose current
PROD_QOH value is 35
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
5
Lost Updates (continued)
9
Suppose that a transaction is able to read a product’s
PROD_QOH value from the table before a previous
transaction (using the same product) has been
committed
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
6
Uncommitted Data
9
The phenomenon of uncommitted data occurs when two transactions, T1 and
T2, are executed concurrently and the first transaction (T1) is rolled back after
the second transaction (T2) has already accessed the uncommitted data—thus
violating the isolation property of transactions. T1 is forced to roll back due to
an error during the update of the invoice total; hence, it rolls back all the way,
undoing the inventory update
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
7
9
Uncommitted Data (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
8
Sun 23-6 Inconsistent Retrievals
9
Inconsistent retrievals occur when a transaction accesses data before and
after another transaction(s) finish working with such data.
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
9
9
Inconsistent Retrievals (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
10
9
Inconsistent Retrievals (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
11
9
The Scheduler
• Special DBMS program
– Purpose is to establish order of operations
within which concurrent transactions are
executed
• Interleaves execution of database operations
to ensure serializability and isolation of
transactions
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
12
9
The Scheduler (continued)
• Bases its actions on concurrency control
algorithms, like locking and time stamping.
• Ensures computer’s central processing unit
(CPU) is used efficiently, not based on FCFS
• Facilitates data isolation to ensure that two
transactions do not update same data
element at same time
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
13
9
The Scheduler (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
14
9
Concurrency Control
with Locking Methods
• Lock
– Guarantees exclusive use of a data item to a
current transaction
– Required to prevent another transaction from
reading inconsistent data
• Lock manager
– Responsible for assigning and policing the
locks used by transactions
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
15
9
Lock Granularity
• Indicates level of lock use
• Locking can take place at following levels:
–
–
–
–
–
Database
Table
Page
Row
Field (attribute)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
16
9
Lock Granularity (continued)
• Database-level lock
– Entire database is locked
• Table-level lock
– Entire table is locked
• Page-level lock
– Entire diskpage is locked
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
17
9
Lock Granularity (continued)
• Row-level lock
– Allows concurrent transactions to access
different rows of same table, even if rows are
located on same page
• Field-level lock
– Allows concurrent transactions to access
same row, as long as they require use of
different fields (attributes) within that row
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
18
9
Lock Granularity (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
19
9
Lock Granularity (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
20
9
Lock Granularity (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
21
9
Lock Granularity (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
22
9
Mon 24-6 Lock Types
• Binary lock
– Has only two states: locked (1) or unlocked (0)
• Exclusive lock
– Access is specifically reserved for transaction that
locked object
– Must be used when potential for conflict exists
• Shared lock
– Concurrent transactions are granted Read access
on basis of a common lock
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
23
9
Lock Types (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
24
9
Two-Phase Locking
to Ensure Serializability
• Defines how transactions acquire and
relinquish locks
• Guarantees serializability, but it does not
prevent deadlocks
– Growing phase - Transaction acquires all
required locks without unlocking any data
– Shrinking phase - Transaction releases all
locks and cannot obtain any new lock
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
25
9
Two-Phase Locking
to Ensure Serializability (continued)
• Governed by the following rules:
– Two transactions cannot have conflicting locks
– No unlock operation can precede a lock
operation in the same transaction
– No data are affected until all locks are
obtained—that is, until transaction is in its
locked point
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
26
9
Two-Phase Locking
to Ensure Serializability (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
27
9
Deadlocks
• Condition that occurs when two transactions
wait for each other to unlock data
• Possible only if one of the transactions wants
to obtain an exclusive lock on a data item
– No deadlock condition can exist among
shared locks
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
28
Deadlocks (continued)
9
• Control through:
– Prevention :A transaction requesting a new lock is
aborted (rolled back and rescheduled) when there is
the possibility that a deadlock can occur.
– Detection :The DBMS periodically tests the
database for deadlocks. If a deadlock is found, one
of the transactions (the “victim”) is aborted (rolled
back and restarted) and the other transaction
continues.
– Avoidance :The transaction must obtain all of the
locks it needs before it can be executed
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
29
9
Deadlocks (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
30
9
Concurrency Control
with Time Stamping Methods
• Assigns global unique time stamp to each
transaction
• Produces explicit order in which transactions are
submitted to DBMS
• Uniqueness
– Ensures that no equal time stamp values can exist
• Monotonicity
– Ensures that time stamp values always increase
• All database operations (READ and WRITE) within
the same transaction must have the same time stamp
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
31
9
Tue 25-6 Wait/Die and Wound/Wait
Schemes
• Wait/die
– Older transaction waits and younger is rolled
back and rescheduled
• Wound/wait
– Older transaction rolls back younger
transaction and reschedules it
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
32
9
Wait/Die and Wound/Wait Schemes
(continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
33
Concurrency Control
with Optimistic Methods
9
• Optimistic approach
– Based on assumption that majority of
database operations do not conflict
– Does not require locking or time stamping
techniques
– Transaction is executed without restrictions
until it is committed
– Phases are read, validation, and write
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
34
Concurrency Control
with Optimistic Methods (cont.)
9
• During the read phase, the transaction reads the database,
executes the needed computations, and makes the updates
to a private copy of the database values. All update
operations of the transaction are recorded in a temporary
update file, which is not accessed by the remaining
transactions.
•
During the validation phase, the transaction is validated to
ensure that the changes made will not affect the integrity and
consistency of the database. If the validation test is positive,
the transaction goes to the write phase. If the validation test is
negative, the transaction is restarted and the changes are
discarded.
•
During the write phase, the changes are permanently applied
to the database.
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
35
Database Recovery Management
9
• Database recovery (managed through backups)
– Restores database from given state, usually
inconsistent, to previously consistent state
– Based on atomic transaction property
• All portions of transaction must be treated as
single logical unit of work, so all operations
must be applied and completed to produce
consistent database
– If transaction operation cannot be completed,
transaction must be aborted, and any changes to
database must be rolled back (undone)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
36
9
Transaction Recovery
• Makes use of deferred-write and writethrough techniques
• Deferred write
– Transaction operations do not immediately
update physical database
– Only transaction log is updated
– Database is physically updated only after
transaction reaches its commit point using
transaction log information
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
37
9
Transaction Recovery (continued)
• Write-through
– Database is immediately updated by
transaction operations during transaction’s
execution, even before transaction reaches its
commit point.
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
38
9
Transaction Recovery (continued)
Database Systems: Design, Implementation, & Management, 8th Edition, Rob & Coronel
39