OPERATING SYSTEM

CONCEPTS
Complete Exam Study Notes
[Link]. (H) Computer Science Sem III (NEP) | DSC 08

Reference: Silberschatz, Galvin & Gagne — OS Concepts, 9th Edition

Covers all 5 Units | Definitions | Examples | Algorithms | Exam Tips

UNITS COVERED

Unit 1 Introduction — What OS Does, Structure, Operations, Process/Memory/Storage Mgmt

Unit 2 OS Structures — Services, System Calls, Programs, Structures
Unit 3 Process Management — Processes, Threads, Sync, Scheduling, Deadlocks
Unit 4 Memory Management — Main Memory, Virtual Memory, Paging, Segmentation
Unit 5 File System — Interface, Implementation, Directory, Allocation Methods
UNIT 1: INTRODUCTION (Chapter 1)
This unit covers the fundamental concepts of what an operating system is, its role, structure, and the
basic services it provides. These sections — 1.1, 1.4, 1.5, 1.6, 1.7, 1.8 — form the backbone of your
OS understanding.

1.1 What Operating Systems Do

A computer system has four major components: hardware, operating system, application programs,
and users.
• Hardware: CPU, memory, I/O devices — provides raw computing resources
• Application Programs: word processors, compilers, browsers — solve user problems
• Operating System: controls and coordinates hardware use among applications and users
• Users: people or other machines that interact with the system

The OS as Resource Allocator

The OS acts as a manager of system resources (CPU time, memory, I/O devices, etc.). When multiple
programs compete for the same resource, the OS must decide who gets what and when — like a traffic
controller or a government.

Simple Analogy
Think of the OS like the government of a country. It doesn't produce anything useful itself — but
without it, individuals (programs) would fight over resources. It enforces rules, allocates
resources fairly, and maintains order.

The OS as Control Program

The OS also acts as a control program — it manages execution of user programs to prevent errors and
improper use of hardware, especially I/O devices.

The Kernel
The most common definition: the OS is the one program running at all times — this is called the
KERNEL. Everything else is either a system program or an application program.

🎯 EXAM TIP
Frequently asked: Define 'Operating System' and 'Kernel'. Know that kernel = the core program
always running. System programs are associated with the OS but not part of the kernel.
Application programs are all other programs.

Types of Computer Systems and OS Goals

System Type OS Goal Example
Personal Computer Ease of use; performance for one user Windows, macOS
(PC)
 Mainframe / Server Resource utilization; fairness among many users Linux, Unix
Mobile Devices Touch UI; battery efficiency; connectivity Android, iOS
Embedded Systems Run with no user interaction; real-time response Car ECU, Microwave

1.4 Operating-System Structure

Modern OSes use multiprogramming and time-sharing to efficiently use hardware.

Multiprogramming
Multiprogramming is the technique of keeping multiple jobs (programs) in memory simultaneously so
the CPU always has something to execute. When one job waits for I/O, the CPU switches to another
job.

How It Works
Jobs are loaded into memory from the job pool (on disk). When Job A waits for I/O, the CPU is
given to Job B. When Job A's I/O finishes, it goes back to the 'ready' state. This keeps CPU
utilization high — the CPU is rarely idle.

Time-Sharing (Multitasking)
Time-sharing is a logical extension of multiprogramming. The CPU switches among jobs so frequently
(every fraction of a second) that each user gets the impression the entire machine is theirs. Each user
has at least one process in memory.
Feature Multiprogramming Time-Sharing
Primary Goal Maximize CPU utilization Minimize response time for users
Switching When a job waits for I/O Every time quantum (e.g., 10ms)
User Interaction Not required Required (interactive)
Number of Users Usually batch jobs Many concurrent users

🎯 EXAM TIP
The difference between multiprogramming and time-sharing is a very common exam question!
Multiprogramming = max CPU use. Time-sharing = interactive, frequent context switches,
minimize response time.

1.5 Operating-System Operations

Modern OSes are interrupt-driven. Hardware and software events cause interrupts that the OS must
handle.
Interrupt-Driven Operation
When a device needs attention (e.g., keyboard press, disk read complete), it sends an interrupt signal
to the CPU. The CPU stops its current work, saves state, and runs the interrupt handler. After handling,
it resumes previous work.
• Hardware Interrupts: Triggered by I/O devices (keyboard, disk, mouse)
• Software Interrupts (Traps): Triggered by user programs — either for errors (divide by zero) or
system calls

Dual-Mode Operation
To protect the OS from user programs (and users from each other), CPUs support at least two modes:
Mode Also Called What Can Run Example Instructions
Kernel Mode Supervisor / All instructions including I/O control, interrupt
System / Privileged privileged ones handling, memory
Mode management
User Mode Non-privileged Mode Only non-privileged Normal user application
instructions code

The mode is tracked by a mode bit in the CPU hardware. Bit = 0 → Kernel mode. Bit = 1 → User mode.

Why Dual Mode?

Without dual mode, a user program could do anything — format the disk, overwrite OS memory,
crash the system. Dual mode ensures that privileged (potentially dangerous) operations can
only be done by the OS, not by user programs.

System Calls (Trap to Kernel)

When a user program needs an OS service (read a file, create a process, etc.), it makes a system call
— a software interrupt that switches from user mode to kernel mode. The OS handles the request and
switches back.

🎯 EXAM TIP
Know the mode bit concept: 0 = kernel, 1 = user. Privileged instructions can ONLY run in kernel
mode. System calls are the mechanism for user programs to request OS services — they trigger
a switch from user mode to kernel mode.

Timer
To prevent a user program from hogging the CPU, the OS uses a hardware timer. The timer is set to
interrupt the CPU after a fixed interval. When it fires, the OS regains control and can switch to another
process. Users cannot modify the timer (it's a privileged operation).

1.6 Process Management

A process is a program in execution — it is the basic unit of work in a system.
 • A program is passive (a file on disk). A process is active (running in memory with resources).
• A single-threaded process has one program counter; multi-threaded has one PC per thread.

OS Responsibilities for Process Management

• Scheduling processes and threads on CPUs
• Creating and deleting user and system processes
• Suspending and resuming processes
• Providing mechanisms for process synchronization
• Providing mechanisms for interprocess communication (IPC)

1.7 Memory Management

The CPU can only directly access main memory (RAM). For a program to run, its instructions must be
in memory. The OS manages what is in memory, and when.

OS Responsibilities for Memory Management

• Keeping track of which parts of memory are being used and by whom
• Deciding which processes and data to move into/out of memory
• Allocating and deallocating memory space as needed
🎯 EXAM TIP
Memory management is tested frequently. Remember: CPU can only access RAM. All programs
must be loaded into memory to run. The OS controls which program gets how much memory.

1.8 Storage Management

The OS abstracts physical storage (disk, USB, SSD) into a uniform logical view — the file system.

1.8.1 File-System Management

• Files are the logical storage unit. The OS manages creation/deletion of files and directories
• Supports primitives: create, delete, read, write, search files
• Maps files to physical storage (disk sectors)
• Backs up files to stable (nonvolatile) storage

1.8.2 Mass-Storage Management

Disks (HDDs, SSDs) are the primary storage medium for both programs and data. Efficient disk
management is critical to overall system performance.
• Free space management: tracking which disk blocks are free
• Storage allocation: deciding where new files go on disk
• Disk scheduling: optimizing the order of disk read/write requests
Storage Hierarchy (Memory Speed vs Cost)
Level Type Speed Cost Volatile?
1 (Top) CPU Registers Fastest Highest Yes
2 Cache (L1, L2, L3) Very Fast High Yes
3 Main Memory (RAM) Fast Moderate Yes
4 SSD / Flash Moderate Low-Moderate No
5 (Bottom) Magnetic Disk (HDD) Slow Lowest No

Volatile storage loses data when power is removed. Nonvolatile storage (disk) retains data. The OS
moves data up the hierarchy as needed for execution.

1.8.3 Caching
Caching is a key performance concept. Frequently used data from slower storage is copied to faster
storage (the cache). When needed again, it's found in cache — fast access without going to slow
storage.

Cache Example
When you open a program, its code is loaded from disk (slow) into RAM (fast). Frequently
accessed parts are brought into CPU cache (faster still). The OS and hardware manage this
hierarchy automatically.

🎯 EXAM TIP
Know the storage hierarchy and caching concept. A very common question is: 'What is caching?
Why is it important?' Answer: copying data from slower to faster storage for performance. Also
know: volatile vs nonvolatile storage.

I/O Subsystem Management

The OS hides hardware specifics of I/O devices from users through the I/O subsystem:
• A memory-management component including buffering, caching, and spooling
• A general device-driver interface
• Drivers for specific hardware devices
UNIT 2: OS STRUCTURES (Chapter 2)
This unit covers how operating systems are organized and how users/programs interact with them. Key
sections: 2.1, 2.3, 2.4, 2.5, 2.7, 2.7.4.

2.1 Operating-System Services

An OS provides an environment for the execution of programs. It provides services to programs and to
the users of those programs:

Services Helpful to Users

Service Description
User Interface (UI) CLI (command-line), GUI (graphical), or touch-based interfaces
Program Execution Load program into memory, run it, end execution (normal or
abnormal)
I/O Operations Programs need I/O; OS provides an interface to do this safely
File-System Manipulation Read, write, create, delete files and directories; search, list info
Communications Processes exchange information via shared memory or message
passing
Error Detection Detect and handle errors in CPU, memory, I/O devices, user
programs

Services for OS Efficiency (not users directly)

Service Description
Resource Allocation Allocate CPU cycles, memory, I/O devices among multiple concurrent
users/jobs
Accounting Track how much and what resources each user uses (for billing or
tuning)
Protection & Security Ensure all access to resources is controlled; authenticate users; defend
against threats

2.3 System Calls

System calls provide the programming interface between a running program and the OS. They are
typically written in C or C++. Although programs can call system calls directly, most use higher-level
APIs.

Common API Examples

• POSIX API (Linux/Unix/macOS): read(), write(), fork(), exec(), open(), close()
 • Win32 API (Windows): ReadFile(), CreateProcess(), WriteFile()
• Java API: Java programs call OS via the JVM

Why Use APIs Instead of Direct System Calls?

• APIs are simpler and more portable (same API across different OS versions)
• Direct system calls vary between OS versions; APIs hide these differences

System Call Implementation

Each system call has a number. A system-call interface maintains a table indexed by these numbers.
When a system call is made, the user passes the number, the OS looks it up, executes it, and returns
the result.

Example: printf()
When you call printf() in C, it eventually leads to the write() system call. The program passes the
system call number and arguments. The CPU switches to kernel mode, the OS handles the
write to the screen, then returns to user mode.

Parameter Passing
System calls often need parameters (e.g., which file to open, how many bytes to read). Three common
methods:
• Registers: Pass parameters in CPU registers (simplest; limited by number of registers)
• Memory block/table: Store parameters in a block in memory; pass address of block in a register
• Stack: Push parameters onto the program stack; OS pops them
🎯 EXAM TIP
Know the 3 parameter-passing methods. Also be able to explain: What is a system call? Why is
an API preferred over direct system calls? Give examples: fork(), read(), write(), open().

2.4 Types of System Calls

Category Examples What They Do
Process Control fork(), exec(), exit(), wait() Create, terminate, load, and
wait for processes
File Management open(), read(), write(), close(), delete() Create, access, modify, and
delete files
Device Management request_device(), read(), write(), Request and release I/O
release() devices
Information Maintenance getpid(), alarm(), sleep(), time() Get/set system date/time,
process info
Communications pipe(), shmget(), socket(), send(), recv() Create communication
connections between
processes
 Protection chmod(), chown(), umask() Control access to resources

2.5 System Programs

System programs (also called system utilities) provide a convenient environment for program
development and execution. They sit between the OS kernel and applications.

Categories of System Programs

• File Management: create, copy, rename, delete, list files — e.g., ls, cp, rm, mv
• Status Information: system date, available memory, active users — e.g., date, who, df
• File Modification: text editors — e.g., vi, nano, gedit
• Programming Language Support: compilers, assemblers, interpreters — e.g., gcc
• Program Loading & Execution: loaders, linkers — e.g., ld
• Communications: email, SSH, FTP, browsers
• Background Services (Daemons): services that run in the background — e.g., print spoolers,
web servers

2.7 Operating-System Structure

How should the OS be organized internally? Several approaches exist, each with tradeoffs:

Simple Structure (MS-DOS Style)

The original MS-DOS was not well-separated into layers. Application programs could access basic I/O
routines directly. This made it vulnerable — a bug in any program could crash the whole system.

Layered Approach
The OS is divided into layers. Layer 0 is the hardware; the highest layer is the user interface. Each
layer only uses functions and services of layers below it. Easy to debug, but performance overhead
between layers.

Microkernel Structure
The kernel is stripped to its minimum. Only essential functions stay in the kernel (process scheduling,
basic IPC, memory management). Everything else (file system, device drivers, UI) is moved to user-
space services.
Feature Monolithic Kernel Microkernel
Size of kernel Large (everything in kernel) Small (minimal services)
Performance High (no IPC overhead for kernel Lower (services communicate via
services) IPC)
Reliability Bug in any module can crash Kernel is isolated; services crash
 kernel independently
Extensibility Harder to add/modify Easier to add new services
Example Linux, traditional Unix MINIX, Mach, QNX

2.7.4 Modules (Modular Approach)

Modern best practice: a monolithic kernel with loadable kernel modules (LKMs). The kernel has a core
set of components, and additional services are loaded dynamically as needed.
• Similar to layered approach, but modules can call each other directly (no strict layering)
• Similar to microkernel, but no message passing overhead since modules run in kernel space
• Example: Linux — device drivers, file systems loaded as modules (insmod/rmmod commands)
Linux Example
In Linux, you can load/unload a device driver without rebooting. When you plug in a USB drive,
the kernel dynamically loads the USB storage driver module. Type 'lsmod' to see loaded
modules.

🎯 EXAM TIP
Know all 4 OS structures: Simple/Monolithic, Layered, Microkernel, Modular. Be able to
compare Monolithic vs Microkernel — their pros/cons are classic exam questions.

Hybrid Systems
Modern OSes actually combine multiple approaches:
• Linux/Unix: Monolithic kernel + loadable modules
• macOS/iOS: Uses a Mach microkernel + BSD Unix layers
• Windows: Layered approach but monolithic in practice
UNIT 3: PROCESS MANAGEMENT (Chapters 3-7)
This is the largest and most important unit. It covers: Processes (Ch 3), Threads (Ch 4), Process
Synchronization (Ch 5), CPU Scheduling (Ch 6), and Deadlocks (Ch 7).

CHAPTER 3: PROCESSES

3.1 Process Concept

A process is a program in execution. It includes not just the program code (text section) but also:
• Text Section: The program code itself
• Program Counter (PC): Address of the next instruction to execute
• Stack: Temporary data — function parameters, local variables, return addresses
• Data Section: Global variables
• Heap: Memory dynamically allocated during runtime (malloc/new)

Program vs Process
A PROGRAM is passive — it's just a file of instructions sitting on disk (like a recipe). A
PROCESS is active — it's the program being executed, with its own memory space, CPU
register values, and resources. The same program can create multiple processes (e.g., two
copies of Chrome running).

3.1.2 Process States

As a process executes, it moves through different states:
State Description
New Process is being created
Ready Process is waiting to be assigned to the CPU (has all resources except CPU)
Running Instructions are being executed by the CPU (only 1 process per CPU core at a
time)
Waiting (Blocked) Process is waiting for an event (e.g., I/O completion, signal)
Terminated Process has finished execution

State transitions:
• New → Ready: process admitted to ready queue
• Ready → Running: scheduler dispatches process
• Running → Waiting: process requests I/O or waits for event
• Waiting → Ready: I/O completes or event occurs
• Running → Ready: process preempted (time quantum expired)
• Running → Terminated: process exits
 🎯 EXAM TIP
Draw the process state diagram from memory. Know all 5 states and the transitions between
them. This is one of the most commonly drawn diagrams in OS exams.

3.1.3 Process Control Block (PCB)

Each process is represented in the OS by a PCB (also called Task Control Block). The PCB contains
all information about the process:
• Process State: new, ready, running, waiting, terminated
• Program Counter: address of next instruction
• CPU Registers: all registers (accumulators, index registers, stack pointers, etc.) — saved during
context switch
• CPU Scheduling Information: priority, pointers to scheduling queues
• Memory Management Information: base/limit registers, page tables
• Accounting Information: CPU time used, time limits, process ID
• I/O Status Information: list of open files, I/O devices allocated

Context Switch
When the CPU switches from Process A to Process B, it saves A's PCB (CPU registers, PC,
etc.) and loads B's PCB. This is called a context switch. The time to do this is overhead — no
useful work is done. Faster CPUs have multiple register sets to minimize this overhead.

3.2 Process Scheduling

3.2.1 Scheduling Queues
• Job Queue: ALL processes in the system (including those on disk waiting to be loaded)
• Ready Queue: Processes in memory, ready to execute, waiting for CPU — usually a linked list
of PCBs
• Wait Queue (Device Queue): Processes waiting for a specific I/O device

3.2.2 Schedulers
Scheduler Also Called Frequency What It Does
Long-Term Scheduler Job Scheduler Infrequent (seconds to Selects which jobs from job
minutes) pool to load into memory
(controls degree of
multiprogramming)
Short-Term CPU Scheduler Very frequent Selects which ready process
Scheduler (milliseconds) gets the CPU next
Medium-Term Swapper Moderate Removes processes from
Scheduler memory to disk (swapping)
to reduce degree of
multiprogramming
Processes can be classified by their burst pattern:
• I/O-bound process: spends more time doing I/O than computation (many short CPU bursts)
• CPU-bound process: spends more time doing computation (long CPU bursts, infrequent I/O)
Long-Term Scheduler Importance
The long-term scheduler controls the mix of CPU-bound and I/O-bound processes in memory. A
good mix keeps both CPU and I/O devices busy. If all processes are CPU-bound, the ready
queue fills up and I/O devices sit idle.

3.2.3 Context Switch

When the CPU switches to another process, the system must save the state of the old process and
restore the state of the new process. This state is stored in the PCB.
• Context switch time is pure overhead (no useful computation during the switch)
• Time ranges from microseconds to milliseconds
• Hardware support (multiple register sets) can speed up context switching

3.3 Operations on Processes

3.3.1 Process Creation (fork())
A process (parent) can create new processes (children) using system calls. This creates a process
tree.
• In UNIX/Linux: fork() creates a child process that is a copy of the parent
• After fork(), the child can execute a new program using exec()
• The child process gets a unique PID (Process ID)

pid = fork(); // Create child process if (pid == 0) { // Child

process runs here execlp("/bin/ls", "ls", NULL); // Replace child with
ls command } else { // Parent process runs here wait(NULL);
// Wait for child to finish }

Resource Sharing Options (Parent vs Child)

• Parent and child share all resources
• Child shares subset of parent's resources
• Child shares no resources with parent

Execution Options
• Parent and child execute concurrently
• Parent waits until child terminates (wait() call)
3.3.2 Process Termination
• Normal termination: process calls exit(), returning a status value to parent via wait()
• Parent can terminate child: using kill() or TerminateProcess() in Windows
• Reasons parent might terminate child: child exceeded resource limits, task no longer needed,
parent itself is terminating

Zombie and Orphan Processes

Term Definition What Happens
Zombie Process Child has terminated but parent hasn't Entry remains in process
called wait() yet table; wastes resources.
Cleaned up when parent calls
wait().
Orphan Process Parent terminated without waiting for In Unix, orphans are adopted
child by init (PID 1) which calls
wait() for them.

🎯 EXAM TIP
Know fork() and exec() and what they do. fork() duplicates the process. exec() replaces the
process image with a new program. Zombie = terminated child not yet waited for. Orphan = child
whose parent died.

CHAPTER 4: THREADS

4.1 Overview — What is a Thread?

A thread is a basic unit of CPU utilization. A single process can have multiple threads, each sharing the
process's code, data, and OS resources, but each with its own:
• Thread ID
• Program Counter (PC)
• Register set
• Stack

A traditional (heavyweight) process has a single thread of control. A multithreaded process has multiple
threads running within the same process.

Example: Web Server

A single-threaded web server handles one request at a time — very slow. A multithreaded
server creates a new thread for each incoming request. Multiple clients are served
simultaneously, sharing the server's code and resources efficiently.
Benefits of Multithreading
Benefit Explanation
Responsiveness One thread can respond to UI while another does heavy computation
Resource Sharing Threads share process memory and resources — more efficient than
separate processes
Economy Creating a thread is much faster than creating a process (less
overhead)
Scalability Threads can run truly in parallel on multi-core CPUs

4.2 Multicore Programming

Multicore systems have multiple CPU cores on a single chip. True parallelism is possible — multiple
threads run simultaneously, one per core.
• Concurrency: Multiple tasks make progress (can be single-core with time-slicing)
• Parallelism: Multiple tasks run at the SAME TIME (requires multiple cores)

Challenges in Multicore Programming

• Dividing activities: Break task into parallel sub-tasks
• Balance: Ensure all cores do equal work
• Data splitting: Divide data among cores
• Data dependency: If task A depends on task B's output, they can't fully parallelize
• Testing & debugging: Many more execution paths to test
🎯 EXAM TIP
Distinguish between concurrency and parallelism — a common exam question. Concurrency =
one at a time but switching fast (illusion). Parallelism = truly simultaneous (requires multiple
cores).

4.3 Multithreading Models

Threads can exist at two levels: user threads (managed by user-space library) and kernel threads
(managed by the OS). The relationship between them defines the model:
Model Mapping Pros Cons Example
Many-to-One Many user threads Efficient; no kernel Entire process Green
→ 1 kernel thread involvement blocks if one thread threads
makes a blocking (early
system call; no true Java)
parallelism
One-to-One 1 user thread → 1 True parallelism; one Creating many Linux,
kernel thread thread blocks, others kernel threads is Windows
continue expensive
Many-to-Many Many user threads Best of both worlds; no Complex to Solaris
→ smaller/equal limit on user threads implement (older)
kernel threads
4.4 Thread Libraries
A thread library provides programmers with an API for creating and managing threads.
• POSIX Pthreads: Standard C thread library for Unix/Linux. Most common in exams.
• Java Threads: Built into Java language; all Java programs are multithreaded
• Win32 Threads: For Windows applications

4.4.1 Pthreads (POSIX Threads)

#include <pthread.h> void *runner(void *param) { // Thread's work here
int i = *((int *)param); printf("Sum up to %d\n", i); pthread_exit(0);
// Thread exits } int main() { pthread_t tid; // Thread ID
pthread_attr_t attr; // Thread attributes int n = 5;
pthread_attr_init(&attr); // Set default attributes
pthread_create(&tid, &attr, runner, &n); // Create thread
pthread_join(tid, NULL); // Wait for thread to finish
return 0; }

Key Pthreads functions:

• pthread_create(): Create a new thread
• pthread_join(): Wait for a thread to finish (like wait() for processes)
• pthread_exit(): Terminate the calling thread
• pthread_mutex_lock() / pthread_mutex_unlock(): Mutual exclusion

🎯 EXAM TIP
Be able to write/read Pthreads code. Practical exam questions often ask you to write a Pthreads
program for computing sum of n numbers. Know pthread_create(), pthread_join(),
pthread_exit().

CHAPTER 5: PROCESS SYNCHRONIZATION

5.1 Background — The Race Condition Problem

When multiple processes access and manipulate shared data concurrently, the outcome depends on
the order of access. This is a race condition — and it leads to incorrect results.

Classic Example: Producer-Consumer

A producer process adds items to a shared buffer; a consumer removes them. They share a
variable 'count'. If both execute 'count++' and 'count--' concurrently without synchronization, the
final value of count may be incorrect — a race condition.

The code count++ actually compiles to THREE machine instructions:

 register = count // Load count into register register = register + 1 //
Increment count = register // Store back // If two processes
interleave between these instructions: RACE CONDITION!

5.2 The Critical-Section Problem

The critical section is the part of a program where a process accesses shared resources. The problem:
ensure that when one process is in its critical section, no other process can enter its critical section.

A solution to the critical-section problem must satisfy THREE conditions:

• 1. Mutual Exclusion: Only one process can be in its critical section at a time
• 2. Progress: If no process is in critical section and some want to enter, only those not in their
remainder section can decide who enters next — and this decision cannot be postponed
indefinitely
• 3. Bounded Waiting: There must be a limit on how many times other processes can enter their
critical sections after a process has requested entry — prevents starvation
🎯 EXAM TIP
The 3 conditions for a correct critical-section solution are ALWAYS asked: Mutual Exclusion,
Progress, Bounded Waiting. Memorize these!

5.3 Peterson's Solution

Peterson's Solution is a classic software-based solution for two processes (P0 and P1) using two
shared variables:
• int turn: whose turn it is to enter the critical section
• boolean flag[2]: whether each process wants to enter the critical section

// For Process Pi (the other is Pj, where j = 1 - i): flag[i] = true; //

I want to enter turn = j; // But I'll give priority to the other
while (flag[j] && turn == j); // Wait if other wants to enter AND it's their
turn /* Critical Section */ flag[i] = false; // I'm done /*
Remainder Section */

Peterson's solution satisfies all three conditions: mutual exclusion, progress, and bounded waiting.
However, it assumes atomic load/store — modern architectures may reorder instructions, making
Peterson's unreliable without memory barriers.

5.3.4 Mutex Locks

A mutex lock (mutual exclusion lock) is a simpler, practical synchronization tool provided by the OS. A
process must acquire the lock before entering the critical section and release it when done.
acquire(); // Acquire the lock (blocks if already locked) /*
Critical Section */ release(); // Release the lock
 • acquire() sets available = false (lock is now held)
• release() sets available = true (lock is released)
• If lock is not available, process SPINS (busy-waits) — called a spinlock
• Spinlocks are efficient for very short critical sections (no context switch needed)

Semaphores
A semaphore S is an integer variable that is accessed only through two atomic operations:
Operation Effect Name Variations
wait(S) / P(S) Decrements S. If S <= 0, the process blocks wait(), P(), down()
(goes to waiting queue)
signal(S) / V(S) Increments S. If processes are waiting, wake signal(), V(), up()
one up

• Binary Semaphore: S can be 0 or 1 (works like a mutex lock)

• Counting Semaphore: S can range over an unrestricted domain — useful for managing N
identical resources

// Counting Semaphore Example — 3 identical printers: semaphore printers = 3;

// 3 available // Using a printer: wait(printers); // S becomes 2;
if S was 0, block /* Use printer */ signal(printers); // S becomes
3 again; wake a blocked process

🎯 EXAM TIP
Know the difference between mutex lock and semaphore. Mutex = binary lock for mutual
exclusion. Semaphore = more general, can count resources. Know wait() and signal()
operations and what they do to the counter.

CHAPTER 6: CPU SCHEDULING

6.1 Basic Concepts

CPU scheduling is the basis of multiprogrammed operating systems. The CPU scheduler selects from
among processes in the ready queue and allocates the CPU to one of them.

CPU-I/O Burst Cycle

Process execution alternates between CPU bursts (computation) and I/O bursts (waiting for I/O). The
short-term scheduler fires every time a CPU burst ends.
Preemptive vs Non-Preemptive Scheduling
Type Description When Scheduling Happens
Non-Preemptive Once a process gets the CPU, it keeps it until Process terminates; Process
it voluntarily releases it (terminates or I/O) requests I/O; Process switches
from running to waiting
Preemptive OS can forcibly take CPU away from a Above 3 situations PLUS: time
running process quantum expires; higher-
priority process arrives

6.2 Scheduling Criteria

Criterion Goal Maximize or Minimize?
CPU Utilization Keep CPU busy as much as possible Maximize (ideally 40-
90%)
Throughput Number of processes completed per unit Maximize
time
Turnaround Time Total time from submission to completion Minimize
Waiting Time Time spent in the ready queue Minimize
Response Time Time from request submission to first Minimize
response

Key Formulas
Turnaround Time = Completion Time - Arrival Time Waiting Time = Turnaround Time - Burst
Time Response Time = Time of First Response - Arrival Time Average Waiting Time = Sum of
all Waiting Times / Number of Processes

6.3 Scheduling Algorithms

6.3.1 First-Come, First-Served (FCFS)

The simplest scheduling algorithm. The process that requests the CPU first gets it first. Implemented
using a FIFO queue. NON-PREEMPTIVE.

FCFS Example
Processes: P1 (Burst=24ms), P2 (Burst=3ms), P3 (Burst=3ms), all arrive at time 0 Gantt Chart: |
P1 (0-24) | P2 (24-27) | P3 (27-30) | Waiting Times: P1=0, P2=24, P3=27 → Average =
(0+24+27)/3 = 17ms If order was P2, P3, P1: Gantt Chart: | P2 (0-3) | P3 (3-6) | P1 (6-30) |
Waiting Times: P2=0, P3=3, P1=6 → Average = (0+3+6)/3 = 3ms

• Convoy effect: short processes wait behind one long process — leads to very high average wait
times
 • Simple to implement but poor performance in most scenarios

6.3.2 Shortest-Job-First (SJF)

Assigns the CPU to the process with the SMALLEST next CPU burst. OPTIMAL algorithm — gives
minimum average waiting time. Can be preemptive or non-preemptive.
• Non-Preemptive SJF: Once CPU is assigned, process keeps it until burst ends
• Preemptive SJF (SRTF): If a new process arrives with shorter burst than remaining burst of
current, preempt current process — also called Shortest-Remaining-Time-First (SRTF)

SJF Example (Non-Preemptive)

Processes: P1(Burst=6), P2(Burst=8), P3(Burst=7), P4(Burst=3), all arrive at t=0 Order: P4(3),
P1(6), P3(7), P2(8) Gantt: |P4(0-3)|P1(3-9)|P3(9-16)|P2(16-24)| Waiting: P4=0, P1=3, P3=9,
P2=16 → Average = 7ms With FCFS: Average would be much higher

• Main problem: Cannot know the length of the next CPU burst in advance for short-term
scheduling
• Solution: Estimate burst length using exponential averaging of past bursts

6.3.3 Priority Scheduling

Each process is assigned a priority number. The CPU is given to the highest-priority process. Can be
preemptive or non-preemptive.
• Lower number = Higher priority (typically)
• SJF is a special case: priority = inverse of CPU burst length
• Main problem: STARVATION — low-priority processes may never execute
• Solution: Aging — gradually increase the priority of processes that wait for a long time

🎯 EXAM TIP
Three most important algorithms for exam: FCFS (simple, convoy effect), SJF (optimal average
wait, but needs future knowledge), Round Robin (for time-sharing). Always draw Gantt charts
and calculate average waiting time!

6.3.4 Round Robin (RR)

Designed specifically for time-sharing systems. Each process gets a small unit of CPU time called a
TIME QUANTUM (or time slice), typically 10-100 milliseconds. After its quantum expires, the process is
preempted and added to the end of the ready queue.

Round Robin Example

Processes: P1(Burst=24), P2(Burst=3), P3(Burst=3), Time Quantum=4ms Gantt: |P1(0-4)|P2(4-
7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)| Waiting: P1=(10-4)=6, P2=(4-0)=4,
P3=(7-0)=7 → Average = (6+4+7)/3 = 5.66ms Note: P2 and P3 finish quickly because their
 bursts < quantum

• Quantum too small: Too many context switches — overhead dominates

• Quantum too large: Degenerates to FCFS
• Rule of thumb: 80% of CPU bursts should be shorter than the time quantum

CHAPTER 7: DEADLOCKS

7.1 System Model

A deadlock is a situation where a set of blocked processes each holds a resource and is waiting for a
resource held by another process in the set — a circular wait.

Classic Deadlock Example

Traffic deadlock at a 4-way intersection: Car A occupies lane 1, wants lane 2 Car B occupies
lane 2, wants lane 3 Car C occupies lane 3, wants lane 4 Car D occupies lane 4, wants lane 1
No car can move — deadlock!

Resources can be:

• Preemptable: Can be taken away without harm (e.g., CPU, memory)
• Non-preemptable: Cannot be taken away without causing failure (e.g., printer in mid-print,
mutex lock)

7.2 Deadlock Characterization — Four Necessary Conditions

Deadlock can arise ONLY IF all four conditions hold simultaneously:
Condition Description
1. Mutual Exclusion At least one resource must be held in non-shareable mode (only one
process at a time)
2. Hold and Wait A process holds at least one resource and is waiting for additional
resources held by other processes
3. No Preemption Resources cannot be preempted; they must be released voluntarily by
the holding process
4. Circular Wait A set of processes {P0, P1, ..., Pn} such that P0 waits for P1, P1 waits
for P2, ..., Pn waits for P0

🎯 EXAM TIP
The FOUR conditions for deadlock are the most important thing to know in this chapter. They
must ALL hold simultaneously. Eliminating ANY ONE condition prevents deadlock. Memorize:
Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait.
Resource Allocation Graph (RAG)
Deadlock can be described with a Resource Allocation Graph. Nodes: processes (circles) and
resources (rectangles). Edges:
• Request Edge (P → R): Process P is requesting resource R
• Assignment Edge (R → P): Resource R is assigned to process P

• If the RAG contains NO CYCLE → No deadlock

• If the RAG contains a CYCLE → possible deadlock (definite deadlock if each resource type has
exactly one instance)

7.3 Methods for Handling Deadlocks

Approach Method Description
Prevention 7.4 Ensure at least one of the 4 conditions never holds
Avoidance 7.5 OS makes smart decisions to ensure system never enters unsafe
state (Banker's Algorithm)
Detection & 7.6, 7.7 Allow deadlocks, detect them when they occur, and recover
Recovery
Ignore (Ostrich) — Ignore the problem. Used by most OSes including Windows/Linux —
deadlocks are rare enough to restart the system

Deadlock Prevention (Eliminating Conditions)

• Eliminate Mutual Exclusion: Make resources shareable (not always possible — printers must be
exclusive)
• Eliminate Hold and Wait: Process must request ALL resources before starting, OR release all
held resources before requesting new ones. Problem: low resource utilization; starvation.
• Allow Preemption: If a process holding resources requests another that can't be immediately
allocated, preempt its held resources. Works for memory/CPU, not for printers/files.
• Eliminate Circular Wait: Impose a total ordering on all resource types. Each process can only
request resources in increasing order. If process holds Ri, it can only request Rj where j > i.

🎯 EXAM TIP
Know how to prevent deadlock by eliminating each of the 4 conditions. Also understand the
Banker's Algorithm concept (safe state = there exists a sequence in which all processes can
finish).
UNIT 4: MEMORY MANAGEMENT (Chapters 8 & 9)
Memory management is how the OS controls the allocation and use of main memory. Sections: 8.1.3,
8.2, 8.3, 8.4, 8.5-8.5.2, 9.2, 9.4-9.4.4.

CHAPTER 8: MAIN MEMORY

8.1 Background
The CPU can only directly access main memory (RAM) and CPU registers. Instructions and data must
be in memory for the CPU to use them. Disk access requires OS intervention and is 100s-1000s of
times slower.

8.1.3 Logical vs Physical Address Space

Term Definition Who Generates It
Logical Address Address generated by the CPU (also called CPU / running
virtual address) program
Physical Address Address seen by the memory unit (actual Memory Management
RAM location) Unit (MMU)

The Memory Management Unit (MMU) is hardware that maps logical addresses to physical addresses
at runtime.

Why Logical Addresses?

If programs used physical addresses directly, they'd need to be loaded at fixed memory
locations — very inflexible. With logical addresses, a program always thinks it starts at address
0, while the OS/MMU handles the actual physical placement.

8.2 Swapping
A process can be swapped out of memory to backing store (disk) and later swapped back in. This
allows the OS to run more processes than can fit in memory at once.
• Backing store: Fast disk with enough space for all memory images of all users
• Roll out, roll in: A form of swapping for priority-based scheduling
• Biggest cost in swapping: transfer time (proportional to amount of memory swapped)

Swapping in Mobile Systems

Mobile systems (iOS, Android) generally don't support swapping because flash memory has
limited write cycles and no device is large enough. Instead, apps are terminated when memory
is low, and data is paged out in iOS.
8.3 Contiguous Memory Allocation
Each process occupies a single contiguous section of memory. The OS occupies low memory; user
processes occupy high memory.

Memory Partitioning
Method Description Problem
Fixed Partitioning Memory divided into fixed-size partitions; Internal fragmentation:
one process per partition allocated partition may be
larger than needed
Variable Partitioning OS keeps table of free/used memory External fragmentation: free
holes. Allocates exact size needed. holes scattered throughout
memory; total free may be
enough but no single hole is
large enough

Allocation Strategies (Variable Partitioning)

• First-Fit: Allocate the FIRST hole that is big enough. Fast.
• Best-Fit: Allocate the SMALLEST hole that is big enough. Minimizes wasted space in that hole,
but creates many tiny unusable holes.
• Worst-Fit: Allocate the LARGEST hole. Produces the largest leftover hole (which might be
useful).

Performance
First-Fit and Best-Fit are better than Worst-Fit for decreasing time and storage utilization. First-
Fit is generally fastest.

Fragmentation
Type Description Solution
External Fragmentation Total free memory is enough, but it's Compaction: shuffle memory
scattered in small non-contiguous contents to consolidate free
holes space into one large block
(requires relocation to be
dynamic)
Internal Fragmentation Allocated memory slightly larger than Use smaller partitions (but
requested; unused memory is inside increases fragmentation
the partition overhead)

8.4 Segmentation
Segmentation is a memory management scheme that supports the programmer's view of memory. A
program is a collection of segments — each segment is a named logical unit such as the main
program, procedure, stack, data, etc.
 • Each segment has a name (or number) and a length
• User specifies addresses by: (segment-number, offset)
• Segment table: each entry has base (physical starting address) and limit (length of segment)

Segment Table Entry: | Base Address | Limit | Logical Address: (segment#,

offset) Check: if offset >= limit → segment fault (address error) Physical
Address = base + offset

• Segmentation supports sharing (e.g., shared code segment between processes)

• Segmentation can cause external fragmentation (segments are different sizes)

8.5 Paging
Paging is the most common memory management scheme. It eliminates external fragmentation by
breaking memory into fixed-size blocks.
• Physical memory is divided into fixed-size frames
• Logical memory (process) is divided into pages of the same size as frames
• OS maintains a PAGE TABLE for each process that maps page numbers to frame numbers

Key Insight
A process's pages can be scattered anywhere in physical memory — they don't need to be
contiguous! The page table keeps track of where each page is. This eliminates external
fragmentation completely.

Address Translation in Paging

Logical address = (page number p, page offset d)
• Page number p: index into page table to find the frame number f
• Page offset d: combined with frame number to get physical address
Logical Address: | Page Number (p) | Page Offset (d) | Page Table: page p →
frame f Physical Address: | Frame Number (f) | Offset (d) |

Page Size and Address Bits

If logical address space = 2^m and page size = 2^n bytes, then:
• Page number needs m-n bits
• Page offset needs n bits
• Typical page sizes: 4KB to 1MB (4KB = 2^12, so offset = 12 bits)

Example
32-bit logical address space, 4KB (2^12) page size: - Offset bits = 12 - Page number bits = 32 -
12 = 20 bits - Max pages per process = 2^20 = 1,048,576 pages - Physical memory with 50 free
 frames: OS tracks these in a frame table

8.5.1 Hardware Support — TLB

Looking up the page table in memory for EVERY memory access would be very slow (2 memory
accesses per instruction). Solution: Translation Look-aside Buffer (TLB) — a fast hardware cache for
page table entries.
Scenario Steps Performance
TLB Hit Check TLB → Found → Use frame Fast: ~1 extra cycle
number directly
TLB Miss Check TLB → Not Found → Go to page Slow: 2 memory accesses
table in memory → Update TLB

• Hit Ratio (α): Percentage of lookups found in TLB. Higher is better.

• Effective Access Time (EAT) = α × (TLB time + memory) + (1-α) × (TLB time + 2×memory)

8.5.2 Protection
Paging provides memory protection through protection bits associated with each page table entry:
• Valid-Invalid bit: 'valid' means page is in the process's logical address space and is legal to
access; 'invalid' means page is not in the address space
• Read/Write bits: control whether page is read-only or read-write
🎯 EXAM TIP
Paging is the most important memory management topic. Key points: fixed-size pages/frames,
page table maps logical to physical, eliminates external fragmentation but causes internal
fragmentation, TLB speeds up translation. Know address translation formula.

CHAPTER 9: VIRTUAL MEMORY

9.2 Demand Paging

Virtual memory allows execution of processes that are NOT completely in memory. Pages are loaded
into memory ONLY when they are needed (demanded) — not all at once. This allows more processes
to run than physical memory can hold.

• Lazy swapper: Never swap a page into memory unless it will be needed
• Pager: Swaps individual pages (not entire processes) — more efficient than swapper

Page Fault
When a process accesses a page that is NOT in memory (its valid-invalid bit is 'invalid'), a page fault
occurs:
 1. CPU generates a trap (page fault interrupt)
2. OS checks if the reference was valid (legal address) — if invalid, abort the process
3. Find a free frame in physical memory
4. Load the needed page from disk into the frame
5. Update the page table (set the frame number, set valid bit)
6. Restart the interrupted instruction

Pure Demand Paging

Start a process with NO pages in memory. On first instruction execution → page fault. Load that
page. Continue until all needed pages are loaded. This is the extreme case of demand paging
— very slow at startup but minimal initial memory use.

Effective Access Time with Page Faults

Let p = page fault rate (0 ≤ p ≤ 1). p = 0 means no page faults; p = 1 means every access causes a
fault.
EAT = (1-p) × memory_access_time + p × page_fault_time Page fault time =
service page fault interrupt + read page from disk + restart process Disk
access ≈ 8ms = 8,000,000ns Memory access ≈ 200ns For p = 0.001 (1 fault per
1000 accesses): EAT = 0.999 × 200 + 0.001 × 8,000,000 = 8,199.8ns ≈ 40x slower
than no faults!

9.4 Page Replacement

When a page fault occurs and there are NO free frames, the OS must replace (evict) an existing page
— page replacement. The goal: minimize the number of page faults.

Page Replacement Algorithms

9.4.1 FIFO (First-In, First-Out)
Replace the page that has been in memory the LONGEST. Simple to implement — just track the order
pages were loaded.

FIFO Example (3 frames)

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1 7 → [7] fault | 0 → [7,0] fault | 1 → [7,0,1]
fault 2 → Replace 7 → [2,0,1] fault | 0 → [2,0,1] hit 3 → Replace 0 → [2,3,1] fault | ... Total page
faults = 12

• Belady's Anomaly: For FIFO, increasing the number of frames can INCREASE page faults!
(counterintuitive)

9.4.2 Optimal Algorithm (OPT)

Replace the page that will NOT be used for the LONGEST time in the future. Provably optimal — gives
the minimum number of page faults.
 • Problem: Requires knowing the future reference string — impossible in practice
• Used as a benchmark to compare other algorithms

9.4.3 LRU (Least Recently Used)

Replace the page that has NOT been used for the LONGEST TIME in the past. Uses past behavior to
predict future. Good approximation of OPT.
• Counter implementation: Each page has a timestamp of last use; replace the one with the oldest
timestamp
• Stack implementation: Keep a stack of page numbers. On each access, move page to top.
Bottom of stack = LRU page.

9.4.4 LRU-Approximation Algorithms

True LRU requires hardware support (updating counters/timestamps on every memory access). Most
hardware provides a reference bit instead:
• Reference bit: Set to 1 when page is accessed; OS periodically clears all bits to 0
• Additional Reference Bits: Keep an 8-bit shift register per page. Each time period, shift right and
add current reference bit. Smallest number = LRU.
• Second Chance (Clock) Algorithm: Circular queue. If page's reference bit is 1, give it a second
chance (clear bit, advance). If bit is 0, replace it. Acts like a rotating clock hand.

🎯 EXAM TIP
For page replacement, know FIFO (simple, Belady's anomaly), OPT (theoretical best), LRU
(practical best, approximates OPT), and Second-Chance (practical LRU approximation). Be able
to solve page replacement problems by tracing through a reference string!

Algorithm Basis for Replacement Belady's Anomaly? Practical?

FIFO Oldest loaded page Yes (can suffer Yes (simple)
from it)
OPT Longest time until future use No No (needs future)
LRU Least recently used in the past No Yes (with
hardware)
Second Chance Modified FIFO with reference No Yes
bit (approximation)
UNIT 5: FILE SYSTEM (Chapters 11 & 12 in 9th Ed.)
Note: The syllabus references 'Chapter 10' and 'Chapter 12' using the 8th edition numbering. In the 9th
edition Silberschatz textbook, these correspond to Chapter 11 (File-System Interface) and Chapter 12
(File-System Implementation).

FILE-SYSTEM INTERFACE (Syllabus Ch. 10 = 9th Ed. Ch. 11)

10.1 File Concept

A file is a named collection of related information stored on secondary storage (disk). From the user's
perspective, a file is the smallest allotment of logical secondary storage.

File Attributes
Attribute Description
Name Symbolic name — the only human-readable attribute
Identifier Unique tag (inode number) within the file system
Type Needed for systems that support different types (text, binary,
executable)
Location Pointer to device and disk block where file starts
Size Current size in bytes, words, or blocks
Protection Access control — who can read, write, execute
Time, Date, User ID Creation time, last modification time, owner

10.1.1 File Operations

• Create: Allocate space, make directory entry
• Write: Write data at the write pointer position; advance write pointer
• Read: Read data at the read pointer; advance read pointer
• Reposition (Seek): Move file pointer to a given position (random access)
• Delete: Release file space; erase directory entry
• Truncate: Keep attributes but erase file contents, reset length to 0

10.1.2 File Types

Operating systems handle file types in different ways:
OS Approach Example
UNIX/Linux Magic number at start of file indicates type; file .sh, .c, .py — but not
extension is just a convention enforced
Windows File extension determines type and associated .exe, .docx, .pdf, .mp3
 application
macOS Creator code and type code in file metadata System stores which app
created it

10.2 Access Methods

Method Description Use Case
Sequential Access Data read in order, one record after another. Tape drives, log files,
Advance pointer after each read. Can rewind. streaming
Simplest and most common.
Direct Access Arbitrary record can be read or written directly Databases, large files with
(Random) using block numbers. File seen as a numbered random queries
sequence of blocks.
Index Sequential Keep an index file. Search index for block Large sequential files with
number, then direct-access that block. random access (VSAM)

🎯 EXAM TIP
Know the three access methods: Sequential (most common, tape-like), Direct (random access
by block number), and Index Sequential (index points to blocks). Databases use direct/index
access.

10.3 Directory Structure

A directory is a collection of nodes containing information about all files. It maps file names to their
locations.

Directory Operations
• Search for a file by name
• Create a file (add entry to directory)
• Delete a file (remove entry)
• List a directory (enumerate entries)
• Rename a file
• Traverse the file system

Directory Organization Schemes

Structure Description Pros Cons
Single-Level All files in one directory; all users Simple Name collision if two
share same namespace files have same
name; poor
organization
Two-Level Separate directory per user Isolates users; Sharing between
(User File Directory); Master File efficient search users is difficult; no
Directory on top grouping within user
 directory
Tree-Structured Generalized to arbitrary depth. Natural grouping; Deleting directory
Current directory (working efficient search; with files is complex
directory) concept. Paths: unlimited depth
absolute (from root) and relative.
Acyclic-Graph Allows sharing — same Flexible sharing Dangling pointers if
file/directory can appear in between users original deleted;
multiple directories via links. Two cycles possible
types of links: hard links and
symbolic links.
General Graph Allows cycles in directory Maximum flexibility Garbage collection
structure needed; traversal
risks infinite loops

10.3.6 Protection
The owner of a file controls what can be done with it and by whom. Two mechanisms:

UNIX/Linux: rwx Permission Bits

Each file has a 9-bit protection code: 3 groups × 3 permissions
Format: [type][owner][group][others] Example: -rwxr-xr-- - = regular file (d
for directory) rwx = owner: read, write, execute r-x = group: read, no
write, execute r-- = others: read only chmod 755 file → owner: rwx (7),
group: r-x (5), others: r-x (5) chmod 644 file → owner: rw- (6), group: r--
(4), others: r-- (4)

• r (read): can open and read the file

• w (write): can modify the file
• x (execute): can run the file as a program; for directories: can enter (cd)

Access Control Lists (ACLs)

More fine-grained than rwx. Each file has a list of (user, permission) pairs. Example: file1:
[(Alice, rw), (Bob, r), (Carol, rwx)]. Allows per-user control but is more complex to manage.
Supported in Linux via getfacl/setfacl.

🎯 EXAM TIP
Know UNIX permissions: rwx for owner, group, others. Be able to interpret permissions like
'drwxr-xr-x' and convert octal (755, 644) to permission bits. chmod, chown, chgrp commands are
in the practicals.

FILE-SYSTEM IMPLEMENTATION (Syllabus Ch. 12)

12.1 File-System Structure
The file system is typically organized in multiple layers:
Layer Function
Application Programs User programs that use files
Logical File System Manages directory structure; protects files; uses FCBs
File-Organization Module Knows about files, blocks, free space; manages logical-to-physical
block translation
Basic File System Issues generic commands to device driver to read/write blocks
I/O Control Device drivers and interrupt handlers; translates commands to
hardware signals
Devices Physical disk/storage hardware

File Control Block (FCB / inode)

A File Control Block (FCB) contains all information about a file:
• File permissions, file dates, file owner, file size
• Data blocks pointers (where the file's data blocks are on disk)
• In UNIX/Linux, the FCB is called an INODE (index node)

On-Disk and In-Memory Structures

Structure Location Purpose
Boot Control Block Volume's first block Contains info to boot OS from this volume
Volume Control Block Per volume Volume details: total blocks, free blocks,
(superblock) block size
Directory Structure Per file system File names and associated inode/FCB
numbers
FCB (inode) Per file File details: permissions, size, data block
pointers
Mount Table In memory Mounted file systems information
Open-File Table In memory, system- FCBs of all currently open files
wide
Per-Process Open File Table In memory, per process Pointer into system-wide table; per-
process data

12.4 Allocation Methods

How should disk blocks be allocated to files? Three main methods:
12.4.1 Contiguous Allocation
Each file occupies a contiguous set of blocks on disk. Directory entry stores the starting block and the
length.
• Advantages: Simple; excellent read performance (sequential and random access both fast);
minimal seeks
• Disadvantages: External fragmentation (holes between files); file size must be known at creation
time; difficult to extend files

12.4.2 Linked Allocation

Each file is a linked list of disk blocks, which may be scattered anywhere. Directory entry has pointer to
first and last block. Each block has a pointer to the next block.
• Advantages: No external fragmentation; file can grow as long as free blocks exist
• Disadvantages: Random access is very slow (must follow links); pointers waste space; pointer
corruption causes data loss

FAT (File Allocation Table)

An important variation of linked allocation. All the pointers are stored together in a table (FAT) at
the beginning of the disk, rather than inside each block. The FAT can be cached in memory for
faster access. Used by MS-DOS and many USB drives.

12.4.3 Indexed Allocation

All pointers for each file are collected into one block — the INDEX BLOCK (i-node in Unix). Directory
entry contains the index block pointer.
• Advantages: Efficient random access (read index block, then go directly to desired block); no
external fragmentation
• Disadvantages: For very small files, index block wastes space; for very large files, one index
block may not be enough

Handling Large Files with Indexed Allocation

Scheme Description Max File Size
Linked Scheme Index blocks linked together in a chain Large but slow for long
chains
Multilevel Index Outer index points to inner index blocks, Very large (two-level:
which point to data blocks block_size^2 × block_size)
Combined (Unix inode) Direct pointers + single indirect + double Extremely large (terabytes)
indirect + triple indirect blocks

Unix Inode Structure

Unix inodes typically have: - 12 direct block pointers (small files: fast direct access) - 1 single
indirect pointer (points to block of pointers) - 1 double indirect pointer (pointer → block of
pointers → blocks) - 1 triple indirect pointer (three levels of indirection) With 4KB blocks and 4-
byte pointers, a file can be huge.

🎯 EXAM TIP
The three allocation methods are critical: Contiguous (simple, fast, fragmentation), Linked (no
fragmentation, slow random access, FAT variation), Indexed (fast random access, i-nodes in
Unix). Know advantages and disadvantages of each!

Method Sequential Access Random Access External Space

Fragmentation Efficiency
Contiguous Excellent Good Yes (major problem) High
Linked Good Poor (O(n)) No Low
(pointer
overhead)
Indexed Good Good (O(1)) No Moderate
(index
overhead)
QUICK REVISION — KEY DEFINITIONS & FORMULAS

Must-Know Definitions
Term One-Line Definition
Operating System Program that manages computer hardware and acts as intermediary
between users and hardware
Kernel The one program always running on the computer — the core of the
OS
Process A program in execution — includes code, stack, heap, data, and
execution state
Thread Basic unit of CPU utilization within a process — lightweight process
PCB Process Control Block — OS data structure containing all info about
a process
Context Switch Saving state of current process and loading state of next process
System Call Interface between user programs and OS services — switches CPU
to kernel mode
Multiprogramming Keeping multiple programs in memory to maximize CPU utilization
Time-Sharing Rapidly switching CPU among users for interactive response
Deadlock Each process in a set waits for a resource held by another process in
the set
Page Fault Accessing a page that is not currently in physical memory
Thrashing Excessive paging — process spends more time paging than
executing
Semaphore Integer variable for synchronization, accessed via wait() and signal()
only
Critical Section Code segment where shared resources are accessed
Fragmentation Wasted memory — external (free space scattered) or internal
(allocated but unused)
TLB Translation Look-aside Buffer — hardware cache for page table
entries
Inode Unix File Control Block — stores file metadata and data block
pointers

Critical Formulas & Calculations

Formula Equation
Turnaround Time = Completion Time - Arrival Time
Waiting Time = Turnaround Time - Burst Time
Response Time = First Response Time - Arrival Time
Average Waiting Time = Σ(Waiting Times) / Number of Processes
CPU Utilization = CPU busy time / Total time × 100%
Effective Access Time (TLB) = α(TLB + Mem) + (1-α)(TLB + 2×Mem) where α = hit ratio
EAT with Page Faults = (1-p)×mem_time + p×page_fault_time, where p = fault rate
Page Number = Logical Address / Page Size (integer division)
Page Offset = Logical Address mod Page Size
Physical Address = (Frame Number × Page Size) + Offset

The 4 Deadlock Conditions (Must Memorize!)

• 1. MUTUAL EXCLUSION — resource held in non-shareable mode
• 2. HOLD AND WAIT — process holds resource while waiting for more
• 3. NO PREEMPTION — resources cannot be forcibly taken away
• 4. CIRCULAR WAIT — P0→P1→P2→...→Pn→P0 (chain of waiting)

Scheduling Algorithm Comparison

Algorithm Type Key Feature Main Drawback
FCFS Non-preemptive Simple FIFO Convoy effect; high
avg wait
SJF Both Minimum avg wait (optimal) Need to know burst
time; starvation
SRTF Preemptive SJF Preempts on shorter arrival Same as SJF
Priority Both Based on priority number Starvation (solve
with aging)
Round Robin Preemptive Equal time quantum for all Performance
depends on
quantum size
Multilevel Queue Preemptive Separate queues per priority class No movement
between queues

Page Replacement Summary

Algorithm Replace Which Page? Belady's Anomaly Optimal?
FIFO Oldest loaded page Can suffer from it No
OPT Not used longest in future No Yes
(theoretical)
LRU Least recently used in past No Best practical
Second Chance FIFO with reference bit check No Good
approximation

Memory Allocation Methods (Disk)

Method Access Pattern Fragmentation Example OS
Contiguous Sequential + Random (fast) External Old batch systems
Linked Sequential (good), Random None FAT (USB drives,
(O(n) slow) MS-DOS)
Indexed (i-node) Sequential + Random (fast) None Unix/Linux, NTFS

Important Linux Commands (Practicals)

Category Commands Purpose
Information date, who, cal, wc, clear, pwd System info, word count,
calendar
File Management cat, cp, rm, mv, cmp, comm, diff, find, grep, Create, copy, delete, compare,
awk search files
Directory cd, mkdir, rmdir, ls Navigate and manage directories
Process Control fork, getpid, ps, kill, sleep Process creation, status,
termination
I/O input/output redirection (>, <, >>), pipe (|) Connect commands, redirect
streams
Protection chmod, chown, chgrp Change permissions, owner,
group
LIKELY EXAM QUESTIONS WITH ANSWERS

Short Answer Questions

Q1: What is an Operating System? What are its two main roles?
An OS is a program that manages computer hardware and acts as intermediary between users and
hardware.
• As Resource Allocator: Manages CPU, memory, I/O devices — allocates resources to
competing processes
• As Control Program: Manages execution of programs to prevent errors and improper use

Q2: Differentiate Multiprogramming and Time-Sharing.

Aspect Multiprogramming Time-Sharing
Goal Maximize CPU utilization Minimize response time
Switching On I/O wait Every time quantum
User interaction Not needed Required
Number of users Single or batch Multiple concurrent

Q3: Explain Dual Mode Operation. Why is it needed?

Dual mode provides hardware support for protecting OS from user programs. Two modes:
• Kernel Mode (bit=0): All instructions including privileged ones can execute
• User Mode (bit=1): Only safe, non-privileged instructions allowed
Needed because without it, any user program could crash the OS or corrupt other programs. System
calls trigger a switch from user to kernel mode for OS services.

Q4: What is a Process? Explain its states with transitions.

A process is a program in execution. It includes text (code), program counter, stack, data, and heap.
Five states: New → Ready → Running → Waiting/Terminated
• New→Ready: Process admitted; Ready→Running: CPU dispatched
• Running→Waiting: I/O requested; Waiting→Ready: I/O completed
• Running→Ready: Preempted (time expired); Running→Terminated: Process exits

Q5: What is a Race Condition? What is the Critical Section problem?

A race condition occurs when multiple processes access shared data concurrently and the result
depends on execution order.
Critical Section: Code where shared resources are accessed. A correct solution needs: (1) Mutual
Exclusion, (2) Progress, (3) Bounded Waiting.

Q6: Calculate Average Waiting Time using FCFS and SJF.

Processes: P1 (Arrival=0, Burst=10), P2 (Arrival=0, Burst=4), P3 (Arrival=0, Burst=6)
FCFS Order: P1(0-10), P2(10-14), P3(14-20) Waiting: P1=0, P2=10, P3=14 →
Average = 24/3 = 8ms SJF Order: P2(0-4), P3(4-10), P1(10-20) Waiting: P2=0,
P3=4, P1=10 → Average = 14/3 = 4.67ms SJF gives much better average waiting
time!

Q7: Explain Paging. How does address translation work?

Paging divides physical memory into fixed-size frames and process memory into same-size pages. A
page table maps pages to frames.
Given: Page Size = 2KB = 2048 bytes, Logical Address = 5000 Page Number = 5000
/ 2048 = 2 (page 2) Offset = 5000 mod 2048 = 904 If page 2 → frame 5, Physical
Address = 5×2048 + 904 = 11144

Q8: What is a Deadlock? State the four necessary conditions.

Deadlock: A set of processes are all blocked, each waiting for a resource held by another in the set.
Four conditions (ALL must hold): 1) Mutual Exclusion, 2) Hold and Wait, 3) No Preemption, 4) Circular
Wait.

Q9: Compare Contiguous, Linked, and Indexed Disk Allocation.

Feature Contiguous Linked Indexed
Sequential access Excellent Good Good
Random access Good Very poor O(n) Good O(1)
Fragmentation External None None
File growth Difficult Easy Easy
Overhead None Pointer per block Index block per file

Q10: What is a Page Fault? How does the OS handle it?

A page fault occurs when a process accesses a page not in physical memory (invalid bit in page table).
OS handling: (1) Trap to OS, (2) Verify valid address, (3) Find free frame, (4) Load page from disk, (5)
Update page table, (6) Restart instruction.

🎯 EXAM TIP
Final tip: Always show your work in numerical problems (Gantt charts, page replacement traces,
address translations). Examiners give partial marks for correct method even if final answer is off.
Time management: attempt all questions — even partial answers get marks!