Exercise 2: Mutual Exclusion Holds for Three Competing Processes — Possible Solution ==================================================================== THE TEST ------------------------------ procs = [kernel.create_process(num_pages=0) for _ in range(3)] # all three map the SAME physical frame as the lock results = [mutex.try_acquire() for _ in range(3)] RESULT ------------------------------ three processes all call try_acquire() in a row: [True, False, False] Exactly one of the three calls succeeds -- the first. The second and third both fail, even though neither of them is "the same" competitor that already lost to someone else -- each is failing against the current, real state of the lock at the moment it's checked. WHY NOTHING IN try_acquire() NEEDED TO CHANGE ------------------------------ try_acquire()'s entire implementation is: def try_acquire(self): old = atomic_test_and_set(self.mem, self.lock_paddr) return old == 0 This never references how many processes exist, never keeps a list of "who's competing," and never counts callers. It only ever asks one question, atomically: "what was the lock's value right before I set it to 1?" That question has exactly the same well-defined answer no matter how many other processes are also asking it -- either the lock was 0 (this caller wins) or it was already 1 (this caller loses), regardless of whether there's one other competitor or a hundred. Mutual exclusion for N processes isn't a separate feature bolted onto mutual exclusion for 2 -- it's the SAME guarantee, because the mechanism was never built around any specific number of competitors in the first place. WHY THIS IS WORTH VERIFYING DIRECTLY, NOT JUST ASSUMING ------------------------------ It would be easy to imagine a buggy implementation that "accidentally" only works for exactly two competitors -- for example, a lock that toggles between two specific process IDs instead of checking a genuine binary free/held state. Testing with three (not just two) processes rules that specific failure mode out concretely, rather than trusting that "it worked for two, so it probably works for any number" without actually checking. WHY THIS WORKS AS AN ANSWER ------------------------------ Running three try_acquire() calls back to back and checking the exact sequence of results (not just "did more than one succeed") confirms the FIRST caller wins and every subsequent one loses, in order -- matching exactly what a correct atomic test-and-set predicts, regardless of how many total competitors are involved.