20 Memory Management – Paging III
Mary Anitha Rajam
23.1 Introduction
There are memory management schemes, in which, the process need not be put as a whole contiguously into the main memory. The process can be divided or split into parts and each part can be put in different free spaces in the main memory. Paging and segmentation are examples of these memory management schemes.
Paging is a memory management scheme that lets the physical address space of a process to be noncontiguous. The process is allocated physical memory space, wherever space is available. In this scheme, the physical memory is divided into fixed-sized blocks called frames or page frames (size is power of 2, between 512 bytes and 8192 bytes). The logical memory is also divided into blocks of the same size called pages.
Since the physical memory is divided into frames, to know which frames are free, it is necessary to keep track of all the free frames. When a process of size n pages is to be placed in the main memory, it is necessary to find n free frames and load the pages of the process into these free frames. These frames where the pages are placed need not be contiguous. So, there arises a necessity to remember in which frames the pages are kept. For this, a page table is maintained. The page table helps in translating the logical addresses that are generated to physical addresses.
Hashed page tables, inverted page tables and hierarchical paging are some of the techniques for structuring the page table. In this module, we learn how hierarchical page tables are used and how pages can be shared.
23.2. Hierarchical Page Tables
Modern systems support large logical address space (232 bytes to 264 bytes). Therefore, the number of pages in a process becomes very large and the hence, the page table becomes large due to the large number of page table entries. Page tables are usually kept in the main memory. Since the size of the page tables becomes very large, it becomes difficult to place the page table as a whole into a single physical frame in the main memory. So, the single page table is now broken into multiple page tables.
When hierarchical paging is used, there are different ways in which the mapping can be done from the logical address to the physical address. A simple technique to implement hierarchical paging is a two-level page table. We now see using an example how two-level paging is implemented.
23.2.1 Two-Level Paging Example – I
Consider a 32-bit logical address space. Let the page size be 4K. Since it is a 32-bit logical address, the maximum size of a process can be 232. Since the page size is 212 (4K = 4 x 210), 12 bits are needed to address one of the 212 locations within a single page. The page offset therefore needs 12 bits. Of the 32 bits in the logical address, the remaining 20 bits (32 – 12) are used for the page number. Since the page number has 20 bits, 20 bits can be used to address 220 different pages. Also, if you divide the 232 byte logical address space by the size of the page (212), you get 220 pages. Therefore, the page table may have up to 220 entries, that is, about 1 million entries. If each entry in the page table is 4 bytes, each process might need up to 4 MB (4 x 220) physical address space for the page table alone (220 entires x 4 bytes = 4 MB). But the size of each page is only 4 KB. Hence, the page table (4 MB size) cannot be kept in a single page. Therefore, the page table is now paged (divided into pages). Similar to how the logical address space is divided into pages, the page table is now divided into pages.
Fig. 23.1 Two-level paging (Source: [1])
Figure 23.1 shows that the page table is divided into pages. Each page of the page table is placed in a different frame in the main memory. To know where each page of the page table is placed in the main memory, an outer page table is maintained. Each entry in the outer page table has the frame number of the frame in main memory where each page of the page table is kept. This is called two-level paging.
Suppose each entry in the page table is 4 bytes (32 bits). If page table size is 4KB, in 4KB, 1KB entries can be kept (since each entry is 4 bytes). To address one of these 1KB (210 ) entries within a page of the page table, 10 bits are needed. Therefore, the 20-bit page number is further divided into another 10-bit page number and a 10-bit page offset.
Fig. 23.2 Split up of logical address in two-level paging (Source: [1])
Thus, the logical address is split as shown in Figure 23.1, where p1 is used as an index into the outer page table. From the outer page table, the starting address of the page of the inner page table is obtained. p2 is the displacement within the page of the inner page table. From this entry the frame number of the page in memory is got. The offset d is added to the frame number to get the physical location in memory (Figure 23.3).
Fig. 23.3 Two-level paging – Address translation (Source: [1])
23.2.2 Two-Level Paging Example – II
Let us now look at another example where two-level paging is used. Consider the VAX architecture, which is a 32-bit machine with a page size of 512 bytes. Since the page size is 512 (29) bytes, the number of bits for the offset = 9. Therefore, the remaining 23 bits should be used for the page number. But, here, the logical address space is divided into four different sections, each consisting of 230 bytes. 2 bits are used to identify one of the four sections. The next 21 bits represent the logical page number. Thus, the logical address is divided as shown in Figure 23.4.
Fig. 23.4 Logical address – VAX 32-bit architecture (Source: [1])
s is the section number used to identify one of the sections, p is an index into the page table, and d is the displacement within the page. s is used to identify one of the four sections and p is used as an index into the page table of the identified section. The frame number is got from the page table. The frame number is added to the offset d to get the physical address.
23.2.3 Multi-level Paging
Let us look at yet another example of multi-level paging. Consider a 64-bit logical address space. The maximum size of a process can be 264. The size of each page is 4KB (212) bytes.
Therefore, the maximum number of pages in a process and hence the number of entries in a page table is (264 / 212) = 252. We see that the size of the page table becomes very large. 12 bits are used for the offset (since page size is 212). The remaining 52 bits are to be used for the page number. If two-level paging scheme is used, the inner page table is now divided into pages (each page having 210 4-byte entries) such that each page of the page in the page table can be placed in a single frame in the main memory. The addresses will now look like
| p1 | p2 | offset |
| 42 bits | 10 bits | 12 |
The outer page table will now have 242 entries which again, is very large. Hence, the outer page table is also divided into pages. Each entry in the outer page table is 4 bytes and hence there will be 210 entries in each page of the outer page table. The logical address will now look like
| p1 | p2 | p3 | offset |
| 32 | 10 | 10 | 12 |
The outer page table is still 232 bytes large. So, we can go for a four-level paging scheme.
Different architectures support different levels of paging. The SPARC architecture (32-bit addressing) supports a 3-level paging scheme. The 32-bit Motorola 68030 architecture supports 4-level paging scheme.
23.3 Shared Pages
The advantage of paging is the possibility of sharing common code. Consider 20 users, each using a text editor. The text editor has 150 KB of code and 50 KB of data space. To support 20 users, 50KB code has to be copied for all and hence 4000 KB (50KB x 20) space is needed. But, if the code is re-entrant (non-self-modifying – does not change during execution), the code can be shared. If the code can be shared, it is enough to have only one copy of the code part in the main memory. This one copy of code can be shared by all the users. Therefore, 3950 KB space is saved.
Consider the example shown in Figure 23.5. Process P1 is an editor process which has 4 pages. The editor’s code occupies the first 3 pages. The code part of the process occupies 1 page. Process P2 also has 4 pages. The first 3 pages are for text/code and the last page is for data. Similar is the case for process P3. The first 3 pages are kept as common to the three processes. The common pages ed1, ed2 and ed3 are kept in the frames 3, 4 and 6 respectively in the main memory. The mapping from the logical pages to the physical frames is done using the page table of each process. The data of the three processes P1, P2 and P3 are kept in frames 1, 7 and 2 respectively.
Thus, for shared code, it is enough to maintain only one copy of the code in the physical memory. For private code and data, each process keeps a separate copy of the data. Data pages are mapped onto different frames.
Fig. 23.5 Sharing of pages (Source: [1])
23.3.1 Sharing of pages in an inverted page table architecture
Fig. 23.5 Inverted page table architecture (Source: [1])
Inverted page tables cannot use shared pages. In inverted page table architecture, there is an entry in the page table corresponding to each frame in the physical memory. Each entry of the page table has the process id of the process whose page is kept in the corresponding frame and the page number of the page. For example, the fourth entry in the page table has the process id and the page number of the page kept in the fourth frame in the physical memory.
In shared pages multiple virtual addresses of different processes are mapped onto a single physical memory. In an inverted page table, it is not possible to share pages. If a page has to be shared, then the process ids of all the processes that are sharing the page should be kept in the page table, which is not possible. In an inverted page table, there is only one virtual page corresponding to one physical page. Hence multiple processes cannot share a page.
23.4 Summary
When logical address space becomes larger, size of page table becomes large. Hence, paging of page tables is done. Sharing of pages is possible if the contents of the page do not get modified during execution. Pages cannot be shared if inverted page tables are used.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.
- Charles Crowley, “Operating Systems: A Design-Oriented Approach”, Irwin Professional Publishing, 1996.