JP3060481B2 - Segment roll-in / roll-out method - Google Patents

Description

Description: BACKGROUND OF THE INVENTION The present invention relates to a segment roll-out / roll-in method between a main storage device and an auxiliary storage device in an operating system having a virtual storage mechanism.

[Conventional technology]

Conventionally, when realizing a virtual storage mechanism in an operating system, an area of an auxiliary storage device to which a segment is rolled out / rolled in must be reserved for a dedicated purpose. It could not be used for purposes other than roll-in.

[Problems to be solved by the invention]

The auxiliary storage device of the system is used not only as an area to be rolled out, but also as a file system. In the above-described conventional method, the size of each is limited. In particular, under a processor having a wide addressing function compared to the sizes of the auxiliary storage device and the main storage device, the size of the swap area has become a limiting factor of the size of the program to be executed.

[Means for solving the problem]

According to the configuration of the present invention, the file system in the auxiliary storage device is a file system management block having a group of blocks to be used for a file or a swap area or a pointer to such a block, and additionally having a mutual pointer. A collection of free blocks not used as the file or the swap area among the blocks of the file system are formed by having a pointer to another free block in the free block itself. It has a function of managing by a queue, connecting and disconnecting a designated block to and from the free block queue, and further includes, within the file system management block,
A free file system management block having no pointer to the file or the swap area is managed by a queue formed by having a pointer to another free file system management block in the free file system management block itself. And a file management mechanism having a function of connecting and disconnecting a designated file system management block to and from the free file system management block queue, and an input / output for inputting / outputting data to / from the auxiliary storage device using position information in the auxiliary storage device. If there is sufficient free space in the fixed swap area for the purpose of roll-out / roll-in only in the auxiliary storage device, a roll-out is performed using the input / output mechanism, and the roll-out destination Segment information is stored for each process. A rollout mechanism that sets information indicating that such area is in use in the fixed swap area management table, and calls a file system rollout mechanism when there is not enough space for this area. Using the file management mechanism, from the file system, fetch the required number of blocks to roll out from the free block queue, and further divide the required number of file system management blocks to point to these blocks. The block is taken out from the free file system management block queue, and the block is rolled out. As the position information of the rollout destination, the identification of the auxiliary storage device, the position of the file system management block in the auxiliary storage device, the file system management Point to a block within a block A file system rollout mechanism for setting the position of the segment in the segment management table, and when the rollout destination of the segment is the fixed swap area, the position information of the rollout destination of the auxiliary storage device from the segment management table. Then, using the input / output mechanism, the segment is rolled into the main storage device, the position information in the segment management table is rewritten, and the rolled-in address of the main storage device is set as the fixed swap area. If the area of the management table sets information indicating that it is not in use and the rollout destination is a file system, a roll-in mechanism that calls a file system roll-in mechanism, and from the segment management table,
The location information of the rollout destination is obtained, and by using the information, the input / output management mechanism is used to roll in the main storage device and erase the pointers to all the rolled-in file system management blocks. Then, the block is connected to the empty block queue, and if all pointers to the blocks of the file system management block are deleted by this processing, this is connected to the empty file system management block queue, and the position of the segment management table is A file system roll-in mechanism that rewrites information and uses the roll-in address of the main storage device, and a necessary segment is placed on the main storage when a program is executed, and the roll-in mechanism is used as soon as a new segment is needed. Using the auxiliary storage device and the main storage device And rolls in, when the main memory is insufficient, the use of a roll-out mechanism, characterized by having a virtual memory mechanism for a segment is unnecessary to perform roll out to auxiliary storage.

〔Example〕

 Next, the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing one embodiment of the present invention, FIG. 2 is a detailed view of the file system 9 in FIG. 1, and FIG. 3 is a detailed view of the segment management table 11 in FIG. FIG. 4 is a diagram showing the relationship between the fixed swap area management table 10 and the fixed swap area 8 in detail.

In FIG. 2, the file system 9 includes a swap file system and a non-swap file system.
The swap file system includes a file system management block area 107 and a block area 108. The file system management block area 107 is composed of a group of file system management blocks 101, 102, 103, 104, 105 and 106. Such file system management blocks include free file system management blocks 102, 105, 10
6, File management block 101, Swap management block
There are 103 and 104, all three of which have different names depending on the purpose of use, and by changing the contents, they change each other.

Also, the block area 108 includes blocks 201, 202, 203, 20
It consists of a collection of 4,205,206,207,208,209,210,211,212. The blocks include management blocks 205, 210, 211, 204,
208, file blocks 201 and 209, and swap block
Although there are 202 and 207, all three have names changed according to the purpose of use, and these change mutually by changing the pointer. The file management block 101 holds pointers to the blocks 201, 206, and 209, and constitutes a file by this. Swap management block 10
3 holds a pointer to another swap management block 104 and is connected by the pointer.

Further, they hold pointers to the blocks 202, 207, 203, 212, and the content pointed out by the blocks 202, 207, 203, 212 stores the rolled out contents. The free file system management blocks 102, 105, and 106 are the remaining file system management blocks other than the two, and hold pointers to other free file system management blocks, and are linked by the pointers to form a queue. The empty blocks 205, 210, 211, 204, and 208 hold pointers to other empty blocks, and are linked by the pointers.

The pointer to the block from the file system management block may be any pointer that can identify the position on the auxiliary storage device. However, the input / output mechanism 7 must be capable of performing input / output using this position information.

Conversely, in a non-swap file system, the file system rollout mechanism 5 does not become a rollout target, and no swap block or swap management block is created. Others are exactly the same as the swap file system.

In a swap file system, if no swap occurs, and if so, after all of them have been rolled in, the swap block and the swap management block no longer exist in the file system. In this state, the swap file system is no different from a non-swap file system. The swap file system uses the free blocks of the file system for rollout as needed.

The file management mechanism 6 has a function of extracting a free block of a file system from the free block queues 205, 210, 211, 204, and 208, a function of connecting a block to the free block queue, a function of extracting a file system management block from the free file system management block queues 102, 105, and 106. It has a function to connect the file system management block to the free file system management block queue.

In FIG. 4, the fixed swap area 8 divides an area of the auxiliary storage device into a certain size, and is divided into 401, 402, 403, 404, and 40.
5,406,407,408, which are used only for the purpose of roll-out / roll-in. The fixed swap area management information 10 manages which part is used. The fixed swap area management information 10 exists for each fixed swap area.

The input / output means 7 transfers data from the auxiliary storage device to the main storage or from the main storage to the auxiliary storage device based on the position information of the main storage device and the auxiliary storage device.

Next, details of the processing of each mechanism will be described along with the flow of the roll-out and roll-in processing.

In the case of expanding the program area or when there is no area required for creating a new process, the virtual storage mechanism 1 determines which segment of which process is to be rolled out, and uses the process identifier and the segment identifier based on the process identifier and the segment identifier. , The rollout means 3 is called.

The rollout means 3 is called from the virtual storage mechanism 1 when a rollout is required, and first checks the fixed swap area management information 10 to determine whether or not the fixed swap area 8 has a free space. If there is a vacancy, an attempt is made to roll out to the fixed swap area 8 with priority. At this time,
Which area of the fixed swap area was used,
Described in the fixed swap area management information 10. At this time, since there are generally a plurality of fixed swap areas 8, an identifier for identifying the auxiliary storage device is also described. By doing so, the auxiliary storage device can be used for discriminating whether it is used for a file system described later or for a fixed swap area, which is convenient. In this manner, the input / output processing mechanism 7 is called up based on the identification of the auxiliary storage device and the internal position information, and rolls out.

If there is no free space in the fixed swap area, the file system rollout means 5 is called. The file system rollout means 5 takes out the block from the free block queue using the file management mechanism 6. This process is repeated as necessary. In the middle,
If there are no more free blocks in the file system, this process is aborted, all blocks taken so far are returned to the free block queue using the file management mechanism 6, and an error is notified to the caller. Finish the process.

If a free file block can be secured as desired, the free file system management block is then taken from the free file system management block queue using the file management mechanism 6. If the file system management block cannot be secured here, as in the case where the free file block is insufficient, an error is notified to the caller as a swap failure, and the processing is terminated.

The newly taken file block and file system management block are used for roll-out / roll-in, so they are called a swap block and a swap management block, respectively. Holds a pointer to When there are a plurality of swap management blocks, they are connected by a pointer. The head of this is held by the file management mechanism 6.

If there is room in the pointer area of the swap management block in the immediately preceding rollout processing, the swap block when the next rollout is performed is first pointed from the swap management block. Also, if this area is swapped in, the pointer will be missed, but the next rollout process will preferentially connect to the file management block with the missing pointer.

If it is desired to prevent the file system from being squeezed due to frequent rollouts, the relationship between the upper limit of the rollout and the free blocks of the file system is defined at the time of system configuration. For example, it may be determined based on the remaining number of empty file blocks. The file system to be rolled out is also specified at the time of system configuration. For example, a swap is performed for one that does not hinder the running of the system.

Of course, there may be a plurality of rollout destination file systems. At this time, if the rollout fails for a certain file system, an attempt is made to another file system.

Then, the secured free file management block is connected to the swap management block, and the swap block is connected to the swap management block in the order in which the blocks are rolled out.

When the virtual storage mechanism 1 refers to a segment that does not exist in the main storage during execution of a program, the program counter of the program knows which segment has been accessed, and uses the program identifier and the segment identifier to determine Call roll-in means. Usually, as a function of the processor, an internal interrupt such as "there is no inconsistency in the logical address but no actual memory exists" is prepared, and this triggers.

The roll-in means 2 is called from the virtual storage mechanism 1 when the segment needs to be rolled in, first obtains the segment management information 11 of the corresponding process, checks where the rollout destination is, and fixes In the case of the swap area 8, the position inside the auxiliary storage device is further obtained from the process management information 11, and the input / output mechanism 7 is called by this to roll in. If the file system has been rolled out to the file system 9, the file system roll-in means 4 is called.

In the file system roll-in mechanism 4, from the segment management information 11, identification of the file system, that is, identification of an auxiliary storage device, the position of the file system management block in the file system, and a plurality of files in the file system management block Information on which pointer is among the pointers to the block is obtained. As a result, the position of the segment on the auxiliary storage device to which the segment has been rolled out can be known, and based on this, the segment is rolled into the main storage using the input / output control mechanism.

The swap block that has become unnecessary due to the roll-in is connected to the free block queue using the file management mechanism 6 and, at the same time, the pointer of the swap management block is removed. For the segment that requested this processing,
repeat. If any of the swap file management blocks has no pointer to the file block as a result of this processing, the swap management block is linked to the free file management block queue using the file management mechanism 6. .

Under the virtual storage mechanism 1, not all user programs exist in the main memory, only the part 12 involved in execution exists in the main memory preferentially, and the remaining segments Sometimes rolled into main memory. This situation will be described with reference to FIG. In FIG. 3, the user program is composed of five segments 302, 303, 304, 305, and 306. Two of the segments 302, 304, and 305 exist in the main storage device 313, 315, and 314, but one of the remaining segments 303 has four blocks of the fixed swap area 8. Rolled out to 403,404,405,406, one remaining segment 306 is block 2 of file system 9
Rolled out to 03,207.

In the segment management information 11, the size of each segment of the program and the location of the segment, that is, the main storage device 13, the fixed swap area 8, the file system 9
In the case of the main storage device, information on the address of the auxiliary storage device in the case of the main storage device, and information on which auxiliary storage device is located in the auxiliary storage device of the file system management block serving as a pointer to the swap block in the file system. In the case of the main storage device, information on the position of the pointer in the real memory is stored. ing.

〔The invention's effect〕

As described above, according to the present invention, the area to be swapped out can be dynamically secured, and when the swapout is unnecessary, these empty blocks can be provided to a file. .

[Brief description of the drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention, and FIG.
FIG. 3 is a detailed view of the file system 9 in FIG.
FIG. 4 shows the relationship between the segment management table 11 and the program 12 on the main memory. FIG. 4 shows the relationship between the details of the fixed swap area management table 10 in FIG. 1 virtual memory mechanism 2 roll-in mechanism 3 roll-out mechanism 4 system file roll-in mechanism 5 system file roll-out mechanism 6
File management mechanism 7, Input / output mechanism 8, Fixed swap area 9, File system 10, Fixed swap area management table 11, Segment management table
12: Program in main memory, 13: Main memory, 14 ...
... Auxiliary storage device, 101 ... File management block, 102 ...
… Free file management block (queue top), 103 ……
Swap management block (head of queue), 104: Swap management block, 105, 106: Free file management block, 107: File system management block area, 108:
… Block area, 201, 206, 209… Block (file block), 202, 203, 207, 212, 401 to 408… Block (swap block), 204, 208, 210, 211… Block (empty block), 205… Block (empty block queue top), 301… Execution program, 302,303,304,30
5,306: segment of execution program, 307: segment management table, 308: position information of segment 302,
309: Position information of segment 303, 310: Segment 3
04 location information, 311 …… Segment 305 location information, 312
…… Segment 306 position information, 313 …… Segment 302
(In main memory), 314... Entity of segment 304 (in main memory), 315... Entity of segment 305 (in main memory),
403, 404, 405, 406... Entity of segment 303 (within fixed swap area), 207, 203... Entity of segment 306 (within file system).

Continuation of the front page (56) References Junro Emura, "Structural Approach to Operating Systems (2)" (Japan Computer Association, 1977) P871-889 Leffler et al, "The Desing and Implementment of the 4.3 BSD" UNIX opportuning system "(Addison-Wesley, 1989) p134-136, p155-161 (58) Fields investigated (Int. Cl. ⁷ , DB name) G06F 12/08-12/12 G06F 9/46 G06F 12 / 00

Claims (1)

(57) [Claims] A file system in an auxiliary storage device is a group of blocks for providing a file or a swap area, or a group of file system management blocks having pointers to such blocks and also having mutual pointers. In the blocks of the file system, empty blocks not used as the file or the swap area are stored in the empty blocks themselves.
It has a function of managing a queue formed by having a pointer to another free block, connecting and disconnecting a specified block to and from the free block queue, and further includes, within the file system management block, The empty file system management block having no pointer to the swap area is managed and designated by a queue formed by having a pointer to another empty file system management block in the empty file system management block itself. A file management mechanism having a function of connecting and disconnecting the obtained file system management block to and from the free file system management block queue, an input / output mechanism for performing input / output to / from the auxiliary storage device using position information in the auxiliary storage device, Roll-out in the auxiliary storage device If there is a sufficient free space in the fixed swap area provided only for the purpose of roll-in, a roll-out is performed using the input / output mechanism, and the position information of the roll-out destination is stored in the segment management table for each process. A fixed swap area management table to set information indicating that such area is in use, and a rollout mechanism that calls a file system rollout mechanism when there is not enough space for this,
Using the file management mechanism, from the file system, fetch the required number of blocks to roll out from the free block queue, and further divide the required number of file system management blocks to point to these blocks. The block is taken out from the free file system management block queue, and the block is rolled out. As the position information of the rollout destination, the identification of the auxiliary storage device, the position of the file system management block in the auxiliary storage device, the file system management A file system rollout mechanism for setting the position of a pointer to a block within a block in the segment management table, and an auxiliary storage from the segment management table when the rollout destination of the segment is the fixed swap area. Dress Then, using the input / output mechanism, the segment is rolled into the main storage device, the position information in the segment management table is rewritten, and the roll-in destination of the main storage device is rewritten. Information indicating that the area of the fixed swap area management table is not in use, a roll-in mechanism for calling a file system roll-in mechanism when the roll-out destination is a file system, and the segment From the management table, the location information of the rollout destination is obtained, and by using this, the input / output management mechanism is used to roll in to the main storage device and to all the blocks in the file system management block that have been rolled in. Pointer, and connect such a block to the empty block queue. If all the pointers to the blocks of the file system management block are erased by this process, this is linked to the empty file system management block queue, the position information of the segment management table is rewritten, and the main storage device is rolled in. A file system roll-in mechanism to be used as an address, and a necessary segment is placed on the main storage at the time of execution of a program, and as soon as a new segment is needed, the roll-in mechanism is used to transfer data from the auxiliary storage device to the main storage device. Roll-in / roll-in of a segment characterized by having a virtual storage mechanism for rolling-in and, when the main memory is insufficient, using the roll-out mechanism to roll out a segment unnecessary for execution to an auxiliary storage device. Out method.