UNIVERSITY COLLEGE OF ENGINEERING

ANNA UNIVERSITY TIRUCHIRAPPALLI

IV Semester / B.E., CSE
AL3452 — Operating Systems
Second Internal Assessment — Answer Script

PART — A (2 Marks Each)

1. Define Swapping.
Swapping is a memory management technique in which a process is temporarily moved (swapped out) from
main memory (RAM) to secondary storage (disk), freeing RAM for other processes. When the process is
needed again, it is swapped back in. This allows the OS to run more processes than the physical memory can
hold simultaneously, effectively extending the degree of multiprogramming.

2. What is Thrashing?
Thrashing is a condition in which a process spends more time swapping pages in and out of memory than
executing actual instructions. It occurs when a process does not have enough frames to hold its working set,
causing frequent page faults. The CPU utilisation drops drastically, and the system appears to "hang." It is
prevented using the Working Set Model or Page Fault Frequency algorithm.

3. What is Virtual Memory?

Virtual Memory is a memory management capability of an OS that creates an illusion of a large, contiguous
address space for each process, larger than the available physical RAM. It allows programs to execute even if
they are not completely loaded into memory. The OS brings pages into physical memory on demand (demand
paging). It enables better CPU utilisation, process isolation, and supports running large programs on limited
RAM.

4. State the Two Types of Fragmentation.

(i) Internal Fragmentation: Wasted space inside an allocated memory block. Occurs when the allocated block
is larger than the requested size (e.g., fixed-size partitioning or paging — the last page may not be fully used).
(ii) External Fragmentation: Wasted space outside allocated blocks. Free memory exists in many small,
non-contiguous holes that together are large enough to satisfy a request, but individually cannot. Occurs in
variable-size partitioning. Solved by compaction.

5. Two Differences Between Paging and Segmentation.

Aspect Paging Segmentation

Division Process divided into fixed-size pages Process divided into variable-size segments (logical units)

Fragmentation Causes internal fragmentation Causes external fragmentation

6. Under What Circumstances Does a Page Fault Occur?

A page fault occurs when:
• The referenced page is not present in physical memory (valid bit = 0 in the page table entry).
• A process accesses a page for the first time (initially all valid bits are 0 in demand paging).

AL3452 — Operating Systems | Answer Script Page 1

 • The page was previously swapped out to disk to free a frame, and is now accessed again.
The OS handles the page fault by locating the page on disk, loading it into a free frame, updating the page table,
and restarting the faulting instruction.

7. Define Physical Address.

Physical Address (also called real address or absolute address) is the actual address in the physical memory
(RAM) where a data item or instruction resides. It is generated by the Memory Management Unit (MMU) by
translating the logical (virtual) address produced by the CPU. The user program never directly accesses
physical addresses; the mapping is handled transparently by the MMU using the page table.

AL3452 — Operating Systems | Answer Script Page 2

 PART — B (12 Marks Each — Any FOUR)

B1. Various File Allocation Methods

Introduction
File allocation methods determine how disk blocks are assigned to files. The choice of allocation method directly
affects disk access speed, space utilization, and fragmentation. There are three primary file allocation methods:
Contiguous, Linked, and Indexed.
File Allocation Methods — Visual Summary
Contiguous:

Blk 0 Blk 1 Blk 2 Blk 3 Blk 4 ← Sequential allocation

Linked:

B0|next B1|next B2|next B3|next B4|next NULL

Indexed:

Index Blk Blk0 Blk1 Blk2 Blk3

[0][1][2][3]

Contiguous: Fast access, external fragmentation | Linked: No fragmentation, slow random access | Indexed: Random access, index overhead

1. Contiguous Allocation
In contiguous allocation, each file occupies a set of contiguous (adjacent) blocks on disk. The directory entry
stores only the starting block number and the length (number of blocks) of the file.
Advantages: Simple implementation. Excellent read performance — both sequential and random access are
efficient because blocks are adjacent. Minimal seek time on magnetic disks.
Disadvantages: External fragmentation — over time, free space is scattered in small holes. File size must be
known in advance, which is often impractical. Difficult to grow a file once allocated. Compaction is required
periodically to reclaim fragmented space, which is expensive.

2. Linked Allocation
In linked allocation, each file is stored as a linked list of disk blocks. Each block contains a pointer to the next
block. The directory entry stores the address of the first block and the last block of the file.
Advantages: No external fragmentation — any free block anywhere on disk can be used. Files can grow
dynamically without knowing the size in advance. Simple to implement for sequential access.
Disadvantages: Inefficient for random (direct) access — to reach block i, all i−1 preceding blocks must be
traversed. Pointer storage wastes space within each block. Reliability risk — a damaged pointer corrupts the
rest of the file.
FAT (File Allocation Table) is a variation where all pointers are stored in a separate table (the FAT) in memory,
improving random access performance.

3. Indexed Allocation
In indexed allocation, all block pointers for a file are stored in a dedicated index block. The directory entry
points to this index block. The index block contains an array of addresses of the actual data blocks.
Advantages: Supports both sequential and direct (random) access efficiently. No external fragmentation. Files
can grow dynamically up to the size of the index block.
Disadvantages: Overhead of the index block itself — wastes space for small files. For very large files, a single
index block is insufficient. This is handled by:

AL3452 — Operating Systems | Answer Script Page 3

 • Linked scheme: Link multiple index blocks together.
• Multilevel index: Use a top-level index pointing to secondary index blocks (similar to UNIX i-nodes with
direct, single-indirect, double-indirect, triple-indirect pointers).
• Combined scheme (UNIX i-node): First 12 pointers are direct; 13th is single-indirect; 14th is
double-indirect; 15th is triple-indirect — balancing efficiency for both small and large files.

Comparison Table
Feature Contiguous Linked Indexed

Access Type Sequential & Random Sequential only Sequential & Random

Fragmentation External None None

File Growth Difficult Easy Easy

Space Overhead Low Pointer per block Index block

Reliability High Low (pointer damage) Medium

Used In CD-ROM, DVDs FAT file system UNIX (i-node)

AL3452 — Operating Systems | Answer Script Page 4

 B2. Page Replacement — FIFO, LRU, Optimal (Ref: 1,2,3,4,1,2,5,1,2,3,4,5 | 4 Frames)

Introduction
When a page fault occurs and no free frame is available, the OS must select a victim page to replace. Page
replacement algorithms determine which page to evict. We evaluate three algorithms on the reference string 1,
2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 4 frames.

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

The page that has been in memory the longest is replaced first. A queue maintains the order of page arrivals.
When a fault occurs, the front of the queue (oldest page) is evicted.

FIFO Page Replacement (Reference: 1,2,3,4,1,2,5,1,2,3,4,5 | 4 Frames)

FIFO Simulation
Ref 1 (4
2 Frames)3 — Reference
4 String:
1 1 2 3 4 12 2 5 1 2 354 5 1 2 3 4 5

F1 →
Ref 1 2 3 4 1 2 5 1 2 3 4 5

Frame
F2 1 1 1 1 1 1 1 2 3 4 5 1 2

Frame
F3 2 2 2 2 2 2 3 4 5 1 2 3

Frame
F4 3 3 3 3 3 4 5 1 2 3 4

Frame 4 4 4 4 5 1 2 3 4 5

Fault? F F F F H H F F F F F F

FIFO → Page Faults (Misses): 10 | Hits: 2 | Miss Ratio: 10/12 = 0.83 | Hit Ratio: 2/12 = 0.17

2. LRU (Least Recently Used)

The page that was used least recently (farthest in the past) is replaced. It uses the principle of temporal locality
— recently used pages are likely to be used again soon.
LRU Simulation (4 Frames) — Reference String: 1 2 3 4 1 2 5 1 2 3 4 5
Ref → 1 2 3 4 1 2 5 1 2 3 4 5

Frame 1 1 2 3 4 1 2 5 1 2 3 4 5

Frame 2 1 2 3 4 1 2 5 1 2 3 4

Frame 3 1 2 3 4 1 2 5 1 2 3

Frame 4 1 2 3 4 4 4 5 1 2

Fault? F F F F H H F H H F F F

LRU → Page Faults (Misses): 8 | Hits: 4 | Miss Ratio: 8/12 = 0.67 | Hit Ratio: 4/12 = 0.33

3. Optimal Page Replacement

Replace the page that will not be used for the longest time in the future. This is a theoretical algorithm (not
implementable in practice since future knowledge is required) but serves as a benchmark for the best possible
performance.

AL3452 — Operating Systems | Answer Script Page 5

 Optimal Simulation (4 Frames) — Reference String: 1 2 3 4 1 2 5 1 2 3 4 5
Ref → 1 2 3 4 1 2 5 1 2 3 4 5

Frame 1 1 1 1 1 1 1 1 1 1 1 2 2

Frame 2 2 2 2 2 2 2 2 2 2 3 3

Frame 3 3 3 3 3 3 3 3 3 5 5

Frame 4 4 4 4 5 5 5 5 4 4

Fault? F F F F H H F H H H F H

Optimal → Page Faults (Misses): 6 | Hits: 6 | Miss Ratio: 6/12 = 0.50 | Hit Ratio: 6/12 = 0.50

Summary Table
Algorithm Page Faults (Misses) Hits Miss Ratio Hit Ratio

FIFO 8 4 8/12 = 0.67 4/12 = 0.33

LRU 8 4 8/12 = 0.67 4/12 = 0.33

Optimal 6 6 6/12 = 0.50 6/12 = 0.50

Note: Optimal always gives the minimum page faults (Belady's optimal). FIFO may suffer from Belady's
anomaly (more frames → more faults in some cases). LRU is practical using hardware counters or stack
implementation.

AL3452 — Operating Systems | Answer Script Page 6

 B3. Logical to Physical Address Conversion Using Paging

Concept of Paging
Paging is a non-contiguous memory allocation scheme that eliminates external fragmentation. The logical
address space of a process is divided into fixed-size units called pages, and physical memory is divided into
same-sized units called frames. The OS maintains a Page Table for each process to map page numbers to
frame numbers.

Address Structure
A logical (virtual) address generated by the CPU is split into two parts:
• Page Number (p) — used as an index into the page table to find the frame number.
• Page Offset (d) — the offset within the page; combined with the frame number to get the physical address.
Logical Address = Page Number (p) Page Offset (d)

Physical Address = Frame Number (f) Page Offset (d)

Conversion Formula
If page size = 2n bytes, then:
Page Number (p) = Logical Address ÷ Page Size
Offset (d) = Logical Address mod Page Size
Physical Address = Frame Number × Page Size + Offset

Diagram: Address Translation

Physical Memory
0: Frame 0
Page Table
1: Frame 1

Page Frame 2: Frame 2

0 3
CPU Page# | Offset Frame# | Offset 3: Frame 3
1 7
(Logical Addr) 4: Frame 4
2 1

3 5 5: Frame 5

6: Frame 6

7: Frame 7
Physical Address = Frame Number x Page Size + Offset
Logical Address = Page Number x Page Size + Offset

Role of the MMU (Memory Management Unit)

The MMU is a hardware component that performs the logical-to-physical address translation at runtime. It uses
the Page Table Base Register (PTBR) to locate the page table in memory. Every memory access requires two
memory accesses: one for the page table and one for the actual data — this is optimised by the TLB
(Translation Lookaside Buffer), a fast hardware cache that stores recent page-to-frame mappings.

TLB Operation
When the CPU generates a logical address, the MMU first checks the TLB for the page number:
• TLB Hit: Frame number found in TLB → direct computation of physical address. Access time = TLB access
time + memory access time.

AL3452 — Operating Systems | Answer Script Page 7

 • TLB Miss: Page table in memory is consulted → frame number retrieved → TLB updated (LRU/FIFO
replacement). Access time = TLB access time + 2 × memory access time.

Protection and Sharing

Each page table entry also contains protection bits (read/write/execute) and a valid–invalid bit. If a process
accesses a page marked invalid, a page fault is triggered. Shared pages (e.g., shared libraries) can map to the
same frame in multiple processes' page tables, reducing memory usage.

Numerical Example
Page size = 4 KB (212). Logical address = 12345.
Page number p = 12345 ÷ 4096 = 3 (integer division). Offset d = 12345 mod 4096 = 57.
Suppose page table entry for page 3 gives frame 7. Then:
Physical Address = 7 × 4096 + 57 = 28672 + 57 = 28729.

AL3452 — Operating Systems | Answer Script Page 8

 B4. Various Disk Scheduling Algorithms

Introduction
Disk scheduling algorithms determine the order in which disk I/O requests (for various cylinder/track numbers)
are serviced. The goal is to minimise seek time (time for the disk head to move to the desired track), which is
the dominant factor in disk access time. Other components are rotational latency and transfer time.

1. FCFS — First Come, First Served

Requests are served in the order they arrive in the queue. It is the simplest algorithm and is fair (no starvation).
However, it does not optimise head movement, so total seek time can be very high. The head may move back
and forth across the disk (wild swing effect).
Example: Queue = 98, 183, 37, 122, 14, 124, 65, 67; Head = 53. Order:
53→98→183→37→122→14→124→65→67. Total = 640 cylinders.

2. SSTF — Shortest Seek Time First

The request closest to the current head position is served next. It reduces total seek time significantly compared
to FCFS. However, it may cause starvation — requests far from the head may wait indefinitely if closer
requests keep arriving.
Example: Head = 53. Order: 53→65→67→98→122→124→183→37→14. Total = 236 cylinders.
Disk Scheduling — SSTF Example (Queue: 98,183,37,122,14,124,65,67 | Head=53)

0 14 37 53* 6567 98 122

124 183 199
SSTF:

SSTF Total Head Movement: 299 cylinders

FCFS: Serve in arrival order | SSTF: Nearest first | SCAN: Sweep like elevator | C-SCAN: Circular sweep | LOOK: Like SCAN but reverses at last request

3. SCAN (Elevator Algorithm)

The disk arm moves in one direction (e.g., towards higher cylinders), servicing all requests in its path. When it
reaches the last request in that direction, it reverses and moves back, servicing requests on the return trip. It
resembles an elevator — hence the name. It provides uniform wait time and prevents starvation.
Example: Head = 53 (moving towards 0). Order: 53→37→14→0→65→67→98→122→124→183. Total = 236
cylinders.

4. C-SCAN (Circular SCAN)

A variant of SCAN where the head moves only in one direction. After reaching the last cylinder, it immediately
returns to the beginning (cylinder 0) without servicing requests on the return journey, then sweeps again. This
provides a more uniform wait time compared to SCAN, as requests at the beginning of the disk do not wait for
a full sweep.
Example: Head = 53 (moving upward). Order: 53→65→67→98→122→124→183→199→0→14→37. Total =
382 cylinders.

5. LOOK

AL3452 — Operating Systems | Answer Script Page 9

 Similar to SCAN, but the head reverses direction at the last actual request in that direction (not at the physical
end of the disk). This avoids unnecessary head travel to the end of the disk when no requests exist there, saving
seek time.

6. C-LOOK
Circular variant of LOOK. The head moves upward servicing requests, and after the last request in that
direction, jumps directly to the smallest cylinder request (without going to cylinder 0) and sweeps upward again.
Combines advantages of C-SCAN and LOOK.

Comparison Table
Algorithm Order of Service Total Movement Starvation Complexity

FCFS Arrival order High No Low

SSTF Closest first Low-Medium Yes Medium

SCAN Directional sweep Medium No Medium

C-SCAN One-way circular Medium No Medium

LOOK Sweep to last req. Low No Medium

C-LOOK Circular to last req. Lowest No Medium

Conclusion: SSTF is best for throughput but risks starvation. LOOK and C-LOOK are generally considered the
most efficient practical algorithms, balancing low seek time with fairness.

AL3452 — Operating Systems | Answer Script Page 10

 B5. Concept of Demand Paging

Introduction
Demand Paging is a virtual memory technique where pages of a process are loaded into physical memory only
when they are demanded (i.e., accessed) during execution — not all at once at process start. It is based on the
principle of lazy loading. A page that is never accessed is never loaded, saving memory and startup time.
Demand paging is fundamental to modern operating systems (Windows, Linux, macOS) and enables virtual
memory, memory sharing, and efficient multitasking.

Diagram: Demand Paging and Page Fault Handling

Demand Paging — Page Fault Handling
Page Table
Page | Frame | Valid
CPU Access
1 | 3 | 1
Process OS Page Fault
2 | - | 0 <- Fault
Handler Secondary
Read page
1. Find free frame Storage
2. Load page from disk (Disk / SSD)
Page Fault
Trap to OS
Update valid bit Physical Load
Memory
Restart instruction
Frame 0: Page A
Frame 1: Page B
Frame 2: [new page]
Frame 3: Page C

Steps: [Link] accesses page [Link] bit=0 → Page Fault [Link] locates page on disk
[Link] into free frame [Link] page table (valid=1) [Link] instruction

Key Components
• Page Table with Valid-Invalid Bit: Each page table entry has a valid (v) or invalid (i) bit. If valid → page is
in memory. If invalid → page is on disk (not yet loaded, or swapped out).
• Secondary Storage (Swap Space): The disk area where pages not currently in RAM are stored. Also
called the swap partition or paging file.
• Page Fault Handler (OS): The OS routine that handles the trap, locates the page on disk, allocates a free
frame, loads the page, and restarts the instruction.

Page Fault Handling — Step-by-Step

Step 1 — Memory Reference: The CPU generates a logical address to access a page. The MMU checks the
page table.
Step 2 — Check Valid Bit: If valid bit = 1, the page is in memory → normal access. If valid bit = 0, a page fault
trap is raised.
Step 3 — Trap to OS: Control transfers to the OS page fault handler. The CPU state (registers, PC) is saved.
Step 4 — Verify Legal Access: The OS checks if the access is legitimate (valid page for this process). If illegal
→ abort process with segmentation fault.
Step 5 — Find Free Frame: The OS finds a free frame in physical memory using a free-frame list. If no free
frame → page replacement algorithm selects a victim.
Step 6 — Load Page from Disk: The OS issues a disk I/O request to load the required page from the swap
space into the chosen frame.

AL3452 — Operating Systems | Answer Script Page 11

 Step 7 — Update Page Table: After loading, the page table entry is updated: frame number is set and valid bit
is set to 1. TLB is also updated.
Step 8 — Restart Instruction: The faulting instruction is restarted. This time the page is in memory, so
execution proceeds normally.

Performance of Demand Paging

Effective Access Time (EAT) is calculated as:
EAT = (1 − p) × memory access time + p × page fault service time
where p is the page fault rate (0 ≤ p ≤ 1). Page fault service time includes disk seek time (~8ms) + rotational
latency (~4ms) + transfer time (~0.1ms) + OS overhead, totalling ~8–20 ms. Even a page fault rate of 1/1000
can increase EAT by 40× over normal memory access (~100 ns), highlighting the importance of minimising
page faults.

Advantages of Demand Paging

• Processes can be larger than available physical memory (virtual memory illusion).
• Faster process startup — only the initial pages need to be loaded.
• More processes can reside in memory simultaneously (higher degree of multiprogramming).
• Pages never accessed are never loaded, saving memory bandwidth.

Disadvantages
• Page faults introduce high latency (disk I/O is slow).
• Thrashing can occur if the working set is larger than available frames.
• Requires special hardware support (MMU, valid-invalid bits) and OS complexity.

Pre-paging vs Demand Paging

Pre-paging loads some pages before they are referenced (e.g., pages likely to be used based on working set
from last run). Pure Demand Paging starts with no pages in memory and loads only on fault. Most real OS use
a hybrid approach — a few pages are pre-loaded at process start, then demand paging takes over.

— End of Answer Script —

AL3452 — Operating Systems | Answer Script Page 12