5. Operating Systems — Computer Science | CSS Solved Past Papers

FPSC CSS Computer Science past papers (2016–2026) — 56 questions: 11 MCQs, 45 subjective parts. Newest first.

Part A — Subjective Questions

2025 · Paper-II · Q5(a) (10 marks)

Question

Consider the following pseudo code for producer and consumer: // producer do{ //produce an item //place in buffer }while(true); // consumer do{ // remove item from buffer // consumes item }while(true); (i) What is race condition? (2) (ii) Is there any possibility of the race condition if two threads named producer and consumer simultaneously execute the above functions? Provide the reasoning in two-three sentences. (2) (iii) Add the necessary synchronization in the above functions, you may use semaphores or mutex. You may provide just pseudo code or exact C/C++ code. (3) (iv) Consider a process that uses a user level threading library to spawn 10 user level threads. The library maps these 10 threads on to 2 kernel threads. The process is executing on a 8-core system. What is the maximum number of threads of a process that can be executing in parallel? (3)

Solution

(i) A race condition occurs when two or more processes/threads access and manipulate shared data concurrently, and the final outcome depends on the particular (unpredictable) timing/interleaving order in which their instructions execute, potentially producing incorrect or inconsistent results.

(ii) Yes, a race condition is possible. Both the producer and consumer access the same shared buffer without any mutual-exclusion or synchronization mechanism; if, for example, both check/update a shared buffer count or index at overlapping times, updates can be lost or the consumer could read/remove from an empty buffer (or the producer overwrite an unread slot), because neither thread's access to the shared buffer is protected.

(iii) Using a mutex for mutual exclusion plus counting semaphores to track empty/full slots (classic bounded-buffer solution):

semaphore mutex = 1;      // ensures exclusive access to the buffer
semaphore empty = N;      // N = buffer size, counts empty slots
semaphore full  = 0;      // counts filled slots

// producer
do {
    produce an item
    wait(empty);           // wait for a free slot
    wait(mutex);            // enter critical section
    place item in buffer
    signal(mutex);          // leave critical section
    signal(full);           // one more filled slot
} while(true);

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

(iv) Maximum parallel threads = 2. Even though the 8-core system has enough hardware cores to run up to 8 threads simultaneously, the many-to-few (M:N, here 10:2) user-level threading model maps this process's 10 user threads onto only 2 kernel threads; the OS scheduler can only schedule kernel threads onto cores, so at most 2 of this process's kernel threads can be running at any instant — limiting true parallel execution of this process's threads to 2, regardless of the number of free cores.

2025 · Paper-II · Q5(b) (10 marks)

Question

Consider a multi-level memory management scheme with the following format for virtual addresses: Virtual Page # (10 bits) | Virtual Page # (10 bits) | Offset (12 bits) Virtual addresses are translated into physical addresses of the following form: Physical Page # (20 bits) | Offset (12 bits) Page table entries (PTE) are 32 bits and contain the 20-bit physical page number and OS bookkeeping bits (e.g., valid, dirty, used, etc.). (i) How big is a page? (1) (ii) What is the maximum amount of memory (in bytes) in a single virtual address space? Explain your answer. (3) (iii) What is the maximum amount of physical memory (in bytes) that this memory management scheme supports? Explain your answer. (3) (iv) Sketch the format of the page table for the multi-level virtual memory management scheme. Illustrate the process of resolving an address as well as possible. Assume there is no TLB or cache. (3)

Solution

(i) Page size = 2^(offset bits) = 2^12 = 4096 bytes = 4 KB.

(ii) The virtual address is 10+10+12 = 32 bits wide, so the maximum virtual address space = 2^32 bytes = 4 GB (4,294,967,296 bytes). This is because a 32-bit address can uniquely address 2^32 distinct byte locations.

(iii) The physical address is 20 (physical page #) + 12 (offset) = 32 bits wide, so the maximum physical memory this scheme supports = 2^32 bytes = 4 GB as well, since a 32-bit physical address likewise addresses 2^32 distinct bytes.

(iv) Two-level page table structure: the top 10 bits of the virtual address index into an Outer Page Table (a single table with 2^10 = 1024 entries), where each entry is a 32-bit PTE pointing to the base address of a second-level (inner) Page Table. The next 10 bits index into that chosen inner page table (also 1024 entries of 32-bit PTEs each), where each entry contains a 20-bit physical page number plus valid/dirty/used control bits. The final 12 bits (offset) are not translated — they are appended directly to the physical page number extracted from the inner PTE. Address resolution steps (no TLB/cache): (1) take bits 31-22 (first 10 bits) of the virtual address, use it as an index into the outer page table (held in a register, e.g., a page-table base register) to get the base address of the correct inner page table; (2) take bits 21-12 (next 10 bits), use it as an index into that inner page table to fetch the 32-bit PTE, check the valid bit, and extract the 20-bit physical page number; (3) concatenate this physical page number with the 12-bit offset (bits 11-0) unchanged to form the final 32-bit physical address; (4) access physical memory at that address. This requires two sequential memory accesses to the page tables before the actual data access, which is why a TLB is normally used in practice to avoid this overhead.

2024 · Paper-I · Q2(b) (6 marks)

Question

Discuss the difference between a computer virus a trojan and a worm?

Solution

A virus is malicious code that attaches itself to a legitimate host program or file; it requires a user action (running/opening the infected file) to activate and spread, and it replicates by infecting other files/programs on the same or connected systems.

A worm is a standalone malicious program that does not need to attach to a host file; it self-replicates and spreads automatically across networks by exploiting vulnerabilities, without requiring any user action, often consuming bandwidth/resources rapidly as it propagates.

A Trojan (Trojan horse) disguises itself as legitimate or useful software to trick a user into installing it; unlike viruses and worms, it does NOT self-replicate or clone itself - instead, once installed, it performs hidden malicious actions such as opening a backdoor, stealing data, or granting remote access to an attacker.

2024 · Paper-II · Q5(a) (7 marks)

Question

Compare the file systems of UNIX and Windows in terms of structure, permissions, and file organization. How do these file systems cater to the needs of diverse computing environments?

Solution

Structure: UNIX-family file systems (e.g., ext4) use a single hierarchical tree rooted at "/", with all storage devices mounted as subdirectories within this one tree. Windows (NTFS) uses multiple independent root volumes, each identified by a drive letter (C:, D:, ...), giving a separate tree per volume.

Permissions: UNIX uses a simple owner/group/other model with read-write-execute (rwx) permission bits per file, well suited to multi-user server environments where broad classes of users need distinguishable access. NTFS uses Access Control Lists (ACLs), allowing fine-grained, per-user and per-group permissions on each file/folder, offering more flexibility for complex enterprise/desktop security needs, at the cost of more administrative complexity.

File organization: UNIX file names are case-sensitive and files are identified internally via inodes (data structures holding metadata and block pointers); NTFS file names are case-insensitive (but case-preserving) and uses a Master File Table (MFT) to track file metadata and locations. Both support journaling for crash recovery/reliability. UNIX's simpler, uniform model suits portable, scriptable, multi-user server environments, while NTFS's richer ACL-based model suits Windows' typical desktop/enterprise environments needing granular per-user security control.

2024 · Paper-II · Q5(b) (7 marks)

Question

How does an operating system mediate between application programs and the computer hardware? Discuss the key roles and responsibilities of an operating system in managing resources.

Solution

The operating system provides an abstraction layer between applications and the underlying hardware through system calls and APIs, so that applications interact with simple, standardized services rather than manipulating hardware registers/devices directly - this abstraction also enforces protection, preventing one application from corrupting hardware state or another application's resources.

Key OS responsibilities in managing resources:

Process management: creating, scheduling, and terminating processes, allocating CPU time fairly among them.
Memory management: allocating/deallocating memory to processes, providing virtual memory and protection so processes cannot access each other's memory.
Device/I/O management: providing device drivers and a uniform interface for interacting with peripherals (disks, network cards, printers).
File system management: organizing, storing, and retrieving data on persistent storage through a logical file/directory abstraction.
Security and access control: authenticating users and enforcing permissions on resources.
User interface: providing a shell or graphical interface through which users interact with the system.

2024 · Paper-II · Q5(c) (6 marks)

Question

What is process management in the context of operating systems? How does the operating system handle processes, and what role does it play in multitasking?

Solution

Process management is the set of OS functions responsible for creating, scheduling, synchronizing, and terminating processes (running instances of programs), as well as tracking each process's state and resources throughout its lifetime.

The OS maintains a Process Control Block (PCB) for each process, recording its current state (new, ready, running, waiting, terminated), program counter, CPU register values, memory allocation information, and open file/resource handles. When switching from one process to another (a context switch), the OS saves the current process's state into its PCB and loads the next scheduled process's state from its own PCB.

In multitasking, the OS's scheduler rapidly switches the CPU between multiple ready processes (using algorithms like round-robin, priority scheduling, or multilevel feedback queues), giving each one a small slice of CPU time in turn. Because these switches happen very quickly, users perceive multiple programs as running simultaneously, even on a machine with only one or a few physical CPU cores - process management is what makes this illusion of concurrent execution possible while keeping each process's data safely isolated from the others.

2023 · Paper-II · Q4(b) (8 marks)

Question

Consider a program that access a single I/O device and compare un-buffered I/O to the use of a buffer. Show that the use of buffer can reduce the running time by at most a factor of two.

Solution

Let C be the time the program spends computing per unit of data, and I be the time spent performing I/O per unit of data, over n units of data.

Without buffering, computation and I/O must happen strictly sequentially for each unit (the program must wait for I/O to finish before computing on that data, and vice versa), so the total running time is: T_unbuffered = n(C + I).

With (double) buffering, I/O for one unit of data can be overlapped with computation on a different unit, so the CPU and the I/O device can work concurrently. In the best case, the total time is bounded below by whichever of the two (computation or I/O) takes longer overall, since one of them is always the bottleneck that cannot be hidden by overlap: T_buffered >= n * max(C, I).

Since max(C, I) >= (C + I) / 2 always holds (the maximum of two non-negative numbers is at least their average), we get: T_buffered >= n(C+I)/2 = T_unbuffered / 2.

Therefore, buffering can reduce the running time by AT MOST a factor of two - this bound is achieved exactly when C = I (computation and I/O take equal time), in which case T_buffered = n*C = T_unbuffered/2, but buffering can never do better than halving the total time, since one of the two activities (compute or I/O) must still occur n times regardless of overlap.

2023 · Paper-II · Q5(a) (10 marks)

Question

An I/O-bound program is one that, if run alone, would spend more time waiting for I/O than using the processor. A processor-bound program is the opposite. Suppose a short term scheduling algorithm favors those programs that have used little processor time in the recent past. Explain why this algorithm favors I/O bound programs and yet does not permanently deny processor time to processor-bound programs?

Solution

An I/O-bound program, by definition, uses the CPU only in short bursts between its (longer) I/O waits. Because it spends little time actually running on the CPU, its "recent processor usage" measure stays low, so this scheduling algorithm - which favors low recent CPU usage - naturally gives it high priority whenever it becomes ready. This is beneficial for overall system performance because it lets the I/O-bound program quickly issue its next I/O request, keeping I/O devices busy and improving overall throughput and interactive responsiveness.

The algorithm does not permanently starve processor-bound programs because the "recent processor usage" measure is typically computed with some form of decay/aging over time (e.g., recent usage counters are periodically halved or reduced) rather than being a permanent penalty. This means that once a processor-bound program has been waiting without running for some time, its recorded recent usage naturally decreases, and its priority correspondingly rises again until it eventually gets scheduled. The scheme is therefore self-correcting: it favors I/O-bound behavior in general, but no program's priority is permanently fixed, so starvation is avoided over the long run.

2022 · Paper-II · Q2(a) (10 marks)

Question

The following processes are being scheduled using a preemptive, round robin scheduling algorithm. Each process is assigned a numerical priority, with a higher number indicating a higher relative priority. In addition to the processes listed below, the system also has an idle task (which consumes no CPU resources and is identified as Pidle). This task has priority 0 and is scheduled whenever the system has no other available processes to run. The length of a time quantum is 10 units. If a process is preempted by a higher-priority process, the preempted process is placed at the end of the queue. Process Priority Burst Arrival P1 40 20 0 P2 30 25 25 P3 30 25 30 P4 35 15 60 P5 5 10 100 P6 10 10 105 Show the scheduling order of the processes using a Gantt chart. What is the turnaround time and waiting time for each process?

Solution

Rule used: strict priority-preemptive scheduling; among processes tied at the same priority, CPU time is shared round-robin with quantum = 10 (a process is requeued at the back of its priority level when its quantum expires or it is preempted by a higher-priority arrival).

Step-by-step trace:

t=0-20: P1 (pri 40, only ready process) runs to completion. P1 finishes at 20.
t=20-25: nobody ready (P2 arrives at 25) -> idle task runs.
t=25-35: P2 (pri 30) runs; at t=30 P3 (pri 30, same priority - no preemption) arrives and joins the queue. P2's quantum expires at 35 (used 10, remaining 15) and it is placed behind P3.
t=35-45: P3 (pri 30) runs its quantum (10), remaining 15, requeued behind P2.
t=45-55: P2 runs its quantum (10 of its remaining 15), remaining 5, requeued behind P3.
t=55-60: P3 begins its quantum, but P4 (pri 35, higher) arrives at 60 and preempts it after 5 units; P3 remaining = 15-5 = 10, requeued at back of the priority-30 queue (behind P2).
t=60-75: P4 (pri 35, highest ready, no higher arrivals) runs to completion (burst 15). P4 finishes at 75.
t=75-80: back to priority-30 queue: P2 (remaining 5) runs to completion, finishes at 80.
t=80-90: P3 (remaining 10) runs to completion, finishes at 90.
t=90-100: nobody ready (P5 arrives at 100) -> idle task runs.
t=100-105: P5 (pri 5) runs; P6 (pri 10, higher) arrives at 105 and preempts P5 after 5 units; P5 remaining = 10-5 = 5.
t=105-115: P6 (pri 10, no higher arrivals, alone) runs to completion (burst 10). P6 finishes at 115.
t=115-120: P5 resumes with its remaining 5 units and finishes at 120.

Gantt chart: | P1 | idle | P2 | P3 | P2 | P3 | P4 | P2 | P3 | idle | P5 | P6 | P5 | 0 20 25 35 45 55 60 75 80 90 100 105 115 120

Turnaround time (TAT = completion - arrival) and waiting time (WT = TAT - burst):

P1: CT=20, TAT=20-0=20, WT=20-20=0
P2: CT=80, TAT=80-25=55, WT=55-25=30
P3: CT=90, TAT=90-30=60, WT=60-25=35
P4: CT=75, TAT=75-60=15, WT=15-15=0
P5: CT=120, TAT=120-100=20, WT=20-10=10
P6: CT=115, TAT=115-105=10, WT=10-10=0

2022 · Paper-II · Q2(b) (6 marks)

Question

Suppose the disk head is initially located at track 20, set to move in order of increasing tracks. Assume a disk with 100 tracks and that the disk request queue has random requests in it. The requested tracks, in the order received by the disk scheduler, are 18, 25, 73, 46, 9, 92. Using C-SCAN algorithm, find the performance in terms of average seek time.

Solution

C-SCAN moves the head in one direction, servicing requests as it goes, all the way to the end of the disk (track 99 here, since tracks are numbered 0-99), then jumps back to track 0 without servicing any request on the return jump, and continues moving upward servicing the remaining requests.

Head starts at 20, moving toward increasing tracks. Requests >= 20 in increasing order: 25, 46, 73, 92. Then jump to the end of the disk (track 99), then wrap to track 0, then service requests < 20 in increasing order: 9, 18.

Sequence of head movement: 20 -> 25 -> 46 -> 73 -> 92 -> 99 -> 0 -> 9 -> 18

Movement per hop: |25-20|=5, |46-25|=21, |73-46|=27, |92-73|=19, |99-92|=7, |0-99|=99 (the wrap jump), |9-0|=9, |18-9|=9.

Total head movement = 5+21+27+19+7+99+9+9 = 196 tracks.

Number of requests serviced = 6 (18,25,73,46,9,92).

Average seek time (in tracks moved per request) = 196 / 6 ≈ 32.67 tracks per request. If a per-track seek time is given (e.g., x ms/track), multiply 32.67 by x to get the average seek time in milliseconds.

2022 · Paper-II · Q2(c) (4 marks)

Question

What design and management issues are raised by the existence of concurrency?

Solution

Concurrency (multiple processes/threads making progress at overlapping times) raises several design and management issues:

Mutual exclusion: ensuring only one process accesses a shared resource/critical section at a time.
Synchronization: coordinating the relative timing of processes (e.g., producer-consumer, readers-writers problems).
Deadlock: circular waiting for resources that can bring the system to a permanent halt, requiring prevention, avoidance, or detection/recovery strategies.
Starvation: a process being perpetually denied access to a needed resource even though it is available.
Race conditions: incorrect results caused by unsynchronized concurrent access to shared data.
Resource allocation and scheduling fairness: deciding which process gets CPU/resources and when, without harming throughput or fairness.
Communication between processes: providing safe mechanisms (semaphores, monitors, message passing) for cooperating processes to exchange data.

2022 · Paper-II · Q3(a) (12 marks)

Question

Consider the following snapshot of the system. Using banker's algorithm, determine whether the state is safe or unsafe. If the state is safe, illustrate the order in which the processes may complete. Otherwise, illustrate why the state is unsafe. (Given: Claim Matrix C and Allocation Matrix A for 5 processes P1-P5 across 4 resource types R1-R4, Resource Vector = (12,13,6,8), Available Vector = (0,3,0,1).) Claim (Max) Matrix C: P1: 5 1 1 3 P2: 3 2 1 1 P3: 3 3 2 3 P4: 4 6 1 3 P5: 6 3 2 3 Allocation Matrix A: P1: 3 1 1 3 P2: 2 2 1 0 P3: 3 1 2 2 P4: 0 4 1 0 P5: 4 2 1 2

Solution

Step 1: compute Need = Claim - Allocation for each process (per resource R1,R2,R3,R4):

P1: (5-3, 1-1, 1-1, 3-3) = (2,0,0,0)
P2: (3-2, 2-2, 1-1, 1-0) = (1,0,0,1)
P3: (3-3, 3-1, 2-2, 3-2) = (0,2,0,1)
P4: (4-0, 6-4, 1-1, 3-0) = (4,2,0,3)
P5: (6-4, 3-2, 2-1, 3-2) = (2,1,1,1)

Available = (0,3,0,1).

Step 2: safety algorithm - repeatedly find a process whose Need <= Available; if found, pretend it runs to completion and add its Allocation back to Available; repeat until all processes finish or no such process exists.

Check P1 (2,0,0,0) vs Avail(0,3,0,1): R1 needs 2 > available 0 -> cannot run.
Check P2 (1,0,0,1) vs Avail(0,3,0,1): R1 needs 1 > available 0 -> cannot run.
Check P3 (0,2,0,1) vs Avail(0,3,0,1): 0<=0, 2<=3, 0<=0, 1<=1 -> P3 CAN run. Finish P3, release its allocation (3,1,2,2): new Available = (0+3, 3+1, 0+2, 1+2) = (3,4,2,3).
Check P1 (2,0,0,0) vs Avail(3,4,2,3): yes -> P1 CAN run. Release P1's allocation (3,1,1,3): Available = (3+3,4+1,2+1,3+3) = (6,5,3,6).
Check P2 (1,0,0,1) vs Avail(6,5,3,6): yes -> P2 CAN run. Release P2's allocation (2,2,1,0): Available = (8,7,4,6).
Check P4 (4,2,0,3) vs Avail(8,7,4,6): yes -> P4 CAN run. Release P4's allocation (0,4,1,0): Available = (8,11,5,6).
Check P5 (2,1,1,1) vs Avail(8,11,5,6): yes -> P5 CAN run and finishes.

All five processes could be sequenced to completion, so the state IS SAFE, with a safe sequence:

P3 -> P1 -> P2 -> P4 -> P5

2022 · Paper-II · Q3(b) (4 marks)

Question

Give an account of different functions of Logical File System.

Solution

The Logical File System is the layer of the file system that manages metadata and provides the file abstraction to users/applications (as opposed to the physical layer which manages actual disk blocks). Its main functions:

Maintains directory structure: organizes files into a hierarchy of directories/folders and manages naming.
Manages file metadata: keeps file attributes such as owner, permissions, size, timestamps, and location pointers, typically in a File Control Block (FCB)/inode.
Provides symbolic file names to users, translating them into the identifiers (e.g., inode numbers) the lower layers use.
Enforces access control and protection: checks permissions before allowing operations on a file.
Provides the logical view of files (as a sequence of bytes/records) to applications, hiding physical storage details like block allocation, which is handled by the lower physical/basic file system layers.

2022 · Paper-II · Q3(c) (4 marks)

Question

What resources are used when a thread is created? How do they differ from those used when a process is created?

Solution

Creating a thread requires only a small, lightweight set of resources: its own program counter, register set, and stack (its execution context), while it shares the code, data, heap, and open files/OS resources of the parent process with all its sibling threads.

Creating a process, by contrast, requires the OS to set up a completely independent address space: separate code, data, heap and stack segments, a new Process Control Block (PCB), its own page tables/memory mappings, and its own set of file descriptors and OS handles - none of which are shared with other processes by default.

Difference: process creation is "heavyweight" (large memory allocation, new address space, more OS bookkeeping and context-switch overhead), while thread creation is "lightweight" (minimal new state, faster to create/destroy/switch between, and communication between threads is easier since they share memory directly, unlike processes which need IPC mechanisms).

2021 · Paper-II · Q3(a) (3 marks)

Question

Memory managed by BITMAP is shown below (6x6 grid of 1s and 0s). Show properly filled memory according to the BITMAP where memory index starts from zero.

Solution

Reading the 6x6 bitmap row by row (index 0 at top-left, 1 = allocated unit, 0 = free unit), 36 allocation units total (index 0-35): Row0 (idx 0-5): 1 1 1 1 1 0 Row1 (idx 6-11): 0 1 1 0 0 0 Row2 (idx 12-17): 1 0 0 1 1 1 Row3 (idx 18-23): 1 0 0 0 0 0 Row4 (idx 24-29): 1 1 0 0 0 0 Row5 (idx 30-35): 0 0 0 0 1 1

So the memory, laid out as a linear array of 36 allocation units, is ALLOCATED at indices: 0,1,2,3,4, 7,8, 12,15,16,17, 18, 24,25, 34,35 and FREE at indices: 5,6, 9,10,11, 13,14, 19,20,21,22,23, 26,27,28,29, 30,31,32,33. This gives the free 'holes': [5-6] (length 2), [9-11] (length 3), [13-14] (length 2), [19-23] (length 5), [26-29] (length 4), [30-33] (length 4).

2021 · Paper-II · Q3(b) (3 marks)

Question

Insert a page H of size 3 allocation units in memory drawn in part 'a' using first-fit algorithm. Redraw memory and the BITMAP after insertion.

Solution

First-fit scans the bitmap from index 0 upward and allocates the page in the FIRST free run whose length is >= the required size (3 units). Free runs in order: [5-6] (length 2, too small), [9-11] (length 3, exact fit — SELECT THIS ONE). So page H (size 3) is placed at indices 9, 10, 11. Updated bitmap Row1 (idx 6-11) changes from 0 1 1 0 0 0 to 0 1 1 1 1 1. All other rows are unchanged. The memory array now shows indices 9,10,11 as allocated to H.

2021 · Paper-II · Q3(c) (3 marks)

Question

Now insert another page K of size 2 allocation units in memory drawn in part 'b' using next-fit algorithm. Redraw memory and the BITMAP after insertion.

Solution

Next-fit continues scanning from where the PREVIOUS allocation ended (index 12, right after H's block at 9-11), wrapping around only if needed. Scanning from index 12 onward: idx12=1(occupied), idx13=0, idx14=0 → a free run of length 2 at [13-14] — exactly matches the requested size 2, so page K is placed at indices 13, 14 (no need to continue further or wrap around). Updated bitmap Row2 (idx 12-17) changes from 1 0 0 1 1 1 to 1 1 1 1 1 1. All other rows remain as after step (b).

2021 · Paper-II · Q3(d) (6 marks)

Question

Use linked list data structure for the above memory mapping (Only give equivalent figure).

Solution

The linked-list representation stores memory as a chain of nodes, each describing one contiguous run — either a Process/Page (P) or a Free (F) hole — with {tag, start index, length, next pointer}:

[P,0,5] -> [F,5,2] -> [P,7,2] -> [H,9,3] -> [P,12,1] -> [K,13,2] -> [P,15,3] -> [P,18,1]
  -> [F,19,5] -> [P,24,2] -> [F,26,4] -> [F,30,4] -> [P,34,2] -> NULL

Each node's 'start index, length' pair corresponds exactly to a maximal run of consecutive identical bitmap bits found in part (c)'s bitmap; free (F) nodes are exactly the holes an allocation algorithm would search through, while P/H/K nodes mark occupied ranges — this is the classic OS allocated/free linked-list memory map, which is generally more efficient to scan for a fit than re-scanning the raw bitmap bit-by-bit.

2021 · Paper-II · Q3(e) (5 marks)

Question

Use hash table to keep track of active pages in the above memory (Only give figure).

Solution

A hash table indexed by page/process name maps each active page directly to its (start index, length) in memory, giving O(1) average lookup instead of scanning the bitmap or linked list:

Hash Table (key = page name, value = (start, length))
Bucket 0: -
Bucket 1: H -> (9, 3)
Bucket 2: K -> (13, 2)
Bucket 3: -
... (other original
process blocks, e.g. P1->(0,5), P2->(7,2), etc., hashed to their own buckets)

Whenever a page is allocated (like H or K above) or freed, the hash table is updated in O(1), letting the OS instantly find where any named active page currently resides without traversing the whole bitmap or linked list.

2021 · Paper-II · Q4(a) (3 marks)

Question

Calculate effective memory access time using following data: TLB hit ratio is 85%, TLB access time=20nsec, Memory access time=115nsec. Effective memory access time=Hit rate * (TLB access time+ Mem access time)+(1-Hit rate)( TLB access time+Process_table access time+ Mem access time)

Solution

Given: Hit ratio = 0.85, TLB access time = 20 ns, Memory access time = 115 ns. On a TLB miss, the page/process table itself must also be looked up in memory, which (in the absence of a separately given value) is taken as one additional memory access = 115 ns, per the formula's own structure. EMAT = HitRate × (TLB + Mem) + (1 − HitRate) × (TLB + PageTable + Mem) = 0.85 × (20 + 115) + 0.15 × (20 + 115 + 115) = 0.85 × 135 + 0.15 × 250 = 114.75 + 37.5 = 152.25 ns So the effective memory access time is 152.25 nanoseconds.

2021 · Paper-II · Q4(b) (4 marks)

Question

Consider a logical address and physical address of 31 and 22 bits respectively. What will be total logical and physical address space?

Solution

Logical (virtual) address space = 2^31 = 2,147,483,648 addressable locations ≈ 2 GB (if byte-addressable). Physical address space = 2^22 = 4,194,304 addressable locations = 4 MB. This means the system supports a much larger virtual address space (2 GB) than the actual installed physical memory (4 MB), which is exactly the scenario virtual memory/paging is designed to handle — only a subset of the logical address space can be resident in physical memory at any given time.

2021 · Paper-II · Q4(c) (3 marks)

Question

Does resource allocation graph shown below consist of a deadlock or not? Justify with reason.

Solution

General rule: in a Resource-Allocation Graph, if every resource involved has only a SINGLE instance, then a CYCLE in the graph is both a necessary and sufficient condition for deadlock. If some resources have multiple instances, a cycle is necessary but not always sufficient (it only indicates a POSSIBILITY of deadlock). Reading the given graph, there is a cycle: P1 → (resource) → P2 → R2 → P1, i.e. P1 is waiting on a resource held/requested via P2, P2 is waiting on/holding R2, and R2 is allocated back to P1, closing the loop (with R2 additionally pointing to P3, which is an extra edge outside the cycle and does not break it). Since this forms a closed cycle among the processes and resources, and assuming each resource shown has a single instance, the graph DOES indicate a deadlock: P1, P2 (and transitively any process depending on R2) are stuck in a circular wait with no external process able to release a resource to break the cycle.

2021 · Paper-II · Q4(d) (10 marks)

Question

What is race condition? What are the different techniques to avoid race condition in the processes? Which one is optimal and why?

Solution

A race condition occurs when two or more processes or threads access and manipulate shared data concurrently, and the final outcome of that shared data depends on the unpredictable relative timing/order in which their operations happen to be interleaved by the scheduler — producing incorrect or inconsistent results. Classic example: two processes both executing counter = counter + 1 on a shared counter can, if interleaved at the machine-instruction level, both read the same old value and each write back the same incremented value, losing one increment. Techniques to avoid race conditions:

Disabling interrupts — simple, but only works on single-processor systems, is dangerous (can hang the system if not re-enabled), and is inefficient.
Strict alternation (turn variable) — forces processes to take turns entering the critical section even when one doesn't need it, wasting CPU via busy-waiting and restricting concurrency unnecessarily.
Peterson's Algorithm — a software-only solution using a 'turn' variable plus per-process 'interested' flags; correct but still relies on busy-waiting (spinning).
Hardware atomic instructions — Test-and-Set (TSL) or Compare-and-Swap provide an atomic read-modify-write the hardware guarantees cannot be interrupted, used to implement spinlocks.
Semaphores — OS-provided synchronization primitives (counting/binary) that BLOCK/sleep a waiting process instead of busy-waiting, and can handle both mutual exclusion and general producer-consumer style synchronization.
Monitors — a high-level language construct that automatically encapsulates shared data with built-in mutual exclusion and condition variables, so the programmer cannot forget to lock/unlock. Which is optimal: Semaphores (and, at an even higher level of safety, Monitors) are generally considered optimal for real operating systems, because they avoid the wasted CPU cycles of busy-waiting solutions (Peterson's, TSL spinlocks) by putting a waiting process to sleep until the resource becomes available, are general-purpose enough to solve both mutual exclusion AND producer-consumer synchronization problems, and (in the case of monitors) reduce programmer error by making correct locking automatic rather than manual.

2020 · Paper-II · Q3(a) (7 marks)

Question

What is the kernel of an operating system? Explain the difference between a monolithic and microkernel.

Solution

The kernel is the core part of an operating system that runs with the highest privilege and directly manages the system's fundamental resources — the CPU (process scheduling), memory (allocation, protection), and devices (I/O) — providing basic services on which all other software depends. Monolithic kernel: the entire OS — process management, memory management, file systems, and device drivers — runs together in a single large program within one privileged address space. Communication between components is via direct function calls, making it fast (no context-switch/IPC overhead), but less robust and modular — a bug or crash in any single driver can bring down the whole system. Examples: traditional Linux, Unix. Microkernel: only the bare minimum functionality (inter-process communication, basic scheduling, minimal memory management) runs in kernel/privileged mode; other services such as file systems, network stacks, and device drivers run as separate user-space processes ('servers') that communicate via message passing. This is more robust, secure, and modular — a failing driver can be restarted without crashing the kernel — but incurs performance overhead from the extra IPC/context switches. Examples: Minix, QNX.

2020 · Paper-II · Q3(b) (6 marks)

Question

What is the difference between simple and virtual memory paging? Also explain the purpose of translation lookaside buffer.

Solution

Simple (non-demand) paging: the entire process's address space must be loaded into physical memory, with every page resident, before the process can start executing. Virtual memory (demand) paging: only the pages currently needed are loaded into physical memory at any given time; other pages remain on disk and are brought in on demand when referenced, triggering a page fault if not present. This allows processes larger than physical memory to run, and increases the degree of multiprogramming since memory is used more efficiently. The Translation Lookaside Buffer (TLB) is a small, very fast associative cache inside the MMU that stores recently used virtual-page-to-physical-frame translations. Its purpose is to avoid the extra memory access(es) needed to walk the full page table on every single memory reference: on a TLB hit, the physical address is obtained almost instantly; only on a TLB miss must the full (slower) page-table lookup be performed (after which the TLB is updated), dramatically speeding up average address translation.

2020 · Paper-II · Q3(c) (7 marks)

Question

Why do we have deadlock in the multiprocessing environment? Explain different techniques for dealing with deadlocks.

Solution

Deadlock arises in a multiprocessing environment when a set of processes are each waiting for a resource held by another process in the same set, so none of them can proceed — this requires all four Coffman conditions to hold simultaneously: (1) mutual exclusion (resources cannot be shared), (2) hold-and-wait (a process holds resources while waiting for more), (3) no preemption (resources cannot be forcibly taken away), and (4) circular wait (a cycle of processes each waiting on the next). Techniques for dealing with deadlock:

Prevention — design the system to negate at least one of the four conditions (e.g. require processes to request all needed resources at once, or impose a strict global ordering on resource requests to eliminate circular wait).
Avoidance — use runtime information to only grant a resource request if the resulting state is still 'safe' (e.g. the Banker's Algorithm).
Detection and Recovery — allow deadlocks to occur, periodically run a detection algorithm (using a resource-allocation/wait-for graph to find cycles), and recover by terminating a process or preempting a resource.
Ignorance (the 'Ostrich Algorithm') — simply ignore the problem, assuming deadlocks are rare enough that the cost of prevention/detection outweighs the risk; used by most general-purpose OSes like Windows and Linux.

2020 · Paper-II · Q4(c) (6 marks)

Question

List and briefly define any THREE file organization techniques. Also explain basic Linux file system security.

Solution

Three file organisation techniques:

Sequential organisation — records are stored and must be accessed strictly in order, one after another; simple and efficient for batch processing but slow for locating a specific record.
Indexed (Indexed-Sequential) organisation — records are kept in sequential order plus a separate index maps key values to record locations, allowing both fast direct lookup and sequential scanning.
Direct/Hashed organisation — a hash function maps a record's key directly to its storage location, giving near O(1) average access time without needing an index structure. Basic Linux file system security is based on Discretionary Access Control: every file/directory has an owner (uid) and a group (gid), and three permission triplets — read/write/execute for owner, group, and others — represented symbolically (rwxr-xr--) or in octal (e.g. 754). Special bits (setuid, setgid, sticky bit) grant temporary elevated execution privileges or restrict deletion in shared directories (e.g. /tmp). For finer-grained control beyond the basic owner/group/other model, Linux also supports Access Control Lists (ACLs), and Mandatory Access Control frameworks like SELinux or AppArmor for policy-enforced restrictions beyond discretionary permissions.

2019 · Paper-II · Q4(a) (8 marks)

Question

Demonstrate step by step procedure for process swapping between main memory and secondary memory.

Solution

Swapping moves an entire process's memory image between RAM and a reserved area of disk (the swap space/backing store) to free up main memory. Steps:

The OS's medium-term scheduler decides a process must be swapped out (e.g. it has been waiting long, or memory is under pressure).
The process's execution context (PCB: program counter, registers, memory-management info) is saved.
The process's entire memory image (code, data, stack segments) is copied from RAM to the swap area on secondary storage.
The main-memory frames it occupied are marked free in the OS's memory-allocation table/free list, available for other processes.
When the process is ready to run again, the OS locates enough free memory for it (which may be a different physical location than before).
The process's image is copied back (swapped in) from disk into main memory; any address relocation needed (base/limit registers or page-table update) is performed.
The saved PCB/register context is restored, and the process is placed back on the ready queue to resume execution.

2019 · Paper-II · Q4(b) (6 marks)

Question

Show flow chart of a process scheduling mechanism using various queues.

Solution

A multi-queue scheduling flow (described since a literal diagram cannot be drawn):

[New Process] --(admit)--> [Job Queue] --(long-term scheduler)--> [Ready Queue]
     [Ready Queue] --(short-term scheduler / dispatch)--> [CPU]
     [CPU] --(I/O request)--> [Device/Wait Queue] --(I/O completion)--> [Ready Queue]
     [CPU] --(time-slice expiry / preemption)--> [Ready Queue]
     [CPU] --(process creates child)--> [Ready Queue] (for the child)
     [CPU] --(process complete)--> [Exit]
     [Ready/Blocked Queue] --(memory shortage, medium-term scheduler)--> [Suspended Queue] --(resources available)--> [Ready Queue]

This shows a process entering via the job queue, being admitted to the ready queue, dispatched to the CPU, and then cycling between the ready queue, device/wait queues (for I/O), and possibly a suspended queue (if swapped out), until it eventually terminates.

2019 · Paper-II · Q4(c) (6 marks)

Question

Explain the difference between Sequential Access and Indexed Sequential Access in the context of file access using a suitable example.

Solution

Sequential Access: records in the file must be read/written strictly in physical order, one after another, from the start. To reach the Nth record, all preceding N-1 records must first be read/skipped. It is simple and efficient for bulk processing but slow for locating a specific record. Example: reading a plain log file line by line, or data stored on magnetic tape. Indexed Sequential Access (ISAM): the file's records are still stored in sequential (usually key) order, but an additional INDEX structure maps key values to approximate record locations. To find a record, the system first does a fast lookup in the (much smaller) index to jump close to the target, then performs a short sequential scan to the exact record. This supports both efficient direct access and full sequential scans. Example: a database table with a primary-key index, or a telephone directory with an alphabetical index of starting letters pointing to page ranges.

2018 · Paper-I · Q2(c) (3 marks)

Question

What are the responsibilities of Operating system kernel?

Solution

The kernel is the core component of the OS, running in privileged mode, with responsibilities including:

Process management: creating, scheduling, and terminating processes; context switching.
Memory management: allocating/deallocating memory, virtual memory (paging/segmentation).
File system management: organizing, storing, and providing access to files on storage devices.
Device management: controlling I/O devices via device drivers, handling interrupts.
Inter-process communication and synchronization: providing mechanisms (pipes, semaphores, message queues) for processes to communicate and coordinate safely.
System calls: providing the interface through which user-space applications request kernel services.
Security and access control: enforcing permissions and protecting resources from unauthorized access.

2018 · Paper-I · Q2(g) (2 marks)

Question

If time slice is of 50 milliseconds and context switch requires a microsecond, how many processes can the machine service in a second?

Solution

Each process 'turn' consumes: time slice + context switch overhead = 50 ms + 0.001 ms = 50.001 ms.

Total time available in one second = 1000 ms.

Number of processes serviced per second = 1000 / 50.001 = 19.9996 (approximately)

So the machine can service approximately 20 processes per second.

2018 · Paper-II · Q4(A) (8 marks)

Question

There are three processes PA, PB and PC and three resources RA, RB and RC. Resources RA and RB have one instance each while resource RC has two instances. PA is holding one instance of RC and has requested for RA. Process PB is holding RA and has requested for RB. RB is allocated to PC which has also requested an instance of RC. Represent the scenario with a resource allocation graph. Discuss whether there is a deadlock or not? If yes, which processes are blocked?

Solution

Resource Allocation Graph (RAG) edges:

RC -> PA (allocation: PA holds one instance of RC)
PA -> RA (request: PA requests RA)
RA -> PB (allocation: PB holds RA)
PB -> RB (request: PB requests RB)
RB -> PC (allocation: RB is allocated to PC)
PC -> RC (request: PC requests an instance of RC)

Tracing the graph, there is a cycle: PA -> RA -> PB -> RB -> PC -> RC -> PA.

However, for resource types with MULTIPLE instances (here RC has 2 instances), a cycle in the RAG is a NECESSARY but NOT SUFFICIENT condition for deadlock. We must check whether the cycle actually blocks all processes involved. RC has 2 instances, and only 1 instance is currently allocated (to PA); the SECOND instance of RC is free/available (no other process holds it). Since PC's request is for 'an instance of RC' and a free instance exists, PC's request can be immediately granted - PC is NOT blocked. PC can therefore proceed, complete its work, and release RB; RB then becomes available for PB, which can complete and release RA; RA then becomes available for PA, which can complete and release RC.

Conclusion: this is NOT a deadlock. Although the resource-allocation graph contains a cycle, the extra free instance of RC breaks the cycle's blocking effect, so no process is permanently blocked - the system can still reach completion for all three processes given the correct scheduling of the free RC instance to PC.

2018 · Paper-II · Q4(B) (6 marks)

Question

In the context of Paging, consider the case where memory addresses are 32 bits i.e. 20 bits Virtual Page Numbers and 12 bits of offset. How many virtual pages are there and what is the size of each page? Given the virtual address 0x7589, find the virtual page number and offset. If the respective page table entry contains 0x900DF, find the physical address.

Solution

Number of virtual pages = 2^20 = 1,048,576 pages (since the Virtual Page Number field is 20 bits).

Page size = 2^12 = 4096 bytes = 4 KB (since the offset field is 12 bits).

Virtual address given: 0x7589. Writing this out in binary/hex-aligned form (4 hex digits = 16 bits): 0x7589 = 0111 0101 1000 1001. The lowest 12 bits form the offset (bottom 3 hex digits): offset = 0x589 = 1417 (decimal). The remaining upper bits form the Virtual Page Number: VPN = 0x7589 >> 12 = 0x7 = 7 (decimal) (with leading zeros to pad to the full 20-bit VPN field).

Given that this VPN's page table entry contains the frame number 0x900DF: Physical Address = (Frame Number << 12) | Offset = (0x900DF << 12) | 0x589 = 0x900DF000 + 0x589 = 0x900DF589

So: Virtual Page Number = 0x7 (7), Offset = 0x589 (1417), and the Physical Address = 0x900DF589.

2018 · Paper-II · Q4(C) (6 marks)

Question

In the context of I/O management, differentiate between Pooling and Interrupts.

Solution

(Note: this is standardly known as 'Polling' vs 'Interrupts' in I/O management.)

Polling: the CPU repeatedly checks (polls) the status register of an I/O device in a loop, to see if it is ready for data transfer or has completed an operation. The CPU actively/continuously spends cycles checking, even when the device is not ready, wasting significant CPU time (busy-waiting) - simple to implement, but very inefficient, especially for slow devices, since the CPU cannot do other useful work while polling.

Interrupts: instead of the CPU repeatedly checking device status, the I/O device itself signals the CPU (raises an interrupt) only when it is ready or has completed its operation. The CPU can meanwhile execute other processes/instructions, and only switches to handle the I/O device (via an Interrupt Service Routine) when actually notified - making far more efficient use of CPU time, since no cycles are wasted on unnecessary status checks.

Key difference: Polling is a CPU-driven, synchronous, busy-wait approach (CPU actively asks 'are you ready?' repeatedly); Interrupts are a device-driven, asynchronous approach (device tells the CPU 'I'm ready now') - interrupts are generally far more efficient for CPU utilization, though polling can sometimes be simpler and even faster for extremely high-frequency, low-latency I/O where interrupt overhead itself would dominate.

2017 · Paper-I · Q2(c) (6 marks)

Question

Virtual memory is used by the computer to support the running of heavy applications. Describe the functioning of virtual memory in the computer. Also comment on the management of virtual and physical memory by an operating system.

Solution

Virtual memory is a memory-management technique that gives each process the illusion of a large, contiguous, private address space, independent of the actual amount of physical RAM installed, by using disk space (a 'swap area'/page file) as an extension of RAM.

Functioning: a process's virtual address space is divided into fixed-size pages; physical RAM is divided into equal-size frames. A per-process page table maps virtual pages to physical frames. Only the pages currently needed are kept in RAM; the rest reside on disk. When a process accesses a page not currently in RAM, a page fault occurs, the OS suspends the process, locates the page on disk, loads it into a free (or newly-freed, via a page-replacement algorithm such as LRU) frame, updates the page table, and resumes the process.

Management by the OS: the OS maintains page tables (with a Memory Management Unit/MMU performing address translation in hardware for speed), tracks free frames, chooses victim pages to evict when memory is full (page-replacement policy), and handles the actual disk I/O for swapping pages in/out. This lets the OS run more/larger processes than physical RAM alone would allow, at the cost of a performance penalty (thrashing) if too many page faults occur because RAM is heavily over-committed.

2017 · Paper-I · Q8(d) (5 marks)

Question

Write short notes on any FOUR of the following (5 each): (d) Resource allocation during runtime processes

Solution

Resource allocation during runtime is the operating system's ongoing task of assigning CPU time, memory, I/O devices, and files to processes as they execute and request resources dynamically (as opposed to allocating everything statically before execution begins).

Key aspects:

CPU allocation: handled by the CPU scheduler, which decides which ready process runs next based on a scheduling algorithm (FCFS, SJF, Round Robin, Priority, etc.).
Memory allocation: the memory manager assigns physical frames to a process's pages/segments on demand (e.g. via demand paging), and reclaims memory when a process terminates or pages are evicted.
Device/I/O allocation: the OS's device manager grants exclusive or shared access to I/O devices (printers, disks) through request queues and device drivers, sometimes using techniques like spooling.
Synchronization and safety: since multiple processes may compete for the same limited resources at runtime, the OS must apply mutual exclusion, avoid race conditions, and guard against deadlock (e.g. using the Banker's algorithm) or starvation (using aging/fair-scheduling policies).

Good runtime resource allocation aims to maximize resource utilization and system throughput while maintaining fairness among processes and avoiding unsafe states such as deadlock.

2017 · Paper-II · Q2(a) (8 marks)

Question

Discuss the following methods of storage systems: (i) Direct Access (ii) Random Access

Solution

Direct Access (Direct Access Storage/File Access Method): allows accessing any block/record of a file directly by its block number/address, without having to read through preceding blocks first - the storage medium (e.g. magnetic disk) is organized into fixed-size, individually addressable blocks so the read/write head can move directly to the required block. This enables efficient random-order access to records, essential for databases and indexed files. Access time depends on seek time to the target block, not on the position of previously accessed data.

Random Access (Random Access Memory/storage): refers to memory/storage where any location can be accessed in (approximately) equal time, regardless of its physical position in the storage - i.e., there is no requirement to access data sequentially or in the order it is physically stored. RAM (as opposed to sequential-access magnetic tape) is the classic example: the CPU can read/write any memory address directly with uniform access latency.

Relationship: Direct Access storage devices (like hard disks) support both direct file-access patterns and, in effect, provide a form of random access at the block level, whereas truly sequential devices (like magnetic tape) support neither efficiently since data must be read in physical order.

2017 · Paper-II · Q4(a) (8 marks)

Question

What are differences between Optimal & LRU (Least Recently Used) page Replacement Policies?

Solution

Optimal Page Replacement (OPT/MIN): replaces the page that will NOT be used for the longest time in the future - it requires perfect knowledge of the future reference string. It produces the theoretically minimum possible number of page faults for any given reference string, and is used only as a theoretical benchmark to evaluate other algorithms, since future references are not knowable in a real running system.

LRU (Least Recently Used): replaces the page that has not been used for the longest time in the PAST, using the (reasonable) heuristic assumption that a page unused recently is unlikely to be needed soon (temporal locality). It is implementable in practice (via counters, a stack, or reference bits/aging), unlike Optimal.

Key differences:

Knowledge required: Optimal needs future knowledge (impossible in practice); LRU only needs past access history (practically implementable).
Performance: Optimal always gives the fewest page faults possible; LRU approximates this well in practice but can perform worse in some access patterns (though it never suffers from Belady's anomaly, unlike FIFO).
Implementation cost: Optimal cannot truly be implemented for live systems; LRU requires extra hardware/software overhead (timestamps or a stack) to track recency of use, which is why approximations of LRU (e.g. Clock/Second-Chance algorithm) are often used instead of exact LRU.

2017 · Paper-II · Q4(b) (6 marks)

Question

Discuss the four necessary conditions for deadlock to occur. How can we deny any two of these conditions?

Solution

The four necessary conditions (Coffman conditions) that must ALL hold simultaneously for deadlock to occur:

Mutual Exclusion: at least one resource must be held in a non-shareable mode (only one process can use it at a time).
Hold and Wait: a process holding at least one resource is waiting to acquire additional resources currently held by other processes.
No Preemption: resources cannot be forcibly taken away from a process; they can only be released voluntarily.
Circular Wait: a set of processes {P0, P1, ..., Pn} exists such that P0 waits for a resource held by P1, P1 waits for P2, ..., and Pn waits for a resource held by P0, forming a cycle.

Denying any two of these conditions (deadlock prevention):

Deny Hold and Wait: require each process to request and be allocated ALL the resources it will ever need at once, before it starts execution (or require it to release all currently held resources before requesting new ones) - eliminates the possibility of a process holding some resources while waiting for others.
Deny Circular Wait: impose a strict, total (linear) ordering on all resource types, and require every process to request resources only in strictly increasing order of this numbering - this makes it impossible to form a cycle of waiting processes, since a process already holding a higher-numbered resource can never request a lower-numbered one held by a process waiting on it.

2017 · Paper-II · Q4(c) (6 marks)

Question

Consider three processes given in the table. Find average waiting time and average turnaround (completion) time when these processes are scheduled using Round-Robin scheduling using time quantum (TQ) = 4. Process CPU Burst P1 24 P2 7 P3 10

Solution

Round Robin, TQ=4, all processes assumed to arrive at time 0, ready-queue order P1,P2,P3:

t=0: P1 runs 4 (rem 20). Queue: P2,P3,P1 t=4: P2 runs 4 (rem 3). Queue: P3,P1,P2 t=8: P3 runs 4 (rem 6). Queue: P1,P2,P3 t=12: P1 runs 4 (rem 16). Queue: P2,P3,P1 t=16: P2 runs 3, FINISHES at t=19. Queue: P3,P1 t=19: P3 runs 4 (rem 2). Queue: P1,P3 t=23: P1 runs 4 (rem 12). Queue: P3,P1 t=27: P3 runs 2, FINISHES at t=29. Queue: P1 t=29: P1 runs 4 (rem 8). Queue: P1 t=33: P1 runs 4 (rem 4). Queue: P1 t=37: P1 runs 4, FINISHES at t=41.

Completion times: P1=41, P2=19, P3=29.

Turnaround Time (TAT) = Completion - Arrival(0): P1: 41, P2: 19, P3: 29. Average TAT = (41+19+29)/3 = 89/3 = 29.67

Waiting Time (WT) = TAT - Burst Time: P1: 41-24=17, P2: 19-7=12, P3: 29-10=19. Average WT = (17+12+19)/3 = 48/3 = 16

Answer: Average Waiting Time = 16, Average Turnaround Time = 29.67 (89/3).

2017 · Paper-II · Q5(c) (6 marks)

Question

What happens in the following cases? (i) If the job size is kept very low in time sharing systems. (ii) If the page size is kept very small in paged memory management.

Solution

(i) If job/time-slice size is kept very low in time-sharing systems: the CPU switches between processes extremely frequently. This gives excellent apparent responsiveness (each process gets CPU attention very often), but the overhead of context switching (saving/restoring process state) becomes a much larger fraction of total time, since context switches themselves consume CPU cycles without doing any useful work. If the time slice is too small, the system can spend most of its time context-switching rather than executing actual processes, severely reducing overall throughput and effective CPU utilization.

(ii) If page size is kept very small in paged memory management: internal fragmentation decreases (less wasted space in the last, partially-filled page of a process, since a smaller page means less potential waste), and memory utilization improves. However, the number of pages per process increases sharply, which increases the size of each process's page table (more entries needed), increasing memory overhead for page tables and address-translation (TLB) overhead; it also increases the number of page faults for programs whose memory-access patterns span across page boundaries, and increases disk I/O overhead since each I/O transfer moves less data per page. Thus, there's a fundamental trade-off: very small pages reduce internal fragmentation but increase page-table and page-fault overhead, and very large pages do the opposite.

2016 · Paper-II · Q4(a) (8 marks)

Question

Deadlock prevention algorithms prevents deadlock by restraining how requests can be made, the restrain ensure that at least one of the necessary conditions for deadlock cannot occur and hence, that deadlock cannot hold. Explain the Banker's Algorithm for deadlock avoidance.

Solution

The Banker's Algorithm (Dijkstra) is a deadlock-avoidance algorithm that treats resource allocation like a banker granting loans: it only grants a resource request if the resulting state is still 'safe' (i.e., there exists some order in which all processes can still finish).

Data structures used (for n processes, m resource types):

Available[m]: number of available instances of each resource type.
Max[n][m]: maximum demand of each process for each resource type.
Allocation[n][m]: currently allocated resources to each process.
Need[n][m] = Max - Allocation: remaining resources each process may still request.

Safety algorithm: find a sequence of all processes such that each process's Need can be satisfied by (current Available + resources released by previously finished processes in the sequence). If such a complete sequence exists, the system is in a safe state.

Resource-request algorithm: when process Pi requests resources Request[i]:

If Request[i] <= Need[i], continue; else error (exceeds max claim).
If Request[i] <= Available, continue; else Pi must wait.
Pretend to allocate: Available -= Request[i]; Allocation[i] += Request[i]; Need[i] -= Request[i].
Run the safety algorithm on this new state. If safe, the allocation is finalized; if unsafe, roll back and make Pi wait.

This guarantees the system never enters an unsafe state, thereby avoiding deadlock, but requires that each process declare its maximum resource need in advance.

2016 · Paper-II · Q4(b) (6 marks)

Question

Central Processing Unit (CPU) scheduling deal with the problem of deciding which of the processes in the ready queue is to be allocated to the CPU. What are the pros and cons of Multilevel Queue Scheduling and Multilevel Feedback Queue Scheduling?

Solution

Multilevel Queue Scheduling: the ready queue is permanently partitioned into several separate queues (e.g. foreground/interactive processes, background/batch processes), each with its own scheduling algorithm, and queues themselves are scheduled relative to each other (e.g. fixed priority or time-slicing between queues). Pros: simple to implement; allows different, appropriate scheduling policies per process class (e.g. Round Robin for interactive, FCFS for batch); good response time for high-priority queues. Cons: rigid - a process is permanently assigned to a queue and cannot move between queues, so it cannot adapt if its behaviour changes; can cause starvation of low-priority queues if higher queues are always busy.

Multilevel Feedback Queue Scheduling: similar multiple queues, but processes CAN move between queues based on their behaviour and how much CPU time they have used - typically, a process that uses too much CPU time is demoted to a lower-priority queue, while one that waits a long time may be promoted. Pros: much more flexible and adaptive; naturally favours short/interactive jobs (low turnaround) while still eventually servicing long CPU-bound jobs; can be tuned with many parameters (number of queues, algorithm per queue, promotion/demotion rules). Cons: most complex scheduler to design/implement/tune; requires careful parameter selection to avoid starvation of long jobs; overhead of tracking process history and moving between queues.

2016 · Paper-II · Q4(c) (6 marks)

Question

What do you know about Process Control Block? Discuss its components in detail.

Solution

A Process Control Block (PCB), also called a Task Control Block, is a data structure maintained by the operating system for every process; it stores all the information needed to manage and later resume that process, and is the manifestation of a process in the OS.

Key components:

Process ID (PID): unique identifier for the process.
Process State: current state (new, ready, running, waiting/blocked, terminated).
Program Counter: address of the next instruction to be executed for this process.
CPU Registers: contents of all process-specific registers (accumulators, index registers, stack pointers) saved during a context switch so execution can resume exactly where it left off.
CPU Scheduling Information: process priority, pointers to scheduling queues, and other scheduling parameters.
Memory Management Information: base/limit registers, page tables, or segment tables showing the process's memory allocation.
Accounting Information: CPU time used, time limits, process/account numbers.
I/O Status Information: list of I/O devices allocated to the process, open file list.

When a context switch occurs, the OS saves the currently running process's state into its PCB and loads the next process's state from its own PCB, which is how multiprogramming/multitasking is made possible.

Part B — MCQs

2025 · Paper-II · Q11 (MCQ)

Process synchronization can be done on:

A. Hardware level
B. Software level
C. Both (A) & (B)
D. None of these

Answer: C

Explanation: Synchronization primitives exist at both levels — hardware support such as test-and-set/compare-and-swap instructions, and software solutions such as Peterson's algorithm, semaphores and monitors.

2025 · Paper-II · Q12 (MCQ)

Which module gives control of the CPU to the process selected by the short-term scheduler?

A. Dispatcher
B. Interrupt
C. Scheduler
D. None of these

Answer: A

Explanation: The dispatcher is the OS module that actually performs the context switch and hands the CPU over to the process chosen by the short-term (CPU) scheduler.

2025 · Paper-II · Q13 (MCQ)

If the semaphore value is negative:

A. Its magnitude is the number of processes waiting on that semaphore
B. It is invalid
C. No operation can be further performed on it until the signal operation is performed on it
D. None of these

Answer: A

Explanation: In the standard counting-semaphore implementation, a negative value is valid and its absolute value equals the number of processes currently blocked waiting on that semaphore's queue.

2025 · Paper-II · Q14 (MCQ)

For 3 page frames, the following is the reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 How many page faults does the LRU page replacement algorithm produce?

A. 10
B. 15
C. 11
D. 12

Answer: D

Explanation: Simulating LRU with 3 frames step by step over the 20 references gives page faults at references 7,0,1,2,3,4,2,3,0,1,0,7 — a total of 12 faults (the remaining 8 references are hits).

2024 · Paper-I · Q10 (MCQ)

If an employee requests root access to a UNIX system in which you serve as the administrator, you shouldn't provide them access or this authority unless their job necessitates certain rights and privileges. Which cyber security notion may it be seen as an excellent example of:

A. Least privileges
B. Separation of Privileges
C. Open Design
D. None of these

Answer: A

Explanation: The principle of least privilege states that a user should be granted only the minimum access rights necessary to perform their job, exactly as described in the scenario.

2024 · Paper-I · Q11 (MCQ)

After a certain amount of time, say thirty minutes, the online application, similar to banking websites, should prompt users to log in again. Which cyber security concept may it be seen as a prime example of:

A. Compromise recording
B. Psychological acceptability
C. Complete mediation
D. None of these

Answer: C

Explanation: Complete mediation requires that every access to a resource be checked for authorization every time, not just once; forcing periodic re-authentication ensures access rights are re-verified rather than assumed to still hold indefinitely.

2024 · Paper-I · Q12 (MCQ)

Which of the following malware types does not infect others and duplicate or clone itself?

A. Rootkits
B. Trojans
C. Worms
D. None of these

Answer: B

Explanation: Trojans disguise themselves as legitimate software and rely on tricking a user into installing them; unlike worms (which self-replicate and spread automatically), Trojans do not self-replicate or clone themselves.

2024 · Paper-II · Q2 (MCQ)

A computer is in System mode when:

A. CPU is executing a program which is part of the operating system
B. The process execution is halted to listen to device inputs
C. The system is switching between processes
D. None of these

Answer: A

Explanation: System (kernel) mode is the privileged CPU mode in which the operating system's own code executes with full hardware access, as opposed to user mode used for ordinary application processes.

2024 · Paper-II · Q7 (MCQ)

Which is better, Time slicing or time sharing?

A. Time slicing is better because it deals with process allocation at the CPU level
B. Time sharing is better because it gives multiple users the illusion of each having his own processor
C. The comparison is not possible because one is part of the other
D. None of these

Answer: B

Explanation: Time sharing is the overall system goal of letting multiple users/processes interact with the computer as if each had a dedicated processor; time slicing (round-robin CPU allocation) is simply one mechanism used to implement time sharing, so time sharing's user-facing benefit is the more meaningful comparison point.

2024 · Paper-II · Q8 (MCQ)

Which type of algorithms are applicable to scheduling resources in operating systems?

A. State space search
B. Machine learning
C. Bayesian learning
D. None of these

Answer: A

Explanation: Classic OS resource/CPU scheduling can be framed as searching through a state space of possible process orderings/allocations to find one satisfying scheduling goals, which is the basis of state-space search algorithms used in scheduling theory.

2024 · Paper-II · Q9 (MCQ)

Which of the following are/is true?

A. In the era of platform independence all Operating systems can be made without considering low level details of machines
B. Operating systems can be made without using assembly languages
C. Operating systems aren't needed because everything can run on the internet
D. None of these

Answer: B

Explanation: Modern operating systems (e.g., much of Linux, Windows kernels) are written almost entirely in high-level languages like C, with only very small, hardware-specific portions in assembly, showing that OS development largely does not require assembly; option A is false since low-level hardware details still matter significantly, and C is clearly false.