Synchronization and CPU Scheduling in Operating Systems

Chapter 5: Synchronization

Critical Section Conditions

• Mutual Exclusion: Only one process may be in the critical section at a time.
• Progress: If the critical section is empty, some waiting process can enter.
• Bounded Waiting: No starvation; each process waits a bounded number of turns.

Atomic Instructions

• Test-and-Set: old = *b; *b = TRUE; return old
• Swap: temp = *a; *a = *b; *b = temp

Spinlocks

• TAS:

  bool m = false;
  lock() { while (TestAndSet(&m)); }
  unlock() { m = false; }
  

• Swap:

  bool m = false;
  lock() { bool key = true; while (key) Swap(&m, &key); }
  unlock() { m = false; }
  

Semaphores

• wait(S): S.val--; if S.val < 0 block
• signal(S): S.val++; if S.val <= 0 wake one
• Binary semaphore as mutex: init = 1; lock = wait; unlock = signal

Peterson's Algorithm

flag[i] = true; turn = j;
while (flag[j] && turn == j);
... // critical section ...
flag[i] = false;

Priority Inversion

A high-priority process waits for a low-priority lock while a medium-priority process runs.

Fix: Priority inheritance protocol.

Monitors

Only one active thread is allowed inside a monitor.

Condition variable (CV) semantics:

• Hoare semantics: signal → immediate handoff.
• Mesa semantics: signal → waiter READY; signaller continues.

Bounded buffer (Mesa):

put(x) {
  while (count == N) notFull.wait();
  buf[in] = x; in = (in + 1) % N; count++;
  notEmpty.signal();
}
get() {
  while (count == 0) notEmpty.wait();
  x = buf[out]; out = (out + 1) % N; count--;
  notFull.signal();
  return x;
}

Race Example: x--; x++; if (x != 7) print(x) → Protect with mutex.

Chapter 6: CPU Scheduling

Metrics

Turnaround: T = Completion - Arrival

Waiting: W = T - Burst

Response: R = FirstRun - Arrival

Policies

FCFS: simple; convoy effect.

SJF: minimal average waiting time if bursts are known.

SRTF: preemptive SJF.

Priority: aging prevents starvation.

RR(q): fairness; small q → better response, more overhead.

Lottery: CPU share proportional to tickets.

RR Quantum

Throughput increases with larger quantum (q).

Lottery Shares

Short = 5, Long = 2

5 short + 5 long → total 35 → short each 14.3%, long each 5.7%

1 short + 10 long → total 25 → short 20%, long each 8%

Set A

P1(3), P2(7), P3(2), P4(4), P5(1)

FCFS finish: 3, 10, 12, 16, 17 → W: 0, 3, 10, 12, 16 (Avg W = 8.2)

SJF finish: 1, 3, 6, 10, 17 → W: 0, 1, 3, 6, 10 (Avg W = 4.0)

Priority finish: 3, 10, 12, 13, 17 → W: 0, 3, 10, 9, 13 (Avg W = 7.0)

Set B

P1(15), P2(5), P3(11), P4(9), P5(8)

FCFS finish: 15, 20, 31, 40, 48 → W: 0, 15, 20, 31, 40 (Avg W = 21.2)

SJF finish: 5, 13, 22, 33, 48 → W: 0, 5, 13, 22, 33 (Avg W = 14.6)

Priority finish: 9, 24, 35, 43, 48 → W: 0, 9, 24, 35, 40 (Avg W = 21.6)

CPU Burst Prediction

Formula: τ(n+1) = α * t(n) + (1 - α) * τ(n)

Equal weight α = 0.5: τ ≈ 5, 7.5, 8.75, ...

No history α = 1: τ = t(n)

Reminders

Mesa monitors: while (cond) wait();

SJF minimizes average waiting time if bursts are known.