Question

Suppose a machine does not use a multi-level page table. Suppose further, that the system uses a 54-bit virtual address and a 30-bit physical address. If the page size is 16K, how many entries should you have in the page table? You may express the answer as a power of 2.

(1) Is the decision to have a single level page table a reasonable one? Explain

(2) If you are to use the inverted page table in this system, what would be the size of the page table in bytes? Assuming that a process ID takes 3 bytes to store.

(3) If you are to use a multiple level paging for the above system, how many levels would you introduce and why? Describe the format of a virtual address showing the size of each field.

Answer 1

logial/virtual address space=$2^{54}$ bytes

physical address space=$2^{30}$ bytes

page size=16K=$2^{4}$ x $2^{10}$ bytes=$2^{14}$ bytes

so,total number of pages in the logical address space= $2^{54}/2^{14}}$ =$2^{40}$

also,total number of pages in the logical address space=Total number of entries in the page table=$2^{40}$

(1)In a single level page table, the whole table will be searched even for a small amount of data, so space required to access any data is =$2^{40}$ x 4 bytes which is a huge space if we assume that size of each page table entry is 4 bytes. But,paging pages in multilevel paging is more specific, we can decide with the help of the multi level paging scheme that which specific page among the $2^{40}$ pages has the data and selects it.So,here we need only the specific page to be in memory while we run the process. So, instead of single level page table, it is better to use multi level page table.

(2)Process ID needs 3 bytes.

Each entry of the inverted page table contains Process ID,Page number, and page size(offset) which is a total of 54 bits(Virtual address)

page size=16K=$2^{14}$ bytes

so,14 bits are required for offset.

therefore,bits needed to store page number=54-(offset+process ID)=54-(14+3)=37 bits

physical address space=$2^{30}$ bytes

total number of frames in the physical address space=$2^{30}/2^{14}=2^{16}$ = Total entries in the inverted page table

here we have taken frame size=page size=$2^{14}$ bytes

size of each page table entry in the inverted page table=(process ID+page Number) bits=(3+37)bits=40 bits

so,size of the inverted page table=number of entries in the inverted page table x size of each page table entry

=$2^{16}$ x 37 bits

=2^13 x 37 bytes

=303104 bytes

(3)here, the size of each page table entry is not mentioned,it should be there in question.

let me assume it to be of 4 bytes

page size=$2^{14}$ bytes

number of page table entry in each page=($2^{14} /4$) =$2^{12}$

total number of entries in the page table=$2^{40}$

Number of pages in the first level page table=($2^{40} /2^{12}$)=$2^{28}$

Number of pages in the second level page table=$2^{28}/2^{12}}$=$2^{16}$

Number of pages in the third level page table=$2^{16}/2^{12}}$=$2^{4}$

Number of pages in the fourth level page table=$2^{4}/2^{12}$=1(we take it as 1 as it comes less than 1 and total entries in page table can't be in fraction)

So, 4 level page table is used, only if we take page size entry as 4 bytes.(as there is no information about page size entry in question,the result may vary with different page size entry, but the process to calculate the number of levels of the page table is the same).

Format of virtual address(total 54 bits):-

4

12

12

12

14

where the last 14 bits denotes offset, the three consecutive 12 bits are for the first 3 levels of the page table from right and the last 4 bits are for the fourth level of the page table.