Topic 07: Kernel Synchronization β€” Mutex & Semaphore Notes

Overview: How the kernel coordinates access to shared resources using a custom sleeping Mutex and a counting Semaphore in src/sync.rs, preventing race conditions without burning CPU in spinloops.


1. Mutex (Mutual Exclusion)

Mutex = Mutual Exclusion
Purpose: Protect shared data or a critical section so that only one task can access it at any time.

The mutex is implemented in src/sync.rs:54 (Mutex) and contains three key components:


2. How Mutex::lock() Works

When a task requests access to shared data via lock(), there are two possible cases:

Case 1: Mutex is Free

Initially, locked == false. The task atomically swaps false β†’ true:

Mutex is Free (locked = false)
        β”‚
        β–Ό
Atomic Swap: false β†’ true (Succeeds)
        β”‚
        β–Ό
Task acquires the mutex
        β”‚
        β–Ό
Returns MutexGuard
        β”‚
        β–Ό
Task accesses shared data safely

Only the task holding the returned MutexGuard is permitted to access the protected data.

Case 2: Mutex is Already Locked

Suppose Task A currently holds the mutex, and Task B calls lock():

Task B calls lock()
        β”‚
        β–Ό
Atomic Swap fails (already locked)
        β”‚
        β–Ό
Gets Task B's ID from Scheduler
        β”‚
        β–Ό
Adds Task B to wait_list queue
        β”‚
        β–Ό
Calls sleep() (marks Task B as Blocked and triggers software interrupt)
        β”‚
        β–Ό
CPU immediately switches to another ready task!

Instead of spinning in an empty loop and burning CPU cycles, Task B is cleanly put to sleep. This is why our implementation is a blocking/sleeping mutex, not a spinlock.


3. How the Mutex is Released (RAII & Drop)

Our mutex uses RAII (Resource Acquisition Is Initialization) through MutexGuard defined in src/sync.rs:89.

When the guard variable goes out of scope (for example, reaching the end of an enclosing block }), Rust automatically invokes its Drop implementation:

MutexGuard goes out of scope
             β”‚
             β–Ό
Rust automatically calls Drop::drop()
             β”‚
             β–Ό
1. Releases lock: stores false into locked
             β”‚
             β–Ό
2. Checks wait_list: pops the first waiting TaskId
             β”‚
             β–Ό
3. Calls wake(task_id) (moves task to ready_queue)
⚠️ Important Concurrency Note:
Calling wake(task_id) does not immediately switch the CPU to that task. It moves the task from the blocked queue back into the scheduler's ready queue. The scheduler will give it CPU time when its turn comes in the round-robin schedule.

4. Why Use a Guard?

Without a guard, code would have to call manual lock() and unlock() methods. If the code returned early, encountered an error, or panicked between the two calls, the lock would remain held forever, freezing the entire system in a deadlock.

By wrapping the lock inside a MutexGuard, Rust guarantees that the lock is released the exact moment the guard goes out of scopeβ€”no matter how the function exits. You can never forget to unlock the mutex.

🎯 Interview Soundbite β€” Why use RAII & a Guard?
β€œI use RAII through a MutexGuard. The guard represents active ownership of the mutex. When it goes out of scope, Rust automatically drops it, which resets the lock flag and wakes the next waiting task. This guarantees that locks are never leaked even if code branches or returns early.”

5. Complete Mutex Execution Flow

                     Calling lock()
                           β”‚
                 Is mutex available?
                   /               \
                YES                 NO
                 β”‚                   β”‚
           locked = true       Get current TaskId
                 β”‚                   β”‚
         Return MutexGuard     Add TaskId to wait_list
                 β”‚                   β”‚
          Critical Section     Call sleep()
                 β”‚                   β”‚
       Guard goes out of scope  Task Blocked (CPU switches)
                 β”‚
            Drop called
                 β”‚
           locked = false
                 β”‚
     Wake first task in wait_list (moves back to ready queue)

6. Counting Semaphore

While a mutex is binary (allowing only 1 task into the critical section at a time), a counting semaphore manages a pool of $N$ interchangeable resources.

The semaphore is implemented in src/sync.rs:118 (Semaphore) and contains:

For example, initializing a semaphore with a count of 3 means up to 3 tasks can hold a resource simultaneously.


7. How Semaphore::wait() Works

A task calls wait() to acquire a resource unit:

Initial Count = 3
  Task A calls wait() ──► Count = 2 (Proceeds)
  Task B calls wait() ──► Count = 1 (Proceeds)
  Task C calls wait() ──► Count = 0 (Proceeds)
  Task D calls wait() ──► Count = 0 (No resources left: Task D sleeps on wait_list)

8. How Semaphore::signal() Works

When a task finishes using a resource unit, it calls signal():

Task calls signal()
         β”‚
         β–Ό
1. Increments count by 1 (e.g., 0 β†’ 1)
         β”‚
         β–Ό
2. Pops the first waiting task from wait_list
         β”‚
         β–Ό
3. Calls wake(task_id) to make that task runnable again

9. Mutex vs. Counting Semaphore Comparison

Feature Mutex (Mutex<T>) Counting Semaphore (Semaphore)
Main Purpose Protect critical section / shared mutable data Manage a finite pool of identical resources
State Binary: Locked (true) or Free (false) Integer counter ($N \ge 0$)
Max Concurrent Tasks Strictly 1 Up to $N$
Core Operations lock() / automatic RAII drop() wait() / signal()
Waiting Mechanism Blocks task via sleep() on wait_list Blocks task via sleep() on wait_list
Implemented in sync.rs βœ… Yes (Line 54) βœ… Yes (Line 118)
Used in Final Tasks βœ… Yes (Counter and Clock tasks) ❌ No (Implemented in sync layer only)
Mutex:
   Shared Counter / Buffer
             β”‚
             β–Ό
        [ Mutex ]
             β”‚
  Only ONE task modifies at a time

Semaphore (Capacity = 3):
    3 Available Resource Slots
             β”‚
   Task A ────
   Task B ───┼──► [ Semaphore(3) ] ──► All 3 proceed concurrently
   Task C β”€β”€β”€β”˜
   Task D ───────────────────────────► Sleeps on wait_list until a slot frees up

10. Spinlock vs. Blocking Mutex

The synchronization module in src/sync.rs:7 also contains a low-level Spinlock<T>:


11. Key Interview Soundbites

🎯 Describing the Mutex:
β€œI implemented a blocking mutex using an atomic lock state and a wait queue. If the mutex is free, the task acquires it. If it is already held, the task is added to the wait queue and put to sleep. When the owner releases the mutex, the guard's Drop implementation releases the lock and wakes a waiting task.”
🎯 Describing the Semaphore & Resume Follow-up:
β€œI also implemented a counting semaphore using a counter and a wait queue. wait() decrements the counter when a resource is available; otherwise, the task sleeps. signal() increments the counter and wakes a waiting task. I implemented it as part of the synchronization layer, but I did not actually use it in the final task workloadβ€”the shared-data synchronization was done using the mutex.”
🎯 One-Line Distilled Difference:
β€œA mutex provides exclusive access to a critical section for one task at a time, whereas a counting semaphore controls access to multiple units of a limited resource across several tasks.”