GTU 3140702 Operating System (OS) Summer 2025 Solved Paper & Solutions

Program vs Process vs Thread

1. Program:

• A passive entity consisting of a collection of instructions stored on disk as an executable file (e.g., app.exe). Does not consume CPU or RAM.

2. Process:

• An active entity representing a program in execution. Has its own dedicated address space, Program Counter, stack, data, and PCB.

3. Thread:

• The smallest unit of CPU execution within a process, often called a lightweight process.
• Shares the code, data section, and OS resources with peer threads of the same process, but maintains its own private Program Counter, register set, and stack.

Process States and Operating System Queues

A process transitions through five primary states during its lifetime:

Corresponding OS Scheduling Queues:

1. Job Queue: Holds all processes admitted to the system residing on secondary storage.
2. Ready Queue: Resides in main memory holding all processes that are ready and waiting to be allocated CPU time by the Short-Term Scheduler.
3. Device / I/O Queue (Wait Queue): List of processes waiting for a specific I/O device (e.g., disk controller, network card).

1. Core Functions of an Operating System

• Processor Management: Allocates CPU time to processes via scheduling algorithms.
• Memory Management: Dynamically tracks and allocates/deallocates primary memory partitions.
• File System Management: Organizes files into directories and controls access permissions.
• Device Management: Manages I/O devices through unified device drivers and buffers.
• Security & Protection: Protects system resources against unauthorized access.

2. Detailed Explanation of Types of Operating Systems

A. Batch Operating System:

• Users submit jobs on punch cards/tapes to an operator without direct interactive computer access.
• The operator sorts jobs with similar requirements into batches and runs them as a group.
• Pros: Maximizes CPU utilization for heavy sequential workloads.
• Cons: Zero user interaction; long turnaround times; high starvation risk for small jobs.

B. Time-Sharing (Multitasking) Operating System:

• Extends multiprogramming using CPU scheduling (Round Robin) and rapid time-slicing (quantum $\approx 10\text{ to }100\text{ ms}$).
• The CPU switches between active users so rapidly that each user perceives dedicated access to the machine.
• Pros: Immediate user response time; prevents single-process CPU monopolization.
• Examples: Unix, Linux, Windows NT.

C. Real-Time Operating System (RTOS):

• Designed for systems where computational correctness depends strictly on the logical result and the time deadline within which results are produced.
• Hard RTOS: Missing a deadline results in catastrophic failure (e.g., Aircraft flight control, Missile guidance, Pacemakers). No virtual memory used.
• Soft RTOS: Missing a deadline degrades service quality but does not cause total failure (e.g., Video streaming, cellular telephony).

CPU Scheduling Metrics:

1. Turnaround Time (TAT):

• The total interval of time elapsed from the moment a process is submitted to the moment of its final completion.

2. Waiting Time (WT):

• The total amount of time a process spends sitting in the Ready Queue waiting to be allocated CPU execution time.

3. Throughput:

• The total number of complete processes executed and completed per unit of time (e.g., $10\text{ processes/second}$). Higher throughput indicates better system efficiency.

Comparison: FCFS vs SJF vs Round Robin

1. What is a Semaphore?

A Semaphore is an integer synchronization variable introduced by Edsger Dijkstra, accessed strictly through two atomic, indivisible operations:

• wait(S) (or P(S)): Decrements the semaphore value. If $S \le 0$, the calling process blocks.
• signal(S) (or V(S)): Increments the semaphore value. If processes are blocked, one is unblocked.

2. Readers-Writers Problem Implementation

Multiple readers can read concurrently, but a writer requires exclusive access (no other reader or writer allowed).

Shared Variables:

semaphore mutex = 1;  // Protects 'readcount' updates
semaphore rw_mutex = 1; // Mutual exclusion for writers / first reader
int readcount = 0;    // Number of active readers

Writer Process:

do {
    wait(rw_mutex);       // Request exclusive write access

    /* Writing is performed */

    signal(rw_mutex);     // Release write access
} while (1);

Reader Process:

do {
    wait(mutex);
    readcount++;
    if (readcount == 1) {
        wait(rw_mutex);   // First reader locks out all writers
    }
    signal(mutex);

    /* Reading is performed concurrently */

    wait(mutex);
    readcount--;
    if (readcount == 0) {
        signal(rw_mutex); // Last reader releases lock for writers
    }
    signal(mutex);
} while (1);

Shell vs Kernel in Unix

1. Kernel (Core Engine):

• The central, foundational core of the Unix operating system running in privileged Kernel Mode.
• Interacts directly with hardware to manage CPU scheduling, virtual memory, device I/O drivers, and interrupt handling.

2. Shell (Command Interpreter):

• The user-space command-line interface running in User Mode that wraps around the kernel.
• Reads commands typed by the user, parses them, and invokes the appropriate kernel system calls (e.g., bash, sh, zsh).

Coffman's Four Conditions for Deadlock

A deadlock can occur if and only if all four conditions hold simultaneously in a system:

1. Mutual Exclusion:

• At least one resource must be held in a non-shareable mode (only one process can use it at a time).

2. Hold and Wait:

• A process must be currently holding at least one resource and simultaneously waiting to acquire additional resources held by other processes.

3. No Preemption:

• Resources cannot be forcibly confiscated from a process; they can only be released voluntarily by the holding process after completing its task.

4. Circular Wait:

• A closed circular chain of processes $\{P_0, P_1, \dots, P_n\}$ exists such that $P_0$ is waiting for a resource held by $P_1$, $P_1$ is waiting for $P_2$, and $P_n$ is waiting for a resource held by $P_0$.

Banker’s Algorithm for Deadlock Avoidance

The Banker's Algorithm (developed by Edsger Dijkstra) tests for safety by simulating the allocation of predetermined maximum possible resources before granting any request, ensuring the system never enters an Unsafe State.

Data Structures:

Let $n = \text{number of processes}$, $m = \text{resource types}$:

1. Available[m]: Available instances of each resource type.
2. Max[n][m]: Maximum resource demand of each process.
3. Allocation[n][m]: Resources currently allocated to each process.
4. Need[n][m]: Remaining resource need:

Safety Algorithm:

1. Initialize vectors Work = Available and boolean array Finish[i] = false for all $i$.
2. Find an index $i$ such that:

If no such $i$ exists, go to Step 4.

3. Update state:

Go back to Step 2.

4. If Finish[i] == true for all $i$, the system is in a Safe State; the order in which processes finished forms a Safe Sequence.

Internal vs External Fragmentation

Linux/Unix Commands:

1. cat (Concatenate and Display):

• Displays the content of files or concatenates multiple files into one.
• Example: cat file1.txt file2.txt > combined.txt

2. rmdir (Remove Directory):

• Removes an existing empty directory.
• Example: rmdir /home/user/empty_dir

3. sort (Sort Lines):

• Sorts lines of text files alphabetically or numerically.
• Example: sort -n numbers.txt (sorts numbers numerically).

4. chmod (Change Mode / Permissions):

• Modifies read (r=4), write (w=2), and execute (x=1) file permissions for user, group, and others.
• Example: chmod 755 script.sh (Read/Write/Execute for owner; Read/Execute for others).

Page Replacement Algorithms

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3 with 3 Page Frames:

1. FIFO (First-In, First-Out)

Replaces the page that has resided in memory the longest (queue discipline).

• Page Faults: Suffers from Belady’s Anomaly (page faults can increase when frames increase).

2. LRU (Least Recently Used)

Replaces the page that has not been referenced for the longest period of past time.

• Tracks history using stack or counters; provably immune to Belady’s Anomaly.

3. Optimal Page Replacement (OPT / MIN)

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

• Property: Guarantees the absolute lowest possible page-fault rate; used as an ideal theoretical benchmark.

Comparison of Traces:

Security vs Protection in Operating Systems

File Allocation Methods for Disk Space

1. Contiguous Allocation:

• Each file occupies a set of consecutive blocks on disk.
• Pros: Excellent sequential and direct access performance ($O(1)$ block computation).
• Cons: Severe external fragmentation; files cannot easily grow.

2. Linked Allocation:

• Each file is a linked list of disk blocks scattered across the disk; each block contains a pointer to the next block.
• Pros: Zero external fragmentation; dynamic file growth.
• Cons: Slow direct/random access ($O(n)$ traversal); pointer storage overhead.

3. Indexed Allocation (UNIX Inode Model):

• Each file has an Index Block containing an array of pointers to all its data blocks.
• Pros: Fast direct access without external fragmentation.
• Cons: Index block overhead for very small files.

File and Directory Management in Unix/Linux

Unix treats everything as a file (regular files, directories, device drivers, pipes, sockets) organized in a hierarchical inverted-tree namespace rooted at /.

1. Inode (Index Node) Architecture

Every file is managed by a unique numeric metadata structure called an Inode:

• File type and permission bits (rwxr-xr-x).
• Owner UID and Group GID.
• File size in bytes.
• Timestamps: Access (atime), Modification (mtime), Change (ctime).
• Link count (number of hard links).
• Pointers to Data Blocks:
• 12 Direct Pointers (for fast access to small files).
• 1 Single Indirect Pointer.
• 1 Double Indirect Pointer.
• 1 Triple Indirect Pointer (enabling terabyte-scale files).

2. Directory Structure

• A directory in Unix is simply a special file containing a list of pairs:

• The directory file maps human-readable names to underlying inode numbers.
• Every directory contains two default entries: . (current directory) and .. (parent directory).