concept
Its a memory-management scheme that permits the Physical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available
Divide physical memory into fixed-sized blocks called frames
Size is power of 2, between 512 bytes and 16 Mbytes
Divide logical memory into blocks of same size called pages
To run a program of size N pages, need to find N free frames and load program
Set up a page table to translate logical to physical addresses
Backing store likewise split into pages
disadvantage : Still have Internal fragmentation
Address Translation Scheme
Page number (p) – used as an index into a page table which contains base address of each page in physical memory
Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit
Calculating internal fragmentation
Page size = 2,048 bytes
Process size = 72,766 bytes
35 pages + 1,086 bytes
Internal fragmentation of 2,048 - 1,086 = 962 bytes
Worst case fragmentation = 1 frame – 1 byte
On average fragmentation = 1 / 2 frame size
So small frame sizes desirable?
But each page table entry takes memory to track
Page sizes growing over time
Implementation of Page Table
Page table is kept in main memory
Page-table base register (PTBR) points to the page table
Page-table length register (PTLR) indicates size of the page table
In this scheme every data/instruction access requires two memory accesses
One for the page table and one for the data / instruction
The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)
Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
On a TLB miss, value is loaded into the TLB for faster access next time
Replacement policies must be considered
Some entries can be wired down for permanent fast access
Associative Memory
Associative memory – parallel search
Address translation (p, d)
If p is in associative register, get frame # out
Otherwise get frame # from page table in memory
Effective Access Time
Associative Lookup = "e" time unit
Can be < 10% of memory access time
Hit ratio = "a"
Hit ratio – percentage of times that a page number is found in the associative registers; ratio related to number of associative registers
Consider "a" = 80%, "e" = 20ns for TLB search, 100ns for memory access
EAT = 0.80 x (20 + 100) + 0.20 x (20 + 100 + 100) = 140ns
Consider slower memory but better hit ratio -> "a" = 98%, "e" = 20ns for TLB search, 140ns for memory access
EAT = 0.98 x 160 + 0.02 x 300 = 162.8ns
Memory Protection
Memory protection implemented by associating protection bit with each frame to indicate if read-only or read-write access is allowed
Can also add more bits to indicate page execute-only, and so on
Valid-invalid bit attached to each entry in the page table:
“valid” indicates that the associated page is in the process's logical address space, and is thus a legal page
“invalid” indicates that the page is not in the process’ logical address space
Or use PTLR (Page-table length register)
Shared Pages
Shared code
One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems)
Similar to multiple threads sharing the same process space
Private code and data
Each process keeps a separate copy of the code and data
The pages for the private code and data can appear anywhere in the logical address space
