Memory Management in OS: Paging, Segmentation

Every running process needs memory for its code, data, heap and stack, and physical memory is limited and shared. Memory management is the part of the operating system that decides which process gets which piece of RAM, translates the addresses programs use into real locations, keeps processes out of each other's memory, and takes memory back when a process exits. This note covers the techniques interviewers ask about, from simple contiguous allocation to paging and segmentation. How paging is used to run programs larger than RAM is in Virtual Memory and Demand Paging.

Logical and physical addresses

• A logical address (also called a virtual address) is what the CPU generates while running a program: "variable x is at address 4500 in my space".
• A physical address is the actual location in RAM, as seen by the memory chips.

The memory management unit (MMU), a hardware unit in the CPU, translates every logical address to a physical one on every memory access. The process only ever sees logical addresses, so the OS can place it anywhere in RAM and move it later.

The simplest MMU uses two registers. The relocation (base) register holds where the process starts in physical memory, and the limit register holds the size of its logical space. Every address is checked against the limit, then added to the base; here the base is 30000 and the limit 12000:

1. The CPU issues logical address 4500. The MMU checks it against the limit register: 4500 < 12000, so it is inside the process. It adds the base register: 30000 + 4500 = 34500.
2. Logical address 0 is the first byte of the process: it passes the check and maps to 30000, the base itself. The process never learns where in memory it sits.
3. Logical address 12500 fails the check, 12500 ≥ 12000: it lies outside the process's space, so no memory is touched and the MMU traps to the operating system with an addressing error.

Addresses can be bound to physical locations at compile time (fixed addresses, the program cannot move), at load time (fixed when the program is loaded), or at execution time (translated on every access by the MMU). Modern systems bind at execution time, which is what makes relocation, swapping and compaction possible.

Swapping moves a whole process out to a backing store on disk and back in later, so more processes can exist than fit in memory. Modern systems swap individual pages instead of whole processes.

Contiguous memory allocation

In contiguous allocation each process occupies one continuous block of physical memory.

• Fixed partitions: memory is divided into partitions of set sizes in advance, one process per partition. Simple, but a small process in a large partition wastes the rest, and the number of partitions caps the number of processes.
• Variable partitions: each process gets exactly the size it asks for. Free memory becomes a set of holes scattered between processes. When a process asks for memory, the OS must choose a hole.

First fit, best fit and worst fit

The three classic placement strategies:

• First fit: take the first hole, from the start of memory, that is big enough.
• Best fit: take the smallest hole that is big enough; this needs a search of the whole list unless it is kept sorted by size.
• Worst fit: take the largest hole, hoping the leftover stays useful.

Next fit is first fit that resumes searching where the last search stopped.

Worked example

Free holes, in memory order: H1 = 150 KB, H2 = 400 KB, H3 = 250 KB, H4 = 600 KB, H5 = 300 KB. Requests arrive in the order 220 KB, 380 KB, 130 KB, 560 KB. The leftover part of a hole stays where it was as a smaller hole.

1. Five free holes sit between processes, and requests of 220, 380, 130, 560 KB arrive in that order. Each strategy places the same requests; the leftover of a hole stays where it was as a smaller hole.
2. 220 KB: first fit stops at the first hole big enough, H2; best fit takes the smallest that fits, H3; worst fit the largest, H4.
3. 380 KB goes to H4 under first fit, H2 under best fit and H2 under worst fit. Best fit's leftovers are already tiny: 20 and 30 KB.
4. 130 KB goes to H1 under first fit, H1 under best fit and H4 under worst fit. Best fit's leftovers are already tiny: 20, 20 and 30 KB.
5. 560 KB: first fit has 970 KB free in five holes but none of 560, so the request waits — external fragmentation. Best fit still has 600 KB in H4; worst fit's largest hole is 300 KB.

Best fit places all four requests here; first fit and worst fit cannot place the 560 KB one. Under first fit, 970 KB is still free when it fails (20 + 180 + 250 + 220 + 300), but no single hole holds 560 KB. That is external fragmentation in action. Do not over-learn this example, though: on other request sequences first fit wins, and best fit tends to leave tiny unusable slivers like the 20 KB holes above. Simulation studies generally find first fit and best fit similar in memory use, with first fit faster, and worst fit worse than both.

Fragmentation and compaction

Compaction shuffles the processes in memory together so that all the holes merge into one. It needs execution-time binding, since a moved process only gets a new base register, and it is slow because large amounts of memory must be copied. The lasting cure is to stop needing contiguous space at all, which is what paging does.

Paging

Paging lets a process's physical memory be non-contiguous. Physical memory is divided into fixed-size blocks called frames, the logical address space into blocks of the same size called pages, and a per-process page table records which frame holds each page. Any free frame can hold any page, so there is no external fragmentation.

Address translation

If the page size is 2ⁿ bytes, the low n bits of a logical address are the offset d within the page and the remaining high bits are the page number p:

• page number p = logical address ÷ page size (integer division)
• offset d = logical address mod page size
• physical address = frame number × page size + offset

Worked example. The page size is 4 KB (4096 bytes, so n = 12) and part of a process's page table is:

Translate logical address 13000:

1. p = 13000 ÷ 4096 = 3 (since 3 × 4096 = 12288), and d = 13000 − 12288 = 712.
2. The page table maps page 3 to frame 6.
3. Physical address = 6 × 4096 + 712 = 24576 + 712 = 25288.

1. 13000 in binary (its low 16 bits; the rest are 0). A 4 KB page is 2¹² bytes, so the low 12 bits are the offset, d = 712, and the bits above them the page number, p = 3.
2. The page number indexes the process's page table: entry 3 says page 3 is in frame 6. The offset is not looked up at all.
3. The frame number replaces the page number and the offset is copied unchanged: 6 × 4096 + 712 = 25288, or 0x62C8. Translation is a table look-up and a bit substitution, with no addition.

Page table size. With 32-bit logical addresses and 4 KB pages, the page number has 32 − 12 = 20 bits, so the page table has 2²⁰ = 1,048,576 entries. At 4 bytes an entry that is 4 MB per process, which is why real systems use multi-level page tables.

Internal fragmentation. A process of 10,500 bytes with 4 KB pages needs 3 pages (10,500 ÷ 4096 = 2, remainder 2,308). The third page uses only 2,308 bytes, so 4096 − 2308 = 1,788 bytes are wasted. On average half a page per process is lost this way, which argues for small pages, while smaller pages mean bigger page tables.

Hardware details

The page table lives in memory, located by the page-table base register (PTBR). A plain implementation therefore needs two memory accesses per reference: one for the page-table entry and one for the data. A small, fast cache of recent translations, the translation look-aside buffer (TLB), removes most of that cost; it is covered with its timing in the virtual memory note. Each page-table entry also carries protection bits (read, write, execute) and a valid-invalid bit that marks pages outside the process's address space. Paging also makes sharing easy: several processes' page tables can point to the same frames of read-only code, such as a shared library.

Segmentation

Segmentation follows the programmer's view of a program as a collection of variable-size, logically separate parts: code, global data, heap, stack, each library. A logical address is a pair (segment number s, offset d). The segment table gives each segment a base (where it starts in physical memory) and a limit (its length). The MMU checks d < limit, then adds the base.

1. Address (2, 300) names segment 2, data, and offset 300. The segment table gives its base 4000 and limit 800; 300 < 800, so the physical address is 4000 + 300 = 4300.
2. (0, 1199) is the last byte of the code segment: 1199 < 1200 passes, by one, and maps to 3199. An offset equal to the limit would already be outside.
3. (1, 520) asks for byte 520 of the stack segment, which is only 500 bytes long. 520 ≥ 500, so the MMU traps before 6520 is touched: a segmentation fault.

Because segments are meaningful units, protection fits naturally: code read-only and executable, data read-write, and a whole segment can be shared. The cost is that segments have variable sizes, so allocating them brings back external fragmentation. Systems that combined the two, such as 32-bit x86, split memory into segments and then paged each segment; 64-bit x86 keeps segmentation only in vestigial form and relies on paging.

Paging vs segmentation

Common mistakes

• Saying paging has no fragmentation at all. It has no external fragmentation, but the last page of each process wastes some space internally.
• Using 1 KB = 1000 bytes in address arithmetic. Page sizes are powers of two: 4 KB is 4096 bytes.
• Forgetting the limit check in segmentation, or comparing with ≤ instead of <: an offset equal to the limit is already outside the segment.
• Treating best fit as always best. It leaves the smallest leftovers, which are often too small to use.
• Mixing up pages and frames: pages are logical, frames are physical, and they are the same size.
• Computing the page table size from the physical memory size; the number of entries depends on the logical address space.

Interview questions

What does the MMU do? It translates every logical address the CPU generates into a physical address, at run time, using base and limit registers or page and segment tables. It also enforces protection, raising a trap when a process touches memory outside its space or breaks a page's permissions.

Why does paging eliminate external fragmentation? Every frame is the same size and any free frame can hold any page, so a process never needs a contiguous run of free memory. Any free frame is usable, so free memory is never stranded in holes too small to use.

How do you find the number of bits for the page number and offset? The offset needs log₂(page size) bits, such as 12 bits for 4 KB pages. The page number takes the remaining bits of the logical address, such as 20 bits of a 32-bit address, giving 2²⁰ pages.

What is the trade-off in choosing a page size? Small pages waste less to internal fragmentation and track memory use more finely, but need larger page tables and more TLB entries. Large pages mean smaller tables and fewer TLB misses but more internal fragmentation.

Why is segmentation said to match the user's view of memory? Programmers think of a program as code, data, a stack and libraries, each of a different size. Segmentation gives each of those its own segment with its own length and permissions, instead of slicing everything into equal pages.

What is the difference between swapping and paging? Classic swapping moves an entire process between memory and disk. Paging moves individual pages, so only the parts of a process actually needed are in memory.

Next, read Virtual Memory and Demand Paging, or check yourself with the Operating Systems (Basic) skill test.