Q1. Differentiate between Logical and Physical Address Space.

Detail the five key

requirements of Memory Management.
Answer:
A fundamental concept in operating systems is the abstraction of memory. To securely and
efficiently run multiple programs, the OS decouples the addresses a program uses from the actual
hardware addresses.
●​ Logical Address (Virtual Address): This is the address generated by the CPU during
program execution. The application developer and the compiled program only ever see
logical addresses. The set of all logical addresses generated by a program is the Logical
Address Space.
●​ Physical Address: This is the actual, tangible address seen by the memory hardware (the
RAM chips). The set of all physical addresses corresponding to the logical addresses is the
Physical Address Space.

To successfully map logical addresses to physical addresses, an Operating System's memory

management module must satisfy five critical requirements:
1.​ Relocation: In a multiprogramming system, a program's location in main memory is not
known at compile time. Furthermore, a process may be swapped out to disk and later
swapped back into a different physical location. Therefore, the OS must be able to
dynamically translate (relocate) logical references into exact physical memory addresses at
execution time.
2.​ Protection: The OS must guarantee that a process cannot read or write to the memory space
of another process (or the OS kernel) without explicit permission. Because processes are
relocated dynamically, absolute addresses cannot be checked at compile time; protection
must be enforced by hardware at run time during every memory access.
3.​ Sharing: While protection is crucial, the OS must also allow controlled sharing. If multiple
processes are running the same application (e.g., three users running the same text editor),
they should share the same copy of the executable code in memory rather than loading three
separate copies, thereby conserving RAM.
4.​ Logical Organization: Main memory is physically organized as a linear, one-dimensional
array of bytes. However, software is written in logical modules (main program, math
library, user interface). The OS should handle memory in a way that reflects this modularity,
allowing modules to be independently compiled, protected (e.g., marking a code module as
read-only), and shared.
5.​ Physical Organization: The hierarchy of memory (fast/volatile RAM vs. slow/persistent
Disk) must be managed seamlessly by the OS. The programmer cannot be burdened with
 manually moving data between RAM and the disk when memory runs out.

Q2. Analyze Memory Partitioning techniques: Fixed Partitioning versus Dynamic

Partitioning.
Answer:

Early operating systems managed memory by dividing it into contiguous chunks called
partitions.

Fixed Partitioning

In this primitive scheme, the main memory is divided into a set of static, non-overlapping
partitions established at system boot time. Each partition can hold exactly one process. The
maximum degree of multiprogramming is rigidly limited by the number of partitions.
●​ Equal-Size Partitions: Every partition is the exact same size. Flaw: A massive program
might not fit in any partition, forcing the programmer to use complex overlays. Conversely,
a tiny program will occupy an entire massive partition, leading to severe wasted space
inside the partition (Internal Fragmentation).
●​ Unequal-Size Partitions: Memory is divided into partitions of varying sizes (e.g., 2MB,
4MB, 8MB). This partially mitigates the problem by allowing the OS to place smaller jobs
 in smaller partitions, slightly reducing internal fragmentation.

Dynamic Partitioning

To overcome the rigid limitations of fixed partitioning, dynamic partitioning was introduced.
Here, partitions are not created at boot time. Instead, they are created dynamically, with variable
lengths and numbers.
●​ Mechanism: When a process arrives, the OS allocates it a chunk of memory exactly the size
it requested—no more, no less.
●​ Hole Management: The OS maintains a linked list of allocated memory blocks and free
memory blocks, known as "holes."
●​ Flaw: As processes continually enter, execute, and terminate, they leave behind scattered
holes of various sizes. Eventually, the free memory becomes fragmented into tiny, unusable
holes scattered throughout the RAM. This leads to severe External Fragmentation.

Q3. Explain the Dynamic Storage Allocation Algorithms and the Buddy System.
Answer:
In dynamic partitioning, when a process requests $n$ bytes of memory, the OS must search its
list of free "holes" and select one. It uses placement algorithms to make this decision:
●​ First-fit: The OS scans the list from the beginning and allocates the first hole it finds that is
large enough. Pros: Extremely fast. Cons: Tends to clutter the beginning of memory with
 tiny, fragmented leftover holes.
●​ Best-fit: The OS scans the entire list and allocates the hole that is closest in size to the
request (the smallest hole that is big enough). Pros: Saves larger holes for future massive
processes. Cons: Slower because it must search the whole list, and it leaves behind
microscopic, useless leftover holes.
●​ Worst-fit: The OS scans the entire list and allocates the absolutely largest hole available.
Pros: The leftover hole is usually large enough to be useful for another process. Cons: It
rapidly depletes the largest available contiguous blocks.
●​ Next-fit: A variant of First-fit. It begins its search from the exact location where the last
search ended, rather than starting from the beginning. This helps distribute fragmentation
evenly across the memory.

The Buddy System

The Buddy System is a compromise between fixed and dynamic partitioning, utilizing a
power-of-2 memory allocator.

●​ Allocation: Memory requests are always satisfied in block sizes that are an exact power of
2 (e.g., 4KB, 8KB, 16KB). If a process requests 10KB, the system mathematically rounds it
up to the next power of 2, allocating a 16KB block.
●​ Splitting: If a 16KB block is needed but only a 64KB block is free, the system recursively
splits the 64KB block in half into two 32KB "buddies", and splits one of those into two
16KB buddies to satisfy the request.
●​ Coalescing (Advantage): When memory is freed, the system checks if its adjacent "buddy"
is also free. If so, they are instantly merged (coalesced) back into a larger power-of-2 block,
rapidly preventing external fragmentation.
●​ Disadvantage: Because it rounds up requests (giving 16KB to a 10KB request), it suffers
from severe Internal Fragmentation.

Q4. Define Fragmentation. Distinguish between Internal and External Fragmentation and
their solutions.
Answer:

Fragmentation is a phenomenon where memory space becomes wasted and unusable, severely
degrading system performance.
1.​ Internal Fragmentation:

○​ Definition: This occurs when the physical memory block allocated to a process is
strictly larger than the memory actually requested by the process.
○​ Mechanism: The unused space is "internal" to the allocated partition. Because the
partition belongs to the process, the OS cannot give that empty space to anyone else.
○​ Occurrence: It happens heavily in Fixed Partitioning, the Buddy System, and Paging.
2.​ External Fragmentation:
○​ Definition: This exists when the total amount of free memory in the system is large
enough to satisfy a new process's request, but this memory is not contiguous (it is
scattered in tiny chunks).
○​ Mechanism: The OS must reject the process because it requires a single, continuous
block of RAM.
○​ Occurrence: It is the primary flaw of Dynamic Partitioning and pure Segmentation.
○​ Solutions: * Compaction: The OS aggressively shuffles memory contents to slide all
active processes to one end of the RAM, combining all free holes into one massive
contiguous block. This is computationally expensive and requires dynamic relocation
capability.
■​ Paging/Segmentation: The modern solution is to eliminate the requirement that a
process must be stored contiguously in memory.
Q5. Explain the Paging architecture, Address Translation, and the critical role of the TLB.
Answer:

The Concept of Paging

Paging is a memory management scheme that completely eliminates external fragmentation by
allowing a process's physical memory to be non-contiguous.
●​ Frames: Physical memory (RAM) is divided into fixed-sized physical blocks called frames.
●​ Pages: Logical memory (the process) is divided into blocks of the exact same size called
pages.
●​ When a process needs to run, its pages are loaded into any available physical frames,
regardless of whether those frames are next to each other.
Address Translation Architecture

Every logical address generated by the CPU is mathematically divided into two parts:
1.​ Page Number ($p$): Used as an index to access a data structure called the Page Table. The
page table contains the physical base address (frame number) where that specific page is
currently stored in RAM.
2.​ Page Offset ($d$): The exact displacement or location of the byte within that page.​
The memory management unit (MMU) takes the physical frame number from the table and
combines it with the offset $d$ to define the exact physical RAM address.

The TLB and the Two-Memory-Access Problem

●​ The Problem: The page table itself is huge and must be stored in main memory. Therefore,
to read a single variable, the CPU must access memory twice: First, to read the page table to
find the frame, and Second, to actually read the variable. This cuts system speed in half.
●​ The Solution (TLB): To solve this, the OS uses specialized, ultra-fast, expensive hardware
caching called a Translation Look-aside Buffer (TLB) or Associative Memory.
●​ The TLB stores a small subset of the most recently used Page-to-Frame translations. When
the CPU generates an address, it queries the TLB in parallel.
○​ TLB Hit: If the page number is found in the TLB, the frame is retrieved instantly.
○​ TLB Miss: If not found, the system accesses the page table in RAM, retrieves the
frame, and updates the TLB for future use.
Q6. Detail Advanced Page Table Structures: Hierarchical, Hashed, and Inverted Page
Tables.
Answer:
Modern computers use massive 32-bit or 64-bit logical address spaces. This causes the page
tables themselves to become excessively large, consuming megabytes of contiguous RAM just to
store the table. OS designers use advanced structures to manage this.
Hierarchical (Two-Level) Page Tables:
○​ Instead of one giant page table, the OS "pages the page table."
○​ The logical address is split into three parts. The first part indexes into an Outer Page
Table. The entry in the outer table points to an Inner Page Table. The inner page table
finally yields the physical frame. This prevents the OS from having to keep the entire
page table continuously in memory.
Hashed Page Tables:

○​ Highly effective for address spaces greater than 32 bits.

○​ The virtual page number is passed through a mathematical hash function. The result
points to a specific entry in the Hashed Page Table.
○​ Because multiple page numbers might hash to the same location (collisions), each entry
contains a linked list. The system traverses the linked list, comparing the requested
virtual page number to the items in the list until it finds a match and extracts the
physical frame.
 Inverted Page Tables:

○​ Standard page tables have one entry for every virtual page of the process (which can be
millions of entries).
○​ An inverted page table has exactly one entry for every physical frame in the actual
RAM.
○​ The entry stores the virtual address that is currently occupying that physical frame,
along with the Process ID.
○​ Advantage: It drastically reduces the memory required to store the page table.
○​ Disadvantage: When a process asks for a virtual page, the OS must search the entire
inverted table to find which frame holds it, which is painfully slow unless combined
with a hash table.

Q7. What is Segmentation? Compare it with Paging, and explain Segmentation with
Paging.
Answer:
Segmentation
While paging is a hardware-driven concept, segmentation is a user-driven memory management
scheme. It reflects how a programmer actually views a program. A program is not a linear array
of bytes; it is a collection of logical segments like the Main Program, the Stack, the Math
Library, and global variables.
●​ A logical address is a two-tuple: <segment-number, offset>.
●​ The Segment Table maps this to physical RAM. Because segments are logically different
sizes, each entry in the table must contain two things:
1.​ Base: The exact physical starting address of the segment in RAM.
2.​ Limit: The exact length of the segment.
●​ Protection: The hardware checks every memory request. If the offset is greater than the
Limit, the OS traps the error (Segment Violation), preventing the process from reading
outside its segment.

Paging vs. Segmentation

 ●​

Hybrid: Segmentation with Paging

To harness the logical benefits of segmentation (protection and sharing) while avoiding external
fragmentation, OS designers combined them.
●​ In this hybrid system, the logical address still provides a segment number. However, the
Segment Table entry does not contain a physical base address.
●​ Instead, each segment is internally broken down into fixed-size pages. The Segment Table
points to the base address of a Page Table dedicated solely to that segment.

Q8. Explain Virtual Memory, Demand Paging, and the exact steps for Handling a Page
Fault.
Answer:
Virtual Memory & Demand Paging
●​ Virtual Memory is a revolutionary architectural concept that completely separates the
user's logical memory from physical RAM. It creates the illusion of a massive, contiguous
memory space, even if the physical RAM is quite small. It allows programs to run even if
they are larger than the physical RAM.
●​ Demand Paging is the primary way Virtual Memory is implemented. Instead of loading the
entire program into RAM at startup, the OS uses a "lazy swapper." It only brings a page into
RAM from the hard disk exactly when the CPU explicitly demands (accesses) it.

Handling a Page Fault

The OS uses a Valid-Invalid bit in the page table to track things. If the bit is 1 (Valid), the page
is in RAM. If the bit is 0 (Invalid), the page is either illegal or currently sitting on the hard disk.
Accessing an invalid page triggers a Page Fault. The OS handles this in six strict steps:
1.​ Trap: The memory hardware detects the invalid bit and traps to the OS kernel.
2.​ Check: The OS checks internal tables to determine if the reference was an illegal memory
access (abort program) or just a valid page currently residing on the backing store (disk).
3.​ Find Frame: The OS searches the RAM to find a free physical frame.
4.​ Read: The OS schedules a disk operation to read the desired page from the hard disk into
the newly found free frame.
5.​ Update: Once the disk read completes, the OS updates the page table, mapping the page to
the new frame and changing the Valid-Invalid bit to 1.
6.​ Restart: The OS restarts the exact CPU instruction that was interrupted by the page fault,
allowing the program to continue as if the page had always been in memory.
Note on Thrashing: If the system does not have enough physical frames to support the active
processes, it will constantly trigger page faults. The OS spends all its time reading and writing
pages to the disk instead of executing user code. This severe performance collapse is called
Thrashing.

Q9. Discuss the primary Page Replacement Algorithms: FIFO, Optimal, and LRU.
Answer:
During demand paging, if a page fault occurs and the OS discovers that RAM is completely full
(no free frames), it must execute a Page Replacement Algorithm to select a "victim" frame, evict
it to the disk, and load the new page in its place.
1.​ FIFO (First-In-First-Out) Algorithm:
○​ Concept: The simplest algorithm. The OS maintains a queue of all pages in memory.
When a replacement is needed, it simply evicts the oldest page (the one at the head of
the queue) that was brought into memory first.
○​ Flaw (Belady's Anomaly): FIFO is blind to how heavily a page is used. Furthermore, it
suffers from Belady's Anomaly: mathematically, providing the system with more
physical RAM frames can paradoxically result in more page faults for certain access
patterns.
2.​ Optimal Page Replacement Algorithm (OPT):
○​ Concept: This algorithm dictates that the OS should replace the page that will not be
used for the longest period of time in the future.
○​ Reality: It guarantees the absolute lowest possible page fault rate and does not suffer
from Belady's Anomaly. However, it is impossible to implement in reality because the
OS cannot predict the future execution path of a program. It is used strictly as a
benchmark to test the efficiency of other algorithms.
3.​ Least Recently Used (LRU) Algorithm:
○​ Concept: Since the OS cannot predict the future, it uses the past as a predictor. LRU
replaces the page that has not been used for the longest period of time in the past.
○​ Implementation: It requires significant hardware assistance to track when pages are
used. One method uses Counters: Every page table entry has a time-of-use register.
Every time a page is read or written, the current clock time is copied into the register.
During a page fault, the OS scans all registers and evicts the page with the smallest
(oldest) time value.
Q10. Define the following OS terminologies: Coalescing, Overlays, and Locality of
Reference.
Answer:
●​ Coalescing: In dynamic memory allocation (and specifically the Buddy System), coalescing
is a defragmentation technique. When a process finishes and frees its memory block, the OS
checks if the physically adjacent blocks are also free. If they are, the OS mathematically
merges (coalesces) them into a single, much larger free memory block. This actively
combats external fragmentation.
●​ Overlays: Historically, before Virtual Memory was invented, physical RAM was extremely
small. If a program was larger than RAM, the programmer had to manually split the
program into independent modules. The OS would load one module (overlay), run it, and
when finished, completely overwrite it in memory with the next required module. It placed a
massive burden on the programmer.
●​ Locality of Reference: This is a fundamental principle of computer science stating that
computer programs do not access their address space randomly; they exhibit predictable
clustering. Virtual memory and caches rely entirely on this principle.
○​ Temporal Locality (Time): If a specific memory location is referenced, it is highly
likely that the exact same location will be referenced again very soon in the future (e.g.,
executing a for loop, or updating a counter variable).
○​ Spatial Locality (Space): If a specific memory location is referenced, it is highly likely
that memory locations immediately adjacent to it will be referenced shortly (e.g.,
iterating through elements in an Array, or reading instructions sequentially). To exploit
this, hardware brings in whole blocks of data into the cache rather than single bytes.