Operating Systems Quick Reference¶

CPU Scheduling Algorithms¶

Algorithm	Type	Advantage	Disadvantage
FCFS	Non-preemptive	Simple, no starvation	Convoy effect
SJF	Non-preemptive	Optimal avg waiting time	Needs burst prediction
SRTF	Preemptive	Minimal avg waiting time	Overhead, starvation
Round Robin	Preemptive	Fair, good for time-sharing	Context switch overhead
Priority	Both	Important tasks first	Starvation without aging

Formulas¶

Turnaround Time      = Completion Time - Arrival Time
Waiting Time         = Turnaround Time - Burst Time
Response Time        = First Run Time - Arrival Time
Average Waiting Time = Sum(Waiting Times) / Number of Processes

Synchronization¶

Semaphore Operations¶

wait(S) {           // P() or down()
    while (S <= 0)
        ; // busy wait
    S--;
}

signal(S) {         // V() or up()
    S++;
}

Critical Section Requirements¶

Mutual Exclusion: Only one process in CS at a time
Progress: Decision cannot be postponed indefinitely
Bounded Waiting: Limit on times others enter before a waiting process

Classic Problems¶

Producer-Consumer: Use semaphores (full, empty, mutex)
Readers-Writers: Multiple readers OR one writer
Dining Philosophers: Deadlock prevention strategies

Deadlock¶

Four Necessary Conditions (Coffman)¶

Mutual Exclusion: Non-shareable resources
Hold and Wait: Hold resources while waiting for more
No Preemption: Resources cannot be forcibly taken
Circular Wait: Circular chain of waiting processes

Banker's Algorithm¶

Available[m]      // Available resource instances
Max[n][m]         // Maximum demand
Allocation[n][m]  // Currently allocated
Need[n][m]        // Max - Allocation

Safety check: Find sequence where all processes can finish

Memory Management¶

Paging¶

Page Size            = 2^offset_bits
Number of Pages      = Address Space / Page Size
Page Table Size      = Number of Pages × Entry Size
Physical Address     = (Frame Number × Page Size) + Page Offset

TLB Effective Access Time¶

EAT = (hit_rate × TLB_time) + ((1 - hit_rate) × (TLB_time + Memory_time))

Page Replacement Algorithms¶

Algorithm	How it works	Notes
FIFO	Replace oldest page	Belady's anomaly possible
Optimal	Replace page unused longest in future	Theoretical only
LRU	Replace least recently used	Good but expensive
Second Chance	FIFO with reference bit	Approximates LRU

Belady's Anomaly¶

More frames can sometimes cause MORE page faults (FIFO only).

Effective Access Time with Page Faults¶

EAT = (1 - p) × memory_time + p × page_fault_service_time

File Systems¶

Inode Structure¶

Direct pointers (12):   12 × block_size
Single indirect:        (block_size/ptr_size) × block_size
Double indirect:        (block_size/ptr_size)² × block_size
Triple indirect:        (block_size/ptr_size)³ × block_size

With 4KB blocks, 4-byte pointers:
  Direct:   48KB
  Single:   4MB
  Double:   4GB
  Triple:   4TB

File Allocation Methods¶

Method	Sequential	Random	Fragmentation	Notes
Contiguous	Fast	Fast	External	Hard to grow
Linked	Fast	Slow	None	Pointer overhead
Indexed	Fast	Fast	None	Index block overhead

File Permissions¶

rwxr-xr--
|||
||└- Others: r-- = 4
|└-- Group:  r-x = 5
└--- Owner:  rwx = 7

Octal: r=4, w=2, x=1
Example: 755 = rwxr-xr-x

Important Commands¶

Process Management¶

ps aux              # All processes
ps -ef              # Full format
top                 # Interactive viewer
kill -9 <PID>       # Force kill
nice -n 10 cmd      # Run with lower priority

Memory¶

free -h             # Memory usage
vmstat              # Virtual memory stats
cat /proc/meminfo   # Detailed memory info

File System¶

df -h               # Disk space usage
du -sh dir/         # Directory size
ls -li              # List files with inodes
stat file           # File metadata
chmod 755 file      # Change permissions

Common Calculations¶

CPU Utilization¶

CPU Utilization = (Time CPU is busy / Total time) × 100%

Throughput¶

Throughput = Number of processes completed / Total time

Proportional Frame Allocation¶

frames_i = (size_i / total_size) × total_frames