Multilevel Paging Operating System

1
votes

I had this problem in an exam today:

Suppose you have a computer system with a 38-bit logical address, page size of 16K, and 4 bytes per page table entry.

  1. How many pages are there in the logical address space? Suppose we use two level paging and each page table can fit completely in a frame.

  2. For the above mentioned system, give the breakup of logical address bits clearly indicating number of offset bits, page table index bits and page directory index bits.

  3. Suppose we have a 32MB program such that the entire program and all necessary page tables (using two level paging) are in memory. How much memory (in number of frames) is used by the program, including its page tables?

How do I go about solving such a problem? Until now I would have thought page size = frame size, but that won't happen in this case.

Here is what I think:

Since the page size is 16K, my offset will be 17 bits (2^17 = 16K). Now how do I divide the rest of the bits, and what will be the frame size? Do I divide the rest of the bits in half?

1
operating-systempaging
@MichaelPetrotta well, since Page size is 16K, now this means my offset will be 17 bits(2^17 = 16K). Now how do i divide my rest of the bits, and what will be my frame size? Do i divide my rest of the bits in half? - Kraken
@Karan: your offset within a page is 14-bit long because 2^14=16384. Use a calculator... - Alexey Frunze

1 Answers

3
votes
  1. 238 / 16384 = 16777216 pages.
  2. On one hand, the remaining 38-log216384=24 bits of address may be reasonable to divide equally between the page directory and page table portions of the logical address since such a symmetry will simplify the design. On the other hand, each page table should have the same size as a page so they can be offloaded to the disk in exactly the same way as normal/leaf pages containing program code and data. Fortunately, in this case using 12 bits for page directory indices and page table indices gets us both since 212 * 4 bytes of page table entry size = 16384. Also, since a page address always has 14 least significant bits set to zero due to the natural page alignment, only 38-14=24 bits of the page address need to be stored in a page table entry and that gives you 32-24=8 bits for the rest of control data (present, supervisor/user, writable/non-writable, dirty, accessed, etc bits). This is what we get assuming that the physical address is also not longer than 38 bits. The system may have slightly more than 38 bits of the physical address at the expense of having fewer control bits. Anyway, everything fits. So, there, 38=12(page directory index)+12(page table index)+14(offset).
  3. 32MB/16KB = 2048 pages for the program itself. Each page table covers 212=4096 pages, so you will need about 2048/4096=0 page tables for this program. We round this up to 1 page table. Then there's also the page directory. 2048+1+1=2050 is how many pages are necessary to contain the entire program with its related pages tables in the memory.