Operating Systems

1. What an Operating System Really Is

The OS has two big jobs

• Resource manager — it shares the CPU, memory, disk and devices between many programs, fairly and safely.
• Extended machine — it hides messy hardware behind simple ideas. You say "open file notes.txt"; you never say "read sector 88123 from platter 2".

What it manages, one line each

Kinds of OS you may be asked to name

• Batch — jobs are collected and run one after another, no user interaction. Old mainframes.
• Multiprogramming — several programs sit in memory. When one waits for disk, the CPU runs another. Goal: keep the CPU busy.
• Time-sharing (multitasking) — switch between programs so fast that every user feels the computer is theirs. Goal: quick response.
• Real-time (RTOS) — must respond within a fixed deadline. Car airbags, pacemakers. Hard real-time: missing a deadline is a failure. Soft: missing it is just bad (video drops a frame).
• Distributed — many machines work together and look like one system.

2. User Mode, Kernel Mode & System Calls

What happens during a system call

1. Your code calls a library function, e.g. printf, which calls write().
2. The library puts the system call number and arguments in registers.
3. It runs a special trap instruction (syscall on x86-64). The CPU jumps into the kernel and switches to kernel mode.
4. The kernel checks the request (is this file yours?), does the work, and puts the result in a register.
5. The CPU switches back to user mode and your code carries on.

Common system calls by group

System calls are slow-ish compared to a normal function call, because of the mode switch and checks. That's why libraries buffer: printf collects text and makes one write() instead of one per character.

3. Kernel Designs

Linux is monolithic but modular. You can load and unload kernel modules (drivers) at runtime with modprobe, so you don't rebuild the kernel for a new device. They still run in kernel mode, though — a bad module can still crash it.

4. Booting Up

1. Power on → firmware. The CPU starts running code stored on a chip on the motherboard: BIOS (old) or UEFI (modern).
2. POST (Power-On Self-Test). Firmware checks RAM, CPU and devices are present and working.
3. Find the boot device. Firmware looks at disks in a set order. BIOS reads the first sector (the MBR, 512 bytes); UEFI reads a bootloader file from a special EFI partition.
4. Bootloader (e.g. GRUB) runs. It lets you pick an OS, then loads the kernel and a small temporary file system (initramfs) into memory.
5. Kernel starts. It sets up memory management, detects hardware, loads drivers and mounts the real root file system.
6. First process. The kernel starts init — today usually systemd — as process ID 1. It starts every other service: networking, logging, the login screen.

5. Programs, Processes & the PCB

What a process looks like in memory

The PCB — the process's ID card

The OS keeps one Process Control Block (PCB) for every process. It's a record of everything needed to pause the process and later resume it exactly where it left off.

In Linux the PCB is a C struct called task_struct. All of them are linked into the kernel's process table.

6. Process States

Suspended states (the 7-state model)

If RAM gets full, the OS can move a whole process out to disk — this is called swapping out. That adds two more states: Ready-Suspended and Blocked-Suspended. Same meaning as before, but the process is on disk instead of in RAM.

The three schedulers

• Long-term scheduler (job scheduler) — decides which new jobs are let into memory. Controls the degree of multiprogramming (how many processes are in memory).
• Short-term scheduler (CPU scheduler) — picks the next ready process to run. Runs very often, every few milliseconds, so it must be fast.
• Medium-term scheduler — swaps processes out to disk and back in, to free memory.

7. Threads

Process vs thread

User-level vs kernel-level threads

• User-level threads are managed by a library inside your program. The kernel doesn't know they exist — it sees one process. Switching is very fast (no system call). But if one thread makes a blocking system call, the whole process blocks, and they can't run on two cores at once.
• Kernel-level threads are known to and scheduled by the OS. One can block while others run, and they can use many cores. Creating and switching them costs a bit more.

Multithreading models (how user threads map to kernel threads)

8. Context Switching

Process A running
   │  timer interrupt / system call / I/O wait
   ▼
Kernel: save A's registers + PC  → PCB(A)
        A.state = ready (or waiting)
        scheduler picks B
        load B's registers + PC  ← PCB(B)
        switch memory map to B's
   ▼
Process B running

Why it matters

• It's pure overhead. While switching, no useful work is done. Typically a few microseconds.
• The hidden cost is bigger: the new process finds the CPU caches and the TLB (section 23) full of the old process's data, so it runs slowly for a while.
• Switching between threads of the same process is cheaper — the memory map stays the same.

What triggers a switch

• A timer interrupt — the process used up its time slice.
• The process makes a blocking system call (reads a file, waits on a lock).
• A higher-priority process becomes ready (in preemptive scheduling).
• The process exits.

9. fork, exec, wait — Zombies & Orphans

#include <unistd.h>
#include <sys/wait.h>

int main() {
    pid_t pid = fork();              // ONE call, returns TWICE

    if (pid < 0) {
        perror("fork failed");
    } else if (pid == 0) {           // child sees 0
        execlp("ls", "ls", "-l", NULL);   // child becomes "ls"
        perror("exec failed");       // only reached if exec fails
    } else {                         // parent sees the child's PID
        int status;
        wait(&status);               // block until child exits
        printf("child done\n");
    }
}

Key facts about fork

• It returns 0 in the child, the child's PID in the parent, and -1 on failure.
• The child gets a copy of the parent's memory, open files and registers. After fork, changes in one don't affect the other.
• Copying all memory would be slow, so Linux uses copy-on-write: both share the same pages until one of them writes, and only then is that page copied.

The classic counting question

fork();
fork();
fork();
printf("hi\n");

Each fork doubles the number of processes. After 3 forks: 2³ = 8 processes, so "hi" prints 8 times. Child processes created = 2ⁿ − 1 = 7. This exact question appears in GATE and campus tests.

Zombie and orphan

10. Scheduling Basics

Preemptive vs non-preemptive

• Non-preemptive — once a process gets the CPU, it keeps it until it finishes or waits for I/O. Simple, but one long job blocks everyone.
• Preemptive — the OS can take the CPU away mid-run (timer, or a more important process arrives). All modern desktop and server OSes do this.

The words every numerical uses

What a good scheduler aims for

• Maximise: CPU utilisation (keep it busy) and throughput (jobs finished per second).
• Minimise: turnaround time, waiting time and response time.
• Be fair: nobody waits forever (no starvation).

11. FCFS, SJF & SRTF

FCFS — First Come, First Served

• Easy to write, no starvation.
• Suffers from the convoy effect: one long CPU-bound job makes many short jobs wait behind it, so the average waiting time is high.

SJF — Shortest Job First

• Catch 1: the OS can't know the future burst time. Real systems guess it from past bursts using an average that weights recent bursts more (exponential averaging: τ(n+1) = α·t(n) + (1−α)·τ(n)).
• Catch 2: long jobs can starve if short ones keep arriving.

SRTF — Shortest Remaining Time First

The preemptive version of SJF. When a new process arrives, compare its burst with the remaining time of the running one. If the newcomer is shorter, switch to it. Even better average waiting time than SJF, at the cost of more switches.

12. Priority, Round Robin & Multilevel Queues

Priority scheduling

• Problem — starvation: a low-priority process may wait forever if high-priority ones keep coming. (Legend says when MIT shut down an old IBM 7094 in 1973, they found a low-priority job submitted in 1967 still waiting.)
• Fix — aging: slowly raise the priority of a process the longer it waits. Eventually it becomes important enough to run.
• Watch the convention: in many textbooks and in Linux nice values, a smaller number means higher priority. The question will say — read it.

Round Robin (RR)

• Designed for time-sharing. Gives good response time; no starvation.
• Quantum too large → it behaves like FCFS.
• Quantum too small → most time is wasted on context switches.
• Rule of thumb: about 80% of CPU bursts should finish within one quantum. Typical values: 10–100 ms.
• With n processes and quantum q, no process waits more than (n − 1) × q before its next turn.

Multilevel queue

Split the ready queue into several queues by type — e.g. system, interactive, batch. Each queue has its own algorithm (RR for interactive, FCFS for batch). The queues themselves have fixed priority: batch runs only when the higher queues are empty. A process stays in its queue forever, so low queues can starve.

Multilevel feedback queue (MLFQ)

Like multilevel queue, but processes move between queues based on how they behave:

Queue 0  (highest)  RR, quantum 8 ms   ← every new process starts here
Queue 1             RR, quantum 16 ms  ← used its full 8 ms? move down
Queue 2  (lowest)   FCFS               ← still CPU-hungry? move down again

Gives up the CPU early (I/O)  → stays high (it's interactive)
Waits too long in a low queue → moved up (aging, prevents starvation)

MLFQ learns which processes are interactive without being told. It's the most general scheduler and the basis of real ones. Linux today uses CFS / EEVDF, which tracks how much CPU time each process has had and always runs the one that has had the least, weighted by priority.

All algorithms at a glance

13. Worked Example — Gantt Charts

Four processes. Times in milliseconds.

FCFS

| P1      | P2   | P3        | P4    |
0         8      12          21      26

        CT    TAT = CT−AT    WT = TAT−BT
P1       8     8 − 0 =  8     8 − 8 =  0
P2      12    12 − 1 = 11    11 − 4 =  7
P3      21    21 − 2 = 19    19 − 9 = 10
P4      26    26 − 3 = 23    23 − 5 = 18
                  total 61         total 35
Average TAT = 61 / 4 = 15.25     Average WT = 35 / 4 = 8.75

SJF (non-preemptive)

At time 0 only P1 is here, so it runs to 8. At 8, P2 (4), P3 (9) and P4 (5) are all waiting. Shortest first: P2, then P4, then P3.

| P1      | P2   | P4    | P3        |
0         8      12      17          26

        CT    TAT    WT
P1       8     8     0
P2      12    11     7
P3      26    24    15
P4      17    14     9
Average TAT = 57 / 4 = 14.25     Average WT = 31 / 4 = 7.75

SRTF (preemptive SJF) and Round Robin (quantum = 4)

SRTF step by step. At 0, P1 starts (needs 8). At 1, P2 arrives needing 4 — less than P1's remaining 7, so P2 takes over. At 2 and 3, P3 (9) and P4 (5) arrive, but P2's remaining time is smaller, so it keeps running to 5. At 5 the remaining times are P1 = 7, P3 = 9, P4 = 5 → P4 runs to 10. Then P1 (7) to 17, then P3 (9) to 26.

SRTF    CT    TAT    WT
P1      17    17     9
P2       5     4     0
P3      26    24    15
P4      10     7     2
Average TAT = 52 / 4 = 13.00     Average WT = 26 / 4 = 6.50

Round Robin step by step. P1 runs 0–4 (4 left). By then P2, P3, P4 have arrived and joined the queue in order; P1 goes behind them. Queue: P2, P3, P4, P1. P2 runs 4–8 and finishes. P3 runs 8–12 (5 left). P4 runs 12–16 (1 left). P1 runs 16–20 and finishes. P3 runs 20–24 (1 left). P4 runs 24–25 and finishes. P3 runs 25–26 and finishes.

RR q=4  CT    TAT    WT    Response (first run − AT)
P1      20    20    12     0 − 0 = 0
P2       8     7     3     4 − 1 = 3
P3      26    24    15     8 − 2 = 6
P4      25    22    17    12 − 3 = 9
Average TAT = 73 / 4 = 18.25     Average WT = 47 / 4 = 11.75
Average response = 18 / 4 = 4.5

14. Inter-Process Communication (IPC)

int fd[2];
pipe(fd);                 // fd[0] = read end, fd[1] = write end
if (fork() == 0) {        // child
    close(fd[1]);
    read(fd[0], buf, sizeof buf);
} else {                  // parent
    close(fd[0]);
    write(fd[1], "hello", 5);
}

Shared memory vs message passing

15. Race Conditions & the Critical Section

Why count++ isn't safe

It looks like one step, but the CPU does three:

count++   is really:   1. load  count into register
                       2. add   1 to register
                       3. store register into count

count = 5. Two threads, interleaved badly:
  T1: load  → reg1 = 5
  T2: load  → reg2 = 5        ← reads before T1 has stored
  T1: add   → reg1 = 6
  T2: add   → reg2 = 6
  T1: store → count = 6
  T2: store → count = 6       ← should be 7. One increment lost.

Three rules every solution must satisfy

1. Mutual exclusion — if one thread is inside the critical section, no other can be.
2. Progress — if nobody is inside and some want to enter, one of them must be allowed in soon. Threads not interested can't block the decision.
3. Bounded waiting — after a thread asks to enter, there's a limit on how many times others can go ahead of it. No one waits forever.

Every critical-section answer is checked against these three. In GATE, a lot of "which of these is correct" questions are really "which rule does this code break".

do {
    entry section      // ask permission
    critical section   // touch shared data
    exit section       // give up permission
    remainder section  // everything else
} while (true);

Peterson's solution (two threads, pure software)

bool flag[2] = {false, false};   // flag[i]: "I want to enter"
int  turn;                       // whose turn it is to go first

// Code for thread i  (the other thread is j = 1 - i)
flag[i] = true;          // I want in
turn = j;                // but you can go first
while (flag[j] && turn == j)
    ;                    // wait while you want in AND it's your turn
/* critical section */
flag[i] = false;         // I'm done

It's polite: each thread says "I want in, but after you". If both want in at once, turn can hold only one value, so exactly one gets through. It satisfies all three rules.

Hardware help: atomic instructions

An atomic operation happens in one unbreakable step — no other thread can see it half-done.

// test_and_set: return the old value and set it to true, in ONE step
bool lock = false;

while (test_and_set(&lock))
    ;                    // spin until the old value was false
/* critical section */
lock = false;

Others: compare-and-swap (CAS) — "if the value is still X, change it to Y" — and atomic increment. All locks are built on these.

A lock that waits in a loop like this is a spinlock. Spinning wastes CPU, so it's only good when the wait will be very short and you have several cores. This kind of waiting is called busy waiting.

16. Mutexes & Semaphores

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&m);
count++;                       // safe now
pthread_mutex_unlock(&m);

Semaphore operations

wait(S)   also called P(S), down(S)       signal(S)  also called V(S), up(S)
{                                          {
    S = S - 1;                                 S = S + 1;
    if (S < 0)                                 if (S <= 0)
        put this thread to sleep                   wake one sleeping thread
        on S's queue;                      }
}

Both run atomically. A negative S tells you how many threads are asleep on it.

The old textbook version is simpler but busy-waits: wait(S) { while (S <= 0); S--; }. The version above sleeps instead of spinning, so it doesn't waste CPU.

Two kinds

• Binary semaphore — value only 0 or 1. Works like a lock.
• Counting semaphore — any value. Starts at the number of identical resources (e.g. 5 database connections). Each user does wait to take one and signal to return it.

A classic GATE-type question

A counting semaphore starts at 7. Then 20 P operations and 15 V operations are done. Final value? 7 − 20 + 15 = 2. (Each P subtracts 1, each V adds 1.)

Mutex vs semaphore

17. Monitors & Condition Variables

Condition variable operations

• wait(cond) — release the monitor lock and sleep. When woken, take the lock back before continuing.
• signal(cond) — wake one sleeping thread (if none sleep, nothing happens — the signal is lost).
• broadcast(cond) — wake all sleeping threads.

// Java: every object is a monitor
class Counter {
    private int value = 0;
    public synchronized void increment() { value++; }   // one thread at a time
}

// Waiting for a condition — always in a loop
synchronized (queue) {
    while (queue.isEmpty())    // NOT "if" — re-check after waking
        queue.wait();
    item = queue.remove();
}

Semaphore signal vs condition signal: a semaphore remembers — signal adds 1 even if nobody is waiting. A condition variable forgets — signal with no waiters does nothing. A favourite interview distinction.

18. Classic Synchronisation Problems

1. Producer–consumer (bounded buffer)

Producers put items into a buffer of size N; consumers take them out. Producers must wait when it's full, consumers when it's empty. This is every job queue, print queue and message queue.

semaphore mutex = 1;   // protects the buffer itself
semaphore empty = N;   // free slots
semaphore full  = 0;   // filled slots

Producer:                       Consumer:
  while (true) {                  while (true) {
    item = produce();               wait(full);    // any item?
    wait(empty);   // any space?    wait(mutex);
    wait(mutex);                    item = remove();
    insert(item);                   signal(mutex);
    signal(mutex);                  signal(empty); // one more free slot
    signal(full);  // one more item consume(item);
  }                               }

2. Readers–writers

Many threads may read shared data at once, but a writer needs it all to itself. Think of a database row or a config file.

semaphore rw_mutex = 1;   // writers (and the first reader) take this
semaphore mutex    = 1;   // protects read_count
int read_count = 0;

Writer:                       Reader:
  wait(rw_mutex);               wait(mutex);
  /* write */                   read_count++;
  signal(rw_mutex);             if (read_count == 1) wait(rw_mutex);  // first reader locks writers out
                                signal(mutex);
                                /* read */
                                wait(mutex);
                                read_count--;
                                if (read_count == 0) signal(rw_mutex); // last reader lets writers in
                                signal(mutex);

This is the "readers-preference" version: as long as readers keep arriving, a writer can starve. A writers-preference version fixes that but can starve readers. Real code uses a read-write lock (pthread_rwlock_t, Java's ReentrantReadWriteLock).

3. Dining philosophers

Five philosophers sit round a table with one chopstick between each pair. To eat, a philosopher needs both neighbouring chopsticks. It models processes needing several shared resources at once.

semaphore chopstick[5] = {1,1,1,1,1};

philosopher(i):
  wait(chopstick[i]);             // left
  wait(chopstick[(i + 1) % 5]);   // right
  eat();
  signal(chopstick[i]);
  signal(chopstick[(i + 1) % 5]);
  think();

Problem: if all five pick up their left chopstick at the same moment, everyone waits forever for the right one — deadlock.

Fixes:

• Allow only 4 philosophers at the table at once (a counting semaphore set to 4).
• Asymmetric: odd-numbered philosophers pick left first, even-numbered pick right first. This breaks the circle.
• Pick up both or neither — check both inside a critical section.
• Number the chopsticks and always pick the lower number first (resource ordering).

19. Deadlock & Its Four Conditions

The four Coffman conditions — all four must hold

1. Mutual exclusion — a resource can be used by only one process at a time (a printer, a lock).
2. Hold and wait — a process holds at least one resource while waiting for another.
3. No preemption — you can't forcibly take a resource away; the holder must give it up.
4. Circular wait — P1 waits for P2, P2 waits for P3, … and the last waits for P1. A closed loop.

These are necessary conditions: if even one is missing, deadlock is impossible. That's the key to preventing it — break any one.

Resource allocation graph (RAG)

A picture of who holds what and who wants what. Circles are processes, squares are resource types, and dots inside a square are instances (e.g. 2 printers = 2 dots).

Reading a RAG

• No cycle → no deadlock. Always.
• Cycle, and every resource has one instance → deadlock. Certain.
• Cycle, but some resources have several instances → maybe deadlock. Another process outside the cycle might release an instance and break it.

Four ways to handle deadlock

20. Prevention, Avoidance & Banker's Algorithm

Prevention — break one condition

Lock ordering in code is exactly the circular-wait fix: if every thread takes lockA before lockB, a loop can't form.

Avoidance — the safe-state idea

• Safe state → no deadlock is possible.
• Unsafe state → deadlock may happen (not must). Unsafe ≠ deadlocked.

Banker's algorithm — the data

Available[j]     = free instances of resource j right now
Max[i][j]        = most of resource j process i will ever need
Allocation[i][j] = what process i holds now
Need[i][j]       = Max[i][j] − Allocation[i][j]     ← compute this first

Worked example

5 processes, 3 resource types. Total instances: A = 10, B = 5, C = 7.

Total allocated = (7, 2, 5). So Available = (10, 5, 7) − (7, 2, 5) = (3, 3, 2).

Safety check: start with Work = Available. Repeatedly find a process whose Need ≤ Work. Let it "finish" and return its Allocation to Work.

Work = (3,3,2)
P0  need (7,4,3) ≤ (3,3,2)?  no — skip for now
P1  need (1,2,2) ≤ (3,3,2)?  YES → Work = (3,3,2) + (2,0,0) = (5,3,2)
P2  need (6,0,0) ≤ (5,3,2)?  no
P3  need (0,1,1) ≤ (5,3,2)?  YES → Work = (5,3,2) + (2,1,1) = (7,4,3)
P4  need (4,3,1) ≤ (7,4,3)?  YES → Work = (7,4,3) + (0,0,2) = (7,4,5)
P0  need (7,4,3) ≤ (7,4,5)?  YES → Work = (7,4,5) + (0,1,0) = (7,5,5)
P2  need (6,0,0) ≤ (7,5,5)?  YES → Work = (7,5,5) + (3,0,2) = (10,5,7)

All finished → SAFE.  Safe sequence: <P1, P3, P4, P0, P2>

Sanity check: the final Work (10, 5, 7) equals the total — every instance came back. If your final Work doesn't match the total, you've made an arithmetic slip.

Should a new request be granted?

P1 asks for (1, 0, 2).

1. Is it ≤ P1's Need (1, 2, 2)? Yes.
2. Is it ≤ Available (3, 3, 2)? Yes.
3. Pretend to grant it: Available = (2, 3, 0), P1 Allocation = (3, 0, 2), P1 Need = (0, 2, 0).
4. Run the safety check on that pretend state: P1 (0,2,0) ≤ (2,3,0) → Work (5,3,2); P3 → (7,4,3); P4 → (7,4,5); P0 → (7,5,5); P2 → (10,5,7). Safe.
5. So the request is granted. If it had been unsafe, P1 would wait and the pretend state would be thrown away.

Why it isn't used much in real OSes: processes rarely know their maximum needs, the number of processes changes all the time, and running the check on every request is slow (about m × n² steps for m resource types and n processes).

21. Detection, Recovery, Livelock & Starvation

Detection

• One instance per resource: simplify the RAG into a wait-for graph (just processes; an edge P1 → P2 means "P1 waits for P2"). Any cycle = deadlock.
• Several instances: run a Banker's-style check using current requests instead of maximum needs. Processes that can't finish are deadlocked.
• How often to check? Every request is expensive. Common choice: every so often, or when CPU use suddenly drops.

Recovery

• Kill processes — kill all deadlocked ones (simple, wasteful), or kill one at a time until the cycle breaks (pick the cheapest victim: lowest priority, least work done).
• Preempt resources — take a resource from one process and give it to another. The victim must be rolled back to a safe earlier point, often restarted.
• Make sure the same process isn't picked as victim every time, or it starves.

Databases do this all the time: they detect a deadlock between two transactions and abort one, which your app sees as an error to retry.

Deadlock vs livelock vs starvation

Deadlock always involves a cycle of waiting. Starvation doesn't — the system as a whole is making progress, just not for one unlucky process. Aging fixes starvation; random back-off (wait a random time before retrying) fixes livelock.

22. Memory Basics & Fragmentation

Address binding — when is the real address decided?

The simplest MMU: base and limit registers

physical = base + logical          if logical < limit
                                   else → trap: "segmentation fault"

base = 14000, limit = 3000
logical 346   → 14000 + 346 = 14346   ✓
logical 3500  → 3500 ≥ 3000 → trap    ✗ (outside its memory)

The limit check is what stops one process reading another's memory. Only the kernel can change base and limit.

Contiguous allocation

The oldest approach: each process gets one continuous block of RAM. As processes come and go, free memory becomes scattered gaps called holes. Where do you put a new process?

• First fit — the first hole big enough. Fast.
• Best fit — the smallest hole big enough. Leaves tiny useless leftovers.
• Worst fit — the biggest hole. Leaves a big, still-useful leftover — in theory.

Classic example. Holes (in order): 100, 500, 200, 300, 600 KB. Processes arrive: 212, 417, 112, 426 KB.

Here best fit placed all four. In practice, first fit and best fit do about equally well, and both beat worst fit. First fit is usually preferred because it's faster.

Fragmentation — wasted memory

Picture it: internal is a 5-seater car carrying 3 people — 2 seats wasted inside. External: a car park with five single empty spaces scattered about, but you're towing a trailer and need two together.

23. Paging & the TLB

Splitting an address

A logical address is split into a page number (p) and an offset (d) — how far into the page. With page size 2ⁿ, the lowest n bits are the offset.

page number p = logical address ÷ page size   (integer division)
offset      d = logical address mod page size
physical      = frame number × page size + d

The numbers in the diagram. Page size 1 KB = 1024 bytes. Logical address 2500 → p = 2500 ÷ 1024 = 2, d = 2500 − 2048 = 452. Page table says page 2 is in frame 5. Physical = 5 × 1024 + 452 = 5572.

Counting bits (very common in GATE)

32-bit logical address, 4 KB pages (4 KB = 2^12 bytes)
  offset bits      = 12
  page-number bits = 32 − 12 = 20      → 2^20 ≈ 1 million pages
  page table size  = 2^20 entries × 4 bytes each = 4 MB  — per process!

Physical memory 1 GB = 2^30, frame size 4 KB = 2^12
  number of frames = 2^30 / 2^12 = 2^18   → frame number needs 18 bits

Paging still has internal fragmentation: a process needing 4097 bytes with 4 KB pages uses 2 pages and wastes 4095 bytes in the last one. On average, half a page per process.

The TLB — making paging fast

With a page table in RAM, every memory access would need two accesses: one for the page table, one for the data. That halves speed.

The TLB (Translation Lookaside Buffer) is a tiny, very fast cache inside the CPU holding recent page → frame translations. Thanks to locality (programs keep using the same few pages), hit rates are usually above 99%.

Effective Access Time (EAT)
  TLB lookup = 20 ns, memory access = 100 ns, TLB hit ratio = 80%

  hit:  20 + 100       = 120 ns   (TLB, then data)
  miss: 20 + 100 + 100 = 220 ns   (TLB, page table, then data)

  EAT = 0.80 × 120 + 0.20 × 220 = 96 + 44 = 140 ns
  Without a TLB it would be 200 ns; perfect hits would give 120 ns.

24. Multi-level Page Tables & Segmentation

Why one big page table doesn't work

We just saw a 32-bit system needs a 4 MB page table per process, and it must be contiguous. 100 processes = 400 MB of page tables, mostly describing memory nobody uses. On 64-bit systems a flat table would be impossibly huge.

Two-level (hierarchical) paging

32-bit address, 4 KB pages, 4-byte entries:

| p1 (10 bits) | p2 (10 bits) | offset (12 bits) |
   outer index    inner index    within the page

outer table: 2^10 entries × 4 B = 4 KB  (fits exactly in one page)
each inner table: also 4 KB, created only if needed

64-bit x86 uses 4 levels (9 + 9 + 9 + 9 + 12 bits = 48-bit addresses), newer chips 5. The cost: a TLB miss now needs several memory reads — which is why the TLB matters so much.

Other options worth naming: inverted page table — one entry per physical frame instead of per page, so its size depends on RAM, not on how many processes there are (slower lookup, needs hashing). Hashed page table — hash the page number into a table; common for large address spaces.

Segmentation

Segment table:   seg   base    limit
                  0    1400    1000
                  1    6300     400
                  2    4300     400

(2, 53)   → 53 < 400  → physical = 4300 + 53 = 4353   ✓
(2, 500)  → 500 ≥ 400 → trap (segmentation fault)     ✗
(0, 999)  → 999 < 1000 → 1400 + 999 = 2399           ✓

Segmented paging combines them: split into segments, then page each segment. Gets segmentation's logical view without external fragmentation. x86 historically did this; modern 64-bit OSes mostly use plain paging and keep segments flat.

25. Virtual Memory & Page Faults

What you get from it

• Programs can be bigger than RAM.
• More programs fit in memory at once, since each only keeps its active pages.
• Faster start-up — you don't load the whole program first.
• Easy sharing (shared libraries mapped into many processes) and copy-on-write after fork.

The valid bit

Each page-table entry has a valid/invalid bit. Valid = the page is in RAM. Invalid = it's on disk (or not part of the process at all). Other bits worth knowing: dirty (modified since loading — must be written back before eviction), referenced (used recently — helps replacement), and protection (read/write/execute).

What happens on a page fault

A page fault is the trap the MMU raises when a process touches a page marked invalid.

1. The CPU traps into the kernel.
2. The kernel checks: is this address legal for the process? If not → kill it (segfault).
3. If legal, find a free frame. If none is free, pick a victim page to evict (section 26). If the victim is dirty, write it to disk first.
4. Schedule a disk read to bring the page into the frame. The process waits meanwhile; others run.
5. Update the page table: set the frame number and mark it valid.
6. Restart the instruction that faulted. This time it works.

How much a page fault costs

Memory access = 200 ns,  page fault service = 8 ms = 8,000,000 ns
Page fault rate p

EAT = (1 − p) × 200 + p × 8,000,000

If p = 1/1000:
EAT = 0.999 × 200 + 8,000
    = 199.8 + 8,000 ≈ 8,200 ns   → about 40× slower than normal!

To stay within 10% of 200 ns (EAT ≤ 220):
  200 + p × 7,999,800 ≤ 220  →  p ≤ 0.0000025   (fewer than 1 in 400,000)

That's the whole point of the next two sections: a disk is around 100,000× slower than RAM, so page faults must be very rare.

26. Page Replacement

The algorithms

• FIFO — evict the page that has been in memory the longest. Simple queue. But the oldest page might be the most used one.
• Optimal (OPT / Belady's MIN) — evict the page that will next be used furthest in the future. Gives the fewest faults possible. Impossible in practice (needs the future) — used as a yardstick to measure others.
• LRU (Least Recently Used) — evict the page not used for the longest time. Uses the past to guess the future. Very good, but tracking exact order on every access is costly.
• Clock (Second Chance) — a cheap LRU approximation. Pages sit in a circle with a reference bit. The "hand" moves round: bit = 1 → clear it and skip (second chance); bit = 0 → evict. Real OSes use variants of this.
• LFU / MFU — least / most frequently used. Rarely used; mentioned for completeness.

Worked example — 3 frames

Reference string (the order pages are used): 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Each cell shows the frames after that reference. F = page fault, blank = hit.

FIFO    = 15 faults
LRU     = 12 faults
Optimal =  9 faults     (no algorithm can do better on this string)

Hit ratio for LRU = (20 − 12) / 20 = 40%

How to do it fast in an exam. FIFO: keep a queue, evict the front. LRU: look backwards from the current position; the page whose last use is furthest back goes. Optimal: look forwards; the page whose next use is furthest away (or never) goes.

Belady's anomaly

Reference string: 1 2 3 4 1 2 5 1 2 3 4 5   (FIFO)

3 frames:  1F 2F 3F 4F 1F 2F 5F 1  2  3F 4F 5     → 9 faults
4 frames:  1F 2F 3F 4F 1  2  5F 1F 2F 3F 4F 5F    → 10 faults  (more!)

LRU and Optimal never suffer from it. They are stack algorithms: the set of pages kept with n frames is always a subset of the set kept with n + 1 frames. FIFO doesn't have that property.

27. Thrashing & the Working Set

The vicious circle

too many processes → each has too few frames → lots of page faults
→ processes wait on disk → CPU use drops
→ OS thinks "CPU is idle, let's admit more processes"
→ even fewer frames each → even more faults …   (collapse)

On a graph of CPU use vs number of processes, use rises, peaks, then falls off a cliff. That cliff is thrashing.

Locality and the working set

Locality of reference: at any moment, a program uses a small group of pages heavily (the current function, its data). That group is its locality, and it shifts over time.

The working set is the set of pages a process used in its last Δ references (Δ is a window, e.g. the last 10,000 accesses).

Δ = 5, recent references: … 2 6 1 5 7 7 7 7 5 1 | now
working set over the last 5 refs (7 7 7 5 1) = {1, 5, 7}  → size 3

D = sum of all processes' working-set sizes
If D > total frames → thrashing is coming → suspend a process
If D is well below   → room to admit another process

Other fixes

• Page-fault frequency (PFF) — set an upper and lower fault rate. Above the upper → give the process more frames. Below the lower → take some away.
• Reduce multiprogramming — swap out or suspend some processes.
• Local replacement — a process can only evict its own pages, so one thrashing process can't drag others down.
• And the honest real-world one: add more RAM.

28. File Systems

What a file has

• Data — the content.
• Metadata — size, owner, permissions, timestamps (created, modified, accessed), and where its blocks are.
• Operations: create, open, read, write, seek (jump to a position), close, delete.

When you open a file, the OS returns a small number called a file descriptor (fd). Every later read/write uses that number. 0, 1 and 2 are always stdin, stdout and stderr.

Directory structures

• Single-level — all files in one folder. Names clash quickly.
• Two-level — one folder per user.
• Tree — folders within folders. What you use every day. Paths are absolute (/home/ada/notes.txt) or relative (../notes.txt).
• Acyclic graph — a tree plus links, so one file can appear in two folders.

How a file's blocks are stored — allocation methods

Inodes (Unix's indexed scheme)

In Unix/Linux every file has an inode — a record with all the metadata except the name, plus pointers to the data blocks. The name lives in the directory, which is just a list of name → inode number pairs.

inode
├── owner, permissions, size, timestamps, link count
├── 12 direct pointers        → data blocks
├── 1 single indirect pointer → a block full of pointers → data blocks
├── 1 double indirect pointer → pointers → pointers → data
└── 1 triple indirect pointer → three levels deep

Block 4 KB, pointer 4 B → one block holds 1024 pointers
  direct:          12 × 4 KB          = 48 KB
  single indirect: 1024 × 4 KB        = 4 MB
  double indirect: 1024² × 4 KB       = 4 GB
  triple indirect: 1024³ × 4 KB       = 4 TB

Small files (most files) are reached in one step through direct pointers. Huge files are still possible through the indirect ones. GATE often asks for the max file size — add up all four lines.

Hard links vs soft links

Picture it: a hard link is a second front door into the same house. A soft link is a note on a door saying "the house is at 12 Baker Street" — if the house is demolished, the note still exists but leads nowhere.

Journaling — surviving a crash

Creating a file touches several places: the inode, the directory, the free-block list. If power fails halfway, the file system is left inconsistent. Old systems ran a slow full check (fsck) on reboot.

A journaling file system first writes a note of what it's about to do into a log (the journal), then does it, then marks the note done. After a crash it just replays or discards unfinished notes — seconds, not hours. Same idea as a database's write-ahead log. Examples: ext4, NTFS, XFS. (Newer ones like Btrfs, ZFS and Apple's APFS use copy-on-write instead: never overwrite, write new and switch the pointer.)

29. Disk Scheduling

Disk access time

access time = seek time + rotational latency + transfer time
              (move arm)   (wait for sector     (read the data)
                            to spin under head)

Average rotational latency = half a rotation.
7200 RPM → 7200/60 = 120 rotations per second → 1 rotation = 8.33 ms
         → average latency = 4.17 ms

The algorithms

• FCFS — in order of arrival. Fair, but lots of back-and-forth.
• SSTF (Shortest Seek Time First) — always go to the nearest request. Much less movement, but far-away requests can starve.
• SCAN (elevator) — move in one direction to the end of the disk, serving requests on the way, then reverse.
• C-SCAN (circular SCAN) — move in one direction to the end, then jump back to the start without serving, and sweep again. More even waiting times.
• LOOK / C-LOOK — like SCAN / C-SCAN, but only go as far as the last request, not the physical end.

Worked example

Cylinders 0–199. Head at 53, moving towards higher numbers. Queue: 98, 183, 37, 122, 14, 124, 65, 67.

FCFS:   53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
        45 + 85 + 146 + 85 + 108 + 110 + 59 + 2           = 640

SSTF:   53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
        12 + 2 + 30 + 23 + 84 + 24 + 2 + 59               = 236

SCAN:   53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 37 → 14
        (199 − 53) + (199 − 14) = 146 + 185               = 331

C-SCAN: 53 → … → 183 → 199 → jump to 0 → 14 → 37
        146 + 199 (jump) + 37                             = 382
        (183 if the question says not to count the jump)

LOOK:   53 → 65 → 67 → 98 → 122 → 124 → 183 → 37 → 14
        (183 − 53) + (183 − 14) = 130 + 169               = 299

C-LOOK: 53 → … → 183 → jump to 14 → 37
        130 + 169 (jump) + 23                             = 322
        (153 if the jump isn't counted)

30. I/O: Interrupts, Polling, DMA & Buffering

Polling vs interrupts

What happens on an interrupt

1. The device raises a signal on an interrupt line.
2. The CPU finishes its current instruction, saves where it was, and jumps into kernel mode.
3. It looks up the interrupt vector table to find the right handler (ISR, interrupt service routine) for that device.
4. The handler does the minimum quickly (e.g. copy the key pressed) and schedules the rest for later.
5. The CPU restores what it saved and carries on.

Hardware interrupts come from devices. Software interrupts / traps come from programs — system calls, or errors like divide-by-zero. Fast network cards switch between interrupts and polling depending on load (Linux's NAPI does this).

DMA — Direct Memory Access

Buffering, caching and spooling

• Buffer — a temporary holding area for data in transit, to smooth out speed differences. Video players buffer a few seconds ahead. Double buffering: fill one buffer while the other is being used.
• Cache — a fast copy of data kept for reuse. The OS page cache keeps recently read file blocks in RAM, which is why opening a file the second time is instant.
• Spooling — a queue on disk for a device that can serve only one job at a time. The printer spooler lets ten people "print" at once; jobs are written to disk and fed to the printer one by one. (SPOOL = Simultaneous Peripheral Operations On-Line.)

Blocking vs non-blocking I/O

Blocking: read() waits until data arrives — the thread sleeps. Non-blocking: read() returns straight away, with data or "nothing yet". Asynchronous: you ask, carry on, and get notified when done. Node.js is built on non-blocking I/O plus an event loop (using epoll on Linux), which is how one thread handles thousands of connections.

31. Linux Essentials for Developers

Looking at processes

ps aux                 # every process: user, PID, CPU%, MEM%, state, command
ps -ef --forest        # with parent–child tree
top / htop             # live view, sorted by CPU
pgrep node             # PIDs of processes named node
pstree -p              # tree of processes
lsof -i :3000          # which process is using port 3000
free -h                # RAM and swap usage
vmstat 1               # memory, swapping, CPU every second
strace -p 1234         # watch the system calls a process makes

The STAT column in ps: R running/ready, S sleeping (waiting, can be woken), D uninterruptible sleep (usually stuck on disk I/O), Z zombie, T stopped. These map straight onto the process states in section 6.

Background jobs

node server.js &       # run in background
jobs                   # list background jobs
fg %1                  # bring job 1 to foreground
Ctrl+Z, then bg        # pause, then resume in background
nohup node server.js & # keep running after you log out
nice -n 10 ./backup.sh # start with lower priority (higher nice = nicer to others)
renice -n 5 -p 1234    # change priority of a running process

Signals

A signal is a small message the OS delivers to a process. The process can catch most of them and run its own handler.

(Signal numbers shown are for Linux on x86/ARM.)

File permissions

$ ls -l deploy.sh
-rwxr-x---  1 ada  devs  512 Oct 6 10:00 deploy.sh
│└┬┘└┬┘└┬┘
│ │  │  └── others: --- (nothing)
│ │  └───── group:  r-x (read, execute)
│ └──────── owner:  rwx (read, write, execute)
└────────── type: - file, d directory, l symlink

r = 4, w = 2, x = 1  → add them up per group
rwx = 7, r-x = 5, --- = 0   →  chmod 750 deploy.sh

chmod 644 file    # rw-r--r--  normal file
chmod 755 dir     # rwxr-xr-x  normal directory / script
chmod +x run.sh   # add execute for everyone
chown ada:devs f  # change owner and group

On a directory, r means list its contents, w means create/delete files in it, and x means enter it (cd). That's why folders need x.

Root (user ID 0) bypasses permission checks. Run services as a normal user, and use sudo only for the one command that needs it.

32. Virtual Machines vs Containers

Hypervisor types

• Type 1 (bare-metal) — runs directly on the hardware. VMware ESXi, Xen, Microsoft Hyper-V, KVM (part of Linux). Used in data centres and clouds.
• Type 2 (hosted) — runs as an app on a normal OS. VirtualBox, VMware Workstation. Used on laptops.

What makes a container possible (Linux kernel features)

• Namespaces — give a process its own view of things: its own process IDs (it thinks it's PID 1), network interfaces, mount points, hostname, users.
• cgroups (control groups) — limit how much CPU, memory and I/O a group of processes may use. docker run --memory=512m sets a cgroup limit.
• Union / overlay file systems — image layers stacked on top of each other, shared between containers, with a thin writable layer on top.

Interview Q&A — quick answers

Basics

• What is an OS? The software that manages hardware and shares it safely between programs, and gives programs simple abstractions like files and processes.
• What is the kernel? The core of the OS that always stays in memory and runs in kernel mode with full hardware access.
• User mode vs kernel mode? User mode blocks privileged instructions; kernel mode allows everything. Apps run in user mode and enter the kernel only through system calls, interrupts or faults.
• What is a system call? A controlled request from a program to the kernel (open, read, fork). It uses a trap instruction to switch to kernel mode and back.
• Monolithic vs microkernel? Monolithic keeps all services in the kernel (fast, less isolated — Linux). Microkernel keeps only the bare minimum and runs the rest as user-space servers (safer, slower — QNX, MINIX).
• Multiprogramming vs multitasking? Multiprogramming switches when a process waits, to keep the CPU busy. Multitasking also switches on a timer, to keep response times low.

Processes & threads

• Program vs process? A program is a passive file on disk; a process is a running instance with its own memory, registers and state.
• What is a PCB? The kernel's record of a process — PID, state, program counter, registers, memory info, open files — used to pause and resume it.
• Process states? New, Ready, Running, Waiting, Terminated. Waiting goes back to Ready, never straight to Running.
• Process vs thread? Processes have separate memory; threads in a process share code, data, heap and files, but each has its own stack, registers and PC. Threads are cheaper to create and switch.
• What is a context switch? Saving one process's CPU state to its PCB and loading another's. Pure overhead, plus cache and TLB warm-up cost.
• What does fork return? 0 in the child, the child's PID in the parent, −1 on failure. n forks in a row give 2ⁿ processes.
• Zombie vs orphan? Zombie: child finished but parent hasn't called wait(). Orphan: parent finished first; init adopts the child.
• User vs kernel threads? User threads are managed by a library and invisible to the kernel (fast, but one block blocks all). Kernel threads are scheduled by the OS and can use multiple cores.

Scheduling

• Preemptive vs non-preemptive? Preemptive can take the CPU away mid-run; non-preemptive waits for the process to finish or block.
• Which algorithm gives minimum average waiting time? SJF (non-preemptive) / SRTF (preemptive) — provably optimal, but needs burst times.
• What is the convoy effect? In FCFS, short processes stuck behind one long process.
• How do you prevent starvation in priority scheduling? Aging — gradually raise the priority of waiting processes.
• Effect of time quantum in RR? Too large → becomes FCFS. Too small → time wasted on context switches.
• TAT and WT formulas? TAT = CT − AT. WT = TAT − BT. RT = first run − AT.
• What is MLFQ? Multiple queues with different priorities and quanta; processes move down if CPU-hungry and up if they wait long. Learns process behaviour.

Synchronisation

• What is a race condition? When the result depends on the timing of threads accessing shared data, e.g. two threads doing count++.
• Critical section requirements? Mutual exclusion, progress, bounded waiting.
• Mutex vs semaphore? A mutex is a lock with an owner (only the locker unlocks). A semaphore is a counter any thread can signal; counting semaphores manage N resources.
• Binary semaphore vs mutex? Similar values (0/1), but a mutex has ownership and a binary semaphore doesn't — so a semaphore can be used for signalling between threads.
• What is busy waiting / a spinlock? Looping until a lock frees up. Wastes CPU; only worth it for very short waits on multi-core machines.
• What is a monitor? A language-level construct whose methods run one at a time automatically, with condition variables for waiting. Java's synchronized.
• Why wait in a while loop? Spurious wakeups and other threads acting first — the condition must be re-checked after waking.
• Producer–consumer semaphores? mutex = 1, empty = N, full = 0. Wait on empty/full before mutex, or it deadlocks.
• How to avoid deadlock in dining philosophers? Allow at most 4 at the table, make one philosopher pick up in reverse order, or pick up both chopsticks atomically.

Deadlock

• Four necessary conditions? Mutual exclusion, hold and wait, no preemption, circular wait. Break any one to prevent deadlock.
• Most practical prevention? Break circular wait by always acquiring resources (locks) in a fixed global order.
• Safe vs unsafe state? Safe: some order exists in which every process can finish. Unsafe means deadlock is possible, not certain.
• What does Banker's algorithm do? Grants a request only if the resulting state is still safe. Need = Max − Allocation.
• Cycle in a RAG always means deadlock? Only if each resource has a single instance. With multiple instances, a cycle means possible deadlock.
• Deadlock vs starvation vs livelock? Deadlock: all stuck waiting on each other. Starvation: one process keeps being passed over. Livelock: processes keep reacting to each other but make no progress.

Memory

• Logical vs physical address? Logical is what the program uses; physical is the real RAM location. The MMU translates at run time.
• Internal vs external fragmentation? Internal: unused space inside an allocated block. External: free memory split into gaps too small to use. Paging removes external; segmentation removes internal.
• What is paging? Splitting logical memory into fixed-size pages and RAM into frames, mapped by a per-process page table.
• What is the TLB? A small fast cache of recent page-to-frame translations, avoiding an extra memory access per lookup.
• Why multi-level page tables? A flat table is huge (4 MB per process on 32-bit); multi-level tables only create the parts actually used.
• What is virtual memory? Letting processes use more memory than physical RAM by keeping only active pages in RAM and the rest on disk.
• What is a page fault? A trap when a process touches a page not in RAM; the OS loads it from disk and restarts the instruction.
• Best page replacement algorithm? Optimal in theory (needs the future). LRU in practice, usually approximated by the Clock algorithm.
• What is Belady's anomaly? With FIFO, more frames can cause more page faults. LRU and Optimal are immune.
• What is thrashing? The system spends most of its time paging rather than working, because processes don't have enough frames for their working sets.

Files, disks & I/O

• What is an inode? A Unix record of a file's metadata and block pointers — everything except its name.
• Hard link vs soft link? Hard link: another name for the same inode (survives deleting the original). Soft link: a file holding a path (breaks if the target goes).
• What is journaling? Logging intended changes before making them, so the file system can recover quickly after a crash.
• Which disk algorithm minimises seek but can starve? SSTF. SCAN/C-SCAN avoid starvation; C-SCAN gives the most uniform wait.
• What is DMA? A controller that moves data between a device and RAM without the CPU, interrupting once when the transfer is complete.
• Polling vs interrupts? Polling: CPU repeatedly checks the device. Interrupts: device notifies the CPU when ready.
• What is spooling? Queueing jobs on disk for a device that handles one at a time, like a printer.

Practical

• SIGTERM vs SIGKILL? SIGTERM (15) asks politely and can be handled for a clean shutdown. SIGKILL (9) can't be caught — the kernel kills the process immediately.
• What does chmod 755 mean? Owner rwx, group r-x, others r-x.
• VM vs container? A VM virtualises hardware and runs its own OS kernel. A container is an isolated process sharing the host kernel, using namespaces and cgroups — lighter and faster, less isolated.
• What are namespaces and cgroups? Namespaces control what a process can see; cgroups control how much it can use.

Learning Path

1. The big picture — what the kernel does, user vs kernel mode, system calls. Run strace ls and look at the calls it makes.
2. Processes — states, PCB, fork/exec/wait. Write a small C program that forks, and solve a few "how many times does this print" puzzles.
3. Threads — write a program where two threads increment a shared counter a million times. See the wrong answer. Fix it with a mutex.
4. Scheduling numericals — practise FCFS, SJF, SRTF, Priority and RR until drawing the Gantt chart is automatic. Always double-check by summing.
5. Synchronisation — semaphores, then producer–consumer, readers–writers and dining philosophers from memory.
6. Deadlock — the four conditions, RAGs, and at least three Banker's problems end to end.
7. Memory — address splitting and bit-counting, TLB effective access time, then paging vs segmentation.
8. Virtual memory — page faults and the three replacement algorithms on paper. Reproduce Belady's anomaly yourself.
9. Files and disks — inodes and max file size, links, and disk scheduling numericals in both directions.
10. Hands-on Linux — ps, top, kill, chmod, signals. Write a Node server that shuts down gracefully on SIGTERM.
11. Containers — run a Docker container, then look at its processes from the host with ps. Seeing it as "just a process" makes namespaces click.
12. Then — previous-year GATE OS questions, topic by topic. They repeat patterns heavily.