Principles of concurrency, race condition, critical region · Mutual…
Open in the Padhaiko app3.1 Principles of concurrency, race condition, critical region
Concurrency and Concurrent Processes
Concurrency is the property of a system in which multiple computations execute during overlapping time periods. Processes that coexist in main memory at the same time are called concurrent processes.
- Single-Processor Multiprogramming (Interleaving): A single CPU switches rapidly between active processes in time so their instruction streams are interleaved, creating the illusion of simultaneous execution.
- Multiprocessor Execution (Overlapping / Parallelism): Multiple CPUs execute instructions of different processes at the exact same physical instant, both interleaving and overlapping their execution.
Concurrent processes fall into two categories based on how they interact:
| Aspect | Independent Processes | Cooperating Processes |
|---|---|---|
| State & Data Sharing | Do not share data, memory, or messages with any other process | Share variables, memory buffers, files, or exchange messages |
| Interaction Mode | Compete only for system resources (CPU time, memory, I/O devices) | Both compete for resources and collaborate to accomplish a common task |
| Determinism | Execution is deterministic and reproducible (output depends only on initial input) | Execution is potentially non-deterministic and subject to race conditions unless synchronized |
Fundamental Problems of Concurrent Processing
When concurrent processes execute without coordination, two major system hazards arise:
- Sharing of Global Resources: When two or more processes read and write the same shared global variable or file, the final outcome depends critically on the exact relative order in which their read and write operations interleave.
- Optimal Resource Allocation: If process requests and receives exclusive control of an I/O channel and is then suspended before using it, locking that resource prevents other runnable processes from progressing and can trigger a deadlock.
Character Echo Procedure Anomaly
Consider a shared operating system input-echo procedure invoked by multiple processes (OS Ch3):
char chin, chout; /* Shared global variables */
void echo(void) {
chin = getchar();
chout = chin;
putchar(chout);
}- Unprotected Interleaving (Single Processor):
- Process invokes
echo(), reads character'x'from the keyboard viagetchar(), and stores'x'in global variablechin. - Immediately afterward, a clock interrupt preempts .
- Process is scheduled, calls
echo(), reads'y', stores'y'into the sharedchin(overwriting'x'), copies'y'tochout, and prints'y'. - When resumes at
chout = chin;, its original character'x'has been lost; copies'y'and prints'y'a second time.
- Process invokes
- Unprotected Parallel Execution (Multiprocessor): When and execute on separate processors simultaneously, executes
chin = getchar()('x'), immediately executeschin = getchar()('y'), and both executechout = chinandputchar(chout), displaying'y'twice and losing'x'. - Resolution: Enforce mutual exclusion on
echo()so only one process may be inside the procedure at a time. If invokesecho()while is inside (even if is temporarily suspended), is blocked until exitsecho().
Race Condition
Race Condition
A race condition occurs when two or more concurrent processes read and write shared data and the final result depends on the exact timing or scheduling order in which the processes execute.
Classic Example: The Printer Spooler Directory
When a process wants to print a file, it writes the file name into a shared spooler directory array with numbered slots . A background printer daemon periodically checks the directory, prints queued files, and removes their entries.
Two shared integer variables coordinate the spooler:
out: index of the next file to be printed by the daemon (currentlyout = 4).in: index of the next free slot in the directory (currentlyin = 7, with slots occupied).
Suppose Process and Process both decide to queue a file for printing at nearly the same instant:
| Time Sequence | Process Action | Process Action | A.next_free_slot | B.next_free_slot | Shared in | Slot 7 Content |
|---|---|---|---|---|---|---|
Reads shared in () into local next_free_slot | — | — | Empty | |||
| Clock interrupt! CPU switches from to | Scheduled to run | — | Empty | |||
| Suspended | Reads shared in () into local next_free_slot | Empty | ||||
| Suspended | Writes "fileB.txt" into slot ; sets in = 7 + 1 = 8 | "fileB.txt" | ||||
Resumes; writes "fileA.txt" into slot A.next_free_slot () | Executing other tasks | "fileA.txt" (overwrites B!) | ||||
Computes 7 + 1 and sets in = 8 | Executing other tasks | "fileA.txt" |
Although the spooler directory remains internally consistent (in = 8), Process has silently overwritten Process 's entry in slot , so Process 's file is permanently lost.
Critical Region (Critical Section)
Critical Region and the Four Synchronization Conditions
The critical region (or critical section) is the segment of code in a process where shared memory, shared files, or other shared resources are accessed and modified.
To prevent race conditions and ensure correct, deadlock-free cooperation among concurrent processes, any valid critical-section solution must satisfy four conditions:
- Mutual Exclusion: No two processes may be simultaneously inside their critical regions.
- No Speed or CPU Assumptions: No assumptions may be made about the relative execution speeds of processes or the number of CPUs in the system.
- Progress: No process running outside its critical region (in its non-critical/remainder region) may block another process from entering its critical region.
- Bounded Waiting (No Starvation): No process waiting to enter its critical region should have to wait forever; there must be a finite bound on the number of times other processes are allowed to enter their critical regions before the waiting request is granted.
while (TRUE) {
/* Entry Section: request permission to enter critical region */
critical_region(); /* Access shared data safely */
/* Exit Section: release permission so waiting processes may enter */
noncritical_region(); /* Remainder section: independent work */
}3.2 Mutual exclusion, semaphores, and mutex
Mutual Exclusion
Mutual exclusion is the concurrency control principle that prevents simultaneous access to a shared resource: while one process is executing in its critical region updating shared data, all other processes are excluded from entering their critical regions for that same resource.
Mutual Exclusion with Busy Waiting (Spinlocks)
Busy waiting refers to a technique in which a process repeatedly tests a condition in a tight CPU loop while waiting to enter its critical region. A lock that uses busy waiting is called a spinlock. Five classic hardware and software approaches are studied in operating systems:
1. Disabling Interrupts
On a single-processor system, a process can disable all hardware interrupts immediately upon entering its critical region and re-enable them just before leaving. Because the CPU is switched between processes only on clock or I/O interrupts, disabling interrupts guarantees that no context switch can preempt the current process.
- Why it fails as a general user-level mechanism:
- Unwise to trust user processes: If a buggy or malicious user process disables interrupts and never turns them back on (e.g., enters an infinite loop), the entire operating system freezes permanently.
- Fails on multiprocessors: Disabling interrupts affects only the CPU executing the disable instruction; processes running on other CPU cores continue executing and can freely access the shared memory.
- Valid use case: Inside the OS kernel itself for a few instructions while updating internal kernel queues or tables.
2. Lock Variables
A software approach using a single shared integer variable lock, initialized to 0:
lock == 0means no process is in the critical region.lock == 1means a process is currently inside the critical region.
while (lock != 0) ; /* Busy wait until lock is 0 */
lock = 1; /* Acquire lock */
critical_region();
lock = 0; /* Release lock */
- Flaw (violates Condition 1 — Mutual Exclusion): Testing
lock == 0and settinglock = 1are two separate, non-atomic operations. If Process readslockas0and is preempted before executinglock = 1, Process can run, seelock == 0, setlock = 1, and enter its critical region. When resumes, it also setslock = 1and enters, placing both processes inside their critical regions simultaneously.
3. Strict Alternation (Dekker's Naive Turn Variable)
Two processes and share an integer variable turn (initialized to 0) that tracks whose turn it is to enter the critical region:
/* Process 0 */ /* Process 1 */
while (TRUE) { while (TRUE) {
while (turn != 0) ; /* spin */ while (turn != 1) ; /* spin */
critical_region(); critical_region();
turn = 1; turn = 0;
noncritical_region(); noncritical_region();
} }- Flaw (violates Condition 3 — Progress): Suppose leaves its critical region (
turn = 1), and quickly executes its critical region, setsturn = 0, and enters a very slownoncritical_region(). Next, finishes its critical region, setsturn = 1, and quickly finishes itsnoncritical_region(). When loops back and wants to enter its critical region again, it is blocked (turn == 1) even though is outside its critical region! Taking turns fails whenever one process is much slower than the other.
4. Peterson's Solution (1981)
Gary Peterson combined the idea of taking turns (turn) with per-process intent flags (interested[2]) to achieve a pure software mutual-exclusion algorithm for two processes ( and ) that satisfies all four critical-section conditions:
#define FALSE 0
#define TRUE 1
#define N 2 /* Number of processes */
int turn; /* Whose turn is it? */
int interested[N]; /* All values initially 0 (FALSE) */
void enter_region(int process) /* process is 0 or 1 */
{
int other; /* Number of the other process */
other = 1 - process; /* The opposite of process (0 -> 1, 1 -> 0) */
interested[process] = TRUE; /* Declare interest in entering CR */
turn = process; /* Set turn flag */
while (turn == process && interested[other] == TRUE) ; /* Busy wait */
}
void leave_region(int process) /* process: who is leaving */
{
interested[process] = FALSE; /* Indicate departure from critical region */
}- Single process entry: If only calls
enter_region(0), it setsinterested[0] = TRUEandturn = 0. Sinceinterested[1] == FALSE, thewhilecondition is false and enters immediately. - Simultaneous entry (tie-breaking): If both and call
enter_regionconcurrently, both setinterested[0] = TRUEandinterested[1] = TRUE. Both write toturn, but only the last write survives:- Suppose 's assignment
turn = 1executes second (overwritingturn = 0). - When both reach the
whileloop, checksturn == 0 && interested[1] == TRUE(which is false sinceturn == 1), so enters the critical region immediately! - Meanwhile, checks
turn == 1 && interested[0] == TRUE(which is true), so spins until callsleave_region(0)and setsinterested[0] = FALSE.
- Suppose 's assignment
5. Hardware TSL (Test and Set Lock) Instruction
Many CPU architectures provide an atomic hardware instruction TSL RX, LOCK (Test and Set Lock):
- It reads the contents of the memory word
lockinto CPU registerRX. - It stores a nonzero value (
1) into the memory locationlock.
The CPU locks the memory bus for the entire duration of TSL, making the read and write indivisible (atomic) across all processors in a multiprocessor system.
enter_region:
TSL REGISTER, LOCK | Copy lock to register and atomically set lock = 1
CMP REGISTER, #0 | Was the old value of lock zero?
JNE enter_region | If nonzero, lock was already set, so loop (spin)
RET | Return to caller; critical region entered
leave_region:
MOVE LOCK, #0 | Store a 0 in lock to release critical region
RET | Return to caller| Technique | Mechanism | Multiprocessor Safe? | Satisfies All 4 Conditions? | Primary Limitation |
|---|---|---|---|---|
| Disabling Interrupts | Masks CPU interrupt lines during CR | No | No | User process can hang OS; affects only local CPU core |
| Lock Variable | Shared flag lock tested then set in software | No | No | Non-atomic test-and-set causes race condition (violates Condition 1) |
| Strict Alternation | Shared variable turn alternates between and | Yes | No | Process outside CR blocks the other process (violates Condition 3) |
| Peterson's Solution | Combines interested[N] flags with turn variable | Yes | Yes | Busy waiting wastes CPU cycles; software-only for 2 processes |
| TSL Instruction | Hardware bus-locked atomic read-and-set (TSL) | Yes | Yes | Busy waiting wastes CPU cycles and can cause priority inversion |
Sleep and Wakeup
Both Peterson's solution and TSL rely on busy waiting: a waiting process burns CPU cycles continuously testing a variable. Worse yet, busy waiting can cause the priority inversion problem: if a high-priority process becomes ready while a low-priority process is inside its critical region, preempts and spins forever waiting for to leave the critical region, while can never run to leave the critical region because hogs the CPU!
To eliminate busy waiting, blocking primitives put a waiting process into the Blocked (Sleep) state instead of spinning:
sleep(): A system call that blocks the calling process and suspends its execution until another process wakes it up.wakeup(process): A system call that transitions the specified blocked process back to the Ready state.
However, raw sleep() and wakeup() suffer from the lost-wakeup problem: if Process checks a condition, sees it must sleep, and is preempted just before calling sleep(), Process may change the condition and call wakeup(A). Because is not yet asleep, the wakeup signal is lost; when resumes, it calls sleep() and sleeps forever.
Semaphores
Semaphore and Atomic Operations (P / V)
Introduced by E. W. Dijkstra (1965), a semaphore is an integer synchronization variable that records the number of available resource units (or saved wakeups) and is accessed exclusively through two indivisible (atomic) kernel operations (besides initialization):
down(s)/wait(s)/P(s)(from Dutch Proberen, "to test/try"): Checks whether . If , it decrements () and the calling process continues execution. If , the calling process is immediately placed to sleep on 's wait queue without completing thedownoperation. Testing , modifying , and going to sleep are executed as a single, indivisible atomic action.up(s)/signal(s)/V(s)(from Dutch Verhogen, "to increment/raise"): Increments the semaphore value (). If one or more processes are sleeping on , the kernel selects one waiting process, wakes it up, and allows it to complete its pendingdownoperation (leaving with one fewer sleeping process). No process ever blocks on anupoperation.
/* Busy-waiting conceptual view */ /* Blocking (sleep-queue) OS view */
void wait(Semaphore *s) { void down(Semaphore *s) {
while (*s <= 0) ; disable_interrupts_and_lock();
*s = *s - 1; if (s->value > 0)
} s->value--;
else
void signal(Semaphore *s) { block_process_on(s->queue);
*s = *s + 1; unlock_and_restore_interrupts();
} }Types of Semaphores
- Counting Semaphore: Can take any non-negative integer value (). Used to control access to a pool of identical resource instances (initialized to ).
- Binary Semaphore: Restricted to values
0and1only. Initialized to1and used by two or more processes to enforce mutual exclusion (each process performswait(s)before entering its critical region andsignal(s)upon leaving).
Mutex (Mutual Exclusion Lock)
Mutex Lock
A mutex is a simplified, lightweight lock variable designed solely for enforcing mutual exclusion over a shared resource or critical section (when a semaphore's counting capability is unnecessary). A mutex exists in one of two states: unlocked (0) or locked (nonzero), and is manipulated via mutex_lock() and mutex_unlock().
Mutexes are compact and fast, making them ideal for user-space thread packages. Unlike a pure spinlock, if a user-level thread finds the mutex already locked, it calls thread_yield() to immediately yield the CPU to another runnable thread instead of spinning for an entire time quantum:
mutex_lock:
TSL REGISTER, MUTEX | Copy mutex to register and atomically set mutex = 1
CMP REGISTER, #0 | Was mutex zero (unlocked)?
JZE ok | If zero, mutex was unlocked -> acquire lock and return
CALL thread_yield | Mutex is busy; yield CPU to schedule another thread
JMP mutex_lock | Try acquiring the lock again when rescheduled
ok: RET | Return to caller; critical region entered
mutex_unlock:
MOVE MUTEX, #0 | Store 0 in mutex to unlock
RET | Return to caller| Aspect | Semaphore | Mutex |
|---|---|---|
| Core Mechanism | Signaling and counting synchronization variable (wait / signal) | Locking mechanism strictly for mutual exclusion (mutex_lock / mutex_unlock) |
| Ownership | No ownership: any process may call signal(s), even one that did not call wait(s) | Strict ownership: only the thread that locked the mutex is permitted to unlock it |
| Value Range | Non-negative integers (counting) or (binary) | Two states only: unlocked () or locked () |
| Primary Use Cases | Resource counting, producer-consumer buffering, and inter-process ordering | Protecting critical sections in multithreaded and shared-memory programs |
3.3 Message passing and monitors
Inter-Process Communication (IPC) Models
Cooperating processes require an Inter-Process Communication (IPC) mechanism to address three core issues:
- Information transfer: How one process passes data to another.
- Mutual exclusion: Ensuring two processes do not interfere with each other (e.g., two airline reservation processes grabbing the last seat simultaneously).
- Proper sequencing: Enforcing precedence dependencies (e.g., if Process produces data and Process prints it, must wait until has produced data).
Operating systems provide two fundamental IPC models (OS Ch3):
| Aspect | Shared Memory IPC | Message Passing IPC |
|---|---|---|
| Communication Mechanism | Processes read and write variables in a common shared memory region | Processes exchange structured messages via OS system calls (send / receive) |
| Kernel Involvement | Kernel is invoked only once to establish the shared memory region; subsequent accesses are direct memory reads/writes | Every send and receive operation passes through the OS kernel |
| Distributed Systems | Applicable only on single-machine or shared-memory multiprocessors | Works transparently across networks and distributed systems |
| Synchronization Responsibility | Application programmer must explicitly synchronize shared accesses using semaphores/mutexes | Synchronization is built into the blocking send and receive primitives |
Message Passing
Message Passing Primitives
Message passing is an IPC mechanism in which processes communicate and synchronize their actions without sharing the same address space. After establishing a communication link, processes exchange data using two system call primitives:
send(destination, &message)— transmits a message to a target process or mailbox.receive(source, &message)— receives a message from a specified source (or any source) into a buffer.
Design Issues in Message Passing Systems
| Design Dimension | Variants | Operating Mechanism |
|---|---|---|
| Addressing | Direct Addressing vs. Indirect Addressing (Mailboxes / Ports) | In direct addressing, send(P, msg) and receive(Q, msg) name the partner process explicitly. In indirect addressing, messages are sent to and received from shared intermediate queues called mailboxes (or ports). |
| Synchronization | Blocking (Synchronous) vs. Non-Blocking (Asynchronous) | Blocking send/receive: sender blocks until message is received (or buffered); receiver blocks until a message arrives. When both block with no buffer, it is called a rendezvous. Non-blocking: sender/receiver returns immediately. |
| Buffering Capacity | Zero Capacity, Bounded Capacity (), Unbounded Capacity | Zero capacity buffers no messages (strict rendezvous). Bounded capacity holds up to messages in a mailbox before blocking the sender. |
| Reliability & Faults | Acknowledgements, Timeouts, Sequence Numbers | Across networks, the OS guards against lost messages using retransmission timers and sequence numbers to discard duplicate packets. |
Monitors
When programs use low-level semaphores, a single programming mistake—such as reversing the order of two wait() calls or forgetting a signal() on an error path—causes the entire system to deadlock or corrupt data. To eliminate these errors, Brinch Hansen (1973) and C. A. R. Hoare (1974) introduced a high-level language synchronization construct called a monitor.
Monitor and Condition Variables
A monitor is a high-level programming language module (abstract data type) that encapsulates shared variables, the procedures/methods that operate on those variables, and initialization code into a single unit with two fundamental guarantees:
- Encapsulation: Internal shared variables of a monitor cannot be accessed directly by external processes; they can be manipulated only by calling the monitor's local procedures.
- Automatic Mutual Exclusion: The compiler automatically enforces mutual exclusion so that only one process can be active inside the monitor at any instant. Any other process calling a monitor procedure is automatically queued at the monitor entry until the active process exits or waits.
To allow a process inside the monitor to block when a required logical condition is not yet met, monitors provide condition variables (condition c;) supporting two operations:
wait(c)(orc.wait()): Suspends the calling process on condition variablecand atomically releases mutual exclusion on the monitor so another process can enter the monitor.signal(c)(orc.signal()): Resumes one process suspended on condition variablec. If no process is currently waiting onc, thesignal(c)operation has no effect (unlike a semaphoreup(), which increments an integer counter and saves wakeups for the future).
monitor ResourceAllocator {
int available_units;
condition free_resource;
void acquire(int amount) {
while (available_units < amount) {
wait(free_resource); /* Releases monitor lock and sleeps */
}
available_units -= amount;
}
void release(int amount) {
available_units += amount;
signal(free_resource); /* Wakes waiting process, if any */
}
void init(int total) {
available_units = total;
}
}Worked Out Examples
3.1
Two concurrent processes and share an integer variable x initialized to . Process executes the statement x = x + 4; and Process executes x = x - 3;. On a RISC processor, each high-level statement compiles into three machine instructions:
- :
I1: R1 = x;I2: R1 = R1 + 4;I3: x = R1; - :
J1: R2 = x;J2: R2 = R2 - 3;J3: x = R2;
- Show three distinct instruction interleavings that produce three different final values of
x, and list all possible final values ofx. - Show how a binary semaphore
mutex = 1prevents the race condition and guarantees the unique correct final value.
Case 1 — reads x, runs to completion, then writes x ('s update is lost): Consider the interleaved execution sequence :
I1: loadsR1 = 10.I2: computesR1 = 10 + 4 = 14(preempted before storing).J1, J2, J3: loadsR2 = 10, computesR2 = 10 - 3 = 7, and writesx = 7.I3: resumes and writesx = R1 = 14, overwriting .
Case 2 — reads x, runs to completion, then writes x ('s update is lost): Consider the interleaved sequence :
J1, J2: loadsR2 = 10and computesR2 = 10 - 3 = 7(preempted before storing).I1, I2, I3: loadsR1 = 10, computesR1 = 14, and writesx = 14.J3: resumes and writesx = R2 = 7, overwriting .
Case 3 — Serialized execution ( completes before , or completes before ): Under (or ):
- updates
xfrom to . - then loads
R2 = 14, subtracts , and stores:
Thus, the set of all possible final values under unprotected concurrency is .
Enforcing Mutual Exclusion with a Binary Semaphore (mutex = 1): Wrapping each three-instruction sequence in wait(mutex) and signal(mutex) makes the read-modify-write sequence atomic with respect to the other process:
- :
wait(mutex); x = x + 4; signal(mutex); - :
wait(mutex); x = x - 3; signal(mutex);
If enters first, mutex becomes ; if is scheduled after I1, blocks on wait(mutex) until finishes I3 and executes signal(mutex). The final value is deterministically .
- Unprotected interleavings yield three possible final values for
x: (when overwrites ), (when overwrites ), and (when one completes before the other starts). - Protecting each update with
wait(mutex)andsignal(mutex)(initialized tomutex = 1) serializes the critical sections and guarantees the unique correct value .
3.2
Solve the following two counting-semaphore problems:
- A counting semaphore is initialized to . Then
wait(S)() operations andsignal(S)() operations are completed on . What is the final value of ? - A binary/counting semaphore is initialized to . During an interval,
wait(M)operations andsignal(M)operations are issued on . Find the signed value of and determine how many processes are currently blocked in 's waiting queue.
Part 1 — Computing the final value of : Each wait(S) () operation decrements the semaphore value by , and each signal(S) () operation increments it by :
Since , there are available resource instances and processes blocked.
Part 2 — Computing the signed value of and blocked process count: Using the signed semaphore balance equation with , , and :
Interpreting the negative semaphore value: A negative signed semaphore value means the semaphore's available count is and there are:
sleeping in the semaphore queue waiting for future signal(M) calls.
- Final value of semaphore is ( processes blocked).
- Signed value of semaphore is , meaning processes are currently blocked in 's waiting queue.
3.3
In Peterson's two-process solution (N = 2), initially interested[0] = 0, interested[1] = 0, and turn = 0. Suppose Process and Process both call enter_region concurrently in the following interleaved order:
- executes
other = 1 - 0; interested[0] = TRUE; - executes
other = 1 - 1; interested[1] = TRUE; - executes
turn = 1; - executes
turn = 0; - Both and evaluate
while (turn == process && interested[other] == TRUE);
Trace the exact values of interested[0], interested[1], turn, and the while condition for each process to determine which process enters the critical region first and which process waits.
Tracing variable states before the while loop:
- After sets
interested[0] = 1and setsinterested[1] = 1, both intent flags are1(TRUE). - sets
turn = 1, and then overwritesturn = 0. - Thus, entering the
whilecheck:
Evaluating the while condition for Process (process = 0, other = 1 - 0 = 1): Process evaluates:
Because the loop condition is TRUE, Process spins (waits) in the while loop.
Evaluating the while condition for Process (process = 1, other = 1 - 1 = 0): Process evaluates:
Because turn == 0 != 1, Process 's while condition is FALSE, so Process exits enter_region(1) immediately and enters its critical region first.
Exiting the critical region: When Process finishes its critical region and calls leave_region(1), it sets interested[1] = 0. Immediately, Process 's loop condition (turn == 0 && interested[1] == 1) becomes FALSE, allowing Process to enter its critical region next.
At the while check, interested[0] = 1, interested[1] = 1, and turn = 0 (since wrote turn last). Consequently, Process enters the critical region first (its loop condition turn == 1 && interested[0] == 1 is FALSE), while Process busy-waits until Process calls leave_region(1).
Exercises
Practice Exercises — Concurrency, Mutual Exclusion, Semaphores & Monitors
Define race condition and critical region. State the four conditions that must hold to provide a valid, deadlock-free solution to the critical-region problem, and illustrate a race condition using the printer spooler directory example.
Definitions of Race Condition and Critical Region:
- Race Condition: A situation in which two or more concurrent processes read and write shared data and the final outcome depends on the exact relative timing or scheduling order of their execution.
- Critical Region (Critical Section): The part of a program where shared memory, files, or global variables are accessed. Preventing two processes from being in their critical regions simultaneously eliminates race conditions.
Four Conditions for a Good Critical-Region Solution:
- Mutual Exclusion: No two processes may be simultaneously inside their critical regions.
- No Assumptions on Speeds or CPUs: No assumptions may be made about the relative speeds of processes or the number of processors.
- Progress: No process running outside its critical region may block other processes from entering their critical regions.
- Bounded Waiting: No process should have to wait forever to enter its critical region.
Printer Spooler Race Condition Illustration: In a printer spooler directory with shared variable in pointing to the next free slot (initially in = 7):
- Process reads
in = 7into its local variablenext_free_slot = 7, and a clock interrupt preempts . - Process runs, also reads
in = 7into its localnext_free_slot = 7, stores its file name in slot , and updatesin = 8. - Process resumes, writes its file name into slot
next_free_slot = 7(erasing Process 's file name), and setsin = 8. Process 's print job is permanently lost.
A race condition occurs when concurrent accesses to shared data produce results dependent on scheduling order; the code accessing shared data is the critical region. A valid solution requires: (1) Mutual Exclusion, (2) No speed/CPU assumptions, (3) Progress (no blocking by a process outside its CR), and (4) Bounded Waiting. In the printer spooler, two processes reading in = 7 before either increments in both write to slot , causing the second write to overwrite the first.
Explain why Strict Alternation fails to be a valid critical-region solution, and show how Peterson's Solution overcomes this flaw with C code.
Why Strict Alternation Fails: In Strict Alternation, Process spins while turn != 0 and sets turn = 1 on exit; Process spins while turn != 1 and sets turn = 0 on exit. If Process exits its critical region (turn = 0) and spends a long time in its noncritical_region(), Process can enter and exit its critical region (turn = 1), finish its own noncritical_region(), and loop back. Process is now blocked (turn == 1) even though Process is outside its critical region—violating Condition 3 (Progress).
How Peterson's Solution Overcomes This: Peterson's algorithm introduces boolean intent flags interested[2] alongside turn. A process is forced to wait (turn == process && interested[other] == TRUE) only if the other process is also interested in entering the critical region. If Process is in its non-critical region, interested[1] == FALSE, so Process can enter repeatedly without waiting for Process .
Peterson's C Implementation:
#define FALSE 0
#define TRUE 1
#define N 2
int turn;
int interested[N];
void enter_region(int process) {
int other = 1 - process;
interested[process] = TRUE;
turn = process;
while (turn == process && interested[other] == TRUE) ;
}
void leave_region(int process) {
interested[process] = FALSE;
}Strict alternation violates the Progress condition because a process in its non-critical region holds the turn and blocks the other process from re-entering. Peterson's solution adds interested[N] flags so a process waits only when the other process has actively declared interest (interested[other] == TRUE) and turn == process.
A counting semaphore is initialized to . In Phase 1, wait(S) () operations and signal(S) () operations are executed. In Phase 2, wait(S) operations and signal(S) operations are executed.
- Calculate the value of at the end of Phase 1 and state how many resource instances remain available.
- Calculate the signed value of at the end of Phase 2 and state how many processes are blocked on .
Phase 1 Calculation: Starting from , with wait(S) decrements and signal(S) increments:
Since , resource instances remain available and processes are blocked.
Phase 2 Calculation: From , applying wait(S) decrements and signal(S) increments:
(Equivalently over both phases: .)
Number of Blocked Processes: Because , there are available resource instances and process blocked in the semaphore queue.
- At the end of Phase 1, ( available resource instances, blocked processes).
- At the end of Phase 2, the signed value is , meaning process is blocked on .
Compare Semaphores and Mutexes. Also explain how the hardware TSL (Test and Set Lock) instruction works and why thread_yield() is used in user-space mutex implementations instead of pure spinning.
Semaphore vs. Mutex Comparison:
- A semaphore is a generalized integer counter () manipulated by
wait()(down) andsignal()(up) without process ownership; any process can signal a semaphore to wake another waiting process. - A mutex is a binary lock (
0= unlocked,1= locked) with strict ownership: only the thread that locked the mutex viamutex_lock()may unlock it viamutex_unlock().
How the TSL Instruction Works: TSL REGISTER, LOCK atomically copies the current value of the memory word LOCK into REGISTER and writes 1 into LOCK while locking the memory bus so no other CPU can access LOCK mid-instruction. The caller then compares REGISTER with 0: if 0, the caller acquired the lock; if 1, the lock was already held.
Role of thread_yield() in User-Space Mutexes: In user-space threads, the kernel sees only a single process. If a user thread spins in a tight TSL loop waiting for a lock held by another user thread in the same process, the spinning thread will consume the entire CPU time quantum without the lock-holding thread ever getting scheduled! Calling thread_yield() immediately hands control to the user-level thread scheduler so the lock-holding thread can run, finish its critical region, and call mutex_unlock().
A semaphore is a counting/signaling mechanism without ownership, whereas a mutex is a strict-ownership binary lock (0 or 1) for mutual exclusion. TSL RX, LOCK atomically reads LOCK into RX and sets LOCK = 1 by locking the memory bus. User-space mutexes call thread_yield() on contention so the thread holding the lock can be scheduled immediately rather than starving behind a spinning thread.
What is a Monitor in operating system synchronization? Explain how condition variables (wait and signal) operate inside a monitor and why a monitor is less error-prone than semaphores.
Monitor Definition and Automatic Mutual Exclusion: A monitor is a high-level language construct that groups shared data variables, procedures operating on them, and initialization code into a single module. Only monitor procedures can access the shared variables, and the compiler guarantees automatic mutual exclusion: at most one process can be active inside the monitor at any time.
Condition Variables (wait and signal): When a process inside a monitor discovers it cannot proceed (e.g., a buffer is full), it calls wait(c) on a condition variable c. This suspends the calling process on c's queue and releases the monitor lock so another process may enter. When another process inside the monitor changes the state, it calls signal(c) to wake one process waiting on c. Unlike a semaphore's up(), if no process is waiting on c when signal(c) is called, the signal is simply ignored (not stored).
Why Monitors Are Safer Than Semaphores: With semaphores, every process must manually pair wait(mutex) and signal(mutex) in the exact right order; omitting signal(mutex) or swapping two wait() calls causes immediate deadlock. In a monitor, the compiler generates all mutual-exclusion locking automatically, confining synchronization logic inside one clean module.
A monitor is an abstract data type encapsulating shared variables and procedures where the compiler enforces automatic mutual exclusion (only one active process inside the monitor at a time). Condition variables (wait(c) and signal(c)) allow processes to block and wake inside the monitor; unlike semaphores, signal(c) has no effect if no process is waiting, and mutual exclusion is handled automatically by the compiler.
Two concurrent banking threads and share an account variable balance = 1000. Thread deposits Rs. (balance = balance + 500) while Thread withdraws Rs. (balance = balance - 300). Each update executes as LOAD R, balance, ADD/SUB R, amount, and STORE balance, R.
- Determine all possible final values of
balanceif no synchronization is used. - Specify the correct synchronized value and write the pseudocode using
mutex_lock(&m)andmutex_unlock(&m).
Identifying All Possible Unprotected Final Values:
- Interleaving 1 ( lost): loads
1000, loads1000, subtracts300, and stores700, then adds500to its register (1000 + 500) and stores:
- Interleaving 2 ( lost): loads
1000, loads1000, adds500, and stores1500, then subtracts300from its register (1000 - 300) and stores:
- Interleaving 3 (Serialized or ): Both updates take effect sequentially:
Synchronized Implementation Using a Mutex:
/* Thread T1 (Deposit) */ /* Thread T2 (Withdraw) */
mutex_lock(&m); mutex_lock(&m);
balance = balance + 500; balance = balance - 300;
mutex_unlock(&m); mutex_unlock(&m);With mutual exclusion, the second thread cannot load balance until the first thread has stored its updated result, guaranteeing balance = 1200.
- Without synchronization, the possible final values of
balanceare , , and . - The unique correct synchronized balance is , achieved by enclosing each thread's read-modify-write statement inside
mutex_lock(&m)andmutex_unlock(&m).