Search code examples
operating-systempagingpage-tables

How is the page number checked against the PT entries?

In the book Operating System Concepts by Silberschatz et al. and in other representations of paging, each Page Table (PT) entry is shown to contain a Frame Number(FN). I have been trying to solve some problems on this topic and the solutions also assume the same.

Image

I am new to this topic and all I've read is that the PT (or part of it) is usually stored in the physical memory. This means that the PT must start at some particular physical address. This value is stored in the PTBR. So when the CPU generates a logical address which is divided into a Page Number(PN) and the offset, the PN must be compared against it's value in the PT to determine the corresponding FN, right? Suppose, p=14. Now, 14, in its binary form, must be checked in the PT to find the entry 14.

So, does this mean that some bits of each entry of the PT store the PN and the rest of them store the corresponding FN? Then what about the problems which calculate the PT size assuming that it's only a multiple of the number of bits of the FN and completely ignore the PN bits? Or is it that since the values in the PT are stored in increasing order of PN, some calculations are performed on the PTBR to get the particular PT entry? If so, once the calculation to access the particular PT entry has been done, how is the memory access switched from the base address in the PTBR to the 'n'th entry? What hardware is used for that switch?

Basically, what I'd like to know is, where is the index, p(page number), which checks for the corresponding FN stored? How exactly is this value checked against the PT entries to get the FN?

Solution

  • Physical Page Frames are stored sequentially in hardware.

    A logical address consists of a logical page number and an offset into the page. For page translation, we can ignore the offset.

    In the simplest case, the page table is an array of Page Table Entries. The Logical Page Number serves as an indicate into this table.

    The Page Table Entry may or may not have a value for a Physical Page Frame.

    This means that the PT must start at some particular physical address. The address and size of the Page Table is usually specified by hardware registers.

    So when the CPU generates a logical address which is divided into a Page Number(PN) and the offset, the PN must be compared against it's value in the PT to determine the corresponding FN, right?

    You appear to be describing an INVERTED PAGE TABLE that is used on a few processors. In most systems the Page Number is an index into the table. There is no comparison.