JP3557026B2 - Virtual memory management method - Google Patents

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a virtual storage management method, and more particularly, to a virtual storage management method for performing virtual storage management by paging using a single virtual storage space shared by all processes executed on a computer system.
[0002]
[Prior art]
In recent years, with the improvement of the computer architecture, the increase in the capacity of storage devices, and the drastic expansion of the available virtual storage space due to the 64-bit processor, etc., multiple programs and data are stored on a single virtual storage space. A method of centrally managing these by arranging them has been regarded as effective. This is because, by making all processes share the same virtual storage space, objects such as programs and data placed on the virtual storage are uniquely associated with virtual addresses on the virtual storage, and these objects are associated with each other. It is to define / manage in a unified manner.
[0003]
A specific advantage is that the correspondence between the virtual address and the physical address is the same for all processes on a certain computer, so that the same object can be referenced from any process by a specific virtual address. In addition to guaranteeing the equivalence of objects, there are cited persistence of objects, direct inter-process communication across a plurality of program areas arranged in space, and easy data sharing.
[0004]
When providing such a single virtual storage mechanism with basic software such as an OS, there are some points which are problematic.
[0005]
One of the problems is how to realize protection of each area arranged in a single virtual storage space. The single virtual space itself presents the addressability of the entire space to all the spawned processes, but when used in a multi-user environment etc., the individual virtual space that is actually located in the space It is necessary to be able to specify / set access protection for each user or each process for an area. This is to protect the area from careless reference, area destruction due to erroneous operation, malicious operation, and the like. This protection function is essentially essential for the OS.
[0006]
Setting the access protection attribute for the process for each area means that the range of the accessible area is defined for each process.
[0007]
Therefore, the range of the accessible area for each process is referred to as an “access protection area”, and a method for realizing this protection function will be considered below. Here, a virtual storage management mechanism that performs virtual / physical address conversion using an address conversion table (this indicates a page table, a TLB (Translation Lookaside Buffer), etc.) currently used in many architectures is provided. Consider a case where the above-described protection function is realized on a computer.
[0008]
[Problems to be solved by the invention]
(1) First, consider that a single address conversion table is shared by all processes to realize an access protection area for each process. In this case, at the time of a page fault, the protection check by the paging function can be applied in accordance with the protection relationship between the page where the page fault has occurred and the process. However, since this protection check is performed only at the time of a page fault, if another process without access permission tries to access the page once accessed by one process, it will correspond to the reference page in the address translation table. If the address translation table entry to be executed is valid, no page fault occurs, so that this illegal access cannot be detected by software or hardware. This is shown in FIG.
[0009]
FIG. 25 shows a case where processes 1 and 2 share the same page table and a page corresponding to area A accessible only by process 1 exists on a physical page frame (physical memory). A state is shown in which the unauthorized access to the page is performed by the process 2 having no right.
[0010]
As described above, when the combination of protection attributes such as read, write, and execute for the same page differs between processes, the same address conversion table cannot be shared.
[0011]
That is, if processes having different ranges / attributes of the access protection area share the address conversion table, consistency in area protection cannot be guaranteed.
[0012]
(2) Then, it is considered that a separate address conversion table is held for each process. In this method, as shown in FIG. 26, the range of the area that can be accessed for each process is managed independently by each address conversion table, so that the process 2 that does not have access right Is prohibited from accessing the page in the area A, and safe space use is enabled. Since a process holds a separate address translation table, every time the process is switched, the address translation table must be switched (including the TLB flash when the TLB is installed).
[0013]
In this method, when the same page is shared by a plurality of processes, the address translation table entry state associated with each process corresponding to the simultaneously referenced page becomes valid at some point (however, the page can be referenced). Even if it is a process, if the page is not referred to, the state of the address translation table entry may remain invalid.)
[0014]
Thereafter, when a process needs a new page and there are no unused pages in the physical memory, a page-out is performed. When a shared page currently being referred to by a plurality of processes is selected as a page to be paged out, in order to guarantee the consistency of the table, an address translation table entry for each process currently referred to for the page is checked. It becomes necessary to invalidate all states, and the invalidation notification cost for this increases with the number of reference processes.
[0015]
Further, since each process holds a page table, even when using an architecture adopting a multi-staged page table, the physical memory and the 2nd memory wasted due to such storage management resources. The amount of the storage area for the secondary storage increases in proportion to the number of processes. As a result, the cache hit rate decreases, and the overhead such as the page table switching and TLB flush at the time of process switching affects system efficiency. Will come.
[0016]
As described above, in the case of the method (1) in which a single address translation table is shared by all processes, the consumption of storage resources is small and the consistency of the address translation information can be easily maintained. Because access protection is not possible, the system is always at risk and cannot be used safely. On the other hand, the method (2) using the address translation table separately for each process has a problem that memory resources are wasted.
[0017]
(3) As means for solving such a problem, an address conversion table is shared only between processes having the same access protection area, and the storage management resource is maintained while maintaining the access protection function for each process. It is possible to optimize.
[0018]
However, in order for the access protection area to completely match between the processes, the access protection area must be fixedly defined in the plurality of processes to be grouped. It is difficult to realize a flexible protection function that dynamically adds or changes an accessible protection area only for a certain one of the processes.
[0019]
On the other hand, it is generally considered that the information of the access protection area set by the system when the process is generated is a subset of the area that can be used by the generation process and does not include all the information that can be used in the space. This is because there may be many areas in the vast virtual storage space that can be referenced by any process, and these are extracted one by one and reflected as access protection area information attached to the creation process. It is not practical to maintain this. Therefore, a change such as addition or deletion of the access protection area accompanying the process can be performed by giving an instruction from the program or accessing another area other than the area held as the current access protection area information. It is considered natural that the method is dynamically performed when a fault occurs, the access permission is checked, and the access is permitted. Under such circumstances, it is difficult to guarantee perfect matching of the access protection areas in a strict sense.
[0020]
As described above, the matters that are problematic when realizing the function of setting the range of the accessible area flexibly for each process using the single virtual storage space have been described. However, there are several examples of optimization of a process running in a certain address space by reducing the weight of the process by sharing an address translation table and minimizing the practical context. However, these are generally applied to the entire virtual storage space, such as the multiple virtual storage system, because the entire virtual storage space completely matches the protection area, and is limited only to the virtual storage space having an applicable range. This method does not provide a solution regarding an optimization method of an access protection function that functions efficiently in a situation where the range of a plurality of areas arranged in a single virtual storage space can be dynamically changed.
[0021]
Next, a problem in scheduling a process capable of setting each accessible area range on a single virtual storage space will be described. Normally, in an architecture using a multiple virtual storage space, when processes are accommodated in an execution queue and dispatched in order, it is necessary to switch a page table or TLB flush every time a process is switched. However, in an architecture that uses a single virtual storage space where the page table can be shared among multiple processes, the scheduler selects the process to be selected as the next execution process as the one that shares the page table with the current execution process. If it can be determined, the above operation is essentially unnecessary at the time of dispatch. However, in the conventional scheduling method, the shared information on the address translation table is not used for scheduling at all. Therefore, if a general scheduling method is applied to an architecture using a single virtual memory space, a page is always generated every time a process is switched. Table switching or TLB flush is performed.
[0022]
Next, a description will be given of a problem in a case where a process capable of setting each accessible area range on a single virtual storage space is assigned to a processor in a distributed memory type (loosely-coupled) multiprocessor system environment.
[0023]
Under the multiprocessor system environment, each CPU has a configuration in which an MMU and a local memory are attached. However, since each CPU does not allow another CPU to access its own local memory, it shares an address conversion table. When two processes are assigned to different CPUs, one process creates a copy of the address translation table on the local memory of the corresponding CPU and newly uses this. In this case, the advantage that the address translation table can be shared is lost, and the contents of the cache are also switched. Therefore, every time the processor is moved, it is necessary to recache and take in the data.
[0024]
Such a conventional technique considering the affinity of the cache on each processor includes, for example, cache affinity scheduling for controlling a process (thread) to be executed on the same processor as much as possible [Reference: R. Vaswani and J.M. Zahorjan. "The implementations of cache affinity on processor scheduling for multiprogrammed, shared memory multiprocessors. In Proceedings of Osm. 26-40, 1991. ] Exists. However, the above-mentioned scheduling method is intended only to improve the cache effect by controlling the processor allocation so that one process (thread) is executed on the same processor as much as possible. No consideration is given to the affinity with the sharable processes.
[0025]
The present invention has been made in consideration of the above problems, and in a system in which a single virtual storage space is shared by all processes, an address translation table between processes is ensured while guaranteeing access protection for each process. The object of the present invention is to provide a virtual storage management method capable of sufficiently increasing the sharability of a virtual machine, and realizing a highly reliable storage management resource and minimizing the cost at the time of process switching. I do.
[0026]
[Means for Solving the Problems]
The present invention provides a virtual storage management method for performing virtual storage management by paging using a single virtual storage space shared by a plurality of processes executed on a computer system. For each of the plurality of areas to be obtained, an area accessible for each process and an attribute of access protection for the area are defined, and a page currently read in the physical memory belongs to an accessible area of a certain process. A process is detected in which the accessible area is accessible and the access protection attribute for the area is the same as the above process, and an address translation table for translating a virtual address to a physical address is shared between the processes. It is characterized by the following.
[0027]
In this virtual storage management method, attention is paid to an accessible area to which a page currently read in a physical memory belongs within an accessible area of a certain process, the accessible area is accessible, and access protection is performed. If there is another process having the same attribute, the address translation table is shared between the processes. Therefore, even if the accessible areas and the access protection attributes do not all match, if the access protection attributes match only for the area corresponding to the page currently read in the physical memory, the address translation table is shared. As a result, it is possible to sufficiently increase the possibility of sharing the address translation table between the processes while guaranteeing the access protection function of each process, thereby achieving high reliability, storage management resources, and process switching. Cost can be minimized.
[0028]
Further, when a page belonging to a new area in which consistency of access protection cannot be guaranteed between processes sharing the address translation table is read into the physical memory due to the occurrence of a page fault, the sharing of the address translation table is performed. It is preferable to release. As a result, consistency of area protection can be guaranteed.
[0033]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[0034]
1 to 3 show configuration examples of a computer architecture to which a virtual storage management method according to an embodiment of the present invention is applied. The computer architecture of FIG. 1 is a uniprocessor computer, has one CPU 11 and physical memory 13, and is equipped with a mechanism for realizing virtual storage such as an MMU 12 (Memory Management Unit). This computer has basic software such as an OS, and under the control of the computer, control for virtual storage management is performed. The secondary storage device 14 is used as a swap backing storage.
[0035]
FIG. 2 shows a distributed memory type (loosely coupled type) multiprocessor system including a plurality of processors, each of which has one CPU 11 and physical memory 13 and a virtual memory such as an MMU 12 (Memory Management Unit). Equipped with a mechanism for realizing memory. The secondary storage device 14 is shared between processors as a swap backing storage.
[0036]
FIG. 3 is another configuration example of a distributed memory type (loosely coupled type) multiprocessor system including a plurality of processors. A distributed computer system in which a plurality of processors are coupled via a network such as a LAN or a WAN is illustrated. Is illustrated. The secondary storage device 14 of each processor is usually used as a swap backing storage. However, if the secondary storage resources on other computers can be used as the swap area in a network environment, the secondary storage device 14 is not necessarily used for each processor. There is no need to provide a separate secondary storage.
[0037]
FIG. 4 illustrates an example of a relationship between an execution process on the computer and data. By the process management mechanism and the virtual storage management mechanism of the OS provided in the computer environment, various areas such as all programs and data (hereinafter referred to as “memory section areas”) are illustrated on a single virtual storage space illustrated. Is realized, and a single virtual storage space can be shared from all running processes. That is, when data reference is made from a process to a specific virtual address, the same byte string is seen for all running processes. Further, since the same virtual storage space is shared by all the processes, a data change on a specific virtual address is immediately reflected on other processes other than the process that made the change.
[0038]
In FIG. 4, a process 1 running on a program A located in a memory section area A changes data in a memory section area B, and transfers the changed data to a program located in a memory section area C. A state in which the process 2 running on B is referring to is shown.
[0039]
FIG. 5 shows an example of the relationship between each process to be managed by the inter-process virtual storage and the access protection area range. A plurality of processes executed on a single virtual storage space are provided with an access protection mechanism capable of setting / changing a memory section area range that can be independently accessed. That is, each process is readable, writable, executable, etc. for each memory section area arranged on a single virtual storage space (hereinafter, these operations are collectively referred to as access or reference). By designating the access protection attribute, the range of accessible / inaccessible areas can be set freely for each process unit. The access protection mechanism enables the memory section area to be protected from intentional / inadvertent access from an unauthorized process.
[0040]
In FIG. 5, memory section areas A, B, and D are assigned as access protected areas for process 1, memory section areas D and E are assigned as access protected areas for process 2, and memory section areas C, D, and E are assigned. It is assigned as an access protection area for process 3.
[0041]
FIG. 6 shows a configuration example of an OS for realizing the inter-process virtual storage management mechanism of the present invention.
[0042]
As shown, the inter-process virtual storage management mechanism includes a process management unit 21 and a virtual storage management unit 22. The virtual storage management unit 22 includes a page table management unit 23, a memory section management unit 24, and a protection unit. It comprises an area management unit 25. The paging method exemplified here is intended for an architecture that employs a page table for a virtual / physical address conversion table. However, a cache memory dedicated to a page table entry such as a TLB (Translation Lookaside Buffer) not shown is used. May be installed.
[0043]
The process management unit 21 is responsible for generating processes that can be executed on the computer and scheduling a plurality of processes. The process management unit 21 includes a process generation unit 211, a process information saving unit 212, a process scheduling unit 213, and a process dispatching unit. 214, a process information setting unit 215, a process information acquisition unit 216, and the like, and hold information such as process information and a process execution queue.
[0044]
The page table management unit 23 is responsible for generating a page table associated with each process, setting a page table entry, and the like. The page table generation unit 231, the page table entry setting unit 232, and the page table entry information acquisition unit 233. , Etc.
[0045]
The memory section area management unit 24 determines whether to allocate an area (memory section area), such as a program or data, which can be arranged on a single virtual storage space, or to set or access a protection attribute related to a process / memory section area. It is a part in charge of obtaining protection attribute information necessary for the determination, and includes a memory section generation unit 241, a memory section protection attribute setting unit 242, a memory section area information acquisition unit 243, and the like.
[0046]
The protection area management unit 25 is in charge of determination / execution for sharing / separating a page table between processes based on access protection area information (described later) and active protection area information (described later) set for each process. In parts, access protection area setting section 251, access protection area information acquisition section 252, active protection area setting section 253, active protection area information acquisition section 254, page table sharing determination section / execution section 255, page table separation determination section / execution It comprises a unit 256 and the like.
[0047]
The respective management units are related to each other, and the respective components cooperate to perform processing necessary for realizing the inter-process virtual storage control mechanism.
[0048]
Next, a method of setting the protection attribute of the memory section area in the process (for the process) will be described.
[0049]
The memory section area is set for each process according to instructions of various programs. The OS holds a list of access permission attributes for each memory section area as “access protected area” information, and is managed by the access protected area management unit 25. The range of the access protection area set for a certain process does not necessarily need to cover the information for all the areas arranged in a single virtual storage space, and may be fixed in advance by a programmer or a system. An area range is sufficient. This is because the access right is dynamically checked when accessing a potentially accessible / inaccessible area. FIG. 7 shows an example of the process structure.
[0050]
In the process structure, in addition to the priority, process attribute, register save information, jump destination in exception processing, etc., a page table head address (here, distinguished from register save information), access protection area list management A structure and an active protection area list management structure (described later) are recorded. The access / active protection area list management structure is a group of pointers that specify the information storage position of the access / active protection area of the corresponding process. Here, the access protection area indicates all memory sections accessible by the process. The active protection area indicates a memory section area to which a page currently read into the physical memory belongs in the access protection area.
[0051]
As shown in FIG. 8, the access protection area list management structure is composed of the first entry and the last entry of the memory section area structure linked in ascending order of the virtual address where the memory section area is located. Is done. Further, as shown in the figure, a hint for recording the position of the memory section area structure entry last referred to may be included. Similarly to the access protection area list management structure, the active protection area list management structure also includes the first entry of the active memory section area structure linked in ascending order of the virtual address where the memory section area is located. And the end entry, and a hint for recording the location of the last referenced memory section area structure entry.
[0052]
As shown in FIG. 9, each memory section area structure holds a forward / backward link, a memory section ID, and the like, and may include a protection attribute used as a cache of an access right to the memory section area. Good.
[0053]
Further, the access protection area information can be set not only for the process but also for each memory section area. This can be usually specified / set when the area is arranged in the virtual storage space. If necessary, the access permission / non-permission attribute can be dynamically changed after the arrangement. .
[0054]
In this case, the memory section area management data structure can be realized by a bidirectional list similar to that shown in FIG. As shown in FIG. 10, each memory section area structure entry includes a head / end virtual address of the memory section area, a forward / backward link, a protection attribute flag, a pair area permission / non-permission list, a pair Process permission / non-permission list.
[0055]
As a result, in each memory section area, access permission / non-permission can be set independently for the memory section area in which the program is stored and for each process. The entry contents maintained for this purpose are shown in FIGS. 11 (a) and 11 (b). In addition to the memory section ID / process ID, protection attributes such as read / write / execution are recorded. In addition, using the protection attribute flag in the memory section area structure entry, settings are made so that access (read / write / execution, etc.) can be permitted / prohibited from all processes (memory section area). It is possible.
[0056]
Hereinafter, embodiments using each of these will be described.
[0057]
In the first embodiment, the possibility of sharing the page table is determined and the sharing control is performed between the processes based on the inclusion relationship between the active protection area information and the access protection area information accompanying each process.
[0058]
There are several ways to determine the sharability of the page table and when to actually share the page table. The process can be explicitly specified by the programmer or implicitly performed by the OS or other system. Is automatically searched and shared.
[0059]
Here, an example will be described in which the program specifies another process to be a page table sharing partner when the process is generated.
[0060]
FIG. 12 shows a state where the process 1 has already been generated and the areas (A), (B), and (C) are set / managed by the access protection area management unit as the access protection areas of the process 1. .
[0061]
Subsequently, it is assumed that the execution of the process 1 is started, several pages in the area (A) and the area (C) are read on the physical frame, and the corresponding page table entry becomes valid. Here, the areas (A) and (C) including the page corresponding to the activated page table entry become the active protection area (FIG. 13).
[0062]
The active protection area is created one-to-one with respect to the page table, and is held by the active protection area management unit.
[0063]
Next, a case will be described in which, when a new process 2 is generated, the page table of the process 1 is requested to be shared.
[0064]
FIG. 14 shows that the access protection areas set in the process 2 at the time of mapping are areas (A), (C), and (D). FIG. 15 shows a table summarizing these situations.
[0065]
Here, a description will be given, with reference to FIG. 16, of a processing procedure in a case where the process 2 is requested to share the same page table as the process 1 when the process 2 is generated, and the process 2 is requested to share the same page table. .
[0066]
After allocating and initializing the process structure, the process generation unit calls up the page table management unit and requests permission determination regarding page table sharing (S1501). The page table management unit extracts the active protection area list of the process 1 requested to share the page table from the active protection area information acquisition unit (S1502), and further accesses the access protection area list of the process 2 that is the request source. It is extracted from the protection area information acquisition unit (S1503).
[0067]
Next, the page table management unit compares these two pieces of information with the page table sharing determination unit based on the determination criterion information that is the sharing condition specified by the system or the user (S1504). As a specific example of the criterion information, when the access protection area range includes the active protection area range (the protection attribute is assumed to be the same), sharing is considered. . For example, in a situation as shown in FIG. 15, if the process 2 can access the active protection areas A and C of the process 1 and the access protection attributes of the active protection areas A and C are the same in the processes 1 and 2. In this case, the sharing condition is satisfied. Even if the process 2 cannot access the active protection area C of the process 1 or if the access protection attribute related to the active protection area C is different, if the page corresponding to the active protection area C is invalidated, It is also possible to apply the above criterion for sharing the page table while guaranteeing the consistency of protection.
[0068]
When the page table sharing is permitted by the page table sharing determination unit, the page table management unit calls the page table sharing execution unit, and actually, the active protection area list of the requesting process (process 2) and the top of the page table. A process for sharing the address information with the request destination process (process 1) is performed (S1506).
[0069]
Finally, after ending the page table allocation, the page table management unit shifts the control to the process generation unit, finishes the preparation necessary for executing the process, and returns (S1509). FIG. 17 shows the sharing state (data structure) at this time.
[0070]
If the sharing is not permitted in step S1505, the requesting process needs to maintain its own page table. Therefore, a new page table is created, associated with the process, and a page table entry is set and required. Is performed (S1507). A new active protection area list is set for the requesting process (S1508).
[0071]
As described above, in the present embodiment, by introducing the active protection area and permitting the sharing of the page table while maintaining the consistency at the present time, the sharing conditions are relaxed, and the opportunity for sharing is realized. Is increasing.
[0072]
If the condition is not satisfied, sharing is not permitted, and another page table is created as described above, and this is used by the process 2 anew, or returns an error. When such sharing fails, the semantics such as system calls for requesting sharing of page tables and creating processes are shared as much as possible, but separate page tables are prepared if sharing is not possible. It depends on how to decide the policy, such as whether to create a process or not to create a process if it cannot be shared.
[0073]
In the inter-process virtual storage control mechanism, even for an area other than the area held in the access protection area information associated with the process, the process that attempts to refer to the area and the page table shared with the process are shared. As long as the access permission for the process is lowered, reference to the area is possible, and an entry corresponding to this area can be added to the active protection area information and the access protection area information of each process to ensure consistency. It is possible.
[0074]
Note that, here, a method of specifying a process that has already been created is used to specify the sharing target page table. However, a group is formed between processes requesting sharing, and sharing is performed by specifying this group identifier. Examples of the modification include a method of automatically finding a page table that can be shared by the system and a method of trying to share the page table for all processes to be generated.
Next, a second embodiment will be described.
[0075]
Overview of processing
The page table shared in the first embodiment can be continuously used as long as the page area range actually referenced from each process does not break the consistency of the access protection. However, in a case where access is permitted in a certain group of page table shared processes but access is not permitted in any of the other processes, access is permitted as it is and processing is performed. If continued, access protection of the area cannot be guaranteed.
[0076]
Therefore, when such an access occurs after sharing the page table, the sharing of the page table is canceled from the process that requests the access, and another page table is prepared and used by the process. Control provides a mechanism to ensure consistency of access protection.
[0077]
In addition to the method of separating a process from the page table sharing process group when a reference that does not maintain the consistency of access protection is actually performed (detected at the time of a page fault), there are several other methods. Can be.
[0078]
For example, besides this page fault, it is also conceivable to use the system according to a user's designation by a system call or the like, or according to each trigger.
[0079]
Here, first, a description will be given of a separation process in a case where the necessity of separation of a process from a page table sharing process group is determined at the time of a page fault. For example, as shown in FIG. 18, if a page fault occurs in process 1 by referring to an area E in which access is permitted in process 1 but is not permitted in process 2, process 1 is activated. Separated from page table sharing group.
[0080]
Hereinafter, a specific procedure of the separation process when a page fault occurs will be described with reference to FIG.
[0081]
When a page fault occurs (S1801), the active protection list management unit is called from within the page fault handler, and an active protection area list accompanying the page reference source process (executing process) is extracted (S1802). This corresponds to the acquisition of an active protection area list management structure, which is an attribute in the process structure of the running process. It is checked from the extracted list whether the fault destination virtual address is included in the area range held by the list (S1803). This is because, from the head entry of the list, the area range information (area start / end address) in the memory section area structure identified by the memory section ID destination which is the entry internal attribute is sequentially compared with the fault destination virtual address. It is done by doing. The entries for the active protection area list may be linked in ascending order of the virtual address, and the entry selected immediately before may be maintained as hint information, and search efficiency may be improved such that sequential inspection is performed thereafter. . When it is detected that the fault destination virtual address is included in the range in the active protection area list, the protection attribute (the one cached from the memory section area structure member) of the corresponding active protection area list entry and the reference The access right is checked from the operation (read, write, execute, etc.) (S1804). If it is determined in step S1805 that access is permitted, page table entry settings (virtual / physical address translation / protection attribute settings, page-in processing as necessary) are performed (S1817), and the process returns (S1819). ). If it is determined in S1805 that the access is not permitted, an error such as a protection exception is returned (S1818), and the process returns (S1819). If it is detected in S1803 that the fault destination address is out of the range of the active protection area of the reference source process, an access protection area list accompanying the process is extracted (S1806), and the fault destination address is included in the access protection area list. It is checked whether a memory section area including a virtual address is included (S1807). If this is included, the protection attribute (cached from the memory section area structure member) of the entry for the access protection area list corresponding to the memory section area and the reference operation (read, write, execute, etc.) The access right is checked (S1808). If it is determined in S1809 that the access is permitted, it is checked whether the access protection area is shared by all the other page table sharing processes (S1810). If the page table is shared by all processes, the page table entry is set, etc., the memory section area corresponding entry including the page is added / set to the active protection area list of the process (S1817), and the process returns. (S1819). If not shared by all the page table sharing processes, consistency of access protection cannot be maintained if the page tables are shared, so the page table generation unit must be requested to create a new page table for the process, and If it is, copy the contents of the currently used shared page table, separate the process from the page table shared process group, attach the newly created page table to the process, set the page table entry, etc. (S1811), an entry corresponding to the memory section area including the page is added / set to the active protection area list of the process (S1812), and the process returns (S1819).
[0082]
If it is determined in step S1809 that the access is not permitted, an error such as a protection exception is returned (S1818) because the request is rejected by one of the combinations of read, write, and execute (S1819), and the process returns (S1819).
[0083]
In S1817, if the access destination area virtual address is not included in the access protection area list, a memory section area list for managing the memory section area information including the fault page is extracted (S1813). The access right of the process is acquired from the protection attribute flag, the area permission list, the area non-permission list, the process permission list, and the process non-permission list, which are the structure members (S1814). As a result, if the access right is recognized, the entry corresponding to the memory section area including the page is set in the access protection area list of the process, inserted in ascending order of the virtual address, and control is transferred to S1810 (S1816). If the access right is not recognized in S1815, an error such as a protection exception is returned (S1818). It returns (S1819). If it is determined in S1814 that the access right is undecided, the access is prohibited.
[0084]
It should be noted that, for the virtual / physical address conversion of the page table entry, the address conversion information is efficiently held by using a multi-stage table such as a “virtual / physical address conversion shared map” as shown in FIG. It is also possible. This is a method similar to the conventional multi-stage page table, in which the page identification part of the virtual address is divided into two, and the first half is used as an offset to an entry in the level 1 table and the second half is used as an offset to an entry in the level 2 table. As shown in FIG. 21, (physical address / page size) is set in each table entry, and a protection attribute such as a page table is not set. Instead, the corresponding memory section area structure identifier is set as a cache in the remaining few bits in the entry in the level 2 table, and the memory section information including the address is again rewritten at high speed from the virtual address at the time of the fault. You may use it to search.
[0085]
The entry in the page table associated with each process is when the address translation information of the corresponding entry of the above “virtual / physical address translation shared map” is valid (when the corresponding page is read in the physical page frame). In this case, the physical address position can be set at high speed by copying this entry. If the address translation information of the corresponding entry is invalid, an entry of the virtual / physical address translation sharing map is set after paging processing is performed, if necessary, and this is the corresponding entry in the process associated page table being executed. Will be copied within. After setting the address conversion information, the protection attribute in the page table entry is set based on the access right of the running process to the memory section area.
[0086]
In the present embodiment, an example is shown in which only one process that has caused an access escapes from the page table sharing process group. However, as a variation, there are some other processes that do not lose access protection due to the access. In such a case, it is conceivable to break away with them. In this case, one new page table is created and shared between the escaped process groups.
[0087]
Further, in the present embodiment, the necessity of departure from the page table sharing process group is determined by a page fault, but the release of the page table sharing is explicitly released by a programmer using a system call or the like. Requests can be easily realized. In this case, the difference from the processing at the time of page fault is that (A) the page fault occurrence and the page fault handler call at the time of the page fault are replaced with the system call request and the system call processing, and (B) the separation determination processing inside the OS. Is unnecessary, and the processing is performed so as to be always separated, so that the subsequent processing can be realized similarly.
[0088]
Next, a third embodiment will be described.
[0089]
Here, a scheduling method is adopted in which a group of processes sharing the address conversion table is continuously executed. As a result, the cost for switching between processes can be significantly reduced.
[0090]
That is, since there is no need to perform a page table switching operation between processes sharing the page table, the scheduler dispatch unit notifies the scheduler of the current page table associated with the next execution process selected from the process execution queue. Is determined, and if the values are the same, a process of not changing the page table is performed. FIG. 22 shows a simple flow from the saving of the execution context of the running process to the dispatch to the next execution process selected by the scheduling.
[0091]
At the time of process switching, first in S2002, the execution context such as register information is saved by the process information saving unit of the process management unit, and the next execution process is selected from the execution queue by the scheduler (process scheduling unit) according to the scheduling policy and the like. This is performed (S2003). Next, the page table top address information of the currently executing process and the selected process is compared, and it is determined whether or not they have the same value (S2004). If the values are the same, the execution context other than the page table top address information of the selection process is recovered (S2005), and the process returns (S2007). If it is determined in S2004 that the values are not the same, the page table start address of the selected process is set in a specific hardware register or TLB flashing is performed (S2006), and then the page table start address information of the selected process is removed. The execution context is recovered (S2005), and the process returns (S2007).
[0092]
By continuously using the page table, switching of the page table and TLB flush are not required at the time of dispatch. Further, after the process switching, when re-accessing the page referred to by the immediately preceding process, if re-accessing the page for which the page table entry is valid, the page table entry can be used as it is. The resetting cost of the entry becomes unnecessary.
[0093]
Further, this optimization policy can be applied at the time of switching between arbitrary processes, and is also applicable when the next execution process is selected between processes having different priorities.
[0094]
Also, if there are multiple processes with the same priority when selecting the next execution process, if there is a process with the same page table as the process executed immediately before, select the process as much as possible. It is preferable to control.
[0095]
Several variations of this policy are possible. (A) A format in which the scheduler sequentially searches the execution queue for a process having the same page table as the process executed immediately before the next execution process is selected. (B) The priority is set when a process is created or a blocked process is restarted. When there is a process sharing the page table in the same execution queue, a process entity is arranged immediately after the process, and the process entity is arranged as continuously as possible. (C) The target process when the running process wakes up the sleeping process. , If they share the same page table, there is a format to preferentially select as the next execution thread. These are shown in FIG.
[0096]
In the above control method, a system / programmer can specify / specify a page table head address associated with each process structure at a registration time of a process entity in an execution queue and a next execution process selection time. This can be realized by comparing / determining based on a control policy.
[0097]
However, if these scheduling policies are prioritized too much, it may cause process starvation or a bias toward the execution of some processes, so it is necessary to calculate for scheduling according to time factors. is there.
[0098]
Next, a fourth embodiment will be described.
[0099]
Here, in a distributed memory type (loosely coupled type) multiprocessor system environment, dispatching is performed so that processes capable of sharing the address conversion table can be executed on the same processor as much as possible.
[0100]
FIG. 24 shows a procedure for assigning processors when a process is generated according to the fourth embodiment.
[0101]
When the process management unit of the OS receives the process generation request (S2201), the process generation unit is called to generate a request to arrange the received process generation request on the processor having the sharable process of the address translation table. It is checked whether the process side has requested (S2202). This request can be made by instructing the OS from the process generation side, for example, by setting an attribute in an argument of the process generation system call.
[0102]
When the request specification is not detected, the process generation unit performs a process generation process on the process generation source processor (S2206, S2208).
[0103]
On the other hand, in the determination of S2202, when the designation of the sharing request for the table is detected, a search request message is transmitted to each processor in order to search for the process sharable process allocation destination processor (S2203). As a procedure for transmitting the message, first, a search may be performed on the processor that has generated the processor, and then, if the processor cannot be detected, a search request may be made with respect to another processor. Returning to the flow, the search request of S2203 is notified to each processor, and each processor receiving the message searches whether the table sharable process exists in its own processor. This search is performed by, for example, comparing the access protection area range on the generation process side with information on a plurality of active protection area ranges that can be stored in each processor, as in the address conversion table sharing determination procedure described in the first embodiment. Can be processed.
[0104]
Next, the search request source processor receives the search result returned from each processor, and determines whether or not the processor holding the address translation table sharable process has detected (S2204). As a result of this determination processing, if the processor is not detected, the process generation source processor is selected, and a request to allocate a generation process is transmitted to the process generation unit on this processor to the generation unit.
[0105]
When the processor holding the address translation table sharable process is detected in the process of S2204, it is checked whether or not the detected processor (group) includes the process generation source processor (S2205). If it is included, after selecting the generation process source processor (S2206), it transmits a generation process allocation request to the process generation unit of the generation process source processor (S2208). If no generation process source processor is included in S2205, an arbitrary processor is selected from the detected processors (group) (S2207), and a generation process allocation request is transmitted to the process generation unit on the processor (S2208). When there are multiple corresponding processors, the selection method can be any of the following.However, the system or programmer specifies the method based on the first response, or the processor usage rate and the available physical memory. It is conceivable to select an appropriate processor according to the selected selection criterion.
[0106]
After the above processing, the process of arranging the process information and the execution queue entry on the local memory associated with the selected processor of the generation process is performed as necessary.
[0107]
As described above, in a loosely-coupled multiprocessor system environment, by scheduling the processes that can share the address translation table so that they can be executed on the same processor as much as possible, it is possible to reduce storage management resources and improve cache efficiency. In addition, since the address translation table is shared using the information of the activated address translation table entry, there is a possibility that the page to be referred to is stored in the local memory associated with the processor in advance. There is also a feature of high.
[0108]
In the present embodiment, the method of allocating to the processor at the time of process generation has been described. As an application example, the system implicitly and periodically checks the active protection area information on each local memory and shares a certain address translation table. By detecting a state in which possible processes are arranged on a plurality of processors, these can be transferred to one local memory, and consequently a process migration can be performed based on the present embodiment. Can be easily realized.
[0109]
In the above description, the processor assignment processing of the address translation table sharable process in the loosely-coupled multiprocessor system environment has been described. However, this processing is performed as shown in FIG. 3 in which each computer host is interconnected on a network. Even when applied in a distributed system environment, the memory arrangement is basically equivalent to that of a loosely-coupled multiprocessor, and can be realized by the control mechanism of the fourth embodiment without loss of generality.
[0110]
As described above, according to the embodiment of the present invention, a single virtual storage space is created on a computer equipped with an MMU and a virtual storage management mechanism that uses a paging table for a paging address conversion method. Address associated with each process in a basic software configuration such as an OS that provides an access protection mechanism that can set an accessible area range for each process for a plurality of areas arranged in a single virtual storage space. By calculating the range of the valid page area based on the entry information validated in the translation table, and increasing the opportunity of sharing the address translation table that guarantees the consistency of the access protection to the area among a plurality of processes, Reduction of storage space management resources (page table, TLB, etc.) and the accompanying storage of physical memory Improvement of area size (cache ratio), reducing the change notification frequency for address conversion between table coherence controller according to the address conversion table number of reduction by the address conversion table sharing allows like.
[0111]
Further, until a reference is made to an area where the consistency of the access protection cannot be guaranteed if the address translation table is shared, the timing of creating a new separate address translation table / associating the new address table with the corresponding process is delayed. be able to.
[0112]
Further, by selecting the next process to be executed and arranging the process entities in the process execution queue as much as possible by detecting the group of processes sharing the address translation table and controlling the scheduling, the page table switching TLB generated at the time of process switching is performed. The number of flushes can be reduced, the cache rate can be improved by continuously using the shared address translation table, and resetting of the address translation table entry can be avoided.
[0113]
Furthermore, in a distributed memory type (loosely coupled type) multiprocessor system, by allocating processors focusing on the possibility of sharing an address conversion table of a generation process, resources for virtual memory space management can be reduced for each local memory of each processor. It is also possible to reduce the frequency of reporting consistency control between processors for virtual storage management information.
[0114]
The present invention is not limited to the above-described embodiments, and can be variously modified and implemented without departing from the gist thereof.
[0115]
【The invention's effect】
As described above, according to the present invention, in a system in which a single virtual memory space is shared by all processes, the address translation table can be shared between processes while guaranteeing the access protection function of each process. Therefore, it is possible to sufficiently improve the reliability, to achieve high reliability, and to minimize the cost for storage management resources and process switching.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration example of a single processor system to which a virtual storage management method according to an embodiment of the present invention is applied.
FIG. 2 is a block diagram showing a first configuration example of a multiprocessor system to which a virtual storage management method according to an embodiment of the present invention is applied;
FIG. 3 is a block diagram showing a second configuration example of a multiprocessor system to which the virtual storage management method according to one embodiment of the present invention is applied;
FIG. 4 is an exemplary view showing an example of a relationship between an execution process and data in the embodiment.
FIG. 5 is an exemplary view showing an example of a relationship between each process and an access protection area range in the embodiment.
FIG. 6 is an exemplary block diagram showing a configuration example of an OS for realizing the virtual storage management method of the embodiment.
FIG. 7 is an exemplary view showing an example of a process structure used in the virtual storage management method according to the embodiment;
FIG. 8 is an exemplary view showing an example of an access / active protection area structure used in the virtual storage management method of the embodiment.
FIG. 9 is an exemplary view showing the configuration of an access / active protection area list entry used in the virtual storage management method according to the embodiment;
FIG. 10 is an exemplary view showing the configuration of a memory section area structure entry used in the virtual storage management method according to the embodiment;
FIG. 11 is an exemplary view showing a configuration of a permission / non-permission entry of a pair area and a process used in the virtual storage management method of the embodiment.
FIG. 12 is a view showing an arrangement of an access protection area in a process 1 in the embodiment.
FIG. 13 is a view showing the arrangement of active protection areas during execution of process 1 in the embodiment.
FIG. 14 is a view showing an arrangement of an access protection area in a process 2 in the embodiment.
FIG. 15 is an exemplary view showing the relationship of an access / active protection area between processes 1 and 2 in the embodiment.
FIG. 16 is an exemplary flowchart illustrating the procedure of a process of sharing a page table by specifying a process in the embodiment.
FIG. 17 is an exemplary view showing an example of sharing the active protection area list and the page table of the process 1 by the process 2 in the embodiment.
FIG. 18 is a diagram showing a state of the active protection area and each access protection area after the process 1 accesses the area (E) during execution in the embodiment.
FIG. 19 is an exemplary flowchart showing the processing procedure for determining the possibility of continuation of sharing of the page table and for separation when a page fault occurs in the embodiment.
FIG. 20 is an exemplary view showing the relationship between the virtual / physical address conversion sharing map and the page table of the currently executed process according to the embodiment;
FIG. 21 is a diagram showing a configuration of a page table entry in FIG. 20.
FIG. 22 is an exemplary flowchart showing the flow of scheduling corresponding to dispatch between page table sharing processes in the embodiment.
FIG. 23 is an exemplary view showing an example of selection / arrangement of a process entity related to the page table sharing process in the embodiment.
FIG. 24 is an exemplary flowchart showing the procedure of processor assignment processing during process generation in the embodiment.
FIG. 25 is a diagram showing an example of a conventional single virtual storage space management method.
FIG. 26 is a diagram showing another example of a conventional single virtual storage space management method.
[Explanation of symbols]
11 CPU, 12 MMU, 13 physical memory, 14 secondary storage, 21 process management unit, 22 virtual storage management unit, 23 page table management unit, 24 memory section area management unit, 25 protection Area management unit.

Claims (2)

A virtual storage management method for performing virtual storage management by paging using a single virtual storage space shared by a plurality of processes executed on a computer system,
For each of a plurality of areas that can be arranged in the single virtual storage space, define an area accessible for each process and an attribute of access protection for the area,
Detecting a process to which an accessible area to which a page currently read in the physical memory belongs in an accessible area of a process is accessible, and an access protection attribute for the area is the same as the process,
A virtual storage management method, characterized by sharing an address conversion table for converting a virtual address into a physical address between the processes. A virtual storage management method for performing virtual storage management by paging using a single virtual storage space shared by a plurality of processes executed on a computer system,
For each of a plurality of areas that can be arranged in the single virtual storage space, define an area accessible for each process and an attribute of access protection for the area,
Detecting a process to which an accessible area to which a page currently being read in the physical memory belongs in an accessible area of a process is accessible, and an access protection attribute for the area is the same as the process;
An address translation table for translating a virtual address to a physical address is shared between the processes,
Canceling the sharing of the address translation table when a page belonging to a new area that cannot guarantee the consistency of access protection between processes sharing the address translation table is read into the physical memory due to the occurrence of a page fault. A virtual storage management method characterized by the following.

Images