Operating Systems (OS)

An Operating System (OS) is system software that manages computer hardware and software resources and provides common services for computer programs.

Think of it as the "manager" of your computer.

+---------------------+
|   Your Apps         |
| (Chrome, VS Code)   |
+----------+----------+
| Operating System    |
| (Windows, Linux, macOS) |
+----------+----------+
| Hardware            |
| (CPU, RAM, Disk, GPU) |
+---------------------+

Why Do We Need an OS?

Without OS → You’d write machine code for every CPU instruction.
With OS → You just double-click an app.

Core Functions of an OS

Types of Operating Systems

Key Components of an OS

+---------------------+
|     User Space      |
|  Apps, Libraries    |
+----------+----------+
|     Kernel Space    |
|  [Kernel]           |
|  ├─ Process Mgr     |
|  ├─ Memory Mgr      |
|  ├─ File System     |
|  ├─ Device Drivers  |
|  └─ System Calls     |
+----------+----------+
|     Hardware        |
+---------------------+

Von Neumann Architecture

The Von Neumann Architecture is the foundational design of most modern computers, where a single memory stores both program instructions and data, and the CPU executes instructions in a fetch-decode-execute cycle.

+------------------+
|     Memory       | ← Stores BOTH Instructions & Data
| [1010] [Data]    |
+--------+---------+
         ↑
         |
       CPU
  +------+------+
  |  ALU  |     |
  |  Registers  |
  |  Control    |
  +-------------+

"Stored Program Concept" – Instructions and data are stored in the same memory and are indistinguishable in format.

Core Components

1. CPU (Central Processing Unit) – The Executor

+---------------------+
|        CPU          |
|  +---------------+  |
|  |  ALU          |  | ← Arithmetic Logic Unit (ADD, AND, etc.)
|  +---------------+  |
|  |  Control Unit |  | ← Orchestrates fetch-decode-execute
|  +---------------+  |
|  |  Registers     |  | ← High-speed storage (PC, IR, ACC, etc.)
|  +---------------+  |
+---------------------+

Sub-Components of CPU

2. Memory (RAM) – The Shared Workspace

Memory Address | Content
---------------|---------
0x1000         | LOAD R1, [0x2000]
0x1004         | ADD R1, R2
0x1008         | STORE R1, [0x2008]
0x2000         | 5        ← Data
0x2004         | 3        ← Data

• Stores both:
• Instructions (code)
• Data (variables)
• Random Access: Any location in ~same time
• Volatile: Lost on power off

3. I/O System – The Bridge to the World

Disk → Memory → CPU → Screen

Bus System – The Data Highways

The Bus System is a set of parallel wires (physical or logical) that carry data, addresses, and control signals between CPU, Memory, and I/O.

CPU ↔ [Address Bus] ↔ Memory
CPU ↔ [Data Bus]    ↔ Memory
CPU ↔ [Control Bus] ↔ Memory/I/O

Three Types of Buses

Summary Table

Golden Rule:

"CPU asks Memory for instructions/data using Address Bus, gets them via Data Bus, and uses Control Bus to say READ/WRITE."

CPU Registers (The "Scratchpad")

Instruction Cycle (Fetch-Decode-Execute)

REPEAT FOREVER:
  1. FETCH
     PC → MAR
     Memory[MAR] → MDR → IR
     PC = PC + 1

  2. DECODE
     Decode IR → know operation (ADD, LOAD, etc.)

  3. EXECUTE
     Do the operation (ALU, memory, I/O)
     Update flags if needed

Modes of Execution

Switching: Apps use system calls → trap to kernel mode.

Example: Simple Program in Memory

Memory Address | Content
---------------|---------
0x1000         | LOAD R1, [0x2000]   ← PC points here
0x1004         | LOAD R2, [0x2004]
0x1008         | ADD R1, R2
0x100C         | STORE R1, [0x2008]
0x1010         | HALT

Data:

0x2000: 5
0x2004: 3
→ Result: 0x2008 = 8

Next: Want to see pipelining, interrupts, or real CPU (x86, ARM)?
Ask: "Explain CPU pipelining" or "How does an interrupt work?"

Process Management

1. What is a Program?

A program is a passive set of instructions stored on disk.

hello.c  →  Source
hello.exe → Executable (binary file on disk)

• No CPU, no memory
• Just a file

2. What is a Process?

A process is an active program in execution.

Program (on disk) → OS loads → Process (in RAM + CPU)

3. Process Control Block (PCB) – Process Attributes

PCB is the "ID card" of a process – OS stores all info here.

struct PCB {
    int pid;              // Process ID
    int state;            // Running, Ready, Blocked
    int priority;         // Scheduling priority
    void* pc;             // Program Counter
    void* registers[];    // CPU registers
    void* memory_limits;  // Base/limit
    list open_files;      // File descriptors
    int cpu_time_used;    // Total CPU used
    int arrival_time;     // When it arrived
    int burst_time;       // CPU needed
    // ... more
};

4. Process States (Lifecycle)

5. Process Operations (System Calls)

pid_t pid = fork();     // Creates child
if (pid == 0) exec("ls"); // Child runs ls

6. Scheduling Queues

OS maintains queues of PCBs:

+-------------+     +-------------+     +-------------+
| Ready Queue | →   | Device Queue| →   | Job Queue   |
| (FCFS, RR)  |     | (Disk, Net) |     | (Batch)     |
+-------------+     +-------------+     +-------------+

7. CPU Scheduler & Dispatcher

8. Context Switching

Saving state of current process → Loading state of next process

Process A (Running)
   ↓
Save: PCB_A (PC, registers, SP)
   ↓
Load: PCB_B
   ↓
Process B (Running)

Time: 1–100 μs (overhead)

9. CPU Scheduling Timings

10. Types of Schedulers

11. Summary Diagram

12. Golden Rules

CPU Scheduling Algorithms**

Goal: Maximize CPU utilization, throughput, minimize waiting time, turnaround time, response time.

1. First-Come, First-Served (FCFS)

"Queue at the counter" – Non-preemptive

Avg WT = (0+20+22)/3 = 14

Cons: Convoy Effect – Short jobs wait behind long ones.

2. Shortest Job First (SJF) – Optimal (Non-Preemptive)

"Do small tasks first"

Cons: Starvation for long jobs, needs burst time prediction

3. Shortest Remaining Time First (SRTF) – Preemptive SJF

"If a shorter job arrives, pause current"

Same as SJF if no new arrivals during execution.
With new short job, it preempts.

4. Round Robin (RR) – Preemptive, Time-Sharing

"Everyone gets 1 turn" – Time Quantum (e.g., 4 ms)

Pros: Fair, responsive
Cons: High context switch overhead if quantum too small

5. Priority Scheduling

"VIPs go first" – Preemptive or Non-Preemptive

Cons: Starvation of low-priority jobs
Fix: Aging – Increase priority over time

6. Multilevel Queue Schedulers

Why?

"Fixed priority queues – processes stay in their queue."

+--------------------+
| Queue 0 (RR, q=8)  | ← System processes (Highest)
+--------------------+
| Queue 1 (RR, q=16) | ← Interactive (Foreground)
+--------------------+
| Queue 2 (FCFS)     | ← Batch (Background)
+--------------------+

Pros & Cons

7. Multilevel Feedback Queue (MLFQ)

"Dynamic priority – processes move between queues based on behavior."

+--------------------+
| Q0 (RR, q=8)       | ← New / Short jobs
+--------------------+
| Q1 (RR, q=16)      | ← Used full quantum
+--------------------+
| Q2 (FCFS)          | ← CPU-bound (long jobs)
+--------------------+

Rules of MLFQ

Queue Movement

But in real systems, MLFQ wins because short jobs finish fast.

Aging (Anti-Starvation)

Every 5 seconds:
  for each process in lower queue:
    priority++

Prevents infinite wait.

Real-World Use

MLFQ is the foundation of modern OS schedulers.

Linux CFS

CFS = Completely Fair Scheduler
Goal: Give every process a fair share of CPU time, proportional to its nice value.

• Replaced O(1) and earlier schedulers
• Default in Linux since 2007
• Used in Ubuntu, RHEL, Android, etc.

Core Idea: Virtual Runtime (vruntime)

"The process that has used the least CPU time runs next." "Every nanosecond of CPU is accounted for, and the task that has waited longest (in weighted time) runs to run."

vruntime = actual_runtime × (1024 / weight)

• Lower vruntime → higher priority
• Fairness = equal vruntime over time

Key Concepts

Algorithm

Summary Table: CPU Scheduling

Inter-Process Communication (IPC)

IPC = How processes talk to each other

Process A        Process B
   ↓                ↓
[Shared Memory] OR [Message Passing]

1. Why IPC?

2. Two Models of IPC

IPC Mechanisms

1. Pipes

Unidirectional data channel between related processes (parent-child).
- Anonymous: Created via pipe() → 2 file descriptors (read/write)
- Named (FIFO): mkfifo() → any process can open
Use: Shell pipelines (ls | grep), parent → child data

int pipefd[2];
pipe(pipefd);
write(pipefd[1], "hi", 2);  // Parent
read(pipefd[0], buf, 2);    // Child

• Anonymous Pipe: Parent → Child
• Named Pipe (FIFO): Any process

2. Message Queues

Kernel-persistent queue for structured messages.
- mq_open(), mq_send(), mq_receive()
- Messages have priority
- Survives process crash
Use: Decoupled communication, task queues

mqd_t mq = mq_open("/myqueue", O_CREAT);
mq_send(mq, "data", 4, 0);
mq_receive(mq, buf, size, &prio);

Pros: Decoupled, priority

3. Shared Memory

Fastest IPC: processes map same physical memory.
- shmget(), shmat()
- No kernel copy → zero-copy
- Requires synchronization (semaphore/mutex)
Use: High-performance data sharing (databases, video)

int shmid = shmget(key, 1024, IPC_CREAT);
char* data = shmat(shmid, NULL, 0);
strcpy(data, "Hello");

Fastest but needs synchronization

4. Semaphores

Semaphore – An integer variable used for synchronization and resource counting.
Supports two atomic operations: - wait() (P): Decrement (block if 0) - signal() (V): Increment (wake up waiter)

Types: - Binary Semaphore = 0 or 1 → acts like a lock - Counting Semaphore = N → allows N resources

Mutex vs Semaphore – Key Difference

Mutex = "I own this lock"
Semaphore = "There are 5 slots available"

Producer-Consumer Problem

Problem:
One or more producers generate data → put in a bounded buffer
One or more consumers take data from buffer
Challenges: - Buffer overflow (producer too fast) - Buffer underflow (consumer too fast) - Race condition on buffer access

Solution Using 3 Semaphores

#define BUFFER_SIZE 10
int buffer[BUFFER_SIZE];
int in = 0, out = 0;

// Semaphores
sem_t empty;    // Counts empty slots (init = 10)
sem_t full;     // Counts full slots  (init = 0)
sem_t mutex;    // Binary lock for buffer access (init = 1)

Producer Code

void producer() {
    int item;
    while (1) {
        item = produce_item();

        sem_wait(&empty);    // Wait for empty slot
        sem_wait(&mutex);    // Lock buffer

        buffer[in] = item;   // Critical section
        in = (in + 1) % BUFFER_SIZE;

        sem_post(&mutex);    // Unlock
        sem_post(&full);     // Signal: one more full slot
    }
}

Consumer Code

void consumer() {
    int item;
    while (1) {
        sem_wait(&full);     // Wait for full slot
        sem_wait(&mutex);    // Lock buffer

        item = buffer[out];  // Critical section
        out = (out + 1) % BUFFER_SIZE;

        sem_post(&mutex);    // Unlock
        sem_post(&empty);    // Signal: one more empty slot

        consume_item(item);
    }
}

How Semaphores Solve It

Summary: Semaphores in Producer-Consumer

empty → "How many slots are free?"
full  → "How many items are ready?"
mutex → "Only one at a time can touch buffer"

No overflow, no underflow, no race condition — guaranteed by atomic wait()/signal()

5. Sockets

Bidirectional communication endpoint (local or network).
- UNIX Domain: Local (AF_UNIX) → fast, file-based
- TCP/UDP: Network (AF_INET)
Use: Client-server, microservices, distributed systems

// TCP
socket() → bind() → listen() → accept()
// OR
socket() → connect()

Used in networking, microservices

6. Signals

Asynchronous notification to a process.
- kill(pid, SIGUSR1) → send
- signal(SIGUSR1, handler) → receive
- Limited data (just signal number)
Use: Terminate, pause, custom events (SIGUSR1/SIGUSR2)

kill(pid, SIGUSR1);  // Send
signal(SIGUSR1, handler); // Receive

Asynchronous, limited data

5. Summary Table: IPC

Golden Rules

# Concurrent Programming

Concurrent Programming is the practice of designing and writing programs that can execute multiple tasks at the same time, either by parallel execution on multiple CPU cores or by interleaving operations on a single core.

Sequential:
Task A → Task B → Task C

Concurrent:
Task A  ↘
         ↘  →  Result
Task B  ↗

• Thread: Lightweight execution unit in a process
• Process: Isolated program with own memory
• Critical Section: Code that must run atomically

Why Concurrent Programming?

Concurrency vs Parallelism

All parallel is concurrent, but not all concurrent is parallel. "Concurrency is about structure. Parallelism is about speed."

Models of Concurrent Programming

Challenges & Solutions

Deadlock?

Deadlock = A set of processes are permanently blocked, each holding a resource and waiting for another resource held by another process in the set.

P1 holds R1 → wants R2
P2 holds R2 → wants R1
→ Circular wait → DEADLOCK

4 Necessary Conditions for Deadlock (Coffman Conditions)

All 4 must be true → deadlock possible
Break any one → deadlock impossible

1. Deadlock Prevention

Design system so that at least one of the 4 conditions is never satisfied.

1: Eliminate Mutual Exclusion

Rarely used – most resources are inherently exclusive.

2: Eliminate Hold and Wait

// Example
lock(R1, R2, R3);  // Get all or none
do_work();
unlock(R1, R2, R3);

Cons: - Low resource utilization - Starvation (long list of needs) - Hard to predict all needs

3: Allow Preemption

Used in: - Virtual memory (page stealing) - Some database systems

Cons: - Complex - Not all resources preemptible (printer half-printed)

4: Prevent Circular Wait → MOST PRACTICAL

// Correct
lock(R1);  // 1
lock(R3);  // 3

// Wrong → violates order
lock(R3);  // 3
lock(R1);  // 1 → DENIED or BLOCK

Pros: - Simple - No runtime overhead - Widely used

Cons: - Arbitrary ordering - May reduce concurrency

Prevention Summary Table

2. Deadlock Avoidance

Allow the system to enter unsafe states, but avoid deadlock using runtime checks.

Banker’s Algorithm (Dijkstra)

Safety Algorithm

1. Find a process where Need ≤ Available
2. Assume it finishes → add Allocation to Available
3. Repeat
4. If all finish → Safe, else Unsafe

Example:
Available: [3,3,2]
P1 Need: [1,0,2] → Safe → Run → Release
→ Available becomes [4,3,4]

Pros: Optimal utilization
Cons: Requires future knowledge, high overhead

Used in: Early systems, rarely in modern OS

3. Deadlock Detection

Allow deadlock to occur, then detect and recover.

Resource Allocation Graph (RAG)

graph TD
    P1 --> R1
    P2 --> R2
    R1 --> P2
    R2 --> P1
    style P1 fill:#f96
    style P2 fill:#f96

• Cycle = Possible deadlock
• Cycle + no preemption = Deadlock

Detection Algorithm

1. Mark all processes with no outgoing request
2. Remove them and their resources
3. Repeat
4. If any process remains → Deadlock

Run periodically or on resource request failure

4. Deadlock Recovery

Once detected, break the deadlock.

1: Process Termination

Cons: Lose work

2: Resource Preemption

Used in: Databases (transaction rollback)

Recovery Cost Factors

Real-World Example: Dining Philosophers

Philosopher i:
  think()
  pick_left_chopstick(i)
  pick_right_chopstick((i+1)%5)
  eat()
  put_down()

Deadlock: All pick left → wait for right → cycle

Prevention:

// Break circular wait
if (i == 4) {
  pick_right_first()
} else {
  pick_left_first()
}

Summary Table

Best Practice in Modern Systems

Golden Rules

Multithreading

Multithreading = Running multiple threads within one process.
Threads share memory, code, and file descriptors.

Process
├── Thread 1
├── Thread 2
└── Thread 3
    └── Shared: Heap, Code, Global Vars

Types of Threads

1. User-Level Threads (ULT) – M:1 Model

Process
├── ULT1 → Scheduler (in user space)
├── ULT2 → Runs on one KLT
└── ULT3

Example: Early Java Green Threads, Go (before 1.5)

2. Kernel-Level Threads (KLT) – 1:1 Model

Process
├── KLT1 → Kernel schedules
├── KLT2 → on CPU cores
└── KLT3

Default in Linux (NPTL), Windows, macOS

3. Hybrid Threads (M:N Model)

Process
├── ULT1 → Mapped to KLT1
├── ULT2 → KLT1
├── ULT3 → KLT2
└── Scheduler (user + kernel)

Used in: - Go (goroutines → KLT) - Java (fibers, Project Loom) - Erlang (actors)

Multithreading vs Multiprocessing

When to Use What?

5. Real-World Examples

6. Summary Table

Golden Rules

Memory Management

Memory management is the core OS function that allocates, tracks, protects, and reclaims memory for running programs. It ensures isolation, efficiency, and scalability by abstracting physical RAM into virtual address spaces.

1. Program Loading & Its Types

Program Loading = Process of transferring a program from disk to RAM and preparing it for execution.

Steps in Program Loading

1. User invokes (e.g., ./app, execve() syscall).
2. Loader reads executable file (ELF/PE format).
3. Allocates virtual memory regions:
4. Text (code) – read-only
5. Data – initialized globals
6. BSS – uninitialized (zero-filled)
7. Heap – dynamic allocation
8. Stack – local vars, function calls
9. Loads segments into memory.
10. Performs relocation (adjust addresses).
11. Links libraries (static/dynamic).
12. Sets PC (Program Counter) to entry point.
13. Starts execution.

Types of Program Loading

Example:
gcc -static app.c → Static
python script.py → Dynamic (imports loaded on demand)

2. Main Memory Management

Goal: Allocate physical RAM to processes efficiently.

Two main approaches:

A. Contiguous Allocation

Each process gets one continuous block of memory.

Allocation Strategies

Fragmentation in Contiguous

• External: Free holes too small to use.
• Internal: Allocated block larger than needed.

Solution: Compaction (move processes) → expensive.

B. Non-Contiguous Allocation

Memory divided into fixed or variable units; process can span non-adjacent blocks.

3. Paging (Most Important – Non-Contiguous)

Paging = Divides memory into fixed-size pages (usually 4KB).

• Logical Address Space → divided into pages
• Physical Memory → divided into frames (same size)

Virtual Address:  [ Page Number | Page Offset ]
                   (p bits)     (f bits)

Page Table

Maps virtual page number → physical frame number

Page Table Entry (PTE):
| Valid Bit | Frame Number | Protection | Dirty | ...

Example

• 32-bit address, 4KB page → 20-bit offset, 12-bit page number
• 2^12 = 4096 pages → Page table has 4096 entries
• Each PTE = 4 bytes → Page table size = 16KB

Address Translation

Virtual Address: 0x12345678
→ Page Number: 0x1234
→ Page Offset: 0x5678

Page Table[0x1234] = Frame 0x9ABC
→ Physical Address = 0x9ABC5678

Multi-Level Paging (To Reduce Page Table Size)

Problem: 64-bit system → 2^52 pages → huge page table

2-Level Paging (32-bit)

Page Directory (PD) → Points to Page Tables (PT)
PT → Points to Frames

4-Level Paging (x86-64)

PML4 → PDPT → PD → PT → Frame

• Only used levels are allocated → sparse memory efficient

Translation Lookaside Buffer (TLB)

TLB = Cache of recent page table entries (in CPU)

• Hit: 1–2 cycles
• Miss: Page walk (100+ cycles)

CPU → TLB → Hit? → Physical Address
         ↓ Miss
     Page Walk (MMU) → Load PTE → TLB

• TLB Shootdown: On context switch or page invalidation → flush TLB.

Paging with Hashing (Hashed Page Table)

For 64-bit systems with sparse addresses.

• Hash(Virtual Page Number) → Hash Table Entry
• Handles huge address space efficiently.

4. Segmentation

Segmentation = Divides memory into variable-sized segments based on logical structure.

Segment Table

Segment Base | Limit | Protection

• Address: [Segment Number | Offset]
• Offset < Limit → Valid

Pros

• Logical division
• Easy sharing (e.g., shared library segment)

Cons

• External fragmentation
• Complex management

5. Segmentation + Paging (Paged Segmentation)

Best of both: Logical segments + fixed pages.

Segment Table → Points to Page Table
Page Table → Points to Frames

• Used in some older systems (e.g., Multics)
• Modern OS prefer pure paging (simpler)

Summary Table

Key Advantages of Paging (Why It's Dominant)

Golden Rules

Virtual Memory & Demand Paging

It allows programs to run as if they have more memory than physically available, enables process isolation, and supports efficient memory sharing.

Virtual Memory = An abstraction that gives each process the illusion of a large, private, contiguous memory space, even when physical RAM is limited.

Process A sees: 0x00000000 → 0xFFFFFFFFFFFFFFFF (16 EB)
Process B sees: Same range
→ But they are isolated and mapped to different physical RAM

Key Goals of Virtual Memory

Virtual vs Physical Address Space

How Virtual Memory Works

Paging is the foundation of virtual memory.

• Memory divided into fixed-size pages (usually 4KB).
• Virtual Address = [Page Number | Page Offset]

64-bit Virtual Address:
+--------------------------------------------------+
|  PML4 (9) | PDPT (9) | PD (9) | PT (9) | Offset (12) |
+--------------------------------------------------+

• Physical Memory = divided into frames (same size).
• Page Table maps virtual page → physical frame.

Demand Paging – "Load Only When Needed"

Demand Paging = Pages are loaded from disk into RAM only when accessed (on a page fault).

Why Demand Paging?

• Most programs don’t use all memory at once.
• Startup faster (don’t load entire binary).
• More processes can run (only active pages in RAM).

Page Fault Handling – Step by Step

Valid/Invalid Bit in Page Table

4. Backing Store (Swap Space)

Swap File/Swap Partition on disk stores pages evicted from RAM.

# Linux
swapon /swapfile
free -h
# → Swap: 8GB

• Executable pages: Loaded from original binary (e.g., /bin/ls).
• Anonymous pages (heap, stack): Saved to swap.

5. Page Replacement Algorithms

When RAM is full, OS evicts a page to make room.

Key Metrics

Golden Rules

Thrashing

Thrashing = A severe performance degradation in a virtual memory system where the CPU spends more time handling page faults (swapping pages in/out of disk) than executing actual program instructions.

CPU Utilization: 90% → 10% → 1%
Page Fault Rate: 100/sec → 10,000/sec → 100,000/sec
→ System becomes unresponsive

Why Does Thrashing Happen?

Root Cause: Insufficient Physical RAM

• Too many processes → Total working set > Physical RAM
• OS keeps evicting pages to make room
• Evicted pages are immediately needed again
• → Endless page faults

graph LR
    A[Too Many Processes] --> B[Working Set > RAM]
    B --> C[Frequent Page Faults]
    C --> D[OS Evicts Pages]
    D --> E[Pages Needed Again]
    E --> C
    style C fill:#f96,stroke:#333

Working Set of a process = Set of pages it references in a time window (e.g., last 10 million instructions).

Total RAM = 1 GB
3 processes → 850 MB working set → Fits → Smooth
5 processes → 1.5 GB working set → Thrashing

Thrashing in Action – Step-by-Step

Time 0:
  RAM: [P1 pages] [P2 pages] [P3 pages] → Full

Time 1:
  P4 starts → Needs 200 MB
  OS evicts P1's pages → P4 loads

Time 2:
  P1 runs → Page fault! → Evict P2 → Load P1
  P2 runs → Page fault! → Evict P3 → Load P2
  P3 runs → Page fault! → Evict P4 → Load P3

→ CPU busy with page faults, not work

Symptoms of Thrashing

# Monitor
vmstat 1
# → si/so: swap in/out (high = bad)
# → bi/bo: blocks in/out

sar -B 1
# → pgpgin/s, pgpgout/s

Page Fault Types

Belady’s Anomaly & Thrashing

With FIFO replacement, increasing frames can increase page faults → worsens thrashing.

Reference string: 1,2,3,4,1,2,5,1,2,3,4,5
3 frames → 9 faults
4 frames → 10 faults ← Anomaly

How OS Detects Thrashing

Solutions to Prevent/Recover from Thrashing

1. Increase Physical RAM

2. Best fix: Add more RAM or use faster storage (SSD).

3. Reduce Multiprogramming Degree

4. Suspend/Swap out processes until working sets fit.

5. Improve Locality

6. Optimize code: Reduce random access, use arrays sequentially.

7. Compiler: Better loop ordering.

8. Priority-Based Swapping

9. Swap out low-priority or idle processes first.

10. Working Set Model (Theoretical)

11. OS tracks working set window (Δ).
12. If working set > RAM → suspend process.

Use Local Replacement (not Global) - Each process has fixed frame allocation. - Prevents one process from stealing all frames.

Linux Thrashing Protection

Real-World Example

Laptop: 8GB RAM
Running: Chrome (50 tabs) + VS Code + Docker + Zoom
→ Working set = 12GB
→ Thrashing: Disk LED blinking, UI freezes
→ Fix: Close Chrome tabs or add RAM

Golden Rules to Avoid Thrashing

File System & Disk Management**

File systems and disk management are core OS components that organize, store, retrieve, and protect data on storage devices. They abstract raw disk blocks into user-friendly files and directories, while ensuring performance, reliability, and security.

1. What is a File?

File = A named collection of related data stored on disk.

File Attributes:
- Name: report.pdf
- Type: PDF
- Size: 2.1 MB
- Location: /home/user/docs/
- Permissions: rw-r--r--
- Timestamps: Created, Modified, Accessed
- Owner: user

File Types

2. File System – The Big Picture

File System = Software + Data Structures that manage how files are stored, organized, and accessed on a storage device.

3. Key File System Operations

4. File System Structure on Disk

+---------------------+
| Boot Block          | ← Bootloader (optional)
+---------------------+
| Superblock          | ← FS metadata (size, inodes, blocks)
+---------------------+
| Inode Table         | ← File metadata (size, blocks, perms)
+---------------------+
| Data Blocks         | ← Actual file content
+---------------------+

5. Inode – The Heart of File Metadata

Inode = Index Node – Stores all file metadata except name.

struct inode {
    mode_t     mode;        // Permissions + type
    uid_t      uid;         // Owner
    gid_t      gid;         // Group
    off_t      size;        // Size in bytes
    time_t     atime;       // Access time
    time_t     mtime;       // Modify time
    time_t     ctime;       // Change time
    blkcnt_t   blocks;      // Number of blocks
    blkptr_t   block[15];   // Pointers to data blocks
};

Inode Block Pointers (EXT2/3/4)

12 Direct → 4KB blocks
1 Indirect → 1024 direct pointers
1 Double Indirect → 1024 indirect
1 Triple Indirect → 1024 double
→ Max file: ~2TB

6. Directory Structure

Directory = A special file containing (name, inode) pairs.

Directory Entry:
+--------+----------+
| Name   | Inode #  |
+--------+----------+
| .      | 2        |
| ..     | 2        |
| file.txt | 156      |
| docs/  | 789      |
+--------+----------+

• Hard Link: Multiple names → same inode
• Symbolic Link: File containing path to target

7. Disk Management – Partitioning & Formatting

1. Partitioning

Divides disk into logical sections.

# MBR (Legacy)
Partition 1: /boot (ext4)
Partition 2: / (ext4)
Partition 3: swap

# GPT (Modern)
GUID Partition Table → Up to 128 partitions

Tools: fdisk, gdisk, parted

2. Formatting

Installs file system on partition.

mkfs.ext4 /dev/sda1
mkfs.ntfs /dev/sdb1

8. Popular File Systems

9. Journaling – Crash Recovery

Journal = Log of pending operations before commit.

Write Intent → Journal → Commit → Data Blocks
→ If crash → Replay journal

Types: - Data Journaling: Log data + metadata (slow, safe) - Metadata Journaling: Log metadata only (fast) – EXT3/4 default - Ordered: Write data first, then metadata

10. File System Mounting

Mount = Attach file system to directory tree.

mount /dev/sda1 /home
# → /home now accesses sda1

/ (root)
├── home/
│   └── user/ ← /dev/sda1
├── boot/
└── etc/

Unmount: umount /home

11. Virtual File System (VFS) – Abstraction Layer

VFS = Unified interface for all file systems.

struct file_operations {
    ssize_t (*read) (struct file *, char *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char *, size_t, loff_t *);
    // ...
};

• Allows ls, cat to work on EXT4, NTFS, NFS, procfs

12. Disk Scheduling Algorithms

Optimize disk head movement to reduce seek time.

13. RAID – Disk Redundancy & Performance

14. Disk Caching & Buffering

• Page Cache: RAM cache of disk blocks
• Write-Back: Delay writes → coalesce
• Write-Through: Immediate write

Summary Diagram

Golden Rules