Skip to content

Quick-Reference-Guide.md

Latest commit

 

History

History
208 lines (148 loc) · 4.53 KB

Quick-Reference-Guide.md

File metadata and controls

208 lines (148 loc) · 4.53 KB
Raw

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

  1. Mutual Exclusion: Only one process in CS at a time
  2. Progress: Decision cannot be postponed indefinitely
  3. 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)

  1. Mutual Exclusion: Non-shareable resources
  2. Hold and Wait: Hold resources while waiting for more
  3. No Preemption: Resources cannot be forcibly taken
  4. 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