TANENBAUM - Memory Management - Paging

Question

A computer has 32-bit virtual addresses and 4-KB pages. The program and data together fit in the lowest page (0-4095). The stack fits in the highest page.  How many page table entries are needed for two-level paging, with 10 bits in each part?

Comments

Question 9: A computer has 32-bit virtual addresses and 4-KB pages. The program and data together fit in the lowest page (0-4095). The stack fits in the highest page. How many en tries are needed in the page table if traditional (one-level) paging is used? How many page table entries are needed for two-level paging, with 10 bits in each part?

Answer: For a one-level page table, there are 232 / 2 12 or 1M pages needed. Thus the page table must have 1M entries. For two-level paging, the main page table has 1K entries, each of which points to a second page table. Only two of these are used. Thus in total only three page table entries are needed, one in the top-level table and one in each of the lower-level tables

--i found the solution in one of the sites but did nt get it fully
http://www.vumultan.com/Books/CS703_(23-45)_100_QA_Tanenbaum.pdf?bcsi_scan_64741547a7fe261b=0&bcsi_scan_filename=CS703_(23-45)_100_QA_Tanenbaum.pdf
--how are 3 page table entries required for 2 level?pls explian

Answer 1

2M total page table entries will be there

10 bits each means 10 bits each for outer and inner page tables .
ie
Out 32 bit  Virtual Address 12 bits are used as page offset remaining is 20 bits
Out of this 20 bits 10 bits each is used for each level of paging .

Comments

how are there 2 entries in outer pae table and 2 entries in inner??can you pls elaborate more??

---

is'nt this possible that data/code page and stack page are referenced by same page table of second level instead ofdifferent page tables at second level and with that ,we will need only 1 entry in first level..?

i mean how u got to know that data/code and stack page are pointed by diff second level page tables.??

---

The program and data together fit in the lowest page (0-4095).
The stack fits in the highest page."

Lowest Page

0000 0000 00

0000 0000 00

xxxx xxxx xx

Code / Data is at page 0 of outer page and page 0 of inner page

Highest Page

1111 1111 11

1111 1111 11

xxxx xxxx xx

Stack resides at page 1023th of outer page table and 1023th  of inner page table

See diagram it should bring more clarity .

We need to have 4 entries in total.

Dont trust in my solution . Just challenge your intellectual :)
May be @Kapilp @vijaycs @sreshtha @mcjoshi @gabbar could help u better :)

Answer 2

as question says it implements 2 level paging,out of 32 bits 12 bits are used for page size,remaining 20 bits are used for first and second level paging.(10 for each).

Comments

ooh ohkay..so how many page table entries are there in two level paging scheme??

---

give me a program size

---

program size is not given..neither do you want here.

Answer 3

The program and data toget­her fit in the lowest page (0-4095) The stack fits in the highest page.

means they will only occupy one frame since frame size is 4KB.so one entry is for this page in first level

and stack occupy highest page so one more entry for stack,as only required pages are brought in memory.

so total 2 entries in first level page table

So, while the total number of page table entries is 1048576, of those you only use 2 entries, one for each of those 2 pages (entry 0 points at the code/data page and entry 1048575 points at the stack page)

see pc diagram above for more clarification of what i am saying..

but for two level paging there will be 2 more entries for two first level pages i mentioned above

for more detailed https://stackoverflow.com/questions/12485737/oper-systems-and-memory-management-theoretical