Segmentation and Paging

• Segmentation is used to give each program several independent protected address spaces
  • each segment is an independent protected address space
  • access to segments is controlled by data which describes size, privilege level required to access, protection (whether segment is read-only etc)
  • segments may or may not overlap
    • disjoint segments can be used to protect against programming errors
    • separate code, data stack segments

• Disjoint Segments can be used to exploit expanded address space
  • In 16 bit architectures e.g. (8086 and 80x86 in V86 mode) each segment has only 16 bits of address space
  • In distributed networks consisting of multiple 32 bit machines, segmentation can be used to support single huge address space
• Segments can span identical regions of address space - flat model
  • Windows NT and Windows '95 use 4 Gbyte code segments, stack segments, data segments

Working Sets and Page Replacement

Slide

Locality and Memory Hierarchy

• Example:
• • for(i=0;i<n;i++){
  • for(j=0;j<m;j++){
  • x[i][j] += a*z[j]*y[i][j];
  • }}
  • Note that consecutive elements of z, x[i],y[i] are accessed (spatial locality)
  • Note that a, i, j, m, n are repeatedly accessed (temporal locality)

Observations on Locality Example

• Registers can be used to store scalar data that are repeatedly accessed
  • a,i,j,m,n would be generally stored in a register
  • example repeatedly sweeps over array z
    • the primary or secondary cache might be small enough to store z
  • x,y elements are only accessed once, but consecutive memory locations are accessed
    • amortizes overheads associated with page table access and overheads associated with bringing pages in from disk

Intel x86 Memory Management

• Hardware support for both segmentation and paging
• First we consider segmentation - assume that paging is not used (paging can actually be disabled)
• Each logical or virtual address consists of a 16 bit segment selector and a 32 bit offset
  • segment selector points to an offset in a table of segment descriptors
  • there is a single Global Descriptor Table (GDT), there can also be many Local Descriptor Tables (LDT)
  • 1 bit in segment selector specifies whether to use a GDT or LDT, 13 bits of segment selector used as index into GDT or LDT
  • GDT or LDT identified using Global Descriptor Table Register (GDTR) or Local Descriptor Table Register (LDTR)

Intel x86: Segment Translation

Slide

• Segment selector
  • 13 bits that point to segment descriptor
  • 1 bit to specify LDT or GDT
  • 2 bits to specify requester protection level
• Segment descriptor
  • base (20 bits) - location of segment in 4 Gbyte address space
    • base may be scaled by 2**12
  • Limit - size of the segment
  • S bit
    • whether segment is a system segment

• Type
  • Defines whether segment is data or code
  • Says whether segment descriptor has been loaded into segment register
  • Defines permissions - different permissions are allowed for code or data segment
  • read-only, read/write, execute-only etc.
    • e.g. data: read-only, read/write
    • e.g. code: execute-only, execute/read-only
• Segment present
  • if bit is clear, this means that the segment is unavailable
  • exception generated when segment descriptor is loaded into register

Power Architecture: Segment Architecture

• Sixteen, 32 bit segment registers
• 24 bit subset (segment ID) used to specify segment
• Segment ID concatenated with high order 16 bits from effective address - virtual page number
• Virtual page number and low order 12 bits from effective address form the 52 bit virtual address
• Virtual address gets translated to 32 bit real address

Power Architecture: Virtual Address Translation and Generation

Slide

Intel x86: Paging

• Paging is optional - (if the PG bit of register CR0 is set, paging is enabled)
  • if paging is not enabled, the linear address is used as a physical address
• Linear Address
  • Page directory: bits 22-31
    • index into the page directory pointed to by the Page Directory Base Register (PDBR - also called CR3)
  • Page table: bits 12-21
    • index into the page table pointed to by a page directory entry
  • Offset: bits 0-11
    • physical address

Page Table Entries

• Page frame address - bits 12-31
  • starting address of a page
• Present - Bit 0
  • is page in physical memory?
  • if present bit is not set, attempts to access a page lead to a page fault exception
    • OS copies the page from disk storage into physical memory
    • OS loads page frame address into page table entry
      • when page frame address is loaded, TLB is invalidated

Page Table Entries

• Accessed - Bit 5
  • accessed bit set before read or write

accessed bit can be periodically cleared by OS. This can be used to approximate Least Recently Used (LRU) page replacement policy

• Dirty - Bit 6
  • report write access to page
  • used to determine if a replaced page needs to be written to disk

Intel x86: Paging

Slide

Combining Paging and Segmentation

• Flat model
  • map stack, code and data spaces to same 4 Gbyte range of linear addresses
  • each process can have its own 4Gbyte address space
    • different processes have different page directories so address spaces are disjoint
• Each segment can span some set of pages
• Each segment can have its own page directory

Power Architecture: Translating a Virtual Page Number to a Real Page Number

Slide

• Use inverted page table
  • each page frame is associated with a virtual page number
  • a hash table is used to obtain the page frame associated with a given virtual page
  • Translation look-aside buffers (TLB) also used to associate real pages with virtual page numbers
    • Data TLB (D-TLB) is 2 way set associative with 64 sets
    • Low order bits of virtual page number determine which TLB set to examine
    • High order bits of virtual page number are used as the D-TLB tag