What is an Operating System?

Definition: An Operating System is software that manages computer hardware and provides services to applications.

Why Do We Need an OS?

  • Resource Management: Allocates CPU, memory, and I/O devices efficiently
  • Process Management: Controls execution of multiple programs
  • Memory Management: Manages RAM and virtual memory
  • File System: Organizes and manages data storage
  • Security: Protects data and prevents unauthorized access
  • User Interface: Provides CLI or GUI for user interaction

OS Layers

┌─────────────────────────────────────────────┐ │ USER APPLICATIONS │ │ (Word, Browser, Games, Email, etc.) │ ├─────────────────────────────────────────────┤ │ OPERATING SYSTEM │ │ (Process, Memory, File, Device Mgmt) │ ├─────────────────────────────────────────────┤ │ HARDWARE LAYER │ │ (CPU, RAM, Disk, I/O, Network) │ └─────────────────────────────────────────────┘

System Architecture

Dual-Mode Operation

┌─────────────────────────────────────────┐ │ USER MODE (Restricted) │ │ • Limited instruction set │ │ • Cannot access hardware directly │ │ • Applications run here │ └─────────────────────────────────────────┘ ↕ (System Call) ┌─────────────────────────────────────────┐ │ KERNEL MODE (Unrestricted) │ │ • Full instruction set │ │ • Direct hardware access │ │ • OS runs here │ └─────────────────────────────────────────┘

Protection Mechanisms

  • Memory Protection: Prevents process from accessing other process's memory
  • I/O Protection: Only OS can execute I/O instructions
  • CPU Protection: Timer interrupt prevents infinite loops

Process Synchronization Basics

What is Synchronization?

Synchronization ensures that multiple processes/threads access shared resources safely without conflicts.

The Race Condition Problem

Process A: Read X (value: 5) Process B: Read X (value: 5) Process A: X = X + 1 → Write 6 Process B: X = X + 1 → Write 6 Final Result: X = 6 (Should be 7!)

Critical Section

Definition: A code segment where a process accesses shared resources.

Solution Requirements:

  • Mutual Exclusion: Only one process in critical section at a time
  • Progress: If no process in critical section, waiting process can enter
  • Bounded Waiting: Process won't wait indefinitely

Mutex & Semaphores

Mutex (Mutual Exclusion)

Definition: A lock that allows only one thread to access a resource at a time.

How Mutex Works:

Thread A: Lock(mutex) ✓ Acquired Thread B: Lock(mutex) ✗ Blocked (waiting) Thread A: Critical Section Thread A: Unlock(mutex) Thread B: Lock(mutex) ✓ Acquired

Semaphore

Definition: A synchronization variable with an integer value and two operations: wait() and signal().

Types of Semaphores:

Type Range Use Case
Binary Semaphore 0 or 1 Same as Mutex
Counting Semaphore 0 to N Control access to N resources

Semaphore Operations:

wait(S): if S > 0 S = S - 1 else block process signal(S): S = S + 1 wake up one blocked process

✓ Advantages

  • Simple to understand
  • Efficient implementation
  • Flexible (binary or counting)

✗ Disadvantages

  • Easy to misuse
  • Can cause deadlock
  • No priority mechanism

Producer-Consumer Problem

Problem Statement

Producers create data and place it in a bounded buffer. Consumers retrieve and consume data. Both must synchronize to avoid conflicts.

Solution Using Semaphores:

Semaphore empty = N; // Buffer is empty Semaphore full = 0; // No items initially Semaphore mutex = 1; // Mutual exclusion Producer: while true: produce_item() wait(empty) wait(mutex) add_to_buffer() signal(mutex) signal(full) Consumer: while true: wait(full) wait(mutex) remove_from_buffer() signal(mutex) signal(empty) consume_item()

Key Points

  • Empty semaphore tracks available buffer space
  • Full semaphore tracks items ready to consume
  • Mutex ensures only one process accesses buffer

Reader-Writer Problem

Problem Statement

Multiple readers can read simultaneously, but writers need exclusive access. Readers and writers cannot access simultaneously.

Reader-Preference Solution:

int read_count = 0; Semaphore write_sem = 1; Semaphore read_sem = 1; Reader: wait(read_sem) read_count++ if read_count == 1: wait(write_sem) signal(read_sem) read_data() wait(read_sem) read_count-- if read_count == 0: signal(write_sem) signal(read_sem) Writer: wait(write_sem) write_data() signal(write_sem)

Issues

  • Reader-Preference: Continuous readers can starve writers
  • Writer-Preference: Writers get priority, but readers may starve

Dining Philosophers Problem

Problem Statement

Five philosophers sit at a round table with 5 chopsticks. Each needs 2 chopsticks to eat.

Philosopher 1 | Chop 1 --|-- Chop 2 / \ P5 | | P2 \ / Chop 5 --|-- Chop 3 | Philosopher 3

The Deadlock Scenario

  • All 5 philosophers pick up their left chopstick
  • All wait for the right chopstick
  • No philosopher can eat → DEADLOCK!

Solution: Asymmetric Approach

Philosopher 1 to 4: while true: think() pick_left_chopstick() pick_right_chopstick() eat() put_left_chopstick() put_right_chopstick() Philosopher 5 (Different): while true: think() pick_right_chopstick() // Different order! pick_left_chopstick() eat() put_right_chopstick() put_left_chopstick()

Why This Works

By breaking the circular wait condition, at least one philosopher can always eat.

H2O Synchronization Problem

Problem Statement

Create water molecules (H2O) from hydrogen and oxygen atoms. Each water needs 2 hydrogen and 1 oxygen atom. Atoms must synchronize to form molecules.

Key Constraints

  • 2 hydrogen atoms + 1 oxygen atom = 1 water molecule
  • Atoms wait until they can form a complete molecule
  • No atom should wait indefinitely

Solution Approach

Semaphore h_sem = 0; Semaphore o_sem = 0; Semaphore h_barrier = 0; Semaphore o_barrier = 0; int h_count = 0, o_count = 0; Hydrogen: wait(h_sem) h_count++ if h_count == 2: signal(o_barrier) else: signal(h_barrier) Oxygen: wait(o_sem) o_count++ if o_count == 1: signal(h_barrier) signal(h_barrier) form_water() reset_counts()

Quiz 1: Synchronization & Deadlock (From PDF)

Q1: In the Reader-Writer problem (reader-preference version), what occurs when a continuous stream of readers arrives while writers are waiting?

Q2: A writer-preference Reader-Writer solution ensures writers do not starve. What tradeoff is introduced?

Q3: In Dining Philosophers, all philosophers pick up their left fork simultaneously and wait for the right fork. Which Coffman condition makes deadlock possible?

Q4: If resource ordering is applied in Dining Philosophers, which deadlock condition is explicitly broken?

Q5: In the H2O synchronization problem, if three hydrogen threads are allowed to proceed without oxygen synchronization, what property is violated?

Q6: If a counting semaphore initialized to N protects a resource pool, what does N logically represent?

Q7: Which synchronization primitive inherently supports ownership semantics?

Q8: If multiple readers enter the critical section simultaneously in Reader-Writer, which property is preserved?

Deadlock - Basics

What is Deadlock?

Definition: A situation where two or more processes are unable to proceed because each is waiting for a resource held by another.

Coffman's Four Necessary Conditions

Condition Meaning
1. Mutual Exclusion Resource can be used by only one process at a time
2. Hold and Wait Process holds resources while waiting for others
3. No Preemption Resources cannot be forcibly taken from a process
4. Circular Wait Circular chain of processes waiting for resources

Real-World Example

Process A: Holds File1, Waits for File2 Process B: Holds File2, Waits for File1 ↓ DEADLOCK!

Resource Allocation Graph (RAG)

What is RAG?

Definition: A directed graph used to detect deadlock by representing processes and resources.

RAG Example - Deadlock

P1 → R1 → P2 ↑ ↓ └─ R2 ←──┘ Circular Wait = DEADLOCK!

Deadlock Detection Algorithm

  1. Check if RAG contains a cycle
  2. If cycle exists → Deadlock detected
  3. If no cycle → No deadlock

Important Note

A cycle in RAG implies deadlock only when there is a single instance of each resource type.

Banker's Algorithm (Deadlock Avoidance)

What is Banker's Algorithm?

An algorithm that prevents deadlock by ensuring the system never enters an unsafe state.

Key Concept: Safe State

Definition: A state where there exists at least one safe sequence of process execution that will not result in deadlock.

Algorithm Steps

When a process requests resources: 1. Check if request can be granted 2. Simulate granting the request 3. Check if system remains in safe state 4. If safe: grant the request 5. If unsafe: deny the request and make process wait

Advantages & Disadvantages

✓ Advantages

  • Prevents deadlock completely
  • Allows maximum concurrency
  • Mathematically proven

✗ Disadvantages

  • Requires knowing max resource demand in advance
  • Computationally expensive
  • Assumes fixed number of resources

Quiz 2: Deadlock (From PDF & Exam Perspective)

Q1: Which deadlock handling strategy requires prior knowledge of maximum resource demand?

Q2: A system is in a safe state. Which statement is strictly correct?

Q3: In deadlock detection using a resource allocation graph, a cycle implies deadlock only when:

Q4: If a thread holds one resource and requests another while still holding the first, which deadlock condition is satisfied?

Q5: In a deadlock recovery strategy that terminates processes, what is the primary drawback?

Q6: If a semaphore implementation allows negative values internally, what does a negative value represent?

Q7: In Banker's algorithm, a request is granted only if:

Memory Management

Contiguous Memory Allocation

Definition: Each process gets a single contiguous block of memory.

Memory Layout:

┌─────────────────────┐ │ OS (Kernel) │ 0x0000 ├─────────────────────┤ │ Process A │ 0x1000 ├─────────────────────┤ │ Process B │ 0x3000 ├─────────────────────┤ │ Free Memory │ 0x5000 ├─────────────────────┤ │ Process C │ 0x7000 ├─────────────────────┤ │ Free Memory │ 0x9000 └─────────────────────┘

Memory Allocation Strategies

Strategy Description Speed Fragmentation
First Fit Allocate first available hole Fast High
Best Fit Allocate smallest sufficient hole Slow Low
Worst Fit Allocate largest hole Slow Medium

Memory Fragmentation

Internal Fragmentation

Definition: Wasted memory within allocated blocks.

Process needs 1000 bytes Allocated 2048 bytes Wasted: 1048 bytes (inside the allocated block)

External Fragmentation

Definition: Wasted memory between allocated blocks.

┌──────────┬────┬──────────┬────┬──────────┐ │ Process A│Free│ Process B│Free│ Process C│ │ 2KB │1KB │ 2KB │1KB │ 2KB │ └──────────┴────┴──────────┴────┴──────────┘ Total Free: 2KB (fragmented into 1KB + 1KB) Cannot allocate 2KB contiguous block!

Comparison

Type Location Cause Solution
Internal Inside allocated block Fixed block size > process size Variable block sizes
External Between allocated blocks Process allocation/deallocation Paging or Compaction

Quiz 3: Memory Management

Q1: Which memory allocation strategy is fastest but causes more fragmentation?

Q2: What causes internal fragmentation?

Q3: External fragmentation can be solved by:

Q4: Best Fit allocation strategy is slower than First Fit because:

Q5: Which type of fragmentation is inherent to paging?

Paging Basics

What is Paging?

Definition: A memory management technique that divides memory into fixed-size blocks called pages and frames.

Key Terms

Term Definition
Page Fixed-size block in logical memory (process view)
Frame Fixed-size block in physical memory (RAM)
Page Table Maps logical pages to physical frames
Logical Address Address used by process (page number + offset)
Physical Address Actual RAM address (frame number + offset)

Paging Structure

LOGICAL MEMORY (Process View) ┌─────────────┐ │ Page 0 │ ├─────────────┤ │ Page 1 │ ├─────────────┤ │ Page 2 │ ├─────────────┤ │ Page 3 │ └─────────────┘ ↓ (Page Table) PHYSICAL MEMORY (RAM) ┌─────────────┐ │ Frame 2 │ ← Page 0 ├─────────────┤ │ Frame 0 │ ← Page 1 ├─────────────┤ │ Frame 3 │ ← Page 2 ├─────────────┤ │ Frame 1 │ ← Page 3 └─────────────┘

✓ Advantages

  • No external fragmentation
  • Simple address translation
  • Supports virtual memory

✗ Disadvantages

  • Internal fragmentation
  • Page table overhead
  • TLB miss penalty

TLB & Address Translation

What is TLB?

Definition: Translation Lookaside Buffer - a fast cache that stores recent page table entries.

Address Translation Process

Logical Address ↓ Check TLB ─→ HIT (Fast!) → Physical Address ↓ MISS ↓ Access Page Table → Update TLB → Physical Address

TLB Performance

Scenario Time
TLB Hit ~1 ns
TLB Miss (Page Table Access) ~100 ns
Page Fault (Disk Access) ~10 ms

Effective Access Time (EAT)

EAT = (Hit Rate × TLB Time) + (Miss Rate × Memory Time) Example: Hit Rate = 95%, TLB Time = 1ns, Memory Time = 100ns EAT = (0.95 × 1) + (0.05 × 100) = 0.95 + 5 = 5.95 ns

Quiz 4: Paging & Address Translation

Q1: What is a page in paging?

Q2: What is the primary purpose of TLB?

Q3: If TLB hit rate is 99% and hit time is 1ns, miss time is 100ns, what is EAT?

Q4: Paging eliminates which type of fragmentation?

Q5: In address translation, if page size is 4KB and logical address is 0x2345, what is the offset?

Segmentation

What is Segmentation?

Definition: A memory management technique that divides memory into variable-sized logical segments (code, data, stack, heap).

Segmentation vs Paging

Feature Segmentation Paging
Block Size Variable Fixed
Fragmentation External Internal
Address Space Logical Physical
Protection Per segment Per page

Quiz 5: Segmentation

Q1: What is a segment in segmentation?

Q2: Segmentation causes which type of fragmentation?

Q3: Which memory technique provides better protection per unit?

Virtual Memory

What is Virtual Memory?

Definition: A technique that allows processes to use more memory than physically available by using disk as an extension of RAM.

Benefits

  • Process can use more memory than available RAM
  • Multiple processes can run simultaneously
  • Better resource utilization
  • Simplified memory management

Demand Paging

What is Demand Paging?

Definition: Pages are loaded into memory only when needed (on demand).

Page Fault Handling:

1. Process accesses page not in memory 2. CPU raises Page Fault exception 3. OS finds page on disk 4. Loads page into free frame 5. Updates page table 6. Resumes process

Copy-on-Write (COW)

Definition: Parent and child processes share pages until one tries to write.

Quiz 6: Virtual Memory & Demand Paging

Q1: What is demand paging?

Q2: What is the main cost in demand paging?

Q3: In Copy-on-Write, when does the OS create a copy of a page?

Page Replacement Algorithms

What is Page Replacement?

Definition: When physical memory is full, the OS must select a page to remove to make space for a new page.

FIFO (First-In-First-Out)

Algorithm: Remove the oldest page in memory.

LRU (Least Recently Used)

Algorithm: Remove the page not used for the longest time.

LFU (Least Frequently Used)

Algorithm: Remove the page used least frequently.

Comparison

Algorithm Criterion Performance
FIFO Oldest page Poor
LRU Least recently used Good
LFU Least frequently used Very Good

Quiz 3 & 4: Operating Systems (From Exam)

Complete Quiz - 15 Questions from BSCS-5th Semester Exam

Q1: In the Reader-Writer problem (reader-preference version), a continuous stream of readers arrives while writers are waiting. What is the precise condition occurring?

Q2: A writer-preference Reader-Writer solution ensures writers do not starve. What tradeoff is introduced?

Q3: In Dining Philosophers, all philosophers pick up their left fork simultaneously and wait for the right fork. Which Coffman condition makes the deadlock possible?

Q4: If resource ordering is applied in Dining Philosophers, which deadlock condition is explicitly broken?

Q5: In the H2O synchronization problem, if three hydrogen threads are allowed to proceed without oxygen synchronization, what property is violated?

Q6: Which deadlock handling strategy requires prior knowledge of maximum resource demand?

Q7: A system is in a safe state. Which statement is strictly correct?

Q8: If a counting semaphore initialized to N protects a resource pool, what does N logically represent?

Q9: In deadlock detection using a resource allocation graph, a cycle implies deadlock only when:

Q10: If a thread holds one resource and requests another while still holding the first, which deadlock condition is satisfied?

Q11: In a deadlock recovery strategy that terminates processes, what is the primary drawback?

Q12: If a semaphore implementation allows negative values internally, what does a negative value represent?

Q13: Which synchronization primitive inherently supports ownership semantics?

Q14: If multiple readers enter the critical section simultaneously in Reader-Writer, which property is preserved?

Q15: In Banker's algorithm, a request is granted only if:

Quiz 7: Page Replacement

Q1: Which page replacement algorithm is generally best?

Q2: Belady's Anomaly occurs in which algorithm?

Q3: LRU requires tracking which information?

Q4: Which algorithm is optimal but impractical?