Segmentation with Paging

• Advantages of Segmentation
  • Different protection for different segments read-only status for code
  • Enables sharing of selected segments (see Fig. 4.17)
  • Easier to relocate segments than entire address space
  • Enables sparse allocation of address space
• Disadvantages of Segmentation
  • Still expensive/difficult to allocate contiguous memory to segments
  • External fragmentation: Wasted memory
  • Paging; Allocation easier, Reduces fragmentation
• Advantages of Paging
  • Fast to allocate and free;
    • Alloc: Keep free list of free pages and grab first page in list, no searching by first-fit, best-fit
    • Free: Add page to free list, no inserting by address or size
  • Easy to swap-out memory to disk
    • Page size matches disk block size
    • Can swap-out only necessary pages
    • Easy to swap-in pages back from disk
• Disadvantages of Paging
  • Additional memory reference: Inefficient. Page table too large to store as registers in MMU. Page tables kept in main memory. MMU stores only base address of page table.
  • Storage for page tables may be substantial
    • Simple page table: Require entry for all pages in address space. Even if actual pages are not allocated
    • Partial solution: Base and bounds (limits) for page table. Only processes with large address spaces need large page tables. Does not help processes with stack at top and heap at bottom.
  • Internal fragmentation: Page size does not match allocation size
    • How much memory is wasted (on average) per process?
    • Wasted memory grows with larger pages
• Combine Paging and Segmentation
  • Structure
    • Segments correspond to logical units: code, data, stack. Segments vary in size and are often large
    • Each segment contains one or more (fixed-size) pages
  • Two levels of mapping to make tables manageable (2 look-ups!)
    • Page table for each segment
    • Base (real address) and bound (size) for each page table
• Segments $+$ Pages Advantages
  • Advantages of Segments
    • Supports sparse address spaces. If segment is not used, no need for page table. Decreases memory required for page tables.
  • Advantages of Paging
    • Eliminate external fragmentation
    • Segments to grow without any reshuffling
  • Advantages of Both. Increases flexibility of sharing. Share at two levels: Page or segment (entire page table)
• Segments + Pages Disadvantages
  • Internal fragmentation increases. Last page of every segment in every process
  • Increases overhead of accessing memory
    • Translation tables in main memory
    • 1 or 2 overhead references for every real reference
  • Large page tables
    • Do not want to allocate page tables contiguously
    • More problematic with more logical address bits
    • Two potential solutions: Page the user page tables (multilevel page table), Inverted page table