BE Computer Engineering (IOE, TU) Operating System (IOE, CT 656) Question Paper 2078 Nepal

(a) Gantt Charts

Preemptive Priority (lower number = higher priority). At each instant the ready process with the smallest priority number runs.

• $t=0$: only P1 runs.
• $t=1$: P2 (priority 1) arrives and preempts P1.
• P2 runs to completion (it has the highest priority) finishing at $t=5$.
• $t=5$: ready = P1(pr3, 7 left), P3(pr4), P4(pr2). P4 has the highest priority → runs 5 ms → done at 10.
• $t=10$: P1(pr3) vs P3(pr4) → P1 runs its remaining 7 ms → done at 17.
• $t=17$: P3 runs 9 ms → done at 26.

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

Round Robin (time quantum = 3 ms). Newly arrived processes join the tail of the ready queue before a preempted process.

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

Completion: P1=23, P2=16, P3=26, P4=21.

(b) Average Waiting Time and Turnaround Time

Turnaround = Completion − Arrival; Waiting = Turnaround − Burst.

Preemptive Priority (completions: P1=17, P2=5, P3=26, P4=10)

• Average TAT $= (17+4+24+7)/4 = 52/4 = 13$ ms
• Average WT $= (9+0+15+2)/4 = 26/4 = 6.5$ ms

Round Robin (completions: P1=23, P2=16, P3=26, P4=21)

• Average TAT $= (23+15+24+18)/4 = 80/4 = 20$ ms
• Average WT $= (15+11+15+13)/4 = 54/4 = 13.5$ ms

Comment: Preemptive Priority performs better for this workload (avg WT 6.5 vs 13.5 ms, avg TAT 13 vs 20 ms). Round Robin shares the CPU fairly but its frequent context switches and round-trips inflate waiting and turnaround times. Priority scheduling, however, risks starvation of low-priority processes (here P3), which RR avoids.

(a) The Critical-Section Problem

When several processes share data, each has a segment of code called the critical section (CS) in which it accesses or updates the shared data. The critical-section problem is to design a protocol the processes can use to cooperate, so that no two processes execute in their critical sections at the same time. Each process has the structure: entry section → critical section → exit section → remainder section.

Any correct solution must satisfy three requirements:

1. Mutual Exclusion — If a process is executing in its critical section, then no other process can be executing in its critical section at the same time.
2. Progress — If no process is in its CS and some processes wish to enter, then only those not in their remainder section participate in deciding who enters next, and this decision cannot be postponed indefinitely (no process outside the CS may block another from entering).
3. Bounded Waiting — There exists a bound on the number of times other processes are allowed to enter their critical sections after a process has made a request to enter and before that request is granted (prevents starvation).

(b) Bounded-Buffer Problem using Semaphores

A producer puts items into a buffer of $n$ slots and a consumer removes them. Three semaphores coordinate them:

• mutex — a binary semaphore (initial value 1) providing mutual exclusion on the buffer.
• empty — a counting semaphore (initial value n) counting the empty slots.
• full — a counting semaphore (initial value 0) counting the filled slots.

Producer process:

do {
    // produce an item in next_produced
    wait(empty);          // wait for an empty slot
    wait(mutex);          // enter critical section
        // add next_produced to the buffer
    signal(mutex);        // leave critical section
    signal(full);         // one more full slot
} while (true);

Consumer process:

do {
    wait(full);           // wait for a filled slot
    wait(mutex);          // enter critical section
        // remove an item from buffer into next_consumed
    signal(mutex);        // leave critical section
    signal(empty);        // one more empty slot
    // consume the item in next_consumed
} while (true);

empty/full block the producer when the buffer is full and the consumer when it is empty, while mutex guarantees that the buffer is updated by only one process at a time. Note that wait(empty)/wait(full) must precede wait(mutex) to avoid deadlock.

(a) Demand Paging and Page-Fault Handling

Demand paging is a virtual-memory technique in which a page is brought from secondary storage into main memory only when it is actually referenced (on demand), rather than loading the whole process at once. Each page-table entry carries a valid/invalid bit: valid means the page is in memory, invalid means it is not (it is on disk or illegal).

Steps to handle a page fault:

1. The CPU references a page; the MMU finds the page-table entry marked invalid → a page-fault trap to the OS.
2. The OS checks an internal table to decide whether the reference is legal (just not yet loaded) or illegal (terminate the process).
3. Find a free frame in physical memory (from the free-frame list). If none is free, run a page-replacement algorithm to free one (write it back to disk if dirty).
4. Schedule a disk read to bring the desired page from backing store into the chosen frame; the process is blocked meanwhile.
5. On I/O completion, update the page table (set the frame number and the valid bit) and the OS internal tables.
6. Restart the instruction that caused the fault; the reference now succeeds.

Diagram (in words): CPU → reference → page table (invalid) → trap to OS → check legality → locate page on backing store → bring page into a free frame → reset page table → restart the trapped instruction.

(b) Page Replacement — 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 → 15 page faults.

Optimal (replace the page not used for the longest time in future): 9 page faults.

LRU (replace the least-recently-used page): 12 page faults.

Belady's anomaly: Only FIFO suffers from it — increasing the number of frames can increase the number of page faults. This happens because FIFO replaces pages purely by load order, ignoring usage, so its set of pages held with more frames is not guaranteed to be a superset of the set held with fewer frames. Optimal and LRU are stack algorithms (the pages held with $n$ frames are always a subset of those held with $n+1$ frames), so they never exhibit Belady's anomaly.

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

(a) Need Matrix and Available Vector

Need = Max − Allocation.

Total allocated = (7, 2, 5). Available = Total − Allocated = (10−7, 5−2, 7−5) = (3, 3, 2).

(b) Safe-State Check (Banker's Algorithm)

Start with Work = Available = (3, 3, 2); all processes unfinished.

All processes finish, so the system is in a safe state, with safe sequence ⟨P1, P3, P0, P2, P4⟩ (other valid sequences also exist).

(c) Request (1, 0, 2) from P1

Apply the Resource-Request algorithm:

1. Request (1,0,2) ≤ Need(P1) = (1,2,2)? Yes.
2. Request (1,0,2) ≤ Available = (3,3,2)? Yes.
3. Tentatively allocate: Available = (3,3,2) − (1,0,2) = (2,3,0); Allocation(P1) = (3,0,2); Need(P1) = (0,2,0).

Run the safety check from Work = (2,3,0):

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

The resulting state is safe (sequence ⟨P1, P3, P0, P2, P4⟩), so the request can be granted immediately.

Process State Transition Diagram

A process passes through these states (arrows show transitions):

          admit            dispatch           exit
  NEW ----------> READY -----------> RUNNING --------> TERMINATED
                    ^                  |  |
        I/O / event |        timeout / |  | I/O or event wait
         completion |        interrupt |  v
                    +---------------- WAITING

• New — the process is being created.
• Ready — waiting to be assigned to the CPU.
• Running — instructions are being executed.
• Waiting (Blocked) — waiting for an event such as I/O completion.
• Terminated — the process has finished execution.

Key transitions: admit (New→Ready), dispatch (Ready→Running by the scheduler), timeout/interrupt (Running→Ready), I/O or event wait (Running→Waiting), I/O completion (Waiting→Ready), exit (Running→Terminated).

Process Control Block (PCB)

The PCB is the data structure the OS keeps for each process. It stores:

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

Why the PCB is needed during a context switch

When the CPU switches from one process to another, the OS must save the current process's state into its PCB (program counter, registers, etc.) and load the next process's state from its PCB. The PCB thus preserves the complete execution context so a suspended process can later resume exactly where it left off, making safe multiplexing of the CPU among processes possible.

Preemptive vs Non-Preemptive Scheduling

Scheduling Criteria

• CPU Utilization — the fraction of time the CPU is kept busy doing useful work; we want to maximize it (ideally 40–90% in real systems).
• Throughput — the number of processes completed per unit time; we want to maximize it.
• Turnaround Time — total time from submission of a process to its completion: $\text{TAT} = \text{Completion} - \text{Arrival}$; minimize.
• Waiting Time — total time a process spends in the ready queue: $\text{WT} = \text{TAT} - \text{Burst time}$; minimize.
• Response Time — time from submission until the first response (first time the process gets the CPU), important in interactive systems; minimize.

(a) Deadlock and the Four Necessary Conditions

A deadlock is a situation in which a set of processes are blocked because each process is holding a resource and waiting to acquire a resource held by another process in the set, so none can proceed.

Four conditions must hold simultaneously for a deadlock (Coffman conditions):

1. Mutual Exclusion — at least one resource is held in a non-sharable mode; only one process can use it at a time.
2. Hold and Wait — a process holding at least one resource is waiting to acquire additional resources held by other processes.
3. No Preemption — a resource cannot be forcibly taken away; it is released only voluntarily by the holding process.
4. Circular Wait — there exists a set $\{P_0, P_1, \dots, P_n\}$ such that $P_0$ waits for a resource held by $P_1$, $P_1$ for one held by $P_2$, …, $P_n$ for one held by $P_0$.

(b) Deadlock Prevention vs Deadlock Avoidance

Concept of Paging

Paging is a non-contiguous memory-management scheme. 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, and a per-process page table maps each page number to a frame number. A logical (virtual) address is split into a page number ($p$) and a page offset ($d$); $p$ indexes the page table to obtain the frame number $f$, and the physical address is formed as $(f \times \text{page size}) + d$. Paging eliminates external fragmentation.

Given Data and Address Sizes

• Logical address space = 16 pages → $16 = 2^4$, so page number = 4 bits.
• Page size = 1 KB = $2^{10}$ bytes → offset = 10 bits.
• Physical memory = 32 frames → $32 = 2^5$, so frame number = 5 bits.

Logical address size $= 4 + 10 = \mathbf{14\ bits}$ (logical space $= 16 \times 1\text{KB} = 16$ KB).

Physical address size $= 5 + 10 = \mathbf{15\ bits}$ (physical memory $= 32 \times 1\text{KB} = 32$ KB).

Address Translation

 Logical address (14 bits):  | page no. p (4 bits) | offset d (10 bits) |
                                      |
                                      v
                              page table[p] = frame no. f (5 bits)
                                      |
                                      v
 Physical address (15 bits): | frame no. f (5 bits) | offset d (10 bits) |

Example: suppose page 2 maps to frame 5 and the offset is 100. Physical address $= f \times 1024 + d = 5 \times 1024 + 100 = 5220$. The 10-bit offset is copied unchanged; only the page-number field is replaced by the frame number from the page table.

Fragmentation

Fragmentation is the wastage of memory that arises as memory is allocated to and freed by processes, leaving unusable space.

Contiguous Allocation Strategies

For a request of size $n$, the OS searches the list of free holes:

• First-fit — allocate the first hole that is large enough. Fast (least searching); leaves leftover holes spread throughout memory.
• Best-fit — allocate the smallest hole that is large enough (search whole list / keep it sorted). Minimizes leftover in that hole, but tends to create many tiny, unusable holes and is slower.
• Worst-fit — allocate the largest available hole. The idea is that the leftover is large enough to be useful, but in practice it wastes big holes quickly and performs worst on utilization.

Comparison

• First-fit and Best-fit are generally better than Worst-fit in storage utilization; First-fit is also faster.
• Best-fit produces the most external fragmentation in the form of many small leftover holes.
• Worst-fit leaves larger usable leftovers but exhausts large blocks fastest, giving the poorest overall utilization. All three suffer from external fragmentation, which can be reduced by compaction.

File Allocation Methods

Summary

• Contiguous gives the best access in both modes but the worst space management (fragmentation, growth problems).
• Linked solves fragmentation and growth but cripples direct access and adds reliability risk.
• Indexed supports both sequential and direct access well and avoids external fragmentation, at the cost of index-block space overhead.

Request queue (cylinders): 98, 183, 37, 122, 14, 124, 65, 67. Head starts at 53. (SCAN assumes a 0–199 cylinder disk; head first moves toward higher cylinders.)

FCFS (serve in arrival order)

Path: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

$$|53-98|+|98-183|+|183-37|+|37-122|+|122-14|+|14-124|+|124-65|+|65-67|$$ $$=45+85+146+85+108+110+59+2 = \mathbf{640\ cylinders}$$

SSTF (always serve the nearest request)

Path: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

$$12+2+30+23+84+24+2+59 = \mathbf{236\ cylinders}$$

SCAN (move up to the end, then reverse)

Sorted requests: 14, 37, 65, 67, 98, 122, 124, 183. Going up: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (disk end), then reverse: 199 → 37 → 14.

$$(199-53) + (199-14) = 146 + 185 = \mathbf{331\ cylinders}$$

Summary

SSTF gives the least movement here; FCFS the most. (If SCAN does not travel to cylinder 199 but reverses at the last request 183, the total would be $(183-53)+(183-14)=130+169=299$.)

Thrashing

Thrashing is a condition in which a process (or the system) spends more time paging (servicing page faults) than executing useful instructions, because it does not have enough frames to hold its actively used pages.

Cause — Degree of Multiprogramming vs CPU Utilization

The OS monitors CPU utilization; when it is low, it raises the degree of multiprogramming by admitting more processes. As more processes compete for a fixed amount of physical memory, each gets fewer frames. Eventually a process does not have enough frames for its working set, so it faults frequently. Faulting processes queue for the paging device, the ready queue empties, and CPU utilization drops further. The OS misreads this as needing even more processes, admits more, and the situation worsens sharply.

Graphically, CPU utilization rises with the degree of multiprogramming up to a point, then falls steeply once thrashing begins.

Controlling Thrashing — The Working-Set Model

The working set $WS(t)$ of a process is the set of pages referenced in the most recent $\Delta$ references (the working-set window). Its size $WSS_i$ approximates the locality the process currently needs.

• Compute the total demand $D = \sum WSS_i$ over all processes.
• If $D > m$ (total available frames), the system will thrash. The OS then suspends/swaps out one or more processes (lowering the degree of multiprogramming) and distributes their frames to the rest.
• A process is only allowed to run if enough frames are available to hold its entire working set, which keeps the page-fault rate low and prevents thrashing.

(An alternative practical control is the page-fault-frequency (PFF) scheme: keep each process's fault rate between an upper and lower bound by allocating/reclaiming frames accordingly.)

(Answer any two.)

(a) Inter-Process Communication (IPC) using Message Passing

Message passing lets processes communicate and synchronize without sharing an address space, using two primitives send(message) and receive(message). A communication link must exist between the processes. Implementation choices:

• Direct vs indirect — name the receiver/sender explicitly, or send through a shared mailbox/port.
• Synchronous (blocking) vs asynchronous (non-blocking) — blocking send waits until the message is received; non-blocking send continues immediately.
• Buffering — zero, bounded, or unbounded capacity queue.

It is well suited to distributed systems and avoids race conditions on shared memory, but has higher overhead (kernel involvement, copying).

(b) Multithreading Models

These describe how user threads map to kernel threads:

• Many-to-One — many user threads map to one kernel thread. Thread management is fast (user space) but a single blocking system call blocks the whole process, and it cannot run threads in parallel on multiple cores.
• One-to-One — each user thread maps to its own kernel thread. True parallelism and a blocking call blocks only that thread, but creating many kernel threads is costly (used by Linux, Windows).
• Many-to-Many — many user threads are multiplexed onto a smaller or equal number of kernel threads. Combines concurrency with parallelism and avoids the drawbacks of the other two.

(c) System Calls and Their Types

A system call is the programmatic interface through which a user program requests a service from the OS kernel, switching from user mode to kernel mode (usually via an API such as the Win32 API or POSIX). Major categories:

1. Process control — fork(), exit(), wait(), load, execute.
2. File management — open(), read(), write(), close(), create/delete.
3. Device management — request/release device, read/write.
4. Information maintenance — getpid(), get/set time, system data.
5. Communication — create/delete connection, send()/receive(), pipes.
6. Protection — set permissions, allow/deny access.