Operating Systems · topic
Inter-process communication by shared memory, message passing and pipes; race conditions and the three critical-section requirements; Peterson, bakery and hardware instructions; semaphores, mutexes and monitors; producer-consumer, readers-writers and dining philosophers.
Why processes need IPC; shared memory versus message passing and their costs; direct and indirect (mailbox) naming; blocking and non-blocking send and receive; zero, bounded and unbounded buffering; anonymous pipes and their end-of-file and broken-pipe rules, named pipes (FIFOs), message queues, signals and sockets; a computed pipe-capacity example; and a single-slot producer-consumer handoff that shows why shared memory still needs synchronization.
A partial preview of the top of the sheet. The full sheet is in the Operating Systems cheat sheet pack.
Race conditions shown with the lost-update interleaving and the range of final values when two processes increment a shared counter; the three requirements for a critical-section solution; the classic two-process attempts and which requirement each breaks; Peterson's algorithm and its assumptions; the bakery algorithm for n processes; disabling interrupts; test-and-set, swap and compare-and-swap locks, the bounded-waiting version, spinlocks and memory ordering. All claims about the protocols were checked by exhaustive state search.
A partial preview of the top of the sheet. The full sheet is in the Operating Systems cheat sheet pack.
Semaphore wait and signal in the non-negative model and in the blocking model where the value can go negative; counting versus binary semaphores; value arithmetic after many operations; forcing an order of events with semaphores initialised to 0, with exhaustively enumerated outputs; mutex versus binary semaphore; monitors and condition variables with Hoare and Mesa signalling; and the solved GATE CS 2024 Set 2 Q.46 on a deadlock caused by waiting while holding a semaphore.
A partial preview of the top of the sheet. The full sheet is in the Operating Systems cheat sheet pack.
The bounded-buffer producer-consumer solution with its three semaphores and what happens when the producer or the consumer takes the mutex first; the first readers-writers solution with the read count, why readers share and writers are exclusive, and why writers can starve; the dining philosophers, the deadlock when all pick up the left chopstick, and four ways to prevent it. Deadlock and exclusion claims were checked by a full state-space search.
A partial preview of the top of the sheet. The full sheet is in the Operating Systems cheat sheet pack.
