From The River To The Sea

Day 0: We still remember Gaza

Mohammed's avatar
Mohamed Mostafa

Software Engineer

OS Concepts Explained

This article provides detailed explanations of the operating system concepts implemented in SimuKernel.

Source code: https://github.com/Mo7ammedd/SimuKernel

Table of Contents

  1. CPU Scheduling
  2. Memory Management
  3. Process Management
  4. Performance Metrics

CPU Scheduling

What is CPU Scheduling?

CPU scheduling is the process of determining which process in the ready queue will be allocated the CPU for execution. The goal is to maximize CPU utilization, throughput, and minimize waiting time and response time.

Process States

A process transitions through several states:

  • New: Process is being created
  • Ready: Process is waiting to be assigned to CPU
  • Running: Instructions are being executed
  • Waiting: Process is waiting for I/O or event
  • Terminated: Process has finished execution

Scheduling Algorithms

1. Round Robin (RR)

How it works:

  • Each process gets a fixed time slice (quantum)
  • After quantum expires, process moves to end of ready queue
  • Next process in queue gets CPU
  • Preemptive algorithm

Advantages:

  • Fair allocation of CPU time
  • No starvation
  • Good for time-sharing systems
  • Predictable response time

Disadvantages:

  • Context switching overhead
  • Average waiting time can be high
  • Performance depends on time quantum selection

Time Quantum Selection:

  • Too small: High context switching overhead
  • Too large: Becomes FCFS, poor response time
  • Typical: 10-100 milliseconds

Example:

Processes: P1(burst=10), P2(burst=5), P3(burst=8)
Quantum = 4

Execution Order:
P1[0-4] → P2[4-8] → P3[8-12] → P1[12-16] → P2[16-17] → P3[17-21] → P1[21-22]

2. Priority Scheduling

How it works:

  • Each process has a priority number
  • CPU allocated to highest priority process
  • Can be preemptive or non-preemptive
  • Lower number = higher priority (convention)

Preemptive Priority:

  • Running process can be interrupted
  • New higher priority process gets CPU immediately

Non-Preemptive Priority:

  • Process runs to completion
  • Priority checked only when CPU becomes free

Advantages:

  • Important processes execute first
  • Good for real-time systems
  • Flexible based on process needs

Disadvantages:

  • Starvation: Low priority processes may never execute
  • Priority inversion in complex systems

Starvation Prevention:

  • Aging: Gradually increase priority of waiting processes
  • After threshold time, boost priority

Example:

Processes: P1(priority=3), P2(priority=1), P3(priority=4), P4(priority=2)

Non-Preemptive Order: P2 → P4 → P1 → P3
(Execution order by priority)

3. Multilevel Feedback Queue (MLFQ)

How it works:

  • Multiple queues with different priorities
  • Each queue has its own scheduling algorithm (usually RR)
  • Different time quantums for each level
  • Processes can move between queues

Queue Structure:

Queue 0 (Highest Priority) - Quantum: 2ms
Queue 1 (Medium Priority)  - Quantum: 4ms  
Queue 2 (Lowest Priority)  - Quantum: 8ms

Process Movement Rules:

  1. New processes enter highest priority queue
  2. If process uses entire quantum: Move down one level
  3. If process blocks (I/O): Stay in same level or move up
  4. If process waits too long (aging): Move up one level

Advantages:

  • Favors short jobs (I/O-bound)
  • Prevents starvation through aging
  • Adapts to process behavior
  • No need to know burst time in advance

Disadvantages:

  • Complex to implement
  • Requires parameter tuning
  • Can have high overhead

Real-World Use:

  • Linux CFS (Completely Fair Scheduler)
  • Windows Thread Scheduler
  • macOS Grand Central Dispatch

Memory Management

Virtual Memory

Concept:

  • Separation of logical and physical memory
  • Processes use virtual addresses
  • MMU (Memory Management Unit) translates to physical addresses
  • Allows running programs larger than physical RAM

Benefits:

  • Process isolation (security)
  • Efficient memory use
  • Simplified programming model
  • Support for shared libraries

Paging

How it works:

  • Divide memory into fixed-size blocks
  • Pages: Logical memory blocks (process view)
  • Frames: Physical memory blocks (hardware view)
  • Page table maps pages to frames

Page Table:

Virtual Page → Physical Frame
    0       →      2
    1       →      5
    2       →      1
    3       →      7

Address Translation:

Virtual Address = Page Number + Offset
Physical Address = Frame Number + Offset

Example:
Virtual: Page 2, Offset 100
Physical: Frame 1, Offset 100

Page Replacement Algorithms

When memory is full and new page needed, must replace existing page.

1. FIFO (First-In-First-Out)

Algorithm:

  • Maintain queue of pages in memory
  • Replace oldest page (first loaded)

Implementation:

Queue: [P1, P2, P3, P4]
New page P5 arrives → Replace P1
Queue: [P2, P3, P4, P5]

Advantages:

  • Simple to implement
  • Low overhead
  • Fair (all pages age equally)

Disadvantages:

  • Belady's Anomaly: More frames can cause more faults
  • Doesn't consider page usage patterns
  • May replace frequently used pages

Belady's Anomaly Example:

Reference: 1,2,3,4,1,2,5,1,2,3,4,5

3 Frames: 9 page faults
4 Frames: 10 page faults (worse!)

2. LRU (Least Recently Used)

Algorithm:

  • Replace page not used for longest time
  • Assumes: Recently used pages will be used again soon

Implementation:

  • Timestamp each page access
  • On replacement, choose minimum timestamp
  • Or use stack/counter

Advantages:

  • Better performance than FIFO
  • No Belady's anomaly
  • Approximates optimal

Disadvantages:

  • High overhead (tracking access times)
  • Requires hardware support
  • Complex implementation

Hardware Support:

  • Timestamp register
  • Stack of page numbers
  • Counter for each page table entry

Example:

Time: 0  1  2  3  4  5
Ref:  1  2  3  1  4  2

Access times when referencing page 5:
P1: 3, P2: 5, P3: 2, P4: 4
Replace P3 (oldest access)

3. Optimal Page Replacement

Algorithm:

  • Replace page that won't be used for longest time in future
  • Theoretical optimal (minimum possible faults)

Implementation:

  • Look ahead in reference string
  • For each frame, find next use time
  • Replace frame with farthest next use
  • If page never used again, replace it immediately

Advantages:

  • Minimum page faults (provably optimal)
  • Good benchmark for other algorithms

Disadvantages:

  • Impossible to implement (requires future knowledge)
  • Only useful for analysis and comparison

Example:

Reference: 1,2,3,4,1,2,5,1,2,3,4,5
Frames: 3

At step 6 (need to load page 5):
P1: next used at step 7 (distance: 1)
P2: next used at step 8 (distance: 2)  
P3: next used at step 10 (distance: 4)
P4: not used again (distance: ∞)

Replace P4 (optimal choice)

Page Fault Handling

Page Fault Process:

  1. CPU tries to access page not in memory
  2. MMU generates page fault interrupt
  3. OS locates page on disk
  4. Selects victim frame (if memory full)
  5. Writes victim page to disk (if modified)
  6. Loads requested page into frame
  7. Updates page table
  8. Restarts instruction

Page Fault Cost:

  • Trap to OS: ~1-10 microseconds
  • Disk access: ~1-10 milliseconds
  • Total: ~1000x slower than memory access

Process Management

Process Control Block (PCB)

Contains process information:

  • Process ID (PID)
  • Process state
  • Program counter
  • CPU registers
  • Memory management info
  • I/O status
  • Accounting information

Context Switch

What happens:

  1. Save state of current process to PCB
  2. Select next process to run
  3. Restore state from new process PCB
  4. Switch to user mode

Cost:

  • Direct: Saving/restoring registers
  • Indirect: Cache/TLB flush, pipeline stall
  • Typical: 1-10 microseconds

Process Creation

Unix/Linux (fork/exec):

parent process
    ↓
fork() → creates child with copy of parent memory
    ↓
exec() → replaces child memory with new program
    ↓
child executes new program

Performance Metrics

CPU Scheduling Metrics

1. Turnaround Time

Turnaround Time = Completion Time - Arrival Time

Total time from submission to completion.

2. Waiting Time

Waiting Time = Turnaround Time - Burst Time

Time spent in ready queue.

3. Response Time

Response Time = First Run Time - Arrival Time

Time from submission to first execution.

4. CPU Utilization

CPU Utilization = (Total CPU Busy Time / Total Time) × 100%

Percentage of time CPU is doing useful work.

5. Throughput

Throughput = Number of Processes / Total Time

Processes completed per time unit.

Memory Management Metrics

1. Page Fault Rate

Page Fault Rate = (Number of Page Faults / Total References) × 100%

2. Effective Access Time (EAT)

EAT = (1 - p) × memory_access_time + p × page_fault_time

where p = page fault rate

Example:

  • Memory access: 100 ns
  • Page fault time: 10 ms = 10,000,000 ns
  • Page fault rate: 0.1% = 0.001
EAT = 0.999 × 100 + 0.001 × 10,000,000
    = 99.9 + 10,000
    = 10,099.9 ns

3. Memory Utilization

Memory Utilization = (Used Memory / Total Memory) × 100%

Real-World Applications

Linux Process Scheduler

CFS (Completely Fair Scheduler):

  • Red-black tree of runnable processes
  • Each process has virtual runtime (vruntime)
  • Runs process with smallest vruntime
  • Time slice based on nice value and number of processes

Windows Memory Manager

Working Set Management:

  • Each process has working set (pages in physical memory)
  • Minimum and maximum working set sizes
  • Page frame database tracks all physical memory
  • Modified page writer writes dirty pages to disk

Android Process Management

Low Memory Killer:

  • Processes assigned priority levels
  • When memory low, kills lowest priority processes
  • Background apps killed before foreground
  • System services protected

Further Reading