Operating System- Multilevel Paging, Inverted Page Table

A slide on Multilevel Paging and Inverted Page Table.

1. Operating System Assignment- 2

2. Name- Zishan Mohsin Branch-C.S.E-4 Roll No-1000112240 Class Sl No-53 Submitted to- Dr.Mohd.Rizwan Beg Sir

3. 1- Multilevel Paging Modern computer systems support a large logical-address space. In such a condition, the page table itself becomes excessively large and it is clear that, we would not want to allocate the page table contiguously in main memory. One simple solution to this problem is to divide the page table into smaller pieces.There are several ways to accompalish this division. One way is to use a two-level paging algorithm,in which the page table itself is also paged. Two-Level Paging   A logical address (on 32-bit machine with 4K page size) is divided into:

4.    page number                                                   page offset    p1      p2 d     10 10 12 where  pi  is an index into the outer page table, and  p2  is the  displacement within the page of the outer page table.    1. a page number consisting of 20 bits.    2. a page offset consisting of 12 bits. Since the page table is paged, the page number is further  divided into:   3. a 10-bit page number.   4. a 10-bit page offset.   5. Thus, a logical address is as follows:

5. Multilevel Paging Page 0 ... ... ... Outer Page Table Logical Memory ... ... Page Table ... page number p1 page offset d 10 12 p2 10

6. Multilevel Paging Translation page number p1 page offset d p2 outer page table inner page table desired page d p2 p1

7. Advantages of multi-level paging: The hierarchical system has its advantages in that all those that live in a system understand what extortionists they need to pay and obey.

8. Problem with multi-level paging: Extra memory references to access translation tables can slow programs down by a factor of two or more. Solution: Use translation look-aside buffers (TLB) to speed up address translation

9. Consider a system in which the virtual address space is 64 bits, the page size is 4KB, and the amount of physical memory is 512MB. How much space would a simple single-level page table take? Such a table contains one entry per virtual page, or 264−12 = 252 entries. Each entry would require about 4 bytes, so the total page table size is 254 bytes, or 16 petabytes ( peta - > tera - > giga -)! And this is for each process! Of course, a process is unlikely to use all 64 bits of address space, so how about using multilevel page tables? How many levels would be required to ensure that each page table require only a single page? Assuming an entry takes a constant 4 bytes of space, each page table can store 1024 entries, or 10 bits of address space. Thus d52/10e = 6 levels are required. But this results in 6 memory accesses for each address translation ! Inverted Page Table

10. But notice that there are only 512MB of memory in the system, or 229−12 = 217 = 128K physical pages. If we can somehow manage to store only a single page table entry per physical page, the page table size decreases considerably, to 2MB assuming each entry takes 16 bytes. And since processes share physical memory, we need only have a single global page table. This is the concept of an inverted page table. 1.1 Linear Inverted Page Tables The simplest form of an inverted page table contains one entry per physical page in a linear array. Since the table is shared, each entry must contain the process ID of the page owner. And since physical pages are now mapped to virtual, each entry contains a virtual page number instead of a physical. The physical page number is not stored, since the index in the table corresponds to it.

11. As usual, information bits are kept around for protection and accounting purposes. Assuming 16 bits for a process ID, 52 bits for a virtual page number, and 12 bits of information, each entry takes 80 bits or 10 bytes, so the total page table size is 10 · 128KB = 1.3MB. In order to translate a virtual address, the virtual page number and current process ID are compared against each entry, traversing the array sequentially. When a match is found, the index of the match replaces the virtual page number in the address to obtain a physical address. If no match is found, a page fault occurs.

12. 1.2 Hashed Inverted Page Tables A hashed inverted page table adds an extra level before the actual page table, called a hash anchor table. This table is at least as large as the page table, and maps process IDs and virtual page numbers to page table entries. Since collisions may occur, the page table must do chaining. Since each member in the chain must map to a physical page and therefore must have a corresponding page table entry, the chain can be represented as a sequence of page table entries, with each entry pointing to the next entry in the chain

13. This requires an extra 4 bytes per entry, so the page table size is now 14 ·128KB = 1.8MB. The hash anchor table takes an additional 4 · 128KB = 512KB, for a total of 2.3MB. Now in order to translate a virtual address, the process ID and virtual page number are hashed to get an entry in the hash anchor table. The entry’s pointer to a page table entry is followed, and the process ID

14. and virtual page number are compared against that stored there. If they don’t match, the page table entry’s next pointer is followed to get another page table entry, and the process is repeated until a match is found. Figure-1

15. Figure-2

16. Figure 1: Translation procedure using a linear inverted page table. Info bits exist in each entry, though they are not shown. If a chain is exhausted by hitting an invalid next pointer, a page fault results. The translation process is illustrated in figure 2. Assuming a good hash function, the average chain length should be about 1.5, so only 2.5 memory accesses are required on average to translate an address [1]. This is pretty good, considering a two-level page table requires 2 accesses. Caching can still improve the access time considerably.

17. ● Use hash table to limit the search to one — or at most a few — page-table entries .

18. ● One entry for each real page of memory. ● Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page. ● Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs .