Operating System Concepts: Process, Memory, and Disk Management

Primary Functions of an Operating System

An operating system (OS) is system software that acts as an interface between the user and the computer hardware. Its primary functions are:

• Process Management: Creation, scheduling, and termination of processes.
• Memory Management: Allocation and deallocation of memory.
• File Management: Organization, storage, and retrieval of files.
• Device/I-O Management: Controls peripheral devices.
• Security & Protection: Prevents unauthorized access.

What Is a Batch Processing System?

• A batch operating system groups similar jobs (with the same requirements) together and executes them as a single batch without user interaction.
• A resident monitor reads jobs sequentially from input and submits them to the CPU.
• Advantage: Less idle CPU time; suitable for repetitive tasks.
• Drawback: No interaction; jobs may have long turnaround times.
• Example: Payroll processing, bank statement generation.

The Principle of Concurrency

• Concurrency means the execution of multiple processes (or threads) at the same time, by interleaving instructions on a single CPU or running in parallel on multiple CPUs.
• Goals: Better resource utilization, faster response, and higher throughput.
• Challenges: Race conditions, deadlocks, and starvation—handled by synchronization mechanisms like semaphores, mutexes, and monitors.

Understanding Process States

A process can be in one of the following states during its lifetime:

• New: Process is being created.
• Ready: Process is waiting to be assigned to the CPU.
• Running: Instructions are being executed.
• Waiting/Blocked: Process is waiting for an event (e.g., I/O completion).
• Terminated: Process has finished execution.

Process Identification in a PCB

Process Identification Information stored in a Process Control Block (PCB) includes:

• Process ID (PID): A unique number identifying the process.
• Parent Process ID (PPID)
• User ID: The ID of the user who owns the process.

(Any one is sufficient as the answer; PID is the most common.)

What Is a Resident Monitor?

• A small system program permanently kept ("resident") in main memory in early batch operating systems.
• It controls the sequence and execution of jobs—reads a job, loads it into memory, gives it CPU control, and after completion, takes back control to load the next job.
• It is the predecessor of modern operating systems.

The I/O Subsystem

• The I/O subsystem is the part of the OS that manages communication between the computer and its external (peripheral) devices like keyboards, disks, printers, etc.
• Components: I/O hardware (devices, controllers), device drivers, buffer cache, and interrupt handlers.
• Responsibilities: Buffering, caching, spooling, error handling, device naming, and providing a uniform interface to user programs.

Time-Sharing vs. Multiprogramming OS

Multiprogramming OS

• Multiple jobs are kept in main memory; the CPU switches to another job when the current job goes for I/O.
• Goal: Maximize CPU utilization and throughput.
• No direct user interaction; processes run for long stretches until they block.
• Switching trigger: I/O wait.

Time-Sharing OS (Multitasking)

• The CPU rapidly switches between processes using small time slices (quanta)—every user gets a fair share.
• Goal: Minimize response time; support multiple interactive users simultaneously.
• Direct user interaction (terminals/sessions).
• Switching trigger: Time quantum expiry or I/O wait.

Key Differences

• Time-sharing is a logical extension of multiprogramming.
• Multiprogramming focuses on CPU utilization; time-sharing focuses on user response time.
• Time-sharing requires preemptive scheduling (e.g., Round Robin); multiprogramming can use non-preemptive scheduling.
• Example: Batch processing uses multiprogramming; UNIX and Windows use time-sharing.

Mutual Exclusion Challenges & Solutions

Mutual exclusion ensures that only one process can access a critical section (shared resource) at a time, preventing race conditions.

Challenges

• Race condition: The outcome depends on the order of execution.
• Deadlock: Two or more processes wait indefinitely for each other.
• Starvation: A process never gets a chance to enter the critical section.
• Busy waiting: CPU cycles are wasted while waiting.
• Priority inversion: A high-priority process waits for a low-priority one.

Requirements for a Valid Solution (Critical Section Problem)

• Mutual Exclusion: Only one process can be in the critical section at a time.
• Progress: If no process is in the critical section, a deserving process must be allowed in.
• Bounded Waiting: There must be a limit on how many times other processes can enter the critical section before the current request is granted.

Peterson's Algorithm (Two-Process Software Solution)

// Shared variables
boolean flag[2] = {false, false};
int turn;

// Process i (i = 0 or 1, j = 1 - i)
flag[i] = true;
turn = j;
while (flag[j] && turn == j);   // busy wait

// CRITICAL SECTION

flag[i] = false;                // exit section

It satisfies all three requirements: mutual exclusion, progress, and bounded waiting (each process waits at most once).

Structure and Contents of a PCB

A PCB is a data structure maintained by the OS for every process. It stores all information needed to manage the process.

Contents of a PCB

• Process ID (PID): Unique identifier.
• Process State: New / Ready / Running / Waiting / Terminated.
• Program Counter: Address of the next instruction to be executed.
• CPU Registers: Values of general-purpose registers, stack pointer, etc. (saved during context switch).
• CPU Scheduling Information: Priority, queue pointers, scheduling parameters.
• Memory Management Information: Base/limit registers, page tables, segment tables.
• Accounting Information: CPU time used, time limits, account numbers.
• I/O Status Information: List of open files, allocated I/O devices, pending I/O requests.

Importance

• Used during context switching to save and restore process state.
• Helps the OS keep track of all active processes.
• Forms the basis for the process table maintained by the OS.

Fixed vs. Variable Memory Partitioning

Fixed (Static) Partitioning

• Main memory is divided into a fixed number of partitions of fixed size at system generation time.
• Each partition holds exactly one process. The number of processes is less than or equal to the number of partitions.
• Advantage: Simple to implement.
• Disadvantage: Internal fragmentation—a process smaller than the partition wastes the unused space.
• Disadvantage: Fixed limit on the degree of multiprogramming.

Variable (Dynamic) Partitioning

• Partitions are created dynamically at runtime, of the exact size required by the process.
• When a process leaves, its partition is freed and can be merged with adjacent free space.
• Advantage: No internal fragmentation.
• Disadvantage: Causes external fragmentation—free memory exists but is non-contiguous.
• Solution: Compaction (relocating processes to combine free spaces), which is costly.

Allocation Strategies (Used in Variable Partitioning)

• First-Fit: Allocate the first hole that is large enough.
• Best-Fit: Allocate the smallest hole that fits.
• Worst-Fit: Allocate the largest hole.

Disk Storage Technologies: HDDs vs. SSDs

HDD (Hard Disk Drive)

• Uses spinning magnetic platters and a mechanical read/write head.
• Has moving parts—slower access (seek time + rotational latency ~ ms).
• Lower cost per GB; capacities up to several TB.
• More prone to mechanical failure and sensitive to shock.
• Power consumption is higher due to motors.
• Random access is slow because the head must move to the right track.

SSD (Solid State Drive)

• Uses NAND flash memory chips—no moving parts.
• Access time in microseconds—much faster than HDD (read/write 10–100× faster).
• Higher cost per GB but prices are dropping; capacities up to several TB.
• More durable, shock-resistant, and silent in operation.
• Lower power consumption—better for laptops.
• Limited write cycles (wear leveling needed).

Use Case Summary

• HDD: Large, cheap storage for archives, backups, and bulk data.
• SSD: Operating systems, application loading, and performance-critical workloads.

Multiuser vs. Multiprocessing Systems

Multiuser Operating System

• Allows multiple users to access the same computer system simultaneously, typically through terminals or network connections.
• Each user gets their own session, environment, and protected workspace.
• Uses time-sharing to allocate CPU among users.
• Usually runs on a single CPU (or few CPUs); concurrency is achieved via fast switching.
• Examples: UNIX, Linux servers, mainframes.
• Focus: Fair resource sharing, security, and protection between users.

Multiprocessing Operating System

• The system has two or more CPUs/cores that can execute multiple processes truly in parallel.
• The OS manages the allocation of processes to different CPUs and synchronization between them.
• Goals: Higher throughput, fault tolerance, and faster execution.
• Types:
  • Symmetric Multiprocessing (SMP): All CPUs are peers; they share one OS.
  • Asymmetric Multiprocessing: One master CPU directs other slave CPUs.
• Examples: Modern multi-core desktops, servers (Windows, Linux).

Key Difference

• Multiuser: Many users (logical concurrency).
• Multiprocessing: Many CPUs (physical parallelism).
• A system can be both—e.g., a multi-core Linux server supporting many users.

Layered Operating System Architecture

Layered architecture organizes the OS into hierarchical layers, where each layer uses the services of lower layers and provides services to upper layers.

Typical Layers (Bottom to Top)

• Layer 0: Hardware (CPU, memory, devices).
• Layer 1: CPU Scheduling (low-level scheduler, context switching).
• Layer 2: Memory Management (allocation, paging, virtual memory).
• Layer 3: Device Drivers / I/O Management.
• Layer 4: File System.
• Layer 5: User Programs / Shell / GUI.

Advantages

• Simplicity: Each layer has well-defined functionality.
• Modularity: Changes in one layer do not affect others.
• Easy debugging and maintenance: Issues are isolated to a specific layer.
• Layered design implements information hiding (data abstraction).

Disadvantages

• Performance overhead: Requests from the top layer must travel through all lower layers.
• Defining layer boundaries is difficult; circular dependencies must be avoided.
• Less flexible than microkernel architectures.

Example: THE OS (1968) by Dijkstra used 6 layers.

Deadlock Prevention and Avoidance

Deadlock is a situation where two or more processes are blocked forever, each waiting for a resource held by the other.

Necessary Conditions (Coffman's Conditions)

All four conditions must hold simultaneously for a deadlock to occur:

• Mutual Exclusion: The resource can be used by only one process at a time.
• Hold and Wait: A process holding at least one resource waits for additional resources.
• No Preemption: Resources cannot be forcibly taken from a process.
• Circular Wait: A circular chain of processes exists, each waiting for a resource held by the next.

Deadlock Prevention (Deny One of the Four Conditions)

• Mutual Exclusion: Make resources shareable when possible (e.g., read-only files).
• Hold & Wait: Require a process to request all resources at the start, or release current ones before requesting new ones.
• No Preemption: Allow the OS to preempt resources from waiting processes.
• Circular Wait: Impose a total ordering on resources; require processes to request them in increasing order.

Deadlock Avoidance

• The system uses additional information about future resource needs.
• Resource Allocation Graph (RAG): Used for single-instance resources; checks for cycles before granting.
• Banker's Algorithm: Used for multiple instances; allocates only if the resulting state is safe.
• Safe State: A sequence of processes exists such that each can complete with available + future-released resources.

Comparison

• Prevention is conservative (always avoids deadlock but may waste resources).
• Avoidance is more flexible but requires advance knowledge of maximum resource needs.

Dekker's vs. Peterson's Algorithms

Both are software-based solutions to the critical section problem for two processes; both work without disabling interrupts.

Dekker's Algorithm

• First known correct software solution to the mutual exclusion problem (1965).
• Uses two flags (flag[0], flag[1]) + a turn variable.
• A process indicates intent by setting its flag, then defers to the other if both want to enter—uses turn to break the tie.
• More complex logic with nested while loops.

Peterson's Algorithm

• A simpler version published in 1981.
• Uses two flags + a turn variable, but combines them more elegantly.
• Process logic: set flag[i] = true, set turn = j, then wait while (flag[j] && turn == j).

Comparison

• Both satisfy mutual exclusion, progress, and bounded waiting.
• Peterson's is simpler, more readable, and easier to verify.
• Dekker's has more lines of code and uses extra checks.
• Both use busy-waiting (wasting CPU cycles).
• Both work only for 2 processes; extending to N requires Lamport's bakery algorithm.

Limitations of Both

• Modern CPUs with out-of-order execution may break these algorithms unless memory barriers are used.
• Replaced in practice by hardware atomic instructions (test-and-set, compare-and-swap) and OS-provided mutex/semaphore primitives.

CPU Scheduling: Preemptive SJF vs. Round Robin

Consider the following processes:

(i) Preemptive SJF (Shortest Remaining Time First)

At each tick, schedule the process with the shortest remaining burst time.

Gantt Chart:

| P1 (0-1) | P2 (1-4) | P3 (4-6) | P4 (6-10) | P1 (10-19) |

Trace:

• t=0: Only P1 is available. Run P1 (1 unit, remaining 9).
• t=1: P1(9), P2(3). Run P2.
• t=4: P2 finishes. P1(9), P3(2), P4(arrives @4 with 4). Run P3.
• t=6: P3 finishes. P1(9), P4(4). Run P4.
• t=10: P4 finishes. Run P1 (9 units) until t=19.

Completion Times: P1 = 19, P2 = 4, P3 = 6, P4 = 10.

Turnaround Time (TAT = Completion − Arrival):

• P1: 19 − 0 = 19
• P2: 4 − 1 = 3
• P3: 6 − 3 = 3
• P4: 10 − 4 = 6
• Average TAT: (19 + 3 + 3 + 6) / 4 = 31/4 = 7.75

Waiting Time (WT = TAT − Burst):

• P1: 19 − 10 = 9
• P2: 3 − 3 = 0
• P3: 3 − 2 = 1
• P4: 6 − 4 = 2
• Average WT: (9 + 0 + 1 + 2) / 4 = 12/4 = 3.0

(ii) Round Robin (Quantum = 3)

Gantt Chart:

| P1 (0-3) | P2 (3-6) | P1 (6-9) | P3 (9-11) | P4 (11-14) | P1 (14-17) | P4 (17-18) | P1 (18-19) |

Ready queue trace (arrivals at: P1@0, P2@1, P3@3, P4@4):

• t=0–3: P1 runs (remaining 7). Queue grows: P2(@1), P3(@3), then P1 re-queues.
• t=3–6: P2 runs full burst 3, finishes at t=6.
• t=6–9: P1 runs (remaining 4). P3, P4 queued.
• t=9–11: P3 runs full burst 2, finishes at t=11.
• t=11–14: P4 runs (remaining 1).
• t=14–17: P1 runs (remaining 1).
• t=17–18: P4 runs 1 unit, finishes at t=18.
• t=18–19: P1 runs 1 unit, finishes at t=19.

Completion Times: P1 = 19, P2 = 6, P3 = 11, P4 = 18.

Turnaround Times:

• P1: 19
• P2: 6 − 1 = 5
• P3: 11 − 3 = 8
• P4: 18 − 4 = 14
• Average TAT: (19 + 5 + 8 + 14) / 4 = 46/4 = 11.5

Waiting Times:

• P1: 19 − 10 = 9
• P2: 5 − 3 = 2
• P3: 8 − 2 = 6
• P4: 14 − 4 = 10
• Average WT: (9 + 2 + 6 + 10) / 4 = 27/4 = 6.75

Observation: Preemptive SJF gives lower average waiting time but is theoretical (requires knowing burst time). RR provides fair response time.

Banker's Algorithm Analysis

Deadlock: A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by some other process.

Consider the following snapshot with resources A, B, C. Available = (2, 1, 0).

Step 1: Compute Need Matrix (Need = Max − Allocation)

Step 2: Apply Safety Algorithm

Initial Available = (2, 1, 0). Work = (2, 1, 0).

Check each process for Need ≤ Work:

• P0 need (3,2,1) > Work — skip.
• P1 need (1,1,0) ≤ (2,1,0) — Run P1. Work = Work + Allocation = (2+2, 1+1, 0+2) = (4, 2, 2).
• P0 need (3,2,1) ≤ (4,2,2) — Run P0. Work = (4+1, 2+1, 2+2) = (5, 3, 4).
• P2 need (5,0,1) ≤ (5,3,4) — Run P2. Work = (5+4, 3+0, 4+1) = (9, 3, 5).
• P3 need (7,3,3) ≤ (9,3,5) — Run P3. Work = (9+0, 3+2, 5+0) = (9, 5, 5).
• P4 need (10,1,1) > (9,5,5) — A is short, so FAIL.

Conclusion: P4 cannot finish, so the system is NOT in a safe state with current Available = (2, 1, 0).

Step 3: Can request from P1 for (1, 1, 0) be granted?

• Check: Request ≤ Need[P1] = (1,1,0) ≤ (1,1,0) — True
• Check: Request ≤ Available = (1,1,0) ≤ (2,1,0) — True

Pretend to allocate:

• Available = (2−1, 1−1, 0−0) = (1, 0, 0)
• Allocation[P1] = (3, 2, 2)
• Need[P1] = (0, 0, 0)

Now run safety check again with new Work = (1, 0, 0). No process has Need ≤ (1,0,0) since all need B ≥ 1 or extra A/C. Thus, the state is unsafe.

Hence, the request (1, 1, 0) by P1 CANNOT be granted immediately because granting leads to an unsafe state.

Paging vs. Segmentation Memory Schemes

Paging

• Physical memory is divided into fixed-size blocks called frames.
• Logical memory is divided into same-size blocks called pages.
• A Page Table maps each page to a frame.
• Logical address = (Page number, Offset) → translated to (Frame number, Offset).
• Eliminates external fragmentation (since all frames are the same size).
• Causes internal fragmentation (the last page may be partly empty).
• Hardware support: Page Table Base Register (PTBR), TLB.

Segmentation

• Logical memory is divided into variable-sized segments based on logical units (code, data, stack, etc.).
• Each segment has a name (segment number) and a length.
• A Segment Table stores (base, limit) for each segment.
• Logical address = (Segment number, Offset). Physical address = base + offset (if offset < limit).
• Supports the user's view of memory—matches program structure.
• Causes external fragmentation; no internal fragmentation.

Comparison

Suitability

• Paging suits systems prioritizing efficient physical memory utilization (most modern OSes—Linux, Windows).
• Segmentation suits structured programming and protection at the logical unit level.
• Modern systems use segmentation with paging (e.g., Intel x86): segments are paged for the best of both—logical structure + no external fragmentation.

Virtual Memory Concepts

Virtual memory is a technique that allows the execution of processes that may not be completely in main memory. Programs can be larger than physical memory. Pages are kept on disk (swap space / backing store) and loaded only when needed.

Address Translation

Each logical (virtual) address is divided into two parts:

Virtual Address = (Page Number p, Offset d)

• Page number p is used as an index into the Page Table to find the corresponding frame number f.
• Physical Address = (f × page_size) + d, or simply the concatenation of f and d.

Page Tables

• Maps each virtual page to a physical frame.
• Stored in main memory; pointed to by PTBR (Page Table Base Register).
• Entries include: frame number, valid bit, dirty bit, reference bit, protection bits.
• Multi-level page tables or inverted page tables are used for large address spaces.
• TLB (Translation Look-aside Buffer): A fast cache of recent page table entries to speed up translation.

Demand Paging

• Pages are loaded into memory only when required (lazy loading).
• If a referenced page is not in memory, a page fault occurs.

Page Fault Handling Steps

1. Trap to OS — referenced page is not in memory.
2. OS locates the page on disk.
3. If no free frame, OS uses a page replacement algorithm (FIFO, LRU, Optimal) to evict a page.
4. Read the required page from disk into the chosen frame.
5. Update the page table; set the valid bit.
6. Restart the instruction that caused the fault.

Effective Access Time (EAT) Formula

EAT = (1 − p) × memory_access_time + p × page_fault_service_time

where p = page fault rate.

Advantages of Virtual Memory

• Allows running programs larger than RAM.
• Increases the degree of multiprogramming.
• Better memory utilization.

Issue: Thrashing — if too many page faults occur, the CPU spends most of its time swapping pages instead of executing. This is solved by controlling the degree of multiprogramming (working set model).

File Allocation Methods

File allocation methods determine how disk blocks are assigned to files.

1. Contiguous Allocation

• Each file occupies a set of consecutive blocks on disk.
• Directory stores starting block and length.
• Advantages: Fast access (random + sequential), simple.
• Disadvantages: External fragmentation; difficult to grow files (need contiguous free space).
• Allocation strategy: First-fit, Best-fit, Worst-fit.

2. Linked Allocation

• Each file is a linked list of disk blocks scattered anywhere on disk.
• Each block contains a pointer to the next block.
• Directory stores pointers to the first and last blocks.
• Advantages: No external fragmentation; files can grow easily.
• Disadvantages: Slow random access (must follow pointers); pointer overhead; reliability issues (lost pointer = lost file).
• Variant: FAT (File Allocation Table) — pointers are kept in a separate table (used in DOS, FAT32).

3. Indexed Allocation

• Each file has an index block containing pointers to all its data blocks.
• Directory stores the address of the index block.
• Advantages: Supports direct/random access; no external fragmentation.
• Disadvantages: Wasted space for small files (entire index block reserved).
• For large files, may need multi-level indexing or combined schemes (used in UNIX inode — 12 direct, 1 single-indirect, 1 double-indirect, 1 triple-indirect).

Comparison Summary

File Directory Structures

A directory is a special file containing information (entries) about other files — name, size, location, type, permissions, etc.

Types of Directory Structures

1. Single-Level (Flat) Directory:
   • All files are in one single directory.
   • Advantages: Simple to implement, easy to access.
   • Disadvantages: Naming conflicts (no two files can have the same name); not suitable for multiple users.
2. Two-Level Directory:
   • Each user has their own User File Directory (UFD); a Master File Directory (MFD) points to all UFDs.
   • Resolves naming conflicts between users.
   • Disadvantages: Cannot group related files within a user; sharing files between users is difficult.
3. Tree-Structured (Hierarchical) Directory:
   • Generalizes two-level — directories can contain subdirectories (forming a tree).
   • Each file/directory has an absolute path (from root) or relative path (from current directory).
   • Used in modern OSes (UNIX, Linux, Windows).
   • Advantages: Logical grouping, scalable, easy navigation.
4. Acyclic-Graph Directory:
   • Allows sharing — a file/directory can appear in multiple directories via links (hard or symbolic).
   • Care is needed to avoid dangling pointers when a shared file is deleted.
5. General Graph Directory:
   • Allows cycles — most flexible but introduces challenges like cycle detection during traversal.

Directory Operations

• Search for a file
• Create / Delete a file
• List a directory
• Rename a file
• Traverse the file system (for backup, search)

Comparison: Flat vs. Hierarchical

• Flat is simple but does not scale; hierarchical scales to millions of files.
• Hierarchical supports per-user isolation, security, and logical grouping.
• Modern systems combine hierarchical structures with Access Control Lists (ACLs) for security.

What Is a System Call?

• A system call is a programmatic way in which a user program requests a service from the kernel of the OS.
• It is the interface between a running program and the OS.
• Categories: Process control, File management, Device management, Information maintenance, Communication.
• Examples: fork(), exec(), open(), read(), write(), close(), wait(), exit().

Semaphores and Their Types

A semaphore is an integer variable used as a synchronization tool to control access to shared resources, accessed only through two atomic operations: wait(S) [P] and signal(S) [V].

Types

• Binary Semaphore (Mutex): Takes only values 0 or 1. Used for mutual exclusion.
• Counting Semaphore: Takes any non-negative integer value. Used to control access to a resource with multiple instances (e.g., 5 printers).

What Is Thrashing?

• Thrashing is a condition in which a process spends more time paging (handling page faults) than executing actual instructions.
• Caused by an excessively high degree of multiprogramming — when total memory demand exceeds available RAM.
• CPU utilization drops drastically as the system constantly swaps pages in and out.
• Solution: Working set model, page-fault frequency (PFF) control, or reducing the degree of multiprogramming.

Belady's Anomaly

• Belady's Anomaly is a counter-intuitive phenomenon where increasing the number of page frames leads to more page faults (not fewer).
• Observed in the FIFO page replacement algorithm.
• Algorithms like LRU and Optimal do not suffer from Belady's anomaly (they are stack algorithms).
• Example: For reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames → 9 faults, with 4 frames → 10 faults.

Internal vs. External Fragmentation

• Internal Fragmentation: Memory wasted inside an allocated partition. Occurs when a process is given more memory than it needs. Example: A 100 KB process allocated a 128 KB fixed partition wastes 28 KB.
• External Fragmentation: Free memory is scattered in small non-contiguous blocks that cannot satisfy a process request, even though total free memory is enough. Occurs in variable partitioning.
• Solution: Internal — variable partitioning; External — compaction or paging.

Seek Time and Rotational Latency

• Seek Time: Time taken by the disk arm to move the read/write head to the desired track/cylinder.
• Rotational Latency: Time taken for the desired sector to rotate under the read/write head once the arm is on the correct track. On average = (1 / RPM) × (60 / 2) seconds = half rotation.
• Total Disk Access Time: Seek Time + Rotational Latency + Transfer Time.

What Is RAID?

RAID: Redundant Array of Independent Disks. A technique that combines multiple physical disks into one logical unit for improved performance, reliability, or both.

Common RAID Levels

• RAID 0: Striping (no redundancy). High performance, no fault tolerance.
• RAID 1: Mirroring. Data duplicated on two disks; 100% redundancy.
• RAID 5: Striping with distributed parity. Survives 1 disk failure.
• RAID 10: Combination of RAID 1 and RAID 0. High performance + redundancy.

The Producer-Consumer Problem

Problem Statement

A producer process produces items and places them in a bounded buffer of size N. A consumer process removes items from the buffer. The challenge is to:

• Ensure the producer does not add to a full buffer.
• Ensure the consumer does not remove from an empty buffer.
• Ensure mutual exclusion when accessing the shared buffer.

Solution Using Semaphores

Use three semaphores:

• mutex — binary semaphore for mutual exclusion (init = 1).
• empty — counting semaphore for empty slots (init = N).
• full — counting semaphore for filled slots (init = 0).

Producer Code

do {
    // produce an item
    wait(empty); // wait if buffer is full
    wait(mutex); // enter critical section
    // add item to buffer
    signal(mutex); // exit critical section
    signal(full); // increase count of full slots
} while (true);

Consumer Code

do {
    wait(full); // wait if buffer is empty
    wait(mutex); // enter critical section
    // remove item from buffer
    signal(mutex); // exit critical section
    signal(empty); // increase count of empty slots
    // consume the item
} while (true);

Note: Always acquire empty/full BEFORE mutex to avoid deadlock.

The Dining Philosophers Problem

Problem Statement

Five philosophers sit around a circular table, each alternately thinking and eating. Between every two philosophers is one chopstick (5 chopsticks total). A philosopher needs BOTH adjacent chopsticks to eat. Design a synchronization scheme that prevents deadlock and starvation.

Naive Solution (Causes Deadlock)

// chopstick[i] is a semaphore initialized to 1
do {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    // eat
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    // think
} while (true);

Problem: If all 5 philosophers pick up their left chopstick simultaneously, no one can pick up the right one → deadlock.

Deadlock-Free Solutions

• Allow at most 4 philosophers at the table at once.
• Allow a philosopher to pick up chopsticks only if both are available (atomic check).
• Asymmetric: Odd-numbered philosophers pick left first; even-numbered pick right first.

Solution with a Counting Semaphore (Max 4 Philosophers)

Semaphore room = 4; // max 4 philosophers at a time
Semaphore chopstick[5] = {1,1,1,1,1};

do {
    wait(room);
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    // eat
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    signal(room);
    // think
} while (true);

This guarantees that at least one philosopher can always proceed, eliminating deadlock.

CPU Scheduling: FCFS vs. Priority

Consider the following processes (larger priority number = higher priority):

(i) FCFS (First-Come, First-Served)

Schedule in order of arrival: P1 → P2 → P3 → P4.

Gantt Chart:

| P1 (0-8) | P2 (8-12) | P3 (12-21) | P4 (21-26) |

Completion Times: P1 = 8, P2 = 12, P3 = 21, P4 = 26.

Turnaround Time (TAT = Completion − Arrival):

• P1: 8 − 0 = 8
• P2: 12 − 1 = 11
• P3: 21 − 2 = 19
• P4: 26 − 3 = 23
• Average TAT: (8 + 11 + 19 + 23) / 4 = 61/4 = 15.25

Waiting Time (WT = TAT − Burst):

• P1: 8 − 8 = 0
• P2: 11 − 4 = 7
• P3: 19 − 9 = 10
• P4: 23 − 5 = 18
• Average WT: (0 + 7 + 10 + 18) / 4 = 35/4 = 8.75

(ii) Non-Preemptive Priority

Trace:

• t=0: Only P1 is available → run P1 (burst 8). Runs from 0 to 8.
• t=8: P2, P3, P4 have all arrived. Priorities: P2=1, P3=4, P4=2 → highest priority = P3. Run P3 from 8 to 17.
• t=17: P2 (pri 1), P4 (pri 2) — P4 has higher priority. Run P4 from 17 to 22.
• t=22: Only P2 is left. Run P2 from 22 to 26.

Gantt Chart:

| P1 (0-8) | P3 (8-17) | P4 (17-22) | P2 (22-26) |

Completion Times: P1 = 8, P3 = 17, P4 = 22, P2 = 26.

Turnaround Times:

• P1: 8 − 0 = 8
• P2: 26 − 1 = 25
• P3: 17 − 2 = 15
• P4: 22 − 3 = 19
• Average TAT: (8 + 25 + 15 + 19) / 4 = 67/4 = 16.75

Waiting Times:

• P1: 0
• P2: 21
• P3: 6
• P4: 14
• Average WT: (0 + 21 + 6 + 14) / 4 = 41/4 = 10.25

Observation: FCFS gives lower averages here, but priority scheduling can starve low-priority processes like P2.

Deadlock vs. Starvation

Deadlock

• A situation where two or more processes are blocked forever, each waiting for a resource held by another.
• Caused by circular dependency; processes never progress.
• Permanent unless the OS intervenes (e.g., killing a process, preempting resources).

Starvation

• A situation where a process waits indefinitely for a resource because other processes (typically higher priority) keep getting it first.
• The process is not blocked permanently—it could eventually run if scheduling favors it.
• Caused by unfair scheduling/resource allocation (e.g., priority scheduling without aging).
• Solution: Aging — gradually increasing the priority of waiting processes.

Comparison

Necessary Conditions for Deadlock (Coffman's Conditions)

All four conditions must hold simultaneously for a deadlock to occur. Breaking any one prevents deadlock:

• Mutual Exclusion: Only one process can use a resource at a time.
• Hold and Wait: A process holds at least one resource while waiting for others.
• No Preemption: Resources cannot be forcibly taken away from a process.
• Circular Wait: A circular chain exists where each process waits for a resource held by the next.

User Threads vs. Kernel Threads

User Threads

• Managed by a user-level thread library (e.g., POSIX pthreads in user mode).
• The OS kernel is not aware of these threads—it sees only the process.
• Thread creation, scheduling, and switching are fast (no kernel involvement).
• Disadvantage: If one user thread makes a blocking system call, the entire process blocks (all its threads).
• Cannot exploit multiprocessing—all threads of a process run on one CPU.

Kernel Threads

• Managed directly by the OS kernel.
• The kernel is aware of each thread and schedules them individually.
• A blocking call by one thread does not block others in the same process.
• Can run threads on multiple CPUs (true parallelism).
• Disadvantage: Slower (context switch goes through the kernel).

Comparison

Multithreading Models

Many-to-One Model

• Many user threads map to one kernel thread.
• Fast but no parallelism; one blocking call blocks all.
• Example: Early Solaris green threads.

One-to-One Model

• Each user thread maps to a kernel thread.
• Supports parallelism; blocking is per-thread.
• Drawback: Creating user threads requires creating kernel threads (overhead).
• Example: Linux, Windows.

Many-to-Many Model

• Many user threads are multiplexed onto many (smaller or equal) kernel threads.
• Combines flexibility (no thread cap) and parallelism.
• Example: Solaris before version 9, IRIX.

RAID Levels and Characteristics

RAID: Redundant Array of Independent Disks. Combines multiple physical disks into a single logical unit. Provides improved performance, reliability (fault tolerance), or both.

Characteristics

• Data Striping: Splitting data across multiple disks for parallel access (improves speed).
• Mirroring: Duplicating data on multiple disks (improves reliability).
• Parity: Error-detection/correction information stored to recover lost data.
• Hot Swapping: Replacing a failed disk without shutting down the system.

RAID 0 (Striping)

• Data is split into blocks and striped across N disks.
• Advantages: Very high read/write performance; full disk capacity utilized.
• Disadvantages: No redundancy. Failure of any one disk leads to total data loss.
• Use case: Video editing, gaming, where performance matters more than reliability.

RAID 1 (Mirroring)

• Data is duplicated identically on two (or more) disks.
• Advantages: 100% redundancy—survives any single disk failure. Fast reads (can read from either copy).
• Disadvantages: Only 50% storage efficiency (half capacity wasted). Write is slower (must write to both).
• Use case: Critical data, OS partitions, financial systems.

RAID 5 (Striping with Parity)

• Data and parity blocks are striped across all N disks (parity is rotated). Requires at least 3 disks.
• Advantages: Survives 1 disk failure. Storage efficiency = (N−1)/N. Good read performance.
• Disadvantages: Slow writes (parity must be calculated and updated). Long rebuild time after disk failure. Risk during rebuild—if a second disk fails, all data is lost.
• Use case: File servers, general-purpose enterprise storage.

Summary Table

Banker's Algorithm: Safe State

Consider the following snapshot. Total resources: A=10, B=5, C=7. Available = (3, 3, 2).

Step 1: Compute Need Matrix (Need = Max − Allocation)

Step 2: Safety Algorithm

Start with Work = Available = (3, 3, 2). Finish[i] = false for all i.

• Iteration 1: Find any process Pi with Finish[i] = false and Need[i] ≤ Work.
  • P0 (7,4,3) > Work — skip.
  • P1 (1,2,2) ≤ (3,3,2) — Run P1. Work = Work + Allocation[P1] = (3+2, 3+0, 2+0) = (5, 3, 2). Finish[P1] = true.
• Iteration 2:
  • P0 (7,4,3) > (5,3,2) — skip.
  • P2 (6,0,0) > (5,3,2) — skip.
  • P3 (0,1,1) ≤ (5,3,2) — Run P3. Work = (5+2, 3+1, 2+1) = (7, 4, 3). Finish[P3] = true.
• Iteration 3:
  • P0 (7,4,3) ≤ (7,4,3) — Run P0. Work = (7+0, 4+1, 3+0) = (7, 5, 3). Finish[P0] = true.
• Iteration 4:
  • P2 (6,0,0) ≤ (7,5,3) — Run P2. Work = (7+3, 5+0, 3+2) = (10, 5, 5). Finish[P2] = true.
• Iteration 5:
  • P4 (4,3,1) ≤ (10,5,5) — Run P4. Work = (10+0, 5+0, 5+2) = (10, 5, 7). Finish[P4] = true.

Conclusion: All processes completed. The system is in a SAFE state. Safe Sequence: 〈 P1, P3, P0, P2, P4 〉

CPU Scheduling Criteria & Preemption

CPU Scheduling Criteria

• CPU Utilization: Keep the CPU as busy as possible (target: 40%–90%).
• Throughput: Number of processes completed per unit of time.
• Turnaround Time (TAT): Total time from process submission to completion. TAT = Waiting + Burst + I/O times.
• Waiting Time: Total time a process spends in the ready queue.
• Response Time: Time from submission to first response (important in interactive systems).
• Fairness: Every process gets a fair share of the CPU.

Goals: Maximize CPU utilization and throughput; minimize TAT, waiting time, and response time.

Preemptive Scheduling

• The CPU can be taken away from a running process before it finishes (e.g., on time quantum expiry or arrival of a higher-priority process).
• Examples: Round Robin, Preemptive SJF (SRTF), Preemptive Priority.
• Advantages: Responsive, fair, suitable for time-sharing systems.
• Disadvantages: More context switching overhead; risk of race conditions on shared data.

Non-Preemptive Scheduling

• Once the CPU is given to a process, it keeps it until it terminates or voluntarily yields (blocks for I/O).
• Examples: FCFS, Non-Preemptive SJF, Non-Preemptive Priority.
• Advantages: Low overhead, simple to implement, no synchronization issues during execution.
• Disadvantages: Can lead to long waiting times (convoy effect in FCFS); not suitable for interactive systems.

Comparison

CPU Scheduling: Non-Preemptive SJF vs. RR

Consider the following processes:

(i) SJF (Non-Preemptive)

Trace (decide at each scheduling point based on shortest burst among arrived):

• t=0: Only A is available. Run A (burst 4). Completes at t=4.
• t=4: Arrived = B(7), C(3), D(3), E(5). Shortest = C or D (tie, pick C). Run C (3). Completes at t=7.
• t=7: Remaining = B(7), D(3), E(5). Shortest = D. Run D (3). Completes at t=10.
• t=10: Remaining = B(7), E(5). Shortest = E. Run E (5). Completes at t=15.
• t=15: Run B (7). Completes at t=22.

Gantt Chart:

| A (0-4) | C (4-7) | D (7-10) | E (10-15) | B (15-22) |

Completion Times: A=4, B=22, C=7, D=10, E=15.

Turnaround Time (TAT = Completion − Arrival):

• A: 4 − 0 = 4
• B: 22 − 2 = 20
• C: 7 − 3 = 4
• D: 10 − 3.5 = 6.5
• E: 15 − 4 = 11
• Average TAT: (4 + 20 + 4 + 6.5 + 11) / 5 = 45.5 / 5 = 9.1

Waiting Time (WT = TAT − Burst):

• A: 0
• B: 13
• C: 1
• D: 3.5
• E: 6
• Average WT: (0 + 13 + 1 + 3.5 + 6) / 5 = 23.5 / 5 = 4.7

(ii) Round Robin (Quantum = 2)

Ready queue trace (arrivals: A@0, B@2, C@3, [email protected], E@4):

• t=0–2: A runs (rem 2). Queue: B (arrived @2).
• t=2–4: B runs (rem 5). Queue: A(re-queued), C(@3), D(@3.5), then E will arrive @4.
• t=4–6: A runs (rem 0, finishes at t=6). Queue: C, D, E, B.
• t=6–8: C runs (rem 1). Queue: D, E, B, C.
• t=8–10: D runs (rem 1). Queue: E, B, C, D.
• t=10–12: E runs (rem 3). Queue: B, C, D, E.
• t=12–14: B runs (rem 3). Queue: C, D, E, B.
• t=14–15: C runs (rem 0, finishes at t=15). Queue: D, E, B.
• t=15–16: D runs (rem 0, finishes at t=16). Queue: E, B.
• t=16–18: E runs (rem 1). Queue: B, E.
• t=18–20: B runs (rem 1). Queue: E, B.
• t=20–21: E runs (rem 0, finishes at t=21). Queue: B.
• t=21–22: B runs (rem 0, finishes at t=22).

Completion Times: A=6, B=22, C=15, D=16, E=21.

Turnaround Times:

• A: 6
• B: 20
• C: 12
• D: 12.5
• E: 17
• Average TAT: (6 + 20 + 12 + 12.5 + 17) / 5 = 67.5 / 5 = 13.5

Waiting Times:

• A: 2
• B: 13
• C: 9
• D: 9.5
• E: 12
• Average WT: (2 + 13 + 9 + 9.5 + 12) / 5 = 45.5 / 5 = 9.1

Observation: SJF gives much better average waiting time, but RR is fairer and more responsive.

Page Replacement Algorithms Comparison

Comparison

• FIFO (First-In, First-Out): Replaces the page that came in earliest. Simple but suffers from Belady's anomaly.
• LRU (Least Recently Used): Replaces the page that has not been used for the longest time. Approximates Optimal; needs hardware support (counters or stack).
• Optimal: Replaces the page that will not be used for the longest time in the future. Lowest page faults but theoretical (requires knowing future references).

Reference String: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 (with 3 frames)

(i) FIFO Page Replacement

Total FIFO Faults = 15.

(ii) LRU Page Replacement

Total LRU Faults = 12.

(iii) Optimal Page Replacement

Total Optimal Faults = 9.

Summary Table

Optimal is the lower bound — practical algorithms try to approach it.

TLB Effective Access Time Calculations

Formula

EAT = h × (TLB_time + Memory_access) + (1 − h) × (TLB_time + 2 × Memory_access)

Where:

• On TLB hit: 1 memory access for the data + TLB lookup time.
• On TLB miss: 1 memory access to get the page table entry + 1 memory access for data + TLB lookup time.
• Given: TLB_time = 20 ns, Memory_access = 100 ns.

(i) Hit Ratio h = 0.80

EAT = 0.80 × (20 + 100) + 0.20 × (20 + 200)

EAT = 0.80 × 120 + 0.20 × 220 = 96 + 44 = 140 ns

(ii) Hit Ratio h = 0.95

EAT = 0.95 × (20 + 100) + 0.05 × (20 + 200)

EAT = 0.95 × 120 + 0.05 × 220 = 114 + 11 = 125 ns

Observation: A higher TLB hit ratio drastically reduces effective access time (15 ns saved by going from 80% to 95% hit). This justifies investment in larger/faster TLBs.

Memory Allocation Strategies

Given memory partitions of 100K, 500K, 200K, 300K, 600K (in order), place processes of 212K, 417K, 112K, 426K:

(i) First-Fit

(ii) Best-Fit

All 4 processes fit successfully under Best-Fit.

(iii) Worst-Fit

Comparison & Conclusion

• First-Fit: Fast (stops at first match) but causes early fragmentation; failed at 426K.
• Best-Fit: Slower (scans entire list) but here it placed all 4 processes.
• Worst-Fit: Slowest, leaves large holes — but failed at 426K because the biggest hole got fragmented.

Best-Fit is the most efficient for this workload (all 4 jobs accommodated).

Disk Scheduling Algorithms

A disk has 200 tracks (0–199). The disk arm is at track 143, and the last request was 135. Pending queue: 86, 147, 91, 177, 94, 150, 102, 175, 130.

Direction of last move: 135 → 143 means the head is moving in the direction of increasing track numbers.

(i) FCFS

Service in given order: 86, 147, 91, 177, 94, 150, 102, 175, 130

Movement = |143−86| + |86−147| + |147−91| + |91−177| + |177−94| + |94−150| + |150−102| + |102−175| + |175−130|

Movement = 57 + 61 + 56 + 86 + 83 + 56 + 48 + 73 + 45 = 565 tracks

(ii) SSTF

Always serve the nearest pending request.

Order of service: 147 → 150 → 130 → 102 → 94 → 91 → 86 → 175 → 177

Movement = 4 + 3 + 20 + 28 + 8 + 3 + 5 + 89 + 2 = 162 tracks

(iii) SCAN

Moving toward increasing tracks first, then reversing.

Sorted requests: 86, 91, 94, 102, 130, 147, 150, 175, 177

Service order: 147, 150, 175, 177, then go to end (199), reverse, and service: 130, 102, 94, 91, 86.

Movement = (199 − 143) + (199 − 86) = 56 + 113 = 169 tracks

(iv) C-SCAN

Services only in one direction, then jumps to the start.

Service order: 147, 150, 175, 177, go to 199, jump to 0, then service: 86, 91, 94, 102, 130.

Movement = (199 − 143) + 199 + 130 = 56 + 199 + 130 = 385 tracks

Summary Table

SSTF minimizes head movement; SCAN provides better fairness; C-SCAN provides uniform wait time.

Inter-Process Communication (IPC) Models

Inter-Process Communication (IPC) is a mechanism that allows processes to exchange data and synchronize their actions. It is required because processes have separate address spaces.

1. Shared Memory Model

• A region of memory is shared between two or more processes.
• One process writes to shared memory; others read from it.
• No kernel involvement for actual data transfer once the shared region is established.

Advantages

• Very fast — data is shared at memory speed (no copying).
• Suitable for transferring large amounts of data.

Disadvantages

• Synchronization is the programmer's responsibility (semaphores, mutexes required).
• Risk of data corruption due to race conditions.
• Not directly suitable for distributed systems (processes on different machines).

Example: POSIX shared memory (shmget, shmat), Windows file mapping.

2. Message Passing Model

• Processes communicate by sending and receiving messages via the OS.
• Two basic operations: send(message), receive(message).

Variations

• Direct vs. Indirect — naming the recipient explicitly vs. using a mailbox.
• Synchronous (blocking) vs. Asynchronous (non-blocking).
• Buffered vs. Unbuffered queues.

Advantages

• Easier to implement; no shared memory needed.
• Synchronization is implicit (handled by send/receive primitives).
• Works across networked machines (distributed systems).

Disadvantages

• Slower than shared memory — every message goes through the kernel.
• Overhead of system calls.

Examples: Pipes, sockets, message queues, signals.

Comparison

I/O Management Techniques

(i) Interrupt-Driven I/O

• The CPU issues an I/O command and then continues executing other processes.
• When the I/O device completes the operation, it sends an interrupt signal to the CPU.
• The CPU temporarily suspends current work, jumping to an Interrupt Service Routine (ISR) to handle the result.
• After the ISR completes, the CPU resumes the interrupted process.

Advantages over Polling (Busy Waiting)

• The CPU is not idle while waiting for slow I/O.
• Better CPU utilization, especially with slow devices.

Disadvantages

• Still involves the CPU for every data transfer (one byte/word at a time).
• High overhead for high-speed devices like disks.

(ii) Direct Memory Access (DMA)

• A special hardware controller (DMA controller) transfers data directly between an I/O device and main memory, bypassing the CPU.
• The CPU initiates DMA by providing the source, destination, and size.
• The DMA controller handles the entire transfer.
• When done, the DMA controller interrupts the CPU once (instead of every byte).

Advantages

• Frees the CPU for other work during large I/O transfers.
• Faster — eliminates per-byte CPU overhead.
• Used for high-speed devices: disks, network cards, video, sound.

Disadvantages

• Hardware cost (requires a DMA controller).
• Cycle stealing — DMA temporarily takes the memory bus from the CPU.

(iii) Spooling

• Data destined for a slow output device (like a printer) is first written to a fast intermediate buffer (typically on disk) called a spool.
• A separate background process (spooler) reads from the spool and sends data to the device at its own pace.
• The CPU/process can finish writing quickly without waiting for the slow device.
• Common example: Print spooling. Multiple users can submit print jobs simultaneously — they queue up in the spool, and the printer prints them one by one.

Advantages

• Improves CPU and process throughput (no waiting on slow devices).
• Enables queueing and prioritization of jobs.
• Allows multiple processes to share a non-shareable device gracefully.

Disadvantages

• Requires disk space for the spool buffer.
• Introduces a small latency before output begins.