← CSC 214 Operating Systems
Concurrency, Synchronization, and Deadlocks
Notes
Concurrency and Race Conditions
Modern operating systems run multi-threaded processes across multi-core processors. Concurrency occurs when multiple instruction sequences execute over overlapping intervals of time. While concurrency boosts system throughput, it introduces significant data integrity risks when threads access shared variables without coordination. A race condition arises when the final outcome of an operation depends directly on the relative timing or interleaving of concurrent execution paths. The section of code that accesses shared resources is defined as the critical section.
Synchronization Mechanisms
To maintain deterministic application behavior, the operating system must enforce mutual exclusion: only one thread may enter the critical section at a given instant. Fundamental software and hardware synchronization primitives include atomic test-and-set instructions, mutex locks, and semaphores. A mutex operates as an exclusive binary lock that a thread acquires before entering a critical section and releases upon exit. Semaphores, conceptualized by Edsger Dijkstra, utilize an integer counter alongside wait and signal operations. Counting semaphores govern access to finite pools of homogeneous resources, while binary semaphores behave similarly to mutexes.
Deadlocks and System Stability
Synchronization introduces the danger of deadlock, a state where a set of processes are permanently blocked because each holds a resource while waiting for another resource held by a peer process. Four Coffman conditions must hold simultaneously for a deadlock to occur: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. Operating systems manage deadlocks via prevention, avoidance algorithms such as Dijkstra's Banker's Algorithm, detection via resource allocation graphs, or total recovery via process termination.
Practical example
Consider a core banking system deployed at Equity Bank in Nairobi, servicing simultaneous account transactions. Suppose Account 101 and Account 202 both hold a balance of 50,000 Kenyan Shillings.
Thread 1 (initiated via the Equity Mobile App) attempts to transfer 10,000 Shillings from Account 101 to Account 202. Thread 1 locks Account 101 successfully. At the precise same microsecond, Thread 2 (initiated via an automated standing order batch job) attempts to transfer 5,000 Shillings from Account 202 to Account 101. Thread 2 locks Account 202 successfully.
Next, Thread 1 requests a lock on Account 202, but is blocked because Thread 2 holds it. Simultaneously, Thread 2 requests a lock on Account 101, but is blocked because Thread 1 holds it. This circular wait fulfills all Coffman conditions, locking both threads indefinitely and freezing customer transactions. The operating system resolves this by implementing a global resource ordering policy, mandating that bank threads must always acquire account locks in ascending numerical order (locking Account 101 before Account 202), thereby breaking the circular wait condition.
Quiz
1. Which condition is NOT one of the four essential Coffman conditions required for a deadlock to occur?
2. What is the critical section in concurrent programming?
3. In the Equity Bank transaction example, how was the deadlock hazard definitively eliminated?
Sign in to submit and securely grade your quiz.