PadhaikoAll subjects

Principles of concurrency, race condition, critical region · Mutual…

Operating System (ENCT 254)

Open in the Padhaiko app

3.1 Principles of concurrency, race condition, critical region

Definition

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.

Concurrent processes fall into two categories based on how they interact:

AspectIndependent ProcessesCooperating Processes
State & Data SharingDo not share data, memory, or messages with any other processShare variables, memory buffers, files, or exchange messages
Interaction ModeCompete only for system resources (CPU time, memory, I/O devices)Both compete for resources and collaborate to accomplish a common task
DeterminismExecution 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:

  1. 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.
  2. 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):

Shared Character Echo ProcedureC
char chin, chout;   /* Shared global variables */

void echo(void) {
    chin = getchar();
    chout = chin;
    putchar(chout);
}

Race Condition

Definition

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:

Suppose Process and Process both decide to queue a file for printing at nearly the same instant:

Printer Spooler Race Condition Trace (Initial in = 7)
Time SequenceProcess ActionProcess ActionA.next_free_slotB.next_free_slotShared inSlot 7 Content
Reads shared in () into local next_free_slot——Empty
Clock interrupt! CPU switches from to Scheduled to run—Empty
SuspendedReads shared in () into local next_free_slotEmpty
SuspendedWrites "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 = 8Executing 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)

Definition

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:

  1. Mutual Exclusion: No two processes may be simultaneously inside their critical regions.
  2. 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.
  3. Progress: No process running outside its critical region (in its non-critical/remainder region) may block another process from entering its critical region.
  4. 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.
General Structure of a Concurrent Process around a Critical RegionText
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

Definition

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.

2. Lock Variables

A software approach using a single shared integer variable lock, initialized to 0:

while (lock != 0) ;   /* Busy wait until lock is 0 */
lock = 1;             /* Acquire lock */
critical_region();
lock = 0;             /* Release lock */

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:

Strict Alternation for Two Processes (P0 and P1)C
/* 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();
}                                       }

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:

Peterson's Solution for Two ProcessesC
#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 */
}

5. Hardware TSL (Test and Set Lock) Instruction

Many CPU architectures provide an atomic hardware instruction TSL RX, LOCK (Test and Set Lock):

  1. It reads the contents of the memory word lock into CPU register RX.
  2. It stores a nonzero value (1) into the memory location lock.

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.

Mutual Exclusion Using the Atomic TSL InstructionText
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
Summary of Busy-Waiting Mutual Exclusion Techniques
TechniqueMechanismMultiprocessor Safe?Satisfies All 4 Conditions?Primary Limitation
Disabling InterruptsMasks CPU interrupt lines during CRNoNoUser process can hang OS; affects only local CPU core
Lock VariableShared flag lock tested then set in softwareNoNoNon-atomic test-and-set causes race condition (violates Condition 1)
Strict AlternationShared variable turn alternates between and YesNoProcess outside CR blocks the other process (violates Condition 3)
Peterson's SolutionCombines interested[N] flags with turn variableYesYesBusy waiting wastes CPU cycles; software-only for 2 processes
TSL InstructionHardware bus-locked atomic read-and-set (TSL)YesYesBusy 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:

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

Definition

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):

  1. 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 the down operation. Testing , modifying , and going to sleep are executed as a single, indivisible atomic action.
  2. 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 pending down operation (leaving with one fewer sleeping process). No process ever blocks on an up operation.
Conceptual Structure of Semaphore OperationsC
/* 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

  1. Counting Semaphore: Can take any non-negative integer value (). Used to control access to a pool of identical resource instances (initialized to ).
  2. Binary Semaphore: Restricted to values 0 and 1 only. Initialized to 1 and used by two or more processes to enforce mutual exclusion (each process performs wait(s) before entering its critical region and signal(s) upon leaving).

Mutex (Mutual Exclusion Lock)

Definition

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:

User-Space Mutex Implementation Using TSL and thread_yieldText
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
AspectSemaphoreMutex
Core MechanismSignaling and counting synchronization variable (wait / signal)Locking mechanism strictly for mutual exclusion (mutex_lock / mutex_unlock)
OwnershipNo 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 RangeNon-negative integers (counting) or (binary)Two states only: unlocked () or locked ()
Primary Use CasesResource counting, producer-consumer buffering, and inter-process orderingProtecting 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:

  1. Information transfer: How one process passes data to another.
  2. Mutual exclusion: Ensuring two processes do not interfere with each other (e.g., two airline reservation processes grabbing the last seat simultaneously).
  3. 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):

AspectShared Memory IPCMessage Passing IPC
Communication MechanismProcesses read and write variables in a common shared memory regionProcesses exchange structured messages via OS system calls (send / receive)
Kernel InvolvementKernel is invoked only once to establish the shared memory region; subsequent accesses are direct memory reads/writesEvery send and receive operation passes through the OS kernel
Distributed SystemsApplicable only on single-machine or shared-memory multiprocessorsWorks transparently across networks and distributed systems
Synchronization ResponsibilityApplication programmer must explicitly synchronize shared accesses using semaphores/mutexesSynchronization is built into the blocking send and receive primitives

Message Passing

Definition

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:

Design Issues in Message Passing Systems

Key Design Dimensions of Message Passing Systems
Design DimensionVariantsOperating Mechanism
AddressingDirect 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).
SynchronizationBlocking (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 CapacityZero Capacity, Bounded Capacity (), Unbounded CapacityZero capacity buffers no messages (strict rendezvous). Bounded capacity holds up to messages in a mailbox before blocking the sender.
Reliability & FaultsAcknowledgements, Timeouts, Sequence NumbersAcross 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.

Definition

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:

  1. 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.
  2. 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:

Monitor Pseudocode Structure for Bounded CounterC
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

Example 3.1

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:

  1. Show three distinct instruction interleavings that produce three different final values of x, and list all possible final values of x.
  2. Show how a binary semaphore mutex = 1 prevents 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: loads R1 = 10.
  • I2: computes R1 = 10 + 4 = 14 (preempted before storing).
  • J1, J2, J3: loads R2 = 10, computes R2 = 10 - 3 = 7, and writes x = 7.
  • I3: resumes and writes x = R1 = 14, overwriting .

Case 2 — reads x, runs to completion, then writes x ('s update is lost): Consider the interleaved sequence :

  • J1, J2: loads R2 = 10 and computes R2 = 10 - 3 = 7 (preempted before storing).
  • I1, I2, I3: loads R1 = 10, computes R1 = 14, and writes x = 14.
  • J3: resumes and writes x = R2 = 7, overwriting .

Case 3 — Serialized execution ( completes before , or completes before ): Under (or ):

  • updates x from 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 .

Answer:
  1. Unprotected interleavings yield three possible final values for x: (when overwrites ), (when overwrites ), and (when one completes before the other starts).
  2. Protecting each update with wait(mutex) and signal(mutex) (initialized to mutex = 1) serializes the critical sections and guarantees the unique correct value .
Example 3.2

3.2

Solve the following two counting-semaphore problems:

  1. A counting semaphore is initialized to . Then wait(S) () operations and signal(S) () operations are completed on . What is the final value of ?
  2. A binary/counting semaphore is initialized to . During an interval, wait(M) operations and signal(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.

Answer:
  1. Final value of semaphore is ( processes blocked).
  2. Signed value of semaphore is , meaning processes are currently blocked in 's waiting queue.
Example 3.3

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:

  1. executes other = 1 - 0; interested[0] = TRUE;
  2. executes other = 1 - 1; interested[1] = TRUE;
  3. executes turn = 1;
  4. executes turn = 0;
  5. 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] = 1 and sets interested[1] = 1, both intent flags are 1 (TRUE).
  • sets turn = 1, and then overwrites turn = 0.
  • Thus, entering the while check:

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.

Answer:

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

Question 1

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:

  1. Mutual Exclusion: No two processes may be simultaneously inside their critical regions.
  2. No Assumptions on Speeds or CPUs: No assumptions may be made about the relative speeds of processes or the number of processors.
  3. Progress: No process running outside its critical region may block other processes from entering their critical regions.
  4. 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):

  1. Process reads in = 7 into its local variable next_free_slot = 7, and a clock interrupt preempts .
  2. Process runs, also reads in = 7 into its local next_free_slot = 7, stores its file name in slot , and updates in = 8.
  3. Process resumes, writes its file name into slot next_free_slot = 7 (erasing Process 's file name), and sets in = 8. Process 's print job is permanently lost.
Answer:

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.

Question 2

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:

Peterson's Mutual Exclusion AlgorithmC
#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;
}
Answer:

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.

Question 3

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.

  1. Calculate the value of at the end of Phase 1 and state how many resource instances remain available.
  2. 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.

Answer:
  1. At the end of Phase 1, ( available resource instances, blocked processes).
  2. At the end of Phase 2, the signed value is , meaning process is blocked on .
Question 4

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) and signal() (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 via mutex_lock() may unlock it via mutex_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().

Answer:

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.

Question 5

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.

Answer:

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.

Question 6

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.

  1. Determine all possible final values of balance if no synchronization is used.
  2. Specify the correct synchronized value and write the pseudocode using mutex_lock(&m) and mutex_unlock(&m).

Identifying All Possible Unprotected Final Values:

  • Interleaving 1 ( lost): loads 1000, loads 1000, subtracts 300, and stores 700, then adds 500 to its register (1000 + 500) and stores:
  • Interleaving 2 ( lost): loads 1000, loads 1000, adds 500, and stores 1500, then subtracts 300 from its register (1000 - 300) and stores:
  • Interleaving 3 (Serialized or ): Both updates take effect sequentially:

Synchronized Implementation Using a Mutex:

Synchronized Bank Balance Updates Using MutexC
/* 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.

Answer:
  1. Without synchronization, the possible final values of balance are , , and .
  2. The unique correct synchronized balance is , achieved by enclosing each thread's read-modify-write statement inside mutex_lock(&m) and mutex_unlock(&m).

Past exam questions for Operating System

← Threads and thread schedulingClassical problems of synchronization: Readers-writers problem… →