What is the basic paging storage management method?

Recommended tutorial: FAQ

Introduction

In memory management, the continuous allocation method will form many "fragments". Although many fragments can be spliced ​​into a usable large space through the "compact" method, it must be Pay a lot of expense.

If a process is allowed to be loaded directly into many non-adjacent partitions, there is no need to "compact". Based on this idea, the discrete allocation method was produced. If the basic unit of discrete allocation is a page, it is called the paging storage management method . In the paging storage management mode, if it does not have the page swap function, it is called the basic paging storage management mode, or it is called the pure paging storage management mode. It does not have the function of supporting the implementation of virtual memory. It Each job is required to be loaded into memory before it can be run.

Why page storage is needed

During the memory allocation process, the continuous allocation method is prone to produce a large number of fragments, although it can be "compacted" Organize it, but that requires a lot of overhead.

Therefore, if the continuous logical memory can be dispersed and allocated to multiple non-connected physical memories during the memory allocation of the process, then the large pieces of fragments that were originally wasted will be utilized. Reduce the maximum size of unavailable fragments (to the size of the page, because if the size of the fragment exceeds the size of the page, it will be exploitable) and improve memory utilization. Based on this idea, the discrete allocation method is produced. If the basic unit of discrete allocation is a page, it is called a paging storage management method; if it does not have the page swap function, it is a basic paging storage management method.

Basic concept

Page

The paging storage management method combines the continuous logical addresses of the process The space is divided into several equal-sized address slices, called pages or pages. And number them, such as page 0, page 1. Logically, the addresses in these pages are contiguous, but their corresponding physical block addresses may be discontinuous. The corresponding physical blocks are also named block 0, block 1, etc. accordingly. When a process allocates memory, several pages of the process are loaded into corresponding physical blocks respectively. Since the last page is often not full, intra-page fragmentation is formed that cannot be utilized

Using paging storage management The purpose is to make more use of memory fragmentation. Therefore, the page size is relatively smaller than the address space size required by a normal process. So what is the appropriate size of the page? If the page is too small, although it can reduce the maximum size of unavailable fragments in the memory and improve the utilization of memory space, it will also cause the process to occupy too many pages, making the page table too long and reducing the efficiency of page swapping in and out. efficiency. Similarly, if the page is too large, although it improves the efficiency of page swapping in and out, it will also increase memory fragmentation. Therefore, according to experience, the best page size is about 512B~8KB.

Page table

The page table is an address space maintained in the process, which stores the mapping relationship between pages and physical blocks. Before discussing the page table, first understand Clear the address structure in paging.

For the physical address space, the total memory address space is fixed. For a process, the allocated logical memory space is also fixed and continuous. The logical address space starts from 0. Assume that the logical address of a byte in a process is 1088B, and the page size is 512B. As mentioned when introducing the page, although the logical address space is divided into several pages, the logical addresses of these pages are still continuous. Then we can know the page number P = 2 (starting from 0) to which the byte belongs, and the page address d = (1088 - 512 * 2) = 64.

That is to say, when the page length is known, the page number to which the address space belongs and the relative address in the page can be simply known based on the logical address. Based on these two parameters and the page table, the physical address corresponding to the address can be known.

The page table is a table used to map pages and physical blocks, as shown below:

Through the page table and page number, we know the physical block number, and we also know the starting address of the corresponding physical block space. Coupled with the in-page address, the corresponding physical address is known. In this way, we are able to achieve conversion from logical address to physical address.

Address translation

The above basic concept introduction briefly introduces the principle of address translation. Let’s look at the specific process in detail.

As mentioned above, the mapping from page number to physical block number is found by searching the page table. So where is the page table stored and how to find the page table? ?

The page table can be implemented through a set of registers. Each register stores a page table entry. Because the access speed of the register is fast, it can increase the speed of page table address translation. However, the register cost is high, and the page table entries in the page table may be very large, reaching hundreds or thousands of entries. Therefore, page tables are usually stored in memory. In the system, only one page table register PTR is set to store the starting address and length of the page table in memory. Normally, when the process is not executed, the starting address and page table length are stored in the PCB of this process. When the scheduler schedules a process, these two data are loaded into the page table register. Therefore, in a single-processor environment, although multiple processes can run in the system, only one page table register is needed (that is, when multiple processes are running at the same time, the page table data in multiple processes needs to be stored separately) .

When a process wants to access data in a certain logical address, the paging address conversion mechanism will automatically divide the effective address (relative address) into two parts: page number and intra-page address, and then use the page number as an index to Retrieve page table. Before performing the retrieval, compare the page number with the page table length. If the page number is greater than or equal to the page table length, it means that the address accessed this time has exceeded the address space of the process. Then, this error will be detected by the system and an address out-of-bounds interrupt will be generated. If no out-of-bounds error occurs, add the starting address of the page table to the product of the page number and the length of the page table entry to obtain the position of the entry in the page table, and then obtain the physical block number of the page from it. Load into the physical address register. At the same time, the page address in the effective address register is sent to the block address field of the physical address register. This completes the conversion from logical address to physical address. The following figure shows the address translation mechanism of the paging system

fast table

Since the page table is stored in memory rather than in a register , so each time you read an address, you need to access the memory twice. The first time you access the page table to find the physical block number, and the second time you access the real physical address to get the data. Therefore, adopting this approach will reduce the processing speed of the computer by nearly 1/2.

In order to improve the efficiency of address translation, a set of special cache registers with parallel search capabilities are added to the address translation mechanism, also known as "Associative Memory" (Associative Memory), or "Fast Table" , used to store the currently accessed page table entry data (similar to cache, storing previously searched page table entries, improving the conversion efficiency from page number to physical block number). In this way, the address translation process becomes as shown below:

After the CPU obtains the logical address, the address translation mechanism hands the page number to the fast table to query the corresponding If the physical block number is found, the physical address will be found directly according to the address in the page to access the data. If not, the physical block number will be searched in the normal way and saved in the fast table at the same time. If the fast table is full, the system will automatically remove a page table entry and replace it.

In short, the fast table is equivalent to the page table entry cache.

The above is the detailed content of What is the basic paging storage management method?. For more information, please follow other related articles on the PHP Chinese website!