Paging Flashcards
how is data structured in paging?
- physical address space is divided into fixed size blocks called frames
- logical address space is divided into fixed size blocks called pages
- logical pages are allocated into physical frames
- logical addresses are split into page number p and offset d. the page number is an index into the page table
page table PER PROCESS:
a lookup table mapping page numbers to frame addresses. offset is then used.
how is address structured?
page number p = m-n
page offset d = n
with logical address space 2^m
and page size 2^n
how are processes assigned frames?
there is a free-frame list and the first n frames are given to the process, not necessarily in order. then the n pages that the process uses map to the n frames
external and internal fragmentation in paging?
no external fragmentation
but internal fragmentation can occur within pages
what is the TLB?
the translation lookaside buffer
a cache that examines all keys simultaneously
fast and expensive, so its small
a subset of page table entries are stored in the TLB
- keys are page numbers, values are frame numbers
- we look in the TLB before the page table
- if we miss
- – lookup in page table
- – store mapping in TLB
- – we may need to replace something
what is the TLB hit ratio? what is EAT?
- percentage of time we find a page number in the TLB
- determines the Effective memory Access Time EAT
eat = ( hit ratio x ( memory access time + TLB access time) ) + ( ( 1 - hit ratio) x ( 2 x memory access time + TLB access time)
what is a protection bit?
protection bits are associated with each frame, stored in the page table
one bit can indicate read/write or read only
violation will cause a trap to kernel
can have finer levels of protection with more bits, cominations or read/write/exe
what is hierarchical paging?
the page table itself is paged
the motivation for this is that the table may become very large in a modern system. by paging the page table we break the problem down into smaller pieces
the outer page table pages the inner one, which acts as normal
what is inverted paging?
we have a single central page table, shared between all processes, rather than one per process with an entry for each page used. this is because the size of the logical memory gets impossibly large, and the page table becomes unreasonably large
an entry for each frame, with a process id of the process using it assigned to frames
SORTED BY PHYSICAL ADDRESS
instead of saying “this is the page number, what is the frame number?” we say “this is the frame number for this process
this makes it difficult to share as we have a 1 to 1 mapping of virtual to physical memory
good at saving memory, but we have to walk through the memory
how is hashing used in paging?
in inverted paging we have to walk through the table
a hash function is applied to the page number
its a hit if the process id matches the current process
collisions are dealt with using a chaining scheme
