MICHAEL MUTERO

M173684
PRESENTATION ON CONCURRENCY
CONTROL AND RECOVERY
 WHAT IS CONCURRENCY?

• CONCURRENCY IS THE ABILITY OF THE DBMS TO PROCESS MORE THAN ONE

TRANSACTION AT A TIME
• CONCURRENCY CONTROL IS THE ACTIVITY OF COORDINATING CONCURRENT
ACCESSES TO A DATABASE IN A MULTIUSER DATABASE MANAGEMENT SYSTEM
(DBMS).
• CONCURRENCY CONTROL PERMITS USERS TO ACCESS A DATABASE IN A MULTI
PROGRAMMED FASHION WHILE PRESERVING THE ILLUSION THAT EACH USER IS
EXECUTING ALONE ON A DEDICATED SYSTEM.
 INTERLEAVED CONCURRENCY
• MANY COMPUTER SYSTEMS, INCLUDING DBMSS, ARE USED SIMULTANEOUSLY BY
MORE THAN ONE USER. THIS MEANS THE COMPUTER RUNS MULTIPLE
TRANSACTIONS (PROGRAMS) AT THE SAME TIME. FOR EXAMPLE, AN AIRLINE
RESERVATIONS SYSTEM IS USED BY HUNDREDS OF TRAVEL AGENTS AND
RESERVATION CLERKS CONCURRENTLY. SYSTEMS IN BANKS, INSURANCE AGENCIES,
STOCK EXCHANGES AND THE LIKE ARE ALSO OPERATED BY MANY USERS WHO
SUBMIT TRANSACTIONS CONCURRENTLY TO THE SYSTEM. IF, AS IS OFTEN THE CASE,
THERE IS ONLY ONE CPU, THEN ONLY ONE PROGRAM CAN BE PROCESSED AT A TIME.
TO AVOID EXCESSIVE DELAYS, CONCURRENT SYSTEMS EXECUTE SOME COMMANDS
FROM ONE PROGRAM (TRANSACTION), THEN SUSPENDED THAT PROGRAM AND
EXECUTE SOME COMMANDS FROM THE NEXT PROGRAM, AND SO ON. A PROGRAM IS
RESUMED AT THE POINT WHERE IT WAS SUSPENDED WHEN IT GETS ITS TURN TO USE
THE CPU AGAIN. THIS IS KNOWN AS INTERLEAVING.
 THE FIGURE BELOW SHOWS TWO PROGRAMS A AND B EXECUTING
CONCURRENTLY IN AN INTERLEAVED FASHION. INTERLEAVING
KEEPS THE CPU BUSY WHEN AN EXECUTING PROGRAM REQUIRES AN
INPUT OR OUTPUT (I/O) OPERATION, SUCH AS READING A BLOCK OF
DATA FROM DISK. THE CPU IS SWITCHED TO EXECUTE ANOTHER
PROGRAM RATHER THAN REMAINING IDLE DURING I/O TIME.
 INTERLEAVED VS SIMULTANEOUS
CONCURRENCY
• IF THE COMPUTER SYSTEM HAS MULTIPLE HARDWARE PROCESSORS (CPUS),
SIMULTANEOUS PROCESSING OF MULTIPLE PROGRAMS IS POSSIBLE, LEADING TO
SIMULTANEOUS RATHER THAN INTERLEAVED CONCURRENCY
• MOST OF THE THEORY CONCERNING CONCURRENCY CONTROL IN DATABASES IS
DEVELOPED IN TERMS OF INTERLEAVED CONCURRENCY, ALTHOUGH IT MAY BE
ADAPTED TO SIMULTANEOUS CONCURRENCY.
 INTERLEAVED CONCURRENCY, AS
ILLUSTRATED BY PROGRAM C AND D IN THE
FIGURE BELOW.
 GENUINE VS APPEARANCE OF
CONCURRENCY
• CONCURRENCY IS THE ABILITY OF THE DATABASE MANAGEMENT SYSTEM TO
PROCESS MORE THAN ONE TRANSACTION AT A TIME. YOU SHOULD DISTINGUISH
GENUINE CONCURRENCY FROM THE APPEARANCE OF CONCURRENCY. THE
DATABASE MANAGEMENT SYSTEM MAY QUEUE TRANSACTIONS AND PROCESS
THEM IN SEQUENCE. TO THE USERS IT WILL APPEAR TO BE CONCURRENT BUT
FOR THE DATABASE MANAGEMENT SYSTEM IT IS NOTHING OF THE KIND.
 READ AND WRITE OPERATIONS
• WE DEAL WITH TRANSACTIONS AT THE LEVEL OF DATA ITEMS AND DISK BLOCKS FOR THE
PURPOSE OF DISCUSSING CONCURRENCY CONTROL AND RECOVERY TECHNIQUES. AT THIS
LEVEL, THE DATABASE ACCESS OPERATIONS THAT A TRANSACTION CAN INCLUDE ARE:
• • READ_ITEM(X): READS A DATABASE ITEM NAMED X INTO A PROGRAM VARIABLE ALSO
NAMED X.
• • WRITE_ITEM(X): WRITES THE VALUE OF PROGRAM VARIABLE X INTO THE DATABASE
ITEM NAMED X.
• EXECUTING A READ_ITEM(X) COMMAND INCLUDES THE FOLLOWING STEPS:
1. FIND THE ADDRESS OF THE DISK BLOCK THAT CONTAINS ITEM X.
2. COPY THE DISK BLOCK INTO A BUFFER IN MAIN MEMORY IF THAT DISK IS NOT ALREADY
IN SOME MAIN MEMORY BUFFER.
3. COPY ITEM X FROM THE BUFFER TO THE PROGRAM VARIABLE NAMED X.
• EXECUTING A WRITE_ITEM(X) COMMAND INCLUDES THE FOLLOWING STEPS:

1. FIND THE ADDRESS OF THE DISK BLOCK THAT CONTAINS ITEM X.

2. COPY THE DISK BLOCK INTO A BUFFER IN MAIN MEMORY IF THAT DISK IS NOT
ALREADYING SOME MAIN MEMORY BUFFER.
3. COPY ITEM X FROM THE PROGRAM VARIABLE NAMED X INTO ITS CORRECT
LOCATION IN THE BUFFER.
4. STORE THE UPDATED BLOCK FROM THE BUFFER BACK TO DISK (EITHER
IMMEDIATELY OR AT SOME LATER POINT IN TIME).
• STEP 4 IS THE ONE THAT ACTUALLY UPDATES THE DATABASE ON DISK. IN SOME
CASES THE BUFFER IS NOT IMMEDIATELY STORED TO DISK, IN CASE ADDITIONAL
CHANGES ARE TO BE MADE TO THE BUFFER. USUALLY, THE DECISION ABOUT
WHEN TO STORE BACK A MODIFIED DISK BLOCK THAT IS IN A MAIN MEMORY
BUFFER IS HANDLED BY THE RECOVERY MANAGER OR THE OPERATING SYSTEM.
A TRANSACTION WILL INCLUDE READ AND WRITE OPERATIONS TO ACCESS THE DATABASE.
THE FIGURE BELOW SHOWS EXAMPLES OF TWO VERY SIMPLE TRANSACTIONS.
CONCURRENCY CONTROL AND RECOVERY MECHANISMS ARE MAINLY CONCERNED WITH
THE DATABASE ACCESS COMMANDS IN A TRANSACTION.
• THE ABOVE TWO TRANSACTIONS SUBMITTED BY ANY TWO DIFFERENT USERS
MAY BE EXECUTED CONCURRENTLY AND MAY ACCESS AND UPDATE THE SAME
DATABASE ITEMS (E.G. X). IF THIS CONCURRENT EXECUTION IS UNCONTROLLED,
IT MAY LEAD TO PROBLEMS SUCH AS AN INCONSISTENT DATABASE. SOME OF
THE PROBLEMS THAT MAY OCCUR WHEN CONCURRENT TRANSACTIONS
EXECUTE IN AN UNCONTROLLED MANNER.
• TRANSACTION T1 CANCELS N RESERVATIONS FROM ONE FLIGHT, WHOSE
NUMBER OF RESERVED SEATS IS STORED IN THE DATABASE ITEM NAMED X, AND
RESERVES THE SAME NUMBER OF SEATS ON ANOTHER FLIGHT, WHOSE NUMBER
OF RESERVED SEATS IS STORED IN THE DATABASE ITEM NAMED Y. A SIMPLER
TRANSACTION T2 JUST RESERVES M SEATS ON THE FIRST FLIGHT REFERENCED IN
TRANSACTION T1. TO SIMPLIFY THE EXAMPLE, THE ADDITIONAL PORTIONS OF
THE TRANSACTIONS ARE NOT SHOWN, SUCH AS CHECKING WHETHER A FLIGHT
HAS ENOUGH SEATS AVAILABLE BEFORE RESERVING ADDITIONAL SEATS.
• WHEN AN AIRLINE RESERVATION DATABASE PROGRAM IS WRITTEN, IT HAS THE
FLIGHT NUMBERS, THEIR DATES AND THE NUMBER OF SEATS AVAILABLE FOR
BOOKING AS PARAMETERS; HENCE, THE SAME PROGRAM CAN BE USED TO
EXECUTE MANY TRANSACTIONS, EACH WITH DIFFERENT FLIGHTS AND NUMBER
OF SEATS TO BE BOOKED. FOR CONCURRENCY CONTROL PURPOSES, A
TRANSACTION IS A PARTICULAR EXECUTION OF A PROGRAM ON A SPECIFIC
DATE, FLIGHT AND NUMBER OF SEATS. THE TRANSACTIONS T1 AND T2 ARE
SPECIFIC EXECUTIONS OF THE PROGRAMS THAT REFER TO THE SPECIFIC FLIGHTS
WHOSE NUMBERS OF SEATS ARE STORED IN DATA ITEM X AND Y IN THE
DATABASE. NOW LET’S DISCUSS THE TYPES OF PROBLEMS WE MAY ENCOUNTER
WITH THESE TWO TRANSACTIONS.
 THE LOST UPDATE PROBLEM
• THE LOST UPDATE PROBLEM OCCURS WHEN TWO TRANSACTIONS THAT ACCESS
THE SAME DATABASE ITEMS HAVE THEIR OPERATIONS INTERLEAVED IN A WAY
THAT MAKES THE VALUE OF SOME DATABASE ITEM INCORRECT. THAT IS,
INTERLEAVED USE OF THE SAME DATA ITEM WOULD CAUSE SOME PROBLEMS
WHEN AN UPDATE OPERATION FROM ONE TRANSACTION OVERWRITES ANOTHER
UPDATE FROM A SECOND TRANSACTION.
 UNCOMMITTED DEPENDENCY (OR DIRTY
READ / TEMPORARY UPDATE)
• UNCOMMITTED DEPENDENCY OCCURS WHEN A TRANSACTION IS ALLOWED TO
RETRIEVE OR (WORSE) UPDATE A RECORD THAT HAS BEEN UPDATED BY
ANOTHER TRANSACTION, BUT WHICH HAS NOT YET BEEN COMMITTED BY THAT
OTHER TRANSACTION. BECAUSE IT HAS NOT YET BEEN COMMITTED, THERE IS
ALWAYS A POSSIBILITY THAT IT WILL NEVER BE COMMITTED BUT RATHER
ROLLED BACK, IN WHICH CASE, THE FIRST TRANSACTION WILL HAVE USED
SOME DATA THAT IS NOW INCORRECT - A DIRTY READ FOR THE FIRST
TRANSACTION.
 INCONSISTENT ANALYSIS

• INCONSISTENT ANALYSIS OCCURS WHEN A TRANSACTION READS SEVERAL

VALUES, BUT A SECOND TRANSACTION UPDATES SOME OF THESE VALUES
DURING THE EXECUTION OF THE FIRST. THIS PROBLEM IS SIGNIFICANT, FOR
EXAMPLE, IF ONE TRANSACTION IS CALCULATING AN AGGREGATE SUMMARY
FUNCTION ON A NUMBER OF RECORDS WHILE OTHER TRANSACTIONS ARE
UPDATING SOME OF THESE RECORDS. THE AGGREGATE FUNCTION MAY
CALCULATE SOME VALUES BEFORE THEY ARE UPDATED AND OTHERS AFTER
THEY ARE UPDATED. THIS CAUSES AN INCONSISTENCY.
 NEED FOR RECOVERY
• WHENEVER A TRANSACTION IS SUBMITTED TO A DBMS FOR EXECUTION, THE SYSTEM
IS RESPONSIBLE FOR MAKING SURE THAT EITHER:
1. ALL THE OPERATIONS IN THE TRANSACTION ARE COMPLETED SUCCESSFULLY AND
THE EFFECT IS RECORDED PERMANENTLY IN THE DATABASE; OR
2. THE TRANSACTION HAS NO EFFECT WHATSOEVER ON THE DATABASE OR ON ANY
OTHER TRANSACTIONS.
• THE DBMS MUST NOT PERMIT SOME OPERATIONS OF A TRANSACTION T TO BE APPLIED
TO THE DATABASE WHILE OTHER OPERATIONS OF T ARE NOT. THIS MAY HAPPEN IF A
TRANSACTION FAILS AFTER EXECUTING SOME OF ITS OPERATIONS BUT BEFORE
EXECUTING ALL OF THEM.
 SERIALISABILITY

• THIS IS A CRITERION THAT MOST CONCURRENCY CONTROL METHODS ENFORCE.

INFORMALLY, IF THE EFFECT OF RUNNING TRANSACTIONS IN AN INTERLEAVED
FASHION IS EQUIVALENT TO RUNNING THE SAME TRANSACTIONS IN A SERIAL
ORDER, THEY ARE CONSIDERED SERIALISABLE. WE HAVE USED THE WORD
‘SCHEDULE’ WITHOUT A DEFINITION BEFORE IN THIS CHAPTER. IN THIS SECTION,
WE WILL FIRST DEFINE THE CONCEPT OF TRANSACTION SCHEDULE, AND THEN
WE CHARACTERISE THE TYPES OF SCHEDULES THAT FACILITATE RECOVERY
WHEN FAILURES OCCUR.
LOCKING TECHNIQUES FOR CONCURRENCY
CONTROL
1 BINARY LOCKS
• A BINARY LOCK CAN HAVE TWO STATES OR VALUES: LOCKED AND UNLOCKED (OR 1 AND 0, FOR SIMPLICITY). A
DISTINCT LOCK IS ASSOCIATED WITH EACH DATABASE ITEM X. IF THE VALUE OF THE LOCK ON X IS 1, ITEM X IS
LOCKED AND CANNOT BE ACCESSED BY A DATABASE OPERATION THAT REQUESTS THE ITEM. IF THE VALUE OF THE
LOCK ON X IS 0, ITEM X IS UNLOCKED, AND IT CAN BE ACCESSED WHEN REQUESTED. WE REFER TO THE VALUE OF
THE LOCK ASSOCIATED WITH ITEM X AS LOCK(X). TWO OPERATIONS, LOCK AND UNLOCK, MUST BE INCLUDED IN
THE TRANSACTIONS WHEN BINARY LOCKING IS USED. A TRANSACTION REQUESTS ACCESS TO AN ITEM X BY
ISSUING A LOCK(X) OPERATION. IF LOCK(X) = 1, THE TRANSACTION IS FORCED TO WAIT; OTHERWISE, THE
TRANSACTION SETS LOCK(X) := 1 (LOCKS THE ITEM) AND ALLOWS ACCESS. WHEN THE TRANSACTION IS THROUGH
USING THE ITEM, IT ISSUES AN UNLOCK(X) OPERATION, WHICH SETS LOCK(X) := 0 (UNLOCKS THE ITEM) SO THAT X
MAY BE ACCESSED BY OTHER TRANSACTIONS. HENCE, A BINARY LOCK ENFORCES MUTUAL EXCLUSION ON THE
DATA ITEM. THE DBMS HAS A LOCK MANAGER SUBSYSTEM TO KEEP TRACK OF AND CONTROL ACCESS TO LOCKS.
• WHEN THE BINARY LOCKING SCHEME IS USED, EVERY TRANSACTION MUST OBEY THE
FOLLOWING RULES:
1. A TRANSACTION T MUST ISSUE THE OPERATION LOCK(X) BEFORE ANY READ_ITEM(X) OR
WRITE_ITEM(X) OPERATIONS ARE PERFORMED IN T.
2. A TRANSACTION T MUST ISSUE THE OPERATION UNLOCK(X) AFTER ALL READ_ITEM(X)
AND WRITE_ITEM(X) OPERATIONS ARE COMPLETED IN T.
3. A TRANSACTION T WILL NOT ISSUE A LOCK(X) OPERATION IF IT ALREADY HOLDS THE
LOCK ON ITEM X.
4. A TRANSACTION T WILL NOT ISSUE AN UNLOCK(X) OPERATION UNLESS IT ALREADY
HOLDS THE LOCK ON ITEM X.
• THESE RULES CAN BE ENFORCED BY A MODULE OF THE DBMS. BETWEEN THE LOCK(X)
AND UNLOCK(X) OPERATIONS IN A TRANSACTION T, T IS SAID TO HOLD THE LOCK ON ITEM
X. AT MOST, ONE TRANSACTION CAN HOLD THE LOCK ON A PARTICULAR ITEM. NO TWO
TRANSACTIONS CAN ACCESS THE SAME ITEM CONCURRENTLY.
 2. SHARED AND EXCLUSIVE LOCKS

• THE BINARY LOCKING SCHEME DESCRIBED ABOVE IS TOO RESTRICTIVE IN GENERAL, BECAUSE AT
MOST ONE TRANSACTION CAN TAKE HOLD ON A GIVEN ITEM. WE SHOULD ALLOW SEVERAL
TRANSACTIONS TO ACCESS THE SAME ITEM X IF THEY ALL ACCESS X FOR READING PURPOSES ONLY.
HOWEVER, IF A TRANSACTION IS TO WRITE AN ITEM X, IT MUST HAVE EXCLUSIVE ACCESS TO X. FOR
THIS PURPOSE, WE CAN USE A DIFFERENT TYPE OF LOCK CALLED MULTIPLE-MODE LOCK. IN THIS
SCHEME, THERE ARE THREE LOCKING OPERATIONS: READ_LOCK(X), WRITE_LOCK(X) AND
UNLOCK(X). THAT IS, A LOCK ASSOCIATED WITH AN ITEM X, LOCK(X), NOW HAS THREE POSSIBLE
STATES: ‘READ-LOCKED’, ‘WRITE-LOCKED’ OR ‘UNLOCKED’. A READ-LOCKED ITEM IS ALSO CALLED
SHARE-LOCKED, BECAUSE OTHER TRANSACTIONS ARE ALLOWED TO READ ACCESS THAT ITEM,
WHEREAS A WRITE-LOCKED ITEM IS CALLED EXCLUSIVE-LOCKED, BECAUSE A SINGLE TRANSACTION
EXCLUSIVELY HOLDS THE LOCK ON THE ITEM.
• IF A DBMS WISHES TO READ AN ITEM, THEN A SHARED (S) LOCK IS PLACED ON
THAT ITEM. IF A TRANSACTION HAS A SHARED LOCK ON A DATABASE ITEM, IT CAN
READ THE ITEM BUT NOT UPDATE IT. IF A DBMS WISHES TO WRITE (UPDATE) AN
ITEM, THEN AN EXCLUSIVE (X) LOCK IS PLACED ON THAT ITEM. IF A TRANSACTION
HAS AN EXCLUSIVE LOCK ON AN ITEM, IT CAN BOTH READ AND UPDATE IT. TO
PREVENT INTERFERENCE FROM OTHER TRANSACTIONS, ONLY ONE TRANSACTION
CAN HOLD AN EXCLUSIVE LOCK ON AN ITEM AT ANY GIVEN TIME.
• IF A TRANSACTION A HOLDS A SHARED LOCK ON ITEM X, THEN A REQUEST FROM
ANOTHER TRANSACTION B FOR AN EXCLUSIVE LOCK ON X WILL CAUSE B TO GO
INTO A WAIT STATE (AND B WILL WAIT UNTIL A’S LOCK IS RELEASED). A REQUEST
FROM TRANSACTION B FOR A SHARED LOCK ON X WILL BE GRANTED (THAT IS, B
WILL NOW ALSO HOLD A SHARED LOCK ON X).
GUARANTEEING SERIALISABILITY BY TWO-
PHASE LOCKING (2PL)
BASIC 2PL
• A TRANSACTION IS SAID TO FOLLOW THE TWO-PHASE LOCKING PROTOCOL
(BASIC 2PL PROTOCOL) IF ALL LOCKING OPERATIONS (READ_LOCK,
WRITE_LOCK) PRECEDE THE FIRST UNLOCK OPERATION IN THE TRANSACTION.
SUCH A TRANSACTION CAN BE DIVIDED INTO TWO PHASES: AN EXPANDING (OR
GROWING) PHASE, DURING WHICH NEW LOCKS ON ITEMS CAN BE ACQUIRED
BUT NONE CAN BE RELEASED; AND A SHRINKING PHASE, DURING WHICH
EXISTING LOCKS CAN BE RELEASED BUT NO NEW LOCKS CAN BE ACQUIRED.
 CONSERVATIVE 2PL

• A VARIATION OF THE BASIC 2PL IS CONSERVATIVE 2PL ALSO KNOWN AS STATIC

2PL, WHICH IS A WAY OF AVOIDING DEADLOCK. THE CONSERVATIVE 2PL
REQUIRES A TRANSACTION TO LOCK ALL THE DATA ITEMS IT NEEDS IN ADVANCE.
IF AT LEAST ONE OF THE REQUIRED DATA ITEMS CANNOT BE OBTAINED THEN
NONE OF THE ITEMS ARE LOCKED. RATHER, THE TRANSACTION WAITS AND THEN
TRIES AGAIN TO LOCK ALL THE ITEMS IT NEEDS. ALTHOUGH CONSERVATIVE 2PL
IS A DEADLOCK-FREE PROTOCOL, THIS SOLUTION FURTHER LIMITS
CONCURRENCY.
 STRICT 2PL

• IN PRACTICE, THE MOST POPULAR VARIATION OF 2PL IS STRICT 2PL, WHICH GUARANTEES A STRICT SCHEDULE.
(STRICT SCHEDULES ARE THOSE IN WHICH TRANSACTIONS CAN NEITHER READ NOR WRITE AN ITEM X UNTIL
THE LAST TRANSACTION THAT WROTE X HAS COMMITTED OR ABORTED). IN STRICT 2PL, A TRANSACTION T
DOES NOT RELEASE ANY OF ITS LOCKS UNTIL AFTER IT COMMITS OR ABORTS. HENCE, NO OTHER TRANSACTION
CAN READ OR WRITE AN ITEM THAT IS WRITTEN BY T UNLESS T HAS COMMITTED, LEADING TO A STRICT
SCHEDULE FOR RECOVERABILITY. NOTICE THE DIFFERENCE BETWEEN CONSERVATIVE AND STRICT 2PL; THE
FORMER MUST LOCK ALL ITEMS BEFORE IT STARTS, WHEREAS THE LATTER DOES NOT UNLOCK ANY OF ITS
ITEMS UNTIL AFTER IT TERMINATES (BY COMMITTING OR ABORTING). STRICT 2PL IS NOT DEADLOCK-FREE
UNLESS IT IS COMBINED WITH CONSERVATIVE 2PL.
• IN SUMMARY, ALL TYPE 2PL PROTOCOLS GUARANTEE SERIALISABILITY (CORRECTNESS) OF A SCHEDULE BUT
LIMIT CONCURRENCY. THE USE OF LOCKS CAN ALSO CAUSE TWO ADDITIONAL PROBLEMS: DEADLOCK AND
LIVELOCK. CONSERVATIVE 2PL IS DEADLOCK-FREE.