Operating Systems › Level 6
PART 2 • RESOURCE CONTROL

Coordinate Shared Work without Losing Correctness

Learn why correct individual instructions can produce an incorrect shared result, then use atomic operations, mutexes, semaphores and monitors to control every permitted interleaving.

Level 06 of 15 Intermediate 100–130 minutes Two interactive labs
BY THE END, YOU CAN

Protect shared invariants

  • Identify shared data and its critical section.
  • Test mutual exclusion, progress and bounded waiting.
  • Trace wait and signal operations exactly.
  • Choose mutex, semaphore, monitor or atomic operation.
  • Solve the three classical synchronization problems.
01 • FIND THE SHARED INVARIANT

A Race Condition Is a Correctness Problem, Not Merely “Fast Execution”

Two execution paths may each be locally valid while their combined read–modify–write operations create a result that depends on timing.

read(counter) 1

Copy the shared value into a private register.

add 1 2

Change the private copy.

write(counter) 3

Store the private value back into shared memory.

SHARED INVARIANT After two completed increments, counter = original + 2

An unsafe interleaving lets both paths read the original value before either writes. Two writes then store the same incremented value, so one logical update disappears.

02 • DEFINE A CORRECT SOLUTION

The Critical-Section Problem Has Three Requirements

01

Mutual exclusion

At most one process executes its critical section for the protected resource at a time.

Prevents simultaneous conflicting access
02

Progress

If nobody is inside and some processes want to enter, the choice cannot be postponed indefinitely by unrelated processes.

Prevents needless standstill
03

Bounded waiting

After requesting entry, a process has a finite bound on how often others may enter first.

Prevents starvation
ENTRY SECTION → CRITICAL SECTION → EXIT SECTION → REMAINDER SECTION
03 • CHOOSE THE RIGHT ABSTRACTION

From Hardware Atomicity to Structured Coordination

ATOMIC OPERATION

One indivisible state change

Use for small counters, flags or compare-and-swap loops when the invariant is compact.

Low overhead; reasoning can become subtle
MUTEX

One owner at a time

Lock before a critical section and unlock afterward. Ownership makes it suitable for protecting a shared object.

Only the owner should unlock
COUNTING SEMAPHORE

Represent available permits

An integer count coordinates a pool of identical resources or records available buffer slots.

wait consumes; signal returns
BINARY SEMAPHORE

Signal or exclude

A 0/1 semaphore can provide exclusion or event ordering, but generally has no ownership rule.

More general than a mutex
MONITOR

Encapsulate state and operations

Only one active execution enters the monitor at a time; condition variables express when operations may proceed.

Higher-level, structured safety
CONDITION VARIABLE

Wait for a predicate

Wait releases the associated lock and sleeps; after waking, the predicate must be checked again.

Always wait in a loop
Need Good starting tool Reason
Protect one shared data structure Mutex Clear ownership and one critical region
Limit access to N identical resources Counting semaphore The count represents available permits
Increment a simple independent counter Atomic operation Avoids a larger lock when the operation is truly atomic
Wait until a queue becomes non-empty Condition variable + mutex The condition is a predicate over protected state
Package shared state with safe operations Monitor Encapsulation reduces protocol mistakes
04 • INTERACTIVE SEMAPHORE LAB

Trace Every Permit and Blocked Process

Choose a semaphore type and request operations. The lab applies atomic wait and signal rules and exposes the queue state after every step.

SEMAPHORE S 1 1 permit available
ACTIVE / GRANTED
None
BLOCKED QUEUE
Empty

Operation trace

  1. Semaphore initialized.

Choose a process and execute wait(S).

05 • RECOGNISE THE CLASSICAL PATTERNS

Three Problems Teach Three Different Coordination Pressures

PRIMARY RISK

06 • INTERACTIVE BOUNDED-BUFFER LAB

Make empty, full and mutex Work Together

The buffer has four slots. Produce and consume items while watching the three semaphore values and the required ordering.

empty 4 free slots
full 0 stored items
mutex 1 buffer lock
LAST ATOMIC SEQUENCE Ready: empty = 4, full = 0, mutex = 1

Produce an item or try consuming from the empty buffer.

07 • WRITE ROBUST SYNCHRONIZATION

Small Protocol Rules Prevent Large Failures

Keep critical sections small

Protect the invariant, not unrelated computation or slow I/O.

Use one lock order

When multiple locks are necessary, acquire them in a documented global order.

Release on every path

Structured cleanup must unlock after success, failure, cancellation or exception.

Check predicates in loops

A wake-up means “check again,” not “the condition is guaranteed true.”

Avoid busy waiting when long

Block when the expected wait is longer than the cost of sleeping and waking.

Prefer higher-level primitives

Use tested libraries and message-passing designs instead of inventing lock protocols.

Peterson's solution: why it matters and why it is not the everyday answer

Peterson’s two-process algorithm uses intent flags and a turn variable to demonstrate mutual exclusion, progress and bounded waiting under its theoretical memory assumptions. It is important for learning correctness arguments. Modern compilers and processors reorder memory operations, so production code uses language/library synchronization primitives with defined memory-order guarantees.

08 • CHECK YOUR UNDERSTANDING

Ten Misconception-Specific Checks

Feedback explains the exact protocol or reasoning error.

Answered correctly: 0 of 10
09 • EXPLAIN & PREPARE

University and Placement Questions

2-MARK QUESTIONS
  1. Define a race condition.
  2. What is mutual exclusion?
  3. Define semaphore.
  4. Mutex versus binary semaphore?
  5. What is bounded waiting?
5-MARK QUESTIONS
  1. State critical-section requirements.
  2. Explain wait and signal.
  3. Solve bounded producer–consumer.
  4. Compare monitors and semaphores.
  5. Explain readers–writers variants.
INTERVIEW QUESTIONS
  1. Why must condition waits use a loop?
  2. Can a semaphore value represent resources?
  3. Spinlock versus mutex?
  4. How can lock ordering prevent deadlock?
  5. What makes code thread-safe?
Show a strong answer: “Mutex versus semaphore”
  1. Define both as synchronization primitives.
  2. State mutex ownership: the locking owner releases it.
  3. State semaphore permits: wait consumes and signal returns or transfers a permit.
  4. Explain binary versus counting semaphores.
  5. Choose mutex for protecting one object; counting semaphore for resource counts or coordination.
LEVEL 6 SUMMARY

You Can Now Design and Inspect a Synchronization Protocol

  • Race conditions appear when a shared result depends on uncontrolled interleaving.
  • Correct critical-section solutions require mutual exclusion, progress and bounded waiting.
  • Mutexes express ownership; semaphores express permits or events; monitors encapsulate state.
  • Producer–consumer coordinates buffer capacity and exclusion using empty, full and mutex.
  • Safe protocols use short critical sections, consistent ordering and predicate loops.
COURSE CHECKPOINT

Mark Level 6 after you can trace wait/signal and explain why producer–consumer needs all three semaphores.

Saved only in this browser.