Operating Systems

3-Hour Crash Course Study Guide

Time Section Focus

0:00 - 0:30 Unit 1 Basics OS structures, System calls
0:30 - 2:00 Unit 2 (CORE) Scheduling + Synchronization
2:00 - 3:00 Review Formulas + Practice problems

KEY FORMULAS (Memorize!):

Turnaround Time (TAT) = Completion Time - Arrival Time
Waiting Time (WT) = TAT - Burst Time
SECTION 1: OS BASICS (Unit 1)
What is an Operating System?
Definition: A program that manages computer hardware and provides services to users/applications.

Four Components of Computer System:

1. Hardware - CPU, memory, I/O devices
2. Operating System - Controls hardware, runs programs
3. Application Programs - Word processors, browsers, games
4. Users - People using the computer

Two Views of OS
View Focus Goal

User View Ease of use Make computer easy to use

System View Resource management Efficiently manage CPU, memory, I/O

Dual-Mode Operation (IMPORTANT)

Why? To protect OS from user programs

Mode Who runs? Can do what?

User Mode User programs Limited operations only

Kernel Mode Operating System ALL operations (privileged)

Mode Bit: Hardware bit that tells CPU which mode it's in. System call switches User→Kernel mode.

System Calls
Definition: Interface for programs to request OS services
Flow: Your Program → System Call → OS Kernel → Hardware

6 Types of System Calls:

Type Examples Purpose

Process Control fork(), exit(), wait() Create/terminate processes

File Manipulation open(), read(), write(), close() File operations

Device Manipulation read(), write() to devices I/O operations

Information get time, get process info System info

Communications send/receive messages IPC

Protection set permissions Security

Parameter Passing Methods:

1. Registers - Put parameters in CPU registers (fast, limited)
2. Memory Block/Table - Store params in memory, pass address
3. Stack - Push parameters onto stack
OS Structures (Know the differences!)
Structure Description Example Pros Cons

Simple/Monolithic Everything in one kernel UNIX, MS-DOS Fast Hard to maintain

Layered OS in layers (0=HW, N=user) MULTICS Easy debug Slow

Microkernel Tiny kernel + user services Minix, QNX Reliable, secure Slower

Modular Loadable kernel modules Linux, Solaris Flexible Complex

Hybrid Mix of above macOS, Windows Best of both Complex

Remember: Monolithic = Fast but risky | Microkernel = Safe but slower | Hybrid = Modern systems
SECTION 2: PROCESS MANAGEMENT (Unit 2)
Process Basics
Program Process

Passive (file on disk) Active (running in memory)

Just code Code + Data + Stack + Heap + PCB

Process Memory Layout:

Stack (top) - Local variables, function calls (grows DOWN)
Heap - Dynamic memory - malloc() (grows UP)
Data - Global and static variables
Text (bottom) - Program code/instructions

5 Process States (MUST KNOW!)

NEW → READY → RUNNING → TERMINATED

↓ ↑

WAITING ■■■■■

State Description

New Process being created

Ready Waiting for CPU (in ready queue)

Running Currently executing on CPU

Waiting/Blocked Waiting for I/O or event

Terminated Finished execution

Process Control Block (PCB)

Definition: Data structure containing ALL information about a process

PCB Contains: Process ID (PID), Process State, Program Counter, CPU Registers, Memory limits, I/O status,
Scheduling info (priority)

3 Types of Schedulers
Scheduler When What it does

Long-term (Job) New job enters Decides which jobs load into memory

Short-term (CPU) Every few ms Picks which ready process gets CPU

Medium-term During execution Swaps processes in/out of memory

Context Switch: Saving state of current process and loading state of next process. It's overhead (wastes CPU time).

Process Operations
fork() - Creates child process (copy of parent). Returns 0 to child, PID to parent
exec() - Replaces process memory with new program
wait() - Parent waits for child to terminate
 exit() - Terminates process
Zombie: Child finished but parent hasn't called wait() | Orphan: Parent terminated without waiting

Inter-Process Communication (IPC)

Shared Memory Message Passing

Processes share memory region Processes exchange messages

Faster (no kernel involvement) Slower (goes through kernel)

Needs synchronization Easier for distributed systems

CPU SCHEDULING ALGORITHMS (MOST TESTED!)
Preemptive vs Non-Preemptive
Non-Preemptive Preemptive

Process runs until done OS can stop running process

FCFS, SJF Round Robin, SRTF, Priority

1. FCFS (First Come First Served)

Rule: First process to arrive runs first (like a queue) | Type: Non-preemptive

Example: All arrive at time 0

Process Burst Time

P1 24

P2 3

P3 3
Gantt Chart: | P1 (0-24) | P2 (24-27) | P3 (27-30) |

WT: P1=0, P2=24, P3=27 → Avg WT = (0+24+27)/3 = 17 ms

Problem: Convoy Effect - short processes wait for long ones

2. SJF (Shortest Job First)

Rule: Process with shortest burst time runs first | Type: Non-preemptive

Example: All arrive at time 0

Process Burst Time Order

P1 6 2nd

P2 8 4th

P3 7 3rd

P4 3 1st (shortest)
Gantt Chart: | P4 (0-3) | P1 (3-9) | P3 (9-16) | P2 (16-24) |

Pros: Minimum average waiting time | Cons: Need burst time in advance, starvation possible

3. SRTF (Shortest Remaining Time First)

Rule: Like SJF but PREEMPTIVE - if new process has shorter remaining time, switch!

Example:

Process Arrival Burst

P1 0 8

P2 1 4

P3 2 9

P4 3 5
Gantt: |P1(0-1)|P2(1-5)|P4(5-10)|P1(10-17)|P3(17-26)|
At t=1: P2 arrives (burst=4), P1 remaining=7. Since 4<7, switch to P2!

4. Priority Scheduling
Rule: Process with highest priority runs first (lower number = higher priority usually)

Problem: Starvation | Solution: Aging (increase priority over time)

5. Round Robin (RR) - VERY IMPORTANT

Rule: Each process gets fixed time quantum, then goes to back of queue | Type: Preemptive

Example: Time Quantum = 4

Process Burst

P1 24

P2 3

P3 3
Gantt: |P1(0-4)|P2(4-7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)|P1(26-30)|

Key: If burst ≤ quantum → finishes | If burst > quantum → goes to back of queue

Large quantum = becomes FCFS | Small quantum = too many context switches
PROCESS SYNCHRONIZATION
Race Condition
Definition: When multiple processes access shared data and final result depends on execution order

Example: Two ATM withdrawals at same time from same account!

Critical Section Problem

Critical Section: Code that accesses shared resources
Entry Section → Critical Section → Exit Section → Remainder Section

3 Requirements for Solution (MUST MEMORIZE!)

Requirement Meaning

1. Mutual Exclusion Only ONE process in critical section at a time

2. Progress If no one in CS, someone waiting should enter

3. Bounded Waiting Limit on how long a process waits

Hardware Solutions
Test-and-Set: Atomically tests lock value and sets it to true. Returns old value.
If returns FALSE → lock was free, you have it | If returns TRUE → keep trying

Compare-and-Swap: Compares value with expected, if equal, swaps with new value.

Mutex Lock
acquire() - Get the lock (wait if busy) | release() - Release the lock

Problem: Busy waiting (spinlock) wastes CPU

Semaphores (VERY IMPORTANT!)

Definition: Integer variable accessed through two atomic operations

wait(S) / P() / down() signal(S) / V() / up()

while (S <= 0) wait;

S--; S++;

Binary Semaphore Counting Semaphore

Value: 0 or 1 Value: 0 to N

Like a mutex, one resource For multiple resources

Semaphore Problems
Deadlock: Two processes waiting for each other forever
Starvation: A process waits indefinitely
Priority Inversion: Low priority holds resource needed by high priority → Solution: Priority Inheritance
CLASSICAL SYNCHRONIZATION PROBLEMS
1. Bounded Buffer (Producer-Consumer)
Setup: Buffer of size N, Producer adds items, Consumer removes items

Semaphore Initial Value Purpose

mutex 1 Mutual exclusion for buffer

empty N Count of empty slots

full 0 Count of full slots

Producer: wait(empty) → wait(mutex) → add item → signal(mutex) → signal(full)

Consumer: wait(full) → wait(mutex) → remove item → signal(mutex) → signal(empty)

2. Readers-Writers Problem
Rules: Multiple readers can read simultaneously | Only ONE writer at a time | No reading while writing

Semaphore/Variable Purpose

rw_mutex = 1 Mutual exclusion for writers

mutex = 1 Protect read_count

read_count = 0 Number of readers

First reader locks writers out | Last reader lets writers in

3. Dining Philosophers
Setup: 5 philosophers, 5 chopsticks, need 2 chopsticks to eat

Problem: If everyone picks up left chopstick → DEADLOCK!

Solutions: Allow only 4 to sit | Pick up both atomically | Odd pick left first, even pick right first

MULTIPLE-PROCESSOR SCHEDULING
Asymmetric Symmetric (SMP)

One master CPU schedules Each CPU schedules itself

Others execute only Common or private ready queue

Processor Affinity: Keep process on same CPU to use cached data

Soft: OS tries to keep on same CPU | Hard: Process bound to specific CPU
Load Balancing: Push migration (OS pushes from busy to idle) | Pull migration (idle pulls from busy)
QUICK REFERENCE CHEAT SHEET
Scheduling Algorithm Summary
Algorithm Type Key Point

FCFS Non-preemptive First come first serve, Convoy effect

SJF Non-preemptive Shortest job first, Optimal avg WT

SRTF Preemptive Shortest remaining time, Preempts

Priority Both Based on priority, Starvation→Aging

Round Robin Preemptive Time quantum, Fair

Synchronization Summary
Mechanism Description

Mutex Lock for one process

Binary Semaphore 0 or 1, like mutex

Counting Semaphore 0 to N, multiple resources

LIKELY EXAM QUESTIONS

1. Calculate average waiting time and turnaround time for given processes using FCFS/SJF/RR
2. Draw Gantt chart for scheduling algorithms
3. Explain process states with diagram
4. Difference between preemptive and non-preemptive
5. What is PCB? What does it contain?
6. Explain semaphores with wait() and signal()
7. Solve bounded buffer problem using semaphores
8. What is race condition? How to prevent?
9. 3 requirements for critical section solution
10. Difference between mutex and semaphore

Good luck! Focus on scheduling algorithms and synchronization - they're the most tested topics!