IAE Academy

GATE 2020 CS Q.37: solution and answer

GATE 2020 · CSQ.37 · 2 marks · MCQ

Consider a schedule of transactions and (columns are time slots, left to right):

Here, stands for "Read(X)" and stands for "Write(X)". Which one of the following schedules is conflict equivalent to the above schedule?

GATE 2020 CS question 37: The given schedule has two rows, T1 and T2, with time running left to right.Tap to open full size
Figure from the GATE 2020 CS paper. It is part of the question.
Figure description

The given schedule has two rows, T1 and T2, with time running left to right. T1: RA, then RC, then WD, then WB, then Commit. T2: RB, WB, RD, WC, then Commit at the far right. Interleaved order: RA(T1), RB(T2), WB(T2), RC(T1), RD(T2), WD(T1), WC(T2), WB(T1), Commit(T1), Commit(T2). Each option is a similar two-row table of slots.

  1. (A)

    Figure — T2 runs RB, WB, RD first (T1 empty). Then T1 runs RA, RC, WD, WB while T2 is idle. Then T2 runs WC, then T1 Commit, then T2 Commit.

  2. (B)

    Figure — T1 runs RA, RC, WD, WB first (T2 idle). Then T2 runs RB, WB, RD, WC. Then T1 Commit, then T2 Commit.

  3. (C)

    Figure — T1 runs RA, RC, WD, then T2 runs RB, WB, RD, then T1 runs WB, then T2 runs WC, then T1 Commit, then T2 Commit.

  4. (D)

    Figure — T2 runs RB, WB, RD, WC first (T1 idle). Then T1 runs RA, RC, WD, WB, Commit, then T2 Commit.

Answer and solution

ANSWER

Option (A) is the schedule that is conflict equivalent to the given one.

Official answer: ASource: Official answer key, GATE 2020 CS (IIT Delhi)

  1. Write the given schedule in time order: .

  2. Two operations conflict if they belong to different transactions, touch the same item, and at least one of them is a write. alone uses A, so A gives no conflict. Items B, C and D are touched by both transactions.

  3. Item B: and come before . Required: both operations on B precede .

  4. Item C: comes before . Required: .

  5. Item D: comes before . Required: .

  6. A schedule is conflict equivalent to the given one exactly when it keeps each transaction's own order and all three of these orders.

  7. Option (A): come first, then , then . So , and all hold. Conflict equivalent.

  8. Option (B): runs completely first, so . This reverses the order on B. Not equivalent.

  9. Option (C): comes before . This reverses the order on D. Not equivalent.

  10. Option (D): comes before . This reverses the order on C. Not equivalent. Hence only (A) is conflict equivalent.

KEY IDEA

List every pair of conflicting operations (different transactions, same item, at least one write) in the given schedule. A candidate is conflict equivalent only if it keeps the relative order of every such pair.

WATCH OUT FOR

Comparing only the order of the transactions as a whole and ignoring item-by-item conflicts. Each wrong option reverses exactly one conflicting pair: B reverses the B pair, C the D pair, D the C pair.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 9 Transactions questions, with notes

More Transactions questions