Im studying operating systems and i found an exercise that i cant solve. It asks to compute the memory space needed for a two level page table. The logical addresses are 32 bit, Page size is 4KB and the page entry size is 4 bytes. from the page size i found out that the offset is 12bits from the 32 of the memory address and that every page has 1024 entries. So the 32 bit memory address is like this: 10 bits | 10 bits | 12 bits for outer table, inner table and offset. How can i calculate the memory size i need? (assume that all inner tables are used)
This is a textbook exercise, maybe answering that exerise is part of your homework, so read your lessons, think about a possible answser, take a sheet of paper and draw rectangles and arrows representing memory, page tables, pointers...
First, an historical note, this arrangement 10 | 10 | 12 is the one used in 32bits x86 CPUs, which were fairly popular!
4GB memory is divided into 1Million 4kB pages ( binary million = 2^20). Each "Page Table Entry" occupies 4 bytes. Total = 4MB. These entries are arranged in 1024 tables of 1024 entries. The indexes for the 1024 tables, "Page Directory Entries" each take 4 bytes (on x86, this is usually the same size as PTEs), so 4KB. Total size is therefore 4MB+4kB = 4100kB
A few remarks :
- This size is only needed for mapping the whole 4GB address space. If there is less memory installed, the page tables can be smaller with "invalid" or "unmapped" entries in the first level page table.
- A multitasking OS need to manage different memory maps for the different running applications, so there can be several copies of the page tables.
If we use just paging then it will contain 4MB to maintain table details because (2^32/2^12) = 2^20 pages. we store this page table in physical memory . So 4MB is just wasted to store the page table and the access rate is very slow because if you are going to search a page in 1 million page is much more difficult task . So we can use two level paging , it makes easy to access and less memory to maintain the table . So there is no concern with the physical memory it will take in this example. It will take same physical memory it has taken in the paging without two level paging