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

Consider the following set of processes arriving in a single-processor system, with the length of the CPU burst given in milliseconds:

(a) Draw the Gantt charts illustrating the execution of these processes using Preemptive Priority scheduling (lower number = higher priority) and Round Robin scheduling (time quantum = 3 ms). [6]

(b) Compute the average waiting time and average turnaround time for each of the two algorithms, and comment on which performs better for this workload. [6]

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

(b) Explain how semaphores can be used to solve the bounded-buffer (producer-consumer) problem. Write the structure of the producer and consumer processes using the semaphores mutex, full, and empty. [8]

(a) What is demand paging? Explain the steps taken by the operating system to handle a page fault with the help of a diagram. [6]

(b) Consider the page reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 for a memory with three frames. Determine the number of page faults using FIFO, Optimal, and LRU page replacement algorithms. Which algorithm suffers from Belady's anomaly and why? [6]

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

(a) Compute the Need matrix and the Available vector. [3]

(b) Using the Banker's algorithm, determine whether the system is in a safe state and give a safe sequence if one exists. [6]

(c) If a request (1, 0, 2) arrives from process P1, can it be granted immediately? Justify your answer. [3]

Draw and explain the process state transition diagram. Describe the contents of a Process Control Block (PCB) and state why it is needed during a context switch.

Differentiate between preemptive and non-preemptive scheduling. Explain the meaning of the scheduling criteria: CPU utilization, throughput, turnaround time, waiting time, and response time.

(a) Explain what a deadlock is and list the four necessary conditions that must hold simultaneously for a deadlock to occur. [3]

(b) Differentiate between deadlock prevention and deadlock avoidance. [3]

Explain the concept of paging. Given a logical address space of 16 pages with a page size of 1 KB mapped into a physical memory of 32 frames, determine the number of bits required for the logical address and the physical address, and show how a logical address is translated into a physical address using the page table.

What is fragmentation? Distinguish between internal and external fragmentation. Explain how the First-fit, Best-fit, and Worst-fit contiguous memory allocation strategies work and compare their effect on fragmentation.

Compare the contiguous, linked, and indexed file allocation methods. For each method, discuss its support for sequential and direct (random) access and its disadvantages.

A disk queue with requests for I/O to blocks on cylinders arrives in the order: 98, 183, 37, 122, 14, 124, 65, 67. The disk head is currently at cylinder 53. Calculate the total head movement (in cylinders) required to service these requests using the FCFS, SSTF, and SCAN disk scheduling algorithms (assume the head is moving toward the higher numbered cylinders for SCAN).

What is thrashing? Explain its cause with reference to the degree of multiprogramming and CPU utilization. Describe how the working-set model can be used to control thrashing.

Write short notes on any TWO of the following: (a) Inter-process communication (IPC) using message passing (b) Multithreading models (many-to-one, one-to-one, many-to-many) (c) System calls and their types