JPH01162954A - Memory management system - Google Patents

Abstract

PURPOSE:To effectively store and extend data with a small shift extent of data by allocating the data in a fixed data area so that the idle areas are collected at the center part. CONSTITUTION:A memory control part 12 refers to a data control table 112 and an idle area control table 113 to perform the storage, deletion, expansion, etc., to a fixed data area 111. Then the part 12 replaces the contents of both tables 112 and 113 based on said processing results. The data are allocated so that an idle area is always formed at the center part of the area 111. Thus it is possible to quickly detect the presence or absence of the idle areas required for storage and extension of data. As a result, the data are stored and extend effectively with a small shift extent of data.

Description

[Detailed Description of the Invention] [Summary] Regarding a memory management method for storing, deleting, and expanding multiple pieces of variable-length data in a fixed data area on memory, this method collects free space in the center of the fixed data area. The purpose of this paper is to efficiently create, store, and expand data with a small amount of data movement. When storing data, it is stored alternately from the top or bottom of the fixed data area, and when deleting data, it is stored from the top (bottom) of the fixed data area.
When you delete data on the lower side, move the data upwards (downwards) to fill up the free space for the deleted data, and when expanding data on the upper (lower) side, move the data to the lower side of the data. In order to create a free area, other data is moved to the free area side and expanded data is stored, so that a free area is always formed in the center of the fixed data area.

[Industrial application field]

The present invention relates to a memory management method for storing, deleting, and expanding a plurality of variable length data in a fixed data area having a fixed memory capacity.

[Conventional technology]

In the field of computers, when referring to or updating data in an external storage device such as a disk, the contents of the external storage device are first loaded onto memory. In that case, the following processing is performed.

■ Store data in memory.

■ Delete data from memory.

■ Expand data in memory.

On the other hand, there are conditions such as the memory has a limited capacity, the data has a variable length and must be stored in a continuous area, and the data area cannot be reduced but expanded.

Under these conditions, memory management is performed so that the above-mentioned processes (1) to (4) are performed satisfactorily.

FIG. 6 is a block diagram showing a conventional memory management system. In FIG. 6, reference numeral 21 denotes a memory, a fixed data area 211. Data management table 21
2 and a free space management table 213.

The fixed data area 211 contains data 1. 3. 4 and free areas a to c, etc., exist. The data management table 212 includes a flag indicating whether each data such as data 1 and data 2 exists in the fixed data area 211 (ON when it exists, 0FF when it does not exist), and each data that exists. The registration pointer, data length and position of each data are registered.

In the free space management table 213, the length and position of each free space on the fixed data area 211 are registered.

22 is a memory management control unit, which includes a data management table 212;
Processing such as storing, deleting, and expanding data in the fixed data area 211 is performed with reference to the free space management table 213, and data management table 212 is performed based on the processing results.
and performs processing to update the contents of the free space management table 213.

23 is a data person output control unit and a disk 24A.

Performs human output control such as data storage and retrieval for 24B, 24C, etc. Data is input and output in units of bytes.

In this configuration, when storing data, for example, when storing data 5 from the disk 24A, the memory management control unit 22 refers to the free space management table and determines whether there is a free space in which data 5 can be stored. do. If it exists, the data output control unit 23 outputs it to the disk 24.
Data 5 is extracted from A and stored in the free area. If there is not enough free space, free space a
.

After rearranging b and c so that they are continuous and securing an empty area that can store data 5, the data input/output control unit 2
3, the data 5 is taken out from the disk 24A and stored in the free area. Furthermore, in response to the storage of data 5, a data management table 212 and a free space management table 213 are created.
Update the contents of. If sufficient free space cannot be secured only by rearranging free space, the necessary free space is secured by evicting data in order starting from the oldest.

When deleting data (for example, data 2) on the fixed data area 211, the memory management control unit 22 deletes data 2 from the fixed data area 211, and then deletes the contents of the data management table 212 and free space management table 213. Update.

When expanding data (for example, data 1), the memory management control unit 22 refers to the data management table 212 and the free space management table 213 and determines whether there is a free space next to data 1 that can store the extended data. do. When the space a next to data 1 shown in the figure can store extended data of data 1, the extended data is stored in space a. If the extended data cannot be stored with only free space a,
After rearranging so that empty b or empty C is continuous with empty a and securing the length of the extended data, the extended data is stored following data 1. Further, the contents of the data management table 212 and the free space management table 213 are updated in accordance with the storage of extended data. If sufficient free space cannot be secured only by rearranging free space, the necessary free space is secured by evicting data in order starting from the oldest.

[Problem that the invention seeks to solve]

As mentioned above, the conventional memory management method arranges data areas and free areas irregularly in the data fixed area, manages each data area and free area using a data management table and a free space management table, and manages the data. In order to secure the necessary data area during storage and expansion, data areas and free areas must be rearranged and data must be removed.

However, since data areas and free areas are irregularly arranged, relocation requires moving a lot of data, which complicates processing and takes time to store and expand data. There was a problem. Also,
When the number of small free areas increases, page faults are more likely to occur, and this also poses a problem in that data storage and expansion processing cannot be performed efficiently.

The present invention is an improved memory that arranges each piece of data in a fixed data area so that free areas are grouped together in the center, and can efficiently store and expand data with a small amount of data movement. The purpose is to provide a management method.

[Means for solving problems]

The solution adopted by the present invention will be explained with reference to the principle diagram of FIG. In FIG. 1, 111 is a fixed data area whose capacity is fixed, the upper half of which is an upper data area 111U, and the lower half of which is a lower data area 111L.

When storing data, data is stored alternately up and down from the top or bottom of the free space in the fixed data area 111 (first
(a) in Figure (A)).

When deleting data, when the data in the upper data area 111U (for example, data 1) is deleted, the entire data (data 3) in the upper data area 11LU located below it is moved upward and the deleted data is deleted. Fill up the free space in (
Figure 1 (B)), (C)), lower data area 11
When you delete data in 1L (for example, data 2),
The entire data (data 4) in the lower data area 111L above it is moved downward to fill up the empty area of the deleted data ((b) and (d) in FIG. 1(B)).

When expanding data (for example, data l) in the upper data area 111U, all the data in the upper data area 111U below it must be extended to data 3.
) to the free area side to store expanded data. When expanding data (for example, data 2) in the lower data area 1lIL ((e) in Figure 1(C)), move the The entire data (data 2 and 4) in the lower data area 111L is moved to the free area side and extended data is stored ((f) in FIG. 1(C)).

[For production]

The operation of the present invention will be explained by taking as an example a case where four pieces of data 1 to 4 are stored in the fixed data area 111, and then some of these data are deleted and expanded.

When performing data 1 to 4 in this order alternately starting from the top of the free area of the fixed data area 111,
As shown in a), data 1 and 3 are stored in the upper data area 111U, and data 2 and 4 are stored in the lower data area 111L.

When performing alternately starting from the lower part of the free space in the fixed data area 111, the upper data area 1
Data 2 and 4 are stored in 1IU, and data 1 and 3 are stored in lower data area 111L. By doing this, free space is always available in the fixed data area 11.
It is formed in the center of 1.

When deleting data, when the data in the upper data area 111U (for example, data 1) is deleted, the entire data of the data in the upper data area 111U below it (for example, data 1) is deleted.
In this case, move data 3) upward to fill up the free space of deleted data 1 ((B) in Figure 1) and (C)
)). If data 3 is deleted, the data is not moved because it is unnecessary.

Data in the lower data area 1llL (for example, data 2)
When you delete , the lower data area 11 above it
The data 4 in 1L is moved downward to fill up the free space of the deleted data 2 (see FIG. 1(B) corner) and FIG. 1(d)). If data 2 is deleted, the data is not moved because it is unnecessary.

By doing so, even when data is deleted, the free space is formed in the center of the fixed data area.

When expanding data, when expanding the data (for example, data 1) in the upper data area 111U, the entire data (data 3) in the upper data area 111U below it is expanded.
) to the free area side and store extended data 1' (
(See (e) in (C) of Figure 1). If you expand data 3, the expanded data will be stored in the free space,
No data movement occurs.

Data in the lower data area 111L (for example, data 2)
When expanding data 2', it moves itself (data 2) and all the data in the lower data area 111L above it (data 2 and 4) to the free area and stores expanded data 2' (see Figure 1). (See C) (f)). If data 4 is expanded, only data 4 is moved to the free area side.

By doing this, even when the data is expanded, the free area is formed in the center of the fixed data area.

When storing and expanding data, if the necessary free space is insufficient, delete the least usable data (for example, the oldest data) using the same process as the deletion described above to free up the necessary free space. After securing the data, store or expand the data.

By combining data storage, deletion, and expansion processing, you can store variable-length data in any number of partitions.

Can be deleted and expanded. For example, by combining storage and expansion processing, continuous variable length data can be collectively stored in a continuous area on a fixed data area.

As described above, each piece of data is arranged in the fixed data area 111 so that the free space is always formed in a group, so the presence or absence of the free space required when storing and expanding data is quickly detected, and the necessary free space is quickly detected. This makes it possible to quickly secure free space with a small amount of data movement. Furthermore,
The number of page faults is reduced, and in combination with the above, the processing time required for data storage and expansion can be shortened.

〔Example〕

Embodiments of the present invention will be described with reference to FIGS. 1 to 5. FIG. 2 is an explanatory diagram of the configuration of an implementation system according to an embodiment of the present invention, FIG. 3 is a processing flowchart when storing data in the same embodiment, FIG. 4 is a processing flowchart when deleting data in the same embodiment, and FIG. FIG. 5 is a processing flowchart at the time of data expansion in the same embodiment.

(A) Configuration of Implementation System In FIG. 2, reference numeral 11 denotes a memory, which includes a fixed data area 111 with a fixed capacity, a data management table 112, and a free space management table 113.

The upper half of the fixed data area 111 is the upper data area 111
U, and the lower half is a lower data area 111.

The data management table 112 contains data 1. A flag F indicating whether each data such as data 2 exists in the fixed data area 111 (ON when it exists, 0FF when it does not exist) and whether the data is in the upper data area 111U
flag F2 indicating whether it is in the lower data area or in the lower data area 111L (UP in the former case, DOW in the latter case)
N), the data length and position AD are registered for each table.

The space management table 113 includes an up/down counter (U/DCNT) and the total number of spaces SPN.

Start position ADS of free area and final position A of free area
DSr is registered. Storing and deleting data.

All processing such as expansion is performed in units of sections of a fixed size (number of bytes), and the total number of free spaces SPN is indicated by the total number of free space partitions. When one section of data is stored in the upper data area 111U, U/D CN T becomes "1".
', and each time one block is deleted or evicted, '1
' will be increased by '. Conversely, when one section of data is stored in the lower data area 111L, it is incremented by "1", and every time one section is deleted or evicted, it is decremented by "71".

The initial value of U/DCNT is set to "0", and the value is "
When the value is greater than or equal to 0 (≧0), data is stored from the top side, and when it is less than 0, data is stored from the bottom side.

12 is a memory management control unit, which includes a data management table 112;
Processes such as storing, deleting, and expanding data in the fixed data area 111 are performed with reference to the free space management table 113 and data management table 112 is performed based on the processing results.
and performs processing to update the contents of the free space management table 113.

13 is a data output control unit, and a disk 14A.

This is done by human output control such as storing and retrieving data for 14B, 14C, etc. Data is stored in units of bytes.

(B) Operation of the embodiment The operation of the embodiment is performed when four pieces of data (data 1 to 4) are stored as shown in Figure 1, and some of the stored data is further deleted and expanded. Taking this as an example, the processing steps will be explained with reference to the processing flowcharts of FIGS. 3 to 5.

(1) Data storage operation Referring to FIG. 3, data 1 to 1 are stored in fixed data area 111.
4 will be stored in this order from the top side as an example.

(2) Processing S Il+ S+2+ sla The memory management control unit 12 refers to the free space management table 113 and determines whether there is free space that can store data 1 (on the disk 14A) (Sz).

If there is no free space available for storage, the oldest data is evicted to secure an area for storing data 1.

Note that this expulsion process is performed in the same way as the data deletion process described in (2) below, and the expelled data is stored on the original disk (3, 2).

When the free space for storing data l is confirmed, the free space for storing data 1 is checked by referring to U/D CN T in the free space management table 13.
It is determined whether the directness is "0" or more (≧0). First, U/
It is assumed that the value of DCNT is "0".

■ Processing S14+ S16+ sat processing S13
Since the value of U/DCNT is "0", data 1 is stored in the upper data area 111U side. In this case, the first position ADS of the free area is allocated, and U/DCNT
The value of is decreased by "1" and updated to "-1" (S
14).

When the above processing is completed, the memory management control unit 12 sends the data storage position (starting position ADS) to the data input/output control unit 13.
, ') to instruct storage of data 1.

The data input/output control unit 13 retrieves data 1 for one partition from the disk 14A, and stores it at the starting position of the free area A D S
, that is, it is stored in the upper part of the free area (31g, the first
(See (a) in Figure (A)).

When data 1 is stored, the memory management control unit 12 reduces the total number of free spaces SPN in the free space management table 113 by the amount of stored data, that is, "1", and updates the value of the start position ADS. Furthermore, the contents of the data management table 112 are updated, flag F of data 1 is set to "ON", and flag F2 is set to "ON".
Set it to “UP” and register the length and position of data 1 (S
, t).

■ Storage and processing of data 2 Sll to S l 3 *
When data 2 (on the disk 14B) is to be stored next to SI S to S17, the processing of S to SI3 is performed in the same manner as in the case of data 1 described above. This time U/DC
Since the value of NT is "-1" which is smaller than "0", data 2
is stored in the lower data area IILL side of the free area.

In this case, the final position ADS of the free area is allocated, and the value of U/DCNT is incremented by 1 and updated to "0" (S,...).

Hereinafter, in the same manner as in the case of data 1 described above, S, 6 to SI
7 is performed, data 2 for one section is taken out from the disk 14B, and stored in the final position of the free space ADSR, that is, at the bottom of the free space ('l:116+
(See (a) in FIG. 1(A)).

Next, the total number of vacancies in the vacancy management table 113 is decreased by 1, and the value of the final position ADSr is updated. Furthermore, update the contents of the data management table 112, set flag F of data 2 to "ON", and set flag F2 to r D OW N J
and register the length and position of data 2.

In the same manner, data 3 and data are stored in the upper and lower sides of the free space of the fixed data area 111 as shown in FIG. 1(A).
The data are stored alternately as shown in (a).

(2) Data deletion operation Taking the case of deleting data 1 or 2 from data l to 4 stored in the fixed data area 111 as an example, the data deletion operation will be explained with reference to the processing flowchart in FIG. Explain according to the following.

■ Processing S21 When deleting data 1 in the upper data area 111U of the fixed data area 111, the memory management control unit refers to the data management table 112 and outputs the length and position of data 1! 11 Department 13 will be notified. Upon receiving this notification, the data input/output control unit 13 reads data l from the fixed data area 111 and returns it to the disk 14A.

■ Processing S 221 S 2! , S 2% The memory management control unit 12 refers to the data management table 112 and determines whether the flag F2 of the deleted data 1 is rUPJ or rDO
Determine whether it is WNJ (32□). Since the flag F2 of data l is rUPJ, the memory management control unit 12 moves data 3 below data 1 in the upper data area 1lIU upward. (S23. See (b) and (C) in Figure 1 (B)). If data 3 is deleted, the data is not moved because it is unnecessary.

When the above processing is completed, the memory management control unit 12 increases the total number of free spaces SPN in the free space management table 113 by the amount of deleted data, updates the value of U/DCNT and the starting position of free space ADS, and further, Data management table 112
The contents of are updated and the flag F of data 1 is set to rOFFJ.

■ Processing S21 ``'' S2□, 824-S2S When deleting the data 2 in the lower data area 111L of the fixed data area 111, perform the processing of Sol and S22 in the same way as in the case of the data l described above, Delete data 2 and return it to the disk 14B, refer to the data management table 112, and check whether flag F2 of data 2 is rUP or 'DOWN.
4.

Since the flag F2 of data 2 is r D OW N J, the memory management control unit 12 moves data 4 in the lower data area 111L above data 2 downward,
Fill up the free space of deleted data 2 (S24 +
(See (b) and (d) in Figure 1 (B)).

If data 4 is deleted, the data is not moved because it is unnecessary.

When the above process is completed, the memory management control unit 12 increases the total number of free spaces SPN in the free space management table 113 by the amount of deleted data, and updates the value of U/DCNT and the final position of free space ADSR. . Furthermore, the contents of the data management table 112 are updated, and the flag F of data 2 is set to rOF.
Make it FJ (Sas).

(3) Data extension operation Taking the case of extending data 1 or 2 from data 1 to 4 stored in the fixed data area 111 as an example, the data extension operation will be explained with reference to the processing flowchart in FIG. Explain according to the following.

■ Processing Ss+ to S34 When expanding data 1 in the upper data area 111U of the fixed data area 111, the memory management control unit 12 refers to the free space management table 113 to determine if there is a free area in which data 1 can be expanded. (331).

If there is no free space available for expansion, the oldest data is removed 5) to secure an area for expanding data l.

This expulsion process is performed in the same manner as the data deletion process described above (S32).

When free space is secured to expand data 1, data 1
It is determined whether the next area is free (S33). In the case of data 1, the next area contains data 3, so it is not empty.

If the area next to data 1 is not empty, refer to flag F2 in the data management table 112 and determine whether flag F2 of data 1 is rUPJ or "D○WNJ" (S3
4). The flag F2 of data 1 is rUPJ, and it is determined that data 1 is on the upper data area 111U side.

■ Processing S 35. S36 The memory management control unit 12 moves the entire data in the upper data area 111U below the data l, that is, data 3, by one section to the free area side, and expands data 1 to extended data 1'.
The data input/output control section 13 is notified of the location by securing one section of storage area. Upon receiving this notification, the data person output control unit 13 takes out one section of extended data 1' of data 1 from the disk 14A, and extracts it from the fixed data area 111.
Store extended data 1' in the notified location (S)
s s + see (e) in Figure 1 (C)).

When data 1' is stored, the memory management control unit 12
The contents of the free space management table 13 are updated and the total number of free spaces S is
PN is decreased by the data amount of extended data 1', that is, "1", the value of U/DCNT is decreased by "1", and the value of the free area start position ADS is increased by "1". Furthermore, the contents of the data management table 112 are updated and the length of data 1 is increased by "l" (SAT).

If data 3 is expanded, there is a free area next, so the processes in S34 and S35 are unnecessary, and the process in S3t is performed immediately from process 333, and the free space management table 113 and data management table 112 are The contents of will be updated.

■ Processing S3+ to S34+ S36 to S37 When expanding data 2 in the lower data area 111L'' of the fixed data area 111, the processing in S31'' and S34 is performed in the same manner as in the case of data 1 described above. data 2
There is no free space after , and the flag F2 is r
Since it is DOWNJ, it is determined that it is on the lower data area 111L side.

The memory management control unit 12 moves the entire data in the lower data area 111L above it, including the data 2 itself, that is, the entire data 2 and data 4, to the free area side, and reduces the storage area of the extended data 2' of the data 2 to 1. The partition is secured and its position is notified to the data input/output control unit 13. Upon receiving this notification, the data input/output control unit 13 takes out one partition of the extended data 2' of data 2 from the disk 14B and stores the extended data 2' in the fixed data area 111 at the notified position.
(S3°, see (f) in FIG. 1(C)). Note that when data 4 is expanded, only data 4 is moved by one section to the free area side, and one section of expanded data of data 4 is stored there.

When the data 2' is stored, the memory management control unit 12
Update the contents of the free space management table 13, reduce the total number of free spaces SPN by "1", and change the value of L'/DCNT to "1".
'', and the value of the final free area A D S r is increased by ``
Decrease by 1. Furthermore, the contents of the data management table 112 are updated and the length of data 2 is increased by “1” (S, ,
).

Data storage, deletion, and expansion are performed in units of sections, but by combining these processes, arbitrary variable length data can be stored, deleted, and expanded. For example, by combining storage and expansion processing, continuous data consisting of multiple sections can be collectively stored in a continuous area on a fixed data area.

〔Effect of the invention〕

As explained above, according to the present invention, the following effects can be obtained.

(1) Since each data is arranged so that the free space is always formed in the center of the fixed data area, the presence or absence of the necessary free space is quickly detected when storing and expanding data, and the necessary free space is can be quickly secured with a small amount of data movement.

(2) The number of page faults is reduced, and in combination with (1) above, the processing time required for data storage and expansion can be shortened.

[Brief explanation of the drawing]

Fig. 1 is a diagram of the principle of the present invention; Fig. 2 is an explanatory diagram of the configuration of an implementation system of an embodiment of the present invention; Fig. 3 is a processing flowchart during data storage of the embodiment; Fig. 4 5 is a processing flowchart for data deletion according to the same embodiment. FIG. 5 is a processing flowchart for data expansion according to the same embodiment. FIG. 6 is an explanatory diagram of a conventional memory management system. 1 and 2, 11...memory, 111...fixed data area, 11
1U... Upper data area, 111L... Lower data area, 112... Data management table, 113...
Free space management table, 12...Memory management control unit, 13
...Data input/output control unit, 14A to 14C...Disk, U/DCNT...Up/down counter.

Claims (2)

[Claims] (1) Fixed data area with fixed memory capacity (1
11) In the memory management method for storing, deleting, and expanding multiple pieces of variable length data, (A) when storing data, data is stored alternately up and down from the upper or lower side of the fixed data area (111). (B) When deleting data, the upper data area (111
When data in U) is deleted, all the data in the upper data area (111U) below it is moved upward to fill up the free space of the deleted data, and the data is moved to the lower data area (111U).
111L), move the entire data in the lower data area (111L) above it downward to fill the free space of the deleted data. Data area (111
When expanding the data in the lower data area (111L), move the entire data in the upper data area below it to the free area, store the expanded data, and expand the data in the lower data area (111L). A memory management method is characterized in that the entire data in the lower data area (111L) above itself and the lower data area (111L) is moved to the free area side and extended data is stored therein. (2) Provide an up/down counter (U/DCNT), and if the value is greater than the initial value, the upper (or lower)
Store data in the data area and decrease (increase) the value of the up/down counter by the amount of data stored, and if the value is smaller than the initial value, store the data in the lower (or upper) data area and upload it. 2. The memory management system according to claim 1, wherein the value of the down counter is increased (decreased) by the amount of stored data, and the data is stored alternately in the upper and lower directions.