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.
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:
AtomicBool locked: Tracks whether the mutex is currently locked. Uses atomic compare-and-swap so multiple CPU cores or tasks never read stale state.wait_list: A queue (VecDeque<TaskId>) storing the IDs of tasks currently waiting for the mutex. Protected by an internal spinlock to avoid re-entrancy issues.UnsafeCell<T> data: Stores the protected value and provides controlled mutable access in Rust.Mutex::lock() WorksWhen a task requests access to shared data via lock(), there are two possible cases:
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.
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.
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)
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.
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.
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)
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:
count: An integer representing how many resource units are currently available.wait_list: A FIFO queue storing tasks waiting for a resource unit.For example, initializing a semaphore with a count of 3 means up to 3 tasks can hold a resource simultaneously.
Semaphore::wait() WorksA task calls wait() to acquire a resource unit:
wait_list, calls sleep(), and blocks until another task releases a 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)
Semaphore::signal() WorksWhen 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
| 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
The synchronization module in src/sync.rs:7 also contains a low-level Spinlock<T>:
Blocked, and yields the CPU immediately so other tasks can run.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.β