Paging (see the Fig. 2)

• A VM Larger Than Physical Memory
• Logical address space of a process can be noncontiguous; process allocated physical memory wherever latter available
• Bring page into memory only when needed
  • less I/O needed
  • less memory needed
  • faster response
  • more processes
• Page is needed $\Rightarrow$ reference to it
  • invalid reference $\Rightarrow$ abort
  • Not in memory $\Rightarrow$ bring to memory
• Reference may result from:
  • instruction fetch
  • data reference

  Figure 2: The relation between virtual address and physical memory addresses is given by a page table.

  
• Divide physical memory into fixed-sized blocks called frames (size power of 2, typically 512 bytes - 8KB)
• Divide logical memory into blocks of same size called pages
• A Present/Absent bit keeps track of which pages are physically present in memory
• A page table defines (maps) the base address of pages for each frame in the main memory
• The major goals of paging are to make memory allocation and swapping easier and to reduce fragmentation
• Paging also allows allocation of non-contiguous memory (i.e., pages need not be adjacent.)
• Keep track of all free frames
• Set up page table to translate logical to physical addresses
• Internal fragmentation, sometimes less than full page needed
• Dynamic relocation, each program-generated address ( logical address) is translated to hardware address ( physical address) at runtime for every reference, by a hardware device known as the memory management unit (MMU)
• Memory-Management Unit
  • Hardware maps logical to physical address
  • With MMU, value in relocation register added to every address generated by user process when sent to memory
  • User program deals with logical addresses; never sees real physical addresses

  Figure 3: The position and function of the MMU.

  
• Address Translation Scheme; address generated by CPU divided into:
  • Page number (p) used to index into page table with base address of each page in physical memory
  • Page offset (d) combined with base address defines physical address for memory system
• What happens when an executing program references an address that is not in main memory? (see Fig. 4)
• The page table is extended with an extra bit, present/absent bit
• Page Fault: Access to a page whose present bit is not set causes a special hardware trap, called page fault
• Initially, all the present bits are cleared. While doing the address translation, the MMU checks to see if this bit is set.
  1. Trap to OS
  2. Save user registers and process state
  3. Determine that interrupt was page fault
  4. Check that page reference was legal, determine location of page on disk
  5. Issue read from disk to free (physical) frame:
     • Wait in queue for device to service read request
     • Wait for device seek / rotational latency
     • Wait for transfer
  6. While waiting for disk: allocate CPU to another process
  7. Interrupt from disk
  8. Save registers and process state for other process
  9. Determine that interrupt was from disk
  10. Update page / OS tables to show page is in memory
  11. Wait for CPU to be allocated to this process
  12. Restore registers, process state, page table
  13. Restart instruction
• When a page fault occurs the operating system brings the page into memory, sets the corresponding present bit, and restarts the execution of the instruction
• What happens if no free frame?
  • Page replacement find some page in memory, ideally not in use, swap it out
    • algorithm performance
    • want to minimize number of page faults
  • Same page may be brought into memory several times
• Problem: Both paging and segmentation (we will discuss later) schemes introduce extra memory references to access translation tables.
• Solution? Translation buffers (like caches)
• Based on the notion of locality (at a given time a process is only using a few pages or segments), a very fast but small associative (content addressable) memory is used to store a few of the translation table entries
• This memory is known as a translation look-aside buffer or TLB

  Figure 4: Page fault handling by picture.

  
• Similar to storing memory addresses in TLBs, frequently used data in main memory can also be stored in fast buffers, called cache memory, or simply cache (see Fig. 5)

  Figure 5: Memory Caching.

  
• Basically, memory access occurs as follows:

  for each memory reference 
   if data is not in cache <miss> 
    if cache is full 
     remove some data 
    if read access 
     issue memory read 
     place data in cache 
     return data 
   else <hit> 
    if read access 
     return data 
    else 
     store data in cache
  

• The idea is to make frequent memory accesses faster!
• Cache terminology;
  • Cache hit: item is in the cache.
  • Cache miss: item is not in the cache; must do a full operation. Categories of cache miss:
    • Compulsory: the first reference will always miss.
    • Capacity: non-compulsory misses because of limited cache size.
  • Effective access time: P(hit) * cost of hit + P(miss)* cost of miss, where P(hit) = 1 - P(miss)