Module1_Fundamentals_of_OS_Notes.

md 2026-07-26

Module 1: Fundamentals of Operating System (OS)

Notes prepared for DJS22EC6014 — Operating Systems, Sem VI (based on GeeksforGeeks explanations,
simplified for quick revision)

1. What is an Operating System?

An Operating System (OS) is system software that sits between the user and the computer hardware. You
never talk to the hardware directly — the OS does that for you, and in return gives you a simple, friendly
environment to run your programs.

Think of it like a restaurant manager: you (the user) don't go into the kitchen (hardware) and cook yourself.
You tell the manager (OS) what you want, and the manager coordinates the kitchen staff (CPU, memory, disk,
etc.) to get it done.

Key point: The OS is always running in the background — it's the one program that never stops as long as
the computer is on.

A computer system is generally seen as 4 layers, from bottom to top:

1. Hardware – CPU, memory, I/O devices, storage

2. Operating System – controls and coordinates hardware use
3. System Programs – compilers, editors, loaders
4. Application Programs – browsers, games, office software, etc.

2. Objectives of an Operating System

Objective What it means

Convenience Makes the computer easy and pleasant to use

Efficiency Ensures CPU, memory, and devices are used optimally

Ability to Evolve Should allow new features to be added without breaking existing services

Resource Management Fairly allocates CPU, memory, disk, and I/O among competing programs

Security & Protection Prevents unauthorized access to data and resources

3. Functions of an Operating System

The OS performs several core jobs simultaneously:

Process Management – creating, scheduling, and terminating processes

Memory Management – allocating and freeing memory for processes
File Management – creating, organizing, and controlling access to files
I/O / Device Management – controlling all input-output devices via drivers
Security & Access Control – protecting data and resources from misuse
1/6
Module1_Fundamentals_of_OS_Notes.md 2026-07-26

Error Detection – catching and handling hardware/software errors so the system stays stable
Job Accounting – keeping track of resource usage (useful for billing/auditing in shared systems)

In short: the OS hides hardware complexity and gives you a clean interface (sometimes called a "virtual
machine") to work with.

4. Evolution of Operating Systems

OS design has evolved in stages as hardware improved:

1. No OS (1940s) – Programs were fed directly in machine language; no software layer existed at all.
2. Batch Processing Systems – Similar jobs were grouped ("batched") on punch cards and fed to the
computer one batch at a time, with no user interaction during execution. This removed the need for an
operator to manually handle each job.
3. Multiprogramming Systems – Multiple programs are kept in memory together. When one program is
waiting for I/O (which is slow), the CPU switches to another ready program instead of sitting idle. This
was the real turning point in OS design because it boosted CPU utilization.
4. Time-Sharing Systems – An extension of multiprogramming where the CPU's time is split into small
slices and given to multiple users, so each one feels like they have the system to themselves.
5. Modern/Distributed/Mobile/AI-integrated Systems – Today's OS (Windows, Linux, Android, iOS)
handle networking, multiple cores, mobile devices, and even AI-based features like voice assistants.

Note: Newer generations didn't fully replace older ones — batch and time-sharing concepts still exist in
specific niche use-cases (e.g., mainframes, servers) alongside modern systems.

5. Services of an Operating System

An OS provides a set of common services so that both users and programs don't need to reinvent basic
functionality:

Program Execution – loading and running programs

I/O Operations – handling input/output on behalf of programs, since users can't touch devices directly
File System Manipulation – creating, reading, writing, deleting files and directories
Communication – enabling data exchange between processes (on the same machine or over a
network)
Error Detection & Handling – detecting problems in CPU, memory, or devices and dealing with them
so the system doesn't crash
Resource Allocation – dividing CPU, memory, and devices fairly among multiple running programs
Security & Protection – controlling access so one user/program cannot interfere with another
Accounting – logging how much of each resource every user/process consumes

6. Types of Operating Systems

Type Core Idea Example

Jobs collected and run in groups without user

Batch OS Old mainframes
interaction
2/6
Module1_Fundamentals_of_OS_Notes.md 2026-07-26

Type Core Idea Example

Multiprogramming Multiple programs reside in memory; CPU switches

Early UNIX
OS to keep busy during I/O waits

CPU time is divided into slices shared across multiple

Time-Sharing OS Windows NT, UNIX
users for quick, interactive response

Uses more than one CPU/processor to run tasks

Multiprocessing OS Modern servers
faster and provide fault tolerance

Multiple independent computers connected over a

Distributed OS network act like a single system; users can access Network-based systems
remote files/resources

Used in
Real-Time OS Designed to meet strict timing deadlines for critical
embedded/avionics
(RTOS) tasks (hard or soft real-time)
systems

Manages data, users, groups, security, and access for

Network OS Windows Server
a group of computers on a network

Optimized for touch, battery life, and mobile

Mobile OS Android, iOS
hardware

7. Operating System as a Resource Manager

The OS can be viewed simply as a resource manager — its job is to keep track of who is using what, grant
requests fairly, and resolve conflicts when multiple programs want the same resource at once.

Resources it manages include:

CPU time (via scheduling)

Memory (via allocation/deallocation)
I/O devices (via device drivers and queues)
Files and storage (via the file system)

This "resource manager" view is one of the fundamental ways to define and understand what an OS actually
does — instead of thinking of it purely as a user interface, you think of it as a fair, efficient traffic controller for
hardware.

8. System Calls
A system call is the only official doorway a user program has into the OS kernel. Whenever a program needs
something only the kernel can safely provide (like reading a file, creating a process, or talking over the
network), it must go through a system call — it cannot touch hardware or protected resources directly.

Why it matters: This keeps the system stable and secure — user programs run in user mode (restricted),
while the kernel runs in kernel mode (privileged). A system call temporarily switches the CPU into kernel
mode to safely perform the requested operation, then switches back.

3/6
Module1_Fundamentals_of_OS_Notes.md 2026-07-26

Categories of System Calls

Category Purpose Example calls

Create, execute, terminate, or synchronize

Process Control fork(), exec(), exit()
processes

open(), read(), write(),

File Management Create, open, read, write, close files
close()

Request/release devices, read/write to

Device Management ioctl(), read(), write()
devices

Information
Get/set system data like time, process ID getpid(), alarm(), sleep()
Maintenance

pipes, message passing, shared

Communication Exchange data between processes
memory

Good to remember: A system call causes a mode switch (user → kernel), but it doesn't automatically cause a
context switch — a context switch only happens if the calling process actually has to block/wait.

9. Shell
The shell is the outer layer of the OS that a user directly interacts with — it takes commands from the user
(typed or scripted) and translates them into actions the kernel can perform.

Kernel = inner core, handles hardware-level work (process, memory, I/O management)
Shell = outer layer, handles user interaction (also called "user space")

Types of Shells

Command-Line Shell (CLI) — user types text commands (e.g., Bash in Linux). Lightweight, fast,
preferred by developers/sysadmins.
Graphical Shell (GUI) — user interacts via windows, icons, and menus (e.g., Windows Explorer, GNOME
Shell).

Shell scripting lets you write a sequence of commands into a file so the shell can run them automatically —
useful for automating repetitive tasks, and it supports loops and conditional logic.

10. Operating System Structures (Design Approaches)

How the internal components of an OS are organized affects its performance, reliability, and ease of
maintenance. Common structures:

a) Simple / Monolithic Structure

The entire OS — process management, memory management, file systems, device drivers — is built as
one large program running in a single address space (kernel mode).
Advantage: Fast, since components can call each other directly without overhead.

4/6
Module1_Fundamentals_of_OS_Notes.md 2026-07-26

Disadvantage: Poor fault isolation — a bug in any part can crash the whole system; hard to maintain as
it grows large. MS-DOS is a simple/monolithic example; UNIX and Linux use a monolithic kernel.

b) Layered Structure

The OS is broken into a stack of layers (Layer 0 at the bottom = hardware, topmost layer = user
interface).
Each layer only uses services from the layer directly below it — this is called abstraction, since a layer
doesn't need to know how lower layers actually work internally.
Advantage: Easier to design, debug, and maintain since responsibilities are isolated per layer.
Disadvantage: Slower — a request may have to pass through many layers to get serviced, and careful
planning is needed to decide the order of layers. Example: Windows NT partly follows this approach.

c) Microkernel Structure

Keeps only the bare minimum inside the kernel — typically just IPC (inter-process communication),
basic process scheduling, and minimal hardware handling.
Everything else (device drivers, file systems, network services) runs as separate processes in user space,
and they talk to the microkernel via message passing.
Advantage: More secure and reliable — if a user-space service crashes, the whole system doesn't go
down; also easier to extend without touching the kernel.
Disadvantage: Message passing between user space and kernel is slower than direct function calls in a
monolithic kernel, so raw performance can suffer. Example: MINIX, Mach.

d) Monolithic Kernel vs Microkernel (quick comparison)

Aspect Monolithic Kernel Microkernel

Where services run All in kernel space Only essentials in kernel; rest in user space

Speed Faster (direct calls) Slower (message passing overhead)

Stability/Security One failure can crash system Failures isolated to individual services

Modularity Harder to extend/modify Easy to add new services

Examples Linux, UNIX MINIX, Mach

(Hybrid kernels, like macOS's XNU, blend both approaches — monolithic speed with some microkernel-style
modularity.)

e) Client-Server Model

The OS (or a system) is organized around two roles: clients that request services, and servers that
provide them.
The "kernel" can be reduced to just handling communication (message passing) between clients and
servers — most actual work (file service, process service, etc.) is done by server processes, often running
in user space.
This model works whether the client and server are on the same machine or across a network, which
makes it a natural fit for distributed systems.

5/6
Module1_Fundamentals_of_OS_Notes.md 2026-07-26

Advantage: Centralized control of services, easier to scale (add more servers), easier security
enforcement.
Disadvantage: Communication (request–response) adds overhead compared to direct function calls.

Quick Revision Summary

OS = interface between user and hardware; also seen as a resource manager.
Objectives: convenience, efficiency, evolve-ability, security.
Evolution: No OS → Batch → Multiprogramming → Time-Sharing → Modern/Distributed/Mobile.
Types: Batch, Multiprogramming, Time-Sharing, Multiprocessing, Distributed, Real-Time, Network,
Mobile.
System calls = controlled entry into kernel mode (Process Control, File Management, Device
Management, Information Maintenance, Communication).
Shell = user-facing layer (CLI or GUI); Kernel = hardware-facing core.
Structures: Monolithic (fast, less safe) → Layered (organized, slower) → Microkernel (modular, secure,
message-passing overhead) → Client-Server (good for distributed setups).

Source basis: GeeksforGeeks Operating Systems articles, rewritten and simplified for study purposes.

6/6
Module2_Process_Management_Notes.md 2026-07-26

Module 2: Process Management

Notes prepared for DJS22EC6014 — Operating Systems, Sem VI (based on GeeksforGeeks explanations,
simplified for quick revision)

1. What is a Process?
A process is simply a program in execution. A program sitting on disk is just static code and data — the
moment it starts running, the OS turns it into an active process by giving it memory, a program counter,
registers, and other runtime resources.

Program vs Process (quick distinction):

Program Process

Passive — just code stored on disk Active — code currently executing

Has no resources of its own Owns CPU time, memory, open files, etc.

Static entity Dynamic entity, changes state over time

Attributes of a Process

A process isn't just "the code" — the OS needs to track several attributes for it, including:

Process ID (PID) – unique identifier

Process State – current status (new, ready, running, waiting, terminated)
Program Counter – address of the next instruction to execute
CPU Registers – values that must be saved/restored during switching
Priority & Scheduling Info – used to decide when this process gets the CPU
Memory/Address space info – code, data, stack, heap boundaries
List of open files and I/O devices in use

All of this information is stored together in a structure called the Process Control Block (PCB).

2. Process Control Block (PCB)

The PCB (sometimes called a Task Control Block) is a data structure the OS maintains for every single
process — it's essentially the process's "identity card" that the OS uses to manage and control it.

What's inside a PCB

Process ID (PID)
Process State
Program Counter
CPU registers
CPU scheduling info (priority, pointers to scheduling queues)

1/7
Module2_Process_Management_Notes.md 2026-07-26

Memory management info

Accounting info (CPU used, time limits)
I/O status info (open files, allocated devices)

Why the PCB matters

Context Switching: When the OS switches from one process to another, it saves the current process's
CPU register values into its PCB, and loads the incoming process's saved values from its own PCB — this
is exactly what lets a paused process resume later as if nothing happened.
Resource Sharing: The PCB records exactly what resources (files, memory) a process is holding, so the
OS can manage sharing and avoid conflicts.
Security: The PCB is kept in protected OS memory so ordinary user programs can't tamper with it.

All PCBs together are stored in the Process Table — an array/list where the OS can quickly look up a process's
PCB using its PID.

3. Process Creation
Processes are created when:

A user launches a program

The OS starts a system-initialization process
A running process spawns another (very common in Unix/Linux)

On Unix-like systems, a new process is normally created using the fork() system call:

fork() makes a copy of the calling process. The process that called it becomes the parent, and the
new copy is the child.
The child gets its own unique PID, but starts out as an (almost) identical copy of the parent — same
code, but a separate memory space.
After fork(), both parent and child continue running from the same point in the code — the return
value tells them apart (0 in the child, child's PID in the parent).
Very often, the child then calls exec() to replace its own memory image with a completely new
program — this is the classic fork + exec pattern used to launch new programs from a shell.

Process Termination

A process ends when:

Normal exit – it finishes its work and calls exit(); the OS reclaims its memory, files, and other
resources.
Killed by the OS or its parent – e.g., the task is no longer needed, or it exceeded its resource limit.
Cascading termination – if a parent process is terminated, all its child processes are terminated too.

4. Process States
A process moves through several states during its lifetime. The simplest model has just 2 states, but real
operating systems use a richer model.

2/7
Module2_Process_Management_Notes.md 2026-07-26

a) Two-State Model (simplest view)

Running – currently being executed by the CPU

Not Running – waiting for its turn (this state alone doesn't distinguish why it's waiting)

b) Five-State Model (the standard one used in most textbooks)

State Meaning

New Process is being created; PCB is set up but it hasn't started

Ready Loaded in memory, waiting for the CPU to become free

Running Currently executing on the CPU (only one process per CPU core at a time)

Blocked/Waiting Cannot continue — waiting on I/O completion or some event

Terminated/Exit Finished execution (or was killed); OS is cleaning up its resources

Typical State Transitions

New → Ready – after creation and admission into the ready queue
Ready → Running – the scheduler picks this process ("dispatch")
Running → Ready – time slice expires (preemption) even though the process isn't done
Running → Blocked – process requests I/O or waits for an event/resource
Blocked → Ready – the awaited event completes, process rejoins the ready queue
Running → Terminated – process finishes or is aborted

c) Extended Model with Suspend States

Some systems add two more states to handle memory pressure — moving a waiting/ready process out of
main memory into secondary storage (swapping):

Suspended-Ready – ready to run, but swapped out of main memory

Suspended-Blocked – waiting on an event, and also swapped out of main memory

(This gives the well-known "7-state process model" seen in some textbooks.)

Tip for the transition diagram in your exam: always show the 5 core states as boxes with arrows labeled by
the reason for transition (dispatch, timeout, I/O wait, I/O completion, exit) — that's what examiners look for.

5. Types of Schedulers
The OS uses different schedulers to decide which process gets a resource and when. They operate at different
frequencies and levels:

Also
Scheduler Job Frequency
Called

Long-Term Job Decides which jobs/programs are Runs rarely (controls degree
Scheduler Scheduler admitted into memory (New → Ready) of multiprogramming)

3/7
Module2_Process_Management_Notes.md 2026-07-26

Also
Scheduler Job Frequency
Called

Short-Term CPU Decides which ready process gets the Runs very frequently
Scheduler Scheduler CPU next (Ready → Running) (milliseconds)

Temporarily swaps processes out of

Medium-Term
— memory to reduce load, and swaps Runs occasionally, as needed
Scheduler
them back in later

Preemptive vs Non-Preemptive Scheduling

Aspect Preemptive Non-Preemptive

Can OS interrupt a Yes — CPU can be forcibly taken No — process keeps the CPU until it
running process? away finishes or blocks itself

On time-slice expiry, higher- Only when the process voluntarily gives up

When CPU switches
priority arrival, etc. the CPU (completion or I/O wait)

Overhead Higher (more context switches) Lower

Round Robin, SRTF, Preemptive

Example algorithms FCFS, Non-preemptive SJF
Priority

Time-sharing/interactive
Use case Simple batch systems
systems

Simple way to remember: Preemptive = "the CPU can be taken away from you"; Non-preemptive = "once you
have the CPU, you keep it till you're done or you ask to wait."

6. CPU Scheduling Algorithms

Algorithm Idea Preemptive? Key Drawback

FCFS (First A long job can make

Processes run strictly in arrival order
Come First No everyone else wait
(FIFO queue)
Served) ("convoy effect")

Needs to know burst time

SJF (Shortest Process with smallest burst time runs No (in its
in advance; long jobs may
Job First) first basic form)
starve

SRTF (Shortest Preemptive version of SJF — a new Same starvation risk for
Remaining arrival with a shorter remaining time Yes long jobs, plus more
Time First) can interrupt the current process context switches

Priority Each process gets a priority number; Can be either Low-priority processes
Scheduling highest priority runs first may starve; solved using
aging (gradually raising

4/7
Module2_Process_Management_Notes.md 2026-07-26

Algorithm Idea Preemptive? Key Drawback

priority the longer a
process waits)

Too small a quantum →

Each process gets a fixed time slice
Round Robin too many context
("quantum"); if not finished, it goes to Yes
(RR) switches; too large →
the back of the ready queue
behaves like FCFS

Picks the job with the highest response

HRRN (Highest
ratio, balancing waiting time against More complex to
Response Ratio No
burst time so long-waiting jobs calculate than FCFS/SJF
Next)
eventually get priority

Ready queue is split into several

Multilevel separate queues (e.g., Rigid — a process is
Queue foreground/interactive vs Varies generally stuck in the
Scheduling background/batch), each with its own queue it was assigned to
algorithm

Like multilevel queue, but processes can

Multilevel
move between queues based on their Most flexible, but most
Feedback Yes
behavior (e.g., CPU-bound processes complex to configure
Queue
get demoted)

Common metrics used to compare these algorithms:

Waiting Time – time spent in the ready queue

Turnaround Time – total time from arrival to completion
Response Time – time from arrival to the first time it gets the CPU
Throughput – number of processes completed per unit time
CPU Utilization – percentage of time the CPU is actually busy

7. Types of Threads
A thread is the smallest unit of CPU execution within a process — sometimes called a "lightweight process." A
single process can have multiple threads that share the same memory/resources but execute independently.

a) User-Level Threads (ULT)

Created and managed entirely by a user-level thread library — the kernel doesn't even know they
exist; it just sees one regular process.
Fast to create and switch between (no kernel involvement needed).
Drawback: If one user thread makes a blocking system call, the entire process can get blocked, since
the kernel only sees a single thread of control.

b) Kernel-Level Threads (KLT)

Created, scheduled, and managed directly by the operating system kernel.

5/7
Module2_Process_Management_Notes.md 2026-07-26

The kernel is aware of each individual thread, so it can schedule them independently — allowing true
parallel execution on multiple CPU cores.
Drawback: Slower to create/switch than user-level threads, since every thread operation needs a
system call into the kernel.

Aspect User-Level Threads Kernel-Level Threads

Managed by Thread library (user space) OS kernel

Creation/switching speed Fast Slower

Blocking system call Blocks entire process Only that thread blocks

Multiprocessor support Poor (kernel unaware) Good (kernel schedules each)

Hardware/OS support needed No Yes

8. Multithreading Models
These models describe how user-level threads are mapped to kernel-level threads.

a) Many-to-One Model

Many user-level threads map to just one kernel thread.

Thread management happens entirely in user space → very efficient.
Big drawback: if any one thread makes a blocking system call, the entire process blocks, since only one
thread can access the kernel at a time. Also can't take advantage of multiple CPU cores.

b) One-to-One Model

Each user-level thread maps to its own separate kernel thread.

Allows true concurrency — multiple threads of the same process can run in parallel on a multiprocessor,
and if one thread blocks, the others keep running.
Drawback: Creating a user thread means creating a matching kernel thread too, so there's more
overhead, and OS designers often cap the number of threads for this reason. (Used in Windows and
Linux.)

c) Many-to-Many Model

Many user-level threads are multiplexed over a smaller or equal number of kernel threads.
Combines the best of both worlds: the OS can create as many kernel threads as needed for parallelism,
while the application can still create as many user threads as it wants without overloading the kernel.
Considered the most flexible model — if one thread blocks, the kernel can schedule another user
thread on a different kernel thread, so the whole process doesn't stall.

Model Mapping Blocking Problem? Multiprocessor Use

Many-to-One Many ULT → 1 KLT Yes (whole process blocks) No

One-to-One 1 ULT → 1 KLT No (only that thread blocks) Yes

Many-to-Many Many ULT → Many (≤) KLT No Yes

6/7
Module2_Process_Management_Notes.md 2026-07-26

Quick Revision Summary

Process = program in execution; tracked via its PCB (PID, state, program counter, registers, scheduling
info, memory info).
Processes are created via fork() (copy) and often followed by exec() (replace with new program); they
end via exit() or termination by parent/OS.
States: New → Ready → Running → (Blocked ↔ Ready) → Terminated, with optional Suspend-
Ready/Suspend-Blocked states.
Schedulers: Long-term (admits jobs), Short-term (picks next process for CPU), Medium-term (swaps
processes in/out).
Preemptive = CPU can be taken away; Non-preemptive = process keeps CPU till done/blocked.
Scheduling algorithms: FCFS, SJF/SRTF, Priority, Round Robin, HRRN, Multilevel Queue, Multilevel
Feedback Queue.
Threads: User-level (fast, but one block affects all) vs Kernel-level (true parallelism, more overhead).
Multithreading models: Many-to-One (simple but blocking risk), One-to-One (true concurrency but
overhead), Many-to-Many (best of both).

Source basis: GeeksforGeeks Operating Systems articles, rewritten and simplified for study purposes.

7/7
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Module 3: Concurrency and Deadlock

Notes prepared for DJS22EC6014 — Operating Systems, Sem VI (based on GeeksforGeeks explanations,
simplified for quick revision)

PART A: CONCURRENCY
1. Principles of Concurrency
Concurrency means multiple processes (or threads) making progress "at the same time" — either truly in
parallel (multiple CPUs) or interleaved on a single CPU that switches rapidly between them.

The OS contains two broad categories of processes:

System processes – execute OS code

User processes – execute user/application code

Concurrent processes can be:

Independent – don't share data with any other process, so they can't affect or be affected by others.
Cooperating – share data or resources with other processes, which means their outcomes can depend
on execution order — this is exactly where synchronization problems come from.

Why concurrency is tricky: when cooperating processes access shared data at the same time without
coordination, the final result can depend on the unpredictable order in which their instructions get interleaved
by the CPU scheduler. This is called a race condition, and avoiding it is the whole point of process
synchronization.

2. Inter-Process Communication (IPC)

IPC is the set of mechanisms that let processes exchange data and coordinate their actions, since each process
normally has its own private memory space and can't just read another process's variables directly.

Example: think of an ATM system — one process reads your card and PIN, another checks your account
balance, and a third dispenses the cash. These separate processes must communicate to complete a single
transaction correctly.

Two Main IPC Methods

Method How it Works Speed Notes

The kernel sets up a common Needs the programmer to handle

Shared Fastest IPC
memory region that multiple synchronization (locks/semaphores)
Memory method
processes can directly read/write since there's no built-in protection

1/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Method How it Works Speed Notes

Processes exchange data via Slower Safer — processes don't touch each
Message
send()/receive() calls; the (kernel other's memory directly, so fewer
Passing
kernel manages delivery overhead) synchronization headaches

Other Common IPC Mechanisms

Pipes – a one-way (or two-way) communication channel, often used between a parent and child
process
Message Queues – messages sit in a kernel-managed queue until the receiving process picks them up;
supports asynchronous communication
Semaphores – used alongside shared memory to control access and avoid conflicts
Signals – used to notify a process that an event has occurred

Challenges of IPC

Poor coordination between communicating processes can lead to race conditions, deadlock, starvation,
and data inconsistency — which is exactly why synchronization tools exist.

3. Process / Thread Synchronization

Key Terms

Critical Section: the part of a program where a process accesses shared resources (variables, files,
memory) that must not be touched by more than one process at the same time.
Race Condition: occurs inside a critical section when the final outcome depends on the unlucky/lucky
order in which multiple processes' instructions get interleaved.
Preemption: the OS pausing a running process to give the CPU to another — if this happens in the
middle of a critical section without protection, it can cause an inconsistent read/write.

Classic example of a race condition: Suppose balance = 100. Process P1 wants to add 10; Process P2
wants to subtract 10. If P1 reads balance=100, gets interrupted before writing back, and P2 also reads
balance=100, subtracts 10, and writes 90 — then when P1 resumes and writes 110, the final balance ends up
wrong (should have been 100, but ends up as 90 or 110 depending on timing). This is why unsynchronized
access to shared data is dangerous.

The Critical Section Problem — 3 Requirements

Any good synchronization solution must guarantee:

1. Mutual Exclusion – no two processes may be inside their critical sections at the same time.
2. Progress – if no process is in the critical section, and some processes want to enter, the decision of who
enters next cannot be postponed indefinitely (no unnecessary blocking).
3. Bounded Waiting – there must be a limit on how many times other processes are allowed to enter the
critical section before a waiting process gets its turn (prevents starvation).

4. Mutual Exclusion — Requirements & Support

2/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Mutual Exclusion simply means: no two processes can be executing in their critical section at the same point in
time. It was a term first introduced by Dijkstra, and it's the foundation every synchronization mechanism is
built on.

General Requirements for any Mutual Exclusion Solution

Only one process may be in its critical section at any time.

No assumptions should be made about the relative speed of processes.
A process running outside its critical section must not block other processes from entering theirs.
A process must not be forced to wait forever to enter its critical section.

a) Software Support (no special hardware needed)

Peterson's Algorithm – a classic solution for exactly two processes; uses a turn variable and flag
array to guarantee mutual exclusion, progress, and bounded waiting.
Dekker's Algorithm – one of the earliest two-process solutions, also using flags and a turn variable.
Bakery Algorithm – extends the idea to multiple processes, working like a "take-a-number" system at a
shop counter — whoever has the lowest number goes first.

(Drawback: software solutions are relatively complex to get exactly right and can be error-prone.)

b) Hardware Support (uses special atomic CPU instructions)

Test-and-Set (TSL): Atomically checks a lock variable's value and sets it to "locked" in a single
indivisible step — so no other process can sneak in between the check and the set.
Swap Instruction: Similarly exchanges the values of two variables atomically.

Hardware instructions are fast, since they're a single indivisible CPU instruction, but on their own they still rely
on busy waiting (a process keeps checking the lock in a loop, wasting CPU cycles) and don't fully guarantee
bounded waiting or fairness.

Because of the drawbacks of both software and hardware locks, operating systems introduced higher-
level tools: Semaphores and Monitors.

5. Semaphores and Mutex

Semaphore

A semaphore is an integer variable that can only be accessed through two special atomic operations:

wait() (also called P) – decrements the semaphore; if the result is negative, the calling process is
blocked.
signal() (also called V) – increments the semaphore and wakes up a waiting process, if any.

Because a blocked process is put to sleep (rather than busy-waiting in a loop), semaphores avoid wasting CPU
cycles.

Types of Semaphores:

3/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Type Values Use

Binary Used like a simple lock — 0 means locked/unavailable, 1

Only 0 or 1
Semaphore means unlocked/available

Counting Any non-negative Used to manage a pool of identical resources (e.g., a fixed
Semaphore integer number of printers)

Mutex (Mutual Exclusion Lock)

A mutex is a simpler locking mechanism specifically meant for mutual exclusion — think of it as a key:
whichever thread holds the mutex "key" can enter the critical section; everyone else must wait.

Mutex vs Binary Semaphore (a common exam question!)

Aspect Mutex Binary Semaphore

Locking mechanism, strictly for Signaling mechanism; can also coordinate between
Purpose
mutual exclusion different threads

Only the thread that locked it can Can be signaled by a different thread than the one
Ownership
unlock it that waited on it

Value
Locked / Unlocked 0 or 1
range

Coordinating events between multiple threads (e.g.,

Typical use Protecting a single critical section
producer-consumer)

Simple way to remember: Mutex = "only I can unlock what I locked." Semaphore = "a more general signaling
tool that anyone can raise or lower."

PART B: DEADLOCK
6. Principles of Deadlock
Deadlock is a situation where a set of processes are all blocked, each holding a resource while waiting for
another resource that's held by a different process in the same set — so nobody can move forward.

Classic analogy: two trains approaching each other on the same single track — once they're face-to-face,
neither can move, because moving forward requires the other to move first (which it also can't do).

Important property: Deadlock is not something that resolves itself — once a set of processes is deadlocked,
they stay that way forever unless there's outside intervention (like the OS killing a process).

7. Necessary Conditions for Deadlock (Coffman Conditions)

Deadlock can only occur if all four of these conditions hold simultaneously:

4/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Condition Meaning

Mutual At least one resource must be held in a non-shareable way — only one process can
Exclusion use it at a time (e.g., a printer)

A process is holding at least one resource while waiting to acquire additional resources
Hold and Wait
held by others

A resource cannot be forcibly taken away from a process — it can only be released
No Preemption
voluntarily

A closed chain of processes exists where each one is waiting for a resource held by the
Circular Wait
next process in the chain

Remember: breaking even one of these four conditions is enough to prevent deadlock — this is exactly the
logic behind deadlock prevention techniques (see below).

8. Resource Allocation Graph (RAG)

A Resource Allocation Graph is a visual way to represent which processes hold which resources, and which
processes are waiting for which resources.

Process node – represented as a circle

Resource node – represented as a box (may contain multiple instances/dots if there are multiple units)
Assignment edge (Resource → Process) – means the resource is currently allocated to that process
Request edge (Process → Resource) – means the process is currently waiting for that resource

Reading the Graph

No cycle in the graph → no deadlock, guaranteed.

Cycle exists + each resource type has only ONE instance → deadlock is guaranteed.
Cycle exists + some resource types have MULTIPLE instances → deadlock is only possible, not
guaranteed — you need to check if requirements can still be satisfied by the remaining available
resources.

In short: a cycle is a necessary condition for deadlock, but only sufficient when every resource type in the
cycle has just a single instance.

9. Deadlock Prevention
Deadlock prevention works by making sure at least one of the four Coffman conditions can never happen in
the system:

Condition to
How
Break

Hard to eliminate for inherently non-shareable resources (like a tape drive); for others
Mutual
like printers, use spooling — jobs are queued instead of directly waiting for the device,
Exclusion
so processes don't have to wait for exclusive access

5/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Condition to
How
Break

Hold and Require a process to request all the resources it will ever need before it starts executing,
Wait or force it to release everything it's currently holding before requesting anything new

Allow the OS to forcibly take resources away from a waiting process (and give them back
No
later), or require a process to release all held resources if a new request can't be
Preemption
immediately satisfied

Impose a strict, unique numbering on all resource types, and require every process to
Circular Wait request resources only in increasing order of that number — this makes a circular chain
of requests impossible

Trade-off: Prevention techniques tend to be conservative — they reduce resource utilization and system
throughput because they restrict how freely processes can request resources.

10. Deadlock Avoidance — Banker's Algorithm

Deadlock Avoidance takes a more flexible approach than prevention: instead of permanently restricting how
resources can be requested, the OS makes a dynamic decision each time — it only grants a request if doing
so keeps the system in a "safe state."

Safe State: a state where there exists at least one order (a "safe sequence") in which all processes can
finish, one after another, using only the currently available resources plus what gets released as each
process completes.
Unsafe State: a state where no such safe sequence can be guaranteed — this doesn't necessarily mean
deadlock has happened, but it means deadlock could happen. The OS avoids ever entering such a state.

Banker's Algorithm — Data Structures

For a system with n processes and m resource types:

Structure Size Meaning

1-D array of
Available Available[j] = k → k instances of resource type Rj are currently free
size m

Max[i][j] = k → process Pi may request at most k instances of Rj (its

Max n × m matrix
maximum declared need)

Allocation n × m matrix Allocation[i][j] = k → process Pi currently holds k instances of Rj

Need[i][j] = Max[i][j] − Allocation[i][j] → how many more

Need n × m matrix
instances of Rj process Pi may still request

a) Safety Algorithm (checks if the current state is safe)

1. Initialize Work = Available, and mark all processes as Finish = false.

2. Find a process Pi where Finish[i] = false and Need[i] ≤ Work. If none exists, go to step 4.

6/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

3. Assume Pi gets all resources it needs, finishes, and releases them back: Work = Work +
Allocation[i]; set Finish[i] = true; go back to step 2.
4. If Finish[i] = true for all processes, the system is in a safe state.

b) Resource-Request Algorithm (checks if a specific request can be safely granted)

When process Pi requests some resources:

1. Check Request[i] ≤ Need[i] — if not, the process has exceeded its declared maximum, which is an
error.
2. Check Request[i] ≤ Available — if not enough resources are free, Pi must simply wait.
3. Pretend to allocate the requested resources (temporarily update Available, Allocation, and Need).
4. Run the Safety Algorithm on this new hypothetical state:
If it comes out safe → the request is genuinely granted.
If it comes out unsafe → roll back the pretend allocation, and Pi must wait.

(This same logic extends naturally to multiple resource types — you just work with vectors instead of single
numbers for Available/Allocation/Need/Max across all resource columns simultaneously.)

Limitation of Banker's Algorithm: it requires knowing the maximum resource demand of every process in
advance, which isn't always practical in real systems — and it tends to be conservative (a process might finish
using far less than its declared maximum).

11. Deadlock Detection and Recovery

If a system doesn't use prevention or avoidance, deadlocks may actually occur — so the OS instead
periodically checks for deadlock and recovers from it when found.

Detection Techniques

Wait-For Graph: A simplified version of the resource allocation graph, showing only process-to-
process edges (P1 → P2 means P1 is waiting for a resource held by P2). A cycle in this graph indicates a
deadlock.
Resource Allocation Graph: As discussed above — look for cycles, keeping in mind the single-instance
vs multi-instance distinction.
Detection Algorithm (multi-instance case): Similar in structure to the Banker's Safety Algorithm —
using Available, Allocation, and Request matrices, the algorithm checks whether every process can
eventually get what it needs; if some processes are left permanently unable to proceed, they're
deadlocked.

Recovery Techniques

Once a deadlock is confirmed, the OS can recover using:

1. Process Termination

Abort all deadlocked processes – breaks the deadlock immediately but wastes all their work-in-
progress.

7/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Abort one process at a time – terminate processes one by one (checking after each) until the
deadlock cycle is broken; less wasteful, but requires repeated detection checks.

2. Resource Preemption – forcibly take resources away from some processes in the deadlock and give
them to others. This raises three practical issues:

Selecting a victim – deciding which process/resource to preempt, ideally minimizing cost.

Rollback – deciding how far back to roll back the affected process (often a full restart).
Starvation – making sure the same process isn't repeatedly chosen as the victim every time.

3. Process Rollback – roll a deadlocked process back to an earlier safe checkpoint (requires the system to
periodically save process state), rather than aborting it completely.

Choosing a victim usually considers: process priority, how much execution time would be lost, how many
resources it holds, and how expensive rollback would be — interactive processes are generally spared over
batch processes where possible.

12. Dining Philosophers Problem

A classic example used to illustrate deadlock and starvation in resource-sharing systems.

Setup: n philosophers sit around a circular table. Between every adjacent pair of philosophers, there is exactly
one chopstick (so n chopsticks total for n philosophers). Each philosopher alternates between thinking and
eating — but to eat, a philosopher needs both chopsticks on either side of them.

Where deadlock can arise: If every philosopher simultaneously picks up the chopstick to their left first, then
all chopsticks get taken at once, and every philosopher is left waiting forever for the chopstick to their right
(which their neighbor is holding) — this is a circular wait, and the system deadlocks.

Common solutions:

Semaphore-based: Represent each chopstick as a binary semaphore; a philosopher must successfully

acquire both adjacent semaphores before eating, and releases both when done. (Needs extra care — a
naive version can still deadlock if all philosophers grab their left chopstick at once.)
Resource ordering / asymmetry: Break the symmetry — e.g., have one philosopher pick up their right
chopstick first instead of left, which prevents the circular wait from forming.
Monitor-based: Use a monitor with condition variables so a philosopher only picks up chopsticks if
both are available at the same time — this naturally avoids deadlock, though a correct deadlock-free
solution isn't automatically starvation-free too (a philosopher could still theoretically wait a long time if
unlucky).

Goal of any correct solution:

Free from Deadlock – every philosopher eventually gets a chance to eat.

Free from Starvation – no philosopher waits indefinitely while others keep eating.

Quick Revision Summary

8/9
Module3_Concurrency_and_Deadlock_Notes.md 2026-07-26

Concurrency = multiple processes progressing together; cooperating processes (unlike independent

ones) can create race conditions.
IPC = Shared Memory (fast, needs manual sync) vs Message Passing (slower, safer, kernel-managed).
Critical Section Problem needs: Mutual Exclusion + Progress + Bounded Waiting.
Mutual exclusion support: Software (Peterson's, Dekker's, Bakery) vs Hardware (Test-and-Set, Swap) vs
high-level tools (Semaphores, Mutex, Monitors).
Mutex = strict lock, only owner can unlock; Semaphore = signaling tool, counting or binary, can be
signaled by any thread.
Deadlock needs all 4 Coffman conditions together: Mutual Exclusion, Hold & Wait, No Preemption,
Circular Wait.
RAG: no cycle → no deadlock; cycle + single-instance resources → deadlock guaranteed; cycle + multi-
instance → deadlock only possible.
Prevention = break one Coffman condition permanently (restrictive but safe).
Avoidance (Banker's Algorithm) = dynamically check for a "safe state" before granting any request
(needs max-demand info in advance).
Detection & Recovery = let deadlock happen, detect via Wait-For Graph/RAG, then recover via
termination, preemption, or rollback.
Dining Philosophers = classic circular-wait deadlock example; solved via semaphores, asymmetric
ordering, or monitors.

Source basis: GeeksforGeeks Operating Systems articles, rewritten and simplified for study purposes.

9/9
Module4_Memory_Management_Notes.md 2026-07-26

Module 4: Memory Management

Notes prepared for DJS22EC6014 — Operating Systems, Sem VI (based on GeeksforGeeks explanations,
simplified for quick revision)

1. Memory Management Requirements

Memory management is how the OS controls and organizes the computer's main memory, allocating chunks
of it (called blocks) to different running programs so the whole system performs well.

Every good memory management scheme needs to satisfy a few key requirements:

Requirement What it means

Since memory is shared among many processes in a multiprogramming system, a

program can't always know in advance where it'll sit in memory. Also, if a process is
Relocation
swapped out to disk and later swapped back in, it may not return to its original
location — so addresses must be able to shift.

Processes must be prevented from interfering with each other's memory (accidentally
or maliciously). This check must actually be enforced by the processor hardware (not
Protection
just the OS), because the OS can't monitor every single memory access while a process
is running on the CPU.

Despite needing protection, the system must also allow controlled sharing — e.g.,
Sharing multiple processes using the same library or file can share a single copy in memory
instead of each having a separate copy, saving space.

Programs are typically organized into modules that are written and compiled
Logical
independently — memory management should support this structure (this is one of the
Organization
ideas behind segmentation).

Memory is organized into two levels in most systems — a smaller, faster main memory
Physical
(RAM) and a larger, slower secondary memory (disk). The OS must manage the flow
Organization
of information between the two.

Why relocation matters so much: most programming languages allow addresses to be calculated
dynamically at runtime, so the memory management system needs a flexible way to translate a program's
own internal addresses into wherever it actually ends up sitting in physical memory.

2. Memory Partitioning
Partitioning is about how the OS divides up main memory to give different processes their own space.

a) Fixed (Static) Partitioning

Memory is divided into a fixed number of partitions, decided in advance (at system configuration time) —
and this layout doesn't change afterward.
1/8
Module4_Memory_Management_Notes.md 2026-07-26

Each partition holds exactly one process at a time.

Since partitions don't change size, and a process is placed into a partition that's usually bigger than
what it actually needs, the unused space inside that partition is wasted — this is called Internal
Fragmentation.
Since partitions are fixed and contiguous (no "spanning" across gaps allowed), even if the total free
space across all partitions is enough for a new process, it may still be rejected if no single partition is
big enough — this leftover unusable space across partitions is called External Fragmentation.

Pros: Simple to implement, easy to debug, no complex allocation needed, predictable performance — good
for batch systems with a known, fixed set of processes. Cons: Wastes memory via internal fragmentation; the
number of processes that can run at once is limited by the number of partitions.

b) Dynamic (Variable) Partitioning

Instead of pre-deciding partition sizes, the OS creates a partition at runtime, sized to exactly match the
memory needs of the process requesting it.

Initially, all of memory is one large free block.

As processes arrive, the OS carves out exactly the amount of memory each one needs.
When a process finishes, its memory is released back as a "hole," and this hole can later be reused
(possibly merged with adjacent free holes).

Pros: No internal fragmentation (since each partition is sized exactly to the process); better memory
utilization; supports more processes running concurrently. Cons: Still suffers from External Fragmentation —
as processes come and go, memory gets broken into small scattered free "holes" that individually may be too
small for a new process, even though the total free space might be sufficient. Solved (partially) using
compaction — shifting all occupied memory together to consolidate the free space into one large contiguous
block. Managing dynamic partitions is also more complex than fixed ones.

Fixed vs Dynamic — Quick Comparison

Aspect Fixed Partitioning Dynamic Partitioning

Partition size Decided in advance, unchanging Created at runtime, matches process size

Internal Fragmentation Yes No

External Fragmentation Yes Yes

Complexity Simple More complex

Multiprogramming degree Limited (fixed # of partitions) Higher (flexible)

3. Memory Allocation Strategies (Placement Algorithms)

When a new process needs memory, and there are multiple free "holes" of different sizes available, the OS
needs a strategy to pick which hole to use. The four classic strategies:

2/8
Module4_Memory_Management_Notes.md 2026-07-26

Strategy How it Works Speed Fragmentation Behavior

Scans memory from the beginning Tends to fill up the start of memory
Fast (stops at
First Fit and allocates the first hole large quickly, causing fragmentation
first match)
enough for the process there over time

Same idea as First Fit, but resumes

Faster on Spreads allocations more evenly
scanning from where the last
Next Fit average than across memory instead of clustering
allocation left off instead of
First Fit near the start
restarting from the beginning

Minimizes wasted space per

Searches the entire list of holes and Slowest (must
allocation, but tends to leave many
Best Fit picks the smallest hole that's still scan
tiny, unusable leftover fragments
big enough everything)
over time

Slow (must Leaves a larger leftover fragment

Worst Searches the entire list and picks
scan after allocation, which is more likely
Fit the largest available hole
everything) to be useful for a future process

Is Best-Fit really "best"? Not always — even though it minimizes leftover wasted space per allocation, it takes
more time to search (since it must check every hole), and can actually perform worse than other strategies in
the long run because of the many small unusable fragments it leaves scattered around.

Quick memory trick:

First Fit = "grab the first one that works"

Next Fit = "keep going from where I left off"
Best Fit = "find the snuggest fit" (but slow, and creates tiny leftover crumbs)
Worst Fit = "grab the biggest one" (leaves a large, more usable leftover)

4. Relocation (Address Translation)

Since a process's final location in physical memory isn't always known in advance (and can even change if it's
swapped out and back in), the system distinguishes between two kinds of addresses:

Address Type Meaning

Logical (Virtual) The address generated by the CPU/program itself — it's from the process's own
Address perspective and doesn't physically exist as-is.

The actual, real location in main memory (RAM) where the data or instruction truly
Physical Address
resides.

The Memory Management Unit (MMU) — a piece of hardware — automatically translates every logical
address the CPU generates into the correct physical address, transparently, every time memory is accessed.
This translation is exactly what allows a process to be relocated in physical memory without the program itself
needing to know or care where it physically ends up.

3/8
Module4_Memory_Management_Notes.md 2026-07-26

5. Paging
Paging is a memory management technique that allows a process's memory to be non-contiguous —
instead of needing one unbroken chunk, the process is split into fixed-size pieces.

The process's logical memory is divided into fixed-size blocks called pages.
Physical memory (RAM) is divided into blocks of the same fixed size, called frames.
Pages of a process can be scattered across any available frames in physical memory — they don't need
to be next to each other.

How Address Translation Works in Paging

1. A logical address is split into two parts: a page number and a page offset.
2. The page number is used to look up the corresponding frame number in the process's page table.
3. The frame number combined with the offset gives the final physical address.

Why Paging is Useful

Solves the problem of needing one large contiguous block of memory for a process.
Since memory is managed in uniform fixed-size chunks, allocation/deallocation bookkeeping is
simplified.
Eliminates external fragmentation completely (any free frame can hold any page) — though a small
amount of internal fragmentation can still occur in the last page of a process if it doesn't perfectly fill
a frame.

Downsides

Extra memory access needed to consult the page table before reaching the actual data (partly solved
using a hardware cache called a Translation Lookaside Buffer, or TLB).
The page table itself can get quite large for processes with big address spaces.
Requires more complex hardware/software support (MMU, page tables, page replacement algorithms).

6. Segmentation
Segmentation divides a program into logical, variable-sized chunks called segments — e.g., one segment for
code, one for the stack, one for a data array — based on how the programmer naturally organizes the
program, rather than forcing everything into equal fixed-size pieces.

Segments can differ in size (unlike pages, which are always the same fixed size).
A Segment Table keeps track of each segment's base address (where it starts in physical memory) and
limit (its size).
The logical address in segmentation is two-dimensional: a segment number and an offset within that
segment.

Segmentation vs Paging (a favorite exam comparison!)

4/8
Module4_Memory_Management_Notes.md 2026-07-26

Aspect Paging Segmentation

Variable-size segments (based on logical

Division basis Fixed-size pages (hardware-defined)
program structure)

Visible to Yes — reflects how the programmer views

No — invisible to the user
programmer? the program

Internal fragmentation possible; no External fragmentation possible; little to

Fragmentation
external fragmentation no internal fragmentation

Address structure Page number + offset Segment number + offset

Table used Page Table Segment Table

(Some systems combine both approaches — called Paged Segmentation or Segmented Paging — to get the
logical clarity of segmentation with the fragmentation-avoidance of paging.)

7. Virtual Memory & Demand Paging

Virtual Memory is a technique that lets a process use more memory than what's physically available, by
combining RAM with secondary storage (disk) — creating the illusion of a much larger memory space than
what actually exists physically.

Demand Paging

Demand Paging is the practice of loading pages into physical memory only when they're actually needed,
instead of loading a process's entire address space upfront.

Sequence of events for Demand Paging:

1. A process starts execution with only some of its pages loaded into memory.
2. If the CPU tries to access a page that isn't currently in memory, it generates an interrupt called a Page
Fault.
3. The OS puts the interrupted process into a blocked/waiting state.
4. The OS locates the required page (on disk, in the logical address space).
5. If memory is full, a page replacement algorithm decides which existing page to evict to make room.
6. The required page is brought into physical memory, and the page table is updated to reflect its new
location.
7. The process is placed back in the ready state and resumes as if nothing happened — the whole process
is transparent to the running program.

Benefits: Since only actively-needed parts of a program are loaded, memory is used efficiently, more
processes can be run concurrently (better multiprogramming), and even programs larger than physical RAM
can execute successfully.

8. Structure of Page Tables

The page table is the data structure the OS (with hardware help from the MMU) uses to map each logical
page number to its corresponding physical frame number.
5/8
Module4_Memory_Management_Notes.md 2026-07-26

What a Page Table Entry (PTE) typically contains

Frame number – where this page currently sits in physical memory

Valid/Invalid bit – whether this page is currently loaded in memory at all
Dirty/Modified bit – set to 1 if the page has been changed since it was loaded, so the OS knows
whether it needs to be written back to disk before being replaced
Reference bit – set whenever the page is read or written; helps page replacement algorithms like LRU
figure out which pages have been actively used
Protection bits – control read/write/execute permissions to keep memory access safe

Common Page Table Structures

Single-Level (Hierarchical/Simple) Paging: One large table directly maps every page number to a
frame number. Simple, but the table itself can become huge for large address spaces (e.g., a 32-bit
address space with 4KB pages needs roughly a million entries per process).
Multilevel Paging: Breaks a large page table down into smaller pieces organized across multiple levels
(like a tree), so the whole table doesn't need to be fully resident in memory at once — this saves space
for sparsely-used address spaces.
Hashed Page Tables: Uses a hash function on the page number to quickly locate the matching entry —
useful for very large (e.g., 64-bit) address spaces.
Inverted Page Tables: Instead of one entry per logical page (which could be huge), keeps just one
entry per physical frame — much smaller overall, but requires an extra search step to find the right
entry.

9. Page Replacement Algorithms

When physical memory is full and a new page needs to be brought in, the OS must decide which existing
page to evict. Different algorithms use different strategies for this choice — all aiming to minimize the
number of page faults.

a) FIFO (First-In-First-Out)

Replaces the page that has been in memory the longest, regardless of how often or recently it was actually
used.

Simple to implement (just a queue).

Downside: Doesn't consider whether a page is still actively needed — can evict a frequently-used page
just because it arrived early. Also suffers from Belady's Anomaly (see below).

b) Optimal Page Replacement

Replaces the page that won't be used for the longest time in the future.

Gives the theoretically lowest possible page fault rate — used purely as a benchmark to measure
how other algorithms perform.
Downside: Impossible to implement in a real system, since it requires knowing the future sequence of
page references in advance.

c) LRU (Least Recently Used)

6/8
Module4_Memory_Management_Notes.md 2026-07-26

Replaces the page that hasn't been used for the longest time in the past — based on the idea that a page
unused for a while is unlikely to be needed again soon (the "locality of reference" principle).

Considered a good practical approximation of the Optimal algorithm.

Downside: Needs extra bookkeeping (tracking usage order/timestamps), which adds some overhead,
but is generally worth it for the improved hit rate.

d) LFU (Least Frequently Used)

Replaces the page that has been accessed the fewest number of times overall — instead of looking at
recency, it looks at raw frequency of use.

Works well for programs with consistent, predictable access patterns, where genuinely rarely-used
pages are correctly identified.
Downside: A page that was very popular early on but hasn't been used in a while can still "look"
important based on its old high count, even though it's no longer needed — this is called the problem
of not adapting to changing access patterns. (Ties are often broken using FIFO — whichever tied page
arrived first gets replaced.)

(There's also a related "opposite" idea — Most Frequently Used, MFU — which replaces the page with the
highest access count, based on the reasoning that a heavily-used page has probably already served its purpose
and is less likely to be needed further; it's far less common in practice than LFU.)

Belady's Anomaly

Normally, giving a process more page frames should reduce the number of page faults. Belady's Anomaly is
the surprising exception where, for certain reference patterns, increasing the number of frames actually
increases the number of page faults.

Occurs in: FIFO (and a few similar algorithms like Second-Chance and Random).
Never occurs in: Optimal, LRU, and LFU — because these are all "stack-based" algorithms, meaning
the set of pages kept in memory with n frames is always a subset of what would be kept with n+1
frames, so adding more frames can never make things worse.

Quick Comparison Table

Belady's
Algorithm Basis for Replacement Practical?
Anomaly?

FIFO Oldest page in memory Yes, simple Yes

Page not needed for longest No (needs future knowledge) — used

Optimal No
time in future as benchmark only

Page not used for longest time

LRU Yes, common in practice No
in the past

Page used the fewest number

LFU Yes, for predictable workloads No
of times

Quick Revision Summary

7/8
Module4_Memory_Management_Notes.md 2026-07-26

y
Memory management requirements: Relocation, Protection, Sharing, Logical & Physical organization.
Fixed Partitioning: predefined partitions → internal + external fragmentation, simple but rigid.
Dynamic Partitioning: runtime-sized partitions → no internal fragmentation, but external
fragmentation remains (needs compaction).
Allocation strategies: First Fit (fast), Next Fit (spreads allocations), Best Fit (minimizes waste but slow,
leaves tiny holes), Worst Fit (leaves large usable leftover).
Relocation works via Logical (virtual) → Physical address translation, done by the MMU.
Paging: fixed-size pages/frames, non-contiguous allocation, eliminates external fragmentation, uses a
page table.
Segmentation: variable-size, logical/programmer view, uses a segment table, can suffer external
fragmentation.
Virtual Memory & Demand Paging: load pages only when needed; a page fault triggers loading the
missing page from disk.
Page Table structure: frame number, valid bit, dirty bit, reference bit, protection bits; can be single-
level, multilevel, hashed, or inverted.
Page Replacement: FIFO (simple, can suffer Belady's Anomaly), Optimal (best possible, impractical),
LRU (great practical approximation), LFU (frequency-based, struggles with changing patterns).

Source basis: GeeksforGeeks Operating Systems articles, rewritten and simplified for study purposes.

8/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

Module 5: File Management and Input Output

Management
Notes prepared for DJS22EC6014 — Operating Systems, Sem VI (based on GeeksforGeeks explanations,
simplified for quick revision)

1. File System — Overview

A file system gives a structured way to store, organize, and manage data on storage devices like hard drives,
SSDs, and USB drives. Without it, the OS would have no consistent way to know where one file ends, another
begins, or how to find anything again later.

Typical Layered Structure

User Application – programs that request file operations (create, read, write, delete)
Logical File System – manages metadata: file names, directories, and access permissions
Virtual File System (VFS) – acts as a bridge, letting many different underlying file systems work
through one common interface
Physical file system layer – actually reads/writes the raw blocks on the storage device

File System Implementation — Key Steps

1. Partitioning the storage device into one or more logical sections.

2. Formatting each partition with a specific file system (e.g., NTFS, FAT, ext4, XFS).
3. Maintaining file system structures (directories, allocation tables, etc.) to track files.
4. Supporting standard file operations: create, delete, read, write, open, close, seek.
5. Performance optimization — caching, buffering, and prefetching to reduce access time and system
overhead.

2. File Organization and Access Methods

File Access Methods define how information stored in a file is read back — some systems only support one
method; others (like older IBM systems) support several, and picking the right one for an application is an
important design decision.

Method How it Works Best For

Editors, compilers —
Sequential The simplest method — records/information are read in anything that naturally
Access order, one after another, from the start of the file. processes data top-to-
bottom

Direct Allows jumping straight to any record by moving the file Databases, situations
(Random) pointer to a specific position/offset, without reading needing quick lookup of a
Access everything before it. specific record

1/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

Method How it Works Best For

Records are accessed relative to the current position Processing records in a

Relative Record
of the file pointer, rather than an absolute address. specific order without
Access
Requires fixed-length records. needing arbitrary jumps

Combines sequential storage with an index that allows

Index Large files needing both
quicker lookup — the index points to the approximate
Sequential ordered scans and fast
location, then a short sequential scan finds the exact
Access lookups
record.

Content- Records/blocks are accessed based on their content Systems needing to fetch
Addressable rather than their address — a hash function generates a data by "what it is" rather
Access unique key for lookup. than "where it is"

3. Memory Mapped Files

Memory Mapping is a technique where a file's contents are directly mapped into a process's own virtual
address space — so instead of using read()/write() system calls every time, the program can access the
file's data just like it would access a normal in-memory array or variable.

How it Works

The OS maps a disk block to a page in physical memory.

The very first access to any part of the file triggers a normal page fault, which loads that portion of the
file from disk into a physical page.
After that, further reads/writes to that part of the file are handled as regular memory accesses — no
repeated system calls needed.
When the file is eventually closed, any modified ("dirty") memory-mapped data gets written back to
disk.

Why It's Useful

Faster than repeated read()/write() system calls, since it avoids the overhead of copying data
between kernel buffers and user buffers.
Lazy loading — only the parts of a (possibly huge) file that are actually accessed get loaded into RAM,
saving memory.
Supports sharing — multiple processes can map the same file, and if one process writes to it, the
changes become visible to all the other processes sharing that mapping (this is actually a common way
to implement shared memory).
Some systems support copy-on-write — processes can share a file in read-only mode, but if one
process writes, it gets its own private copy instead of affecting the others.

Limitations

Only works on hardware that has a Memory Management Unit (MMU).

Growing the size of a memory-mapped file isn't straightforward.
Can occasionally be slower than standard file I/O in some access patterns, and increases the risk of page
faults as more of the file gets touched.
2/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

4. Implementing Files — File Allocation Methods

Once the OS has decided where free space exists on disk, it needs a strategy to actually lay out a file's data
blocks. There are three classic methods:

a) Contiguous Allocation

Each file occupies a single, unbroken run of disk blocks — the directory entry just needs the starting block
address and the length of the file.

Advantages: Supports both sequential and direct access easily (the k-th block of a file starting at block
b is simply at b+k); extremely fast since very few disk-arm seeks are needed.
Disadvantages: Suffers from both internal and external fragmentation, making memory utilization
inefficient; growing a file's size is difficult since it depends on whether contiguous free space happens
to be available right next to it.

b) Linked Allocation

Each file is stored as a linked list of disk blocks, which don't need to be next to each other at all.

The directory entry holds a pointer to the file's starting block (and often the ending block too).
Every block contains a pointer to the next block in the file; the very last block's pointer is a null/−1,
marking the end.
Advantages: Very flexible — a file can grow easily since blocks can be scattered anywhere; no external
fragmentation.
Disadvantages: Doesn't support efficient direct/random access (you must follow the chain from the
start); each block "loses" a small amount of space to store the pointer; if a pointer gets corrupted, the
rest of the file chain can be lost.

c) Indexed Allocation

Brings all of a file's block pointers together into one dedicated index block, instead of scattering pointers
across the data blocks themselves.

Each file has its own index block, which simply lists all the disk block addresses that belong to that file.
Advantages: Supports direct access efficiently (just look up the index — no need to traverse a chain);
avoids the pointer-scattering problem of linked allocation.
Disadvantages: For very small files (2–3 blocks), reserving a whole separate index block is wasteful —
the pointer overhead is worse than linked allocation for tiny files; for very large files, a single index
block might not be big enough to hold every pointer (solved using multilevel index — an index block
pointing to other index blocks — or a combined scheme, where a few direct pointers are kept in the
file's own metadata, and only larger files use extra levels of indexing, as UNIX-style file systems do).

Quick Comparison

Aspect Contiguous Linked Indexed

Direct access? Yes (fast) No (must traverse) Yes

3/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

Aspect Contiguous Linked Indexed

Fragmentation Internal + External None None

Overhead None extra 1 pointer per block 1 index block per file

Growing a file Hard Easy Easy

Fast, mostly-static Files needing flexible Large files needing quick

Best for
files growth lookup

5. Directory Structures
A directory is a container the file system uses to organize files (and other directories) — think of it as a way to
store the "table of contents" for what's on the disk.

a) Single-Level Directory Structure

The simplest possible structure — there is only one directory (often called the root), and all files from
all users sit inside it, with no subdirectories at all.
Advantages: Very easy to implement; simple file operations (create, search, delete, update); fast
searching when the number of files is small.
Disadvantages: Every file must have a unique name system-wide — if two users both want to name a
file "test," there's a naming conflict; becomes cluttered and slow to search as the number of files grows;
no way to group related files together.

b) Two-Level Directory Structure

Introduces one User File Directory (UFD) per user — each user gets their own private directory space
(usually named after that user) to create files and subdirectories.
A system-wide Master File Directory (MFD) sits above all the UFDs, and is searched whenever a new
user's directory needs to be located.
Advantages: Solves the naming-conflict problem of single-level directories, since two different users
can now have files with the same name (they just live in different UFDs).
Disadvantages: Still limited — a single user can't create further subdirectories to organize their own
files into logical groups.

c) Hierarchical (Tree) Directory Structure

Goes a step further — users are now allowed to create subdirectories within their own directory,
nested as deep as needed, forming a full tree structure starting from a single root.
This is the structure most modern operating systems (Windows, Linux, macOS) actually use.
Advantages: Much better organization — users can group related files into folders/subfolders exactly
as they like; searching can be faster since it's scoped to relevant subdirectories; supports better access
control at each directory level.
Disadvantages: More complex to implement and manage than single or two-level structures; deleting
a non-empty directory needs careful handling (e.g., deleting everything inside it too).

(Some systems extend this further into a graph structure, allowing a file/directory to have more than one parent
via shared links — but the tree/hierarchical model is the one most commonly taught and used.)
4/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

6. Disks — RAID Levels

RAID (Redundant Array of Independent Disks) combines multiple physical disks into what looks like a
single logical unit to the OS, aiming to improve performance, reliability, or both. RAID levels don't represent
a hierarchy of "better" numbers — each level is simply a different configuration with its own trade-offs.

RAID
Technique Redundancy? Key Trade-off
Level

No — can't recover
Data striping — splits data into Maximizes speed and space, but
RAID 0 from a disk failure at
blocks spread across all disks zero fault tolerance
all

Mirroring — every bit of data is Great reliability and read speed, but
RAID 1 Yes (full duplication)
duplicated on a second disk uses double the disk space

The single parity disk becomes a

Block-level striping with one
RAID 4 Yes bottleneck, since every write must
dedicated parity disk
update it

Block-level striping with parity Avoids RAID 4's bottleneck, but data
Yes (survives 1 disk
RAID 5 distributed across all disks regeneration after a failure is more
failure)
(instead of one dedicated disk) complex

Like RAID 5, but with two Extra fault tolerance, but slower
independent parity Yes (survives 2 disk writes due to double parity
RAID 6
calculations distributed across failures) computation, and needs more disk
disks space for parity

RAID Excellent performance and

Combines mirroring (RAID 1) +
10 Yes redundancy, but expensive (needs
striping (RAID 0)
(1+0) at least 4 disks)

Quick way to remember: RAID 0 = speed, no safety net. RAID 1 = full duplicate copies. RAID 5/6 = parity-
based protection (spread the "backup math" across disks). RAID 10 = best of both worlds, at a higher disk cost.

7. Disk Arm Scheduling Algorithms

Since a disk's read/write head (arm) has to physically move across tracks to service different requests, and this
movement (seek time) is relatively slow, disk scheduling algorithms decide the order in which pending I/O
requests are serviced — aiming to minimize total head movement.

Algorithm How it Works Pros Cons

Can cause a lot of unnecessary

Services requests strictly in the Simple, fair, easy to back-and-forth arm
FCFS
order they arrived implement movement if requests are
scattered

5/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

Algorithm How it Works Pros Cons

SSTF Requests far from the head's

Always services whichever
(Shortest Less total seek time current position may starve
pending request is closest to
Seek Time than FCFS (never get serviced) if closer
the current head position
First) requests keep arriving

The head moves in one Requests in the middle get

direction, servicing every serviced more often than
SCAN
request along the way, until it More uniform those near the edges; still
("Elevator"
reaches the end — then servicing than SSTF involves going all the way to
Algorithm)
reverses direction and does the the very end even if there's
same going back nothing there

Like SCAN, but services

requests in only one Much more
C-SCAN direction; once it reaches the uniform wait times The "jump back" itself doesn't
(Circular end, it jumps straight back to across all requests service anything, so it's a bit of
SCAN) the beginning (without (avoids favoring the wasted movement
servicing on the way back) and middle)
starts again

Like SCAN, but instead of

going all the way to the
physical end of the disk, it Reduces wasted
Slightly more complex to
LOOK reverses direction as soon as movement
implement than SCAN
there are no more pending compared to SCAN
requests further in the current
direction

Like C-SCAN, but also stops as

Fastest and most
soon as there are no more
efficient among this
requests ahead, then jumps Slightly more bookkeeping
C-LOOK family — avoids
back to the closest pending needed
both types of
request instead of the extreme
wasted movement
end

Overall efficiency ranking (roughly): FCFS → SSTF → SCAN → C-SCAN → LOOK → C-LOOK (each an
improvement on wasted movement over the last, though SSTF trades efficiency for fairness issues).

Real-world note: These algorithms matter mainly for traditional spinning hard disks (HDDs), which have real
mechanical seek time. Modern SSDs have effectively zero seek time, so they typically just use simple
FCFS/FIFO ordering instead.

8. Management of Free Blocks (Free Space Management)

The OS needs to track which disk blocks are currently free so it knows where to allocate new files. Several
techniques exist:

6/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

a) Bitmap (Bit Vector)

A long string of bits, one per disk block — 1 typically means the block is free, 0 means it's allocated (or
vice versa, depending on convention).
Advantages: Simple to understand; finding the first free block is efficient — the OS scans in groups of
bits ("words") for a non-zero group, then pinpoints the exact free bit within it.
Disadvantages: For very large disks, the bitmap itself can become too large to comfortably keep
resident in memory.

b) Linked List

All free blocks are linked together, forming a chain — each free block simply stores a pointer to the
next free block, with the head pointer kept in a known/cached location.
Advantages: No wasted space computing/storing a full bitmap; efficient use of total available space.
Disadvantages: To find a free block somewhere in the middle of the list, the OS must traverse the chain
one block at a time — slow, and requires actual disk I/O for each step of the traversal, unlike the bitmap
which can often be scanned quickly in memory.

c) Grouping

A modification of the linked list idea — the first free block stores the addresses of the next n free
blocks (instead of just one). The last of those n addresses then points to another block that itself stores
the next batch of n free block addresses, and so on.
Advantages: Much faster to retrieve a whole batch of free blocks at once (fewer disk accesses overall)
compared to a plain linked list.
Disadvantages: Slightly more complex to manage than a simple linked list; not as beneficial if only one
or two free blocks are actually needed at a time.

d) Counting

Takes advantage of the fact that, in practice, several contiguous blocks are often freed (or allocated)
together. Instead of storing every free block's address individually, the system stores just the starting
address plus a count of how many contiguous free blocks follow it.
Example: an entry like (10, 3) represents blocks 10, 11, and 12 all being free.
Advantages: Greatly reduces the size of the free-space list when free blocks tend to occur in
contiguous runs.
Disadvantages: Less effective if free blocks are scattered randomly rather than in contiguous chunks;
adds a small amount of overhead per entry (needs to store both a starting address and a count).

Quick Comparison

Method Space Efficient? Fast Lookup? Best When

Can be large for big Good (scan for non-zero Disk size is moderate; simplicity
Bitmap
disks word) valued

Linked Efficient (no separate Slow (must traverse, needs Simpler systems, less concern for
List table) disk I/O) lookup speed

7/8
Module5_File_and_IO_Management_Notes.md 2026-07-26

Method Space Efficient? Fast Lookup? Best When

Faster batch retrieval than Systems that often need several

Grouping Efficient
plain linked list free blocks at once

Very efficient for Efficient when runs are Disks with large contiguous free
Counting
contiguous runs common areas

Quick Revision Summary

File system layers: User Application → Logical File System → Virtual File System (VFS) → physical
storage.
Access methods: Sequential (in-order), Direct (jump anywhere), Relative Record (relative position),
Index Sequential (index + scan), Content-Addressable (hash-based).
Memory Mapped Files: map a file directly into a process's virtual memory — faster than read()/write(),
supports sharing and lazy loading, needs an MMU.
File Allocation: Contiguous (fast, but fragmentation), Linked (flexible growth, no direct access), Indexed
(direct access via a dedicated index block).
Directory structures: Single-level (simple, name conflicts) → Two-level (per-user UFDs, solves naming)
→ Hierarchical (full nested subdirectories, used by modern OSes).
RAID levels: 0 = striping/speed only; 1 = mirroring; 4/5 = parity (dedicated vs distributed); 6 = double
parity; 10 = mirror + stripe combo.
Disk scheduling: FCFS (simple) → SSTF (fast but can starve) → SCAN/C-SCAN (elevator-style, uniform)
→ LOOK/C-LOOK (avoids wasted end-to-end movement, most efficient).
Free space management: Bitmap (simple, scan-based), Linked List (space-efficient, slow traversal),
Grouping (batch retrieval), Counting (great for contiguous free runs).

Source basis: GeeksforGeeks Operating Systems articles, rewritten and simplified for study purposes.

8/8
Module6_RTOS_Notes.md 2026-07-26

Module 6: Real Time Operating System (RTOS)

Notes prepared for DJS22EC6014 — Operating Systems, Sem VI (based on the uploaded [Link], simplified for
quick revision)

1. Introduction to RTOS
A Real-Time Operating System (RTOS) is an OS designed to process data and respond to inputs within a
strict, predictable time limit — it's not just about being fast, it's about being on time, every time.

2. Types of Real-Time Operating Systems

Type Meaning Consequence of Missing a Deadline

Every critical task must finish Missing a deadline causes a critical failure — equipment
Hard
within its deadline, no damage or even loss of human life (e.g., airbag systems,
RTOS
exceptions. pacemakers).

Deadlines are important, but

Soft A late response degrades quality but doesn't cause disaster
the system tolerates small
RTOS (e.g., video streaming, online booking systems).
delays now and then.

Deadlines still matter, and the Missing a deadline doesn't cause a catastrophe, but it does
Firm
system tries hard to meet make the output useless or undesirable — e.g., a big drop in
RTOS
them. product quality (a "late" result is basically as bad as no result).

Simple way to remember: Hard = disaster if late. Firm = the late result is worthless. Soft = late is okay, just less
ideal.

3. Characteristics of Real-Time Operating Systems

Characteristic What it Means

Every task has a defined time interval within which it must respond — this is the
Time Constraints
whole foundation of "real-time."

It's not enough to be fast — the result must also be correct, and correct within
Correctness
the time window.

Most RTOS today run as part of an embedded system — a purpose-built

Embedded
combination of hardware and software designed for one specific job.

RTOS provide critical safety guarantees and are built to run reliably for long
Safety
stretches without failure.

Stability Even under heavy load (many tasks running at once), the system still meets its
time constraints — it doesn't let the response get delayed just because things are

1/7
Module6_RTOS_Notes.md 2026-07-26

Characteristic What it Means

busy.

Real-Time Components/devices in the system often need to communicate with each other in
Communication real time too, not just process tasks independently.

Priority-Based
High-priority tasks are always executed before lower-priority ones.
Scheduling

4. Benefits of RTOS
Easy to design, develop, and run real-time applications on.
More compact than general-purpose OSes, so they need less memory.
Achieves maximum utilization of devices and system resources.
Focuses effort on the application actually running, rather than wasting attention on queued/waiting
applications.
Small program size means RTOS can be embedded into devices like transport systems and other
compact hardware.
Designed to be largely error-free.
Very efficient, well-managed memory allocation.

5. Real-Time Task Scheduling

Real-time task scheduling is about deciding the order in which tasks should be executed by the OS — and
in real-time systems, this decision carries genuine urgency, since these tasks are usually tied to reacting to or
controlling real-world events.

Real-time tasks are broadly split into hard real-time tasks and soft real-time tasks (matching the
RTOS types above).
The scheduler is the single most important component of a real-time system — typically a short-term
scheduler.
Its main focus is minimizing the response time of each process — rather than just trying to satisfy the
deadline directly, it's built around responding quickly.

Classification of Real-Time Scheduling Algorithms

Based on how schedulability is decided, whether the analysis is static or dynamic, and how the result is
produced, scheduling algorithms fall into four categories:

Category How it Works

Static Table- Performs the scheduling analysis offline/in advance, and produces a schedule that
Driven tells the system exactly which task to start at which point in time.

Static Priority- Also uses static (advance) analysis, but instead of producing one fixed schedule, it
Driven assigns priorities to tasks — and the scheduler uses those priorities with
Preemptive preemption at runtime.

2/7
Module6_RTOS_Notes.md 2026-07-26

Category How it Works

Dynamic Feasible schedules are worked out dynamically, at runtime — a process is

Planning-Based executed only if it satisfies its required time constraint within a fixed interval.

Instead of guaranteeing a feasible schedule in advance, this approach just tracks

Dynamic Best-
deadlines — if a task's deadline arrives and it isn't done, the task is simply aborted.
Effort
This is the approach used most widely in real-world real-time systems.

6. Table-Driven (Static) Scheduling

Table-Driven Scheduling builds a predefined table, worked out entirely offline, that specifies the execution
order and timing requirements for every task across the system's entire operation.

Property Description

Generated offline based on historical data or fixed priorities; it's static and never
Predefined Schedule
changes during runtime.

Deterministic Every task gets a fixed time slot or priority — execution always follows the
Execution specified order, with no runtime adjustments.

Can't respond to changing workloads or system conditions — the table stays the
Limited Adaptability
same even if new tasks appear or load shifts.

Simple Easy to implement since the schedule is already decided — no complex runtime
Implementation decision-making needed.

Since there's no dynamic recalculating at runtime, the scheduling overhead is low

Reduced Overhead
— the system just follows the table.

7. Cyclic Scheduling
Cyclic Scheduling (also called round-robin scheduling) is a dynamic approach that gives each task a fixed
time slot ("quantum") in a repeating, cyclic order — once a task's time is up (or it finishes early), the scheduler
moves on to the next task in the cycle, and the whole process repeats.

Property Description

Time slices are assigned based on a predetermined quantum; each task runs for
Dynamic Schedule that fixed amount of time before being preempted and sent to the back of the
queue.

Fairness and Every task gets an equal opportunity to run, preventing any single task from
Sharing monopolizing the CPU.

Runtime The scheduler can react to the current system state — task priorities, resource
Adjustments availability, waiting times.

Because every task gets guaranteed CPU time within a fixed slice, the system stays
Responsiveness
reasonably responsive to time-sensitive tasks.

3/7
Module6_RTOS_Notes.md 2026-07-26

Property Description

Overhead and Frequent context switches between tasks add overhead, and managing the task
Complexity queues/preemption needs more complex bookkeeping.

8. Earliest Deadline First (EDF) Scheduling

EDF is an optimal, dynamic priority scheduling algorithm widely used in real-time systems — it can be
applied to both static and dynamic real-time scheduling.

Priorities are assigned based on each task's absolute deadline — the task whose deadline is closest
gets the highest priority.
Priorities are not fixed — they're reassigned dynamically as time passes and deadlines shift.
EDF is highly efficient compared to other scheduling algorithms, and can push CPU utilization to close
to 100% while still guaranteeing every task's deadline is met.

Worked Example

Consider two periodic processes:

Process Period Processing Time

P1 50 25

P2 75 30

Walkthrough of how EDF schedules them:

1. P1's deadline is earlier, so initially P1 has higher priority and runs first, completing its 25 units of
execution.
2. After time 25, P2 starts executing, continuing until time 50 (when P1 becomes ready again).
3. At time 50, comparing deadlines — P1's deadline is 100, P2's is 75 — P2's deadline is closer, so P2
continues executing.
4. P2 finishes its processing at time 55.
5. P1 then executes from 55 until time 75 (when P2 becomes ready again).
6. At time 75, comparing deadlines again — P1's deadline is now 100, P2's is 150 — P1's deadline is
closer, so P1 continues.
7. This pattern repeats. Eventually, at time 150, both P1 and P2 have the same deadline — in that case,
P2 finishes its current processing first, and then P1 executes.

(This example shows EDF's core behavior: at every decision point, the scheduler simply re-checks which ready
task has the nearest deadline and runs that one — the priority ordering can flip dynamically as time progresses.)

Advantages of EDF

Meeting Deadlines: Prioritizing the earliest deadline minimizes the chance of any task missing its
deadline.
Optimal Utilization: Maximizes CPU utilization by keeping the processor busy as long as there's a task
with an active deadline, minimizing idle time.

4/7
Module6_RTOS_Notes.md 2026-07-26

Responsiveness: Provides fast scheduling/execution for time-critical tasks, improving overall system
performance.
Predictability: Scheduling decisions are deterministic and can be analyzed/predicted in advance —
important for real-time guarantees.
Flexibility: Handles both periodic and aperiodic tasks, and supports dynamic task creation without
disrupting tasks already running.

Disadvantages of EDF

Transient Overload Problem – if the system briefly gets overloaded with more work than it can handle,
EDF's guarantees can break down unpredictably.
Resource Sharing Problem – coordinating shared resources between tasks under EDF adds complexity.
Efficient Implementation Problem – achieving an efficient real-world implementation of EDF is non-
trivial.

9. Rate Monotonic (RM) Scheduling

Rate Monotonic (RM) Scheduling is a well-known, priority-based, static scheduling algorithm for tasks with
fixed, periodic deadlines.

Each task's priority is based on its period: shorter period → higher priority, longer period → lower
priority.
A task's period (and therefore its priority) does not change over time — this is what makes RM a static
priority scheme, unlike EDF's dynamic priorities.
RM is a preemptive algorithm: if a task with a shorter period becomes ready during execution, it gains
higher priority and can preempt (block) whatever lower-priority task is currently running.
In short: priority is inversely proportional to the time period — smallest period = highest priority.

Worked Example

Consider three tasks:

Task Release Time (rᵢ) Execution Time (Cᵢ) Deadline (Dᵢ) Period (Tᵢ)

T1 0 0.5 3 3

T2 0 1 4 4

T3 0 2 6 6

Checking schedulability (CPU Utilization):

U = 0.5/3 + 1/4 + 2/6 = 0.167 + 0.25 + 0.333 = 0.75

Since utilization (0.75) is less than 1 (100%), the task set is schedulable under Rate Monotonic scheduling.

Priority order (shorter period = higher priority): T1 (highest) → T2 → T3 (lowest)

Execution Walkthrough:

At t = 0, all three tasks are released. T1 has the highest priority, so it runs first, until t = 0.5.

5/7
Module6_RTOS_Notes.md 2026-07-26

At t = 0.5, T2 has higher priority than T3, so T2 runs next, until t = 1.5. After that, only T3 remains, so it
starts running, continuing to t = 3.
At t = 3, T1 is released again; since it has higher priority than T3, it preempts T3 and runs until t = 3.5
— then T3 resumes its remaining work.
At t = 4, T2 is released again and completes its execution immediately since nothing else is running at
that moment.
At t = 6, both T1 and T3 are released simultaneously; T1 (shorter period) preempts T3 and runs until t =
6.5, after which T3 resumes and runs until t = 8.
At t = 8, T2 (higher priority than T3) is released, preempting T3 and starting its execution.
At t = 9, T1 is released again, preempts T3, executes first, and then at t = 9.5, T3 executes its remaining
part.
This cyclic preemption pattern continues indefinitely, following the same priority rules.

Advantages of RM

Easy to implement.
Optimal among static priority algorithms — if any static-priority assignment can meet all deadlines
for a task set, RM can meet them too.
Uses a properly calculated allocation of time periods, unlike simpler time-sharing algorithms (like
Round Robin) which ignore each process's actual scheduling needs.

Disadvantages of RM

Very difficult to support aperiodic and sporadic tasks (tasks that don't arrive on a strict, predictable
schedule).
Not optimal when a task's period and deadline differ — RM's guarantees assume deadline = period,
and performance suffers when that assumption breaks.

10. Advantages of Scheduling in Real-Time Systems (General)

Meeting Timing Constraints: Ensures real-time tasks finish within their required windows, preventing
failures or losses.
Resource Optimization: Efficiently allocates processor time, memory, and other resources, maximizing
throughput and performance.
Priority-Based Execution: High-priority, time-critical tasks are always given precedence, improving
responsiveness and reliability.
Predictability and Determinism: Lets developers analyze and guarantee worst-case execution and
response times in advance.
Control Over Task Execution: Developers get fine-grained control — setting priorities, deadlines, and
inter-task dependencies — which helps in designing complex real-time systems.

11. Disadvantages of Scheduling in Real-Time Systems (General)

Increased Complexity: Careful analysis of task requirements, priorities, and algorithm choice adds
development time and effort.
Overhead: Context switching, task prioritization, and scheduling decisions all introduce some runtime
overhead.

6/7
Module6_RTOS_Notes.md 2026-07-26

Limited Resources: Real-time systems often run in resource-constrained environments, making it

harder to satisfy every timing constraint simultaneously.
Verification and Validation: Proving that a schedule always meets its deadlines requires rigorous,
time-consuming testing.
Scalability: An algorithm that works fine for a small system may not scale well as the number of tasks
and overall system complexity grows.

Quick Revision Summary

RTOS types: Hard (deadline miss = disaster), Firm (deadline miss = useless output, no disaster), Soft
(deadline miss = tolerable delay).
Characteristics: Time constraints, correctness, embedded nature, safety, stability under load, real-time
communication, priority-based scheduling.
Scheduling algorithm classes: Static table-driven, static priority-driven preemptive, dynamic planning-
based, dynamic best-effort (most common in practice).
Table-Driven Scheduling: Fixed, offline-computed schedule — simple, low overhead, but not
adaptable.
Cyclic Scheduling: Round-robin style, dynamic time-slice allocation — fair and responsive, but adds
context-switch overhead.
EDF: Dynamic priority = closest deadline runs first; near-100% CPU utilization possible; great at meeting
deadlines, but struggles under transient overload.
RM: Static priority = shortest period runs highest; simple and provably optimal among static schemes,
but weak for aperiodic tasks or when deadline ≠ period.
General trade-off: Real-time scheduling buys predictability, safety, and responsiveness — at the cost
of design complexity, runtime overhead, and harder verification.

Note: Your syllabus for this module also lists Linux OS and Mobile OS as topics, but the uploaded slide deck
doesn't cover them — happy to put together notes on those (e.g., via GeeksforGeeks, like the earlier modules)
if you'd like them added.

Source basis: content extracted from the uploaded [Link], reorganized and simplified for study purposes.

7/7