Next: How do we replace
Up: No Title
Previous: Segmentation
- 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
![figure103](img7.gif)
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)
![figure109](img8.gif)
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
![figure121](img9.gif)
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
![figure137](img11.gif)
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
![figure146](img12.gif)
Figure: Paging + Segmentation
Next: How do we replace
Up: No Title
Previous: Segmentation
Omer F Rana
Thu Feb 13 12:31:55 GMT 1997