COM 211

Operating Systems
Comprehensive Study Notes

Kathmandu University
Bachelor of Business Information Systems (BBIS)
Year II | Semester I | 3 Credit Hours

📋 Exam Pattern
Section A: 10 MCQs × 1 mark = 10 marks (10 min)
Section B: 6 Questions × 4 marks = 24 marks (attempt any 6)
Section C: 2 Questions × 8 marks = 16 marks (attempt any 2)
Total: 50 marks end-semester
Full exam: 40 marks (some papers)
UNIT 1: Introduction to Computer Systems and
Operating Systems

1.1 Structure of Computer Systems

A computer system consists of four main components that work
together:
•​ Hardware: Physical components — CPU, memory, I/O
devices, storage
•​ Operating System: Controls and coordinates hardware use
among applications and users
•​ Application Programs: Define how system resources solve
users' computing problems (compilers, browsers, games)
•​ Users: People, machines, or other computers

Hardware, Firmware, and Software

Component Description Examples
Hardware Physical, tangible CPU, RAM,
components of a HDD, keyboard
computer
Firmware Embedded software BIOS, UEFI,
stored in ROM/Flash; device drivers in
bridges hardware and ROM
software
Component Description Examples
Software Programs and OS, applications,
instructions that run on utilities
hardware

1.2 Concept of an Operating System

An Operating System (OS) is system software that manages
computer hardware and software resources and provides common
services for computer programs.

Two views of an OS:

•​ Resource Allocator: Manages and allocates resources (CPU
time, memory space, I/O devices) fairly and efficiently among
competing processes
•​ Control Program: Controls execution of programs to prevent
errors and improper use

Key Definition
The kernel is the one program running at all times on the
computer. Everything else is either a system program or an
application program. The OS is the interface between the
hardware and the user.
1.3 Multiprogramming and Multitasking
Multiprogramming
Multiprogramming increases CPU utilization by organizing jobs so
that the CPU always has one to execute. The OS keeps several jobs
in memory simultaneously. When one job waits (e.g., for I/O), the
CPU switches to another job.
•​ Goal: Keep CPU busy at all times
•​ A subset of jobs is kept in memory; the rest stay on disk (job
pool)
•​ If a running job must wait, OS switches to another job

Multitasking (Time-Sharing)
Multitasking is a logical extension of multiprogramming where the
CPU switches among multiple jobs so frequently that users can
interact with each program while it is running. Also called
time-sharing.
•​ CPU switches rapidly between multiple jobs (response time
typically < 1 second)
•​ Multiple users can share the computer simultaneously
•​ Each user has at least one program executing — called a
process
•​ Virtual memory allows execution of processes not entirely in
memory
Feature Multiprogramming Multitasking
(Time-Sharing)
Primary Goal Maximize CPU Minimize response
utilization time / interactive use
User Batch processing, Interactive, real-time
Interaction minimal interaction feedback
CPU Switching Only when process Rapid switching (time
waits for I/O slices)
Memory Multiple jobs in Multiple jobs +
memory virtual memory

1.4 History and Evolution of Operating Systems

1.​Serial Processing (1940s–early 1950s): No OS; programmers
directly interacted with hardware via console switches and
lights
2.​Simple Batch Systems (1950s–1960s): First OS concept; jobs
batched together; monitor program ran each job automatically
3.​Multiprogrammed Batch Systems (1960s): Multiple jobs in
memory; CPU never idle while jobs wait for I/O
4.​Time-Sharing Systems (1960s–1970s): Multiple interactive
users; IBM OS/360, UNIX developed
5.​Personal Computer OS (1980s): MS-DOS, Apple DOS; single
user, single task
6.​Modern OS (1990s–present): Windows NT, Linux, macOS;
multi-user, multitasking, networked, GUI
1.5 Functions of an Operating System
Core Functions
•​ Process Management: Creating, scheduling, and terminating
processes and threads
•​ Memory Management: Allocating and deallocating memory
space; tracking which parts are in use
•​ File System Management: Creating, deleting files and
directories; mapping files to secondary storage
•​ I/O System Management: Managing I/O subsystem; device
drivers; buffering, caching, spooling
•​ Secondary Storage Management: Disk scheduling; free space
management; storage allocation
•​ Security and Protection: Protecting processes from each
other; user authentication; access control
•​ Networking: Managing network communications and
protocols
•​ Command Interpreter: Interface between user and OS (shell /
GUI)

1.6 Types of Operating Systems

Type Description Examples
Batch OS Processes jobs in batches IBM OS/360
without user interaction
Time-Sharing Multiple users interact UNIX, Multics
OS simultaneously via terminals
Type Description Examples
Distributed Manages a group of distinct Amoeba, Plan 9
OS computers; appear as one
system
Real-Time Guarantees response within VxWorks, QNX,
OS (RTOS) strict time constraints FreeRTOS
Embedded Designed for embedded Android, iOS,
OS systems with limited Embedded Linux
resources
Handheld OS For smartphones and PDAs; Android, iOS,
limited memory and CPU Windows Mobile
Network OS Provides networking Windows Server,
features; serves network Novell NetWare
clients

Exam Tip — Real-Time OS

Real-Time OS (RTOS) is characterized by PREDICTABLE
response times (not unpredictable). It guarantees tasks are
completed within strict deadlines. Examples: VxWorks, QNX.
Used in aircraft, medical devices, industrial control.
1.7 Concept of Virtual Machine
A Virtual Machine (VM) is a software emulation of a physical
computer. It allows an OS to run as an application on top of
another OS (host OS). The technology enabling this is called
Virtualization.
•​ Host OS: The real OS running on physical hardware
•​ Guest OS: The OS running inside the VM
•​ Hypervisor (VMM – Virtual Machine Monitor): Software
layer that creates and runs VMs

Types of Hypervisors
•​ Type 1 (Bare Metal): Runs directly on hardware (e.g., VMware
ESXi, Microsoft Hyper-V, Xen)
•​ Type 2 (Hosted): Runs on top of a host OS (e.g., VirtualBox,
VMware Workstation)

Benefits of Virtual Machines

• Isolation: Each VM is completely isolated from others —
crash doesn't affect host
• Consolidation: Run multiple OS/apps on one physical
machine
• Development/Testing: Test software on different OS
without multiple physical machines
• Snapshots: Save and restore system state instantly
• Cloud Computing: Basis of cloud infrastructure (AWS,
Azure, GCP)
UNIT 2: Process Management

2.1 Process vs Program

Aspect Program Process
Definition A static set of A program in execution
instructions stored on (active entity)
disk
Nature Passive entity (just a Active entity (has
file) resources, state)
Existence Exists on secondary Exists in main memory
storage
Resources Requires no resources Requires CPU,
memory, I/O, files
Example [Link] on disk Running instance of
Notepad

2.2 Process in Memory

A process in memory is divided into several sections:
•​ Text Section (Code): The executable program code
•​ Data Section: Global and static variables
•​ Heap: Memory dynamically allocated during runtime (malloc,
new)
•​ Stack: Temporary data — function parameters, return
addresses, local variables
 Memory Layout
Stack grows downward from high address; Heap grows
upward from low address. They grow toward each other.
Stack overflow occurs when stack reaches heap.

2.3 Process Control Block (PCB)

The PCB (also called Task Control Block) is the data structure
maintained by the OS for each process. It contains all information
about the process.

PCB Contents (Process Attributes)

•​ Process State: Current state (New, Ready, Running, Waiting,
Terminated)
•​ Process ID (PID): Unique identifier for the process
•​ Program Counter (PC): Address of next instruction to execute
•​ CPU Registers: Contents of all process registers
(accumulators, index registers, stack pointer)
•​ CPU Scheduling Information: Priority, scheduling queue
pointers
•​ Memory Management Information: Page tables, segment
tables, base/limit registers
•​ Accounting Information: CPU time used, real time elapsed,
time limits
•​ I/O Status Information: List of I/O devices allocated, list of
open files
2.4 Process States
A process can be in one of five states during its lifetime:

State Description
New Process is being created
Ready Process is waiting to be assigned to a CPU (in
ready queue)
Running Instructions are being executed by CPU
Waiting Process is waiting for some event (I/O completion,
(Blocked) signal)
Terminated Process has finished execution

State Transitions:
•​ New → Ready: Process admitted to ready queue
•​ Ready → Running: Process selected by scheduler (dispatch)
•​ Running → Waiting: Process requests I/O or waits for event
•​ Running → Ready: Interrupted (time slice expired,
preemption)
•​ Waiting → Ready: I/O or event completed
•​ Running → Terminated: Process finishes execution
 Five-State Process Model
New → Ready → Running ↔ Waiting → TerminatedThe
key difference: Ready means waiting for CPU.
Waiting/Blocked means waiting for an event (I/O).

2.5 Operations on Processes

Process Creation
A process (parent) can create other processes (children) using
system calls like fork() in UNIX.
•​ fork(): Creates a copy of the calling process
•​ exec(): Replaces process memory with a new program
•​ wait(): Parent waits for child to complete
•​ Resource sharing options: Child gets all, subset, or no
resources of parent
•​ Execution options: Parent and child execute concurrently, or
parent waits for child

Process Termination
•​ Normal: Process calls exit() after completing
•​ Abnormal: OS terminates process due to error (memory fault,
illegal instruction)
•​ Parent termination: Parent can terminate child via abort()
system call
•​ Cascading termination: Some OS terminate all children when
parent terminates
2.6 Context Switching
Context switching is the process of saving the state of the
currently running process and loading the saved state of another
process. This allows multiple processes to share a single CPU.

Steps in Context Switching

7.​Save context of current process (PCB update: registers, PC,
stack pointer)
8.​Update PCB state to Ready or Waiting
9.​Move PCB to appropriate queue
10.​ Select another process (via scheduling algorithm)
11.​ Update PCB of new process to Running
12.​ Restore context of new process (load registers, PC)
13.​ Resume execution of new process

Context Switch Overhead

Context switching is pure overhead — no useful work is done
during the switch. Time varies from 1–1000 microseconds
depending on hardware support. Hardware features (multiple
register sets) can reduce context-switch time.
2.7 CPU Bound vs I/O Bound Processes
Type Description Behavior Example
CPU Spends most time Long CPU Scientific
Bound doing bursts, calculations,
computations infrequent I/O video
encoding
I/O Bound Spends most time Short CPU Word
waiting for I/O bursts, frequent processor,
I/O web browser,
database

2.8 Interrupts
An interrupt is a signal to the CPU from hardware or software
indicating an event that needs immediate attention. It allows the
OS to respond to events asynchronously.
•​ Hardware Interrupt: Generated by hardware devices
(keyboard press, I/O completion, timer)
•​ Software Interrupt (Trap/Exception): Generated by executing
a program (system call, divide-by-zero, page fault)

Interrupt Handling
14.​ CPU receives interrupt signal
15.​ CPU saves current state (registers, PC)
16.​ CPU transfers control to interrupt service routine (ISR) via
interrupt vector table
 17.​ ISR executes to handle the interrupt
18.​ Saved state restored; CPU resumes interrupted process

2.9 Preemption vs Non-Preemption

Feature Preemptive Non-Preemptive
Definition OS can forcibly remove Process holds CPU
CPU from running until it voluntarily
process releases it
CPU Release Timer expiry, higher Process terminates,
priority process arrives waits for I/O, or yields
Overhead Higher (context Lower (fewer context
switches) switches)
Response Better for interactive Poor for interactive
Time systems systems
Examples Round Robin, Priority FCFS, SJF
(preemptive) (non-preemptive)
Starvation Low High (long processes
Risk block short ones)
2.10 Process Schedulers
Schedulers select processes from queues for execution. There are
three types:

Long-Term Scheduler (Job Scheduler)

•​ Selects which processes are admitted to the ready queue from
job pool (disk)
•​ Controls the degree of multiprogramming
•​ Executes infrequently (seconds to minutes between decisions)
•​ Should balance CPU-bound and I/O-bound processes

Short-Term Scheduler (CPU Scheduler)

•​ Selects which ready process gets the CPU next
•​ Executes very frequently (every 100ms or less)
•​ Must be very fast — if it takes 10ms to decide, and runs every
100ms, that's 10% overhead
•​ Implements the CPU scheduling algorithm

Medium-Term Scheduler
•​ Handles swapping: removes processes from memory (swap
out) to reduce multiprogramming degree
•​ Later reintroduces processes to memory and execution (swap
in)
•​ Helps manage memory pressure and improve process mix
 Exam Tip — Scheduler Selection
The scheduler that selects processes from mass storage (disk)
and loads them into memory for execution is the Long-Term
Scheduler (also called Job Scheduler). Options I & II
(Long-term + Job Scheduler) are the same thing — answer is I
& II.

2.11 Threads
A thread is the basic unit of CPU utilization. A thread comprises a
thread ID, program counter, register set, and stack. Threads
within the same process share code, data, and OS resources (files,
signals).

Aspect Process Thread

Definition Independent program Lightweight process;
in execution unit of execution
within a process
Memory Own address space Shares address space
with other threads in
same process
Resources Own resources (files, Shares resources of its
I/O) process
Creation High (separate address Low (shares most
Cost space) resources)
Aspect Process Thread
Communicati IPC (inter-process Direct via shared
on communication) memory
Context Expensive Cheap
Switch

Multithreading Models
•​ Many-to-One: Many user-level threads mapped to one kernel
thread. Blocking system call blocks all threads. Cannot use
multiple CPUs.
•​ One-to-One: Each user thread maps to one kernel thread.
More concurrency. Overhead: creating user thread = creating
kernel thread. Examples: Linux, Windows
•​ Many-to-Many: Many user threads multiplexed to many
kernel threads. Best of both worlds. OS creates sufficient
kernel threads.

Exam Tip — Threading Model

Many-to-One model maps MANY user-level threads to ONE
kernel thread. This means if one thread makes a blocking call,
ALL threads in the process block.
UNIT 3: CPU Scheduling, Algorithms, and
Synchronization

3.1 CPU Scheduling Concepts

CPU scheduling is the basis of multiprogrammed operating
systems. By switching between processes, the OS can make the
computer more productive.

Time Measures (Must Know for Exam)

Term Definition Formula
Arrival Time Time at which process Given
(AT) enters the ready queue
Burst Time (BT) Time required by Given
process on CPU
Completion Time at which process From Gantt chart
Time (CT) completes execution
Turnaround Total time from arrival CT − AT
Time (TAT) to completion
Waiting Time Time spent waiting in TAT − BT
(WT) ready queue
Response Time Time from arrival to First start − AT
(RT) first CPU allocation
3.2 Scheduling Algorithms
3.2.1 First Come First Serve (FCFS)
Processes are executed in the order they arrive in the ready queue.
Simple FIFO queue.
•​ Type: Non-preemptive
•​ Selection: Process that arrived first gets CPU first
•​ Advantage: Simple to implement; no starvation
•​ Disadvantage: Convoy effect — short processes wait behind
long processes; high average waiting time

FCFS Example
P1 (AT=0, BT=6), P2 (AT=3, BT=5), P3 (AT=5, BT=4), P4
(AT=7, BT=6)
Gantt Chart: [P1: 0-6] [P2: 6-11] [P3: 11-15] [P4: 15-21]CT:
P1=6, P2=11, P3=15, P4=21
TAT: P1=6-0=6, P2=11-3=8, P3=15-5=10, P4=21-7=14
WT: P1=0, P2=3, P3=6, P4=8
Avg TAT = (6+8+10+14)/4 = 9.5
Avg WT = (0+3+6+8)/4 = 4.25

3.2.2 Shortest Job First (SJF) / Shortest Job Next (SJN)

Process with the shortest burst time is selected next. Optimal for
minimizing average waiting time.
•​ Type: Non-preemptive (SJF) or Preemptive (SRTF — Shortest
Remaining Time First)
 •​ Advantage: Minimum average waiting time among all
algorithms
•​ Disadvantage: Starvation of long processes; requires knowing
burst time in advance (impractical)
•​ Burst time prediction: Exponential averaging of past CPU
bursts

3.2.3 Round Robin (RR)

Each process gets a small unit of CPU time (time quantum/slice).
After quantum expires, process is preempted and added to end of
ready queue.
•​ Type: Preemptive
•​ Time Quantum (q): Typically 10–100 milliseconds
•​ Advantage: Fair; no starvation; good for time-sharing systems
•​ Disadvantage: Higher average TAT than SJF; performance
depends on quantum size

Round Robin: Effect of Quantum Size

• If q is very large → degenerates to FCFS
• If q is very small → processes seem to execute in parallel
(processor sharing), but too many context switches increase
overhead
• Rule of thumb: 80% of CPU bursts should be shorter than
the time quantum
 Round Robin Known For
Round Robin (RR) is known for FAIRNESS and AVOIDING
STARVATION. Every process gets CPU time regardless of
burst time. It is the standard algorithm for time-sharing
systems.

3.2.4 Priority Scheduling

Each process is assigned a priority number. CPU is allocated to the
process with highest priority (smallest integer = highest priority in
most systems).
•​ Type: Can be preemptive or non-preemptive
•​ SJF is a special case of priority scheduling where priority =
predicted next CPU burst
•​ Problem: Starvation — low-priority processes may never
execute
•​ Solution: Aging — gradually increase priority of processes
that wait for a long time

Algorithm Type Advantages Disadvantages

FCFS Non-pree Simple, no Convoy effect,
mptive starvation high avg WT
SJF Non-pree Minimum avg WT Starvation, needs
mptive burst time
prediction
Algorithm Type Advantages Disadvantages
SRTF Preemptiv Optimal avg WT Starvation, high
e overhead
Round Preemptiv Fair, no starvation High avg TAT,
Robin e context switch
overhead
Priority Both Important jobs run Starvation of
first low-priority jobs

Which Algorithm Has Highest Turnaround Time?

FCFS typically gives the HIGHEST average turnaround time
for a set of processes due to the convoy effect. SJF gives the
minimum average waiting time.

3.3 Process Synchronization

The Critical Section Problem
When multiple processes share data, concurrent access can lead to
data inconsistency. A critical section is the segment of code where a
process accesses shared data.

Term Definition
Critical Section Code segment that accesses shared resources;
only one process should execute it at a time
Term Definition
Entry Section Code that requests permission to enter the
critical section
Exit Section Code that releases permission after leaving
the critical section
Remainder Rest of the code (non-critical)
Section
Race Condition When outcome depends on the order of
execution of multiple processes accessing
shared data

Requirements for Critical Section Solution

19.​ Mutual Exclusion: Only one process can be in its critical
section at a time
20.​ Progress: If no process is in its critical section and some
want to enter, only those not in remainder section can
participate in the decision; selection cannot be postponed
indefinitely
21.​ Bounded Waiting: There exists a bound on the number of
times other processes enter their critical sections after a
process requests entry and before that request is granted
 Mutual Exclusion
Mutual Exclusion: If process Pi is executing in its critical
section, then no other processes can be executing in their
critical sections. This is the PRIMARY requirement for
solving the critical section problem.

Peterson's Solution
A classic software solution to the critical section problem for two
processes. Uses two shared variables:
•​ int turn: Indicates whose turn it is to enter the critical section
•​ boolean flag[2]: Indicates if a process is ready to enter its
critical section

Process Pi:
flag[i] = true; turn = j;
while (flag[j] && turn == j); /* Entry section */
/* Critical Section */ flag[i] = false; /* Exit section */

Peterson's solution satisfies all three requirements: mutual

exclusion, progress, and bounded waiting.

3.4 Semaphores
A semaphore is an integer variable that, apart from initialization,
is accessed only through two atomic operations: wait() and signal()
(also called P() and V()).
Semaphore Operations
•​ wait(S): Decrements S. If S becomes negative, the calling
process is blocked.
•​ signal(S): Increments S. If there are blocked processes, one is
unblocked.

Type Initial Value Use

Binary 1 Mutual exclusion; controls
Semaphore access to critical section; acts
(Mutex) like a lock
Counting N (resource Controls access to a resource
Semaphore count) with multiple instances

Semaphore Definition
A semaphore is a SYNCHRONIZATION MECHANISM (not
a virus, not a file system structure, not a device driver). It
solves the critical section problem and synchronizes
concurrent processes.

Producer-Consumer Problem (Bounded Buffer)

Classic synchronization problem: Producer creates items,
Consumer consumes them, using a shared buffer of size N.
•​ mutex: Binary semaphore, initialized to 1 (mutual exclusion
for buffer access)
 •​ empty: Counting semaphore, initialized to N (empty slots in
buffer)
•​ full: Counting semaphore, initialized to 0 (full slots in buffer)

3.5 Deadlock
A deadlock is a situation where a set of processes are all blocked,
each waiting for an event that can only be caused by another
process in the set. No process can proceed.

Four Necessary Conditions for Deadlock (Coffman Conditions)

ALL FOUR must hold simultaneously for deadlock to occur:
22.​ Mutual Exclusion: At least one resource must be held in a
non-sharable mode (only one process at a time)
23.​ Hold and Wait: A process must be holding at least one
resource and waiting to acquire additional resources held by
other processes
24.​ No Preemption: Resources cannot be preempted; they can
only be released voluntarily by the holding process
25.​ Circular Wait: There must exist a set of waiting processes
{P0, P1, ..., Pn} such that P0 is waiting for a resource held by
P1, P1 is waiting for P2, ..., Pn is waiting for P0
 Exam Tip — Deadlock Conditions
Q5 from exams: 'Resource held in non-sharable mode;
requesting process must wait until resource is released' → This
is MUTUAL EXCLUSION.
Deadlock in OS is 'a STATE WHERE PROCESSES CANNOT
PROCEED' (not a crash, not a virus, not hardware failure).

Deadlock Prevention
Prevent deadlock by ensuring at least one of the four conditions
cannot hold:
•​ Prevent Mutual Exclusion: Make resources sharable (not
always possible)
•​ Prevent Hold and Wait: Require processes to request all
resources at once; or release all resources before requesting
new ones
•​ Prevent No Preemption: If a process holding resources
requests another that cannot be immediately allocated, release
all currently held resources
•​ Prevent Circular Wait: Impose total ordering on resource
types; each process requests resources in increasing order

Deadlock Avoidance — Banker's Algorithm

The Banker's Algorithm determines if a resource allocation will
leave the system in a safe state before granting the request.
•​ Safe State: System can allocate resources to each process in
some order and avoid deadlock
 •​ Safe Sequence: A sequence where each process's max needs can
be satisfied by available + resources held by earlier processes
•​ Key matrices: Available, Max, Allocation, Need = Max −
Allocation

Banker's Algorithm Steps

1. Calculate Need matrix: Need[i][j] = Max[i][j] −
Allocation[i][j]
2. Find a process whose Need ≤ Available
3. Add that process's Allocation to Available (process finishes)
4. Repeat until all processes finish (safe) or no process can
proceed (unsafe)
UNIT 4: Memory Management

4.1 Memory Unit and Structure

Memory (RAM) is the working storage of the computer. Programs
must be in main memory (RAM) to execute.
•​ Each byte of memory has a unique address
•​ CPU can only directly access main memory and registers
•​ CPU speed far exceeds memory speed → cache memory
bridges the gap

4.2 Memory Hierarchy

Lev Type Speed Cost Size
el
L1 CPU Registers Fastest Highest Bytes
L2 L1 Cache Very fast Very KB
high
L3 L2/L3 Cache Fast High MB
L4 Main Memory Moderat Moderat GB
(RAM) e e
L5 Secondary Slow Low TB
Storage
(SSD/HDD)
L6 Tertiary Slowest Lowest PB
(Optical, Tape)
4.3 Logical vs Physical Address
Aspect Logical Address Physical Address
Also Called Virtual address Real address
Generated CPU during program Memory hardware
By execution (RAM)
Visible To User/program Hardware only
Range 0 to max (logical Actual physical memory
address space) locations

The Memory Management Unit (MMU) performs run-time

mapping from logical to physical addresses.
MMU — Memory Management Unit
The MMU performs the run-time mapping from VIRTUAL
(logical) to PHYSICAL addresses. It uses relocation registers,
page tables, or segment tables. Answer to 'what performs
run-time mapping' = Memory Management Unit.

4.4 Swapping
Swapping is the process of temporarily removing inactive processes
from main memory to secondary storage (disk) to free memory.
Later, the process is brought back (swapped in) to continue
execution.
•​ Medium-term scheduler handles swapping decisions
 •​ Allows more processes than can fit in memory
•​ Major bottleneck: I/O transfer time (swapping a 100MB
process might take seconds)

Swapping Definition
The technique of temporarily removing INACTIVE
programs from memory and placing them on disk is called
SWAPPING (not paging, not segmentation, not compaction).

4.5 Contiguous vs Non-Contiguous Memory Allocation

Contiguous Allocation
Each process occupies a single contiguous block of memory. Two
methods:
•​ Fixed Partitioning: Memory divided into fixed-size partitions.
Suffers from internal fragmentation (wasted space within a
partition).
•​ Variable Partitioning: Partitions created dynamically to
exactly fit processes. Suffers from external fragmentation.
Memory Allocation Strategies (Variable Partitioning)
Strategy Description Advantage Disadvantage
First Fit Allocate first hole Fast; simple External
that is big enough fragmentation
Best Fit Allocate smallest Least wasted External
hole that fits space per fragmentation
allocation ; slow
Worst Fit Allocate largest Leaves large External
hole remaining fragmentation
holes ; most
wasteful

Exam Tip — External Fragmentation

External fragmentation occurs with FIRST FIT, BEST FIT,
AND WORST FIT (all variable partition strategies). It occurs
when total memory exists to satisfy a request, but it is not
contiguous. Answer: I, II & III (ALL of them cause external
fragmentation).

Fragmentation Types
•​ Internal Fragmentation: Wasted space INSIDE an allocated
partition (fixed partitioning, paging)
•​ External Fragmentation: Enough total free memory, but not
contiguous (variable partitioning)
 •​ Compaction: Shuffle memory contents to place all free
memory together (solution to external fragmentation);
requires dynamic relocation

4.6 Paging
Paging is a non-contiguous memory allocation technique that
divides physical memory into fixed-size frames and logical memory
into same-size pages.
•​ Page Size = Frame Size (same fixed size, typically 4KB)
•​ Page Table: Maps logical page numbers to physical frame
numbers
•​ Internal fragmentation may occur (last page may not be
completely full)
•​ No external fragmentation

Address Translation in Paging

Logical Address = Page Number (p) + Page Offset (d)
Physical Address = Frame Number (f ) + Page Offset (d)
•​ p: Index into page table to find frame number f
•​ d: Offset within the page/frame (same in both)
•​ Physical address = f × page_size + d
 Page Table Usage
In a paging system, the PAGE TABLE is used to
TRANSLATE LOGICAL ADDRESSES TO PHYSICAL
ADDRESSES. It maps page numbers to frame numbers.

Internal Fragmentation in Paging

Which Memory Scheme Has Internal Fragmentation?
PAGING suffers from INTERNAL FRAGMENTATION.
The last page allocated to a process may not be completely full
— the remaining space in the frame is wasted (internal
fragmentation). Segmentation has external fragmentation.

4.7 Virtual Memory

Virtual memory is a technique that allows execution of processes
that may not be completely in physical memory. It gives the illusion
of a very large memory.
•​ Logical address space can be much larger than physical
memory
•​ Implemented via demand paging (most common) or demand
segmentation
•​ Only the needed parts of a process need to be in memory
 Virtual Memory Definition
Virtual memory is DISK SPACE USED AS AN EXTENSION
OF RAM. It allows programs larger than physical RAM to
run by keeping only active portions in RAM and the rest on
disk (page file / swap space).

Demand Paging
Pages are loaded into memory only when they are demanded
(accessed), not at program startup.
•​ Lazy swapper (pager): Never swaps a page into memory unless
it will be needed
•​ Valid-Invalid bit: Each page table entry has a bit; valid = in
memory, invalid = on disk or not part of process

Page Fault
When a process accesses a page not in memory (invalid bit set), a
page fault occurs.
26.​ Process accesses a page → CPU generates logical address
27.​ Page table lookup → invalid bit set → TRAP (page fault)
28.​ OS determines if reference is invalid (abort) or just not in
memory
29.​ OS finds free frame; reads page from disk into frame
30.​ Update page table; set valid bit
31.​ Restart the instruction that caused the fault
Page Replacement Algorithms
Algorithm Description Property Performance
FIFO Replace the page No stack Belady's anomaly:
that has been in property more frames can
memory the cause more faults
longest
Optimal Replace page that Stack Best possible; not
(OPT) will not be used property implementable in
for the longest practice
time
LRU Replace page that Stack Good
has not been used property approximation to
for the longest OPT
time
Second FIFO + reference Approxim Practical LRU
Chance bit; give pages a ates LRU approximation
second chance

Stack Property
Algorithms with the STACK PROPERTY: Optimal and
LRU. Stack property means: if you have n frames, the set of
pages in memory is a SUBSET of the pages in memory with
n+1 frames. These algorithms are not susceptible to Belady's
anomaly.
FIFO does NOT have the stack property.
UNIT 5: File and Device Management

5.1 Files
A file is a named collection of related information recorded on
secondary storage. It is the smallest unit of secondary storage that
the user can refer to.

File Attributes
•​ Name: Human-readable symbolic name
•​ Identifier: Unique tag (number) identifying the file within the
file system
•​ Type: Needed for systems that support different file types
(e.g., .txt, .exe, .docx)
•​ Location: Pointer to location on device
•​ Size: Current size of file (in bytes, words, or blocks)
•​ Protection: Access control — who can read, write, execute
•​ Time, Date, and User Identification: For protection, security,
and usage monitoring

File Operations
•​ Create: Allocate space; make entry in directory
•​ Write: Write data at write pointer position
•​ Read: Read data at read pointer position
•​ Reposition (Seek): Move file pointer to given position
•​ Delete: Release space; remove directory entry
 •​ Truncate: Erase content but keep attributes

5.2 File Directories

A directory is a collection of nodes containing information about
all files.

Structure Description Advantage Disadvantage

Single-Level One directory Simple Naming
Directory for all files in implementatio conflicts; no
the system n grouping;
poor for
multi-user
Two-Level Separate No naming Cannot group
Directory directory for conflicts files within a
each user between users user's
(MFD + UFD) directory
Tree-Structur General tree of Efficient Difficult to
ed Directory directories; searching; share files
subdirectories grouping;
allowed current
directory
concept
Acyclic Tree + shared Allows sharing Dangling
Graph subdirectories/ without pointers;
Directory files (links) duplication reference
counting
needed
Structure Description Advantage Disadvantage
General Acyclic graph Most flexible Must handle
Graph + cycles cycles; garbage
Directory allowed collection
needed

Exam Tip — Directory Sharing

Which directory structure allows sharing of subdirectories
and files? Answer: ACYCLIC GRAPH DIRECTORY. It
extends the tree structure to allow files/directories to be
shared via links (hard links or symbolic links).

5.3 File Allocation Methods

Contiguous Allocation
•​ Each file occupies contiguous blocks on disk
•​ Advantage: Simple; supports sequential and random access;
fast
•​ Disadvantage: External fragmentation; must know file size at
creation

Linked (Chained) Allocation

•​ Each file is a linked list of disk blocks; blocks may be scattered
anywhere on disk
•​ Each block contains a pointer to the next block
•​ Advantage: No external fragmentation; no need to declare size
 •​ Disadvantage: Random access is slow (must follow links);
pointer reliability
•​ FAT (File Allocation Table) is a variation that puts all pointers
in a table

Indexed Allocation
•​ Each file has an index block containing all pointers to its data
blocks
•​ Advantage: Supports direct access; no external fragmentation
•​ Disadvantage: Index block overhead; small files waste index
block

5.4 Disk Scheduling

The OS is responsible for using hardware efficiently. For disk
drives, this means minimizing disk access time. Disk access time =
seek time + rotational latency + transfer time.
•​ Seek Time: Time for disk arm to move to desired cylinder
(dominant factor)
•​ Rotational Latency: Time for desired sector to rotate under
disk head
•​ Transfer Time: Time to transfer data
Disk Scheduling Algorithms
Algorithm Description Advantage Disadvantage
FCFS Service requests Simple; fair Not optimal;
in order they high seek time
arrive
SSTF Service request Lower seek Starvation of
(Shortest closest to time than distant requests
Seek Time current head FCFS
First) position
SCAN Head moves in No starvation; Long wait for
(Elevator) one direction uniform requests just
servicing service missed
requests until
end, then
reverses
C-SCAN Like SCAN but More uniform Wasted return
(Circular returns to start wait time sweep
SCAN) without
servicing on
return
LOOK Like SCAN but Better than Slightly
reverses at last SCAN complex
request (not
disk end)
C-LOOK Like C-SCAN More uniform Slightly
but returns to than LOOK complex
Algorithm Description Advantage Disadvantage
first request
(not disk start)

Disk Scheduling Example (from exams)

Disk with 5000 cylinders (0–4999).
Current position: 143.
Previous: 125. Queue: 86, 1470, 913, 1774, 948, 1509, 1022,
1750, 130FCFS:
Service in order:
143→86→1470→913→1774→948→1509→1022→1750→
130SCAN (moving toward 4999): 143→130→86→... wait,
check direction: from 125→143, moving UP →
143→1022→1470→1509→1750→1774→4999→1470... no,
SCAN goes to end then backFor SCAN moving upward:
143→948→1022→1470→1509→1750→1774→4999 then
back →913→130→86

5.5 Disk Structure

The surface of a disk platter is logically subdivided into:
•​ Tracks: Concentric circles on disk surface
•​ Sectors: Pie-slice-shaped divisions of a track (smallest
addressable unit)
•​ Cylinders: Set of tracks at the same position on all platters
•​ Spindle: Central axis on which platters rotate
 Exam Tip — Disk Subdivision
The surface of a disk platter is logically subdivided into
SECTORS and TRACKS (and cylinders).
The answer is: I (Sector) & IV (Tracks) → option b: I &
[Link] is the rotating axle, not a logical subdivision.

5.6 I/O Devices and Memory-Mapped I/O

I/O Device Types
•​ Block Devices: Store information in fixed-size blocks; each
block has its own address; can read/write independently
(HDD, SSD, USB drives)
•​ Character Devices: Deliver/accept stream of characters; not
addressable; no seek operation (keyboard, mouse, serial ports)

Memory-Mapped I/O
In memory-mapped I/O, device registers are mapped to memory
addresses. The CPU uses standard memory access instructions
(load/store) to communicate with I/O devices. This eliminates
special I/O instructions.
•​ Advantage: No special I/O instructions needed; can use all
memory-addressing modes
•​ Used by: Video cards (framebuffer), network interfaces
DMA (Direct Memory Access)
DMA allows I/O devices to transfer data directly to/from memory
without CPU involvement for each byte.
32.​ CPU initiates DMA: tells DMA controller source,
destination, and number of bytes
33.​ DMA controller performs the transfer independently
34.​ DMA controller interrupts CPU when transfer is complete
•​ Benefit: CPU freed from managing slow I/O byte-by-byte; can
do other work during transfer

5.7 File System Mounting

Before a file system can be accessed, it must be mounted. Mounting
attaches a portion of the file system into a directory structure.
•​ Mount Point: The directory where the new file system is
attached
•​ After mounting, files on the new device are accessible through
the mount point

File System Mounting Definition

Mounting = ATTACHING a portion of the file system into a
directory structure (making it accessible). Not removing, not
deleting, not creating. The answer is: c. attaching a portion of
the file system into a directory structure.
5.8 Bootstrap Program
When a computer is powered on, it needs an initial program to run
— the bootstrap program (also called bootstrap loader or
bootloader).
•​ Stored in ROM or EEPROM (firmware); known as BIOS or
UEFI
•​ Initializes all aspects of the system: CPU registers, device
controllers, main memory contents
•​ Loads the OS kernel from disk into memory
•​ Transfers control to the OS to begin execution

Bootstrap Program
The program that initializes all aspects of the system (CPU
registers to device controllers and contents of main memory)
and then starts the OS is the BOOTSTRAP program (option
c). Not 'main', not 'bootloader' (a variant), not 'room'.
EXAM PREPARATION: Answer Key & Common
Questions

Section A: MCQ Answer Guide

Question Topic Correct Explanation
Answer
Not an OS example b. Java Java is a programming
language/platform, not
an OS. MS-DOS, Linux,
Windows are OSes.
Primary role of OS d. All of the OS manages hardware,
above memory, AND processes
— all of these.
Process refers to b. A program Process = active
in execution program. Program alone
= passive file on disk.
CPU Scheduler role c. Manage CPU scheduler selects
CPU process from ready
utilization and queue for execution.
scheduling
Deadlock in OS b. A state Deadlock is NOT a
where crash, virus, or hardware
processes failure.
cannot proceed
Question Topic Correct Explanation
Answer
Highest turnaround a. FCFS FCFS has convoy effect
time → high turnaround
time.
Semaphore b. A Semaphore is for process
synchronizatio synchronization, not a
n mechanism virus/file/driver.
Virtual memory b. Disk space Virtual memory extends
used as RAM using disk (swap
extension of space).
RAM
Real-time OS b. Predictable RTOS guarantees
characteristic response times predictable, bounded
response times.
Fairness & avoiding c. Round RR gives each process
starvation Robin (RR) equal time slice — fair,
no starvation.
Mutual exclusion c. Mutual If Pi in CS, no others
(critical section) exclusion can be in CS = mutual
exclusion.
Virtual to physical a. Memory MMU performs
mapping management run-time address
unit translation.
Directory for c. Acyclic Allows files/directories
sharing graph to be shared via links.
directory
Question Topic Correct Explanation
Answer
File system c. Attaching Mounting attaches a file
mounting into directory system to make it
structure accessible.
Bootstrap program c. bootstrap Bootstrap initializes
system and starts OS.
Disk subdivision b. I & IV Disk surface → tracks
(Sector & and sectors. Cylinder =
Tracks) across platters.
Stack property (page d. LRU LRU and Optimal have
replacement) stack property. FIFO
does not.
External d. I, II & III ALL variable allocation
fragmentation strategies cause external
fragmentation.
Deadlock condition a. Mutual Non-sharable resource
(non-shareable) exclusion → only one process at a
time = mutual exclusion.
Race condition b. Race Outcome depends on
condition access order of
concurrent processes =
race condition.
Virtualization c. Running OS as
Virtualization application in another
OS = virtualization.
Question Topic Correct Explanation
Answer
Timeshare: time slot c. Ready state When time slice expires,
expires process preempted →
back to Ready state.
Many user threads a. Many to one Many-to-one: many user
→ one kernel model threads mapped to one
kernel thread.
Turnaround time c. turnaround Submission to
definition time completion =
turnaround time.
Purpose of a. Execute Threading enables
threading multiple concurrent execution
processes within a process.
Which scheduler a. I & II Long-term = Job
selects for execution (Long-term & Scheduler; selects from
from disk Job Scheduler) mass storage.
Scheduling causing b. Shortest Job SJF can starve long
starvation First processes indefinitely.
Non-preemptive a. Process If no preemption:
no-preemption waits for process holding
strategy resources resources waits if it can't
get more.
FCFS Calculation — Worked Example (Exam Q8)
Given: P1(AT=0, BT=6), P2(AT=3, BT=5), P3(AT=5, BT=4),
P4(AT=7, BT=6)

FCFS Solution
GANTT CHART:[P1: 0→6] [P2: 6→11] [P3: 11→15] [P4:
15→21]
Completion Times: P1=6, P2=11, P3=15, P4=21
Turnaround Times (CT - AT): P1: 6-0=6 | P2: 11-3=8 | P3:
15-5=10 | P4: 21-7=14
Average TAT = (6+8+10+14)/4 = 38/4 = 9.5
Waiting Times (TAT - BT): P1: 6-6=0 | P2: 8-5=3 | P3:
10-4=6 | P4: 14-6=8
Average WT = (0+3+6+8)/4 = 17/4 = 4.25

Banker's Algorithm — Worked Example (Exam Q10)

Given: Resources A(15), B(6), C(9), D(10).
Available: A=6, B=3, C=5, D=4
Current Allocation: P0(2,0,2,1), P1(0,1,1,1), P2(4,1,0,2),
P3(1,0,0,1), P4(1,1,0,0), P5(1,0,1,1)
Maximum Demand: P0(9,5,5,5), P1(2,2,3,3), P2(7,5,4,4),
P3(3,3,3,2), P4(5,2,2,1), P5(4,4,4,4)
Verify Available Array
Total Resources - Sum of Allocations =
AvailableA: 15-(2+0+4+1+1+1) = 15-9 = 6
✓B: 6-(0+1+1+0+1+0) = 6-3 = 3
✓C: 9-(2+1+0+0+0+1) = 9-4 = 5
✓D: 10-(1+1+2+1+0+1) = 10-6 = 4 ✓

Need Matrix (Max - Allocation)

P0: (9-2, 5-0, 5-2, 5-1) = (7, 5, 3, 4)
P1: (2-0, 2-1, 3-1, 3-1) = (2, 1, 2, 2)
P2: (7-4, 5-1, 4-0, 4-2) = (3, 4, 4, 2)
P3: (3-1, 3-0, 3-0, 2-1) = (2, 3, 3, 1)
P4: (5-1, 2-1, 2-0, 1-0) = (4, 1, 2, 1)
P5: (4-1, 4-0, 4-1, 4-1) = (3, 4, 3, 3)

Safe Sequence
Available: (6,3,5,4)P1: Need(2,1,2,2) ≤ (6,3,5,4) → Run P1 →
Available becomes (6,4,6,5)P3: Need(2,3,3,1) ≤ (6,4,6,5) →
Run P3 → Available becomes (7,4,6,6)P4: Need(4,1,2,1) ≤
(7,4,6,6) → Run P4 → Available becomes (8,5,6,6)P0:
Need(7,5,3,4) ≤ (8,5,6,6) → Run P0 → Available becomes
(10,5,8,7)P2: Need(3,4,4,2) ≤ (10,5,8,7) → Run P2 →
Available becomes (14,6,8,9)P5: Need(3,4,3,3) ≤ (14,6,8,9) →
Run P5 ✓Safe Sequence: P1 → P3 → P4 → P0 → P2 → P5
Quick Reference: Key Definitions for Section B/C
Term One-Line Definition
Operating System Software that manages hardware resources
and provides services to programs
Process A program in execution; an active entity
with its own resources and state
Thread Lightweight process; basic unit of CPU
utilization within a process
Context Switch Saving state of current process and loading
state of another process
Deadlock Set of processes permanently blocked, each
waiting for resources held by others
Race Condition Outcome depends on execution order of
concurrent processes accessing shared data
Critical Section Code segment accessing shared resources;
only one process can execute it at a time
Semaphore Integer synchronization variable accessed
only via wait() and signal() operations
Virtual Memory Technique allowing processes larger than
physical memory to execute using disk as
extension
Page Fault Trap when CPU accesses a page not
currently in physical memory
Thrashing Process spends more time paging than
executing; occurs with insufficient frames
Term One-Line Definition
Paging Non-contiguous memory allocation; logical
memory divided into pages, physical into
frames
Segmentation Non-contiguous memory allocation; logical
address space divided by user-defined
segments
Swapping Moving entire processes between memory
and disk to increase multiprogramming
Disk Scheduling Ordering disk I/O requests to minimize seek
time and maximize throughput
Bootstrap Initial program that initializes hardware
and loads OS when computer starts

Common Exam Question Templates

For Section B (4-mark questions) — Structure Your Answers
•​ Define (1 mark): Give a clear one-sentence definition
•​ Explain (2 marks): Elaborate with characteristics, how it
works
•​ Example or Diagram (1 mark): Give a concrete example or
draw a simple diagram
For Section C (8-mark questions) — Detailed Answers
•​ Scheduling problems: Always draw Gantt chart, calculate all
metrics, show average
•​ Theory questions: Define → Explain → Properties →
Example → Comparison if asked
•​ Deadlock: List all 4 conditions with definition; Banker's
algorithm needs all matrices

Final Exam Tips

1. Java is NOT an OS — it's a programming language
2. RTOS has PREDICTABLE (not unpredictable) response
times
3. Round Robin = Fairness + No Starvation
4. LRU and Optimal have stack property; FIFO does NOT
5. External fragmentation: ALL variable allocation strategies
6. Semaphore = synchronization mechanism (not a virus!)
7. Virtual memory = disk space as RAM extension
8. Bootstrap program starts the OS (initializes everything)
9. Acyclic graph directory allows file sharing
10. Disk surface = Tracks + Sectors (not spindle)