Structure of the page table

Structure of the page table

1. STRUCTURE OF THE PAGE TABLE PRESENTATION BY D.Madhuri

2. PAGE TABLE : A PAGE TABLE is the data structure used by a virtual memory system in a computer operating system to store the mapping between virtual addresses and physical addresses.

3. Common Techniques used for structuring the page table are : Hierarchical paging Hashed page tables Inverted page tables

4. Hierarchical paging: It is also known as multilevel paging. The page table might be too big to fit in a contiguous space , so we may have a hierarchy with several levels. So , we break up the logical address space into multiple page tables. For this a simple techniques we can use are: Two level page table Three level page table

5. Two level paging: A logical address (on 32-bit machine with 4k page size) is divided into: A page number consisting of 20 bits. A page offset consisting of 12 bits. Since the page table is paged , the page number is further divided into: A 10-bit page number. A 10-bit page offset. Thus a logical address is as follows: page number | page offset 10 10 12 pi p2 d

6. Address translation scheme for the two level paging is as follows:

7. Three level paging: A logical address(on 64-bit machine with 4k page size) is divided into: outer page inner page offset 42 10 12 2 nd outer page outer page inner page offset 32 10 10 12 Pi P2 d Pi P2 P3 d

8. Hashed page tables: It is a common approach used when address space is >32 bits. The virtual page number is hashed into a page table . This page table contains a chain of elements hashing to the same location. Each element consists of three fields: 1. The virtual page number 2. The value of the mapped page frame 3. A pointer to the next element in the linked list.

9. Address translation scheme for the hashed page table is as follows:

10. Inverted page tables: The inverted page table combines A page table and A frame table into one data structure. One entry for each virtual page number & 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.

11. Address translation scheme for the Inverted page table is as follows: