专利摘要:
According to the present invention, by setting an unallocated pointer indicating an empty memory area in a memory structure, the memory area is quickly searched and allocated on the basis of the unallocated pointer when the memory allocation request is made. The present invention relates to a method for allocating an optimal size memory, comprising: a flag indicating an alloc./empty state of a memory region, an assignable size, and the like. A first step of setting the indicating TOP memory area 10; A second step of setting an unallocated memory area (20, 40) having an unallocated pointer indicating a memory area of a next unallocated state when the flag state is an unallocated state in which the memory is empty; And a third step of setting an allocated memory area 30 in which memory is allocated to an empty memory area, and the memory allocation method according to the present invention uses an unallocated pointer to select an optimal memory. It is a useful invention that can be allocated at a high speed, and that a low-cost CPU can be used in accordance with the increase in the software processing speed.
公开号:KR19990086969A
申请号:KR1019980020756
申请日:1998-05-28
公开日:1999-12-15
发明作者:오용규
申请人:구자홍;엘지전자 주식회사;
IPC主号:
专利说明:

Memory allocation method
The present invention relates to a memory allocation method, and more particularly, to setting an unallocated pointer indicating an empty memory area in a memory structure, thereby freeing the unallocated pointers from the unallocated memory areas when a memory allocation request is made. The present invention relates to an optimal memory allocation method for searching and allocating at high speed.
When running a program on a computer, memory for variables and workspaces is allocated from the operating system (O / S) or system manager (System Management). In order to use memory on the system efficiently, the memory must be allocated dynamically, and after the allocated memory is used, it must be returned to the system so that other programs can use the memory.
On the other hand, in a low-cost system with low memory, memory acquisition and return occur frequently, and the time spent allocating and returning the memory greatly affects system performance depending on the operation speed of the entire software. Products that currently use Reduced Instruction Set Computer (RISK) or Complex Instruction Set Computer (CISK) CPUs, such as NC, Internet Set Top Box, DBS Set Top Box, Digital TV (DTV) As such, the software used for them must dynamically use a finite resource of memory, and the performance related to the allocation and return of the memory has a great effect on the performance of the system.
1 is a memory chain for explaining a memory allocation according to the prior art, the memory chain is a pointer indicating the next memory area, starting with the TOP area (1) as the basis of the memory stack (Next) ) And a pointer to a previous memory area, and a flag indicating a state of each memory area. Herein, the pointer is one of data structures used in a high-level programming language such as C language or Pascal language, and refers to information indicating a location or address of a storage location in which one piece of data is stored. You can go directly to the location where the data is stored. The flag is divided into Alloc. And Empty. When the allocated memory Alloc returns the memory to the system, the flag becomes an empty memory. The memory size is a size of the memory allocated by the memory area and is represented by the number of bytes required by a utility or the like.
Table 1 shows the memory as a structure type on a program. In the programmatic structure, Struct, int, and char are function names, and Memory Block * prev, Memory Block * next, Size, Flag, TASK_ID, and Data [Size} mean variable names. Remarks, such as 'Prev Pointer', are used to describe the contents of the variable. Here, two memory area pointers (Prev. Pointer and Next Pointer) are used, and Data [Size] represents an actual memory address allocated to a user system.
Structure Memory Block in Program Struct Memory Block * prev Previous Memory Area Pointer (Prev. Pointer) Struct Memory Block * next Next memory area pointer int Size Memory size required by utility char Flag Status of memory area (Alloc, Empty) char TASK_ID Identification number of the job requiring memory char Data [Size} Physical memory address assigned to your system
The above-described structure of Table 1 may be used to configure the memory chain of FIG. 1, wherein the TOP memory region 1 is NULL without a previous region, and the A1 memory region 2 has a previous region prev. And the next area next is A2. In the same manner, the memory area is distributed and allocated, and memory allocation and destruction are shown in FIGS. 2A and 2B.
2A and 2B are the last memory areas before and after memory allocation according to the prior art, in which A2 is allocated when A2 (3) is the last memory area, and the next area next is NULL. If 20 Kbytes is required, A3 (4), which is the next area, is created, 20Kbytes are allocated to A2, and the last memory area is created. That is, FIG. 2A is the last memory chain before memory allocation with a size of 200Kbytes and the flag is in an Unallocated state, and FIG. 2B is an Alloc state with 20Kbytes allocated to the memory chain A2 after memory is allocated. The new A3 becomes the last memory chain, where A3 is flagged and the memory size is 180 Kbytes.
FIG. 3 is a diagram illustrating allocating memory to an unallocated area according to the prior art. When the required memory size is 20 Kbytes, the A3 memory area 4 in the unallocated state is 20 Kbytes. Allocates to a memory area. Here, the A3 memory area represents a free, ie, unallocated area existing between the A2 memory area 3 and the A4 memory area 5.
FIG. 4 is a structural diagram of a memory map according to the prior art, and the above-described memory area is allocated by dividing a heap area on the memory map into memory allocation areas. For example, the start address of the A1 memory area is the sum of the address 20000h and the header size (HS), where the previous area pointer points to the TOP, and the next area pointer points to the A2 area. Will be displayed. Here, the heap area refers to a storage area reserved for the operating system in order to allocate a storage space required during the execution of a program. For example, the heap area in the operating system requires a storage space to store data during execution. The storage location at will be allocated to the program. The TOP area is a header area that contains contents of information stored such as a file or a record of a storage device.
In the memory map structure of FIG. 4 described above, a memory allocation method uses a memory allocation method of an optimal size and a last memory allocation method. First, there is always a free area allocated and returned in the middle of the memory area, such as A3 of FIG. 3. To allocate the memory, an empty area, that is, an unallocated area (from the TOP area, which is the head of the memory area, through the Next pointer) Empty Block), and if the size of the empty area is suitable for the required size, memory is allocated, but if there is no size allocated, the required size is compared in the final area. Likewise, the optimal size memory allocation method is to allocate the required size by creating a new last region.
In order to increase the memory allocation speed, the memory is always allocated from the last memory, and if the last memory is insufficient, the method of using the above-described optimal size memory allocation method is the last memory allocation method.
However, in the conventional memory allocation method, the optimal size memory allocation method has a problem that the flag state is empty and it takes a long time to search and compare whether the memory size meets the required size.
In addition, the conventional last memory allocation method may be faster at first but later becomes slower, and is not an optimal memory allocation. Therefore, when a large amount of memory is required, unallocated areas are scattered in various places. Although the entire unallocated area is memory assignable, there is a problem that there is no memory of the assignable size.
Therefore, the present invention was created to solve the above problems, and in the memory allocation method, using an unallocated pointer that refers to an unallocated area while using an optimal size memory allocation method, The goal is to always allocate memory at high speed by searching for unallocated regions in the memory structure.
1 illustrates an embodiment of a memory chain according to the prior art,
2A and 2B show the last memory chain before and after memory allocation according to the prior art;
3 illustrates a memory chain for allocating memory to an unallocated area according to the related art.
4 illustrates a structure of a memory map according to the related art.
5 illustrates a memory chain using an Unassigned Pointer according to the present invention,
Figure 6 shows a memory chain omitting the next memory area pointer in accordance with the present invention,
7 shows a structure of a memory map according to the present invention,
8 is a flowchart illustrating a memory allocation method according to an embodiment of the present invention.
※ Explanation of code for main part of drawing
10: Top memory area 20: First memory area
30: second memory area 40: fourth memory area
According to an aspect of the present invention, there is provided a memory allocation method, comprising: a first step of setting an unassigned pointer indicating a memory area in which a next memory is empty in an area in which the memory is empty; And a second step of searching for and allocating a memory area based on the unassigned pointer when allocating a memory.
In the memory allocation method according to the present invention made as described above, in a memory structure composed of a flag, a request size, and the like, by adding an unassigned pointer indicating a place where the memory is empty, that is, the memory is unallocated to the area where the memory is empty. By setting the pointers, only memory areas having the unallocated pointers can be searched and allocated at high speed during memory allocation.
Hereinafter, a preferred embodiment of a memory allocation method according to the present invention will be described in detail with reference to the accompanying drawings.
FIG. 5 is a memory chain diagram illustrating a region in which memory is allocated using an unallocated pointer according to the present invention. FIG. 5 is a flag indicating an alloc / empty state of a memory region. 1. A memory structure having a size and an assignable size, comprising: a first step of setting a TOP memory area 10 representing a header; A second step of setting an unallocated memory area (20, 40) having an unallocated pointer indicating a memory area of a next unallocated state when the flag state is an unallocated state in which the memory is empty; And a third step of allocating memory to the empty memory area and changing the flag to set the allocated memory area 30, wherein the memory structure has a flag, a required size, and the like. By setting an unassigned pointer to, if the flag is in an unallocated state when allocating memory, a direct search is made from the A1 region 20 to the A3 region 40 by an unallocated pointer that refers to the memory region of the next unallocated state. That is, it is possible to search and allocate only the memory area having the unassigned pointer at high speed without passing through the A2 area 30 which is the memory area 30 to which the memory is allocated.
8 is a flowchart illustrating an operation of a memory allocation method according to the present invention, with reference to the memory chain structure of FIG. 5.
In Fig. 5, by assigning a non-allocating pointer to the next unallocated area in the memory area, when searching for the next unallocated area, A1 (20) → A3 ( It is possible to find the unallocated area immediately by the path of 40), and not to search the first unallocated area in the order of TOP (10) → A1 (20), but to set the unallocated pointer to find the first unallocated area. You can specify it immediately. However, as shown in FIG. 5, when the unallocated pointer is added to search the next unallocated region at high speed, the management memory becomes large.
FIG. 6 is a configuration diagram of a memory chain for streamlining memory management. In FIG. 4 and Table 1, it can be seen that the next memory area pointer Next Point becomes equal to an address after char Data [Size]. That is, since Next Pointer = the sum of the Data Address and the Size, the Next Pointer does not need to have the Next Pointer.
Structure Memory Block in Program StructMemory Block * prevPrevious Memory Area Pointer (Prev Pointer) StructMemory Block * EmptyNext Empty Area Pointer intSizeMemory size required by utility charFlagState of memory area; Alloc, Empty charTASK_IDIdentification number of the job requiring memory charData [Size}Physical memory address assigned to your system / * Struct Memory Block * next = address of Data + Size * /
In other words, as shown in Table 2, the Next Pointer does not actually exist by being allocated an address on the memory area, but is obtained by an operation.
FIG. 7 is a structural diagram of a memory map according to an embodiment of the present invention, which illustrates using an unassigned pointer separately in place of a next memory area pointer (Next Pointer) as compared to FIG. 4 described above. The pointer is obtained by operation.
Meanwhile, a method of allocating a memory using the aforementioned memory chain of FIG. 6 is as follows. In FIG. 8, when the utility requests a memory area to store data (S11), the memory area size is checked based on a preset unassigned pointer and the memory area is checked to meet the required memory size (S12). If the memory size does not match, the next unallocated area is checked. That is, if the size of the first unallocated area A1 is 20 Kbytes and the required memory size is 30 Kbytes, the first unallocated area is skipped, and the next unallocated area A3 area 40. Will be examined.
Then, the next unallocated area is checked, if it meets the size required by the utility, i.e. not smaller than the size requested by the utility (S13), and the size of the unallocated memory area is (required size + size of header). If not exceeded (S14), the corresponding memory area is allocated (S15), and the flag is changed to Alloc, (S16). Herein, it is determined whether or not the big memory area is based on the (required size + size of header).
If the size of the searched unallocated memory area exceeds the (required size) + header size, i.e., is too large than the required size (S14), once the area is a big area pointer (BBP) Will be assigned to). If there is an existing big memory area previously allocated to the big area pointer BBP (S17), the area is ignored and the first big area pointer BBP is allocated (S18). If there is no pre-allocated existing big memory area (S17), the unallocated memory area is allocated to the big area pointer BBP (S19). In this case, setting and allocating the big memory area is to use the small portion of the unallocated area, and selecting the minimum value of the memory area of the big area pointer BBP may increase the memory allocation efficiency.
If there is no area matching the required memory size by searching the unallocated area to the end (S20), that is, there is no memory area larger than the required size or smaller than (required size + header size) In this case, the memory area indicated by the above-mentioned big area pointer is allocated (S21), and the flag is changed to Alloc. (S22).
Accordingly, the present invention utilizes an optimal size allocation method when allocating memory, which is a main memory such as RAM, which is dynamically used in the system, while the memory area is empty, that is, the flag state is empty. Only in-memory areas are searched and allocated at high speed, and if the memory area to be allocated is a big memory area that is too large, the memory is allocated from a relatively small portion among the big memory areas.
The memory allocation method according to the present invention as described above is a useful invention that can allocate the optimal memory at the time of memory allocation using a non-allocating pointer at a high speed, and that a low-cost CPU can be used according to the speed of the software processing speed.
权利要求:
Claims (7)
[1" claim-type="Currently amended] Setting an unassigned pointer indicating a next empty memory area in an area where the memory is empty; And
And a second step of searching for an empty memory area with reference to the unallocated pointer and allocating the empty memory area to the requested data storage space.
[2" claim-type="Currently amended] According to claim 1,
The memory allocation method of the second step, the memory allocation method, characterized in that the memory area is made from a small portion,
[3" claim-type="Currently amended] According to claim 1,
The memory allocation method of claim 1, wherein the sum of the allocated data address and the required memory size is designated as a pointer value indicating the next memory area.
[4" claim-type="Currently amended] According to claim 1,
The unallocated pointer is a memory allocation method, characterized in that the first unallocated region is designated directly without passing through a header region.
[5" claim-type="Currently amended] In the memory allocation method,
Searching for an empty memory area with reference to an unassigned pointer indicating an empty memory area;
A second step of comparing the size of the searched unallocated memory area with the required size; And
And assigning the memory by designating the searched unallocated memory as a big memory according to the comparison result.
[6" claim-type="Currently amended] The method of claim 5,
The third step of the memory allocation method further comprises the step of allocating the searched unallocated memory area according to the comparison result,
[7" claim-type="Currently amended] The method of claim 5,
The third step,
A first substep of checking whether a predetermined big memory area exists if the size of the searched unallocated memory area is larger than the requested memory area size;
A second substep of comparing a size of the searched unallocated memory area if a predetermined big memory area exists;
A third substep of setting the searched unallocated memory area as a big memory according to a comparison result of the second substep; And
And a fourth sub-step of allocating memory to the big memory area if there is no memory area to be repeatedly allocated from the first step until the last unallocated area.
类似技术:
公开号 | 公开日 | 专利标题
US20190213043A1|2019-07-11|Object Optimal Allocation Device, Method and Program
US9110826B2|2015-08-18|Memory allocation in a system using memory striping
US6526422B1|2003-02-25|Striding-type generation scanning for parallel garbage collection
US6249793B1|2001-06-19|Mostly concurrent compaction in a garbage collection system
US6125430A|2000-09-26|Virtual memory allocation in a virtual address space having an inaccessible gap
US5761536A|1998-06-02|System and method for reducing memory fragmentation by assigning remainders to share memory blocks on a best fit basis
US6247105B1|2001-06-12|Externally identifiable descriptor for standard memory allocation interface
US5559978A|1996-09-24|Method for increasing the efficiency of a virtual memory system by selective compression of RAM memory contents
US7334105B2|2008-02-19|System and method for managing the memory in a computer system
US6003115A|1999-12-14|Method and apparatus for predictive loading of a cache
US6862674B2|2005-03-01|Methods and apparatus for performing a memory management technique
US6757890B1|2004-06-29|Methods and apparatus for enabling local Java object allocation and collection
US7587566B2|2009-09-08|Realtime memory management via locking realtime threads and related data structures
US6571260B1|2003-05-27|Memory reclamation method
US6598141B1|2003-07-22|Manipulating interior pointers on a stack during garbage collection
JP2613001B2|1997-05-21|Virtual memory management system, translation index buffer management method, and translation index buffer purge overhead minimization method
US4742450A|1988-05-03|Method to share copy on write segment for mapped files
US7136887B2|2006-11-14|Method and mechanism for finding references in a card in time linear in the size of the card in a garbage-collected heap
CA1266533A|1990-03-06|Method to automatically increase the segment size offile in a page segmented virtual memory dataprocessing system
US5913230A|1999-06-15|Object and method for providing efficient multi-user access to shared operating system kernal code using instancing
US6125434A|2000-09-26|Dynamic memory reclamation without compiler or linker assistance
US7512738B2|2009-03-31|Allocating call stack frame entries at different memory levels to functions in a program
EP1023661B1|2001-12-05|Application programming interface enabling application programs to control allocation of physical memory in a virtual memory system
JP2810675B2|1998-10-15|Debug method
US6735666B1|2004-05-11|Method of providing direct user task access to operating system data structures
同族专利:
公开号 | 公开日
KR100315500B1|2002-02-19|
引用文献:
公开号 | 申请日 | 公开日 | 申请人 | 专利标题
法律状态:
1998-05-28|Application filed by 구자홍, 엘지전자 주식회사
1998-05-28|Priority to KR1019980020756A
1999-12-15|Publication of KR19990086969A
2002-02-19|Application granted
2002-02-19|Publication of KR100315500B1
优先权:
申请号 | 申请日 | 专利标题
KR1019980020756A|KR100315500B1|1998-05-28|1998-05-28|Memory allocating method|
[返回顶部]