How to Implement The Page Table?

PropellerAds

Every access to memory should go through the page table. Therefore, it must be implemented in an efficient way.

a. Using fast dedicated registers
Keep page table in fast dedicated registers. Only the OS is able to modify these registers. However, if the page table is large, this method becomes very expensive since requires too many registers.

using-fast-dedicated-registers

Given a logical address to access the word in physical memory, first access the PT stored in registers, which requires register access time (rat), and then find out the physical address and access the physical memory, which requires memory access time (mat). Therefore effective memory access time (emat) becomes:
emat= rat + mat

b. Keep the page table in main memory
In this method, the OS keeps a page table in the memory. But this is a time consuming method. Because for every logical memory reference,

two memory accesses are required: 
1. To access the page table in the memory, in order to find the corresponding frame number.
2. To access the memory word in that frame

keep-the-page-table-in-main-memory

In this approach emat is:
emat= 2 * mat

c. Use content-addressable associative registers
These are small, high speed registers built in a special way so that they permit an associative search over their contents. That is, all registers may be searched in one machine cycle simultaneously. However, associative registers are quite expensive. So, a small number of them should be used.

use-content-addressable-associative-registers

When a logical memory reference is made, first the corresponding page number is searched in associative registers. If that page number is found in one associative register (hit) then the corresponding frame number is get, else (miss) the page table in memory is accessed to find the frame number and that pair is stored into associative registers. Once the frame number is obtained, the memory word is accessed.

The hit ratio is defined as the percentage of times that a page number is found in associative registers. Hit ratio is important in performance of the system since it affects the effective memory access time. In the case of finding the page number in associative registers, only one memory access time is required whereas if it cannot be found two memory accesses are needed. So, greater the hit ratio, smaller the effective memory access time. Effective
memory access time is calculated as fallows:
formula-1

Sharing Pages

Sharing pages is possible in a paging system, and is an important advantage of paging. It is possible to share system procedures or programs, user procedures or programs, and possibly data area. Sharing pages is especially advantageous in time-sharing systems. A reentrant program (non-self-modifying code = read only) never changes during execution. So, more than one process can execute the same code at the same time. Each process will have its own data storage and its own copy of registers to hold the data for its own execution of the shared program

Try Now – Operating Systems MCQs
Practice Now – Operating System Online Test