Memory Management: Paging, Segmentation, Virtual Memory
Memory Management in Operating Systems
When the operating system (OS) loads a program into memory, it needs to locate code and data, allocate a stack, and initiate its execution. The processor, working with the operating system, translates logical addresses into physical ones.
Requirements for Memory Management
- Relocation: A process might be swapped out to secondary memory (disk) and later reloaded into a different location. The programmer doesn’t know where the program will reside, and this location can change during runtime.
- Protection: Processes should not be able to reference memory addresses that do not belong to them. This check can only be performed at runtime.
- Sharing: Multiple processes must be able to share a common memory region.
- Logical Organization: From a software perspective, it’s beneficial to organize programs into modules, making them read-only, read/write, etc.
- Physical Organization: The programmer is unaware of the program’s location, or even the possibility of swapping.
Paging
With a fixed-size memory model, memory is divided into chunks of that size called frames. Processes are divided into chunks of the same size called pages. Each page of a process is allocated to a frame.
- The OS maintains a page table for each process, storing the frame location of each page.
- If the page size is a power of 2, the least significant bits of a logical address represent the offset within a page, and the most significant bits represent the page number.
- Each page-table entry, besides the frame number, can contain control bits.
- The processor has a register that points to the page table of the running process.
Segmentation
A program is divided into segments based on development-time criteria: code, data, stack, more code, another data segment, etc.
- The operating system maintains one segment table per process.
- Each entry contains at least the corresponding segment’s base address and its length.
- Each segment-table entry, in addition to the segment’s starting address and length, can contain control bits.
- The processor has a register that points to the segment table of the running process.
Pros and Cons
- Regarding memory misuse:
- Paging can suffer from minor internal fragmentation; the last frame might not be completely used.
- Segmentation suffers from external fragmentation.
- Sharing a “segment” among various processes is easier with segmentation.
- Paging offers a better facility for implementing virtual memory. Instead of swapping an entire segment in and out, it can be accomplished by swapping pages in and out.
Combination of Paging and Segmentation
Programs are first subdivided into segments. Each segment is then divided into pages. Each page is located within a memory frame.
- Therefore, every process will have a segment table, and every segment will have a page table.
Virtual Memory
Programs use logical addresses that are mapped to physical addresses at runtime. With paging alone, programs use a flat memory model starting at address 0. With segmentation, programs are aware of it, and logical addresses contain a (segment number, offset) pair.
- Both mechanisms allow keeping only some “chunks” of a program in main memory. The remaining “chunks” can reside in secondary memory (disk).
- If the OS determines that a chunk is not being used, it can swap it out to secondary memory and swap it back in when needed. This is virtual memory.
- Virtual memory is mostly based on paging. Pages are swapped in and out of secondary memory.
- Page-table entries have enough space to contain additional control bits. Some of these can be used to indicate:
- Whether the referenced page is in main memory or not.
- Whether a page has been modified (no need to store it when swapping it out if it hasn’t been changed).
- If it is code. Then, there is no need to store it on disk when swapped out because the code already exists in the program.
- Whether to lock it in main memory. Do not swap this page out.