A level of indirection to manage memory easier

Memory segmentation

3 kinds of addresses:

• Logical address: used in machine language instructions; consists of 1 segment selector and 1 offset
  • Segment selector: 16-bit segment identifier; stored in segment registers. The logical address is written as “<segment register>:<offset>”.
    • 6 segment registers:
      • 3 special: cs, ds, ss
      • 3 general purpose: es, fs, gs
  • Offset: the relative address within the segment
• Linear address: this is the virtual address commonly referred to
  • Linear address = logical address offset + segment base
    • Segment base is taken from the segment descriptor
    • Segment descriptor is an entry in the Global Descriptor Table or Local Descriptor Table:
      • GDT and LDT bases are stored in GDT register and LDT register.
      • Segment register contains the index of the entry that should be looked at
• Physical address

Indeed segmentation and paging are somewhat redundant. Linux prefers paging because:

• Memory management is simpler if all processes use the same segment register values
• Universality: Other CPU architectures (RISC, etc.) don’t support segmentation well

Paging

• “extended paging”: use 4MB instead of normal 4KB pages
  • => no page table, only page directory
  • save memory (reduce page table level) and preserve TLB entries
• In theory, up to 4GB of RAM could be installed on 32-bit systems; in practice, due to the linear address space requirements of User Mode processes, the kernel cannot directly address more than 1 GB of RAM => data center servers run many processes and need more for kernel memory than 1GB.
• Physical Address Extension: enable up to 64GB RAM
  • Translate 32-bit linear address into 36-bit physical address:
    • Use 4KB pages: 64gb = 2^6 gb = 2^16 mb = 2^26 kb = 2^36 bytes into 2^24 frames -> 1 frames = 2^12 bytes = 4KB
    • Each page table entry uses 24 bits to store physical address + 12 bits to store metadata => need 36 bits for 1 entry => entry size = 64 bit, but need to keep page table size = 4096 => only 512 entries per table
    • 32-bit linear address is split into 2 (page directory pointer table) + 9 (page directory) + 9 (page table) + 12 (offset)
  • PAE doesn’t enlarge linear address space => user process still only uses 4GB, only kernel can exploit this expansion to 64GB RAM
• 64-bit paging: need additional page directory level
  • Amd64: 9 + 9 + 9 + 9 + 12 (offset, 4KB page size)
    • Using 9 bits on each level here because we need to fit 8-byte address entries into 4KB page: 4*1024/8=512 => 2^9 entries per page!
    • Only 48 bit addressing:
      • Using full 64 bits needs extra page table level => walking through levels take a lot of time
      • Yet using full 64 bits are too much memory, so people decided 48 bits are enough
    • Canonical address form:
      • AMD decided that only 48 lower significant bits are used for translation in 64-bit addresses
      • They enforce that bit 48 to 63 must be the same as bit 47, otherwise exception is raised
        • Hence we have 2 ranges: 0x0 to 0x00007FFFFFFFFFFF and 0xFFFF800000000000 to 0xFFFFFFFFFFFFFFFF
          • Lower half for user and higher half for kernel space
        • Scalability: this prevents using the remaining 16 bits for other purposes (storing metadata, etc.) hence it is easy should we need to extend from 48 to 64 bits later

Swapping

• Swap space is a dedicated area on disk (a partition or file) that the OS uses as virtual RAM when memory is exhausted.
• When needed, to determine which page to swap out, we can use LRU
  • But keep track of the last access time of each page is difficult…
  • Approximating LRU: we can use clock algorithm:
    • Imagine the list of pages is a circular list
    • Iterate through each page:
      • If the use bit (there is a use bit in PTE) is set => turn off and continue
        • Can use more complex criteria, e.g. if dirty bit is set => needs write back => swapping is expensive => avoid…
      • If not, swap the page out of memory

TLB

• TLB is part of the MMU to cache virtual-to-physical translation