BE Computer Engineering (Pokhara University) Operating Systems (PU, CMP 232) Question Paper 2079 Nepal

(a) SRTF and Round Robin (q = 3 ms)

Processes: P1(0,8), P2(1,4), P3(2,9), P4(3,5).

Shortest Remaining Time First (SRTF) — preemptive

Gantt chart

| P1 |      P2      |   P4   |        P1        |       P3        |
0    1             5        10                 17                26

• t0: only P1 → runs. t1: P2(4) < P1 remaining(7) → preempt to P2.
• P2 runs 1–5 (P3, P4 arrive but have larger remaining). At t5: P1=7, P3=9, P4=5 → run P4.
• P4 runs 5–10. At t10: P1=7, P3=9 → run P1 (10–17). Finally P3 (17–26).

$$\text{Avg TAT}=\frac{17+4+24+7}{4}=13\text{ ms},\qquad \text{Avg WT}=\frac{9+0+15+2}{4}=6.5\text{ ms}$$

Round Robin, quantum = 3 ms

Gantt chart

| P1 | P2 | P3 | P4 | P1 |P2| P3 | P4 | P1 | P3 |
0    3    6    9    12   15 16  19   21   23  26

Ready-queue evolution (FCFS within quantum): P1,P2,P3,P4,P1,P2,P3,P4,P1,P3.

$$\text{Avg TAT}=\frac{23+15+24+18}{4}=20\text{ ms},\qquad \text{Avg WT}=\frac{15+11+15+13}{4}=13.5\text{ ms}$$

(b) Comparison and concepts

• SRTF gives lower average waiting/turnaround time (6.5 vs 13.5 ms) because it is provably optimal for minimizing average waiting time, but it requires knowing burst times in advance and can starve long jobs.
• Round Robin gives larger averages here but provides good responsiveness and fairness (no process waits more than (n−1)·q before getting CPU), which is ideal for time-sharing.

Starvation: a process waits indefinitely for the CPU because shorter/higher-priority jobs keep arriving (e.g., long process P3 under SRTF, or a low-priority job under priority scheduling). It is cured by aging — gradually raising the priority of waiting processes.

Convoy effect: in FCFS, one long CPU-bound process holds the CPU while many short I/O-bound processes queue behind it, leaving I/O devices idle and lowering throughput. Preemptive/short-job-favouring schedulers reduce it.

(a) Banker's Algorithm

Total resources: A=10, B=5, C=7. Allocation sums: A=7, B=2, C=5.

$$\textbf{Available} = \text{Total}-\sum\text{Alloc} = (10-7,\;5-2,\;7-5) = (3,3,2)$$

Need = Max − Allocation

Safety check (Work starts at Available = (3,3,2)):

1. P1: Need(1,2,2) ≤ (3,3,2) ✓ → Work = (3,3,2)+(2,0,0) = (5,3,2)
2. P3: Need(0,1,1) ≤ (5,3,2) ✓ → Work = (5,3,2)+(2,1,1) = (7,4,3)
3. P0: Need(7,4,3) ≤ (7,4,3) ✓ → Work = (7,4,3)+(0,1,0) = (7,5,3)
4. P2: Need(6,0,0) ≤ (7,5,3) ✓ → Work = (7,5,3)+(3,0,2) = (10,5,5)
5. P4: Need(4,3,1) ≤ (10,5,5) ✓ → Work = (10,5,5)+(0,0,2) = (10,5,7)

All processes finish, so the system is in a SAFE state.

$$\boxed{\text{Safe sequence: } \langle P_1, P_3, P_0, P_2, P_4 \rangle}$$

(Other valid sequences exist, e.g. $\langle P_1,P_3,P_4,P_0,P_2\rangle$.)

(b) Four necessary conditions and prevention

All four conditions must hold simultaneously for deadlock; breaking any one prevents deadlock.

(a) Page faults with 3 frames

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

FIFO

Replace the oldest-loaded page. Faults occur at: 7,0,1,2,3,0,4,2,3,0,1,2,7,0,1

$$\textbf{FIFO page faults} = 15$$

Optimal (OPT)

Replace the page whose next use is farthest in the future. Faults at: 7,0,1,2,3,4,0,1,7

$$\textbf{OPT page faults} = 9$$

LRU

Replace the least-recently-used page. Faults at: 7,0,1,2,3,4,2,3,0,1,0,7

$$\textbf{LRU page faults} = 12$$

Summary

Optimal performs best (9 faults). It is the theoretical lower bound but is not implementable since it needs future knowledge; LRU is the best practical approximation.

(b) Belady's anomaly, thrashing, working set

Belady's anomaly: for some reference strings under FIFO, increasing the number of frames increases the number of page faults, contradicting intuition. Classic example: string 1 2 3 4 1 2 5 1 2 3 4 5 gives 9 faults with 3 frames but 10 faults with 4 frames.

Why LRU and OPT are immune: they are stack algorithms — the set of pages in memory with n frames is always a subset of the set with n+1 frames. Therefore adding a frame can never cause a page that was present to be absent, so faults can only stay the same or decrease.

Thrashing: a condition where a process spends more time paging (servicing page faults) than executing, because it has too few frames to hold its active working set. CPU utilization collapses as processes queue on the paging device.

Working-set model: the working set $WS(t)$ is the set of pages referenced in the most recent window $\Delta$ of references. The OS estimates each process's working-set size $WSS_i$ and ensures $\sum WSS_i \le$ total frames. If demand exceeds available frames it suspends (swaps out) a process, allocating enough frames to the rest to keep their working sets resident — preventing thrashing.

(a) The Critical-Section Problem

When several processes share data, the segment of code in which a process accesses/updates that shared data is its critical section. The problem is to design a protocol (entry + exit sections) so that no two processes execute their critical sections at the same time.

A correct solution must satisfy three requirements:

1. Mutual exclusion — if one process is executing in its critical section, no other process may execute in its critical section.
2. Progress — if no process is in its critical section and some processes wish to enter, only those not in their remainder section participate in deciding who enters next, and the decision cannot be postponed indefinitely.
3. Bounded waiting — there is a bound on the number of times other processes may enter their critical sections after a process has made a request and before that request is granted (no starvation).

(b) Producer–Consumer (Bounded Buffer)

A producer generates items into a shared buffer of n slots; a consumer removes them. They must be synchronized so the producer waits when the buffer is full and the consumer waits when it is empty, with mutually exclusive buffer access.

Semaphores used

// Producer
do {
    item = produce_item();
    wait(empty);   // block if no free slot
    wait(mutex);   // enter critical section
    add item to buffer;
    signal(mutex); // leave critical section
    signal(full);  // one more filled slot
} while (true);

// Consumer
do {
    wait(full);    // block if buffer empty
    wait(mutex);
    remove item from buffer;
    signal(mutex);
    signal(empty); // one more free slot
    consume_item(item);
} while (true);

How correctness is guaranteed

• No buffer overflow: wait(empty) lets the producer proceed only while a free slot exists; when empty = 0 the producer blocks.
• No buffer underflow: wait(full) lets the consumer proceed only while a filled slot exists; when full = 0 the consumer blocks.
• No race condition: mutex serializes all buffer index/pointer updates so producer and consumer never modify the buffer simultaneously.

Note the ordering: wait(empty/full) is taken before wait(mutex) to avoid deadlock (acquiring mutex first and then blocking on a full/empty counter would lock out the other party forever).

Process State Transition Diagram

A process moves through five states:

      admit          dispatch         exit
NEW -------> READY ------------> RUNNING ------> TERMINATED
               ^                   |   |
   I/O complete|        timeout/   |   | I/O or event wait
   (event done)|        preempt    |   v
               +--------- READY <--+  WAITING
                                      (blocked)

• New: process is being created.
• Ready: waiting to be assigned to a CPU.
• Running: instructions are being executed.
• Waiting/Blocked: waiting for an event (I/O completion, signal).
• Terminated: finished execution.

Key transitions: Ready→Running (dispatch by scheduler), Running→Ready (timeout/preemption), Running→Waiting (I/O request), Waiting→Ready (I/O completion), Running→Terminated (exit).

Process Control Block (PCB)

The PCB is the kernel data structure representing a process. It stores:

• Process state (ready, running, waiting…) and PID.
• Program counter — address of next instruction.
• CPU registers — accumulators, index, stack pointers, general registers.
• CPU-scheduling information — priority, queue pointers.
• Memory-management information — base/limit registers, page tables.
• Accounting information — CPU time used, time limits.
• I/O status information — list of open files and allocated devices.

Context Switch

When the CPU switches from process P0 to P1, the kernel saves P0's CPU context (program counter and all registers) into P0's PCB, then restores P1's saved context (PC, registers, memory maps) from P1's PCB so P1 resumes exactly where it left off. This save/restore is pure overhead (no useful work is done during it), so frequent context switches reduce efficiency.

Disk Scheduling — head at cylinder 53

Queue (arrival order): 98, 183, 37, 122, 14, 124, 65, 67.

FCFS

Serve in arrival order:

$$53\to98\to183\to37\to122\to14\to124\to65\to67$$ $$45+85+146+85+108+110+59+2 = \boxed{640\text{ cylinders}}$$

SSTF (Shortest Seek Time First)

Always serve the nearest pending request:

$$53\to65\to67\to37\to14\to98\to122\to124\to183$$ $$12+2+30+23+84+24+2+59 = \boxed{236\text{ cylinders}}$$

SCAN (head moving toward higher cylinders, then reverses)

Sorted requests: 14, 37, 65, 67, 98, 122, 124, 183. Move up to the end (199), then sweep down:

$$53\to65\to67\to98\to122\to124\to183\to199\to37\to14$$ $$\underbrace{(199-53)}_{146} + \underbrace{(199-14)}_{185} = \boxed{331\text{ cylinders}}$$

Summary: SSTF = 236 (best here) < SCAN = 331 < FCFS = 640.

File-Allocation Methods Compared

• Contiguous: each file occupies consecutive blocks; fast access but suffers external fragmentation and is hard to grow.
• Linked: each block points to the next; no fragmentation and easy growth, but no efficient random access and pointers consume space / are fragile.
• Indexed: an index block holds all the file's block addresses; supports direct access without external fragmentation, at the cost of an index block per file.

UNIX i-node

UNIX uses a (multi-level) indexed allocation via the i-node. Each i-node contains a few direct block pointers plus single-, double-, and triple-indirect pointers. This is chosen because it:

• supports fast direct (random) access,
• avoids external fragmentation,
• is efficient for small files (direct pointers only) yet scales to very large files through the indirect blocks.

(a) Internal vs External Fragmentation

• Internal fragmentation: memory allocated to a process is slightly larger than requested; the unused space inside an allocated partition/page is wasted (e.g., a 100 KB process placed in a 128 KB fixed partition wastes 28 KB).
• External fragmentation: total free memory is enough, but it is split into many non-contiguous small holes, so a large request cannot be satisfied even though the sum of free space exceeds it. Cured by compaction or paging.

(b) First-Fit, Best-Fit, Worst-Fit

Free partitions (in order): 100, 500, 200, 300, 600 KB. Processes (in order): 212, 417, 112, 426 KB.

First-Fit (first partition large enough)

Best-Fit (smallest hole that fits)

All four processes are allocated with Best-Fit.

Worst-Fit (largest available hole)

Conclusion: for this set, Best-Fit packs all processes successfully, while First-Fit and Worst-Fit fail to place the 426 KB process.

Paging

Paging is a memory-management scheme that allows a process's physical address space to be non-contiguous. Physical memory is divided into fixed-size blocks called frames, and logical memory into blocks of the same size called pages. When a process runs, its pages are loaded into any available frames; a page table maps pages to frames. Paging eliminates external fragmentation (some internal fragmentation remains in the last page).

Logical-to-Physical Address Translation

A logical address generated by the CPU is split into two parts:

$$\text{Logical address} = \langle\; \underbrace{p}_{\text{page number}},\; \underbrace{d}_{\text{offset}} \;\rangle$$

 CPU --> | p | d |
           |
           v
     [ Page Table ]  page p --> frame f
           |
           v
  Physical address = | f | d |  --> Physical Memory

• The page number p indexes the page table to obtain the frame number f.
• The offset d is appended unchanged to f to form the physical address $f \times (\text{page size}) + d$.

Translation Look-aside Buffer (TLB)

If the page table is in main memory, every reference needs two memory accesses (one to read the page-table entry, one for the data) — doubling access time. The TLB is a small, fast associative cache holding recently used (page → frame) mappings.

• On a TLB hit, the frame number is obtained from the TLB with negligible delay, so only one memory access (for the data) is needed.
• On a TLB miss, the page table in memory is consulted and the mapping is loaded into the TLB.

Effective access time with TLB hit-ratio $\alpha$, TLB time $\varepsilon$, memory time $m$:

$$EAT = \alpha(\varepsilon + m) + (1-\alpha)(\varepsilon + 2m)$$

A high hit ratio (typically > 90%) keeps the EAT close to a single memory access, greatly reducing the overhead of paging.

Deadlock Avoidance vs Deadlock Detection

Detection with a Resource-Allocation Graph (single-instance resources)

With one instance per resource type, a cycle in the resource-allocation graph (RAG) is a necessary and sufficient condition for deadlock.

• Request edge: $P_i \to R_j$ (process requests resource).
• Assignment edge: $R_j \to P_i$ (resource allocated to process).

Example:

  P1 --> R1 --> P2 --> R2 --> P1

Here P1 holds R2 and requests R1; P2 holds R1 and requests R2. The edges form the cycle $P1 \to R1 \to P2 \to R2 \to P1$. Since each resource has a single instance, this cycle means each process waits for a resource held by the other — a deadlock. (With multiple instances, a cycle is only necessary, not sufficient, and a detection algorithm is required.)

(a) Programmed I/O vs Interrupt-Driven I/O vs DMA

(b) System Call vs Function Call

• A function (procedure) call transfers control to another routine within the same program, in user mode, using the normal call/return mechanism and the user stack. No privilege change.
• A system call is a request for an OS service (I/O, file, process control) that requires privileged (kernel) operations. It crosses the user→kernel boundary.

User-mode → kernel-mode transition during a system call:

1. The program places the system-call number and arguments in registers (or stack).
2. It executes a special trap / software-interrupt instruction (e.g., syscall, int 0x80, svc).
3. The trap switches the CPU mode bit from user (1) to kernel (0) and jumps via the interrupt/trap vector to the kernel's system-call handler.
4. The handler validates arguments, uses the number to index the system-call dispatch table, and executes the requested service in kernel mode.
5. On return, results are passed back, the mode bit is reset to user mode, and control resumes in the user program.

This controlled, hardware-enforced switch protects the kernel and hardware from direct user access.

(a) Preemptive vs Non-Preemptive Scheduling

• Non-preemptive scheduling: once the CPU is given to a process, it keeps it until it terminates or voluntarily blocks (e.g., for I/O). The scheduler cannot forcibly remove it. Simpler, but a long process can monopolize the CPU and hurt response time (e.g., FCFS, non-preemptive SJF).
• Preemptive scheduling: the OS can forcibly take the CPU from a running process (on a timer interrupt or arrival of a higher-priority process) and give it to another. Better responsiveness and fairness, but incurs context-switch overhead and needs care with shared data (race conditions). Examples: Round Robin, SRTF, preemptive priority.

(b) Priority Inversion

Priority inversion occurs when a high-priority task is forced to wait for a low-priority task because the low-priority task holds a resource (lock) the high-priority task needs — effectively running at low priority.

Scenario: Tasks H (high), M (medium), L (low).

1. L acquires a lock on a shared resource.
2. H becomes ready, preempts L, then blocks trying to acquire the same lock (held by L).
3. M (which needs no lock) becomes ready and preempts L because M > L in priority.
4. Now L cannot run to release the lock, so H is indirectly blocked by M — a medium task delaying a high task. This caused the famous 1997 Mars Pathfinder resets.

Priority-Inheritance Protocol (solution): when a high-priority task H blocks on a lock held by a lower-priority task L, L temporarily inherits H's priority. With the raised priority, L is no longer preempted by medium task M, so L runs, finishes its critical section quickly, and releases the lock. L then reverts to its original priority and H proceeds. This bounds the blocking time to one critical section.