Memory management
CS 273 (OS), Fall 2020
History
Monoprogrammed batch systems
- CPU utilization? (? means "this is an issue." E.g., a compute-bound process could be using the CPU while an I/O-bound process blocks)
Multiprogrammed batch systems
- DMA channels
- Fixed memory partitions, batch queue per partition
- Protection? Base reg, limit
- Memory utilization?
Present-day
Swapping
Paging
Segmented memory
Swapping
Idea: copy (variable length) mem partitions for dormant processes to disk.
- Originally for batch; also used in timesharing
- Segment for dynamic allocation
- Fragmentation?
- Avoid swapping empty space?
- Time performance?
Data structures to manage swapping
Bit map
- Space vs internal fragmentation?
- Time to find given sized segment?
Linked list of "holes"
- Detect and merge adjacent holes
- Algorithm for selecting hole? E.g., "next fit" surprisingly a little worse than "first fit"
- "Best fit:" sorting time? tiny frag?
Buddy system
- Example: 12GB memory, processes +1G, +.5, +4, +1.2, -1, -1.2, -5
- Speed
- Internal fragmentation vs external fragmentation (checkerboarding)
Virtual memory and paging
Idea: memory holds only those portions of a process that are currently being used
Virtual - "behaves as if"
Each process behaves as if it has a complete 32-bit (or 48-bit) memory space to use.
But all those processes share a physical memory address is probably far smaller than those combined virtual address spaces (or even one of them)
Each virtual address is translated into a physical address when that virtual address is needed by its process.
E.g., virtual address 0xABCDEF57 might be translted to physical address 0x108192057
Example: Single memory reference
Terminology
- page
- virtual memory; virtual address; VPN, offset
- physical memory; page frame; PFN, offset
- page table; page table entry
- page fault
Example:
ADDD 2144,#3
Time performance??
- MMU
- TLB ("Associative memory"), a small (e.g., 64 VPNs) hardware cache for page table; usu. located inside of MMU
Size of page table?
- Note that each process needs its own page table.
- Page size tradeoff
- Multi-level page tables; paging the page table
Page replacement policies
- NRU; R, M bits
- FIFO; second chance (if R bit set).
- Belady's anomaly: e.g., 5 pages (0 1 2 3 0 1 4 0 1 2 3 4), 3 vs 4 frames
- LRU
- NFU (Not Frequently Used) with sum of R bits; with aging
Design issues
- Working set concept; thrashing
- Local vs. global application of policies; effect of swapping
- Page size (theoretical analysis based on mem per proc, PTE size), commonly 4-8KB
Implementation considerations
- CPU support: instruction backup
- Locking buffers for DMA operations
- Shared pages; management issues
- Swap area of disk. Area per process vs individual addresses of non-resident pages
- Paging daemon: evict pages to create holes
Page fault handling (algorithm)
- Hardware trap to kernel; save some state
- Save some process state; call OS (
__do_page_fault
) - OS finds desired VPN (
mm/swap.c
) - Check validity and protection of VPN. Get free page frame
(
mm/page_alloc.c
) - If page frame is dirty, page and block process. Reserve that page frame
- Get page from disk (block the process)
- Update page tables, mark page frame as being in use
- Instruction backup
- Schedule the process (
schedule
) - Restore process state; continue execution
Segmented memory
Idea: multiple logically independent linear address spaces, supported by hardware
Visible to the programmer, unlike paging or swapping
Issues/considerations:
- Allows programmer to think in terms of multiple growable parts to memory assigned to a process
- Facilitates sharing and protection
- Could be used with paging (e.g., i386) or without paging(e.g., i286 and earlier)
- Checkerboarding (external fragmentation); compaction
- Vs. software segmentation, e.g., UNIX text, data, bss, stack segments