JP2688039B2 - Memory management device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] A memory management device for storing, deleting, and expanding a plurality of variable-length data in a fixed data area on a memory. When storing data in a memory management device that stores, deletes, or expands variable-length data in a fixed data area on the memory for the purpose of efficiently forming and storing and expanding the data with a small amount of data movement. Is stored alternately from the top or bottom of the fixed data area, and when deleting data, above (below) the fixed data area
When deleting data on the department side, move the data upward (down) to fill the empty area of the deleted data, and when expanding the data on the upper (lower) side, it is necessary under the data. In order to create a free area, other data is moved to the free area side to store the extended data, and the free area is always formed in the central portion of the fixed data area. BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a memory management device for storing, deleting and expanding a plurality of variable length data in a fixed data area having a fixed memory capacity. [Prior Art] 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 temporarily loaded onto a 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, the memory has a limited capacity, the data has a variable length, and must be stored in a continuous area.
There is a condition such that the data area is not reduced but expanded. Under these conditions, memory management is performed so that the above-mentioned processes (1) to (3) are favorably performed. FIG. 6 is a block diagram showing a conventional memory management system. In FIG. 6, reference numeral 21 denotes a memory, which includes a fixed data area 211, a data management table 212, and a free space management table 213 each having a fixed capacity. The fixed data area 211 has areas such as data 1, 3, 4 and vacant areas a to c. In the data management table 212, a data area 211 in which each data such as data 1 and data 2 is fixed
A flag indicating whether it exists above (ON when it exists,
If it does not exist, it is OFF), the registration pointer of each existing data, and the data length and position of each data are registered. The length and position of each free area on the fixed data area 211 are registered in the free space management table 213. Reference numeral 22 denotes a memory management control unit, which refers to the data management table 212 and the free space management table 213 to perform processing such as data storage, deletion, and expansion in the fixed data area 211, and based on the processing result, the data management table 212 and Processing for updating the contents of the free space management table 213 is performed. A data input / output control unit 23 performs input / output control such as data storage and retrieval for the disks 24A, 24B, 24C.
Data is input / output processed in units of several Kbytes. 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 to determine whether there is a free space in which the data 5 can be stored. To do. If it exists, the data input / output control unit 23 takes out the data 5 from the disk 24A and stores the data 5 in the empty area. If there is not enough free space, rearrangement is performed so that the free spaces a, b, and c are continuous to secure a free space for storing the data 5, and then the data 5 is transferred from the disk 24A by the data input / output control unit 23. It is taken out and stored in the empty area. Further, the contents of the data management table 212 and the free space management table 213 are updated corresponding to the storage of the data 5. If sufficient free space cannot be secured only by relocating the free space, the oldest data is sequentially ejected to secure the necessary free space. When deleting data (for example, data 2) in the fixed data area 211, the memory management control unit 22 deletes the data 2 from the fixed data area 211 and then deletes the contents of the data management table 212 and the 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 to determine whether there is a free space next to the data 1 that can store extended data. To do. When the space a next to the data 1 shown in the figure can store the extension data of the data 1, the extension data is stored in the space a.
When the extended data cannot be stored only with the empty a, the rearrangement is performed so that the empty b or the empty c is continuous to a, the length of the extended data is secured, and then the extended data is stored following the data 1. . Further, the contents of the data management table 212 and the free space management table 213 are updated corresponding to the storage of the extended data. If sufficient free space cannot be secured only by rearranging the free space, the oldest data is sequentially ejected to secure the required free space. [Problems to be Solved by the Invention] As described above, the conventional memory management device randomly arranges the data area and the empty area in the data fixed area, and uses the data management table and the empty management table for each data. The area and the empty area are managed, and the data area and the empty area are rearranged and data is expelled in order to secure the data area necessary for storing and expanding the data. However, since the data area and the empty area are arranged irregularly, it is necessary to move a large amount of data when rearranging, and it takes time to store and expand the data, which complicates the processing. There was a problem. Also,
If there is a large amount of small free space, a page fault will occur easily, and from this point as well, there is a problem that data storage and expansion processing cannot be performed efficiently. The present invention is an improved memory in which each data is arranged in a fixed data area so that a vacant area is formed in a central portion, and data can be stored and expanded efficiently with a small amount of data movement. The purpose is to provide a management device. [Means for Solving the Problems] The solving means adopted by the present invention will be described with reference to the principle diagram of FIG. In FIG. 1, 111 is a fixed data area whose capacity is fixed, and the upper half is the upper data area.
111U, the lower half is the lower data area 111L. When data is stored, it is stored alternately from the upper side or the lower side of the empty area of the fixed data area 111 (first
(A) of FIG. When deleting data, if the data in the upper data area 111U (for example, data 1) is deleted, the entire data (data 3) in the upper data area 111U below it is moved upward and deleted. Of the lower data area 111L when data (for example, data 2) in the lower data area 111L is deleted by filling the empty area ((b) and (c) in FIG. 1B). The entire data (data 4) is moved downward to fill the empty area of the deleted data ((b) and (d) in FIG. 1 (B)). When expanding data, when expanding the data (for example, data 1) in the upper data area 111U, the entire data (data 3) in the lower upper data area 111U is moved to the free area side and expanded. Store the data (Fig. 1 (C)
(E)), when expanding the data (for example, data 2) in the lower data area 111L, the entire data (data 2 and 4) in itself and the lower data area 111L above it is moved to the free area side. Then, the extended data is stored ((f) in FIG. 1 (C)). [Operation] The operation of the present invention will be described by taking as an example the case where four data 1 to 4 are stored in the fixed data area 111 and then a part of these data is deleted and expanded. When the data 1 to 4 are alternately performed in this order from the upper side of the empty area of the fixed data area 111, as shown in (a) of FIG. 1A, the data 1 is stored in the upper data area 111U.
And 3 are stored, and data 2 is stored in the lower data area 111L.
And 4 are stored. When performing alternately from the lower side of the free area of the fixed data area 111, as shown by the numbers in parentheses, the upper data area 111U stores data 2 and 4, and the lower data area 111L stores data 1 and 3 is stored. By doing so, the empty area is always formed in the central portion of the fixed data area 111. When deleting data, if 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 (data 3 in this case) is moved upward. Then, the empty area of the deleted data 1 is filled ((b) and (c) of FIG. 1B). If the data 3 is deleted, the movement of the data is not necessary and therefore it is not performed. When the data (for example, data 2) in the lower data area 111L is deleted, the data 4 in the lower data area 111L above the lower data area 111L is moved downward to fill the empty area of the deleted data 2 (see FIG. 1 ( (B) (b) and (d)).
If the data 2 is deleted, the data movement is not necessary and is not performed. By doing so, even when the data is deleted, the empty areas are collectively formed in the central portion of the fixed data area. When expanding data, when expanding the data in the upper data area 111U (for example, data 1), the entire data (data 3) in the lower upper data area 111U is moved to the free area side and expanded. Data 1'is stored (see (e) in FIG. 1C). If the data 3 is expanded, the expanded data is stored in the empty area as it is and the data is not moved. When expanding the data (for example, data 2) in the lower data area 111L, the whole data (data 2 and 4) in itself (data 2) and the lower data area 111L above it (data 2 and 4)
To the free area side to store the extended data 2 '(see (f) in FIG. 1 (C)). If the data 4 is expanded, only the data 4 is moved to the free area side. By doing so, even when the data is expanded, the empty areas are collectively formed in the central portion of the fixed data area. If the required free space is insufficient due to data storage and expansion, the data with the lowest availability (for example, the oldest data) is expelled by the same process as the deletion described above, and the required free space is removed. After securing the data, store or expand the data. By combining data storage, deletion, and expansion processing, it is possible to store, delete, and expand variable-length data of an arbitrary number of partitions. For example, by combining storage and expansion processing, continuous variable-length data can be collectively stored in a continuous area on the fixed data area. As described above, since each data is arranged on the fixed data area 111 so that the empty areas are always formed as a group, the presence or absence of the empty area necessary for storing and expanding the data is promptly detected and necessary. It is possible to quickly secure a large free area with a small amount of data movement. Furthermore,
The number of page faults is reduced, and combined with the above, the processing time required for storing and expanding data can be shortened. [Embodiment] An embodiment of the present invention will be described with reference to FIGS. 1 to 5. FIG. 2 is an explanatory diagram of a configuration of an implementation system of an embodiment of the present invention, FIG. 3 is a processing flowchart when storing data in the embodiment, and FIG. 4 is a processing flowchart when deleting data in the embodiment. FIG. 5 is a processing flowchart at the time of data extension of the embodiment. (A) Configuration of Implementation System In FIG. 2, reference numeral 11 denotes a memory, which includes a fixed data area 111 having a constant 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 111U, and the lower half is the lower data area 111L.
It is. In the data management table 112, a flag F ₁ indicating whether each data such as data 1 and data 2 exists in the fixed data area 111 (ON when it exists, OFF when it does not exist),
Flag F ₂ indicating whether the data is in the upper data area 111U or the lower data area 111L (UP in the former case,
In the latter case, DOWN), the data length L and the position AD are registered for each table. In the free space management table 113, the up / down counter (U / DCNT), the total free space SPN, the free space start position ADS _s, and the free space end position ADS _f are registered. Processing such as data storage, deletion, and expansion are all performed in units of fixed size partitions (several Kbytes), and the total number of free spaces SPN is indicated by the total number of free space partitions. U / DCNT is the upper data area
When one section of data is stored in 111U, it is decreased by "1" and increased by "1" every time one section is deleted or evicted. On the contrary, when one section of data is stored in the lower data area 111L, it is increased by "1" and is decreased by "1" every time one section is deleted or expelled. The initial value of U / DCNT is set to "0". When the value is "0" or more (≥0), the data is stored from the upper side, and when it is smaller than "0", the data is stored from the lower side. It Reference numeral 12 denotes a memory management control unit, which refers to the data management table 112 and the free space management table 113 to perform processing such as data storage, deletion, and expansion in the fixed data area 111, and based on the processing result, the data management table 112 and Processing for updating the contents of the free space management table 113 is performed. A data input / output control unit 13 performs input / output control such as storage and retrieval of data with respect to the disks 14A, 14B, 14C.
Data is recorded in units of blocks of several Kbytes. (B) Operation of the embodiment In the operation of the embodiment, four pieces of data (data 1 to 4) are stored as shown in FIG. 1, and a part of the stored data is deleted and expanded. Will be described with reference to the processing flowcharts of FIGS. 3 to 5 and the processing steps thereof. (1) Data storage operation Referring to FIG. 3, data 1 to data 1 are stored in the fixed data area 111.
The case where 4 is stored in this order from the upper side will be described as an example. The processes S ₁₁ , S ₁₂ , S _{13 The} memory management control unit 12 refers to the free space management table 113 and determines whether there is a free space in which the data 1 (on the disk 14A) can be stored (S ₁₁ ). If there is no free space that can be stored, the oldest data is swept out to secure an area for storing data 1. This eviction process is performed in the same manner as the process of deleting data described in (2) below, and the evict data is stored in the original disk (S ₁₂ ). When the free area for storing the data 1 is confirmed, the U / DCNT of the free management table 13 is referred to and it is determined whether the value is “0” or more (≧ 0). Initially, the value of U / DCNT is "0"
And Process S ₁₄ , S ₁₆ , S _{17 Since} the value of U / DCNT is “0” in process S ₁₃ , data 1
Is stored in the upper data area 111U side. In this case, assigned head position ADS _s free space, the value of U / DCNT is decremented by "1", - it is updated to "1" (S _14). When the above processing is completed, the memory management control unit 12 notifies the data input / output control unit 13 of the data storage position (start position ADS _s ) and instructs the data I / O unit to store data 1. The data input / output control unit 13 takes out one block of data 1 from the disk 14A and stores it in the head position ADS _{s of the} empty area, that is, at the upper side of the empty area (S ₁₆ , see FIG. 1A). ). When the data 1 is stored, the memory management control unit 12 reduces the total number of free spaces SPN of the free space management table 113 by the stored data amount, that is, “1”, and updates the value of the head position ADS _S.
Further, the contents of the data management table 112 are updated, the flag F _{1 of the} data 1 is set to “ON”, the flag F _{2 is set} to “UP”, and the length and position of the data 1 are registered (S ₁₇ ). Storing data 2, when storing processing S ₁₁ ~S _13, S ₁₅ following the data 2 to S ₁₇ (in disk 14B) is of S ₁₁ to S ₁₃ as in the case of data 1 above Processing is performed. Since the value of U / DCNT is "-1" and smaller than "0" this time, data 2 is stored in the lower data area 111L side of the empty area. In this case assigned final position ADS _f of free space, the value of U / DCNT is increased by 1, is updated to "0" (S _15). After that, the processing of S _{16 to} S ₁₇ is performed in the same manner as the case of the data 1 described above, one block of the data 2 is extracted from the disk 14B and stored in the final position ADS _{f of the} empty area, that is, the lower side of the empty area. (S ₁₆ ; see (a) of FIG. 1 (A)). Next, the total number of free spaces in the free space management table 113 is reduced by 1, and the value of the final position ADS _f is updated. Furthermore, the contents of the data management table 112 are updated, and the flag F _{1 of the} data 2 is set to “O
The flag F _{2 is set} to “DOWN” in “N”, and the length and position of the data 2 are registered. Similarly, the data 3 and the data are shown in FIG. 1 (A) on the upper side and the lower side of the empty area of the fixed data area 111.
(A) are stored alternately. (2) Data Deletion Operation Taking the example of deleting data 1 or 2 from the data 1 to 4 stored in the fixed data area 111, the data deletion operation will be described with reference to the processing flowchart of FIG. Follow the instructions below. Process S ₂₁ When deleting the 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 to determine the length and position of the data 1 in the data input / output control unit. Notify 13. Data input / output control unit 13
Upon receiving this notification, the data 1 reads the data 1 from the fixed data area 111 and returns it to the disk 14A. Processing S ₂₂ , S ₂₃ , S _{25 The} memory management control unit 12 refers to the data management table 112 and determines whether the flag F _{2 of} the deleted data 1 is “UP” or “DOWN” (S ₂₂ ), since the flag F _{2 of the} data 1 is “UP”, the memory management control unit 12 moves the data 3 below the data 1 in the upper data area 111U upward and deletes the data 1 The empty area of (S ₂₃ , see (b) and (c) of FIG. 1B). If the data 3 is deleted, the data movement is not necessary and is not performed. After the above processing is completed, the memory management control unit 12 increases the total number of free spaces SPN of the free space management table 113 by the deleted data amount and updates the value of U / DCNT and the free space start position ADS _s . Furthermore, the contents of the data management table 112 are updated, and the flag F _{1 of the} data 1 is set to “OFF”. Processing S _{21 to} S ₂₂ , S _{24 to} S ₂₅ When deleting the data 2 that is in the lower data area 111L of the fixed data area 111, the processing of S ₂₁ and S ₂₂ is performed as in the case of the data 1 described above. , The data 2 is deleted and returned to the disk 14B, and it is determined whether the flag F _{2 of the} data ₂ is “UP” or “DOWN” by referring to the data management table 112. Since the flag F _{2 of the} data 2 is “DOWN”, the memory management control unit 12 determines that the lower data area 11 above the data 2
The data 4 in 1L is moved downward to fill the empty area of the deleted data 2 (S ₂₄ , (b) and (d) in FIG. 1 (B)).
reference). If the data 4 is deleted, the data movement is not necessary and is not performed. When the above process is completed, the memory management control unit 12 increases the total number of free spaces SPN of the free space management table 113 by the deleted data amount and updates the value of U / DCNT and the final position ADS _f of the free space. Furthermore, to update the contents of the data management table 112, the flag F ₁ data 2 to "OFF" (S _25). (3) Data Expansion Operation Referring to the processing flowchart of FIG. 5, the data expansion operation will be described with reference to the processing flowchart of FIG. 5, taking the case of expanding the data 1 or 2 from the data 1 to 4 stored in the fixed data area 111 as an example. Follow the instructions below. Processing S _{31 to} S ₃₄ When expanding the data 1 in the upper data area 111U of the fixed data area 111, the memory management control unit 12 refers to the empty management table 113 and has a free area in which the data 1 can be expanded. It is determined whether or not (S ₃₁ ). If there is no free area that can be expanded, the oldest data is swept out and an area for expanding data 1 is secured.
This eviction process is performed in the same manner as the above-mentioned data deletion process (S ₃₂ ). When the empty area for expanding the data 1 is secured, it is determined whether the area next to the data 1 is empty (S ₃₃ ). In the case of data 1, the next area is not empty because it contains data 3. If the area next to the data 1 is not empty, it is determined whether the flag F _{2 of the} data 1 is “UP” or “DOWN” by referring to the flag F ₂ of the data management table 112 (S ₃₄ ). The flag F _{2 of the} data 1 is “UP”, and it is determined that the data 1 is on the upper data area 111U side. Processes S ₃₅ and S _{36 The} memory management control unit 12 moves the entire data in the upper data area 111U below the data 1, that is, the data 3 by one partition to the free area side, and the extended data 1'of the data 1 The storage area for one section is secured and the position is notified to the data input / output control unit 13. Upon receiving this notification, the data input / output control unit 13 extracts one section of the extended data 1'of the data 1 from the disk 14A and stores the extended data 1'in the notified position of the fixed data area 111 ( _S35). , (E) of FIG. 1 (C)). When the data 1'is stored in the memory management control unit 12,
Update the contents of free space management table 13 and total the free space SPN
Is reduced by the data amount of the extension data 1 ′, that is, “1”, the value of U / DCNT is reduced by “1”, and the value of the start position ADS _s of the empty area is increased by “1”. Further, the contents of the data management table 112 are updated, and the length of the data 1 is increased by "1" ( _S37 ). If the data 3 is to be expanded, the next free space exists, so the processes of S ₃₄ and S ₃₅ are unnecessary, and the process of S _{33 is performed.}
Immediately _thereafter, the processing of S ₃₇ is performed, and the contents of the free space management table 113 and the data management table 112 are updated. Processing _{S 31 ~S 34, S 36 ~S} 37 when extending data 2 in the lower data area 111U fixed data area 111, as in the case of data 1 described above, the processing of S ₃₁ to S ₃₄ Since there is no free area next to the data 2 and the flag F ₂ is “DOWN”, it is determined that the area is on the lower data area 111L side. The memory management control unit 12 moves all the 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 sets the storage area of the extended data 2'of the data 2 to 1 A section is secured and the position data input / output control unit 13 is notified. Data input / output control unit
Upon receiving this notification, the 13 takes out one section of the extended data 2'of the data 2 from the disk 14B, and the fixed data area
The extension data 2'is stored in the notified position of 111 ( _S36 , see (f) of FIG. 1 (C)). When the data 4 is expanded, only the data 4 is moved to the free space side for one partition, and one partition of the expanded data of the data 4 is stored therein. When the data 2'is stored, the memory management control unit 12
The contents of the free space management table 13 are updated, and the total free space SP
Decrease N by "1" and increase U / DCNT value by "1"
Decrease the value of the last ADS _{f in} the free area by "1". Furthermore,
The contents of the data management table 112 are updated, and the length of the data 2 is increased by "1" ( _S37 ). Data storage, deletion, and expansion are done in units of partitions,
By combining these processes, it is possible to store, delete, and expand arbitrary variable-length data. For example,
By combining storage and expansion processing, it is possible to collectively store continuous data composed of a plurality of sections in a continuous area on the fixed data area. [Effects of the Invention] As described above, according to the present invention, the following effects can be obtained. (1) Since each data is arranged such that the empty area is always formed in the central portion of the fixed data area, the presence or absence of the empty area required for storing and expanding the data is promptly detected, and the required empty area It is possible to quickly secure a small amount of data with a moving amount. (2) The number of page faults has been reduced,
Combined with this, the processing time required for storing and expanding data can be shortened.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a principle diagram of the present invention, FIG. 2 is an explanatory diagram of a configuration of an implementation system of an embodiment of the present invention, and FIG. 3 is a data storage time of the embodiment. FIG. 4 is a process flowchart for deleting data in the embodiment, FIG. 5 is a process flowchart for expanding data in the embodiment, and FIG. 6 is an explanatory diagram of a conventional memory management method. is there. 1 and 2, 11 ... Memory, 111 ... Fixed data area, 111U ... Upper data area, 111L ... Lower data area, 112 ... Data management table, 113 ... Vacancy management table, 12 ...... Memory management control unit, 13 ...... Data input / output control unit, 14A to 14C ...
... disk, U / DCNT ... up / down counter.

Claims (1)

(57) [Claims] In a memory management device that manages an unused area by storing, deleting, and expanding data in a memory having a fixed capacity, the data is stored in the upper side and the lower side of the memory when storing the data in the memory. Data storage means for storing data so that the data areas are substantially equal, and when deleting data from the memory, when the deleted data is the upper side area, the data in the upper side area below the deleted data is moved upward. To delete the deleted data area, and if the deleted data is the lower area, move the data in the lower area above the deleted data to the lower area to fill the deleted data area. A memory management device characterized by being provided. 2. When expanding the data to the memory, if the expanded data is the upper area, the data in the upper area below the area to be expanded is moved to the free area side to store the expanded data, and the expanded data is stored in the lower area. 2. The memory management device according to claim 1, further comprising a data expansion means for moving data in a lower area above the area to be expanded to an empty area and storing the expanded data in the case of an area. 3. 2. The data storage means stores the data in the memory such that the numbers of data stored in the upper side and the lower side of the memory are substantially equal when storing the data in the memory. Alternatively, the memory management device described in 2. 4. An unused area management table in which the start position and the end position of the empty area are recorded is provided, and when the data storage means stores data in the memory, the unused area management table is moved downward from the start position or from the end position of the unused area management table. When the storage area is allocated so that the data areas stored above are substantially equal and the start position or the final position of the unused area management table is updated, and the data deleting means deletes the data from the memory, If the deleted data is in the upper area, the data in the upper area below the deleted data is moved upward to fill the data area and update the start position of the unused area management table. In the case of an area, the data in the lower area above the deleted data is moved downward to fill the data area and the unused area management table Memory management device according to claim 1, 2 or 3, characterized in that updating the final position, and so.