CN101008922A - Segmentation and paging data storage space management method facing heterogeneous polynuclear system - Google Patents

Abstract

The invention discloses a segment page storage space management method for a heterogeneous multi-core system. This method implements segmented page storage space management for heterogeneous multi-core systems by first segmenting and then paging within the segment. Segments are segmented according to the logical meaning of the program, and then divided into equal-sized pages within each segment. , so that not only the logical meaning of the segment is preserved, but also the page can be used as the smallest unit of storage scheduling, which avoids the generation of storage space fragmentation and saves storage space resources. In addition, the access page data page fault handling method enables the application program to run on a sufficiently large virtual space, which not only ensures that each segment has a complete logical meaning, but also minimizes the generation of memory fragmentation. This method can be used on heterogeneous multi-core systems.

Description

Segment page storage space management method for heterogeneous multi-core system

technical field

The invention relates to the field of computer operating systems, in particular to a segment page storage space management method for a heterogeneous multi-core system.

Background technique

Storage space management is an important part of the operating system, which is responsible for managing the memory of the computer system. Memory can be divided into two categories: main memory (referred to as main memory) and auxiliary memory (referred to as auxiliary memory).

The storage space of the main memory is generally divided into two parts: one part is the system area, which stores the operating system and some standard subroutines, routine programs, etc.; the other part is the user area, which stores user programs and data. Storage management is mainly to manage the user area in the main memory.

After the computer system adopts multi-programming technology, it often needs to store programs of multiple jobs in the main memory at the same time, and the positions of these programs in the main memory cannot be known in advance, so users cannot use absolute addresses when writing programs. The address indicated by the address part in the instructions of a modern computer is usually an address, and logical addresses can be numbered starting from 0. Users write programs in terms of logical addresses. When loading a program into a computer, first, the operating system must allocate a suitable main memory space for it. Since the logical address is often inconsistent with the absolute address of the allocated main memory space, and the processor executes instructions according to the absolute address, it is necessary to convert the logical address into an absolute address to obtain the real storage place of the information. The work of converting a logical address into an absolute address is called address translation.

When multiple jobs share the main memory, the programs and data in the main memory must be protected and allocated reasonably and effectively in order to fully utilize the efficiency of the main memory.

In order to make it easier for the user to program, so that the user is not limited by the actual capacity of the main memory when writing the program, a certain technology can be used to "expand" the main memory capacity, and a main memory space larger than the actual capacity can be used.

In summary, the goal of storage management is to make it as user-friendly and as efficient as possible for main storage. Specifically, storage management has the following four functions.

1) Allocation and allocation of main memory space

When a job is to be loaded into the main memory, an application must be made to the operating system in a prescribed manner, and the storage management will carry out specific allocation. Storage management Set up a table to record the allocation of storage space, analyze the usage of storage space according to certain strategies according to the requirements of the application, and find out enough free space. The state of the resource, until there is enough main memory space to allocate to him.

When a job in the main memory evacuates or actively returns the main memory resources, the storage management needs to reclaim all or part of the storage space it occupies, making them free areas (also called free areas), and at this time, the relevant items in the table should also be modified . The work of reclaiming the storage area is also called "deallocation".

2) Sharing of main memory space

Sharing of main memory space In order to improve the interest rate efficiency of main memory space, the so-called sharing of main memory space has two meanings:

• Shared main memory resources. Using multi-programming technology, several programs enter the main memory at the same time, each occupying a certain amount of storage space, and sharing a main memory.

• Some areas of main memory are shared. When several jobs have common program segments or data, these common program segments or data can be stored in a certain storage area, and each job can access them when executing.

3) Storage Protection

There are not only system programs but also programs for several user jobs in the main memory. In order to prevent several programs in the main memory from interfering with each other, the programs and data in the main memory must be protected. Usually, the protection function is provided by the hardware and realized by the cooperation of the software. When a certain unit of the main memory is to be accessed, the hardware checks whether the access is allowed, and if it is allowed, it is executed, otherwise an interrupt is generated, and the operating system performs corresponding processing.

The most basic protection measure is to stipulate that each program can only access those areas that belong to it or access the information in the public area, but the public access should be restricted. Generally speaking, there may be the following three situations when a program is executed:

●It is both readable and writable for the current year in its own main storage area;

●The information that is allowed to be shared in the public area or the information of other users that can be used is readable and not allowed to be modified;

●Unauthorized use of information is neither readable nor writable.

4) Expansion of main memory space

With the support of computer hardware and the cooperation of software and hardware, auxiliary storage such as disks can be used as an extended part of the main storage. When a large-scale program needs to be loaded into the main memory, a part of it can be loaded into the main memory first, and the rest can be stored on the disk. If the program needs to use information that is not in the main memory, the operating system will use the overwriting technique. Transfer it into the main memory, so that the user also needs to consider the capacity of the actual main memory space when programming, just as he can use a sufficient main memory. The expansion of this main memory space greatly facilitates the users, so that they can be exempted from considering complicated coverage issues when compiling programs.

With the rapid development of computer technology, more and more self-defined computer architectures emerge in the embedded field, which prompts specific requirements for memory space management of operating systems of such computer architectures.

The traditional storage space management method adopts a continuous space allocation management method, which has the advantages of simple implementation and clear management. However, this management method is prone to problems such as memory space fragmentation during use, especially for embedded systems, memory and other storage devices have limited space, so how to effectively use these limited spaces is very important.

Contents of the invention

The object of the present invention is to provide a method for managing segmented page storage space facing heterogeneous multi-core systems.

The technical scheme that the present invention solves its technical problem adopts is as follows:

1) Segmentation method

I. The operating system of the heterogeneous multi-core system allocates a continuous storage space for each segment that needs to be placed in the main memory in the user operation, and establishes a local descriptor table and a global descriptor table;

II. A segment descriptor consists of 8 bytes, including segment base address, length and custom information;

2) Pagination method within a segment

I. Divide the storage space in the segment into pages of equal size, and establish a page table to realize page access;

II. Put part of the page table into a high-speed memory to form a fast table. When the program accesses data, it will first access the fast table. Only when the access to the fast table does not hit, it will access the main memory, which can improve the access speed ;

3) Access method of storage space

I. Logical address includes selector and offset;

II. Find the corresponding descriptor in the descriptor table through the selector in the logical address. The descriptor contains the segment base address, length and custom information, where the base address and the offset in the logical address together form a linear address;

III. Linear address includes page directory number, page table number and page offset;

IV. First use the page directory number in the linear address to search the page table in the page directory, then search the page through the page table number in the page table, and finally obtain the physical address through the offset in the page to realize real page data access;

When a page fault occurs in the access page data access, the processing method is as follows:

I. When a page fault interrupt occurs when the page access in the main memory is missing, the page needs to be swapped out and a new page is transferred through paging;

II. Paging adopts the clock paging method, and finds the least recently accessed page by cyclically detecting the access bits to be swapped out.

Compared with the background technology, the present invention has the beneficial effects that:

In terms of paging implementation, the clock paging method is adopted, and the access bit is cyclically detected to find the least recently accessed page for swapping out. This enables higher performance and lower page fault rates. This general method can deal with the problem of storage space allocation relatively simply.

At the same time, in the segmented page storage structure adopted, segments are first divided according to the logical meaning of the program, and then each segment is divided into pages of equal size, which not only retains the logical meaning of the segment, but also uses pages as storage scheduling The smallest unit, avoiding the generation of storage space fragmentation. Saves storage space resources.

Description of drawings

Figure 1 is a schematic diagram of the page addressing mode of the middle segment of the main memory.

Figure 2 is the structure of the segment selector.

Figure 3 is a circular queue constructed by clock scheduling.

Figure 4 is the implementation process of clock scheduling.

Detailed ways

1) Segmentation method

I. The operating system allocates a continuous storage space for each piece of code, data, etc. that needs to be placed in the main memory in the user's job, called a segment. According to the different purposes of the segment, it can be divided into: data segment, stack segment, code segment, extended data segment and so on. And establish local descriptor table LDT and global descriptor table GDT. The local descriptor LDT table describes the segments local to each program, including code, data, stack, etc.; the global descriptor table GDT describes the system segments, including the operating system itself.

II. A segment descriptor consists of 8 bytes, including segment base address, length and other information, as shown in Figure 1. in:

●The base address has a total of 32 bits, which are combined in three places to generate the first address of the memory segment, and the 32-bit offset is added to form the memory address.

●The length bits are 20 bits in total, which limit the length of the memory segment addressed by the segment descriptor, and the measurement unit can be byte or page.

• The G bit is used to describe the grain size, which is the unit of measure for segment length. G=0 means that the length is in bytes; G=1 means that the length is in pages.

● D bit: when D=1, it is a 32-bit segment; when D=0, it is a 16-bit segment.

● The P bit indicates whether the memory segment is in the physical main memory, if P=1, it means the segment is in the memory, if P=0, it means the segment is not in the memory.

● The DPL bit represents the privilege level and is used for protection. 0 is the kernel level; 1 is the system call level, 2 is the shared library level, and 3 is the user program level.

●The S bit is the segment, when S=1, it means the current segment is an application program; when S=0, it means the description

specifier will refer to system information outside the memory segment.

●The type field indicates the type of memory segment, such as executable code segment, read-only data segment, call gate, and so on.

●A bit is the access bit, indicating whether the memory segment has been accessed.

2) Pagination method within a segment

I. The operating system divides the storage space in the segment into pages of equal size. And establish a page table, which stores page number, resident flag, block number, auxiliary storage address, and call-out flag in the page table. The function is as follows: the resident flag is used to indicate whether the corresponding page has been loaded into the main memory. If the resident flag is 0, it indicates that the page has not been loaded into the main memory. At this time, the address of the page in the auxiliary memory can be known according to the auxiliary memory address. address. Call-out flags can include modified bits, referenced bits, cache-disabled bits, and accessed bits to track page usage. When a page is modified, the hardware automatically sets the modification bit. Once the modification bit is set, the page must be written back to auxiliary storage when it is called out of main memory. The reference bit is set when the page is referenced, whether by write or write, and its value is used to help the operating system with page eviction. The disable cache bit can prevent the page from being cached, which is very important for pages that are exchanging data with peripherals. The access bits define what kind of access the page is allowed to read, write and execute.

II. Put part of the page table into a dedicated high-speed memory to form a fast table. The access speed of this memory is much faster than the access speed of main memory. When a program accesses data, it first accesses the fast table, if it is hit, it reads it directly, and if it is missing, it accesses the main memory. The commonly used data pages are placed in the page table to ensure a high hit rate, which can improve the access speed. For example, the time to access the main memory is 200 nanoseconds, the time to access the fast table is 40 nanoseconds, and the hit rate of the fast table can reach 90%, so the average time for accessing by logical address is:

(200+40)×90%+(200+200)×10%=256 nanoseconds

36% less than 200 ns x 2 = 400 ns for two accesses to main memory

3) Storage access method

as shown in picture 2:

I. The logical address includes selector and offset. The selector is 16 bits, the highest 13 bits are the index, the lowest bit 0 and the first bit are protection bits, and the second bit is used to determine the global descriptor table GDT Or Local Descriptor Table LDT. The offset is 32 bits.

II. First judge whether it is a global descriptor table or a local descriptor table through the second bit, then clear the lowest 3 bits of the selector to 0, and add it to the start address of the descriptor table to obtain a pointer directly to the segment descriptor , use this pointer to find out the segment descriptor.

The address is first checked for validity by comparing the offset to the segment length. If it is invalid, an exception will be generated. If it is valid, the base address will be taken out and added to the offset in the logical address to form a linear address.

III. A 32-bit linear address includes a 10-bit directory number, a 10-bit page table number, and a 12-bit in-page offset.

IV. First obtain the base address of the page directory from the page directory base address register, then use the directory number in the linear address to search the page table in the page directory to obtain the base address of the page table, and then use the page table number in the page table to Find the page, get the base address of the page, and finally get the physical address through the base address of the page plus the offset in the page to realize real data access;

4) How to deal with missing pages

I. In virtual storage, only a part of the pages are transferred into the main memory, and other pages are placed in the auxiliary memory. When a page fault interrupt occurs when the page access in the main memory is missing, the page needs to be transferred from the auxiliary memory. Then transfer to a new page;

II. The paging method adopts the clock paging method. First, an access flag is set on each page. When the page is transferred into main memory, this bit is set to 0, and if it has been accessed, this bit is set to 1. All the pages in the main memory form a circular queue, and a pointer points to a certain page, as shown in Figure 3. When a page needs to be swapped out, first check the page pointed by the pointer, if the flag bit is 0, swap it out, insert a new page into this position, and then move the pointer forward by one position; otherwise, if the flag bit is 1, Then clear it to 0, move the pointer forward by one position, and continue to repeat the above process until a page whose access bit is 0 is found and swapped out. In this way, the approximate least recently accessed page can be swapped out, as shown in Figure 4 for the process.

Claims (2)

1. A segmented page storage space management method for a heterogeneous multi-core system, characterized in that: 1) Segmentation method I. The operating system of the heterogeneous multi-core system allocates a continuous storage space for each segment that needs to be placed in the main memory in the user operation, and establishes a local descriptor table and a global descriptor table; II. A segment descriptor consists of 8 bytes, including segment base address, length and custom information; 2) Pagination method within a segment I. Divide the storage space in the segment into pages of equal size, and establish a page table to realize page access; II. Put part of the page table into a high-speed memory to form a fast table. When the program accesses data, it will first access the fast table. Only when the access to the fast table does not hit, it will access the main memory, which can improve the access speed ; 3) Access method of storage space I. Logical address includes selector and offset; II. Find the corresponding descriptor in the descriptor table through the selector in the logical address. The descriptor contains the segment base address, length and custom information, where the base address and the offset in the logical address together form a linear address; III. Linear address includes page directory number, page table number and page offset; IV. First use the page directory number in the linear address to search the page table in the page directory, then search the page through the page table number in the page table, and finally obtain the physical address through the offset in the page to realize real page data access; 2. A method for managing segmented page storage space oriented to a heterogeneous multi-core system according to claim 1, characterized in that the processing method when a page fault occurs when accessing page data is accessed is as follows: I. When a page fault interrupt occurs when the page access in the main memory is missing, the page needs to be swapped out and a new page is transferred through paging; II. Paging adopts the clock paging method, and finds the least recently accessed page by cyclically detecting the access bits to be swapped out.

Images