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

Disk Scheduling Algorithms

When many I/O requests for different cylinders are pending, the OS chooses the order in which to service them so as to minimize total head movement (seek time). Consider the request queue:

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

with the head initially at cylinder 53 (range 0–199).

1. FCFS (First-Come First-Served)

Requests are served strictly in arrival order. Simple and fair, but no optimization, so head movement is large.

Order: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

$$45+85+146+85+108+110+59+2 = \textbf{640 cylinders}$$

2. SSTF (Shortest Seek Time First)

Always service the request closest to the current head position. Better average performance, but may starve far-away requests.

Order: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

$$12+2+30+23+84+24+2+59 = \textbf{236 cylinders}$$

3. SCAN (Elevator)

The head moves in one direction servicing requests until the end of the disk, then reverses. Moving toward 0 first:

Order: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183

$$39+14+14+65+2+31+24+2+59 = \textbf{250 cylinders}$$

4. C-SCAN (Circular SCAN)

Head moves one direction to the end, then jumps back to the start (servicing nothing on the return) and scans again. Gives more uniform wait time. Moving toward 199:

Order: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37

$$12+2+31+24+2+59+16+199+14+23 = \textbf{382 cylinders}$$

5. LOOK

Like SCAN but the head only goes as far as the last request in each direction (does not travel to the physical disk end). Moving toward 0 first:

Order: 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183

$$16+23+51+2+31+24+2+59 = \textbf{208 cylinders}$$

Summary

Conclusion: FCFS is simplest but slowest; SSTF and LOOK minimize movement; SCAN/C-SCAN avoid starvation and give fairer service. C-SCAN provides the most uniform waiting time.

File Allocation Methods

A file-allocation method decides how disk blocks are assigned to files so that disk space is used effectively and files can be accessed quickly.

1. Contiguous Allocation

Each file occupies a set of consecutive blocks on disk. The directory stores only the starting block and the length (number of blocks).

Advantages

• Excellent sequential and direct (random) access — block $i$ of a file starting at $b$ is at $b+i$.
• Minimum seek time, simple to implement.

Disadvantages

• Suffers from external fragmentation.
• Hard to grow a file (may need relocation).
• Requires knowing file size in advance.

2. Linked Allocation

Each file is a linked list of disk blocks scattered anywhere on disk. Each block stores a pointer to the next block; the directory holds the address of the first (and last) block.

Advantages

• No external fragmentation; files can grow easily.
• No need to declare file size in advance.

Disadvantages

• Only efficient for sequential access; direct access is slow (must follow pointers).
• Pointers consume space; a damaged pointer can lose the rest of the file. (FAT is a variant that keeps pointers in a table.)

3. Indexed Allocation

Each file has its own index block that holds an array of disk-block addresses. The $i$-th entry points to the $i$-th block of the file.

Advantages

• Supports direct access efficiently without external fragmentation.
• Files can grow easily.

Disadvantages

• Index block overhead, wasteful for small files.
• Maximum file size limited by index-block size (solved with multilevel/linked index, as in Unix inodes).

Summary

Contiguous Memory Allocation

In contiguous memory allocation, each process is loaded into a single continuous block of physical memory. Memory is divided into partitions, and the OS keeps each process and its data together in one contiguous region. A base (relocation) register and a limit register protect each process and translate logical to physical addresses.

Internal vs. External Fragmentation

Placement Strategies (variable partitioning)

When a process of a given size must be placed, the OS searches the list of free holes:

• First-Fit: allocate the first hole that is large enough. Fast (least search time); tends to leave fragmentation near the start of memory.
• Best-Fit: allocate the smallest hole that is large enough. Searches the whole list; minimizes wasted space per allocation but leaves many tiny unusable holes (more external fragmentation).
• Worst-Fit: allocate the largest available hole. Idea is that the leftover hole stays large enough to be useful; in practice performs poorly and is slow.

Example — Holes: 100K, 500K, 200K, 300K, 600K; process needs 212K.

• First-Fit → 500K hole (first that fits).
• Best-Fit → 300K hole (smallest that fits).
• Worst-Fit → 600K hole (largest).

Conclusion: First-fit and best-fit generally outperform worst-fit in both speed and storage utilization; first-fit is usually the fastest.

Semaphore

A semaphore is an integer synchronization variable, proposed by Dijkstra, that is accessed only through two atomic operations: wait() (P, down) and signal() (V, up). It is used to control access to shared resources and to solve critical-section and process-coordination problems.

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

Binary vs. Counting Semaphore

A counting semaphore initialized to 1 behaves like a binary semaphore.

Monitor

A monitor is a high-level synchronization construct that encapsulates shared data, the procedures that operate on it, and the synchronization into a single abstract data type. Only one process can be active inside the monitor at a time, so mutual exclusion is provided automatically by the compiler/runtime — the programmer need not place explicit wait/signal calls for entry.

Key features

• Mutual exclusion: at most one process executes any monitor procedure at a time.
• Condition variables: declared inside the monitor for finer control, with two operations:
  • x.wait() — the calling process is suspended until another process signals x.
  • x.signal() — resumes one process waiting on x (no effect if none waiting; unlike a semaphore, signal is not stored).

Structure

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

Advantage over semaphores: because mutual exclusion is built in, monitors are less error-prone than semaphores, where a misplaced or missing wait()/signal() can cause deadlock or race conditions. Monitors are used to solve classic problems such as bounded-buffer and dining-philosophers.

Preemptive vs. Non-Preemptive Scheduling

Summary: Preemptive scheduling improves responsiveness and is essential for time-sharing/real-time systems, at the cost of overhead and synchronization concerns; non-preemptive scheduling is simpler and has lower overhead but can make short jobs wait.

RAID (Redundant Array of Independent Disks)

RAID is a technology that combines multiple physical disk drives into one logical unit to improve performance (via parallelism/striping) and/or reliability (via redundancy: mirroring or parity). It is described in terms of RAID levels, each offering a different trade-off between speed, capacity, and fault tolerance.

RAID Level 0 — Striping

• Data is split (striped) across all disks in blocks; no redundancy.
• Advantage: highest read/write performance and full capacity utilization (parallel access).
• Disadvantage: no fault tolerance — if any one disk fails, all data is lost. Needs ≥ 2 disks.

RAID Level 1 — Mirroring

• Every block is duplicated on a second disk (exact copy).
• Advantage: high reliability — data survives a single-disk failure; good read performance.
• Disadvantage: 50% storage overhead (usable capacity is half the total); expensive.

(Other levels: RAID 5 uses block-level striping with distributed parity — good balance of performance, capacity, and fault tolerance; RAID 6 adds double parity; RAID 10 combines mirroring and striping.)

Directory Structure of a File System

A directory is a symbol table that maps file names to their file-control information (location, attributes). The way directories are organized is the directory structure.

1. Single-Level Directory

All files reside in one directory for all users.

• Simple but causes naming collisions (no two files can share a name) and is hard to manage with many files/users.

2. Two-Level Directory

A separate directory for each user (User File Directory), under a Master File Directory.

• Avoids name conflicts between users; supports path names. But no grouping/sharing within a user.

3. Tree-Structured Directory

Directories can contain subdirectories, forming a hierarchical tree with a root.

• Allows logical grouping, absolute/relative path names, and is the most common structure (e.g., Unix, Windows). Each file has a unique path.

4. Acyclic-Graph Directory

Allows shared subdirectories/files via links, so a file can appear in multiple directories — but no cycles allowed.

• Enables sharing; complicates deletion (use reference counts).

5. General-Graph Directory

Permits links including cycles.

• Most flexible but needs cycle detection and garbage collection to handle deletion correctly.

Deadlock and Preemptible Resources

Can deadlock occur with preemptible resources? Generally no. A preemptible resource (e.g., CPU, main memory) can be taken away from a process without harm and given to another, and later returned. Because such a resource can be forcibly reclaimed, the "no-preemption" condition for deadlock is broken, so deadlocks are normally avoidable by reallocating these resources. Deadlocks typically arise only with non-preemptible resources (e.g., printer, tape drive, file lock) that cannot be safely removed mid-use.

Necessary Conditions for Deadlock (Coffman conditions)

All four must hold simultaneously:

1. Mutual Exclusion — at least one resource is held in non-sharable mode (only one process at a time).
2. Hold and Wait — a process holds at least one resource while waiting to acquire additional resources held by others.
3. No Preemption — a resource cannot be forcibly taken; it is released only voluntarily by the holding process.
4. Circular Wait — a closed chain of processes exists, each waiting for a resource held by the next process in the chain.

If any one of these conditions is prevented, deadlock cannot occur.

Spooling (Simultaneous Peripheral Operation On-Line)

Spooling is a technique in which data intended for a slow peripheral device is temporarily placed in a buffer/queue (spool) on disk, so that the CPU and the device can work concurrently instead of waiting for each other. A spooler process later feeds the buffered jobs to the device one at a time.

How it works

• Output is written to a disk spool area rather than directly to the device.
• The device services jobs from the spool at its own speed.
• This decouples a fast producer (CPU/process) from a slow consumer (device), improving overall throughput and allowing overlap of I/O with computation.

Example — Print Spooling

When several users send documents to a single printer, the OS does not make each process wait for the printer. Instead, each print job is stored in a print spool (queue) on disk. The print spooler then prints them one after another in order, while the user programs continue with other work. This is why you can keep working immediately after clicking "Print."

Benefits: better CPU utilization, device sharing among multiple processes, and queued/ordered access to non-sharable devices.

Operating System

An operating system (OS) is system software that acts as an intermediary between the user/application programs and the computer hardware. It manages the computer's resources (CPU, memory, I/O devices, files) and provides a convenient, efficient, and safe environment in which programs can run.

Main Functions

1. Process Management — creating, scheduling, synchronizing, and terminating processes; CPU allocation; deadlock handling.
2. Memory Management — allocating/deallocating main memory, keeping track of which parts are in use, and implementing virtual memory/paging.
3. File Management — creating, deleting, organizing files and directories, and controlling access.
4. Device (I/O) Management — managing device drivers, buffering, caching, and spooling for peripheral devices.
5. Storage / Secondary-Storage Management — disk scheduling, free-space management, and allocation.
6. Security and Protection — user authentication and controlling access to resources.
7. Provides a User Interface — CLI or GUI, and system calls for programs.

Examples: Windows, Linux, macOS, Unix, Android.

Multiprogramming vs. Multitasking

Summary: Multiprogramming focuses on keeping the CPU busy by overlapping I/O and computation, whereas multitasking adds rapid time-sharing of the CPU to give each task/user quick, interactive response.