FIT2100 Chap.9 Memory Allocation and Paging
Memory Allocation and Paging
Memory management gives each process a protected logical address space and maps active content into physical memory. Contiguous allocation is easy to translate but suffers from external fragmentation and difficult growth.
Paging divides logical memory into fixed-size pages and physical memory into equal frames, allowing non-adjacent placement.
A page table maps page numbers to frame numbers and carries control information such as validity and access rights. Translation preserves the offset within a page. Paging removes external fragmentation but leaves internal waste in partially used pages and introduces page-table overhead.
Replacement policies decide what to evict when no free frame remains, using different evidence about reference behaviour.
What this chapter covers
- 01
Logical and physical memory
- 02
Contiguous placement
- 03
External fragmentation
- 04
Paging and frames
- 05
Page tables
- 06
Address translation
- 07
Internal fragmentation
- 08
Replacement policies
Worked example · free
Translate a logical address
- +2Page number is floor(5,370 / 1,024) = 5. Offset is 5,370 − 5 × 1,024 = 250.
- +2The page table changes logical page 5 to physical frame 12 while preserving the 250-byte offset.
- +2Physical address is 12 × 1,024 + 250 = 12,538. The offset check passes because 250 is below 1,024.
Key terms
- Logical Address
- An address generated within a process address space before physical-memory translation.
- Physical Address
- The location used to access an actual byte in physical memory after translation.
- Page
- A fixed-size unit of logical address space.
- Frame
- A fixed-size physical-memory slot capable of holding one page.
- Page Table
- The mapping and control structure that connects logical pages to physical frames.
- Replacement Policy
- The rule used to choose a resident page for eviction when another page needs a frame.
Memory Allocation and Paging FAQ
Why does paging avoid external fragmentation?
Every physical frame has the same size, so any free frame can hold any logical page. A process does not need one adjacent physical region. Partly used final pages can still waste space internally.
Why is the address offset unchanged?
Translation replaces the logical page number with a physical frame number. The offset identifies a byte within that fixed-size unit, so changing it would point to a different byte than the process requested.
How does least recently used replacement work?
LRU removes the page whose last reference is oldest, using recent past behaviour as a locality predictor. Exact tracking can be expensive, so systems often use hardware bits or approximations instead of a perfect order.
Why is optimal replacement not implemented directly?
It chooses the page whose next use lies farthest in the future. A running operating system does not know the complete future reference string, so the policy is a benchmark for comparing practical methods.
How can I audit a complete paging answer?
Begin with the declared page size and split the logical address into a page number and an offset. Confirm that the offset is within one page, then inspect the page-table entry for range, validity and permission before using its frame number. Form the physical address with the same offset and keep every unit explicit.
If the page is absent but valid, stop the direct translation and describe the page-fault path instead of inventing a resident frame. For a replacement question, record the frame contents after each reference, label each hit and fault, and justify the victim using only information the named policy possesses. State the initial frames, tie rule, frame allocation and whether replacement is local or global.
Recount faults from the completed table and locate the first differing row if another result disagrees. This audit separates arithmetic, protection and policy, so a correct-looking final address or fault count cannot hide an invalid intermediate decision.
Assessment move
Practise quotient and remainder translation until the offset range check is automatic. Draw page tables with validity and permission information, not only frame numbers. Compare contiguous placement and paging on growth, fragmentation and metadata. For replacement, write the frame contents after every reference and justify each victim using only the information available to that policy.
A final fault count without the intermediate states is difficult to verify. Build translation drills around several page sizes, especially powers of two. For each logical address, compute the page by division, the offset by remainder, verify that zero is no greater than the offset and the offset is below page size, then consult validity and permission before using the frame.
Recalculate with bit splitting and require both methods to agree. Draw the TLB separately from the page table so a TLB miss is not mistaken for a page fault. When comparing allocation, label external fragmentation in variable regions and internal waste in the final fixed-size unit; then state the metadata and translation cost introduced by paging.
For replacement, make a row after every reference containing frames, hit or fault, victim and the evidence the policy used. Never let LRU see a future reference or let FIFO use recent frequency. Run the same reference string with different frame counts and state whether replacement is local or global. For a lab or calculation explanation, preserve the reference table rather than reporting only a fault total.
Diagnose discrepancies at the first differing victim choice. Finish with a protection audit: check address-space identity, read/write authority and valid state before treating a numerical physical address as an allowed access.
Working through Memory Allocation and Paging in FIT2100? Sia is AskSia’s AI Computer Science tutor — ask any FIT2100 Memory Allocation and Paging question and get a clear, step-by-step explanation grounded in how FIT2100 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
