KR20030071299A - Apparatus for managing memory - Google Patents

Abstract

The present invention relates to a memory management apparatus that can be used in a real-time operating system, and more particularly, a memory controller for storing important information of a memory manager, and a memory logically divided into unit areas of a predetermined size, and memory allocation / release is performed in units of the unit area. A memory bitmap mapped to each unit area of the memory and storing a usage state of the unit area of the memory to manage a state of a memory allocated by an application program; and a spare not allocated by the application program; It is composed of a free memory manager that manages memory, and it can maximize memory efficiency because it provides the best-fit memory allocation method with a small amount of calculation while using a smaller amount of management information than the conventional method.

Description

Apparatus for managing memory

The present invention relates to a memory management apparatus that can be used in a real-time operating system.

In general, the memory management function of the operating system is one of the most basic functions and the most important functions provided by the operating system. Most operating systems overcome the limitations of physical memory by providing high-level memory management techniques such as paging, virtual memory, and so on.

However, the real-time operating system used mainly in embedded systems is not only limited by the physical memory size but also provides basic memory management techniques for real-time response.

This feature requires the developer to always be concerned with the operation of memory and requires a lot of memory tuning during the development process. In addition, the efficient operation of memory depends in large part on the developer's ability, not on the operating system.

In general, the memory management method used in the real-time operating system can be divided into two categories.

The first is the fixed length management method, which divides a certain amount of memory into fixed sized units. This method is quite convenient when allocating / releasing memory of the same size, but has a fatal problem when the memory size is not known in advance.

In practice, fixed-length management is a trade-off between dividing memory into areas of different sizes. For example, memory is managed by dividing into 16byte x 1000, 32byte x 1000, and 64byte x 1000. In the above example, when all 16-byte memory areas are allocated and there is no free memory, memory is allocated from the 32-byte memory area. However, since 32 bytes of memory are used for 16 bytes of memory, 16 bytes of memory are wasted. Therefore, in the system development process, it is necessary to adjust the size of each unit memory area to some extent. However, there is no guarantee that the memory is used efficiently even though the adjustment is performed, and there is a problem that more space is required for the stability of the system than is actually required.

The second is a variable length management method that allows a user to allocate / free memory of any size. This approach is familiar to most developers and can be said to be better memory efficient than fixed length management.

Various methods have been introduced as memory allocation algorithms in the case of the variable length management scheme. They can be categorized into three main categories: First-Fit, which finds the first free space to accommodate the required memory. Secondly, the best-fit method is to find the smallest free space that can accommodate the required memory. Third, the Worst-Fit method is to find the largest free space that can accommodate the required memory. Statistically, the best memory efficiency method is known as the best-fit method.

However, in the variable length management scheme described above, a large amount of memory is managed for managing purposes in the kernel of the operating system. In the case of pSOS, which is one of the representative real-time operating systems, the fixed length management method requires less than 5% of additional memory for the management memory, but the variable length management method requires more than 20% of the additional memory. In general, considering that the size of the memory embedded in the embedded system is about a few MBytes, the amount of memory available to the application is reduced by that much.

An object of the present invention is not only to significantly reduce the size of the variable-length memory management information compared to the conventional method, but also variable-length memory management apparatus that can be used in the real-time operating system that can support the memory allocation method of the best-fit method In providing.

1 is a block diagram of a memory management apparatus according to the present invention;

FIG. 2 is a block diagram illustrating a spare memory of FIG. 1.

3 is a diagram illustrating an example of partitioning and integrating a memory according to the present invention.

4 is a flowchart illustrating a memory allocation process according to the present invention.

5 is a flowchart illustrating a memory releasing process according to the present invention.

Explanation of symbols for main parts of the drawings

101: memory control unit 102: real memory area

103: memory bitmap 104: free memory manager

201,202: free memory node 203,204: free memory area

Memory management apparatus according to the present invention for achieving the above object, the memory control unit for storing important information of the memory manager; A memory logically divided into a unit area having a predetermined size, and memory allocation / release is performed in the unit area unit; A memory bitmap mapped to each unit area of the memory, the memory bitmap storing a use state of the unit area of the memory and managing a state of the memory allocated by an application program; And a free memory manager that manages free memory not allocated by the application program.

In the memory bitmap, two bits are allocated to one unit area to indicate a usage state of each unit area. One bit indicates a start position when allocating consecutive unit areas. It is characterized by indicating whether or not the allocated area.

The free memory manager connects unallocated neighboring unit areas to form a large free memory space, manages a list thereof, and concatenates the freed memory blocks with adjacent free memory blocks even when the memory is released. Blocks are formed, and these free memory blocks are characterized in that accessible through the free memory node.

The free memory nodes store free memory blocks, and when all of the designated free memory blocks are deleted, the free memory node itself is deleted, and when there is a new free size memory block that is not managed by the free memory node. A free memory node for indicating a block is generated and added to the free memory node list.

The free memory nodes are arranged in order of the size of the free memory blocks to be managed.

The free memory node includes a size of a free memory block managed by the free memory node, an address for the free memory block, and a pointer to the next free memory node. The free memory block indicated by the free memory node includes management data. It is characterized by storing.

Other objects, features and advantages of the present invention will become apparent from the following detailed description of embodiments taken in conjunction with the accompanying drawings.

Hereinafter, with reference to the accompanying drawings illustrating the configuration and operation of the embodiment of the present invention, the configuration and operation of the present invention shown in the drawings and described by it will be described as at least one embodiment, By the technical spirit of the present invention described above and its core configuration and operation is not limited.

1 is an overall system structure of a memory management apparatus according to the present invention.

Referring to Figure 1, the memory control unit 101 for storing the key information of the memory manager, the actual system RAM area 102, the memory bitmap 103 that stores the use state information of the RAM area, and the information of the free memory It consists of a spare memory manager 104 which manages.

The actual RAM area 102 is logically divided into unit areas of a predetermined size and managed. For example, if the unit area is determined to be 16 bytes in managing 1 Mbyte of memory, 65,536 unit areas are created in the RAM area 102.

In this case, all of memory allocation / release are performed in unit area units.

It is the biggest object of the present invention to efficiently manage the state of such a unit area. The state of each unit area is monitored by the memory bitmap 103.

Each of the memory bitmaps 103 is 1: 1 mapped to one unit area.

However, expressing the state of a unit area only in 1 bit has a disadvantage in that its size cannot be known when allocating consecutive unit areas. For example, when 40 bytes of memory are required, 48 bytes (16 bytes * 3) of memory that can accommodate 40 bytes must be allocated.In order to release 48 bytes correctly when the memory is released later, information that can be bounded by adjacent unit areas is required. need.

Therefore, the present invention solves this problem by using one more bit. These are defined as Start_bit and Alloc_bit, respectively. Start_bit and Alloc_bit are located in the same bitmap space in order to improve management advantages and speed up computation. That is, in order to indicate the memory status of 1 Mbyte, 65536 * 2 bits, that is, 16,384 byte bitmap memory are required.

In this way, the state of memory allocated by the application program is managed by the memory bitmap 103, while the free memory is managed by the free memory manager 104. The free memory manager 104 is responsible for binding the unallocated unit area to create the largest free memory space and maintaining it as a free memory block.

The free memory manager 104 has a pointer (ptr) indicating the location of the free memory of the corresponding size, so that the memory can be immediately allocated when the memory is requested. It also takes care of merging adjacent free memories when merging them and merging them together.

Next, the operation of the memory bitmap 103 will be described in detail.

The main purpose of the memory bitmap 103 is to display the memory state of the unit area. One unit area is represented by two bits. First, Start_bit indicates the start position when allocating consecutive unit areas. In other words, the starting position is 1, otherwise 0 is indicated. The second is alloc_bit to indicate whether it is currently allocated. In other words, the area allocated by the current application is 1 and the area included in the free memory is 0.

Analyzing the combination of Start_bit and Alloc_bit is shown in Table 1 below.

Start_bit Alloc_bit Translate 0 0 The current unit area is not allocated. That is, this area is managed by the free memory manager. 0 One The current unit area is allocated. One 0 Combinations that do not occur One One The current unit area is allocated. Also, the current area is the start area of the allocated contiguous memory.

Based on the combination of Table 1 above, the allocated memory starts with a (1,1) bit combination and is appended with a (0,1) bit combination.

And, it can be understood that the memory is a continuous memory block until (1,1) or (0,0) comes.

Thus, assuming that the location of the (1,1) bit combination is i and the location of the next (1,1) or (0,0) bit combination is j, the size of the currently allocated memory is (ji) * units. It is size (unit_size).

Next, the free memory manager 104 will be described in detail.

The main function of the free memory manager 104 is to connect unallocated unit areas to form one large free memory block and manage a list thereof. In addition, the memory blocks released when the memory is released are connected to adjacent free memory blocks to form an integrated free memory block.

Therefore, free memory is always maintained in the largest block possible, and these blocks can be accessed through the free memory node.

The free memory nodes are arranged in the order of the size of the free memory blocks to be managed so that a node corresponding to the size required for the search can be quickly found.

In this case, the free memory node always stores the free memory block, and when all of the designated free memory blocks disappear, the node itself is deleted. In addition, when a new size of free memory block is not managed by the node, a free memory node for indicating the block is created and added to the free memory node list.

In more detail, as shown in FIG. 2, the spare memory nodes 201 and 202 are largely composed of three fields. That is, each of the free memory nodes 201 and 202 is composed of a size of free memory blocks managed by them, an address for the free memory blocks, and a pointer of the next free memory node.

Therefore, when allocating memory, it is necessary to find a free memory node that satisfies the size required by an application program and allocate an address of a RAM region connected thereto.

In fact, the amount of memory the application will require varies, so it is impossible to know in advance how many free memory nodes you will need. Therefore, in the present invention, the amount of free memory nodes is limited to a certain level.

Due to the characteristics of the embedded system using a real-time operating system, the required memory pattern can be predicted to some extent, so that the amount of free memory nodes can be set to a fixed value to some extent. Of course, the actual implementation will set the value to accommodate the exception. Since the size of the free memory node is about 12 bytes, the amount of memory used for management purposes is less than that of the conventional method even when the size is relatively large.

In addition, the free memory blocks 203 and 204 indicated by the free memory nodes 201 and 202 represent actual RAM areas. The RAM area not allocated to the application program is designated as a free memory block in the free memory manager 104 to record data for management.

The present invention saves a management space for managing the free memory by using an unallocated RAM area as management data. Therefore, in the present invention, it is not only influenced by the diversity of the size of the free memory blocks present in the RAM, but also by the number of free memory blocks.

In the present invention, management information is recorded at the front and the rear of the block in the area managed by the spare memory block. The information recorded at the beginning includes the size of the corresponding memory block and two links (prev link, next link) for connecting the free memory blocks having the same size to each other and occupy 12 bytes of space. In the last 4 bytes of the block, the header address of the block is stored. It serves as a window where the information of the block can be easily accessed from adjacent blocks.

For example, assuming that the memory blocks P1 and P2 are adjacent to each other in the RAM area, the tail information of P1 can be obtained by reading data four bytes before the start coordinates of P2.

That is, P2 can obtain header information of P1 at any time. On the contrary, the address of P1 plus the memory size of P1 becomes the starting address of P2. That is, P1 can obtain header information of P2 at any time. In order to access header information of an adjacent region, first, it is necessary to know whether the region is free memory, which can be determined by examining the memory bitmap 103 of the region.

The following describes the split and merge of free memory blocks.

3 is a diagram illustrating an example of partitioning and consolidation of a spare memory block in a system initial state. The division and integration concept will be described with reference to FIG. 3 as follows.

In general, when an application requires a memory of size k, there may be a free memory block 302 that is larger than k, although there may be free memory blocks that match the required memory.

Assuming that the size of the free memory block is i, the free memory space 304 corresponding to (i-k) remains.

If the size of the free memory space is defined as j, the free memory space of size i is lost due to the memory request of the application, and the free memory space of size j is generated. This process is called memory split.

At system initialization, the system has one free block of memory that is the size of the entire RAM area. Therefore, a frequent memory partitioning process occurs when a memory allocation request is made at the beginning of the system. However, this partitioning process is simple and does not cause system performance degradation. After the partitioning process, the information of the free memory node is also updated.

When the memory 303 having a size k is released by the application program, the free memory block 305 is examined in the RAM area according to the principle of keeping the free memory block as large as possible. Assuming that the size of the adjacent free memory block is j, a new free memory block corresponding to (j + k) is formed. If the size of the free memory space is defined as i, the free memory of size j is lost by freeing the memory of the application, and the free memory block of size i is generated. This process is called memory merge.

When freeing memory, the memory consolidation process occurs up to two times. In other words, integration with Prev block and integration with Next block may occur. After completion of the consolidation process, the information of the free memory nodes is also updated.

At this time, when a large number of memory partitioning and consolidation occurs, there are free memory nodes having various sizes.

At system initialization, the size of free memory blocks is often larger than the amount of memory required by the application, but after a certain period of time, the amount of free memory blocks that match the amount of memory required by the application increases. You lose. In addition, the memory partitioning and consolidation process not only keeps the size of the free memory block as large as possible, but also makes it possible to efficiently cope with the variable memory requirements of the application by using the free memory block corresponding to the size required by the application.

The following is a description of the memory allocation (malloc) algorithm.

The memory allocation procedure of the present invention will be briefly described as follows. A process of partitioning a free memory block connected to the free memory node is performed.

The memory allocation algorithm is described in flow chart in FIG. In other words, if the application requires memory as much as the size (step 401), the size is first normalized to a size k that is an integer multiple of the size So of the unit area (step 402). Next we need to check if there are free memory blocks that can accommodate k. That is, the free memory node list is searched to find the first node i that can accommodate the size k (step 403).

If the node is not found (step 404), NULL is returned (step 405) because the requested memory cannot be accommodated, i.e. out of memory.

On the other hand, if node Ni is found, it prepares to return the free memory block pointed to by node Ni to the application. That is, the start address of the memory block is stored in Ptr, and the memory bitmap 103 is changed in the same order as (1,1) (0,1) by the size k. The memory block is also deleted from the node list (step 406). If the size i of the free memory block managed by the node Ni is larger than k + So (step 407), that is, if the area excluding the memory requested by the application is larger than the unit area, the size corresponding to (ik) A new free memory block is formed (step 408).

The newly created free memory block is added to the free memory node list (step 409). Finally, Ptr is returned (step 410).

The following is a description of the memory free algorithm.

In brief, the memory releasing procedure according to the present invention consists of adding a new spare memory block after consolidation with adjacent free memory blocks.

The memory allocation algorithm is described in flow chart in FIG. That is, when the application program requires the memory release corresponding to Ptr (step 501), the size of the corresponding memory block must be read first. Accordingly, the size k of the memory block is calculated by examining the memory bitmap 103 corresponding to Ptr. In addition, the memory bitmap of the block is updated to (0,0) (step 502). Next, Ptr and k are used to check whether a prev free memory block exists (step 503). That is, if the memory bitmap of the prev free memory block is recorded as 0, it may be determined that the prev memory block exists. Therefore, if there is a Prev free memory block, Ptr and k are updated to accommodate the Prev memory block. At this time, the Prev free memory block is deleted from the corresponding free memory list (step 504). In addition, the next free memory block is also examined to determine if it exists (step 505), so that k is updated to accommodate the next memory block. At this point, the next free memory block is deleted from the corresponding free memory list (step 506). Finally, a free memory block is formed using the finally obtained Ptr and k (step 507), and then added to the free memory node (step 508).

As described above, the amount of memory required to manage the RAM area of 1MByte, that is, 1048576byte, by the method proposed by the present invention is calculated as follows. For example, assume that the size of a unit area uses 16 bytes and 100 free memory nodes.

First, when calculating the size of the memory bitmap 103, since 2 bits represent 16 bytes, 16,384 bytes are required by (1048576 * 2) / (16 * 8). In addition, since the size of the free memory node is 12 bytes, the memory for the free memory node list is 1,200 bytes. Finally, the size of the memory controller 101 is 20 bytes.

Thus, the total required memory is 28,404 bytes, which is equivalent to 2.7% of 1MByte.

If the size of the unit area is 32 bytes, the required bitmap is reduced to 8,192 bytes, and the total required memory is 9,512 bytes, which is 0.9% of 1 MByte.

As described above, the present invention increases the efficiency of the memory by supporting the Best-Fit method, and can reduce the size of the management information by up to about 90% compared to the existing method.

As described above, according to the memory management apparatus according to the present invention, it is possible to provide the memory allocation method of the best-fit method with a small amount of calculation while using the management information of a smaller capacity than the conventional method, thereby maximizing memory efficiency. . It also allows the application to estimate only the total amount of memory needed, allowing for efficient memory management regardless of developer capabilities.

Therefore, when the present invention is used as a memory management module of a real-time operating system such as pSOS, it is possible to efficiently operate memory, improve development speed, and greatly reduce memory related problems that may occur during the development process.

Those skilled in the art will appreciate that various changes and modifications can be made without departing from the spirit of the present invention.

Therefore, the technical scope of the present invention should not be limited to the contents described in the embodiments, but should be defined by the claims.

Claims (3)

A memory controller which stores important information of the memory manager; A memory logically divided into a unit area having a predetermined size, and memory allocation / release is performed in the unit area unit; A memory bitmap mapped to each unit area of the memory, the memory bitmap storing a use state of the unit area of the memory and managing a state of the memory allocated by an application program; And And a free memory manager for managing free memory not allocated by the application program. The method of claim 1, wherein the memory bitmap is Two bits are allocated to one unit area to indicate the usage status of each unit area. One bit indicates the start position when allocating consecutive unit areas, and the other bit indicates whether the current area is allocated. The memory management device, characterized in that for displaying. The memory manager of claim 1, wherein the free memory manager comprises: Concatenates unallocated neighboring unit areas to form a large free memory space, manages a list of them, and concatenates the freed memory blocks with adjacent free memory blocks to form a unified free memory block even when the memory is released. And the free memory blocks are accessible through the free memory node.