JPH0119183B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an improvement in a working set management method in a virtual memory type information processing system that operates with multiprogramming.

In a virtual memory type information processing system that operates with multiprogramming, the problem is how to allocate main memory pages to each program on the main memory.

As a method for determining the number of main memory pages to be allocated to each program, for a certain program,
A so-called working set method is known in which pages referenced within a certain period of time (this is called the window size) are reserved for the program. (hereinafter referred to as the WS method) To accurately implement the WS method, each time a page in main memory is referenced, the referenced time is stored as the last referenced time, and the page is stored in main memory. It is necessary to search for a page in which a time before the above window size is recorded, remove it from the working set, and register it as a free page.
WS management is impractical in terms of management overhead and is actually achieved as follows.

That is, reference bits and reference counters corresponding to each page are prepared in order to manage how each page on the main memory is accessed.

The reference bit is set when a main memory access is made to the corresponding page.

Each time a certain WS review occurs, WS review management is activated, checks the reference bit for all pages on the main memory, and if this is on, that is, if there is a reference to the corresponding page, the reference bit is Counter is reset. When the reference bit is off, that is, when the corresponding page is not accessed, the reference count value is incremented. The reference count value is a certain value n
If the page becomes larger than , that is, if it is not referenced for n cycles and falls outside the window size, the page is removed from the working set frame to which it was connected and placed in the free page pool as an unnecessary page. be registered.

If a page fault occurs during program execution, a page is taken from the free page pool and given to the program.
That is, it is connected to the working set frame corresponding to the program.

With this method, the number of pages allocated to each program is reduced or expanded as necessary depending on the operating status of that program, so main memory can be used more effectively than when pages are fixedly assigned to a program. is possible.

On the other hand, depending on the program, the amount of memory required is often known based on data from the time the program was created or from past program execution. In such a case, it is not necessarily necessary to use the working set method, which measures the amount of memory required at that time each time a program is executed.On the contrary, if the working set method is applied,
Performance may deteriorate due to this management overhead.

It is an object of the present invention to provide an improved working set management scheme with reduced management overhead.

The present invention makes it possible to specify the minimum and maximum amount of memory to be given to a program for which working set information is known, as well as to specify that the working set does not need to be reviewed. This is intended to reduce the overhead of working set review by not reviewing the working set for the working set frame corresponding to the program.

Next, an embodiment of the present invention will be described. Prior to this, an outline of an implementation example of a conventional working set management system will be explained with reference to FIG.

The following tables are prepared to realize working set (hereinafter abbreviated as WS) management.

WS control block 1 (hereinafter abbreviated as WSCB)
is a table for managing pages belonging to a WS frame, which is a unit of each WS management, and for each WS frame,
Here, it is assumed that WS is managed for each program, so each program has an entry i, and entry i contains the number of pages PNi belonging to that WS frame, and the maximum number of pages allowed for that WS frame MXi. , the minimum value MNi, and a pointer PTRi of the page list belonging to that WS frame are prepared.

Pool frame control block 2 (hereinafter abbreviated as pool CB) does not belong to any WS frame. A table for managing unused pages, showing the number of unused pages.
Pointer to PPN and unused page list
Has PPTR.

The memory map 3 is a table for managing real pages on the main memory, and has an entry for each page.

Each entry has a pointer section and a usage information section, and the pointer section allows real pages to form a list of pages that belong to either a WS frame or a pool frame.

Usage status information includes usage bits UB and usage counts UC.

The usage bit UB is set to, for example, "1" when a page is referenced, and the usage count UC is
will be updated when the WS is reviewed as shown below. Further, a threshold register 4 is prepared that holds a cycle threshold (window size) to be removed from the WS. Also, the value of the threshold register 4 and the usage count
A comparison circuit is provided to compare the value of UC.

The following operations are performed for each WS frame by the WS review timer interrupt, which is activated at regular intervals. In other words, the memory map is sequentially traced using the pointer PTRi of WSCBi. The memory map entry is read and the reference bit is checked, and if it is "1", that is, if there is a reference, the reference bit is cleared to "0" and the usage count is cleared. If the reference bit is "0", the usage count is counted up. The comparison circuit 5 compares this update result with the value n of the threshold register 4, and if the usage count value reaches n, this page is considered to be out of the working set and is removed from the page list of this WS frame. (However, if the number of pages in that WS frame is already less than MNi, it will not be returned to the pool.) By performing this operation, n cycles of WS review will be completed. Pages that have not been referenced for a while are
It will be removed from the WS frame and returned to the pool frame.

A flowchart outlining this operation is shown in FIG. In the event of a page fault, first allocate a page from the pool frame to the WS frame of the program that generated this page fault, start transferring the requested page from the packing store, and reduce the number of pages in this WS frame. Perform a check.

If the allocation results in a page larger than the maximum value MXi, if there is a page with a usage count of n in that WS frame, it is returned to the pool frame. If not, for each page in this WS frame,
The usage count is updated while checking and clearing the usage bits, and as a result of this update, the usage count becomes n.
This process is performed until a page is generated, and the page whose usage count reaches n is returned to the pool.

As a result of allocation, if the number of pages in the WS frame is greater than the minimum value but less than the maximum value, check whether there is a page with a usage count of n in this WS frame, and if there is, it is Removed from WS frame and returned to pool frame. If there is no page with a usage count of n, the page is returned to the pool only if there is a shortage in the number of pages in the pool, that is, if the current number of pages in the pool is smaller than the shortage threshold.

If the number of pages PNi in the WS frame is less than the minimum value MNi, the pages will not be returned to the pool.

Note that page allocation from the pool frame to the WS frame is performed as follows.

First, the number of pages PPN of the pool frame control block
is decreased by 1, and the value of the pointer part PPTR, that is, the first page number of the pool at that time, is saved, and the value of the pointer part PTRj of the entry j of memory map 3 specified by PPTR (assuming that it has a value j), that is, The pointer of the pool frame control block is set to the number of the page connected next to the first page. In other words, this is set as the new first page. This completes the removal process from the pool frame. Next, the WS that should connect the page to the pointer PTRj of entry j that corresponds to the pointer saved ahead of the memory map.
Pointer to the i-th entry of the WSCB corresponding to the frame
Set the value of PTRi. After this pointer
The previously saved value j is set in PTRi, and the current page number PN is increased by 1. This means that the page that was previously removed from the pool frame is connected to the WS frame.

Pages are returned from the WS slot to the pool slot at the same time.

FIG. 2 is a block diagram showing the configuration of an embodiment embodying the present invention.

In this example, as shown in the figure, WSCB
In addition to the fields shown in FIG. 1, 1 is provided with a valid bit V for indicating the validity of each entry, and a bit R for indicating whether or not the WS for the corresponding WS frame is necessary.

Next, the operation of one embodiment of the present invention will be explained.

In this embodiment, a WS frame is prepared for each program, that is, a task, and the job control statement for each program specifies the minimum and maximum values of WS to be given to that program and the requirements for WS review for this program. It shall be possible to specify whether or not to do so.

When starting a program, when task control block i is given to this program,
WSCBi is also allocated and the valid bit in WSCBi is turned on as well as the command specified in the job control statement.
The WS minimum and maximum values are set to MNi and MAXi, respectively. Ri is set to "0" if WS review is not necessary, and "1" if it is necessary.
From now on, loading programs, loading pages when a page fault occurs, etc. will be performed in the WS frame specified by the task control block.

In this embodiment, a WS frame selection control section and a WS review control section are provided to control WS review.

The WS frame selection control unit is activated at regular intervals,
A WS frame for which WS review is to be performed is selected, and the WS review control unit performs WS review processing for the WS frame selected by the WS frame selection control unit. When reviewing the WS that is activated at regular intervals, the WS frame selection control unit selects the WS frame that is currently in use, that is, the valid bit Vi is on.
WS frames are selected in sequence, and the review necessity flag Ri of WSCBi corresponding to the selected WS frame i is read. If this value is "0", that is, if review is not necessary, the corresponding WS frame is WS The selection process continues for the next WS frame without making it a subject of review. If the flag Ri is “1”, that is, if it is specified that a review is required, the WS for this WS frame is
Launch review. The above (assuming N) processes are performed for all WSCBs. A flowchart of this operation is shown in FIG.

The activated WS review control unit performs the same processing as in the implementation example. A flowchart of this operation is shown in FIG.

An embodiment of the present invention has been described above, but the gist of the present invention is to prevent WS review from being performed for WS frames that have been designated as not requiring WS review. We have made it possible to reduce the overhead of reviewing WS, and we have provided some information on how to correspond between programs and WS frames, how to specify usage counts, and how to manage specific page usage status. There may be ways to achieve this.

In addition, the WS frame selection control unit shown in this embodiment,
The details of how to implement the WS review control unit, the details of how to connect pages between the WS frame and the pool frame, etc. are not directly related to the gist of the present invention, so to avoid complicating the explanation, I will not discuss them. , it will be clear that these can be realized by conventionally known methods.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing an implementation example of a conventional WS management method, FIG. 2 is a block diagram showing the configuration of an embodiment embodying the present invention, and FIG. 3 is a block diagram showing an embodiment of the present invention. A flowchart of the process of the review WS frame selection control unit is shown. FIG. 4 shows a flowchart of the processing of the WS review control unit in one embodiment of the present invention. 1 is a WS frame control block, 2 is a pool frame control block, 3 is a memory map, 4 is a threshold register, 5 is a comparison circuit, and 6 is a count up circuit.

Claims (1)

[Claims] 1. In a virtual memory information processing system that operates with multiple programs, one or more working set frame control blocks, which are the units for managing working sets, have the minimum and maximum number of pages allowed in that working set frame. and a field to specify whether or not to review the working set at regular intervals. A working set management method characterized by not having to be reviewed.