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

Since the question does not give explicit values, we solve a standard representative data set:

Turnaround Time (TAT) = Completion Time − Arrival Time, Waiting Time (WT) = Turnaround Time − Burst Time.

(a) FCFS (First-Come First-Served)

Execution order = P1, P2, P3, P4, P5 (by arrival).

Average WT $= (0+4+6+6+7)/5 = 23/5 = 4.6$, Average TAT $= (5+7+7+8+10)/5 = 37/5 = 7.4$.

(b) SJF Preemptive (SRTN – Shortest Remaining Time Next)

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

Gantt: P1(0-1) P2(1-2) P3(2-3) P2(3-5) P4(5-7) P5(7-10) P1(10-14)

Average WT $= (9+1+0+2+3)/5 = 15/5 = 3.0$, Average TAT $= (14+4+1+4+6)/5 = 29/5 = 5.8$.

(c) Round Robin (Quantum = 2)

Ready queue serviced in time slices of 2.

Gantt: P1(0-2) P2(2-4) P3(4-5) P4(5-7) P1(7-9) P5(9-11) P2(11-12) P1(12-13) P5(13-14)

Average WT $= (8+8+2+2+7)/5 = 27/5 = 5.4$, Average TAT $= (13+11+3+4+10)/5 = 41/5 = 8.2$.

Conclusion

For this data, SRTN gives the lowest average waiting (3.0) and turnaround (5.8) time, confirming that SJF/SRTN is optimal for minimizing average waiting time, while RR gives the highest because of context-switch overhead but provides better responsiveness.

Deadlock

A deadlock is a situation in which a set of processes is permanently blocked because each process is holding a resource and simultaneously waiting for a resource that is held by another process in the same set. No process can proceed, and the cycle never breaks without external intervention.

Four Necessary Conditions (Coffman conditions)

All four must hold simultaneously for a deadlock:

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 other processes.
3. No Preemption – A resource cannot be forcibly taken away; it is released only voluntarily by the holding process.
4. Circular Wait – There exists a circular chain of processes $P_0 \to P_1 \to \dots \to P_n \to P_0$, where each process waits for a resource held by the next.

Deadlock Avoidance – Banker's Algorithm

Deadlock avoidance uses prior knowledge of the maximum resource demand of each process. The system only grants a request if the resulting state is safe — i.e., there exists a sequence in which all processes can complete. The Banker's algorithm maintains: Available, Max, Allocation, and Need = Max − Allocation.

Example (3 resource types A, B, C; total = 10, 5, 7)

Total allocated = (7 2 5), so Available = (3 3 2).

Safety check: Find a process whose Need ≤ Available, run it, and release its resources.

• Available (3 3 2): P1 Need (1 2 2) ≤ (3 3 2) ✓ → release → Available (5 3 2)
• P3 Need (0 1 1) ≤ (5 3 2) ✓ → Available (7 4 3)
• P4 Need (4 3 1) ≤ (7 4 3) ✓ → Available (7 4 5)
• P0 Need (7 4 3) ≤ (7 4 5) ✓ → Available (7 5 5)
• P2 Need (6 0 0) ≤ (7 5 5) ✓ → Available (10 5 7)

A safe sequence ⟨P1, P3, P4, P0, P2⟩ exists, so the state is safe and no deadlock will occur. If a new request (e.g., P1 requests (1 0 2)) keeps the state safe after the Resource-Request algorithm check, it is granted; otherwise the process must wait.

Resource Allocation Graph (RAG)

A Resource Allocation Graph is a directed graph used to describe the state of resources and processes in a system. It has two kinds of nodes and two kinds of edges:

• Process nodes – drawn as circles ($P_1, P_2, \dots$).
• Resource nodes – drawn as rectangles ($R_1, R_2, \dots$); each dot inside represents one instance of that resource type.
• Request edge $P_i \to R_j$ – process $P_i$ has requested an instance of resource $R_j$.
• Assignment edge $R_j \to P_i$ – an instance of $R_j$ has been allocated to process $P_i$.

Deadlock Detection with Single Instance per Resource

When every resource type has exactly one instance, the RAG reduces to a simpler structure and the following rule holds:

A deadlock exists if and only if the resource allocation graph contains a cycle.

(With multiple instances a cycle is only a necessary, not sufficient, condition — but with single instances, a cycle is both necessary and sufficient.) Detection therefore reduces to cycle detection in a directed graph, which can be done with depth-first search.

Example

Consider resources $R_1, R_2, R_3$ (one instance each) and processes $P_1, P_2, P_3$:

• $R_1 \to P_1$ (R1 allocated to P1), $P_1 \to R_2$ (P1 requests R2)
• $R_2 \to P_2$, $P_2 \to R_3$
• $R_3 \to P_3$, $P_3 \to R_1$

Following the edges gives the cycle:

Since a cycle exists and each resource has a single instance, the system is deadlocked: P1 waits for R2 (held by P2), P2 waits for R3 (held by P3), and P3 waits for R1 (held by P1) — a circular wait that can never resolve. If we remove any one request edge (e.g., P3 does not request R1), the cycle breaks and there is no deadlock.

RAID

RAID (Redundant Array of Independent/Inexpensive Disks) is a technology that combines multiple physical disk drives into a single logical unit to improve performance (through parallelism/striping) and/or reliability (through redundancy/mirroring and parity). The OS sees the array as one drive.

Two RAID Levels

RAID 0 (Striping): Data is split into blocks and striped across multiple disks with no redundancy. It gives the best read/write performance and full capacity utilization, but offers no fault tolerance — failure of any single disk loses all data. Minimum 2 disks.

RAID 1 (Mirroring): Identical copies of data are written to two (or more) disks. It provides high reliability (data survives a disk failure) and fast reads, but storage efficiency is only 50% because every block is duplicated. Minimum 2 disks.

(RAID 5 — block-level striping with distributed parity, tolerating one disk failure with only one disk of overhead — is another commonly cited level.)

Directory Structure of a File System

A directory is a symbol table that maps file names to their file-control-block / metadata, letting users organize and locate files. The common directory structures are:

1. Single-Level Directory – All files reside in one directory. Simple, but every file must have a unique name and it does not scale for multiple users.

2. Two-Level Directory – Each user has a separate User File Directory (UFD), indexed by a Master File Directory (MFD). Allows same file names for different users, but no grouping within a user and limited file sharing.

3. Tree-Structured Directory – A hierarchy with a root and arbitrarily nested subdirectories. Supports grouping, absolute and relative path names, and is the most widely used structure (e.g., Unix, Windows). Each file/directory has one parent.

4. Acyclic-Graph Directory – Allows directories/files to be shared between users via links (hard/symbolic), forming a graph with no cycles. Enables sharing but complicates deletion (dangling pointers / reference counts).

5. General Graph Directory – Permits links freely, possibly creating cycles. Most flexible but needs cycle detection and garbage collection to manage traversal and deletion safely.

Going from single-level to general-graph increases flexibility (sharing, grouping) at the cost of implementation complexity.

Can deadlock occur with preemptive (preemptable) resources?

No. A deadlock generally cannot occur if all resources are preemptable. If a resource can be forcibly taken from a process (preempted) and given to another, then the "No Preemption" condition is violated. Since a deadlock requires all four necessary conditions to hold simultaneously, breaking even one — here, no-preemption — makes deadlock impossible. For example, the CPU and main memory (which can be swapped out) are preemptable, so they rarely cause deadlock; deadlocks instead arise with non-preemptable resources such as printers, tape drives, or file locks.

Conditions for Deadlock (Coffman conditions)

All four must hold at the same time:

1. Mutual Exclusion – a resource is held in non-sharable mode.
2. Hold and Wait – a process holds resources while waiting for others.
3. No Preemption – resources are released only voluntarily.
4. Circular Wait – a circular chain of processes each waiting on the next.

Spooling

Spooling (Simultaneous Peripheral Operations On-Line) is a technique in which data destined for a slow I/O device is temporarily placed in a buffer or queue (the spool, usually on disk) so that the fast CPU/process need not wait for the slow device. A dedicated process (the spooler) then feeds the data to the device at its own pace, decoupling the producer from the consumer.

Benefits: overlaps I/O with computation, allows multiple jobs to share one device, and lets processes "finish" output before the device actually consumes it.

Example – Print Spooling

When several users send documents to a single printer, the OS does not block each process until the printer is free. Instead, each print job is written to a print spool (queue) on disk. The printer daemon/spooler picks jobs from this queue one at a time and sends them to the printer in order. Thus a user's program returns immediately after "printing," the printer is kept busy, and jobs are serialized fairly without conflict. Spooling also avoids deadlock over the printer because the device is only ever accessed by the single spooler process.

Operating System

An Operating System (OS) is a system software that acts as an intermediary between the user/application programs and the computer hardware. It manages hardware resources, provides a convenient environment to execute programs, and controls the overall operation of the computer. Examples: Windows, Linux, macOS, Android.

Main Functions of an Operating System

1. Process Management – Creating, scheduling, synchronizing, and terminating processes; CPU scheduling and inter-process communication.
2. Memory Management – Allocating/deallocating main memory, keeping track of usage, and implementing virtual memory (paging/segmentation).
3. File Management – Creating, deleting, organizing, and controlling access to files and directories on storage.
4. Device (I/O) Management – Managing device drivers, buffering, caching, and spooling to control I/O devices.
5. Storage / Secondary-Storage Management – Disk scheduling, free-space management, and allocation.
6. Security and Protection – Authentication, access control, and protecting resources from unauthorized use.
7. User Interface – Providing a CLI or GUI for user interaction.
8. Resource Allocation & Accounting – Fairly distributing resources among users/programs and tracking usage.

Multiprogramming vs Multitasking

In short, multiprogramming focuses on keeping the CPU busy, whereas multitasking (time-sharing) focuses on giving each task a fair, frequent share of the CPU for fast response.

Process vs Program

A program is a passive entity: a set of instructions stored on disk (an executable file). It does nothing until it is loaded and executed.

A process is an active entity: a program in execution, with an associated program counter, registers, stack, data section, heap, and a Process Control Block (PCB). It is the unit of work in a system.

Thus a process is the runtime instance of a program; running the same program twice creates two distinct processes with separate states.

System Call

A system call is the programmatic interface through which a user program requests a service from the operating-system kernel. It causes a switch from user mode to kernel mode (a trap), the OS performs the privileged operation, and control returns to the program. System calls are the only legitimate entry points into the kernel and are usually wrapped by library functions (e.g., printf uses the write system call).

Types / Categories of System Calls

1. Process Control – create/terminate processes, load/execute, wait, allocate memory. Examples: fork(), exec(), exit(), wait().
2. File Management – create, delete, open, close, read, write files. Examples: open(), read(), write(), close().
3. Device Management – request/release a device, read/write/reposition a device. Examples: ioctl(), read(), write().
4. Information Maintenance – get/set system data such as time, date, attributes. Examples: getpid(), alarm(), time().
5. Communication – create/delete connections, send/receive messages, shared memory. Examples: pipe(), shmget(), send(), recv().
6. Protection – control access to resources, set permissions. Examples: chmod(), umask(), setuid().

Starvation vs Deadlock

Deadlock is a situation where a set of processes are permanently blocked, each waiting for a resource held by another in the set, so none can ever proceed. Starvation (indefinite blocking) is a situation where a process waits indefinitely because resources are continually granted to other (e.g., higher-priority) processes, even though it could run if it got the resource.

In short, every deadlock implies the involved processes are starved, but starvation can occur without a deadlock — it is caused by unfair policy, and is typically cured by aging.