Management of a limited resource :
Sophisticated algorithms needed, together with support from hardware and from compiler and loader.
Key point : program’s view memory is set of memory cells starting at address 0x0 and finishing at some value (logical address)
Hardware : have set of memory cells starting at address 0x0 and finishing at some value (physical address)
Swapping
If memory demand is too high, memory of some processes is transferred to disk. Usually combined with scheduling : low priority processes are swapped out.
Problems :
- Big transfer time
- What to do with pending I/O ?
If a process has unfinished I/O, swapping it out can be problematic or even unsafe.
Fragmentation
Fragmentation is a condition in memory management where free memory is broken into small, non-contiguous blocks, making it difficult to allocate large continuous memory spaces even if enough total free memory exists. It is classified into:
- External Fragmentation: Occurs when free memory is divided into small scattered blocks due to continuous allocation and deallocation.
- Internal Fragmentation: Happens when allocated memory blocks are slightly larger than the requested memory, leading to unused space within those blocks.
Swapping raises two problems :
- over time, many holes (free block of memory) appear in memory (external fragmentation)
- programs only a little smaller that hole leftover too small to qualify as hole (internal fragmentation)
Strategies for choosing holes :
- First-Fit : Start from beginning and use first available hole.
- Rotating first fit : start after last assigned part of memory.
- Best fit : find smallest usable space
- Buddy system : Have hole in sizes of power of 2. If no block of the exact size is available, a larger block is split into two “buddies.” Two buddies of the same size can be merged back if they are both free. Efficient for reducing external fragmentation but can cause some internal fragmentation.
Paging
Alternative approach : Assign memory of a fixed size (page) avoids external fragmentation
Translation of logical address to physical address done via page table.
Using a paging system, memory is divided into fixed size pages and a process currently in memory may be held in several non-contiguous pages. A page table uses mapping to store a link between the physical memory address and the logical address space of each process.
Hardware support mandatory for paging :
If page table small, use fast registers. Store large page tables in main memory, but cache most recently used entries.
Instance of a general principle :
Whenever large lookup tables are required, use cache (small but fast storage) to store most recently used entries.
Memory protection easily added to paging :
protection information stored in page table.
Segmentation
Segmentation is the logical division of address space into varying length segments which depends on the program structure.
Divide memory according to its usage by programs :
- Data : mutable, different for each instance.
- Program Code : immutable, same for each instance
- Symbol Table : immutable, same for each instance, only necessary for debugging
Requires again HW support can use same principle as for paging, but have to do overflow check
Paging motivated by ease of allocation, segmentation by use of memory.
| Aspect | Paging | Segmentation |
|---|---|---|
| Memory Division | Divides memory into fixed-size blocks called pages | Divides memory into variable-size blocks called segments |
| Size | All pages are equal-sized (e.g., 4 KB) | Segments are variable-sized, depending on program structure |
| Purpose | Mainly for efficient memory management and eliminating fragmentation | Matches logical divisions in a program (e.g., code, data, stack) |
| Addressing | Uses a page number and offset | Uses a segment number and offset |
| Fragmentation | Can cause internal fragmentation | Can cause external fragmentation |
Virtual memory
Idea : complete separation of logical and physical memory. Program can have extremely large amount of virtual memory.
Works because most programs use only small fraction of memory intensively.
Demand Paging
Virtual memory implemented as demand paging : memory divided into units of same length (pages), together with valid/invalid bit. Two strategic decisions to be made :
- which process to “swap out” (move whole memory disk and block process) : swapper
- which pages to move to disk when additional page is required : pager
Minimisation of rate of page faults (page has to be fetched from memory) crucial.