ü It is a memory management scheme that permits the physical address space of a process to be noncontiguous.
ü It avoids the considerable problem of fitting the varying size memory chunks on to the backing store.
Divide logical memory into blocks of same size called “pages”.
Divide physical memory into fixed-sized blocks called “frames”
Page size is a power of 2, between 512 bytes and 16MB.
Address Translation Scheme
Address generated by CPU(logical address) is divided into:
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 address i.e.,
Physical address = base address + offset
Paging example for a 32-byte memory with 4-byte pages
Page size = 4 bytes
Physical memory size = 32 bytes i.e ( 4 X 8 = 32 so, 8 pages)
Logical address =0‘ maps to physical address 20 i.e ( (5 X 4) +0)
Where Frame no = 5, Page size = 4, Offset = 0
v When a process arrives into the system, its size (expressed in pages) is examined.
v Each page of process needs one frame. Thus if the process requires =n‘ pages, at least =n‘ frames must be available in memory.
v If =n‘ frames are available, they are allocated to this arriving process.
v The 1st page of the process is loaded into one of the allocated frames & the frame number is put into the page table.
v Repeat the above step for the next pages & so on.
It is used to determine which frames are allocated, which frames are available, how many total frames are there, and so on.(ie) It contains all the information about the frames in the physical memory.
v This can be done in several ways : o Using PTBR
v The simplest case is Page-table base register (PTBR), is an index to point the page table.
v TLB (Translation Look-aside Buffer)
o It is a fast lookup hardware cache.
o It contains the recently or frequently used page table entries. o It has two parts: Key (tag) & Value.
o More expensive.
Paging Hardware with TLB
v When a logical address is generated by CPU, its page number is presented to TLB.
v TLB hit: If the page number is found, its frame number is immediately available & is used to access memory
v TLB miss: If the page number is not in the TLB, a memory reference to the page table must be made.
v Hit ratio: Percentage of times that a particular page is found in the TLB. For example hit ratio is 80% means that the desired page number in the TLB is 80% of the time.
v Effective Access Time:
§ Assume hit ratio is 80%. If it takes 20ns to search TLB & 100ns to access memory, then the memory access takes 120ns(TLB hit)
§ If we fail to find page no. in TLB (20ns), then we must 1st access memory for page table (100ns) & then access the desired byte in memory (100ns).
Therefore Total = 20 + 100 + 100
= 220 ns(TLB miss).
Then Effective Access Time (EAT) = 0.80 X (120 + 0.20) X 220. = 140 ns.
v Memory protection implemented by associating protection bit with each frame
v Valid-invalid bit attached to each entry in the page table:
“valid (v)” indicates that the associated page is in the process‘ logical address space, and is thus a legal page
“invalid (i)” indicates that the page is not in the process‘ logical address space.
(iv) Structures of the Page Table
a) Hierarchical Paging
b) Hashed Page Tables
c) Inverted Page Tables
a) Hierarchical Paging
Break up the Page table into smaller pieces. Because if the page table is too large then it is quit difficult to search the page number.
Example: “Two-Level Paging “
It requires more number of memory accesses, when the number of levels is increased.
(b) Hashed Page Tables
Each entry in hash table contains a linked list of elements that hash to the same location. Each entry consists of;
(a) Virtual page numbers
(b) Value of mapped page frame.
(c) Pointer to the next element in the linked list.
· The virtual page number in the virtual address is hashed into the hash table.
· Virtual page number is compared to field (a) in the 1st element in the linked list.
· If there is a match, the corresponding page frame (field (b)) is used to form the desired physical address.
· If there is no match, subsequent entries in the linked list are searched for a matching virtual page number.
Clustered page table:
v It is a variation of hashed page table & is similar to hashed page table except that each entry in the hash table refers to several pages rather than a single page.
(c)Inverted Page Table
v It has one entry for each real page (frame) of memory & each entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page. So, only one page table is in the system.
v When a memory reference occurs, part of the virtual address, consisting of <Process-id,
Page-no> is presented to the memory sub-system.
v Then the inverted page table is searched for match:
(i) If a match is found, then the physical address is generated.
(ii) If no match is found, then an illegal address access has been attempted.
· Merit: Reduce the amount of memory needed.
· Demerit: Improve the amount of time needed to search the table when a page reference occurs.
(v) Shared Pages
v One advantage of paging is the possibility of sharing common code.
§ Shared code
o One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems).
o Shared code must appear in same location in the logical address space of all processes
§ Reentrant code (Pure code): Non-self modifying code. If the code is reentrant, then it never changes during execution. Thus two or more processes can execute the same code at the same time.
§ Private code and data: Each process keeps a separate copy of the code and data.