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

(a) Process and Process States (6)

A process is a program in execution. It is an active entity that includes the program code (text), the current activity represented by the value of the program counter and CPU registers, a stack (temporary data such as function parameters and local variables), a data section (global variables) and a heap (dynamically allocated memory).

Process states

During its lifetime a process passes through the following states:

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

State-transition diagram (described)

        admit            dispatch
 New ----------> Ready -------------> Running ------> Terminated
                  ^   ^                 |   (exit)
                  |   |  interrupt      | I/O or event wait
      I/O / event |   +-----------------+
      completion  |                     v
                  +------------------ Waiting

Events causing each transition:

• New → Ready (admit): the OS admits the process and allocates the required resources.
• Ready → Running (dispatch / scheduler dispatch): the short-term scheduler selects the process and the dispatcher gives it the CPU.
• Running → Ready (interrupt / time-out): a timer interrupt expires (in pre-emptive scheduling) or a higher-priority process pre-empts it.
• Running → Waiting (I/O or event wait): the process issues an I/O request or a wait() system call.
• Waiting → Ready (I/O or event completion): the awaited event (e.g. I/O completion) occurs and the process becomes runnable again.
• Running → Terminated (exit): the process completes or is aborted.

(b) Process Control Block (PCB) and Context Switch (6)

The PCB is the data structure the OS maintains for every process. It stores all information needed to manage and resume the process:

• Process state (new, ready, running, waiting, terminated).
• Process identifier (PID).
• Program counter — address of the next instruction.
• CPU registers — accumulators, index registers, stack pointers, general-purpose registers, condition codes.
• CPU-scheduling information — priority, scheduling-queue pointers, scheduling parameters.
• Memory-management information — base/limit registers, page tables or segment tables.
• Accounting information — CPU time used, time limits, process numbers.
• I/O status information — list of open files and allocated I/O devices.

Role of the PCB in a context switch

A context switch occurs when the CPU is taken from one process (P1) and given to another (P2). The OS:

1. Saves the context of P1 — the current values of the program counter and CPU registers are copied into P1's PCB so that P1 can later resume exactly where it stopped.
2. Updates P1's state in its PCB (e.g. Running → Ready or Waiting) and places its PCB in the appropriate queue.
3. Selects P2 via the scheduler and loads P2's context — the program counter, registers and memory-management information are restored from P2's PCB into the CPU.
4. P2 resumes execution from the point recorded in its PCB.

Thus the PCB is the storage point that makes saving and restoring of process state possible. Context-switch time is pure overhead (no useful work is done), so the OS tries to keep it small.

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

(a)(i) Shortest Remaining Time First (SRTF) — pre-emptive

At each instant the process with the smallest remaining burst runs.

• t=0 only P1 → P1 runs. At t=1 P2(4) < P1 rem(7) → switch to P2.
• P2 runs 1→5 (it has the shortest remaining at t=2,3,4 too) and finishes at 5.
• At t=5 ready: P1(7), P3(9), P4(5) → smallest is P4(5); P4 runs 5→10, finishes at 10.
• At t=10 ready: P1(7), P3(9) → P1 runs 10→17, finishes at 17.
• P3 runs 17→26, finishes at 26.

Gantt chart:

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

• Average waiting time = (9+0+15+2)/4 = 26/4 = 6.5 ms
• Average turnaround time = (17+4+24+7)/4 = 52/4 = 13 ms

(a)(ii) Round Robin, quantum = 3 ms

Processes enter the ready queue in FCFS order; a process that exhausts its quantum is placed at the tail after newly-arrived processes.

Gantt chart:

| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | P1 | P3 |
0    3    6    9    12   15   16   19   21   23   26

• P1:0–3(rem5), P2:3–6(rem1), P3:6–9(rem6), P4:9–12(rem2), P1:12–15(rem2), P2:15–16(done CT=16), P3:16–19(rem3), P4:19–21(done CT=21), P1:21–23(done CT=23), P3:23–26(done CT=26).

• Average waiting time = (15+11+15+13)/4 = 54/4 = 13.5 ms
• Average turnaround time = (23+15+24+18)/4 = 80/4 = 20 ms

(b) Pre-emptive vs Non-pre-emptive, and Starvation (4)

Pre-emptive scheduling: the CPU can be taken away from a running process before it finishes (on a timer interrupt or arrival of a higher-priority process), e.g. SRTF, Round Robin, pre-emptive priority. It gives better responsiveness but incurs context-switch overhead and needs synchronization for shared data.

Non-pre-emptive scheduling: once a process gets the CPU it keeps it until it terminates or voluntarily blocks for I/O, e.g. FCFS, SJF (non-pre-emptive). It is simpler and has less overhead but can cause poor response time (convoy effect).

Starvation in priority scheduling: in priority scheduling, low-priority processes may wait indefinitely because a continuous stream of higher-priority processes keeps arriving and is always selected first; the low-priority process never gets the CPU.

Solution — Aging: gradually increase the priority of a process the longer it waits in the ready queue. Eventually even an initially low-priority process reaches a high enough priority to be scheduled, guaranteeing it will run.

(a) Four necessary conditions for deadlock (4)

All four must hold simultaneously (Coffman conditions):

1. Mutual exclusion — at least one resource is held in a non-sharable mode; only one process can use it at a time.
2. Hold and wait — a process holding at least one resource is waiting to acquire additional resources currently held by other processes.
3. No pre-emption — a resource cannot be forcibly taken from a process; it is released only voluntarily by the holding process.
4. Circular wait — there exists a set of processes {P0, P1, …, Pn} such that P0 waits for a resource held by P1, P1 for one held by P2, …, and Pn for one held by P0, forming a cycle.

(b) Banker's Algorithm (8)

Step 1 — Compute Need = Max − Allocation:

Available (Work) = (3 3 2)

Step 2 — Apply the safety algorithm (find a process whose Need ≤ Work, run it, release its allocation):

1. P1: Need (1 2 2) ≤ Work (3 3 2)? Yes → Work = (3 3 2) + Alloc (2 0 0) = (5 3 2). Finish P1.
2. P3: Need (0 1 1) ≤ (5 3 2)? Yes → Work = (5 3 2) + (2 1 1) = (7 4 3). Finish P3.
3. P4: Need (4 3 1) ≤ (7 4 3)? Yes → Work = (7 4 3) + (0 0 2) = (7 4 5). Finish P4.
4. P0: Need (7 4 3) ≤ (7 4 5)? Yes → Work = (7 4 5) + (0 1 0) = (7 5 5). Finish P0.
5. P2: Need (6 0 0) ≤ (7 5 5)? Yes → Work = (7 5 5) + (3 0 2) = (10 5 7). Finish P2.

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

Safe sequence: ⟨ P1, P3, P4, P0, P2 ⟩

(Other valid sequences exist, e.g. ⟨P1, P3, P0, P2, P4⟩, since the algorithm only needs one safe sequence.)

(a) Paging and Address Translation (8)

Paging is a memory-management scheme that removes the requirement of contiguous allocation of physical memory. Physical memory is divided into fixed-size blocks called frames, and logical memory is divided into blocks of the same size called pages. When a process runs, its pages are loaded into any available frames, and a page table keeps the mapping from pages to frames.

Logical-to-physical address translation

A logical (virtual) address generated by the CPU is split into two parts:

• Page number (p) — index into the page table.
• Page offset (d) — displacement within the page.

$$\text{Physical address} = (\text{frame number} \times \text{page size}) + \text{offset}$$

If a logical address space is $2^m$ and page size is $2^n$, the high-order $m-n$ bits are the page number and the low-order $n$ bits are the offset.

Translation steps (described):

  Logical address:  | page no. p | offset d |
                          |
                          v
                   [ Page Table ] --> frame number f
                          |
                          v
  Physical address: | frame no. f | offset d |  --> Physical memory

The page number p indexes the page table to obtain the frame number f; the offset d is appended unchanged, giving the physical address which is sent to main memory.

Role of the TLB

Keeping the page table in main memory means every memory reference needs two accesses — one to read the page-table entry and one to read the actual data — which halves performance.

The Translation Look-aside Buffer (TLB) is a small, fast, fully-associative hardware cache that stores recently-used (page → frame) mappings.

• On a memory reference, the page number is presented to the TLB.
• TLB hit: the frame number is obtained immediately (no page-table access).
• TLB miss: the page table in memory is consulted, and the mapping is loaded into the TLB for future use.

With hit ratio $\alpha$, TLB access time $\varepsilon$ and memory access time $m$, the effective access time is

$$EAT = \alpha(\varepsilon + m) + (1-\alpha)(\varepsilon + 2m).$$

Because locality of reference gives a high hit ratio, the TLB makes the average translation almost as fast as a single memory access.

(b) Page Replacement — FIFO vs OPT (6)

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2, 3 frames (all initially empty). A hit is marked H, a fault F.

FIFO (oldest-loaded page is replaced)

FIFO page faults = 9.

Optimal (replace the page that will not be used for the longest time)

OPT page faults = 7.

Conclusion

• OPT (7 faults) performs better than FIFO (9 faults), as expected, because OPT is the theoretically optimal algorithm (lowest possible fault count). However, OPT is not implementable in practice because it requires knowledge of future references; it is used as a benchmark.
• Belady's anomaly is the phenomenon where increasing the number of frames increases the number of page faults. It can occur only with FIFO (it does not affect stack algorithms such as LRU/OPT). For this single 3-frame run we cannot observe the anomaly directly — demonstrating it requires comparing FIFO across two different frame counts — but FIFO is the algorithm that can suffer from Belady's anomaly, whereas OPT cannot.

(a) Critical Section Problem and its Requirements (3)

The critical section (CS) is the segment of code in which a process accesses shared resources (shared variables, files, tables). The critical-section problem is to design a protocol that processes can use to cooperate so that no two processes execute their critical sections at the same time, thereby avoiding race conditions.

Any correct solution must satisfy these three requirements:

1. Mutual exclusion — if one 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 CS 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 CS after a process has requested entry and before that request is granted (no starvation).

(b) Semaphores and the Producer–Consumer Problem (5)

A semaphore S is an integer variable accessed only through two atomic operations:

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

• A counting semaphore can take any non-negative integer value and is used to control access to a resource that has a finite number of instances.
• A binary semaphore (mutex) takes only the values 0 and 1 and is used for mutual exclusion.

Producer–Consumer (bounded buffer of size n)

Three semaphores are used:

• mutex = 1 (binary) — protects the buffer.
• empty = n (counting) — counts empty slots.
• full = 0 (counting) — counts filled slots.

Producer:                       Consumer:
while (true) {                  while (true) {
    produce item;                   wait(full);
    wait(empty);                    wait(mutex);
    wait(mutex);                    remove item from buffer;
    add item to buffer;             signal(mutex);
    signal(mutex);                  signal(empty);
    signal(full);                   consume item;
}                               }

• wait(empty) blocks the producer when the buffer is full; wait(full) blocks the consumer when the buffer is empty.
• mutex ensures only one process manipulates the buffer at a time.
• signal(full) / signal(empty) update the counts so producer and consumer correctly synchronize.

Dining Philosophers Problem

Five philosophers sit around a circular table. There is a bowl of rice in the centre and five forks (chopsticks), one placed between each pair of adjacent philosophers. A philosopher alternates between thinking and eating. To eat, a philosopher needs two forks — the one on the left and the one on the right. After eating, the philosopher puts both forks down and resumes thinking. Each fork is a shared resource that can be held by only one philosopher at a time. The problem is to devise a protocol that lets philosophers eat without deadlock or starvation.

A naive semaphore solution uses one semaphore per fork (fork[5], all initialized to 1):

philosopher i:
    wait(fork[i]);              // pick up left fork
    wait(fork[(i+1) % 5]);     // pick up right fork
    eat();
    signal(fork[i]);
    signal(fork[(i+1) % 5]);

Why this leads to deadlock

If all five philosophers simultaneously pick up their left fork, every fork is held by exactly one philosopher, so fork[i] = 0 for all i. Each philosopher then executes wait(fork[(i+1)%5]) for the right fork, which is held by the neighbour. No philosopher can proceed, and no one releases a fork — a circular-wait deadlock occurs (all four Coffman conditions hold: forks are mutually exclusive, each holds one and waits for another, no pre-emption, circular wait).

One method to prevent it

Any of the following breaks the circular wait:

• Asymmetric / ordered acquisition: make the philosophers pick up forks in a fixed global order — e.g. odd-numbered philosophers pick up the left fork first and even-numbered ones pick up the right fork first. This breaks the symmetry so a complete cycle cannot form.
• Limit concurrency: allow at most four philosophers to sit at the table at once (use a counting semaphore initialized to 4), guaranteeing at least one philosopher can obtain both forks.
• All-or-nothing: let a philosopher pick up both forks only if both are free (acquire forks inside a critical section / monitor), so a philosopher never holds one fork while waiting for the other.

Disk has cylinders 0–199, head starts at 53, request queue: 98, 183, 37, 122, 14, 124, 65, 67.

FCFS (First-Come-First-Served)

Serve in arrival order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67.

Movements: |98−53|+|183−98|+|37−183|+|122−37|+|14−122|+|124−14|+|65−124|+|67−65| = 45+85+146+85+108+110+59+2 = 640 cylinders.

SSTF (Shortest Seek Time First)

Always serve the nearest pending request: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183.

• 53→65 = 12
• 65→67 = 2
• 67→37 = 30
• 37→14 = 23
• 14→98 = 84
• 98→122 = 24
• 122→124 = 2
• 124→183 = 59

Total = 12+2+30+23+84+24+2+59 = 236 cylinders.

SCAN (elevator, moving towards higher cylinders first)

Sorted requests: 14, 37, 65, 67, 98, 122, 124, 183. Moving up from 53, service 65, 67, 98, 122, 124, 183, continue to the end (199), then reverse and service 37, 14.

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

• Up: 199 − 53 = 146
• Down: 199 − 14 = 185

Total head movement = 146 + 185 = 331 cylinders.

(If the head reverses immediately at the last request 183 without going to 199 — the LOOK variant — the total would be (183−53)+(183−14) = 130+169 = 299. Using standard SCAN to cylinder 199 the answer is 331.)

Summary

File Allocation Methods

1. Contiguous allocation

Each file occupies a set of consecutive blocks on disk; the directory stores the start block and length.

• Advantage: excellent sequential and direct (random) access — the block address is start + offset, so it is very fast; minimal seek time.
• Disadvantage: suffers from external fragmentation and it is hard to grow a file (no free space adjacent to it).
• Access suitability: good for both sequential and direct access.

2. Linked allocation

Each file is a linked list of disk blocks; each block contains a pointer to the next block. The directory holds the address of the first (and last) block.

• Advantage: no external fragmentation; files can grow easily by linking a new free block.
• Disadvantage: poor direct access — to reach block i you must follow i pointers; pointers also waste space and a broken pointer corrupts the rest of the file.
• Access suitability: good for sequential access, poor for direct/random access.

3. Indexed allocation

Each file has an index block holding an array of all the disk-block addresses belonging to the file; the i-th entry points to the i-th block.

• Advantage: supports efficient direct (random) access with no external fragmentation.
• Disadvantage: index-block overhead — even a small file needs a whole index block; for very large files multi-level/linked index blocks are required.
• Access suitability: good for both sequential and direct access (the main scheme used in real systems, e.g. UNIX inodes).

Summary table

(a) Thrashing and Degree of Multiprogramming (3)

Thrashing is a condition in which a process (or the whole system) spends more time paging (servicing page faults) than executing useful instructions, causing CPU utilization to collapse.

Cause with respect to the degree of multiprogramming: when the degree of multiprogramming is increased to keep the CPU busy, each process is allotted fewer frames. Once a process does not have enough frames to hold its actively-used pages (its locality), it generates frequent page faults. Faulting processes queue for the paging device, CPU utilization drops, so the OS — seeing the idle CPU — admits even more processes, giving each still fewer frames. This positive-feedback loop causes page-fault rate to soar and CPU utilization to fall sharply beyond a certain point — that is thrashing.

(b) Working-Set Model (3)

The working set $W(t, \Delta)$ is the set of pages referenced by a process in the most recent $\Delta$ memory references (the working-set window). It approximates the process's current locality.

• Let $WSS_i$ be the working-set size of process i. The total demand for frames is $D = \sum WSS_i$.
• The OS detects impending thrashing by monitoring $D$ against the total number of available frames $m$:
  • If $D > m$, demand exceeds supply → thrashing will occur.
• Control: the OS allocates each process enough frames to hold its working set. If $D > m$, it suspends one or more processes (reduces the degree of multiprogramming), frees their frames for the remaining processes, and resumes them later. This keeps each running process supplied with its working set, minimizing page faults and preventing thrashing while maximizing the degree of multiprogramming consistent with the available memory.

Internal vs External Fragmentation

• Internal fragmentation is the memory wasted inside an allocated region. It occurs when a process is given a block larger than it requested (e.g. fixed-size partitions or paging where the last page is partly empty); the unused space inside the allocated block cannot be used by other processes.
• External fragmentation is the memory wasted outside allocated regions. Free memory exists in small, non-contiguous holes scattered between allocations; the total free space may be enough for a request, but no single hole is large enough, so the request fails.

Dynamic (Contiguous) Allocation Strategies

When a process of a given size requests memory, the allocator searches the list of free holes:

• First-fit: allocate the first hole that is large enough. Fast (short search) and generally performs well.
• Best-fit: allocate the smallest hole that is large enough. Minimizes leftover space per allocation but leaves many tiny, unusable holes and requires searching the whole list (unless sorted).
• Worst-fit: allocate the largest available hole. The idea is that the leftover hole is big enough to be reused, but in practice it performs poorly and wastes large holes.

First-fit and best-fit are generally better than worst-fit in both time and storage utilization.

Compaction

All three strategies leave external fragmentation. Compaction is the technique of relocating allocated blocks (shuffling them to one end of memory) so that all the free holes are coalesced into one large contiguous block. This eliminates external fragmentation and allows large requests to be satisfied.

• Compaction is only possible if relocation is dynamic (done at execution time via base/relocation registers).
• It is expensive, since processes may have to be suspended and large amounts of memory copied, so it is performed only when needed.

(a) File vs Directory and Directory Structures (4)

File vs Directory:

• A file is a named collection of related information (data or program) stored on secondary storage, treated by users as a single logical unit; it has attributes such as name, type, size, location and protection.
• A directory is a special system file that organizes and keeps track of files; it maps human-readable file names to their file-control information (location, attributes). A directory can contain files and other directories.

Directory structures:

• Single-level directory: all files of all users are kept in one directory. Simple, but file names must be unique across the whole system and it is hard to organize many files or support multiple users.
• Two-level directory: each user has a separate User File Directory (UFD) under a Master File Directory (MFD). Different users may use the same file name without conflict, but it isolates users and makes sharing files between users difficult.
• Tree-structured directory: directories are arranged as a hierarchical tree with a root and arbitrary nesting of subdirectories. It allows logical grouping of files, supports absolute and relative path names, and is the structure used by most modern operating systems.

(b) RAID and RAID Level 1 (2)

RAID (Redundant Array of Independent/Inexpensive Disks) is a technique that combines multiple physical disk drives into a single logical unit to improve performance (through parallelism/striping) and/or reliability (through redundancy).

RAID Level 1 (mirroring): every block of data is written identically to two (or more) disks, so each disk has a complete copy (mirror) of the other. If one disk fails, the data is still fully available on the mirror disk, so the system keeps running and the data is recovered by copying from the surviving disk. This greatly improves reliability (and can improve read performance), at the cost of 50% storage overhead.

Process vs Thread

Advantages of Multithreading

• Responsiveness — one thread can continue running (e.g. UI) while another blocks on I/O.
• Resource sharing — threads share the code and data of the process, so no extra IPC is needed.
• Economy — creating and context-switching threads is cheaper than for processes.
• Scalability — threads can run in parallel on multiple CPU cores, improving throughput.

Threading Models (mapping user threads to kernel threads)

• Many-to-One: many user-level threads are mapped to a single kernel thread. Thread management is done in user space and is efficient, but a single blocking system call blocks the entire process, and threads cannot run in parallel on multiprocessors.
• One-to-One: each user thread maps to its own kernel thread. Provides true concurrency and a blocking call blocks only that thread, but creating many kernel threads is expensive, so the number of threads may be limited (used by Windows and Linux).
• Many-to-Many: many user threads are multiplexed onto an equal or smaller number of kernel threads. Combines the advantages of both: allows real parallelism and many user threads while limiting kernel-thread count; more complex to implement.

Techniques for Performing I/O

1. Programmed I/O (polling / busy-waiting)

The CPU issues an I/O command and then continuously polls the status register of the device, waiting in a loop until the device is ready, and transfers each word of data itself.

• Simple to implement but wastes CPU time in the busy-wait loop; the CPU is fully occupied during the transfer.

2. Interrupt-driven I/O

The CPU issues the I/O command and then continues with other work. When the device is ready, it raises an interrupt; the CPU suspends its current task, runs the interrupt-service routine to transfer one unit of data, and resumes.

• The CPU is no longer tied up in a polling loop, so it is more efficient than programmed I/O. However, the CPU is still interrupted and involved in transferring every word/byte, which is costly for large/fast transfers.

3. Direct Memory Access (DMA)

A dedicated DMA controller transfers a whole block of data directly between the device and main memory without per-word CPU intervention. The CPU only sets up the transfer (source, destination, count) and is interrupted once when the entire block is complete.

• The DMA controller takes over the memory bus (cycle stealing) to move data while the CPU does other work.

Main advantage of DMA

DMA frees the CPU from the data-transfer work: instead of being involved in transferring every byte/word (as in programmed and interrupt-driven I/O), the CPU is interrupted only once per block. This makes DMA far more efficient for high-speed, large-volume transfers (e.g. disk, network), greatly increasing overall system throughput.