6.3.1 · Schedules: serial vs concurrent; counting possible schedules

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

Write the pattern of a lost update. from Lesson 6.2.1
What is C(n, k)? from Lesson 0.2.4
How many interleavings keep the order of two sequences of lengths m and n? from Lesson 0.2.4

1 · The Hook

To reason about interleavings, write them down exactly: a schedule lists, in time order, every read, write, commit and abort of a set of transactions. GATE also asks pure counting questions: "how many schedules are possible?", "how many are not serial?"

2 · Predict First

T1 has 2 operations and T2 has 3. How many schedules (interleavings keeping each transaction's own order) are there? How many are serial?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

C(5, 2) = 10 schedules; 2 are serial (T1 then T2, or T2 then T1). So 8 are non-serial.

Schedule

A schedule S of transactions T1, …, Tn is a sequence of their operations such that the operations of each Ti appear in the same order as in Ti. Notation: R1(A) = T1 reads A; W2(B) = T2 writes B; C1 = T1 commits; A2 = T2 aborts.

A complete schedule contains a commit or abort for every transaction.

Serial and non-serial

Serial schedule: the transactions run one after another, no interleaving. For n transactions there are n! serial schedules. Each is correct (if each transaction is consistent alone), but there is no concurrency.
Non-serial (concurrent) schedule: operations interleave.

Goal: allow non-serial schedules that are equivalent to some serial one (Chapter 6.4).

Counting schedules

Two transactions with n₁ and n₂ operations: C(n₁ + n₂, n₁) = (n₁ + n₂)! / (n₁! n₂!).
Three or more: (n₁ + n₂ + … + n_k)! / (n₁! n₂! … n_k!).
Non-serial = total − k!.

Examples:

n₁ = 2, n₂ = 2: 4!/(2!2!) = 6 schedules; 2 serial; 4 non-serial.
n₁ = 3, n₂ = 2, n₃ = 1: 6!/(3!2!1!) = 60 schedules; 3! = 6 serial.

Why order inside a transaction is fixed

The transaction's own logic (read balance, then write it) cannot be reordered by the scheduler. Only the interleaving between transactions is chosen.

4 · Visual

T1: R1(A) W1(A)          T2: R2(A) W2(A) R2(B)

serial T1;T2 :  R1(A) W1(A) R2(A) W2(A) R2(B)
serial T2;T1 :  R2(A) W2(A) R2(B) R1(A) W1(A)
one non-serial: R1(A) R2(A) W1(A) W2(A) R2(B)        (lost update!)
total = C(5,2) = 10 schedules

5 · Worked Examples

Example 1 Easy

T1 has 3 operations, T2 has 3. Number of schedules? Non-serial ones?

Solution

6!/(3!3!) = 20; non-serial 18.

Example 2 Medium

Three transactions with 1, 2 and 2 operations. Number of schedules?

Solution

5!/(1!2!2!) = 120/4 = 30.

Example 3 GATE

T1 = R1(A) W1(A) and T2 = R2(A) W2(A). List all schedules in which T2's first operation comes before T1's last operation.

Solution

Total 6 schedules; serial T1;T2 has R2(A) after W1(A): excluded. The other 5: R1 R2 W1 W2, R1 R2 W2 W1, R2 R1 W1 W2, R2 R1 W2 W1, R2 W2 R1 W1. (R2 W2 R1 W1 is serial T2;T1, which also satisfies the condition.)

6 · GATE Traps

Count with factorials divided by each transaction's length factorial, not (Σn)!.
n! serial schedules for n transactions, regardless of their lengths.
A transaction's own operations cannot be reordered.
Commits and aborts count as operations if the question includes them.

7 · Memory Hook

"Shuffle the decks, keep each deck in order." Schedules = (total cards)! / (each deck's size)!

8 · Connect the Dots

Lessons 6.2.1–6.3.1 described what can go wrong and how to write schedules. Next: the Chapters 6.1–6.3 Lock-in, then a short directed-graph primer, needed to test whether a schedule is as good as a serial one.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Counting

T1 has 2 operations and T2 has 4. How many schedules?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Non-serial

T1, T2, T3 have 2, 2 and 1 operations. How many non-serial schedules?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — Serial

How many serial schedules are there for 4 transactions?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Definition

In a schedule, which order must be preserved?

(A) The order of operations across all transactions
(B) Reads before writes
(C) Commits before all reads
(D) The order of each transaction's own operations

Q5 · NAT · 2 mark(s) — Counting

T1 = R1(A) W1(A) R1(B) and T2 = R2(B) W2(B). How many schedules have T1's operations all before T2's or all after?

Numerical answer: ________

10 · Rule Card

Schedule: interleaving that keeps each transaction's order; complete = all end in C/A.
Serial schedules: n! for n transactions.
Total schedules: (Σnᵢ)! / Πnᵢ!; non-serial = total − n!.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

schedulecomplete scheduleserial schedulenon-serial (concurrent) schedulecounting schedules (multinomial)

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

R1(X) R2(X) W1(X) W2(X).
The number of ways to choose k of n items: n!/(k!(n − k)!).
C(m + n, m).