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

Consider the following set of processes with their arrival times, CPU burst times (in milliseconds) and priorities (a smaller number denotes a higher priority):

(a) Draw the Gantt charts for scheduling these processes using Preemptive Shortest Remaining Time First (SRTF) and Preemptive Priority scheduling. (8 marks)

(b) Compute the average waiting time and average turnaround time for each of the two algorithms and state which algorithm performs better for this workload. (4 marks)

(c) Explain what the convoy effect is and how it can degrade the performance of FCFS scheduling. (2 marks)

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

(b) Define a counting semaphore and give the definitions of the wait() and signal() operations, explaining how they are made atomic. (4 marks)

(c) The classical Bounded-Buffer (Producer–Consumer) problem uses a buffer of n slots. Write the synchronized pseudo-code for the producer and consumer processes using the semaphores mutex, empty and full, and explain the purpose of each semaphore. (6 marks)

A system has five processes (P0–P4) and three resource types A, B and C with total instances A = 10, B = 5, C = 7. At time T0 the system state is:

(a) Compute the Need matrix and the current Available vector. (3 marks)

(b) Using the Banker's algorithm, determine whether the system is in a safe state. If it is, give a safe sequence. (7 marks)

(c) If a request (1, 0, 2) arrives from P1, can it be granted immediately? Justify your answer using the resource-request algorithm. (4 marks)

(a) Explain the concept of demand paging and describe, with the help of a diagram, the sequence of steps the operating system takes to service a page fault. (6 marks)

(b) Given the page reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 and a memory of 3 frames, compute the number of page faults for the FIFO, Optimal and LRU page-replacement algorithms. (6 marks)

(c) What is Belady's anomaly? Which of the above algorithms can suffer from it? (2 marks)

(a) Differentiate between a process and a thread, and state two benefits of multithreading. (4 marks)

(b) Draw the process state transition diagram and briefly explain the meaning of each state and transition. (3 marks)

Explain the four necessary conditions for a deadlock to occur. For each condition, briefly describe one strategy by which it can be prevented.

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

(b) Given free memory partitions of sizes 100 KB, 500 KB, 200 KB, 300 KB and 600 KB (in order), show how the First-Fit, Best-Fit and Worst-Fit strategies would allocate processes of 212 KB, 417 KB, 112 KB and 426 KB (in order). Which strategy makes the most efficient use of memory here? (4 marks)

(a) Compare the contiguous, linked and indexed file allocation methods, stating one advantage and one disadvantage of each. (4 marks)

(b) What is the purpose of a File Control Block (FCB)? List any two pieces of information it stores. (2 marks)

A disk has 200 cylinders numbered 0 to 199. The disk head is currently at cylinder 53 and the pending request queue (in arrival order) is:

98, 183, 37, 122, 14, 124, 65, 67

Compute the total head movement for the FCFS, SSTF and SCAN disk-scheduling algorithms (assume SCAN moves toward larger cylinder numbers first). Which algorithm gives the least head movement?

(a) Distinguish between preemptive and non-preemptive scheduling, giving one example algorithm of each. (3 marks)

(b) What is a race condition? Explain with a simple example involving two processes updating a shared variable. (3 marks)

(a) Explain the concept of thrashing in a virtual-memory system and describe how the working-set model helps to control it. (4 marks)

(b) A logical address space has a page size of 4 KB and a logical address is 32 bits wide. How many bits are used for the page number and how many for the page offset? (2 marks)

Write short notes on any two of the following:

(a) System calls and their categories (b) RAID levels 0, 1 and 5 (c) Direct Memory Access (DMA)