BSc CSIT (TU) Science Operating System (BSc CSIT, CSC259) Question Paper 2077 Nepal

Paging

Paging is a non-contiguous memory-management technique that eliminates external fragmentation by dividing the logical address space of a process into fixed-size blocks called pages, and physical memory into blocks of the same size called frames. When a process is executed, its pages are loaded into any available frames (which need not be contiguous).

• Page size = Frame size (typically a power of 2, e.g., 4 KB).
• A page table (one per process) stores the frame number for each page.

Address Structure

The CPU generates a logical (virtual) address consisting of two parts:

• p = page number → used as an index into the page table.
• d = page offset → displacement within the page.

If logical address space = $2^m$ and page size = $2^n$, then the high-order $m-n$ bits give $p$ and the low-order $n$ bits give $d$.

Logical-to-Physical Address Translation

1. The CPU produces logical address $(p, d)$.
2. The page number $p$ indexes the page table, which returns the frame number $f$.
3. The physical address is formed by combining $f$ with the offset $d$:

4. This physical address is sent to memory.

(Diagram in words: CPU → split address into p and d → p selects an entry in the page table → entry gives frame f → f concatenated with d → physical memory.)

Translation Look-aside Buffer (TLB)

Keeping the page table in main memory means two memory accesses per reference (one for the page table, one for the data), doubling effective access time. To speed this up, a small, fast associative cache called the TLB stores recently used page-to-frame mappings.

Steps with TLB:

1. Page number $p$ is presented to the TLB.
2. TLB hit → frame number $f$ is obtained directly; physical address is formed immediately.
3. TLB miss → the page table in memory is consulted to get $f$, and the mapping $(p,f)$ is added to the TLB (replacing an entry if full).

Effective Access Time (EAT): If TLB hit ratio = $\alpha$, TLB access time = $\epsilon$, memory access time = $m$:

Advantages

• No external fragmentation; only minor internal fragmentation (in the last page).
• Allows non-contiguous allocation and supports virtual memory.

Virtual Memory

Virtual memory is a memory-management technique that allows the execution of processes that may not be completely loaded in main memory. It gives the illusion of a very large (virtual) address space by keeping only the currently needed pages in RAM and the rest on disk (backing store/swap area). Benefits: programs larger than physical memory can run, higher degree of multiprogramming, and better memory utilization.

Demand Paging

Demand paging loads a page into memory only when it is referenced (on demand), rather than loading the whole process at once. Each page-table entry has a valid/invalid bit:

• Valid → page is in memory.
• Invalid → page is on disk (not loaded).

When a process references a page marked invalid, a page fault occurs:

1. Trap to the OS.
2. Find a free frame (or select a victim using a replacement algorithm).
3. Read the required page from disk into the frame.
4. Update the page table (set valid bit).
5. Restart the instruction.

Page Replacement Algorithms

When no free frame is available, a page replacement algorithm selects a victim page. Consider the reference string with 3 frames:

FIFO (First-In First-Out)

Replaces the page that has been in memory the longest.

Page faults occur as new pages enter and the oldest is evicted. Total page faults = 9. Simple to implement but can suffer Belady's anomaly (more frames may cause more faults).

Optimal (OPT / MIN)

Replaces the page that will not be used for the longest time in the future.

This yields the minimum possible faults = 7, but is not implementable in practice (requires future knowledge); it serves as a benchmark.

LRU (Least Recently Used)

Replaces the page that has not been used for the longest time in the past (approximates Optimal using history).

Total page faults = 9 (with proper tie handling, LRU performs close to Optimal). Does not suffer Belady's anomaly (it is a stack algorithm) but needs hardware support (counters or a stack).

Comparison

Conclusion: Optimal gives the fewest faults (theoretical bound), LRU is the best practical approximation, and FIFO is simplest but least efficient.

Disk Scheduling Algorithms

Disk scheduling decides the order in which pending disk I/O requests are serviced to minimize total head movement (seek time).

Example: Request queue (cylinders): 98, 183, 37, 122, 14, 124, 65, 67, with the disk head initially at cylinder 53 (disk range 0–199). Head moving toward higher cylinders where direction matters.

1. FCFS (First-Come First-Served)

Requests served in arrival order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67. Total head movement:

Simple and fair, but inefficient (wild swings).

2. SSTF (Shortest Seek Time First)

Serves the request closest to the current head position. Order: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183. Total movement:

Better performance but may cause starvation of far requests.

3. SCAN (Elevator)

Head moves in one direction servicing requests, goes to the end of the disk (0 or 199), then reverses. Moving toward 0 first: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183. Total movement:

4. C-SCAN (Circular SCAN)

Head moves one direction servicing requests to the end, then jumps back to the start without servicing on the return, providing more uniform wait time. Moving up: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → (jump) 0 → 14 → 37. Total movement (up to 199, wrap to 0, up to 37):

5. LOOK

Like SCAN but the head only goes as far as the last request in each direction (does not travel to the physical end). Moving up: 53 → 65 → 67 → 98 → 122 → 124 → 183, then reverse: → 37 → 14. Total movement:

(If moving down first, LOOK gives 53→14→183 = 39 + 169 = 208.)

Summary

Conclusion: SSTF and SCAN minimize movement here; SCAN/C-SCAN/LOOK avoid the starvation possible with SSTF, while FCFS is simplest but worst.

Thrashing

Thrashing is a condition in which a process (or the system) spends more time servicing page faults than executing useful work. It occurs when a process does not have enough frames to hold its working set, so it continuously page-faults — every replaced page is needed again almost immediately. CPU utilization drops sharply while paging-disk activity becomes very high.

Cause: Too high a degree of multiprogramming → too few frames per process → high page-fault rate.

Prevention / Control

1. Working-Set Model: Track each process's working set (set of pages used in a recent window $\Delta$) and allocate enough frames to hold it; suspend a process if the total demand exceeds available frames.
2. Page-Fault Frequency (PFF) control: Monitor each process's page-fault rate; if it rises above an upper threshold, allocate more frames; if it falls below a lower threshold, reclaim frames.
3. Reduce the degree of multiprogramming (swap out some processes) so remaining processes get enough frames.
4. Use local (vs global) page replacement to stop one process from stealing frames from others.
5. Increase physical memory (RAM).

Logical vs Physical Address Space

• A logical (virtual) address is generated by the CPU during program execution; the set of all such addresses is the logical address space.
• A physical address is the actual address seen by the memory unit (loaded into the Memory Address Register); the set of all such addresses is the physical address space.
• The Memory Management Unit (MMU) maps logical addresses to physical addresses at run time (e.g., physical = logical + relocation/base register).

In compile-time and load-time binding, logical and physical addresses are identical; in execution-time binding they differ, and the MMU performs the translation.

Segmentation

Segmentation is a memory-management scheme that supports the user's view of memory: a program is seen as a collection of variable-length logical units called segments, such as the main program, functions, stack, arrays, and global variables. Unlike paging, segments are variable-sized and correspond to logical divisions of the program.

Logical Address

A logical address in segmentation is a pair:

Segment Table

Each process has a segment table; each entry contains:

• Base — the starting physical address of the segment in memory.
• Limit — the length of the segment.

Address Translation

1. Use segment number $s$ to index the segment table → get base and limit.
2. Check that offset $d < \text{limit}$; if $d \ge \text{limit}$, raise an addressing/trap (protection) error.
3. Physical address = $\text{base} + d$.

Advantages

• Matches the logical structure of programs.
• Easy sharing and protection at the segment level (e.g., read-only code segment).
• No internal fragmentation.

Disadvantage

• Causes external fragmentation because segments are of varying size (often solved by segmentation with paging).

Semaphore

A semaphore is an integer synchronization variable, proposed by Dijkstra, used to control access to shared resources and to coordinate processes. It is accessed only through two atomic operations:

• wait(S) (also P/down):

wait(S) {
    while (S <= 0) ;   // busy wait (or block)
    S = S - 1;
}

• signal(S) (also V/up):

signal(S) {
    S = S + 1;
}

These operations must execute indivisibly so two processes cannot modify $S$ simultaneously. Semaphores solve mutual exclusion and the critical-section problem.

Binary vs Counting Semaphore

Example: A binary semaphore guards a single printer; a counting semaphore initialized to 5 manages a pool of 5 identical resources.

Monitor

A monitor is a high-level synchronization construct that encapsulates shared data, the procedures that operate on it, and synchronization within a single abstract data type (module). It overcomes the error-proneness of bare semaphores by enforcing structured access.

Key Properties

• Only one process can be active inside the monitor at a time (mutual exclusion is automatic / compiler-enforced). Other processes calling a monitor procedure are blocked until the monitor is free.
• Shared variables can be accessed only through the monitor's procedures, ensuring controlled access.

Condition Variables

For conditional waiting, a monitor provides condition variables, manipulated by two operations:

• wait(c): the calling process is suspended and placed in the queue of condition $c$, releasing the monitor.
• signal(c): resumes exactly one process waiting on $c$ (if none is waiting, it has no effect).

Structure (skeleton)

monitor MonitorName {
    // shared variables
    condition c;
    procedure P1(...) { ... }
    procedure P2(...) { ... }
    initialization code { ... }
}

Signaling Disciplines

• Hoare (signal-and-wait): signaling process waits, signaled process runs immediately.
• Mesa (signal-and-continue): signaling process continues; signaled process rechecks its condition (uses while instead of if).

Advantage: Easier and safer than semaphores because mutual exclusion is handled automatically by the construct.

Preemptive vs Non-Preemptive Scheduling

CPU scheduling decisions happen in four situations; if scheduling occurs only when a process terminates or voluntarily switches to the waiting state, it is non-preemptive; if it can also occur when a process switches from running to ready (or a new process arrives), it is preemptive.

RAID (Redundant Array of Independent Disks)

RAID is a technology that combines multiple physical disk drives into a single logical unit to improve performance (via parallelism / data striping) and/or reliability (via redundancy such as mirroring or parity). It uses techniques of striping, mirroring, and parity to balance speed, capacity, and fault tolerance.

RAID Level 0 (Striping)

• Data is striped (split into blocks) across multiple disks; consecutive blocks go to different disks.
• No redundancy — there is no parity or mirror.
• Advantage: High read/write performance and full capacity utilization (parallel access).
• Disadvantage: No fault tolerance — failure of any one disk causes total data loss.

RAID Level 1 (Mirroring)

• Every block of data is duplicated on two (or more) disks (a mirror copy).
• Advantage: High reliability — if one disk fails, the mirror still has the data; also faster reads.
• Disadvantage: 50% storage overhead (usable capacity is half the total) and higher cost.

(Other levels: RAID 5 = block-level striping with distributed parity; RAID 6 = double parity; RAID 0+1 / 1+0 = combinations.)

Directory Structure of a File System

A directory is a symbol table that maps file names to their file-control-block / location on disk, allowing files to be organized and located. Common directory structures:

1. Single-Level Directory

• All files are kept in one directory for all users.
• Simple, but suffers naming conflicts (every file must have a unique name) and no grouping. Unsuitable for multiple users.

2. Two-Level Directory

• A separate directory (User File Directory, UFD) for each user, indexed by a Master File Directory (MFD).
• Solves name collisions between users, but no grouping within a user's files and limited sharing.

3. Tree-Structured Directory

• A hierarchy of directories and subdirectories (a tree with a root).
• Allows logical grouping; files are accessed by absolute or relative path names. Most common (e.g., Unix/Windows). No cycles allowed.

4. Acyclic-Graph Directory

• Allows directories/files to be shared via links (a file can appear in more than one directory) while forbidding cycles.
• Enables sharing but complicates deletion (needs reference counts).

5. General-Graph Directory

• Permits cycles (links anywhere). Most flexible but requires cycle detection and garbage collection to manage deletion correctly.

Summary: Structures evolve from single-level (simple, no organization) → tree (grouping, paths) → graph (sharing).

Deadlock and Preemptable Resources

No — deadlock generally cannot occur (or can be broken) if all resources are preemptable. A preemptable resource is one that can be taken away from a process without ill effect (e.g., CPU, main memory). Since the OS can forcibly reclaim such a resource from a holding process and give it to another, the hold-and-wait / no-preemption condition is broken, so a circular wait cannot persist. Deadlock is therefore a problem mainly with non-preemptable resources (e.g., printers, tape drives, file locks), which cannot be taken away until the holder voluntarily releases them.

Necessary (Coffman) Conditions for Deadlock

Deadlock can arise only if all four conditions hold simultaneously:

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 held by others.
3. No Preemption: A resource cannot be forcibly taken from a process; it is released only voluntarily.
4. Circular Wait: A set of processes $\{P_0, P_1, \dots, P_n\}$ exists such that $P_0$ waits for a resource held by $P_1$, $P_1$ for $P_2$, …, and $P_n$ for $P_0$, forming a cycle.

Breaking any one of these (for example, by making resources preemptable, which removes condition 3) prevents deadlock.