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

Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):

(a) Draw the Gantt charts and compute the average waiting time and average turnaround time for Shortest Remaining Time First (SRTF) and Round Robin (RR with time quantum = 3 ms) scheduling.

(b) Compare the two scheduling algorithms based on your results, and explain the problem of starvation and convoy effect with reference to CPU scheduling.

(a) Consider a system with five processes P0 through P4 and three resource types A, B and C. Resource type A has 10 instances, B has 5 instances, and C has 7 instances. At time T0 the snapshot is:

Using the Banker's algorithm, determine whether the system is in a safe state. If so, give a safe sequence.

(b) Explain the four necessary conditions for deadlock and describe how the deadlock prevention strategy attacks each of them.

(a) A demand-paged system uses a reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with three frames. Determine the number of page faults using FIFO, Optimal (OPT), and LRU page-replacement algorithms. Which algorithm performs best for this string?

(b) Explain Belady's anomaly with a suitable example, and discuss why the LRU and Optimal algorithms do not suffer from it. Define thrashing and explain how the working-set model helps to control it.

(a) State the critical-section problem and list the three requirements (mutual exclusion, progress, and bounded waiting) that any solution must satisfy.

(b) Define the classical Producer–Consumer (bounded buffer) problem and present a complete solution using counting and binary semaphores. Clearly identify the role of each semaphore and explain how your solution prevents buffer overflow, buffer underflow, and race conditions.

Draw and explain the process state transition diagram. Describe the contents of a Process Control Block (PCB) and explain what information is saved and restored during a context switch.

Suppose a disk has 200 cylinders (0–199) and the disk head is currently at cylinder 53. The pending requests in the queue (in arrival order) are: 98, 183, 37, 122, 14, 124, 65, 67. Compute the total head movement for FCFS, SSTF, and SCAN disk-scheduling algorithms (assume the head moves toward higher cylinder numbers for SCAN).

Compare contiguous, linked, and indexed file-allocation methods in terms of external fragmentation, direct (random) access support, and storage overhead. Which method is used by the UNIX i-node structure and why?

(a) Explain the difference between internal and external fragmentation.

(b) Given a memory with free partition sizes of 100 KB, 500 KB, 200 KB, 300 KB and 600 KB (in order), show how the First-Fit, Best-Fit, and Worst-Fit algorithms would allocate processes of sizes 212 KB, 417 KB, 112 KB and 426 KB (in order).

Explain paging as a memory-management scheme. With a neat diagram, describe how a logical address is translated into a physical address using the page table, and explain the role of the Translation Look-aside Buffer (TLB) in reducing the effective memory-access time.

Differentiate between deadlock avoidance and deadlock detection. Explain how a resource-allocation graph with single-instance resources can be used to detect a deadlock, using a suitable example.

(a) Distinguish between programmed I/O, interrupt-driven I/O, and DMA (Direct Memory Access).

(b) Explain the difference between a system call and an ordinary function call, and describe how the transition from user mode to kernel mode takes place during a system call.

(a) Explain the difference between preemptive and non-preemptive scheduling.

(b) What is priority inversion? Describe a scenario where it occurs and explain how the priority-inheritance protocol solves the problem.