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

(a) Gantt charts

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

Preemptive SRTF — at each instant run the ready process with the smallest remaining burst:

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

• t=0: only P1 runs. t=1: P2 (rem 4) < P1 (rem 7) → P2 runs to completion at 5.
• t=5: ready P1(rem 7), P3(rem 9), P4(rem 5) → P4 runs to 10.
• t=10: P1(rem 7) < P3(rem 9) → P1 runs to 17, then P3 runs to 26.

Preemptive Priority (smaller number = higher priority): P2=1, P4=2, P1=3, P3=4.

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

• t=0: only P1. t=1: P2(pri 1) preempts P1 → runs to 5.
• t=5: highest priority ready is P4(pri 2) → runs to 10.
• t=10: P1(pri 3) over P3(pri 4) → P1 to 17, then P3 to 26.

For this particular workload the two schedules turn out identical.

(b) Average waiting and turnaround times

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

• Average Turnaround $= (17+4+24+7)/4 = 52/4 = 13\text{ ms}$
• Average Waiting $= (9+0+15+2)/4 = 26/4 = 6.5\text{ ms}$

Both algorithms give the same averages here, so neither performs better for this workload. (In general SRTF is optimal for minimizing average waiting time, while preemptive priority can cause starvation of low-priority processes.)

(c) Convoy effect

The convoy effect occurs in FCFS scheduling when one long CPU-bound process holds the CPU while many short processes wait behind it in the ready queue. The short processes (and any I/O devices they would keep busy) are forced to idle until the long job finishes, lowering CPU and device utilization and greatly increasing average waiting time.

(a) The critical-section problem

Each process has a segment of code, the critical section, in which it accesses shared data. The critical-section problem is to design a protocol that processes can use to cooperate so that no two processes execute in their critical sections at the same time. Any correct solution must satisfy three requirements:

1. Mutual exclusion — if a process is executing in its critical section, no other process may execute in its own 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 this decision cannot be postponed indefinitely.
3. Bounded waiting — there is a bound on the number of times other processes are allowed to enter their critical sections after a process has requested entry and before that request is granted (no starvation).

(b) Counting semaphore

A counting semaphore is an integer variable $S$ that, apart from initialization, is accessed only through two atomic operations wait() (P) and signal() (V). Its value can range over an unrestricted domain (used to control access to a resource with a finite number of instances).

wait(S):              signal(S):
    while S <= 0:          S = S + 1
        ; // busy wait
    S = S - 1

In practice the busy-wait version is replaced by a blocking version that puts the calling process to sleep on a queue when $S<0$ and wakes one up on signal().

Atomicity is guaranteed by executing wait() and signal() as a single, indivisible operation — e.g. by disabling interrupts on a uniprocessor, or using a hardware atomic instruction (TestAndSet / Compare-and-Swap) or a spinlock to guard the semaphore on a multiprocessor. This prevents two processes from modifying $S$ simultaneously.

(c) Bounded-Buffer (Producer–Consumer)

Semaphores: mutex = 1 (mutual exclusion on the buffer), empty = n (count of empty slots), full = 0 (count of filled slots).

Producer:                         Consumer:
while (true) {                    while (true) {
   item = produce_item();           wait(full);
   wait(empty);                     wait(mutex);
   wait(mutex);                     item = remove_from_buffer();
   add_item_to_buffer(item);        signal(mutex);
   signal(mutex);                   signal(empty);
   signal(full);                    consume_item(item);
}                                 }

Purpose of each semaphore:

• empty — counts free slots; blocks the producer when the buffer is full.
• full — counts occupied slots; blocks the consumer when the buffer is empty.
• mutex — a binary semaphore that enforces mutually exclusive access to the shared buffer so producer and consumer do not corrupt it.

Note the ordering: wait(empty)/wait(full) must be taken before wait(mutex); reversing them can deadlock.

(a) Need matrix and Available vector

$Need = Max - Allocation$:

Total allocated $= (7,2,5)$. With totals $(10,5,7)$:

$$Available = (10,5,7) - (7,2,5) = (3,\,3,\,2)$$

(b) Banker's safety algorithm

Start with $Work = (3,3,2)$, all Finish=false. A process can run if $Need_i \le Work$; on finishing, release its allocation: $Work = Work + Allocation_i$.

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

Safe sequence: $\langle P1, P3, P4, P0, P2 \rangle$ (other valid sequences exist, e.g. starting P1, P3, P0, ...).

(c) Request (1, 0, 2) by P1 — resource-request algorithm

1. Check $Request_{1} \le Need_{1}$: $(1,0,2) \le (1,2,2)$ ✔
2. Check $Request_{1} \le Available$: $(1,0,2) \le (3,3,2)$ ✔
3. Pretend to allocate:
   • $Available = (3,3,2)-(1,0,2) = (2,3,0)$
   • $Allocation_{1} = (2,0,0)+(1,0,2) = (3,0,2)$
   • $Need_{1} = (1,2,2)-(1,0,2) = (0,2,0)$
4. Run safety check from $Work=(2,3,0)$: P1 (Need 0,2,0) runs → (5,3,2); P3 → (7,4,3); P4 → (7,4,5); P0 → (7,5,5); P2 → (10,5,7). All finish.

The resulting state is safe, so the request can be granted immediately. A valid safe sequence is $\langle P1, P3, P4, P0, P2 \rangle$.

(a) Demand paging and page-fault handling

Demand paging loads a page into memory only when it is actually referenced (on demand), rather than loading the whole process at start. Each page-table entry has a valid/invalid bit: valid means the page is in memory, invalid means it is on the backing store (disk) — a reference to an invalid page causes a page fault trap.

Steps to service a page fault (described in words, since a figure cannot be drawn here):

1. The CPU references a page; the MMU finds the valid/invalid bit set to invalid and raises a page-fault trap to the OS.
2. The OS checks an internal table to decide whether the reference is legal (the page belongs to the process) or illegal (→ terminate the process).
3. If legal but not in memory, the OS finds a free frame (from the free-frame list).
4. It schedules a disk read to bring the required page from the backing store into the free frame.
5. When the disk I/O completes, the OS updates the page table (sets the frame number and the valid bit) and the internal tables.
6. It restarts the instruction that was interrupted; the reference now succeeds from memory.

If no free frame exists, a page-replacement algorithm selects a victim page to evict first (writing it back if dirty).

(b) Page faults for the reference string (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 evicts the page that has been in memory longest → 15 faults.
• Optimal evicts the page that will not be used for the longest time in the future → 9 faults (the theoretical minimum).
• LRU evicts the least-recently-used page → 12 faults.

So Optimal performs best (fewest faults) and FIFO worst.

(c) Belady's anomaly

Belady's anomaly is the counter-intuitive situation in which increasing the number of frames increases the number of page faults for some reference strings. It can occur with FIFO replacement. Stack-based algorithms such as LRU and Optimal never suffer from it, because the set of pages held with $m$ frames is always a subset of those held with $m+1$ frames.

(a) Process vs. Thread

Two benefits of multithreading:

1. Responsiveness — one thread can keep serving the user while another performs a long/blocking operation.
2. Resource sharing & economy — threads share memory and resources, so creation and context switching are cheaper than for processes; multithreading also enables parallelism on multicore CPUs (and better resource utilization).

(b) Process state transition diagram

              admitted        dispatch          exit
   [New] ----------------> [Ready] ----------> [Running] --------> [Terminated]
                            ^   ^                 |
          I/O or event      |   | interrupt       | I/O or event wait
          completion        |   |                 v
                            [Waiting] <-----------/

• New — the process is being created.
• Ready — it is loaded in memory and waiting to be assigned to the CPU.
• Running — instructions are being executed on the CPU.
• Waiting (Blocked) — the process is waiting for an event (e.g. I/O completion).
• Terminated — the process has finished execution.

Transitions: admitted (New→Ready); dispatch/scheduler dispatch (Ready→Running); interrupt/time-out (Running→Ready); I/O or event wait (Running→Waiting); I/O or event completion (Waiting→Ready); exit (Running→Terminated).

A deadlock can arise only if all four necessary (Coffman) conditions hold simultaneously. Deadlock prevention works by ensuring at least one of them can never hold.

All four must hold for a deadlock; breaking any single one prevents deadlock.

(a) Internal vs. External fragmentation

• Internal fragmentation — memory is allocated in fixed-size blocks/pages; the block given to a process is slightly larger than what it needs, and the unused space inside the allocated block is wasted (e.g. a 212 KB process placed in a 256 KB frame wastes 44 KB). It cannot be used by any other process until the block is freed.
• External fragmentation — enough total free memory exists to satisfy a request, but it is split into many non-contiguous small holes, so no single hole is large enough. It is the wasted space between allocated blocks (typical of variable-partition / contiguous allocation). It can be reduced by compaction.

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

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

First-Fit (first hole that is large enough):

Best-Fit (smallest adequate hole):

Worst-Fit (largest hole):

Conclusion: Only Best-Fit successfully allocates all four processes; First-Fit and Worst-Fit both fail to place the 426 KB process. Hence Best-Fit makes the most efficient use of memory for this workload.

(a) File allocation methods

(b) File Control Block (FCB)

A File Control Block is a per-file data structure (e.g. an inode) maintained by the file system that stores all the metadata needed to manage and locate the file.

Two pieces of information it stores (any two): file name/identifier, file size, file permissions / access-control list, owner and group IDs, timestamps (created/modified/accessed), and the pointers to the data blocks (disk addresses) on disk.

Head starts at cylinder 53; queue: 98, 183, 37, 122, 14, 124, 65, 67.

FCFS (serve in arrival order)

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

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

SSTF (always go to nearest pending request)

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

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

SCAN (move toward larger cylinders first, up to 199, then reverse)

Order: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 37 → 14

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

Comparison

SSTF gives the least total head movement (236 cylinders) for this request set. (Note: SSTF can cause starvation, whereas SCAN guarantees fairer service.)

(a) Preemptive vs. Non-preemptive scheduling

• Non-preemptive scheduling — once the CPU is given to a process, it keeps the CPU until it terminates or voluntarily blocks (e.g. for I/O). The scheduler cannot forcibly take the CPU away. Example: FCFS (also non-preemptive SJF). Simpler, but a long job can hold up others.
• Preemptive scheduling — the CPU can be taken away from a running process before it finishes, e.g. on a timer interrupt or when a higher-priority/shorter process arrives. Example: Round Robin (also SRTF, preemptive priority). More responsive, but incurs context-switch overhead and needs synchronization for shared data.

(b) Race condition

A race condition occurs when two or more processes access shared data concurrently and the final result depends on the order in which their operations are interleaved. The outcome is non-deterministic and usually incorrect.

Example: Two processes increment a shared variable count = 5. The statement count = count + 1 compiles to three steps: read, add, write.

Process A            Process B
read count (5)
                     read count (5)
add 1 -> 6
                     add 1 -> 6
write count = 6
                     write count = 6

Both increments execute, so count should be 7, but because the operations interleave on the unprotected shared variable the final value is 6 — one update is lost. Protecting the update with mutual exclusion (a lock or semaphore around the critical section) eliminates the race.

(a) Thrashing and the working-set model

Thrashing is a state in which a process (or the whole system) spends more time paging (servicing page faults) than executing useful work. It happens when processes do not have enough frames to hold their actively used pages: each one quickly faults, steals a frame from another process, which then faults in turn. CPU utilization collapses while paging-device utilization climbs to ~100%. A naive scheduler, seeing low CPU use, admits more processes, which worsens the situation.

Working-set model: The working set $W(t, \Delta)$ of a process is the set of pages it has referenced in the most recent $\Delta$ references (the working-set window). The OS estimates each process's working-set size and ensures it is allocated enough frames to hold its entire working set. The total demand is $D = \sum WSS_i$. If $D >$ available frames, the OS suspends (swaps out) a process to free frames, keeping the multiprogramming degree at a level where every running process has its working set resident — thereby preventing thrashing.

(b) Page number vs. page offset bits

Page size $= 4\text{ KB} = 2^{12}$ bytes, so the page offset uses 12 bits.

Logical address $= 32$ bits, so the page number uses $32 - 12 = \mathbf{20}$ bits (giving $2^{20}$ pages).

$$\underbrace{20\text{ bits}}_{\text{page number}} \;\Big|\; \underbrace{12\text{ bits}}_{\text{offset}}$$

(Answer any two — all three are given here.)

(a) System calls and their categories

A system call is the programming interface through which a user-mode program requests a service from the operating-system kernel (e.g. via a software interrupt/trap that switches to kernel mode). It is the boundary between an application and the OS. Major categories:

1. Process control — fork, exec, exit, wait.
2. File management — open, read, write, close, create, delete.
3. Device management — request/release device, read/write device.
4. Information maintenance — getpid, get/set time, system data.
5. Communication — pipe, send/receive messages, shared memory.
6. Protection — set permissions, chmod.

(b) RAID levels 0, 1 and 5

• RAID 0 (striping): Data is striped across disks for high performance and full capacity, but no redundancy — a single disk failure loses all data.
• RAID 1 (mirroring): Every block is duplicated on a second disk. Excellent reliability and read performance; storage cost is doubled (50% usable capacity).
• RAID 5 (striping with distributed parity): Data and parity blocks are striped across all $N$ disks; it tolerates one disk failure (rebuild from parity). Usable capacity is $(N-1)/N$; writes incur parity-update overhead. A good balance of cost, performance and reliability.

(c) Direct Memory Access (DMA)

DMA is a technique that lets an I/O device controller transfer a whole block of data directly between the device and main memory without involving the CPU for each byte/word. The CPU sets up the transfer (source/destination address and count) in the DMA controller and continues other work; the DMA controller moves the data and raises a single interrupt when the whole block is done. This frees the CPU from byte-by-byte programmed I/O, greatly improving throughput for high-speed devices (disks, network cards). During the transfer the DMA controller and CPU share the memory bus (cycle stealing).