Scheduling, paging, deadlock & concurrency

Under demand paging only the pages actually referenced are loaded. When a referenced page is not resident a page fault occurs and, if every frame is full, the policy must evict a victim. FIFO evicts the page that has been resident longest. LRU (least-recently-used) evicts the page whose last use is furthest in the past — it exploits temporal locality. Optimal (Belady's MIN) evicts the page whose next use is furthest in the future; it is unrealisable online but gives the theoretical lower bound on faults.

More frames usually means fewer faults, but FIFO can exhibit Belady's anomaly — adding a frame occasionally increases faults. LRU and Optimal are stack algorithms and never suffer the anomaly. The optimal count is always a lower bound; comparing FIFO and LRU against it measures how good a practical policy is.

The dominant cost of a disk access is the seek time — the time to move the read/write head to the target cylinder — which is roughly proportional to the number of cylinders crossed. A disk scheduler reorders the pending request queue to shrink total head movement. FCFS services requests in arrival order (fair, but the head may swing wildly). SSTF (shortest-seek-time-first) always serves the nearest pending request; it is greedy and can starve far requests. SCAN (the elevator) sweeps in one direction to the disk edge, then reverses. C-SCAN sweeps one way, then jumps back to the start and sweeps again, giving more uniform wait. LOOK / C-LOOK behave like SCAN / C-SCAN but turn around at the last request instead of the physical edge.

SSTF and the elevator family dramatically cut average seek distance versus FCFS under load. C-SCAN sacrifices a little total movement for a more uniform response time, since every cylinder is visited on a regular cycle.

The Banker's algorithm avoids deadlock by never entering an unsafe state. Each process declares its Max demand of every resource type up front. The system tracks the Allocation already given and the Available (free) units. The remaining demand is the Need:

A state is safe if there exists an ordering of all processes such that each can obtain its full Need from the currently free units plus whatever earlier processes release on finishing. The safety check maintains a Work vector (initially Available) and a Finish flag per process; it repeatedly finds an unfinished process whose Need is ≤ Work, simulates it running and releasing, adding its Allocation back to Work:

To check a request by process i, the algorithm tentatively grants it (only if Request ≤ Need and Request ≤ Available), then re-runs the safety check; the request is granted only if the resulting state is still safe.

In contiguous allocation the main memory is a row of holes (free partitions) of various sizes. When a process of size s arrives, the allocator must choose a hole large enough to hold it. First-fit scans from the start and takes the first hole that fits — fast and simple. Best-fit takes the smallest hole that fits, aiming to waste the least space, but it tends to litter memory with tiny unusable slivers. Worst-fit takes the largest hole, hoping the leftover stays big enough to be useful.

After placement the chosen hole shrinks by s; the unused tail remains free. Memory ends up checkerboarded with free fragments — this is external fragmentation: enough total free space exists, but no single hole is large enough for the next request.

Best-fit and first-fit usually outperform worst-fit on utilisation; first-fit is often the fastest in practice. None eliminate external fragmentation — only compaction or paging does.

The bounded-buffer problem has a producer adding items to a buffer of N slots and a consumer removing them. Three semaphores keep them safe. The counting semaphore empty (initially N) counts free slots; full (initially 0) counts occupied slots; the binary semaphore mutex (initially 1) gives exclusive access to the buffer. A wait (P) decrements a semaphore and blocks if it would go negative; a signal (V) increments it and may wake a waiter.

Acquiring the counting semaphore before the mutex is essential: if a thread held the mutex while blocked on a full or empty buffer it would deadlock the other party out of the critical section. With this ordering the buffer never overflows (the producer blocks on empty = 0) nor underflows (the consumer blocks on full = 0), and mutual exclusion guarantees no torn updates.