User Applications
─────────────────
System Calls (API to OS)
─────────────────
OS Kernel
─────────────────
Hardware (CPU, RAM, Disk, Network)

New → Ready → Running → Waiting → Terminated
                ↓           ↑
            Preempted    I/O done

New:        Process being created
Ready:      Waiting for CPU (in ready queue)
Running:    Currently executing on CPU
Waiting:    Waiting for I/O or event (blocked)
Terminated: Execution complete

PCB (Process Control Block) contains:
  PID, state, program counter, CPU registers,
  memory limits, open files, I/O status

Scheduling criteria:
  CPU Utilization:    Keep CPU busy (maximize)
  Throughput:         Processes/second (maximize)
  Turnaround Time:    Submission → completion (minimize)
  Waiting Time:       Time in ready queue (minimize)
  Response Time:      First response time (minimize)

Key formulas:
  Turnaround = Completion - Arrival
  Waiting = Turnaround - Burst
  Response = First CPU - Arrival

1. FCFS (First Come First Serve)
   Non-preemptive, simple, convoy effect
   
   Example: P1(24ms) P2(3ms) P3(3ms) all arrive at 0
   Order: P1→P2→P3
   Waiting: P1=0, P2=24, P3=27  Avg=17ms  ← POOR

2. SJF (Shortest Job First) — Non-preemptive
   Optimal average waiting time, needs future burst knowledge
   
   Same example: P2(3)→P3(3)→P1(24)
   Waiting: P2=0, P3=3, P1=6  Avg=3ms  ← OPTIMAL

3. SRTF (Shortest Remaining Time First) — Preemptive SJF
   Preempts current process if new shorter job arrives
   Starvation possible for long processes

4. Round Robin (RR) — Preemptive, time quantum q
   Each process gets q ms on CPU, then back to queue
   Context switch overhead: smaller q = more overhead
   q too large = degenerates to FCFS
   q = 20ms typical for interactive systems

5. Priority Scheduling
   Lower number = higher priority (or vice versa)
   Problem: starvation of low-priority processes
   Solution: Aging — gradually increase priority of waiting processes

6. MLFQ (Multi-Level Feedback Queue)
   Multiple queues with different priorities
   Process moves to lower priority if uses full quantum
   Process moves up if waits too long (aging)
   Used by: Windows, Unix/Linux

Thread vs Process:
  Process: independent, own memory space, expensive to create/switch
  Thread: within process, shared memory, lightweight

Types:
  User-level threads: managed by user library, kernel sees 1 thread
  Kernel-level threads: OS manages, expensive but parallel on multi-core
  
POSIX Threads (pthreads):
  pthread_create()
  pthread_join()
  pthread_mutex_lock/unlock()

Logical (virtual) address: Generated by CPU during execution
Physical address: Actual RAM location

MMU (Memory Management Unit) translates logical → physical
Relocation register: physical = logical + base register

Page: Fixed-size logical memory block (typically 4KB)
Frame: Fixed-size physical memory block (same size as page)

Page Table: Logical page → physical frame mapping
  Each process has its own page table
  Page table entry contains: frame number + valid bit + dirty bit

Address translation:
  Logical address = page number + offset
  Physical address = frame number + offset (offset unchanged)

Multi-level paging: For large address space, page table is too large
  2-level: page directory → page table → frame
  Used by: x86 (32-bit uses 2-level, 64-bit uses 4-level)

TLB (Translation Lookaside Buffer):
  Cache for page table entries
  Hit: O(1) translation, Miss: O(n) page table walk
  Hit ratio h, TLB time t, Memory time m:
  EAT = h(t+m) + (1-h)(t+2m)

Need a page replacement when all frames full and new page needed

FIFO: Replace oldest page
  Belady's Anomaly: More frames can cause MORE page faults
  
OPT (Optimal): Replace page not used for longest time
  Not implementable (needs future knowledge)
  Used as benchmark

LRU (Least Recently Used): Replace least recently used
  Closest approximation to OPT
  Implementation: counters or stack
  No Belady's anomaly

Clock Algorithm (Second Chance): Approximates LRU
  Use bit per page, circular scan
  If use bit=1, clear it and move on
  If use bit=0, replace it

Thrashing: Process spends more time paging than executing
  Cause: Too many processes, not enough frames
  Solution: Working Set Model, reduce degree of multiprogramming

Variable-sized logical segments (code, data, stack, heap)
Segment table: base + limit for each segment
Segment + offset → physical address (if offset < limit)
External fragmentation problem (unlike paging)

4 necessary conditions (ALL must hold for deadlock):
  1. Mutual Exclusion: At least one non-sharable resource
  2. Hold and Wait: Process holds resources while waiting for more
  3. No Preemption: Resources can't be forcibly taken
  4. Circular Wait: P1 waits for P2, P2 waits for P3, P3 waits for P1

Resource Allocation Graph (RAG):
  Process node (circle) → Resource node (square): request edge
  Resource node (square) → Process node (circle): assignment edge
  Cycle in RAG = deadlock (if single instance per resource)
  Cycle ≠ deadlock if multiple instances (need to check fully)

Deadlock Handling:
  Prevention: Negate one of the 4 conditions (restrictive)
    → No Hold & Wait: Request all resources at start
    → Allow Preemption: Take resources from waiting processes
    → No Circular Wait: Order resources, request in order
  
  Avoidance: Banker's Algorithm
    Safe state: all processes can complete in some order
    Unsafe state: may lead to deadlock (not guaranteed)
    Algorithm checks if granting request keeps system safe
    
  Detection: Allow deadlock, detect using RAG reduction
    Recovery: Kill process or preempt resources

GATE favourite: Banker's Algorithm examples
  n processes, m resource types
  Need matrix, Available vector, Allocation matrix
  Find safe sequence

File attributes: name, type, size, location, owner, timestamps

Directory structures:
  Single-level: all files in one directory
  Two-level: one per user
  Tree: hierarchical (most common)
  DAG: allows sharing (links)

File Allocation Methods:
  Contiguous: fast access, external fragmentation
  Linked: no fragmentation, slow random access
  Indexed: index block, supports random access

FAT (File Allocation Table): Linked with in-memory table
Unix inode:
  Inode = 12 direct + 1 single indirect + 1 double + 1 triple indirect
  Single indirect = 1024 block pointers (with 1KB blocks)
  Double indirect = 1024² block pointers

Race condition: Multiple processes access shared data concurrently
Critical section: Code that accesses shared resource

Requirements for solution:
  1. Mutual exclusion: Only one process in CS at a time
  2. Progress: If no process in CS, one wanting to enter should
  3. Bounded waiting: Bound on how long a process waits

Peterson's Solution (2 processes):
  flag[i] = true; turn = j;
  while(flag[j] && turn == j);  // wait
  // critical section
  flag[i] = false;

Semaphore:
  wait(S): S--; if S<0, block
  signal(S): S++; if S≤0, wake one
  Binary semaphore (mutex): 0 or 1
  Counting semaphore: any non-negative integer

Classic problems:
  Producer-Consumer: buffer, mutex + empty + full semaphores
  Readers-Writers: prefer readers or writers
  Dining Philosophers: prevent deadlock in resource sharing

Monitor: High-level synchronization construct (Java synchronized)
  Mutual exclusion built-in
  Condition variables: wait() and signal()

Disk scheduling (for hard drives, less relevant for SSDs):

FCFS: Serve in order of requests
SSTF (Shortest Seek Time First): Go to nearest cylinder
  Starvation possible for far requests
SCAN (Elevator): Move in one direction, reverse at end
C-SCAN: Move one direction only, jump back (no serve on return)
C-LOOK: Like C-SCAN but only go to last request each direction

GATE often gives: track requests and asks for total head movement