Operating Systems Memory and Disk Management Comprehensive Study Guide

Examination Logistics, Guidelines, and Academic Integrity

• Course and Exam Identification: CS 4760 Operating Systems Test 3, Fall 2025. The examination covers critical memory management and disk storage concepts and accounts for a total of 57 points ($57\,pts$).

• Mandatory Requirements and Penalties:     - Identification: Students are required to write their names on the exam. Failure to do so results in a mandatory loss of five points ($5\,pts$).     - Calculations and Work: All calculations and rough work must be performed on the reverse (back side) of the test pages.     - Legibility Requirement: All written answers must be legible. If the instructor cannot read the script, a zero ($0$) will be awarded for that response.

• Permitted and Prohibited Items:     - This is a closed-book examination.     - Permitted: A single notesheet is allowed for reference.     - Prohibited: Logging into computer systems during the test is strictly forbidden. The use of any electronic or communications device is prohibited.     - Cell Phones: All mobile devices must be placed in silent mode.

Prepaging and Performance in Virtual Memory and Paging Systems

• Concept of Prepaging:     - Prepaging refers to the strategy of bringing some of a process's pages into main memory before they are explicitly requested by the process.     - Benefits/Why it might be a good idea: The primary advantage is the reduction of page faults during the initial execution of a process. If the operating system can accurately predict which pages will be needed (leveraging the principle of locality), it can fetch them in a single batch, which is more efficient than individual disk I/O operations.     - Drawbacks/Why not: If the pages brought into memory are not actually used, memory and I/O bandwidth are wasted. This overhead can degrade system performance if the prediction of page usage is inaccurate.

• Impact of Random Memory Access Patterns:     - Suppose a process is written so poorly that memory requests are purely random, showing no correlation with previous requests.     - Effect on Memory Performance: This scenario eliminates the "Locality of Reference" (both temporal and spatial). In such a paging system using virtual memory, performance would plummet, likely leading to "Thrashing."     - Explanation: Since there is no pattern, the OS cannot effectively keep a "working set" of pages in memory. Almost every memory request would result in a page fault because the probability of the next random address being in the current frames is extremely low. The system would spend more time swapping pages in and out of disk than executing the process.

Paging Memory Management: Address Translation and Fragmentation

• Physical Frame and Address Parameters:     - The machine has a total of $256$ frames.     - Frame Size: $4\,K$ (written as $2^{12}$) bytes.     - Offset size: $12$ bits (derived from $2^{12} = 4096$ bytes).

• Free-Frame List (in Hexadecimal):     - The available frames are: 0x24, 0x2F, 0x7A, 0x7A, 0xA5, 0xAD, 0x6A, 0x8D, 0xF3, 0x9F, 0xA4, and 0x0A.

• Page Table Construction for 10-Frame Process:     - Logical Page $0$ $\rightarrow$ Physical Frame 0x24     - Logical Page $1$ $\rightarrow$ Physical Frame 0x2F     - Logical Page $2$ $\rightarrow$ Physical Frame 0x7A     - Logical Page $3$ $\rightarrow$ Physical Frame 0x7A     - Logical Page $4$ $\rightarrow$ Physical Frame 0xA5     - Logical Page $5$ $\rightarrow$ Physical Frame 0xAD     - Logical Page $6$ $\rightarrow$ Physical Frame 0x6A     - Logical Page $7$ $\rightarrow$ Physical Frame 0x8D     - Logical Page $8$ $\rightarrow$ Physical Frame 0xF3     - Logical Page $9$ $\rightarrow$ Physical Frame 0x9F

• Address Translation Examples:     - Logical Address 0x3C1E:         - Split address (3 hex digits for offset): Page is 0x3, Offset is 0xC1E.         - Consultation of Page Table: Page $3$ maps to Frame 0x7A.         - Physical Address: 0x7AC1E.     - Logical Address 0x6E4C:         - Split address: Page is 0x6, Offset is 0xE4C.         - Consultation of Page Table: Page $6$ maps to Frame 0x6A.         - Physical Address: 0x6AE4C.

• Internal Fragmentation Comparison:     - Both paging and fixed partitioning suffer from internal fragmentation.     - Fixed Partitioning: This is a major problem because partitions are often large and mismatched to the process size, leading to significant wasted space in every partition that is not perfectly filled.     - Paging: This is not considered a major problem because the maximum amount of memory wasted per process is always less than one single page (specifically, the last page of the process). With small, uniform page sizes, this waste is negligible compared to the overhead and flexibility benefits of the system.

Memory Management Simulation: First-Fit System

• Initial State: A single block of $256\,KB$ located at address $0$.

• Processing Requests:     1. Time 3: Request for $170\,kb$ (Burst: $10$). Address: $0$ to $170$.        - Blocks left: 1 free block at address $170$ with size $86\,KB$.     2. Time 6: Request for $80\,kb$ (Burst: $4$). Fits in the residue at address $170$.        - Blocks left: 1 free block at address $250$ with size $6\,KB$.     3. Time 6: Request for $90\,kb$ (Burst: $4$). Does not fit in remaining $6\,KB$. Must wait.     4. Time 10: The $80\,kb$ process (started at Time 6) finishes. Memory from $170$ to $250$ is released.     5. Time 13: The $170\,kb$ process (started at Time 3) finishes. Memory from $0$ to $170$ is released.     6. Time 13: Request for $140\,kb$ (Burst: $1$).     7. Time 20: Request for $70\,kb$ (Burst: $14$).     8. Time 24: Request for $10\,kb$ (Burst: $10$).

• Snapshots of Memory Blocks:     - Time 3: $1$ block remaining; Size: $86\,KB$; Address: $170$.     - Time 9: $1$ block remaining; Size: $6\,KB$; Address: $250$.     - Time 18: (Analysis required based on First-Fit logic and merges).     - Time 25: (Analysis required based on First-Fit logic and merges).

Page Replacement Policy Analysis

• Page Request Stream: 0 3 4 2 3 1 2 5 6 3 4

• System Constraints: $3$ available frames. No prepaging assumed.

• Policies Tested:     - (a) OPT (Optimal): Replaces the page that will not be used for the longest period of time in the future. Requires future knowledge of the stream.     - (b) LRU (Least Recently Used): Replaces the page that has not been referenced for the longest period of time.     - (c) SECOND-CHANCE/CLOCK: An approximation of LRU using a reference bit. A circular buffer with a pointer ("hand") scans pages; if the reference bit is $1$, it is cleared and the hand moves on. If it is $0$, that page is replaced.

Disk Storage and Inode Structural Theory

• Physical Disk Specifications:     - Disk Block Size: $1\,K$ (written as $2^{10}$) bytes.     - Total Disk Capacity: $1\,TB$ (written as $2^{40}$) bytes.

• Drive Metrics:     - Total Block Count: $2^{40} / 2^{10} = 2^{30}$ blocks ($1,073,741,824$ blocks).     - Block Pointer Size: To address $2^{30}$ blocks, the pointer requires at least $30$ bits. In practice, this would likely be stored as a $4$-byte ($32$-bit) pointer.

• Inode File System Structure:     - Scheme: 12 direct blocks, 1 single indirect block, and 1 double indirect block (similar to BDS/Berkeley Fast File System but lacking triple indirect pointers).     - Maximum Theoretical File Size Calculation:         - Direct blocks: $12 \times 1\,KB = 12\,KB$.         - Single Indirect: If pointers are $4$ bytes, a $1\,KB$ block holds $256$ pointers. $256 \times 1\,KB = 256\,KB$.         - Double Indirect: $256 \times 256 \times 1\,KB = 65,536 \times 1\,KB = 64\,MB$.         - Sum total provides the theoretical max file size.

Translation Lookaside Buffer (TLB)

• Necessity for Efficiency:     - Without a TLB, every logical memory access would require at least two physical memory accesses: one to look up the entry in the page table (stored in main memory) and one to access the actual data. This would halve the effective memory speed.     - The TLB functions as a high-speed associative cache that performs the translation in a single hardware cycle, significantly reducing effective access time.

• TLB Contents:     - The TLB contains a small footprint of the page table.     - Each entry typically consists of a Tag (the Virtual Page Number) and a Value (the corresponding Physical Frame Number/Frame address).     - It also contains management bits such as the valid bit, dirty bit, and protection bits (read/write/execute).