Paging

• Segments can be of variable lengths, whereas pages are fixed length - memory allocated in chunks of storage
• Virtual address = (p,d), where p: page number in virtual storage and d: displacement within the page
• Pages are placed in primary memory in blocks - page frames of equal size as incoming pages
• page frames are integral multiples of page size (in primary memory - referenced by a page table pointer
• Each address space has its own page table

  
Figure 7: Paging - direct translation

• What happens when required (referenced) page is not in memory ?
• Need to get it from secondary storage - the page table entry must provide an indication of where the page is and how to obtain it from secondary storage (similar to a segment table entry)

  
Figure 8: Page table entry

• Many ways of translating virtual page address to real page address : Direct (mentioned already), Associative mapping and variations
• Direct method is too slow, because page table can be quite large and must be maintained in primary memory, and comparison must be performed between ALL entries one at a time
• Alternative is to keep the page table in high speed memory called cache (will come to this later)
• Another alternative is to find a different way to perform the comparison : Associative Mapping - page table now in a content addressed associative storage

  
Figure 9: Associative Mapping

• When a virtual address v=(p,d) is issued, every entry in the associative storage is searched simultaneously for page p
• Much quicker, as do not need to perform a search sequentially - if a match is found, the real address can be calculated
• However, if still slow, possible to combine direct mapping with associative mapping
• Also possible to have sharing in a paging system, where multiple page frame references in page tables point to the same area of real (physical) storage

• Paging : + : simple memory allocation, easy to share
  - : big page table if sparse address space space wastage
• What's the solution ? : allows simple memory allocation, easy sharing and efficient for sparse address spaces
• Combine paging and segmentation = multilevel translation
• Use tree of tables, Lowest level is page table - Higher levels = segmented
• Segments are restricted to be a multiple of page sizes (though this multiple is not fixed)
• Most architectures today implement some flavour of this

  
Figure 11: Paging + Segmentation

• Where is page table kept ? Where is segment table kept ?
• In primary store - if too large - too much wasted space in primary memory - overhead (as storing tables NOT pages or segments themselves) - so what do we do ?
• Also, possible to put page tables in a special segment that is only accessible to OS
• Use a Translation Lookaside Buffer (TLB) (via cache) : Idea : Make frequent case efficient - infrequent path doesn't matter all that much
• Cache is a fast memory (closer to the CPU than primary memory - and implemented using high speed registers)
• What is this concept ? and more importantly, why does it work better ?
• One of the fundamental concepts in computing : locality of reference : pages or segments accessed last are MOST likely to be accessed again - so place them in the cache

  
Figure: Paging + Segmentation