Memory management and virtual memory

Address spaces and binding

Definition. A process address space is the set of addresses the process can use. Address binding maps program addresses to memory addresses at compile time, load time, or run time. Run-time binding requires hardware support such as a memory-management unit (MMU).

Example. A relocatable program can load at different physical locations when logical addresses are translated at run time.

Exam point. Logical/virtual addresses are generated by the CPU; physical addresses identify memory locations after translation.

Solved examples

Example 1 — base and limit. A process has base 4000 and limit 900. Translate logical address 250 and test address 950, assuming valid logical addresses satisfy 0≤LA<limit.

1. LA 250 is less than 900, so it is valid.
2. Physical address=base+LA=4000+250=4250.
3. LA 950 is not less than 900, so it traps.
4. PA=4250 for 250; 950 is invalid.

Contiguous allocation and fragmentation

Definition. Contiguous allocation assigns one continuous physical region to a process. Fixed partitions can cause internal fragmentation; variable-sized regions can cause external fragmentation as free holes become separated. Compaction moves processes to combine holes if relocation is supported.

Example. A 10-KB process placed in a 16-KB partition wastes 6 KB internally.

Exam point. Internal fragmentation is inside an allocated region; external fragmentation is between allocated regions.

Solved examples

Example 1 — internal waste. Partitions are 8, 16, and 32 KB; a 14-KB process is assigned the 16-KB partition.

1. Allocated size=16 KB.
2. Requested process size=14 KB.
3. Internal fragmentation=16−14=2 KB.
4. Answer: 2 KB internal fragmentation.

Example 2 — placement. Free holes in address order are 100, 500, and 200 KB. A process requests 180 KB using first fit.

1. First hole 100 is too small.
2. Next hole 500 is adequate; allocate 180 from it.
3. Remaining hole there is 320 KB if split.
4. First fit selects the 500-KB hole, not the smallest adequate one.

Paging and address translation

Definition. Paging divides virtual address space into fixed-size pages and physical memory into equal-size frames. A page table maps virtual page numbers (VPNs) to frame numbers; the offset is unchanged by translation. If page size is 2^d bytes, the low d address bits are the offset.

Example. With 1-KB pages, the page offset uses 10 bits.

Exam point. Physical address is frame_number·page_size+offset; page and frame sizes must match.

Solved examples

Example 1 — virtual address split. A 16-bit virtual address uses 1-KB pages. Split address 0x1234 into VPN and offset.

1. Page size=1024=2^10, so offset has 10 bits.
2. Hex 0x1234 is decimal 4660.
3. VPN=floor(4660/1024)=4; offset=4660−4·1024=564.
4. VPN=4, offset=564 (0x234).

Example 2 — physical address. Page 4 maps to frame 17 in the previous system. Translate the address.

1. Frame base=17·1024=17408.
2. Preserve offset 564.
3. PA=17408+564=17972 decimal =0x4634.
4. Physical address is 0x4634.

Field	Value
VPN	4
Offset	564
Frame	17
PA	17972 (0x4634)

Example 3 — number of page-table entries. Virtual address width is 32 bits and page size is 4 KB.

1. Offset bits=log2(4096)=12.
2. VPN bits=32−12=20.
3. Entries required for a flat table are 2^20.
4. There are 1,048,576 virtual pages.

Page-table organization

Definition. A page-table entry can hold a frame number plus valid, protection, dirty, and referenced bits. Multi-level tables allocate lower-level portions only when needed; inverted tables have one entry per physical frame and use process/address tags to locate mappings.

Example. A two-level page table splits VPN bits into outer and inner indices.

Exam point. Address bit partition depends on the stated page-table design and page size.

Solved examples

Example 1 — two-level split. A 32-bit virtual address uses 4-KB pages and a two-level table with 10 outer-index bits. Find the inner-index bits.

1. Offset bits=12.
2. VPN bits=32−12=20.
3. Inner bits=20−10=10.
4. Split: 10 outer, 10 inner, 12 offset bits.

Example 2 — page-table storage. A flat table has 2^20 entries of 4 bytes each.

1. Bytes=2^20·4=2^22.
2. 2^22 bytes=4 MiB.
3. Table size is 4 MiB per process, excluding auxiliary metadata.

Translation lookaside buffer

Definition. A TLB caches recent VPN-to-frame translations. On a hit, translation uses the cached mapping; on a miss, the page table is consulted and the TLB may be updated. Effective access time depends on hit ratio, lookup time, memory access time, and whether page-table memory accesses are included.

Example. With a single-level page table in memory, a TLB miss may require one page-table access plus the data access.

Exam point. State whether TLB lookup is parallel with memory access and whether page tables are in main memory.

Solved examples

Example 1 — EAT. TLB lookup takes 10 ns; memory access 100 ns; hit ratio 0.9. On a hit, total is TLB+memory; on miss, TLB+page-table memory+data memory.

1. Hit time=10+100=110 ns.
2. Miss time=10+100+100=210 ns.
3. EAT=0.9·110+0.1·210=99+21=120 ns.
4. Effective access time is 120 ns under the stated serial lookup model.

Example 2 — parallel lookup variant. If TLB lookup overlaps with data-memory access on a hit, hit time is max(10,100)=100 ns. If a miss still costs 10+2·100=210 ns, compute EAT.

1. Hit contribution=0.9·100=90.
2. Miss contribution=0.1·210=21.
3. EAT=111 ns.

Segmentation and segmentation with paging

Definition. Segmentation divides a process into logical variable-sized segments such as code, stack, and data. A logical address is (segment,offset); segment table entries give base and limit. Segmentation with paging subdivides segments into pages to avoid external fragmentation.

Example. Segment 2 with base 9000 and limit 500 accepts offset 120 and maps to 9120.

Exam point. Check the segment limit before adding the base.

Solved example

Example — segment translation. Segment table: segment 0 base 1000 limit 300; segment 1 base 5000 limit 700. Translate (1,650) and test (0,300), using offset<limit.

1. For (1,650), 650<700, so PA=5000+650=5650.
2. For (0,300), 300 is not less than limit 300.
3. First address maps to 5650; second traps.

Virtual memory and demand paging

Definition. Virtual memory lets a process execute without all pages resident in RAM. Demand paging loads a page when referenced; a page fault traps to the OS, which checks validity, finds a frame, reads the page, updates tables, and restarts the instruction. Invalid references cause an error rather than a successful page-in.