Memory Management: Quick Review & Key Concepts
1. Memory Management Allocation Strategies
Contiguous Memory Allocation: Each process is contained in a single contiguous block of memory.
Fixed Partitioning: Memory is divided into fixed-size regions. Leads to Internal Fragmentation.
Variable (Dynamic) Partitioning: Memory partitions are allocated dynamically according to process size. Leads to External Fragmentation.
Dynamic Storage Allocation Algorithms:
First Fit: Allocates the first available hole that is big enough. (Fastest)
Best Fit: Allocates the smallest available hole that is big enough. (Leaves smallest leftover holes)
Worst Fit: Allocates the largest available hole. (Leaves largest leftover holes)
2. Fragmentation & Compaction
Internal Fragmentation: Unused space inside an allocated block or frame. (Occurs in Fixed Partitioning and Paging)
External Fragmentation: Total memory space exists to satisfy a request, but it is non-contiguous. (Occurs in Variable Partitioning and Segmentation)
Compaction: Technique to shuffle memory contents to place all free memory together in one large block to solve External Fragmentation.
3. Non-Contiguous Allocation: Paging vs. Segmentation
Logical Address (CPU) Physical Address (RAM)
+-----------------------+ +-----------------------+
| Page # | Offset | | Frame # | Offset |
+-----------------------+ +-----------------------+
| | ^ |
v | | |
[ Page Table ]----+--------------------------+ |
Maps Page -> Frame v
[ RAM Location ]
Paging:
Divides logical memory into fixed-sized blocks called Pages.
Divides physical memory into fixed-sized blocks called Frames ($\text{Page Size} = \text{Frame Size}$).
Page Table: Maps logical pages to physical frames.
Translates address: $\text{Logical Address} = (\text{Page Number } p, \text{Offset } d)$. $\text{Physical Address} = (\text{Frame Number } f, \text{Offset } d)$.
Suffers from Internal Fragmentation, but eliminates External Fragmentation.
Segmentation:
Divides memory based on the user/programmer view into variable-length segments (Code, Stack, Heap, Functions).
Segment Table: Stores $\text{Base}$ (starting physical address) and $\text{Limit}$ (length of segment).
Check condition: If $\text{Offset} \ge \text{Limit} \rightarrow$ Trap / Segment Fault.
Suffers from External Fragmentation.
4. Virtual Memory & Paging Mechanics
Virtual Memory: An abstraction technique that gives a process the illusion of having a large, contiguous memory space, using secondary storage (Swap Space / Disk) as an extension of RAM.
Demand Paging: Pages are loaded into RAM only when they are needed during execution.
Page Fault: Occurs when a program accesses a page that is marked invalid or is not currently present in RAM.
Page Fault Handling Sequence: Interrupt CPU $\rightarrow$ Save context $\rightarrow$ Locate page on disk $\rightarrow$ Find free frame in RAM $\rightarrow$ Fetch page from disk $\rightarrow$ Update Page Table $\rightarrow$ Restart instruction.
Translation Lookaside Buffer (TLB): A high-speed associative hardware cache inside the MMU used to store recent Page Table entries for fast address translation.
5. Page Replacement Algorithms & Thrashing
When a page fault occurs and no free frames exist in RAM, a page replacement algorithm selects a victim page to swap out:
FIFO (First-In, First-Out): Replaces the oldest page.
Belady's Anomaly: Peculiar phenomenon where increasing the number of physical memory frames results in an increase in the number of page faults (affects FIFO).
Optimal Page Replacement (OPT): Replaces the page that will not be used for the longest period of time in the future. (Theoretical benchmark; impossible to implement in real OS).
LRU (Least Recently Used): Replaces the page that has not been used for the longest time in the past. (Does NOT suffer from Belady's Anomaly).
Thrashing: A state where the CPU spends more time swapping pages in and out between RAM and disk than executing instructions. Caused when total working-set size exceeds available physical RAM.
Core Computer Science MCQs
What is the primary difference between Von Neumann and Harvard architecture?
Answer: Von Neumann architecture uses a single shared bus and memory space for both instructions and data, whereas Harvard architecture uses physically separate memories and buses for instructions and data.
What is the main cause of the "Von Neumann Bottleneck"?
Answer: The shared communication bus between the CPU and memory, which prevents simultaneous instruction fetching and data reading/writing.
Which memory component provides the fastest data access speed to the CPU?
Answer: CPU Registers (followed by L1 Cache).
In address translation, what is the function of the Memory Management Unit (MMU)?
Answer: To map logical (virtual) memory addresses generated by the CPU into physical RAM addresses.
What is the function of the Translation Lookaside Buffer (TLB)?
Answer: It acts as a hardware cache inside the MMU that stores recent page table entries to accelerate virtual-to-physical address translation.
In paging, what causes Internal Fragmentation?
Answer: When a process does not fully occupy the last fixed-size frame allocated to it, leaving unused space inside that frame.
How does External Fragmentation occur in dynamic memory allocation?
Answer: When total free memory is sufficient to fulfill a process allocation request, but the available space is split into non-contiguous blocks.
Which memory allocation strategy allocates the smallest hole that is large enough for a process?
Answer: Best Fit (Note: It leaves behind the smallest leftover free holes).
What is Belady's Anomaly, and which page replacement algorithm is susceptible to it?
Answer: Belady's Anomaly is the phenomenon where increasing physical RAM frames results in more page faults. It occurs in the FIFO (First-In, First-Out) replacement algorithm.
Which page replacement algorithm delivers the theoretical minimum page fault rate?
Answer: Optimal Page Replacement (OPT), which replaces the page that will not be used for the longest time in the future.
What is Thrashing in an Operating System?
Answer: A severe performance state where the system spends significantly more time swapping pages between RAM and disk than executing process code.
Which register stores the address of the next instruction to be fetched and executed?
Answer: Program Counter (PC).
What is the function of the Instruction Register (IR)?
Answer: It holds the instruction currently being decoded and executed by the CPU.
Which universal logic gates can implement any Boolean logic function independently?
Answer: NAND and NOR gates.
What are the outputs of a Half Adder circuit given inputs A and B?
Answer: $\text{Sum} = A \oplus B$ (XOR) and $\text{Carry} = A \cdot B$ (AND).
How many select lines are required for a 16-to-1 Multiplexer (16:1 MUX)?
Answer: 4 select lines ($2^4 = 16$).
What is the main operational difference between Combinational and Sequential circuits?
Answer: Combinational circuit outputs depend solely on current inputs, while Sequential circuit outputs depend on both current inputs and past states (stored in memory elements like Flip-Flops).
Which Flip-Flop is primarily used to eliminate the race-around condition in JK Flip-Flops?
Answer: Master-Slave JK Flip-Flop (or Edge-Triggered Flip-Flop).
What are the three main types of hazards in CPU pipelining?
Answer: Structural Hazards (resource contention), Data Hazards (data dependencies), and Control/Branch Hazards (branching delays).
According to Flynn's Taxonomy, modern multi-core processors belong to which class?
Answer: MIMD (Multiple Instruction, Multiple Data).
What is Direct Memory Access (DMA)?
Answer: A feature that allows I/O devices to transfer data directly to or from main RAM without continuously involving the CPU.
In Demand Paging, what triggers a Page Fault?
Answer: Accessing a logical page whose Valid/Invalid bit in the Page Table is set to 0 (meaning it is not currently loaded in physical RAM).
What does the "Dirty Bit" (Modify Bit) in a Page Table entry signify?
Answer: It indicates whether the page has been modified in RAM, determining if it must be written back to secondary storage when evicted.
In dynamic address binding, what is the condition for a Segmentation Fault?
Answer: When the address offset $d$ is greater than or equal to the Segment Limit ($\text{Offset} \ge \text{Limit}$).
Which addressing mode provides the fastest access to the operand?
Answer: Immediate Addressing Mode (the operand is part of the instruction itself).
What is the binary 2's complement representation of -5 using an 8-bit signed integer?
Answer:
11111011(1's complement of00000101is11111010; adding 1 gives11111011).
Where are dynamically allocated variables (e.g., using
malloc()in C) stored in memory?Answer: Heap Memory.
Where are local function variables and call-stack frames stored?
Answer: Stack Memory.
What is a Non-Maskable Interrupt (NMI)?
Answer: A high-priority hardware interrupt that cannot be delayed or ignored by the CPU (e.g., hardware failure signals).
What is the average internal fragmentation per process in a system with Page Size $P$?
Answer: $\frac{P}{2}$ bytes (half a page on average).
