JP3610528B2 - Memory management method and apparatus - Google Patents

Description

[0001]
[Industrial application fields]
The present invention relates to a memory management method and apparatus for managing a memory mounted on an information processing device such as a personal computer or a printer.
[0002]
[Prior art]
Conventionally, memory management in information processing devices such as personal computers and printers basically involves allocating a memory area corresponding to the program size requested by the application program, changing the size of the allocated area, and releasing the allocated area. Processing is performed in the memory space possessed.
[0003]
A conventional memory management method will be described with reference to FIGS. Here, a memory management method (hereinafter referred to as a dynamic memory management method, and the allocated area is referred to as an area having a dynamic attribute) capable of moving the allocated area in the memory space will be described. In a continuous memory area 100 of a memory such as a RAM allocated to the application program, as shown in FIG. 11A, areas D1, D2, D3, D4 (each size is set to SD1 in the order from the lower address to the higher address). , SD2, SD3, and SD4) have been allocated, and areas F1, F2, F3, F4, and F5 (each size being SF1, SF2, SF3, SF4, and SF5) are free. If there is an area allocation request of size SD5 from the application program, the size SD5 is compared with the sizes of the free areas F1 to F5 (SF1 to SF5). As a result, if the size SF4 of the area F4 is sufficient to secure the area of the size SD5, as shown in FIG. 11B, a program of the size SD5 is assigned to the area F4, this area is designated as D5, and the remainder of the area F4. The free space is F6 (size SF6 = SF4-SD5).
[0004]
However, the size SD5 of the area to be allocated is compared with the size of each of the free areas F1 to F4. If sufficient area is not found, the already allocated areas D1 to D4 are moved to the lower address side. Thus, as shown in FIG. 11 (c), a new empty area F7 (size SF7 = SF1 + SF2 + SF3 + SF4 + SF5) is created, and an area of size SD5 is allocated to the empty area F7. As shown in d), this is assumed to be D5, and the remaining free area by assigning D5 is assumed to be F8 (size SF8 = SF7-SD5).
[0005]
Further, when the size of the allocated area D2 in the state of FIG. 11A is expanded from SD2 to SD2L, for example, if SD2L> SD2 + SF3 and SD2L ≦ SD2 + SF3 + SF4, then FIG. As shown in FIG. 11F, an empty area F9 is created by moving the area D3 in the upper address direction, that is, the area D4 side. As shown in FIG. 11F, an area of size SD2L is newly created by expanding the area D2. assign. Further, in the case of SD2L> SD2 + SF1 + SF2 + SF3 + SF4 and SD2L> SD2 + SF1 + SF2 + SF3 + SF4 + SF5 in the state shown in FIG. 11 (a), first, FIG. 11 (g) As shown in FIG. 11 (h), the areas D1 and D2 are moved in the lower address direction, and the areas D3 and D4 are moved in the upper address direction, thereby creating a continuous free area F11. D2L, which is an enlarged version of D2, is newly allocated, and the free space remaining by allocating D2L is defined as F12. When the area D2 is released in the state of FIG. 11A, a new continuous free area F13 (size SF13 = SF2 + SD2 + SF3) is created as shown in FIG. 11I.
[0006]
[Problems to be solved by the invention]
However, in the conventional memory management method as described above, when all areas are allocated with a dynamic attribute that can be moved to the application program, a new memory management method is used until the total free area of the memory becomes zero. However, the allocated area may be allocated with a static attribute that cannot be moved in the memory space due to the efficiency of processing in the program. For example, as shown in FIG. 11A, the programs have already been assigned to the areas D1, D2, D3, and D4, and the areas F1, F2, F3, F4, and F5 are free. It is assumed that the area D3 is assigned with a static attribute that cannot be moved. At this time, if the request to increase the size of D2 from SD2 to SD2L is made, the area D3 cannot be moved despite SD2L> SD2 + SF1 + SF2 + SF3 + SF4 + SF5. The empty area F11 as shown in FIG. 11 (g) cannot be created. Therefore, it is impossible to increase the size of D2. That is, if an area having a static attribute that cannot be moved exists in the vicinity of the center of the memory space, a new memory allocation or a change in allocation size may not be possible even though there is a sufficient free area. In addition, due to the disadvantages described above, there have been problems that the frequency of movement of allocated programs increases, or that the stored programs are fragmented and the free space in the memory space cannot be used efficiently.
[0007]
The present invention has been made to solve the above-described problems, and in one continuous memory space, the allocation area to the memory space is separated by the difference in the static or dynamic allocation attribute of the area. Accordingly, it is an object of the present invention to provide a memory management method and apparatus capable of improving the use efficiency of the memory and efficiently allocating a new area of the memory free area and changing the size of the allocated area.
[0008]
[Means for Solving the Problems]
In order to achieve the above object, the memory management method of the invention of claim 1 is a memory management method capable of performing two memory managements in one continuous memory space. The memory space is managed in units of a predetermined size unit and is not relocated due to new allocation of other areas or size changes of other areas, and the size of the area allocated to the application program Is a first memory management method for performing static memory management set to an integral multiple of the unit block, and an area already allocated to the application program is a new allocation of another area or a size change of another area. Second memo that performs dynamic memory management that may be relocated with the move The first memory management method allocates an allocation area in units of the unit block from one end of the memory space, and the second memory management method allocates from the other end of the memory space. Area The first memory management method issues a request for ordering the area to the second memory management method when there is no free block necessary for executing new allocation or size change. The second memory management method is in response to a request for tidy area from the first memory management method. The allocated area is moved and arranged so as to close the other end side.
According to a second aspect of the present invention, there is provided a memory management device capable of managing two memories in one continuous memory space, wherein an area already allocated to an application program is newly allocated to another area. Alternatively, the memory space is not rearranged along with the size change of other areas, and the memory space is managed in units of a predetermined size unit, and the size of the area allocated to the application program is the size of the unit block. The first memory management means for performing static memory management set to an integral multiple and the area already allocated to the application program are moved and rearranged as new areas are newly allocated or other areas are resized. Second memory management means for performing dynamic memory management Said first memory management unit, the place allocated area from one end of the memory space in units of the unit block, the second memory management unit may allocate a region from the other end of the memory space The first memory management means issues a request for ordering the area to the second memory management means when there is no free block necessary for executing new allocation or size change, The second memory management means responds to an area order request from the first memory management means. The allocated area is moved and arranged so as to close the other end side.
[0009]
[Action]
In the memory management method or apparatus according to claim 1 or 2, the first memory management method or means for performing static memory management in response to a memory allocation request from an application program is a memory space The second memory management method or means for allocating the allocation area from one end to the unit block as a unit and performing dynamic memory management allocates the allocation area from the other end of the memory space. Deploy. The first memory management method or means issues a request for ordering the area to the second memory management method or means when there is no free block necessary for executing new allocation or size change. The second memory management method or means responds to the request for ordering the area from the first memory management method or means. The allocated area is moved and arranged so as to close the other end side. As a result, it is possible to efficiently allocate a new area of the memory free area and change the size of the allocated area, and the area size allocated to the application program is an integral multiple of the unit block. As a result, the subdivided areas are not scattered in the memory space and a large free area cannot be created, and the subdivision of the memory space is suppressed, the memory management can be performed efficiently, and the large free area can be saved. Can be secured.
[0010]
[0011]
【Example】
Hereinafter, an embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a schematic block diagram when the memory management device of this embodiment is mounted on a printer controller. The memory management device is mounted on the printer controller 3 that processes a print command sent from the host computer 1 and transfers the processed print image to the printer engine 2. The memory management method according to the present invention is the entire printer controller 3. It is executed by the CPU 4 that controls the above. In addition to the CPU 4, the printer controller 3 includes a ROM 5 that stores a control program for controlling the printer engine 2 and font data, a RAM 6, and an input / output interface 7 that communicates with an external device such as the host computer 1. The printer engine interface 8 communicates with the printer engine 2 and the bus 9 interconnects them.
[0012]
In the memory management device configured as described above, the CPU 4 manages the memory area of the RAM 6 based on the memory management program included in the printer control program stored in the ROM 5, and in the memory space of the RAM 6 in response to a request from the printer control program. Allocate space. For example, an area as a reception buffer for temporarily storing print data sent from the host computer 1 or an area for storing intermediate data generated during processing of print data is assigned to the static attribute area to temporarily Font data stored (cached) is allocated to the dynamic attribute area.
[0013]
FIG. 2 is a diagram showing the concept of the storage area of the RAM 6 in FIG. The memory assumes a continuous memory space 60. In the memory space 60, the lowest address is MemLoEnd 61, the highest address is MemHiEnd 62, an area having a static attribute is assigned in the direction from the upper address to the lower address of the memory, and the lower address is directed to the higher address. Areas with dynamic attributes in the direction are allocated. Hereinafter, the former is called static memory management, and the latter is called dynamic memory management. In the illustrated memory space 60, the hatched area is an already allocated area, and the non-hatched part is an unallocated area.
[0014]
In static memory management, an area having a size required by an application program (in this embodiment, a printer control program) is allocated in order from the MemStEnd 62 toward the MemLoEnd 61. In the memory space 60, a management area 63 for static memory management is secured immediately before MemHiEnd 62, and immediately before the management area 63 is indicated by MemStEnd 64. An area 66 between MemStEnd64 and StAreaBottom 65 is an area used in static memory management. The address indicated by StAreaBottom 65 is the tip of the area allocated by static memory management, and StAreaBottom 65 moves by area allocation and release.
[0015]
In the dynamic memory management, an area having a size required by an application program is allocated in order from the MemLoEnd 61 toward the MemStEnd 64 direction. An area 68 between MemLoEnd 61 and DyAreaTop 67 is an area used in dynamic memory management. The address indicated by DyAreaTop 67 is the tip of the area allocated by dynamic memory management, and DyAreaTop 67 moves by area allocation and release. An area 69 of DyAreaTop 67 and StAreaBottom 65 is an unused free area that is not managed by either static or dynamic memory management.
[0016]
Next, basic functions of static memory management (area allocation, size change of allocated area, release of allocated area) will be described with reference to FIGS. FIG. 3 is a conceptual diagram of the memory space 60 showing the periphery of the space assigned to the static attribute. In static memory management, a usable space (MemLoEnd61 to MemStEnd64) is divided into a certain size. Each of these is called a unit block. As the size of the unit block, an efficient size is set in advance between several hundred bytes to several kilobytes. Information of each individual unit block is stored in the management area 63. In static memory management, management is performed using this unit block as an allocation unit, and an area that is an integral multiple of the unit block that satisfies the size requested by the application program is allocated.
[0017]
FIG. 4 is a flowchart of area allocation in static memory management. In the area allocation process, the CPU 4 calculates how many unit blocks are required for the requested size from the application program (S1), and searches the available number of unit blocks from the usable space DyAreaTop 67 in the MemStEnd64. If a free block is found (YES in S3), the management information in the management area 63 relating to the free block is updated (S4), the start address of the free block is returned to the application program (S5), and the process ends. . On the other hand, if a sufficient free block is not found in S3 (NO in S3), a request for ordering the area is issued to the dynamic memory management (S6).
[0018]
In the dynamic memory management in S6, DyAreaTop 67 moves in the direction of MemLoEnd61 by moving the area used for the allocated dynamic program in the direction of MemLoEnd61, and as a result, DyAreaTop 67 An unallocated empty area 69 between the StAreaBottoms 65 is expanded. If there are enough free blocks in the unallocated area (YES in S7), the information about the free block is updated (S4), the head address of the found free block is returned to the application program (S5), and the process ends. If sufficient free blocks are not found in S7 (NO in S7), the allocation fails and the process ends.
[0019]
FIG. 5 is a flowchart for changing the size of the allocated area in the static memory management. In this process, the size of the already allocated area is changed according to a request from the application program. The number of unit blocks required is calculated according to the requested size (S11), and the number of allocated blocks so far is compared with the required block size for the current request to check whether the allocated block needs to be expanded (S12). ). If it is determined in S12 that the current requested size is smaller than the current allocation size and there is no need for expansion (NO in S12), the allocated area so far is reduced, and the management information in the management area 63 is correspondingly reduced. Is also updated (S13), and the process ends.
[0020]
On the other hand, if there is a need for expansion in S12, the status of the blocks before and after the block allocated so far is searched (S14), and a sufficient area can be secured with the blocks allocated so far and the empty blocks before and after. If so (YES in S15), a necessary block is newly allocated (S16), and the management information in the management area 63 is updated with the new allocation (S17). If necessary, the data in the previous block is copied to the newly allocated block (S18), the head address of the newly allocated block is returned to the application program side (S19), and the process ends.
[0021]
In S15, if the empty area is insufficient in the preceding and succeeding empty blocks (NO in S15), a sufficient empty block is searched from the usable space DyAreaTop 67 in the MemStEnd 64 (S20), and whether or not new allocation is possible. (S21), if possible (YES in S21), the block in the area is assigned as a newly assigned block (S22), and the data in the previous block is copied to the newly assigned block (S23). ), The management information of the previous block and the new block is updated (S24), the head address of the block to be newly allocated is returned to the application program (S25), and the process is terminated.
[0022]
If there are not enough free blocks in S21 (NO in S21), a request for ordering of areas is issued to dynamic memory management in the same manner as S6 in FIG. 4 described above (S26). In the dynamic memory management, the allocated area is moved in the direction of MemLoEnd 61 and packed, so that DyAreaTop 67 is moved in the direction of MemLoEnd 61. As a result, the unallocated area between DyAreaTop 67 and StAreaBottom 65 is expanded. . If there are enough free blocks (YES in S27), the process proceeds to S22 and subsequent steps. In S27, if sufficient empty blocks are not found (NO in S27), the size change fails and the process ends.
[0023]
FIG. 6 is a flowchart for releasing an allocated area in static memory management. In this process, the block instructed by the application program is released to become a free block, the management information in the management area 63 is updated (S31), and the process is terminated.
[0024]
Dynamic memory management will be described with reference to FIGS. FIG. 7 is a conceptual diagram of the memory space 60 showing the periphery of the space assigned to the dynamic attribute. In dynamic memory management, an area is allocated from the lower address of the memory. The memory space that can be used in the dynamic memory management is from the memory lower address MemLoEnd 61 to StAreaBottom 65 that indicates the lower limit of the space used by the static memory management. An area allocated by dynamic memory management may move to secure a new free area. For this reason, the application program cannot manage the start address of the allocated area. Therefore, the start address of the allocated area is stored once in another area 75, and the start address of the allocated area is obtained from the application program via the stored area. An area 75 in which the top addresses of the allocated areas are stored together is called a pointer storage area. The pointer storage area 75 is secured in an area managed by static memory management so as not to be a movement target in dynamic memory management.
[0025]
An area having a size requested by the application program is allocated, and a management area is attached to each allocated area. In FIG. 7, one allocated area 80 is enlarged, and a management information area 80b for managing this area 80a is added immediately before the area 80a allocated to the application program. The management information area 80b stores the size of the area 80, the top addresses of areas existing before and after the area 80, the assigned / unassigned attributes of these areas, and the like.
[0026]
FIG. 8 is a flowchart of area allocation in dynamic memory management. In the area allocation process, a free area that satisfies the size obtained by adding the size and the management information area to the size requested from the application program is searched between MemLoEnd 61 and StAreaBottom 65 (S41), and a sufficient free area is obtained. If there is (YES in S42), the area is allocated, and the management information related to the area and the management information of the areas before and after the area are updated in the management information area 80b (S43). Then, the start address of the area to be allocated is written in the pointer storage area 75 (S44), the address written in the pointer storage area 75 is returned to the application program (S45), and the process ends.
[0027]
On the other hand, if a sufficient free area is not found in S42 (NO in S42), the area managed by dynamic memory management (between MemLoEnd 61 and DyAreaTop 67) is organized (S46). That is, by moving the allocated area in the direction of MemLoEnd 61 and filling the area, DyAreaTop 67 moves in the direction of MemLoEnd 61. If there is sufficient free space in the free space 69 (YES in S47), the process proceeds to S43. If there is not enough free space (NO in S47), the allocation fails and the process ends.
[0028]
FIG. 9 is a flowchart for changing the size of the allocated area in the dynamic memory management. In this process, the size of the already allocated area is changed according to a request from the application program. The requested size is compared with the allocated size so far (S51). If the current size is smaller than before and there is no need to expand the area (NO in S51), the allocated area so far is reduced. Accordingly, the management information is also updated (S52), and the process ends.
[0029]
If it is necessary to expand the area in S51 (YES in S51), the statuses of the areas before and after the allocated area are searched (S53), and the allocated area and the empty areas before and after the area are sufficient. If the area can be secured (YES in S54), a necessary area is newly allocated (S55) and the management information is updated with the new allocation (S56). Data in the previous area is copied to the newly allocated area (S57), and the start address of the allocated area written in the pointer storage area 75 is rewritten to the start address of the newly allocated area (S58), and the pointer storage area The address written in 75 is returned to the application program (S59), and the process ends.
[0030]
If there is not enough free space in S54 (NO in S54), search for sufficient free space between MemLoEnd 61 and StAreaBottom 65 (S60), and if there is enough free space and can be newly allocated (S61). YES), the area is set as a newly allocated area (S62), the data in the area allocated so far is copied to the newly allocated area (S63), the area allocated so far is unused, The management information of the newly allocated area is updated (S64), the start address of the allocated area written in the pointer storage area 75 is rewritten to the start address of the newly allocated area (S65), and the address written in the pointer storage area 75 is changed. It returns to the application program (S66) and ends.
[0031]
If a sufficient free area is not found in S61 (NO in S61), the area managed by dynamic memory management (between MemLoEnd 61 and DyAreaTop 67) is arranged in the same manner as S46 of FIG. 8 described above. (S67). That is, by moving the allocated area in the direction of MemLoEnd 61 and filling it, DyAreaTop 67 moves in the direction of MemLoEnd 61, and as a result, the unallocated area between DyAreaTop 67 and StAreaBottom 65 is expanded. If there is a sufficient free area in the unallocated area (YES in S68), the process proceeds to S62. If there is not enough free space (NO in S68), the allocation fails and the process ends.
[0032]
FIG. 10 is a flowchart for releasing an allocated area in dynamic memory management. In this process, the area instructed by the application program is released to become a free area, management information and the like are updated (S71), and the process ends.
[0033]
According to the memory management method and apparatus according to the present embodiment, when managing the memory space 60, the static memory management allocates an area having a static attribute in the direction from the upper address MemHiEnd 62 to the MemLoEnd 61 in the memory space 60 (see FIG. 4 to 6), the dynamic memory management assigns two different attributes by assigning an area having a dynamic attribute in the direction from the lower address MemLoEnd 61 to MemHiEnd 62 in the memory space 60 (process of FIGS. 8 to 10). Thus, the memory space 60 can be used effectively. Further, the area 66 managed by the static memory management is divided into blocks of a certain size, and the area is allocated as an integral multiple of this block, so that the memory space 60 is subdivided below the certain size. And efficient memory management.
[0034]
In addition, the allocation of the area 68 managed by the dynamic memory management is such that the top address information of the area allocated by the dynamic attribute is returned to the application program via the pointer storage area 75 (S43 in FIG. 8). S45, S64 to S66 and S56 to S59 in FIG. 9, S71 in FIG. 10, change of size of area having dynamic attributes, allocation of areas having other dynamic attributes, size of areas having other dynamic attributes Even when a change or static memory management request is made, the allocated area can be moved freely in the memory space, so the degree of freedom in memory management is great and the efficiency of memory use is increased. And memory management can be performed appropriately.
[0035]
In addition, this invention is not restricted to the said Example structure, A various deformation | transformation is possible. For example, in the above embodiment, the memory space 60 can be used more efficiently by arbitrarily dividing the static program area 66 into unit blocks each having an easy-to-use number of bytes. In the embodiment, the management by the static memory management is performed in the direction from the higher address to the lower address, and the management by the dynamic memory management is performed in the direction from the lower address to the higher address. The area may be allocated in the direction from the upper address to the lower address by dynamic memory management in the direction from the upper address to the upper address.
[0036]
【The invention's effect】
As described above, according to the memory management method or apparatus according to the first or second aspect of the present invention, the memory space is divided into the area having the static attribute and the area having the dynamic attribute, and the area having the static attribute. The static memory management that manages memory is allocated in units of unit blocks in the direction from one end to the other end of the memory space, and the dynamic memory management that manages areas with dynamic attributes is in the direction from the other end to the one end. Allocate space. And The first memory management method or means issues a request for ordering the area to the second memory management method or means when there is no free block necessary for executing new allocation or size change. The second memory management method or means responds to the request for ordering the area from the first memory management method or means. By allocating the allocated area so as to close to the other end side, there is no area allocated with the static attribute between the areas allocated with the dynamic attribute, and the free area can be expanded It is possible to freely allocate and change the size of the dynamic attribute area, thus realizing efficient memory management. In addition, the memory space is divided into unit blocks of a predetermined size in advance, assigned to the application program by an integer multiple of the unit block, and the start address of the allocated area is fixed, so the irregular size It is possible to prevent the memory space from being subdivided, and it becomes easy to secure a free space, and the memory space can be managed efficiently.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a schematic configuration of a memory management apparatus in which a memory management method according to an embodiment of the present invention is used.
FIG. 2 is a diagram showing a concept of a memory space in the present memory management method.
FIG. 3 is a diagram showing a concept of a memory space in management of an area having a static attribute in the present memory management method.
FIG. 4 is a flowchart showing area allocation processing in management of an area having a static attribute.
FIG. 5 is a flowchart showing a process for changing the size of an allocated area in the management of an area having a static attribute.
FIG. 6 is a flowchart showing a process for releasing an allocated area in management of an area having a static attribute.
FIG. 7 is a diagram showing a concept of a memory space in management of an area having a dynamic attribute in the present memory management method.
FIG. 8 is a flowchart showing area allocation processing in management of an area having a dynamic attribute.
FIG. 9 is a flowchart showing a process for changing the size of an allocated area in the management of an area having a dynamic attribute.
FIG. 10 is a flowchart showing a process for releasing an allocated area in management of an area having a dynamic attribute.
FIG. 11 is a conceptual diagram showing movement of a memory space in a conventional memory management method.
[Explanation of symbols]
3 Printer controller (memory management device)
4 CPU (control device)
5 ROM
6 RAM (memory)
60 memory space
61 MemLoEnd (lowest address)
62 MemHiEnd (highest address)
63 Management area
66 Area used for static memory management
68 Area used for dynamic memory management
75 Pointer storage area
80b Management information area

Claims (2)

In a memory management method capable of managing two memories in one continuous memory space,
The area allocated to the application program is not rearranged when a new area is newly allocated or the size of the other area is changed, and the memory space is managed in units of unit blocks of a predetermined size. In addition, a first memory management method for performing static memory management in which the size of the area allocated to the application program is set to an integral multiple of the unit block;
A second memory management method for performing dynamic memory management in which an area allocated to an application program may be moved and rearranged in accordance with a new allocation of another area or a size change of another area;
The first memory management method arranges an allocation area in units of the unit block from one end of the memory space, and the second memory management method arranges an allocation area from the other end of the memory space ,
In the first memory management method, when there is no free block necessary for executing new allocation or size change, the second memory management method issues a request for arranging the area to the second memory management method. In this memory management method, the allocated area is moved and arranged so as to be narrowed to the other end side in response to a request for ordering of areas from the first memory management system . In a memory management device capable of managing two memories in one continuous memory space,
The area allocated to the application program is not rearranged when a new allocation of another area or a size change of another area is performed, and the memory space is managed in units of a unit block of a predetermined size. And first memory management means for performing static memory management in which the size of the area allocated to the application program is set to an integral multiple of the unit block;
A second memory management means for performing dynamic memory management in which an area allocated to an application program may be moved and rearranged in accordance with a new allocation of another area or a size change of another area;
The first memory management means arranges an allocation area in units of the unit block from one end of the memory space, and the second memory management means arranges an allocation area from the other end of the memory space ,
The first memory management means issues a request for ordering the area to the second memory management means when there is no free block necessary for executing new allocation or size change, and the second memory management means. The memory management unit is configured to move and arrange the allocated areas so as to close to the other end side in response to a request for ordering the areas from the first memory management means .

Images