Shulou(Shulou.com)06/03 Report--

This article mainly explains the "methods and steps for the establishment of the paging mechanism". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. let's study and learn the methods and steps for the establishment of the paging mechanism.

1. Logical address, linear address, virtual address and physical address are confused. (1) logical address

Under the IA-32 architecture, segmentation is necessary, but paging is not necessary. Regardless of paging or not, the strategy of "segment base address: intra-segment offset address" must be adopted to access memory. Therefore, access to memory requires a total of 48 bits of 16-bit address information, which is the logical address, the top 12 bits are segment selectors, and the last 32 bits are intra-segment offset addresses.

(2) Linear address

The 32-bit segment base address is obtained by using the selective sub-index to the segment descriptor, and the 32-bit offset address in the logical address is added to get a 32-bit address information, which is the linear address.

(3) Virtual address

If the paging mechanism is not enabled, the linear address is the physical address, and if the paging mechanism is enabled, the linear address is also called the virtual address.

(4) physical address

Physical address, needless to say, the real address of the memory unit

2. What is pagination?

Paging is essentially a mechanism by which memory segments of different sizes are split into blocks of the same size (usually 4KB) for memory management.

3. Why should it be paginated?

The main reason is to facilitate memory management, to solve the problem of too many applications in pure segmentation, or too much memory fragmentation to accommodate new processes. Or the problem of not finding a suitable memory area when reloading a memory segment (previously swapped out). The reason for this: in the case of segmentation only, the linear address is the physical address, and both are contiguous and inflexible, making it impossible to find the right memory area every time. In paging, linear addresses need to be further converted into physical addresses, linear addresses are continuous, but physical addresses can be discontiguous, so it is very flexible to find a suitable memory area, which solves the above problems.

4. Paging mechanism? (based on 32-bit system) (1) Page table

The core function of paging mechanism is to realize the transformation from virtual address to physical address. How to transform it? The mapping relationship between the virtual address and the physical address is established by the page table, and with this mapping relationship, the virtual address can be transformed into the actual physical address. The general idea is to regard the high 20 bits of the virtual address as an index number, index the page table item in the page table, get the physical base address, and add it to the low 12-bit offset address of the virtual address to get the final physical address. This is also the way to convert virtual addresses into physical addresses under the first-level page table, but the first-level page table is not applicable and multi-level page tables are generally used.

(2) Page table entry

A brief introduction to the structure and property bits of page catalog items and page table items is as follows:

(3) second-level page table and address translation

The principle of conversion from virtual address to physical address under the second-level page table is the same as that under the first-level page table, but one more step is carried out. Take a look at the figure first:

The first step: use the segment selector to index the segment descriptor in the GDT, "take out" the segment base address, and the segment component adds the segment base address and the offset address to get a linear address, that is, a virtual address. The second step: take the high 10 bits of the virtual address as the index number to index the page directory entry in the page catalog table. The specific operation: multiply the virtual address high 10 bits by 4 plus the physical address of the page directory in CR3 to get the address of the desired page directory entry, namely a+0x44. The third step: take the 10 bits of the virtual address as the page table item in the secondary page table of the index number index, the specific operation: "take out" the 20-bit page table physical address in the page directory entry, that is, 0x1000. Plus 10 bits in the virtual address multiplied by 4 to get the physical page address, namely 0x1000+0x2344. The fourth step: the last 12-bit offset address of the virtual address and the physical page address obtained in the third step are added to get the final actual physical address. As shown in the figure, 0xfa000+0x567=0xfa567 is the physical address of the last target.

The above is the process of address conversion under the second-level page table, and the method of address conversion under the third-level or even multi-level page table is the same, but the operation of the third step is repeated.

Note: the function of the paging mechanism is to convert the virtual address into a physical address, but in the actual conversion process, it is equivalent to turning off the paging mechanism. That is, the addresses involved in the process of address conversion (CR3 page directory address, page directory entry address, page table entry address) are all actual physical addresses and will not be converted by the paging mechanism, otherwise they will be recursive infinitely.

(4) Why is the first-level page table not applicable?

A 4B page table item points to a 4K page, and 4G / 4K = 1m page table items are required to map the entire 4G space, so the entire page table size is 4m. A process needs a page table of 4m size, and if there are many processes, it will spend a lot of memory to store the page table. In addition, this is only a 32-bit system with only 2 ^ 32 ^ B = 4GB memory. For a 64-bit system, it would require 2 ^ 64 ^ / 2 ^ 12 ^ = 252 page table items, which is simply unthinkable.

(5) Why is the multi-level page table more space-efficient than the first-level page table?

First of all, the page table is a whole, and the 4m (32-bit) page table under the first-level page table is a whole, which needs to be created completely, so each process should have a 4m page table, so the page table really takes up a lot of space. On the other hand, the multi-level page table only establishes the page table for that part of the virtual memory actually used by the process, using only one-level page table needs to create all the page table items, while the multi-level page table only establishes the required page table, which of course saves more space. So why do you only need to create the required part of the page table under the multi-level page table? The multi-level page table is equivalent to paging the first-level page table again, dividing a large page table into several small page tables, and then making several if you want to, which is very flexible and space-saving. Some operating system virtual memory management systems are also implemented in this way, only when a virtual address needs a new page table to map, it will allocate physical pages to it, which achieves the principle of establishing only when necessary, so it saves more space than the first-level page table.

5. How to establish a paging mechanism? (general idea)

1. To establish an initial page table, to establish a page table is to establish a mapping relationship, and to establish a mapping relationship is to add page table items. The virtual address of the operating system kernel is above 0xc0000000, and the initial working address is 1m at the low end of physical memory, so the mapping relationship here is to map the low end 1m of physical memory to more than 0xc0000000 in the virtual address space. 2. GDT, kernel stack, etc., should be placed in the kernel, and its address value needs to be modified. The segment base address in some descriptors also needs to be modified, because the original address is the actual physical address, and the virtual address should be used when paging is enabled. 3. Assign the page directory address to the CR3 register. 4. Turn on the paging mechanism by setting the PE position 1 of the CR0 register. 5. Reload GDT.

At this point, the paging mechanism is enabled, and then the addresses that appear in the operation of the system are virtual addresses, which need to go through the transformation shown in the figure above to obtain the actual physical address.

5. What are the disadvantages of paging? How to solve?

Although paging is very flexible, it needs to do many calculations and access memory many times. If each virtual address has to repeat the above operation, the processor will be overburdened and time-consuming. How to solve the problem? The locality principle is used to establish a cache for address translation, TLB, commonly known as fast table. With TLB, the processor will use the high 20 bits of the virtual address to find the corresponding entry in the TLB before addressing. If it is hit, it will return the physical page address mapped by the virtual address. Otherwise, it will query the page table, find the corresponding physical page address, and then update the TLB.

Thank you for your reading. the above is the content of "the methods and steps for the establishment of the paging mechanism". After the study of this article, I believe you have a deeper understanding of the methods and steps for the establishment of the paging mechanism. the specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.