Operating System Cheatsheet

Introduction

This cheatsheet condenses the entire Operating Systems syllabus into quick-reference format. Use it for last-minute revision before exams, quick lookup during assignments, or as a study companion alongside your textbook. Every entry is designed to be scannable — find what you need in seconds.

Process Management

Process: A program in execution with its own address space, program counter, registers, and stack.

Process States:

PCB (Process Control Block) contains: PID, process state, program counter, CPU registers, memory limits, list of open files, scheduling priority, accounting info.

Process creation: fork() creates child (copy of parent), exec() replaces process image.

Context Switch: Save state of current process → Load state of next process. Overhead includes saving/restoring registers, flushing TLB, cache penalties.

CPU Scheduling

Key Formulas:

• Turnaround Time = Completion Time - Arrival Time
• Waiting Time = Turnaround Time - Burst Time
• Response Time = First CPU Time - Arrival Time
• Throughput = Processes Completed / Total Time

Optimal time quantum for RR: Too small = excessive context switches; too large = becomes FCFS. Typical: 10-100ms.

Process Synchronization

Race Condition: Multiple processes access shared data concurrently, and the outcome depends on execution order.

Critical Section Requirements:

1. Mutual Exclusion — only one process in CS at a time
2. Progress — if CS is free, a waiting process must be allowed in
3. Bounded Waiting — limit on how many times others enter before a waiting process

Synchronization Tools:

Semaphore operations: wait(S): if S > 0, decrement; else block. signal(S): increment, wake one blocked process.

Classic Problems: Producer-Consumer, Readers-Writers, Dining Philosophers.

Deadlock

Four Necessary Conditions (ALL must hold simultaneously):

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

Handling Strategies:

• Prevention: Break one of the four conditions
• Avoidance: Banker's Algorithm (check safe state before allocation)
• Detection: Resource Allocation Graph (single instance), Matrix algorithm (multiple instances)
• Recovery: Kill processes or preempt resources

Banker's Algorithm: Need = Max - Allocation. System is safe if a safe sequence exists where each process can get its needed resources.

Memory Management

Logical vs Physical Address: Logical (virtual) generated by CPU; Physical exists on RAM. MMU translates between them.

Techniques:

Paging:

• Logical address = [Page Number | Offset]
• Physical address = [Frame Number | Offset]
• Page Table maps page → frame
• No external fragmentation; possible internal fragmentation

Segmentation: Divides memory by logical units (code, data, stack). Variable-sized segments → external fragmentation possible.

Page Replacement Algorithms:

Thrashing: Process spends more time paging than executing. Cause: insufficient frames. Solution: Working Set Model, decrease multiprogramming degree.

EAT with TLB: EAT = α × t + (1-α) × 2t, where α = hit ratio, t = memory access time.

File Systems

File Allocation Methods:

• Contiguous: Fast sequential/random access, external fragmentation
• Linked: No fragmentation, slow random access, pointer overhead
• Indexed: Fast random access, index block overhead

Directory Structures: Single-level → Two-level → Tree → Acyclic graph → General graph

Free Space Management: Bit vector, Linked list, Grouping, Counting

File Operations: Create, Open, Read, Write, Seek, Delete, Truncate

I/O Systems

I/O Methods:

1. Programmed I/O — CPU polls device (busy waiting)
2. Interrupt-driven I/O — device signals CPU when ready
3. DMA — device transfers directly to memory, interrupts CPU when done

Disk Scheduling: FCFS, SSTF, SCAN (elevator), C-SCAN, LOOK, C-LOOK

Disk Access Time = Seek Time + Rotational Latency + Transfer Time

Virtual Memory

• Pages loaded on demand (demand paging)
• Valid/Invalid bit in page table indicates if page is in memory
• Page fault triggers: trap → find frame → disk read → update page table → restart instruction
• Copy-on-Write: forked processes share pages until one writes

Security Basics

Authentication: Verify identity (passwords, biometrics, tokens) Authorization: Determine permissions (ACLs, capabilities, RBAC) Access Control Models: DAC (owner controls), MAC (system enforces), RBAC (role-based)

Common Threats: Buffer overflow, privilege escalation, rootkits, ransomware

Linux Quick Reference

Exam Tips

1. For scheduling problems: always draw a Gantt chart first
2. For page replacement: trace through the reference string step by step
3. For Banker's algorithm: calculate Need matrix first, then find safe sequence
4. For deadlock: check all four conditions — if any is absent, no deadlock
5. For disk scheduling: draw the number line showing head position and request queue