Long Answer Questions on File Systems and Memory

Management

May 31, 2025

Set 1: File Systems Long Answer Questions (4 Marks & 8 Marks)

1. Explain what is File? Explain File Attributes and Structure.
A file is a named collection of data stored on a storage device, such as a hard disk or
SSD, managed by the operating system. It can store various types of data, including
text, images, videos, or programs, and is associated with metadata such as name, size,
and permissions.
File Attributes:
• Name: The identifier of the file (e.g., ”[Link]”).
• Size: The amount of storage the file occupies (e.g., 2 MB).
• Type: The file format (e.g., .txt, .jpg, .exe).
• Location: The path where the file is stored (e.g., /home/user/docs).
• Permissions: Access rights (e.g., read, write, execute for owner, group, others).
• Timestamps: Creation, modification, and last access dates.
• Hidden/Read-Only Flags: Indicators for visibility or editability.
File Structure:
• Unstructured (Byte Stream): Treated as a sequence of bytes with no internal struc-
ture (e.g., text files in UNIX).
• Structured: Divided into records or blocks (e.g., database files with fixed-length
records).
• Tree or Indexed Structure: Used in complex files (e.g., a PDF with an index for
pages).
The operating system and file system (e.g., NTFS, FAT32) determine how the file’s data
is stored and accessed on disk.

1
2. Explain File Operations.
File operations are actions that can be performed on a file, interacting with the file system
and often updating metadata (e.g., timestamps, permissions):
• Create: Allocates space on disk and adds the file to a directory.
• Open: Prepares the file for access by creating a file descriptor or handle.
• Read: Retrieves data from the file into memory.
• Write: Adds or modifies data in the file.
• Delete: Removes the file from the directory and frees its disk space.
• Close: Releases system resources associated with the file.
• Rename: Changes the file’s name in the directory.
• Copy/Move: Duplicates the file or relocates it to another directory.
Each operation involves interaction with the file system to ensure data integrity and
consistency.

3. Write a note on Internal File Structure.

The internal file structure refers to how data is organized within a file, which affects how
the operating system and applications read or write data:
• Byte Stream: No internal structure; treated as a sequence of bytes (e.g., UNIX text
files). This is the simplest form, allowing flexible reading and writing.
• Record-Based: Data is divided into fixed or variable-length records (e.g., database
files). Each record may represent a row or entry.
• Tree or Indexed Structure: Used in complex files, such as a PDF, where an index
points to different sections (e.g., pages or objects).
For example, a text editor reads a text file as a stream, while a database system uses
an indexed structure for quick lookups. The file system determines how this structure is
mapped to disk blocks.

4. Explain Directory Structure.

A directory structure organizes files in a file system, balancing complexity, flexibility, and
efficiency:
• Single-Level Directory: All files are stored in a single directory with no subdirecto-
ries. It’s simple but leads to name conflicts and poor scalability.
• Two-Level Directory: A root directory contains user-specific directories (e.g., /user1,
/user2). It avoids name conflicts but lacks deeper hierarchy.
• Tree-Structured Directory: Organizes files hierarchically, allowing subdirectories
(e.g., /home/user/docs). It’s flexible and scalable, used in modern systems like
Windows and Linux.

2
 • Acyclic Graph Directory: Extends the tree structure by allowing shared files or
directories (links) without cycles. It saves storage but is complex to manage.
• General Graph Directory: Allows cycles in the structure (e.g., via symbolic links).
It’s highly flexible but risks infinite loops during traversal.
For example, a tree-structured directory is common in modern operating systems for its
balance of organization and accessibility.

5. Explain File Allocation Methods.

File allocation methods determine how a file’s data is stored on disk:
• Contiguous Allocation: The file occupies consecutive blocks.
– Advantages: Fast access (minimal seek time); simple to implement for sequen-
tial read/write.
– Disadvantages: External fragmentation (free space becomes scattered); file
size must be known in advance; hard to grow files.
• Linked Allocation: Each block contains a pointer to the next block, forming a linked
list.
– Advantages: No external fragmentation; files can grow dynamically by adding
blocks.
– Disadvantages: Slow sequential access (must follow pointers); inefficient for
random access; pointer overhead; risk of data loss if a pointer is corrupted.
• Indexed Allocation: A single index block stores pointers to all file blocks.
– Advantages: Fast random access; no external fragmentation.
– Disadvantages: Extra space for the index block; limited file size (based on
index size).
For example, contiguous allocation is efficient for sequential access but impractical for
dynamic files, while indexed allocation suits random access but requires more overhead.

6. Explain Free Space Management and techniques to implement a free

space list.
Free Space Management tracks unallocated disk space to allocate to new files. The
operating system maintains a free space list to manage this space efficiently.
Techniques to Implement a Free Space List:
• Bit Vector (Bitmap): A binary array where each bit represents a disk block (1 =
free, 0 = allocated). It’s simple but requires scanning to find free blocks.
• Linked List: Free blocks are linked together, with each block pointing to the next
free block. It’s easy to allocate but slow to traverse for large disks.
• Grouping: Stores addresses of free blocks in the first free block, with a pointer to
the next group of free blocks. It’s faster than a linked list for finding free space.

3
 • Counting: Keeps a list of starting addresses of free block groups and their counts
(e.g., 5 free blocks starting at block 100). It’s efficient for contiguous allocation.
For example, a bit vector is space-efficient for small disks, while counting is better for
large disks with contiguous free spaces.

7. Explain Directory Implementation.

Directory implementation refers to how directories are stored and managed in a file
system:
• Linear List: A simple list of file names and their metadata (e.g., pointers to data
blocks). It’s easy to implement but slow for searching, as it requires a linear scan.
• Hash Table: Uses a hash function to map file names to entries, enabling faster
lookups. However, it may suffer from collisions, requiring resolution mechanisms.
• B-Tree: A tree structure used for large directories (e.g., in NTFS). It’s efficient for
searching, insertion, and deletion, especially in large file systems.
For example, FAT32 uses a linear list, which is simple but slow, while NTFS uses B-trees
for better performance in large directories.

8. Explain Protection of File and Directory.

Protection ensures that files and directories are accessed only by authorized users, safe-
guarding data integrity and privacy.
Mechanisms:
• Permissions: Define read, write, and execute rights for the owner, group, and others
(e.g., in UNIX, chmod 644 [Link] gives the owner read/write and others read-only
access).
• Access Control Lists (ACLs): A list specifying permissions for individual users or
groups, offering fine-grained control.
• Role-Based Access: Assigns permissions based on user roles (e.g., admin, user).
• Encryption: Protects file contents by requiring a key to access, ensuring data con-
fidentiality.
For example, in Linux, a user might set permissions to restrict access to sensitive files,
while encryption protects against unauthorized access even if the file is stolen.

9. Explain Protection of File and Directory Structure.

Protecting the file and directory structure ensures the integrity of the file system, pre-
venting corruption or unauthorized modifications:
• Consistency Checks: Tools like fsck (in Linux) or chkdsk (in Windows) verify and
repair directory structures after a crash.
• Access Control: Limits who can modify the directory (e.g., only admins can create
subdirectories), preventing unauthorized structural changes.

4
 • Redundancy: Stores directory metadata in multiple locations to recover from cor-
ruption.
• Logging: File systems like NTFS use logs to track changes, allowing recovery of the
directory structure after failures.
For example, if a system crashes during a directory update, journaling can restore the
directory structure without data loss.

10. Write a note on Recovery of File System.

Recovery of a file system involves restoring it to a consistent state after a failure, such as
a crash or corruption, to prevent data loss and ensure system reliability.
Techniques:
• Journaling: Logs changes before they are applied (e.g., in ext3/ext4 file systems).
After a crash, the journal is replayed to fix inconsistencies.
• Checkpoints: Periodic snapshots of the file system state, allowing rollback to a
consistent state.
• Backup and Restore: Uses backups to recover lost or corrupted data, ensuring data
availability.
• Consistency Checking: Tools like fsck or chkdsk scan and repair file system struc-
tures, fixing errors like orphaned files.
For example, if a system crashes during a file write, journaling ensures the file system
can recover by either completing or undoing the operation, preventing corruption.

Set 2: Memory Management Long Answer Questions (4 Marks &

8 Marks)
1. Discuss LRU-Approximation Page Replacement.
The Least Recently Used (LRU)-Approximation page replacement strategy approximates
the LRU algorithm, which replaces the page not used for the longest time. True LRU is
resource-intensive, requiring tracking the exact order of page accesses.
A common LRU-Approximation method is the Second-Chance (Clock) Algorithm:
• Each page has a reference bit, set to 1 when accessed.
• A pointer moves through page frames in a circular manner (like a clock).
• When a page needs to be replaced:
– If the reference bit is 0, replace the page.
– If the bit is 1, reset it to 0, move to the next page, and give the current page
a ”second chance.”
• Continue until a page with a reference bit of 0 is found.

5
Advantages:
• Lower overhead than true LRU (no timestamps or full stack needed).
• Approximates LRU by prioritizing pages with less recent activity.
Disadvantages:
• Less accurate than true LRU; may evict recently used pages if their reference bit
was reset.
• Performance depends on the clock pointer’s speed and access frequency.
Example: For a reference string 1, 2, 3, 4, 1, 2, 5 with 3 frames, the second-chance
algorithm cycles through frames, resetting bits, and replaces pages with a bit of 0.

2. What is swapping and what is its purpose?

Swapping is a memory management technique where a process (or part of a process) is
moved between main memory (RAM) and secondary storage (e.g., a swap space on disk).
A swapped-out process is temporarily removed from RAM to free space, and swapped
back in when needed.
Purpose of Swapping:
• Memory Overcommitment: Allows running more processes than can fit in RAM by
moving inactive processes to disk.
• Multitasking: Enables the operating system to switch between processes, prioritiz-
ing active ones.
• Handling Memory Shortages: Frees RAM to prevent crashes when memory is over-
allocated.
• Support for Virtual Memory: Swapping enables virtual memory by moving pages
to disk when physical memory is full.
Example: A system with 4 GB RAM running processes needing 6 GB can swap less
active processes to disk, freeing RAM for active ones.

3. Explain paging scheme for memory management, discuss the paging

hardware and Paging model.
Paging Scheme for Memory Management: Paging divides a process’s virtual address space
into fixed-size units called pages, and physical memory into corresponding page frames.
Pages are mapped to frames using a page table, eliminating external fragmentation.
Steps in Paging:
1. The CPU generates a virtual address (page number + offset).
2. The page number indexes the page table to find the frame number.
3. The physical address is computed by combining the frame number and offset.
Paging Hardware:

6
 • Page Table: Stored in memory, maps virtual page numbers to physical frame num-
bers.
• Translation Lookaside Buffer (TLB): A hardware cache storing recent page table
entries for faster address translation.
• Memory Management Unit (MMU): Hardware that translates virtual addresses to
physical addresses using the page table.
• Registers: Page table base register (PTBR) points to the page table; page table
length register ensures valid page numbers.
Paging Model:
• Virtual Address: Divided into a page number (indexes the page table) and an offset
(position within the page).
• Physical Address: Frame number (from the page table) + offset.
• Page Fault: If a page is not in memory, the OS fetches it from disk, updates the
page table, and resumes the process.
Example: A 32-bit virtual address with 4 KB pages uses 20 bits for the page number
(220 × 4 KB = 4 GB) and 12 bits for the offset (212 = 4 KB).

4. Explain about contiguous memory allocation?

Contiguous Memory Allocation allocates each process a single, continuous block of mem-
ory in RAM.
Key Features:
• The operating system maintains a list of free memory blocks (holes).
• When a process requests memory, the OS finds a hole large enough to accommodate
it.
• The process is loaded into that contiguous block.
Allocation Strategies:
• First-Fit: Allocate the first hole that is large enough.
• Best-Fit: Allocate the smallest hole that fits the process.
• Worst-Fit: Allocate the largest hole.
Advantages:
• Simple to implement.
• Fast access (no need for address translation like in paging).
Disadvantages:
• External Fragmentation: Free memory becomes scattered, making it hard to allo-
cate large blocks.
• Internal Fragmentation: Unused space within an allocated block is wasted.

7
 • Processes cannot grow easily if more memory is needed later.
Example: If memory has holes of 100 KB, 50 KB, and 200 KB, and a process needs 75 KB,
first-fit allocates it to the 100 KB hole, leaving 25 KB unused (internal fragmentation).

5. Explain about first fit, best fit, worst fit, next fit algorithms?
These are strategies for allocating memory in contiguous memory allocation:
First-Fit:
• Allocates the first free memory block (hole) that is large enough for the process.
• Advantage: Fast (stops at the first suitable hole).
• Disadvantage: Can lead to external fragmentation as small holes are left scattered.
• Example: Holes: 100 KB, 50 KB, 200 KB; Process: 75 KB → Allocates to 100 KB
(first hole).
Best-Fit:
• Allocates the smallest hole that is large enough for the process.
• Advantage: Minimizes wasted space (less internal fragmentation).
• Disadvantage: Slow (must search the entire list); creates tiny, unusable holes (ex-
ternal fragmentation).
• Example: Holes: 100 KB, 50 KB, 200 KB; Process: 75 KB → Allocates to 100 KB
(smallest fit).
Worst-Fit:
• Allocates the largest hole available.
• Advantage: Leaves larger remaining holes, useful for future large processes.
• Disadvantage: Slow (requires full list search); can lead to external fragmentation.
• Example: Holes: 100 KB, 50 KB, 200 KB; Process: 75 KB → Allocates to 200 KB
(largest hole).
Next-Fit:
• Similar to first-fit but starts searching from the last allocated position.
• Advantage: Faster than first-fit over time (doesn’t always start from the beginning).
• Disadvantage: May miss better fits earlier in the list; still causes external fragmen-
tation.
• Example: Last allocation at 50 KB; Holes: 100 KB, 50 KB, 200 KB; Process: 75
KB → Starts at 50 KB, allocates to 200 KB.

8
6. Explain about advantages and disadvantages of paging? And Explain
difference between paging and segmentation?
Advantages of Paging:
• No External Fragmentation: Pages can be placed anywhere in memory (non-
contiguous allocation).
• Efficient Memory Usage: Fixed-size pages make allocation straightforward.
• Supports Virtual Memory: Pages can be swapped to disk, allowing more processes
to run.
• Simplifies Swapping: Pages can be easily swapped in/out without worrying about
contiguous memory.
Disadvantages of Paging:
• Internal Fragmentation: If a process doesn’t use the entire page, the remaining
space is wasted (e.g., a 3 KB process in a 4 KB page wastes 1 KB).
• Page Table Overhead: Each process needs a page table, which consumes memory.
• Translation Overhead: Address translation adds a small delay, though mitigated
by TLB.
Difference Between Paging and Segmentation:
• Definition:
– Paging: Divides memory into fixed-size pages; process address space is split
into pages.
– Segmentation: Divides memory into variable-size segments (e.g., code, data,
stack).
• Memory Allocation:
– Paging: Non-contiguous; pages can be scattered.
– Segmentation: Can be contiguous or non-contiguous (with segment tables).
• Fragmentation:
– Paging: No external fragmentation, but internal fragmentation exists.
– Segmentation: External fragmentation (free memory may not fit segment
sizes), no internal fragmentation.
• Address Space:
– Paging: Uses a single address space (page number + offset).
– Segmentation: Uses a logical address space (segment number + offset).
• Complexity:
– Paging: Simpler to implement (fixed sizes).
– Segmentation: More complex (variable sizes, logical mapping).

9
 • Example:
– Paging: A 16 KB process split into 4 pages of 4 KB each.
– Segmentation: A program with a 10 KB code segment, 4 KB data segment.

7. Explain about Linux memory management?

Linux Memory Management is a sophisticated system to handle processes efficiently,
leveraging paging, virtual memory, and swapping:
• Virtual Memory: Each process gets its own virtual address space, mapped to phys-
ical memory via page tables.
• Paging: Linux uses paging (typically 4 KB pages); the kernel maintains page tables
for each process.
• Page Replacement: Uses an LRU-based algorithm (approximated via Active/Inactive
List):
– Pages are divided into active (recently used) and inactive (less used) lists.
– The kernel swaps out pages from the inactive list when memory is low.
• Swapping: Uses a swap space on disk to move pages out of RAM when memory is
full.
• Buddy System: Manages free memory blocks, reducing fragmentation.
• Slab Allocator: Efficiently manages small kernel objects.
• Memory Zones: Divides memory into zones (DMA, Normal, HighMem) for hard-
ware constraints.
• OOM Killer: Terminates processes if memory is critically low.
Example: When a process requests memory, the kernel allocates pages, updates the page
table, and maps virtual addresses to physical frames.

8. Explain about the following page replacement algorithms a) FIFO b)

OPR, c) LRU.
a) FIFO (First-In, First-Out):
• Replaces the page that has been in memory the longest (first to arrive).
• Mechanism: Maintains a queue of pages; the oldest page is replaced.
• Advantage: Simple to implement.
• Disadvantage: Suffers from Belady’s Anomaly (more frames can lead to more page
faults); doesn’t consider page usage frequency.
• Example: Reference string: 1, 2, 3, 4, 1, 2, 5; 3 frames → Page faults: 1, 2, 3 → 4
(replaces 1) → 1 (replaces 2) → 2 (replaces 3) → 5 (replaces 4) = 6 faults.
b) OPR (Optimal Page Replacement):

10
 • Replaces the page that will not be used for the longest time in the future.
• Mechanism: Requires future knowledge of the reference string (not practical).
• Advantage: Minimizes page faults (theoretical best).
• Disadvantage: Impossible to implement in practice (future knowledge isn’t avail-
able).
• Example: Reference string: 1, 2, 3, 4, 1, 2, 5; 3 frames → Page faults: 1, 2, 3 → 4
(replaces 3, not used again) → 5 (replaces 4) = 4 faults.
c) LRU (Least Recently Used):
• Replaces the page that has not been used for the longest time.
• Mechanism: Tracks the order of page accesses (e.g., using a stack or timestamps).
• Advantage: Effective; considers actual usage patterns.
• Disadvantage: High overhead (requires tracking all accesses).
• Example: Reference string: 1, 2, 3, 4, 1, 2, 5; 3 frames → Page faults: 1, 2, 3 → 4
(replaces 3, least recent) → 5 (replaces 4) = 4 faults.

9. Differentiate local and global page replacement algorithm.

Local Page Replacement:
• Each process has a fixed number of frames, and page replacement occurs only within
those frames.
• Example: If a process has 3 frames, it can only replace pages within those 3 frames.
• Advantage: Fairness; one process cannot monopolize memory.
• Disadvantage: May not optimize overall system performance (some processes may
need more frames).
Global Page Replacement:
• Pages are replaced across all frames in the system, regardless of which process they
belong to.
• Example: A process needing a frame can replace a page from any process.
• Advantage: Better overall memory utilization (frames go to processes that need
them most).
• Disadvantage: Can lead to unfairness; a process may lose frames to another.
Comparison: Local ensures isolation but may underutilize memory; global optimizes
memory usage but can starve some processes.

10. What is virtual memory? Mention its advantages.

Virtual Memory gives each process the illusion of a large, contiguous address space, even
if physical memory is limited, by mapping virtual addresses to physical addresses and

11
using secondary storage (e.g., disk).
Mechanism:
• Uses paging or segmentation.
• Pages not in RAM are stored in a swap space on disk.
• When a page is needed, it’s brought into RAM (page fault handling).
Advantages:
• Runs More Processes: Allows more processes to run than can fit in RAM by swap-
ping pages to disk.
• Memory Isolation: Each process gets its own virtual address space, preventing
interference.
• Efficient Memory Usage: Only active pages need to be in RAM.
• Simplifies Programming: Programmers can use a large address space without wor-
rying about physical memory limits.
• Supports Multitasking: Processes can share physical memory efficiently.
Example: A system with 4 GB RAM can run a 6 GB process by swapping parts of it to
disk.

11. Differentiate external fragmentation with internal fragmentation.

Internal Fragmentation:
• Occurs when allocated memory is slightly larger than requested, and the unused
portion cannot be used by another process.
• Cause: Fixed-size allocation units (e.g., pages in paging).
• Example: A 3 KB process allocated a 4 KB page wastes 1 KB.
• Solution: Use smaller page sizes (but increases page table overhead).
External Fragmentation:
• Occurs when free memory is scattered in small, non-contiguous blocks, making it
unusable for large requests.
• Cause: Variable-size allocation (e.g., contiguous allocation or segmentation).
• Example: Free memory: 50 KB, 30 KB, 20 KB (total 100 KB); a 75 KB process
cannot be allocated.
• Solution: Compaction (move processes to consolidate free space) or use paging.
Comparison: Internal fragmentation wastes space within allocated blocks; external frag-
mentation wastes space between allocated blocks.

12
12. Write short notes on swapping.
Swapping moves a process (or its pages) between RAM and secondary storage (swap
space) to manage memory.
Key Points:
• Used in virtual memory systems to free up RAM for active processes.
• A swapped-out process is stored on disk and swapped back in when needed.
• Involves overhead (disk I/O is slower than RAM access).
Advantages:
• Allows more processes to run than can fit in RAM.
• Supports multitasking by prioritizing active processes.
Disadvantages:
• Slow (disk access is much slower than RAM).
• Can lead to thrashing if overused (frequent swapping).
Example: A system swaps out an idle process to disk to free RAM for a new process.

13. Briefly explain and compare, fixed and dynamic memory partitioning
schemes.
Fixed Memory Partitioning:
• Memory is divided into fixed-size partitions at system startup; each partition holds
one process.
• Features: Partitions are predefined (e.g., 5 partitions of 10 MB each).
• Advantages: Simple to implement; no external fragmentation within partitions.
• Disadvantages: Internal fragmentation (unused space in partitions); limited flexi-
bility.
Dynamic Memory Partitioning:
• Memory is allocated dynamically as processes arrive, creating partitions of the exact
size needed.
• Features: Partitions created/resized at runtime; uses strategies like first-fit.
• Advantages: No internal fragmentation; flexible for varying process sizes.
• Disadvantages: External fragmentation; requires compaction.
Comparison: Fixed partitioning is simpler but wastes space (internal fragmentation);
dynamic partitioning is more flexible but suffers from external fragmentation.

13
14. Explain with the help of examples FIFO and LRU, optimal page
replacement algorithms with example reference string. Mention the merits
and demerits of each of the above algorithm.
Reference String Example: 1, 2, 3, 4, 1, 2, 5 with 3 frames.
FIFO (First-In, First-Out):
• Explanation: Replaces the oldest page.
• Example: Frames: [ ] → [1] → [1, 2] → [1, 2, 3] → [2, 3, 4] (1 out) → [3, 1] (4 out)
→ [1, 2] (3 out) → [1, 2, 5] (3 out). Page Faults: 6.
• Merits: Simple to implement (just a queue).
• Demerits: Ignores usage patterns; may replace frequently used pages; suffers from
Belady’s Anomaly.
LRU (Least Recently Used):
• Explanation: Replaces the least recently used page.
• Example: Frames: [ ] → [1] → [1, 2] → [1, 2, 3] → [1, 2, 4] (3 out) → [2, 4, 1] (hit)
→ [4, 1, 2] (hit) → [1, 2, 5] (4 out). Page Faults: 4.
• Merits: Effective; considers usage patterns.
• Demerits: High overhead (requires tracking access order).
Optimal Page Replacement:
• Explanation: Replaces the page not used for the longest time in the future.
• Example: Frames: [ ] → [1] → [1, 2] → [1, 2, 3] → [1, 2, 4] (3 out) → [1, 2, 4] (hit)
→ [1, 2, 4] (hit) → [1, 2, 5] (4 out). Page Faults: 4.
• Merits: Minimizes page faults (optimal solution).
• Demerits: Impractical (requires future knowledge).

15. Explain how paging supports virtual memory. With neat diagram
explain how logical address is translated into physical address.
How Paging Supports Virtual Memory:
• Paging divides a process’s address space into pages, which can be mapped to phys-
ical frames or stored on disk.
• Pages not in RAM are stored in swap space.
• When a page is accessed, the OS brings it into RAM (page fault handling).
• The page table maps virtual pages to physical frames or indicates if a page is on
disk.
• Benefits: Processes can use more memory than physically available; pages can be
swapped as needed.

14
Logical to Physical Address Translation:
• Steps:
1. A logical (virtual) address consists of a page number and an offset.
2. The page number indexes the page table to find the frame number.
3. If the page is in memory, the frame number is combined with the offset to
form the physical address.
4. If the page is not in memory (page fault), the OS fetches it from disk, updates
the page table, and resumes.
• Diagram Description (Text-Based):
– CPU generates a virtual address: [Page Number | Offset].
– Page Table: An array mapping page numbers to frame numbers (or disk lo-
cations).
– Arrow from Page Number to Page Table: Look up the frame number.
– Physical Address: [Frame Number | Offset].
– TLB (optional): A cache for faster lookups.
• Example: Virtual Address: 0x00001000 (page size 4 KB). Page Number: 1; Offset:
0. Page Table Entry: Page 1 → Frame 5. Physical Address: 0x00005000.

16. Write about the techniques for structuring the page table.
Techniques for Structuring the Page Table:
• Single-Level Page Table:
– A single table maps all virtual pages to physical frames.
– Advantage: Simple to implement.
– Disadvantage: Large memory overhead (e.g., a 32-bit system with 4 KB pages
needs 220 entries, or 4 MB per process).
• Two-Level Page Table:
– Divides the page table into two levels: a page directory (outer table) and page
tables (inner tables).
– Virtual address: directory index, page index, offset.
– Advantage: Saves memory (only page tables for used pages are allocated).
– Disadvantage: Two memory accesses for translation (mitigated by TLB).
– Example: A 32-bit system might use 10 bits for the directory, 10 bits for the
page, and 12 bits for the offset.
• Multi-Level Page Table:
– Extends to more levels (e.g., three or four levels in 64-bit systems).

15
 – Advantage: Space-efficient for sparse address spaces.
– Disadvantage: More complex; slower due to multiple lookups.
• Hashed Page Table:
– Uses a hash table to map virtual page numbers to physical frames.
– Advantage: Efficient for large, sparse address spaces.
– Disadvantage: Hash collisions can slow down lookups.
• Inverted Page Table:
– One table for the entire system, mapping physical frames to virtual pages
(with process IDs).
– Advantage: Saves memory (proportional to physical memory).
– Disadvantage: Slower lookups (must search the table).

17. What is thrashing and explain the methods to avoid thrashing?

Thrashing occurs when a system spends more time swapping pages in and out of memory
than executing processes, due to excessive page faults.
Cause: Too many processes compete for limited physical memory, causing frequent page
faults.
Symptoms: High CPU idle time, low throughput, high disk I/O.
Methods to Avoid Thrashing:
• Increase Physical Memory: Add more RAM to reduce swapping.
• Reduce Multiprogramming: Limit active processes to ensure each has enough frames.
• Working Set Model: Allocate each process enough frames to hold its working set
(actively used pages). Suspend processes if the working set cannot fit.
• Page Fault Frequency (PFF): Monitor page fault rate; allocate more frames if too
high, reduce if too low.
• Better Page Replacement Algorithms: Use efficient algorithms (e.g., LRU) to min-
imize unnecessary page faults.
• Locality of Reference: Optimize programs for localized data access, reducing page
faults.
Example: A system with 4 GB RAM running 10 processes (each needing 1 GB) causes
thrashing. Reducing to 4 processes or adding RAM helps.

18. Explain the basic concepts of segmentation in detail.

Segmentation is a memory management technique that divides a process’s address space
into variable-size segments based on logical divisions (e.g., code, data, stack).
Key Concepts:

16
 • Segments: Each segment is a logical unit (e.g., a function, array, or stack).
• Segment Table: Maps segment numbers to physical memory (contains base address
and limit).
• Logical Address: Consists of a segment number and an offset.
• Address Translation:
1. The segment number indexes the segment table.
2. The offset is checked against the segment’s limit.
3. If valid, the offset is added to the base address to get the physical address.
Advantages:
• No internal fragmentation (segments are exact sizes).
• Logical separation (reflects program structure).
• Supports sharing (e.g., shared libraries as segments).
Disadvantages:
• External Fragmentation: Free memory may become scattered.
• More complex than paging (variable sizes).
Example: A process has segments: Code (10 KB), Data (4 KB), Stack (2 KB). Segment
Table: [0: (Base: 1000, Limit: 10 KB), 1: (Base: 15000, Limit: 4 KB), 2: (Base: 20000,
Limit: 2 KB)]. Logical Address: Segment 1, Offset 2000 → Physical Address: 15000 +
2000 = 17000.

17