______ Memory management (CS 273 (OS), Fall 2020)
Home
>>    




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)

    1. Hardware trap to kernel; save some state
    2. Save some process state; call OS (__do_page_fault)
    3. OS finds desired VPN (mm/swap.c)
    4. Check validity and protection of VPN. Get free page frame (mm/page_alloc.c)
    5. If page frame is dirty, page and block process. Reserve that page frame
    6. Get page from disk (block the process)
    7. Update page tables, mark page frame as being in use
    8. Instruction backup
    9. Schedule the process (schedule)
    10. 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