OPERATING SYSTEMS

Comprehensive Notes
Based on:
Abraham Silberschatz, Peter Baer Galvin & Greg Gagne
"Operating System Concepts" — 9th Edition, John Wiley & Sons, 2018
Andrew S. Tanenbaum
"Modern Operating Systems" — 4th Edition, Pearson, 2016
1. File Allocation Methods
When a file is created, the OS must allocate disk space. Three primary allocation methods exist, each
with different trade-offs in terms of access speed, fragmentation, and ease of file growth.

1.1 Contiguous Allocation

Each file occupies a set of contiguous blocks on the disk. The directory entry stores only the starting
block address and the length of the file.

Key Characteristics
• Access: Both sequential and direct (random) access are efficient.
• Starting block + length is stored in the directory.
• Finding free space: Best-fit or first-fit strategy used.
• Problem 1 — External Fragmentation: Free space is scattered in small holes.
• Problem 2 — Pre-declaration: File size must be known at creation time.
• Compaction: Can eliminate fragmentation but is I/O intensive.

Example (Silberschatz): If a file starts at block 0 and has length 5, it occupies blocks 0, 1, 2, 3, 4.

1.2 Linked Allocation

Each file is a linked list of disk blocks. Each block contains a pointer to the next block. The directory
stores only the first and last block pointers.

Key Characteristics
• No external fragmentation — any free block can be used.
• Sequential access only — direct access requires traversing pointers.
• Pointer overhead: Part of each block is used for the next-block pointer.
• Reliability: A lost pointer can corrupt the entire file.
• FAT (File Allocation Table): A variation where pointers are stored in a table in memory.
— Used in MS-DOS and Windows FAT file systems.

1.3 Indexed Allocation

Each file has an index block (inode) containing pointers to all the file's data blocks. The directory entry
points to the index block.

Key Characteristics
• Supports direct access efficiently.
• No external fragmentation.
• Index block overhead for small files.
• Multilevel Index: For large files, index blocks can point to other index blocks.
— Single indirect: one level of indirection.
— Double indirect: two levels.
— Triple indirect: three levels (used in UNIX inodes).
• UNIX uses a combined scheme: 12 direct + single + double + triple indirect pointers.

Method Direct Sequential Fragmentatio Pointer Overhead

 Access Access n
Contiguous Yes (fast) Yes (fast) External None
Linked No (slow) Yes None Per block
Indexed Yes (fast) Yes None Index block
2. Directory Structure
A directory is a symbol table that translates file names to their directory entries. It stores file name,
type, address, size, timestamps, and protection info.

2.1 Single-Level Directory

• All files are in the same directory.
• Simple but has naming conflicts — all files must have unique names.
• Not suitable for multi-user systems.

2.2 Two-Level Directory

• Separate directory for each user: User File Directory (UFD) + Master File Directory (MFD).
• Users may have the same file names without conflict.
• Isolation prevents sharing between users.

2.3 Tree-Structured Directory (Hierarchical)

The most common structure. Directories can contain both files and subdirectories, forming a tree
rooted at the root directory '/'.
• Absolute path: full path from root (e.g., /home/user/docs/[Link]).
• Relative path: path relative to current directory.
• Each process has a current working directory (CWD).
• Searching, deleting, and organizing files is flexible and efficient.

2.4 Acyclic-Graph Directory

Allows directories to share subdirectories and files. Two users can share a file if a pointer (link) to it
exists in both directories.
• Hard link: second directory entry pointing to the same inode.
• Symbolic (soft) link: a special file containing the path to another file.
• Dangling pointer problem: when the shared file is deleted, links become invalid.
• Solution: back-references count (reference counting) — delete only when count = 0.

2.5 General Graph Directory

• Cycles are allowed in the directory graph.
• Requires garbage collection to reclaim disk space.
• ln command in UNIX can create links (both hard and symbolic).
Note: Tanenbaum: Directories with cycles must be handled carefully during traversal to avoid infinite
loops.
3. Disk Scheduling Algorithms
The OS must decide which of the pending I/O requests to service first to minimize disk head seek
time. This is done through disk scheduling algorithms.
Example queue used throughout: Disk queue: 98, 183, 37, 122, 14, 124, 65, 67 | Head starts at: 53 |
Total cylinders: 0–199

3.1 FCFS (First-Come-First-Served)

• Requests are serviced in the order they arrive.
• Simple, fair, but high seek time due to wild head movement.
• Head movement: 53→98→183→37→122→14→124→65→67 = 640 cylinders total.

3.2 SSTF (Shortest-Seek-Time-First)

• Services the request closest to current head position.
• Reduces total head movement; better throughput than FCFS.
• Head movement: 53→65→67→37→14→98→122→124→183 = 236 cylinders.
• Problem: Starvation of requests far from the current head position.

3.3 SCAN (Elevator Algorithm)

• Head moves in one direction, servicing requests, until it reaches the end; then reverses.
• Head movement: 53→37→14→0→65→67→98→122→124→183 = 236 cylinders.
• Uniform wait time. Fairer than SSTF.

3.4 C-SCAN (Circular SCAN)

• Head moves in one direction only, servicing requests. When it reaches the end, it returns to
the beginning without servicing.
• More uniform wait time than SCAN.
• Treats the disk as a circular list of cylinders.

3.5 LOOK and C-LOOK

• LOOK: Like SCAN but head only goes as far as the last request in each direction (not to disk
end).
• C-LOOK: Like C-SCAN but returns to the lowest cylinder with a pending request, not cylinder
0.
• More efficient in practice than SCAN/C-SCAN.
Total Cylinders
Algorithm Starvation? Best Use Case
(example)
FCFS 640 No Light load, fairness needed
SSTF 236 Yes Maximise throughput
SCAN 236 No Heavy load, moderate fairness
C-SCAN ~183 No Uniform wait time needed
LOOK/C-LOOK Slightly less No General purpose (preferred)
4. Android Architecture
Android is an open-source, Linux-based mobile operating system developed by Google. Its
architecture is a layered software stack.

Layer 1: Linux Kernel (Bottom Layer)

Android is built on top of the Linux kernel (versions 2.6 and above). It provides:
• Hardware abstraction: drivers for camera, display, audio, keypad, Wi-Fi, Bluetooth.
• Memory management, process management, security, and networking.
• Binder IPC driver: Android-specific inter-process communication mechanism.

Layer 2: Hardware Abstraction Layer (HAL)

• Provides standard interfaces to hardware components.
• Each hardware type (camera, audio, sensors) has a corresponding HAL module.
• Shields upper layers from hardware-specific implementation details.

Layer 3: Android Runtime (ART) & Core Libraries

• ART (Android Runtime): Replaces Dalvik VM (since Android 5.0 Lollipop). Executes .dex
(Dalvik Executable) bytecode.
• AOT (Ahead-Of-Time) compilation: Apps are compiled to native machine code at installation
time, unlike JIT (Just-In-Time).
• Core Libraries: Java-based libraries providing functionality like data structures, math, I/O,
strings.

Layer 4: Application Framework

• Provides high-level services (APIs) that Java/Kotlin applications use:
◦ Activity Manager: manages app lifecycle and the back stack.
◦ Content Providers: enables data sharing between applications.
◦ Resource Manager: manages non-code resources (strings, layouts, drawables).
◦ Notification Manager: manages status bar notifications.
◦ View System: for building UI components (buttons, lists, etc.).

Layer 5: Applications (Top Layer)

• Pre-installed apps (Dialer, Camera, Browser) and third-party apps (APKs).
• Each app runs in its own process with its own instance of ART.
• Android uses UID-based sandboxing for security — each app has a unique Linux UID.
5. Types of Hypervisor, Benefits and Features of
Virtualization
5.1 Virtualization
Virtualization is the technique of simulating hardware so that multiple operating systems (guests) can
run concurrently on a single physical machine (host). The layer providing this simulation is called the
Virtual Machine Monitor (VMM) or Hypervisor.

5.2 Type 1 Hypervisor (Bare-Metal / Native)

Type 1 Hypervisor
• Runs directly on the physical hardware (no host OS underneath).
• Has direct access to hardware resources.
• Higher performance and security than Type 2.
• Examples: VMware ESXi, Microsoft Hyper-V, Xen, KVM (Linux kernel integrated).
• Used in enterprise data centres and cloud infrastructure (AWS, Azure).

5.3 Type 2 Hypervisor (Hosted)

Type 2 Hypervisor
• Runs on top of a conventional host operating system.
• The host OS provides hardware access to the hypervisor.
• Easier to install and use; suitable for development/testing.
• Lower performance due to additional OS layer.
• Examples: VMware Workstation, VirtualBox, Parallels Desktop, QEMU.

Feature Type 1 (Bare-Metal) Type 2 (Hosted)

Runs on Physical hardware directly Host OS
Performance Higher Lower (OS overhead)
Security Better isolation Less isolated
Setup complexity Higher Easier
Use case Production, cloud, enterprise Development, testing, desktop
Examples ESXi, Hyper-V, Xen VirtualBox, VMware Workstation

5.4 Benefits of Virtualization

• Consolidation: Multiple VMs on one physical server → reduced hardware cost.
• Isolation: Each VM is isolated; a crash in one VM does not affect others.
• Portability: VM images can be moved between physical machines (live migration).
• Snapshots: VM state can be saved and restored instantly.
• Security: Malware in a guest VM cannot affect the host.
• Legacy support: Old OS versions run on modern hardware.
• Cloud computing: Foundation for IaaS (Infrastructure as a Service).
Note: Tanenbaum: A VMM must meet three conditions — Fidelity, Safety, and Efficiency (Popek-
Goldberg theorem).
6. Paging
Paging is a memory management scheme that eliminates the need for contiguous allocation of
physical memory and avoids external fragmentation.

6.1 Basic Concept

• Physical memory is divided into fixed-sized blocks called frames.
• Logical memory (process address space) is divided into fixed-sized blocks of the same size
called pages.
• Page size = Frame size. Typical sizes: 4 KB to 64 KB.
• The OS maintains a page table per process, mapping page numbers to frame numbers.

6.2 Address Translation

A logical address is divided into two parts:
• Page number (p): index into the page table to find the frame number.
• Page offset (d): offset within the page/frame.
Physical address = frame_number × page_size + offset

Example (Silberschatz)
Page size = 4 bytes. Logical address space = 16 bytes → 4 pages.
Physical memory = 32 bytes → 8 frames.
Page table: Page 0→Frame 5, Page 1→Frame 6, Page 2→Frame 1, Page 3→Frame 2.
Logical address 13 = Page 3, Offset 1 → Frame 2, Offset 1 → Physical 9.

6.3 Hardware Support — TLB

• Translation Lookaside Buffer (TLB): A fast cache for page table entries.
• TLB hit: Physical address obtained in 1 cycle; TLB miss: page table must be consulted.
• Effective Access Time (EAT) = hit_ratio × (TLB_time + memory_time) + (1−hit_ratio) ×
(TLB_time + 2×memory_time).
• TLB hit rates typically > 99% → EAT ≈ memory access time.

6.4 Multilevel Paging

• For 32-bit or 64-bit address spaces, the page table itself becomes very large.
• Solution: Hierarchical page tables (two-level, three-level).
• Two-level example: outer page table → inner page table → frame.
• Used in x86 (two-level), x86-64 (four-level).

6.5 Inverted Page Table

• One entry per physical frame, not per logical page.
• Reduces memory used by page tables.
• Searching is slower; hashing is used to speed up lookup.
• Used in IBM System 38, AS/400, and PowerPC.
7. Segmentation
Segmentation is a memory management scheme that supports a programmer's view of memory. A
program is a collection of segments — logical units such as the main program, procedures, functions,
stack, symbol table, etc.

7.1 Basic Concept

• Logical address = <segment number s, offset d>.
• Segment table: maps segment number to base address and limit (size) in physical memory.
• If offset d >= limit → segmentation fault (protection violation).
• Physical address = segment_base + d.

Example (Silberschatz)
Process has 5 segments: 0=code, 1=data, 2=stack, 3=symbol table, 4=Fortran library.
Logical address <2, 400>: segment 2 base=3200, limit=400. Physical = 3200+400 = 3600.
Logical address <3, 112>: segment 3 base=4700, limit=580. Physical = 4700+112 = 4812.

7.2 Advantages and Disadvantages

Advantages Disadvantages
Matches programmer's logical view of memory External fragmentation (variable-sized segments)
Protection: each segment has read/write/execute Requires compaction or best-fit allocation
bits
Sharing: code segment can be shared between Hardware support needed (segment table)
processes
Allows segments to grow/shrink dynamically Complex memory management

7.3 Segmentation with Paging

• Combine both techniques: logical address → segment → pages within segment → frames.
• Eliminates external fragmentation (paging) while retaining logical view (segmentation).
• Used in Intel x86 protected mode (segment selector + paged virtual address).
Note: Tanenbaum: Segmentation is visible to the programmer; paging is transparent. Modern OSes
often use paging alone.
8. Demand Paging
Demand paging is a virtual memory technique where pages are loaded into memory only when they
are demanded (accessed) during execution, not at load time.

8.1 Basic Concept

• Process pages reside on disk. When a page is needed, it is loaded into a free frame.
• Lazy swapper (pager): swaps in a page only when needed.
• Valid/Invalid bit in page table: valid = page in memory; invalid = page on disk.
• Benefit: Allows more processes in memory (increased multiprogramming), faster startup.

8.2 Page Fault Handling Procedure

When the MMU encounters a page with invalid bit set:
• 1. CPU generates a page fault (trap to OS).
• 2. OS checks an internal table: valid reference or invalid address?
◦ — Invalid reference → terminate process (segfault).
◦ — Valid reference but not in memory → proceed.
• 3. Find a free frame in physical memory.
• 4. Schedule a disk operation to read the page into the frame.
• 5. Update the page table: set frame number, set valid bit = valid.
• 6. Restart the instruction that caused the page fault.

8.3 Performance of Demand Paging

Effective Access Time (EAT):
EAT = (1 − p) × memory_access_time + p × page_fault_service_time

Numerical Example
Memory access time = 200 ns.
Page fault service time = 8,000,000 ns (8 ms: disk seek + rotational latency + transfer).
p = page fault rate.
For EAT < 220 ns (10% slowdown): p < 0.0000025 (less than 1 fault per 400,000 accesses).
This shows that page fault rate must be kept very low for acceptable performance.

8.4 Copy-on-Write (COW)

• When fork() is called, parent and child share pages (marked copy-on-write).
• A page is copied only when one process modifies it.
• Significantly reduces the overhead of process creation.
• Used in UNIX, Linux, Windows (vfork also uses COW).
9. Page Replacement Algorithms
When a page fault occurs and there are no free frames, the OS must select a victim page to evict.
Page replacement algorithms decide which page to replace.

9.1 FIFO (First-In-First-Out)

• Replace the page that has been in memory the longest.
• Simple to implement using a queue.
• Suffers from Belady's Anomaly: adding more frames may increase page faults.

FIFO Example (Silberschatz)

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
3 frames: 15 page faults | 4 frames: 16 page faults → Belady's Anomaly demonstrated!

9.2 OPT / OPR (Optimal Page Replacement)

• Replace the page that will not be used for the longest time in the future.
• Produces the minimum number of page faults of any algorithm.
• Theoretical only — requires future knowledge of reference string.
• Used as a benchmark to compare other algorithms.

9.3 LRU (Least Recently Used)

• Replace the page that has not been used for the longest period of time.
• Good approximation of OPT. Does not suffer from Belady's Anomaly.
• Implementation 1 — Counter: Each page has a time-of-use counter; replace the smallest.
• Implementation 2 — Stack: Keep a stack of page numbers; most recently used at top.
• Hardware support needed (expensive); approximated in practice.

9.4 LRU Approximation Algorithms

• Reference bit: Each page has a bit, set to 1 by hardware when accessed.
• Second-Chance (Clock Algorithm): FIFO but pages with reference bit=1 get a second chance
(bit cleared); replaced only if bit=0.
• Enhanced Second-Chance: Uses (reference bit, modify bit) pair: prefer (0,0), then (0,1), (1,0),
(1,1) last.

9.5 Counting Algorithms

• LFU (Least Frequently Used): Replace the page with smallest count. Pages used often have
large counts.
• MFU (Most Frequently Used): Replace page with largest count (newly loaded pages have low
count; likely still needed).
• Neither LFU nor MFU approximates OPT well in practice.
Belady's
Algorithm Page Faults Practical Use
Anomaly
FIFO High Yes Simple systems
 Belady's
Algorithm Page Faults Practical Use
Anomaly
OPT Minimum No Benchmark only
(theoretical)
LRU Low No Widely used
Clock (2nd Chance) Near LRU No Most OS implementations
LFU Medium No Specialized workloads
10. Memory Allocation Strategies
When multiple processes compete for memory, the OS must decide how to allocate and manage
memory space for each.

10.1 Contiguous Memory Allocation

Each process occupies a single contiguous section of memory. Two approaches:
• Fixed-Partition (Static): Memory divided into fixed-sized partitions at boot time. Each partition
holds one process. Problem: internal fragmentation.
• Variable-Partition (Dynamic): Partition created exactly the size of the process. Tracked as a
table of holes (free memory).

10.2 Free-Space Management — Allocation Policies

Strategy Description Speed Fragmentation
First-Fit Allocate first hole big enough Fastest Acceptable
Best-Fit Allocate smallest sufficient hole Slowest (must Most external
search all)
Worst-Fit Allocate largest hole Slow Leaves large holes
Next-Fit Like First-Fit but from last allocation Fast Similar to First-Fit
Note: Silberschatz: First-Fit and Best-Fit are generally better than Worst-Fit. First-Fit is fastest.

10.3 Fragmentation
• Internal Fragmentation: Allocated memory larger than requested (wasted inside partition).
Occurs with fixed-size blocks.
• External Fragmentation: Total free memory sufficient, but not contiguous. Occurs with
dynamic allocation.
• Solution to External Fragmentation: Compaction (shuffling memory to create one large block)
— requires dynamic relocation, expensive.
• Paging & Segmentation eliminate external fragmentation entirely.

10.4 Non-Contiguous Allocation

• Paging: Fixed-size pages mapped to frames anywhere in physical memory.
• Segmentation: Variable-size logical segments mapped to physical memory.
• Allows efficient use of memory without needing contiguous space.

10.5 Allocation in Virtual Memory Systems

• Frame allocation: How many frames to allocate to each process?
• Equal allocation: Divide frames equally among all processes.
• Proportional allocation: Allocate based on process size.
• Priority allocation: Higher-priority processes get more frames.
• Global vs. Local replacement: Global — steal frames from any process; Local — replace only
from own allocated frames.
10.6 Thrashing
If a process does not have enough frames, page fault rate becomes very high. The process spends
more time paging than executing — this is called thrashing.
• Cause: Over-commitment of memory (too many processes in memory).
• Detection: CPU utilisation drops while page fault rate spikes.
• Prevention: Working Set Model (keep in memory the set of pages recently used — the
working set).
• Working set window Δ: A process needs |WS| frames to avoid thrashing.
• Page Fault Frequency (PFF): If PFF too high → give more frames. If PFF too low → reduce
frames.
11. Differences Between iOS and Android OS
Both iOS and Android are mobile operating systems, but they differ fundamentally in architecture,
kernel, security model, customisability, and application ecosystem.
Feature Android iOS
Developed by Google (open-source, AOSP) Apple Inc. (proprietary)
Kernel Linux kernel (modified) XNU kernel (Mach + BSD hybrid)
Source code Open Source (AOSP) + Closed source (proprietary)
proprietary additions
Programming language Java, Kotlin (apps); C/C++ Swift, Objective-C (apps); C/C++
(native) (native)
Runtime ART (Android Runtime), AOT Objective-C runtime / Swift
compilation runtime, JIT+AOT
App distribution Google Play Store + sideloading Apple App Store only (strict
(APK) review process)
Customisability Highly customisable (launchers, Very limited customisation
ROMs, widgets)
Sandboxing UID-based Linux sandboxing Mandatory Access Control (MAC),
entitlements-based
File system ext4, F2FS, EROFS APFS (Apple File System)
IPC mechanism Binder IPC Mach ports, XPC services
Update model OEM/carrier dependent Direct from Apple (unified, fast
(fragmentation) rollout)
Multitasking Full multitasking with background Managed/suspended background
processes processes (App Nap)
User interface Material Design (configurable) Human Interface Guidelines
(consistent)
Market share ~72% global (2024) ~27% global (2024)
Device support Multiple OEM devices (Samsung, Apple hardware only (iPhone,
OnePlus, etc.) iPad)
Security model SELinux mandatory enforcement Secure Enclave, Code Signing,
+ sandboxing App Review
Virtual machine ART executes .dex bytecode No separate VM; native machine
code

Key Architectural Differences

• Kernel: Android uses a monolithic Linux kernel with Android-specific drivers (Binder,
Wakelocks, Ashmem). iOS uses XNU, a hybrid microkernel (Mach) + BSD.
• Security: iOS relies on hardware-enforced Secure Enclave and mandatory app signing.
Android relies on SELinux + app sandboxing.
• Openness: Android allows sideloading third-party APKs; iOS strictly enforces App Store
distribution (jailbreak required to bypass).
 • Updates: iOS delivers OS updates directly; Android updates go through OEMs →
fragmentation of OS versions.
Note: Tanenbaum: Both systems evolved from general-purpose OS concepts but are optimised for
battery-constrained, touch-first devices with strong security and memory management requirements.

— End of Notes —