Chapter 3.1 Lock-in

ACompressed recap

x++ = load, add, store; a race loses updates (last store wins). Critical section with entry/exit; requirements: mutual exclusion, progress, bounded waiting. Lock variable ✗ME; strict alternation ✗progress; two flags ✗progress (deadlock); Peterson ✓✓✓ for 2 processes (flag first, then turn). TSL/CAS: atomic; TSL lock has no bounded waiting; CAS returns the old value; spinlocks suit short sections on multiprocessors; priority inversion.

BMerged rule card

3.1.1 Race conditions and the critical-section problem

• x++ = load, add, store; a pre-emption can fall between them.
• Race condition: the result depends on timing. Lost update: both load before either stores; the last store wins.
• Structure: entry section, CS, exit section, remainder section.
• Requirements: mutual exclusion, progress, bounded waiting; no assumptions about speed.
• x++ in two loops of n ≥ 2 each from 0: minimum 2, maximum 2n.

3.1.2 Software solutions: turn and flag attempts, Peterson's algorithm

• Lock variable: fails mutual exclusion.
• Strict alternation (turn): mutual exclusion ✓, progress ✗.
• Two flags: mutual exclusion ✓, progress ✗ (deadlock).
• Peterson: flag[i] = true; turn = j; wait while (flag[j] && turn == j). All three ✓, 2 processes, busy waiting.
• Swapping Peterson's first two lines breaks mutual exclusion.

3.1.3 Hardware help: test-and-set, compare-and-swap, spinlocks

• Atomic instruction: finishes before anything else touches that memory.
• TSL: return old, set true; lock = spin until old is false. ME ✓, progress ✓, bounded waiting ✗.
• CAS(&v, e, n): if v == e then v = n; returns the old value. Swap exchanges atomically.
• Spinlocks: good on multiprocessors for short sections; no context switch.
• Disabling interrupts: one CPU, kernel only. Priority inversion → priority inheritance.

CInterleaved GATE-style questions

Q1 · NAT · 1 mark(s) — Final values

D = 100. Thread 1 runs D = D + 20, thread 2 runs D = D − 50, each as load/compute/store. Largest possible final value of D?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Final values

x = 0. Two threads each run x++ twice. How many different final values of x are possible?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Requirements

"After a process requests entry, other processes can enter only a limited number of times before it does." This is:

1. (A) bounded waiting
2. (B) deadlock freedom
3. (C) mutual exclusion
4. (D) progress

Q4 · MCQ · 1 mark(s) — Two flags

The two-flag attempt (raise your flag, wait while the other's flag is up) satisfies mutual exclusion. Which requirement fails?

1. (A) Mutual exclusion
2. (B) Both
3. (C) Progress
4. (D) Neither

Q5 · MCQ · 2 mark(s) — Peterson

In Peterson's solution, both processes want to enter, and P1 was the last to write turn. Who enters first?

1. (A) P1
2. (B) P0
3. (C) Neither: deadlock
4. (D) Both

Q6 · MCQ · 1 mark(s) — TSL

Which requirement does the simple test-and-set spinlock NOT guarantee?

1. (A) Mutual exclusion
2. (B) It guarantees all three
3. (C) Bounded waiting
4. (D) Progress

Q7 · NAT · 1 mark(s) — CAS

lock = 0. Two threads call CAS(&lock, 0, 1) one after the other. What does the second call return?

Numerical answer: ________

Q8 · MSQ · 2 mark(s) — Spinlocks

Which are true about spinlocks?

1. (A) A waiting process uses CPU time
2. (B) They suit very short critical sections on multiprocessors
3. (C) They are ideal for long critical sections on a single CPU
4. (D) They avoid context-switch overhead