BSc CSIT (TU) Science Operating System (BSc CSIT, CSC259) Question Paper 2075 Nepal

Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph used to describe the state of allocation of resources to processes in a system. It is used to detect and reason about deadlocks.

Components:

• Vertices are of two types:
  • Process nodes ($P_1, P_2, \dots$) drawn as circles.
  • Resource nodes ($R_1, R_2, \dots$) drawn as rectangles; dots inside a rectangle represent the number of instances of that resource.
• Edges are of two types:
  • Request edge $P_i \rightarrow R_j$: process $P_i$ has requested resource $R_j$ and is waiting.
  • Assignment edge $R_j \rightarrow P_i$: an instance of $R_j$ has been allocated to $P_i$.

Deadlock Detection with a Single Instance per Resource

When each resource type has exactly one instance, deadlock detection reduces to a simple rule:

A deadlock exists if and only if the resource allocation graph contains a cycle.

With multiple instances a cycle is only a necessary condition, but with single instances a cycle is both necessary and sufficient.

Detection algorithm: Construct a wait-for graph by removing resource nodes from the RAG and collapsing edges: if $P_i \rightarrow R_j$ and $R_j \rightarrow P_k$, add an edge $P_i \rightarrow P_k$. Then run a cycle-detection (DFS) on the wait-for graph; any cycle indicates deadlock.

Example

Consider processes $P_1, P_2, P_3$ and single-instance resources $R_1, R_2, R_3$:

• $R_1 \rightarrow P_1$ (R1 held by P1)
• $P_1 \rightarrow R_2$ (P1 requests R2)
• $R_2 \rightarrow P_2$ (R2 held by P2)
• $P_2 \rightarrow R_3$ (P2 requests R3)
• $R_3 \rightarrow P_3$ (R3 held by P3)
• $P_3 \rightarrow R_1$ (P3 requests R1)

Following the edges we get the cycle:

Since a cycle exists and each resource has a single instance, the system is deadlocked: $P_1$ waits for $R_2$ held by $P_2$, $P_2$ waits for $R_3$ held by $P_3$, and $P_3$ waits for $R_1$ held by $P_1$ — a circular wait that can never resolve.

If instead $P_3$ had not requested $R_1$ (no edge $P_3 \rightarrow R_1$), the graph would be acyclic and no deadlock would exist.

The Critical Section Problem

A critical section is a segment of code in which a process accesses shared resources (variables, files, devices). When multiple processes run concurrently, uncontrolled access to such shared data causes race conditions. The critical-section problem is to design a protocol that processes use to cooperate, ensuring correct execution.

A correct solution must satisfy three requirements:

1. Mutual Exclusion — at most one process executes in its critical section at a time.
2. Progress — if no process is in its critical section, only the processes contending may decide who enters next, and this decision cannot be postponed indefinitely.
3. Bounded Waiting — there is a bound on how many times other processes enter their critical sections after a process requests entry and before it is granted (no starvation).

The general structure of each process is:

do {
    entry section
        critical section
    exit section
        remainder section
} while (true);

Peterson's Solution

Peterson's solution is a classic software solution for two processes ($P_0$ and $P_1$). It uses two shared variables:

• int turn; — whose turn it is to enter.
• boolean flag[2]; — flag[i] is true if $P_i$ wants to enter.

Code for process $P_i$ (where j = 1 - i):

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);  // busy wait
        // critical section
    flag[i] = false;
        // remainder section
} while (true);

$P_i$ sets its flag and politely gives the turn to $P_j$. It enters only if $P_j$ does not want in (!flag[j]) or it is $P_i$'s turn. This satisfies mutual exclusion, progress, and bounded waiting, but relies on busy waiting and only works for two processes.

Semaphores

A semaphore $S$ is an integer variable accessed only through two atomic operations:

wait(S):  while (S <= 0); S = S - 1;   // also called P()
signal(S): S = S + 1;                   // also called V()

Practical implementations avoid busy waiting by maintaining a waiting queue: wait() blocks the process when $S<0$, and signal() wakes a blocked process.

Achieving synchronization: Initialize a semaphore mutex = 1. Each process wraps its critical section:

wait(mutex);
    // critical section
signal(mutex);
    // remainder section

This guarantees mutual exclusion for any number of processes. Counting semaphores (initialized to $N$) control access to a pool of $N$ identical resources, while a binary semaphore (values 0/1) acts as a mutex lock.

Paging

Paging is a memory-management scheme that allows the physical address space of a process to be non-contiguous, eliminating external fragmentation and the need for compaction.

• Physical memory is divided into fixed-size blocks called frames.
• Logical (virtual) memory is divided into blocks of the same size called pages.
• A typical page/frame size is a power of two (e.g., 4 KB).
• When a process executes, its pages are loaded into any available frames; the OS keeps the page-to-frame mapping in a page table.

Logical-to-Physical Address Translation

The CPU generates a logical address split into two parts:

If the logical address space is $2^m$ and the page size is $2^n$, then the high-order $m-n$ bits give the page number $p$ and the low-order $n$ bits give the offset $d$.

Steps:

1. Extract page number $p$ and offset $d$ from the logical address.
2. Use $p$ as an index into the page table to obtain the frame number $f$.
3. Form the physical address as $f \times (\text{page size}) + d$, i.e., concatenate frame number $f$ with offset $d$.

The offset $d$ is unchanged because pages and frames are the same size.

Translation Look-aside Buffer (TLB)

Using only a page table requires two memory accesses per reference (one to read the page table, one for the data), which is slow. A TLB is a small, fast, fully-associative hardware cache that stores recently used (page → frame) mappings.

Address translation with TLB:

1. Present page number $p$ to the TLB.
2. TLB hit: frame $f$ is returned immediately; combine with offset $d$.
3. TLB miss: access the page table in memory to get $f$, then load that mapping into the TLB for future use.

Effective Access Time (EAT): If TLB lookup takes $\epsilon$, memory access takes $m$, and the hit ratio is $\alpha$:

Example: with $m = 100$ ns, $\epsilon = 20$ ns, $\alpha = 0.8$:

This is far better than the 200 ns required without a TLB on every access.

Deadlock and starvation are both situations where processes fail to make progress, but they differ fundamentally:

Key point: Every deadlock implies starvation for the involved processes, but starvation does not imply deadlock — a starved process may still eventually run.

Context Switching

A context switch is the mechanism by which the CPU is switched from one process (or thread) to another. The kernel saves the state (context) of the currently running process and restores the state of the next scheduled process.

The context of a process is held in its Process Control Block (PCB) and includes:

• Program counter and CPU registers,
• CPU scheduling information and process state,
• Memory-management information (page tables, base/limit registers),
• I/O status and accounting information.

Steps: save current process state → PCB; update its PCB and queues; select next process via the scheduler; restore the next process's state from its PCB; resume execution.

Context switches occur on interrupts, system calls, time-slice expiry, or when a process blocks for I/O.

Overhead

Context switching is pure overhead — during the switch the CPU does no useful work for any user process:

• Time spent saving/restoring registers and PCB data.
• Cache and TLB are flushed/invalidated, so the new process suffers cache misses afterward.
• On paged systems, memory-management structures (page tables) must be reloaded.

The cost depends on hardware support (e.g., multiple register sets reduce it). Frequent context switching (e.g., a very small time quantum in Round Robin) degrades throughput, so the quantum is chosen to keep switching overhead a small fraction of the total CPU time.

Producer-Consumer (Bounded-Buffer) Problem

The producer-consumer problem is a classic synchronization problem involving two types of processes sharing a fixed-size buffer of $N$ slots:

• The producer generates data items and places them into the buffer.
• The consumer removes items from the buffer and uses them.

The challenge (synchronization conditions):

• The producer must not add to a full buffer (wait until a slot is free).
• The consumer must not remove from an empty buffer (wait until an item exists).
• The producer and consumer must not access the buffer simultaneously (mutual exclusion on the shared buffer / count).

Semaphore Solution

Three semaphores are used:

• mutex = 1 — mutual exclusion on the buffer.
• empty = N — counts empty slots.
• full = 0 — counts filled slots.

// Producer
wait(empty); wait(mutex);
    add item to buffer;
signal(mutex); signal(full);

// Consumer
wait(full); wait(mutex);
    remove item from buffer;
signal(mutex); signal(empty);

This ensures the producer blocks when the buffer is full and the consumer blocks when it is empty, while mutex prevents simultaneous access. It illustrates cooperation between processes that must share a bounded buffer correctly.

Dining Philosophers Problem

The Dining Philosophers problem is a classic synchronization problem that illustrates deadlock and resource-sharing issues among concurrent processes.

Setup: Five philosophers sit around a circular table. Each philosopher alternates between thinking and eating. There are five chopsticks, one between each pair of philosophers. To eat, a philosopher needs both the chopstick to their left and the one to their right. After eating, they put both chopsticks down and resume thinking.

The chopsticks are the shared resources, and each is modeled by a semaphore:

semaphore chopstick[5] = {1,1,1,1,1};

do {
    wait(chopstick[i]);             // pick up left
    wait(chopstick[(i+1) % 5]);     // pick up right
        // eat
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
        // think
} while (true);

The problem: If all five philosophers simultaneously pick up their left chopstick, each then waits forever for the right chopstick held by a neighbor — a circular wait, i.e., deadlock. There is also a risk of starvation.

Solutions:

1. Allow at most four philosophers at the table at once.
2. A philosopher may pick up chopsticks only if both are available (pick up inside a critical section).
3. Use asymmetry: odd philosophers pick up left-then-right, even philosophers right-then-left, breaking the circular wait.

Thrashing

Thrashing is a condition in a virtual-memory system where a process (or the whole system) spends more time paging (swapping pages in and out of memory) than executing. CPU utilization drops sharply because processes are constantly waiting for pages.

Cause: It occurs when a process does not have enough frames to hold its working set (the set of pages it is actively using). Each instruction may cause a page fault, evicting a page that is needed again immediately, causing another fault — a high page-fault rate.

The vicious cycle: Low CPU utilization → OS increases the degree of multiprogramming → less memory per process → more page faults → even lower CPU utilization.

Prevention / Control

1. Working-Set Model: Track each process's working set using a window of recent references; allocate enough frames to hold it, and suspend (swap out) a process if the demand exceeds available frames.
2. Page-Fault Frequency (PFF) control: Monitor each process's page-fault rate; if it rises above an upper bound, allocate more frames; if it falls below a lower bound, reclaim frames.
3. Reduce the degree of multiprogramming: Swap out some processes so the rest have enough frames.
4. Use local page-replacement so one greedy process cannot steal frames from others, and add more physical RAM.

Logical vs Physical Address Space

A logical address (also called a virtual address) is generated by the CPU during program execution. A physical address is the actual address seen by the memory unit (loaded into the memory-address register).

Relationship: At compile time and load time the logical and physical addresses are identical. With execution-time binding, they differ, and the MMU maps logical to physical at run time. In a simple base-register scheme the mapping is:

For example, with relocation register $= 14000$, a logical address $346$ maps to physical address $14346$.

Segmentation

Segmentation is a memory-management scheme that supports the user's logical view of memory. A program is regarded as a collection of variable-sized segments — logical units such as main program, function, stack, array, global variables, each with a name and length — rather than one linear array of bytes.

Addressing

A logical address under segmentation is a two-tuple:

The mapping is done through a segment table; each entry has:

• Base — the starting physical address of the segment.
• Limit — the length of the segment.

Address translation:

1. Use segment number $s$ to index the segment table → obtain base and limit.
2. Check that offset $d < \text{limit}$; otherwise raise a trap (addressing error / segmentation fault).
3. Physical address $= \text{base} + d$.

Advantages and Disadvantages

• Advantages: Matches the programmer's logical view; allows protection and sharing at the segment level (e.g., share a code segment, set read/execute permissions per segment); no internal fragmentation.
• Disadvantage: Because segments vary in size, segmentation suffers from external fragmentation and may require compaction.

Semaphore

A semaphore is a synchronization tool — an integer variable $S$ that, apart from initialization, is accessed only through two atomic (indivisible) operations:

wait(S):   while (S <= 0); S = S - 1;   // P(), down
signal(S): S = S + 1;                    // V(), up

It is used to control access to shared resources and to coordinate the execution order of concurrent processes, solving the critical-section and other synchronization problems.

Binary vs Counting Semaphore

In short: a binary semaphore is a special case of a counting semaphore restricted to the values 0 and 1.

Monitor

A monitor is a high-level synchronization construct that provides a convenient and safe mechanism for process synchronization, overcoming the error-prone nature of semaphores (where a misplaced wait/signal can break mutual exclusion or cause deadlock).

Definition: A monitor is an abstract data type that encapsulates:

• Shared variables (the monitor's internal data),
• Procedures/methods that operate on those variables,
• An initialization block.

Key property — automatic mutual exclusion: Only one process can be active inside the monitor at a time. The compiler/runtime enforces this, so the programmer does not place explicit locks. Other processes calling a monitor procedure are blocked until the monitor is free.

Condition variables: To allow a process to wait inside the monitor for a specific condition, monitors provide condition variables with two operations:

• x.wait() — the calling process is suspended and releases the monitor until another process signals x.
• x.signal() — resumes exactly one process waiting on x (if none is waiting, it has no effect).

monitor ResourceAllocator {
    boolean busy;
    condition x;
    procedure acquire() {
        if (busy) x.wait();
        busy = true;
    }
    procedure release() {
        busy = false;
        x.signal();
    }
    initialization { busy = false; }
}

Thus monitors guarantee mutual exclusion automatically and use condition variables for finer-grained waiting/signalling, making concurrent programs easier to write correctly than with raw semaphores.