Gyanrush
Start freeOpen Gyanrush
Start freeOpen Gyanrush
  1. LPU MCA Semester 1
  2. CAP366
  3. Unit 5

CAP366 · Unit 5: Process synchronization

Concept of serializability

12 practice questions · in the MTE and ETE syllabus

Practise this topicPractise this topic

Key points

  • Conflict: different transactions, same item, at least one write
  • Precedence graph acyclic means conflict serializable
  • Cycle means not serializable
  • n transactions have n! serial schedules

A serial schedule runs transactions one after another. A concurrent schedule is conflict serializable if it can be turned into a serial schedule by swapping adjacent non-conflicting operations.

Two operations conflict if they belong to different transactions, access the same item, and at least one is a write.

Test: draw a precedence graph with an edge Ti to Tj when an operation of Ti conflicts with and precedes one of Tj; the schedule is conflict serializable if and only if the graph has no cycle.

ScheduleGraphResult
R1(A) W1(A) R2(A) W2(A)T1 to T2Serializable as T1, T2
R1(X) R2(X) W1(X) W2(X)T1 to T2 and T2 to T1Not serializable

For n transactions there are n! serial schedules (4! = 24).

Exam pitfall: a schedule need not be serial to be serializable, and who writes last does not decide it; check the whole graph for cycles.

Try two questions

Question 1 · Tier 1, Recall

A schedule whose effect is the same as that of some serial schedule is called:

  1. Recoverable
  2. Cascadeless
  3. Serializable
  4. Strict
Show the answer

C. A serializable schedule is equivalent to a serial one, so it preserves consistency.

Why not A: Recoverability concerns commit order after reads of uncommitted data.

Why not B: Cascadeless schedules avoid cascading aborts, not equivalence to a serial schedule.

Why not D: Strictness restricts reads and writes of uncommitted data.

Question 2 · Tier 2, Understand

Which pair of operations conflict (in the serializability sense)?

  1. Read(X) by T1 and Read(Y) by T2
  2. Write(X) by T1 and Write(Y) by T2
  3. Read(X) by T1 and Read(X) by T2
  4. Read(X) by T1 and Write(X) by T2
Show the answer

D. Operations conflict if they belong to different transactions, access the same item, and at least one is a write.