A Memory Management Strategy Based on Buddy Algorithm and High Reliability

Memory management is one of the central tasks of the operating system. Its main task is to organize memory to accommodate the kernel and the program to be executed, to track the current memory usage, allocate memory for the process when needed, and release and reclaim memory after use. At present, there are two main memory management strategies commonly used in embedded systems - static memory allocation and dynamic memory allocation.

Static memory allocation: The required memory is allocated when compiling or linking, and the allocated memory is not released when the program is run. For systems with high real-time and high reliability requirements, delays or allocation failures are not allowed, and static memory allocation must be used.

Dynamic Memory Allocation: A strategy for dynamically allocating memory based on the amount of memory required during program execution. This scheme allocates memory on demand, avoids the waste of memory in static allocation, and has strong flexibility, which brings great convenience to the implementation of the program. The disadvantage is that it is easy to cause memory fragmentation, and it is easy to cause problems such as the program response is not timely.

In summary, static memory allocation and dynamic memory allocation have their own advantages. For the reliability, real-time performance, cost and power consumption of embedded systems, how to make a balanced choice between the two solutions is the embedded operating system. The designer has a headache. The general embedded operating system is an efficient combination of the two solutions, and μC/OSII is no exception. In addition, the embedded operating system has the following requirements for memory allocation:

1 Reliability. Requests for memory allocation must be met, and failure to assign can have catastrophic consequences. For example, if the space shuttle's embedded operating system fails to allocate memory, the loss is immeasurable.

2 rapidity. The guarantee of real-time performance of embedded systems requires simple and fast memory allocation.

3 High efficiency. Memory in embedded systems is a limited and expensive resource, and memory allocation should reduce waste as much as possible.

As a typical embedded operating system, μC/OSII also needs to meet the above three requirements in memory management. The following briefly introduces the memory management strategy of μC/OSII and analyzes its shortcomings.

The μC/OSII memory management module is mainly composed of one data structure and five functions:

â—† memory control block data structure OS_MEM;
â—† Memory partition creation function OSMemCreate(void *addr, INT32U nblks, INT32U blksize, INT8U *err);
â—† Memory block allocation function OSMemGet (OS_MEM *pmem, INT8U *err);
â—† memory block release function OSMemPut (OS_MEM *pmem, void *pblk);
â—† Memory partition state query function OSMemQuery (OS_MEM *pmem, OS_MEM_DATA *p_mem_data);
â—† Memory control block list initialization function OSMemInit(void).

μC/OSII uses a memory control block (OS_MEM) to manage memory partitions, which is managed by the following four steps:

1 memory control block list initialization function OSMemInit () is responsible for creating a linked list of empty memory control block structure, the link table length is determined by the OS_MAX_MEM_PART macro defined in the kernel OS_CFG.H file.

2 The memory block creation function OSMemCreate() first obtains an empty memory control root block structure from the empty memory control block structure linked list, and creates a partition according to the size of the memory block required by the user. A partition contains the same size of memory blocks. Each memory block is also linked by a linked list. The size of the memory blocks in different partitions is generally different. The size of the memory blocks in ParTITION # 1 and ParTITIon # 2 is different as shown in Figure 1. of.

Figure 1 μC/OSII manages memory through the memory control block

3 The memory block allocation function OSMemGet() finds the memory control block that can meet the needs of its own memory block from the memory control block list, and then obtains the memory block it needs from the partition list header pointed to by the memory control block.

4 The memory block release function OSMemPut() is responsible for reclaiming memory blocks. When an application no longer uses a memory block, it must be released in time and placed back in the appropriate memory partition.

As mentioned earlier, the μC/OSII memory management solution is short and concise, with only a hundred lines of code and 5 functions. However, considering the three requirements of the embedded system for the memory management strategy mentioned in Section 1, the memory management strategy of μC/OSII has the following shortcomings:

1 The original μC/OSII memory management solution is not reliable. Because the memory partitions in the original scheme are isolated, there is no connection. When a memory block on a memory partition runs out, it cannot use the memory block on other partitions, but simply reports an error, which greatly reduces system reliability. In the case where the memory block size and demand are uncertain, if the memory application is not satisfied frequently, it is not tolerated by the embedded system.

2 The memory allocation in the original μC/OSII memory management scheme is not flexible enough. For example, an application requires three memory blocks of size 1 KB, 512 B, and 256 B. The original solution has two solutions. One is to create a memory partition with a memory block size of 1 KB, and the number of memory blocks. At least three; the second is to create three memory partitions, the memory block size is 1 KB, 512 B, 256 B. Solution 1 creates fewer partitions, and performance is guaranteed, but it wastes memory resources. Although scheme 2 does not waste memory, it calls 3 times OS_MemCreate() function, which is inefficient.

The Buddy algorithm is a classic algorithm for memory management. The purpose is to solve the problem of external fragmentation of memory and improve the reliability of memory management. The Buddy algorithm has been successfully applied in the Linux kernel memory management module.

As shown in Figure 2, the Buddy algorithm groups all free page frames into 10 block linked lists, each block element of each block linked list contains 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 A contiguous page frame, the physical address of the first page frame of each block is an integer multiple of the block size. For example, a block of size 4 pages has a starting address of 4×212 (the size of a page frame is 4K, the size of 4 page frames is 4×4K, 1K=1024=210, 4K=212). multiple.

Figure 2 Introduction to the Buddy algorithm

Suppose you want to request a block of 128 page frames. The algorithm first checks whether there are free blocks in the linked list of 128 page frames. If not, if you check the linked list of 256 page frames, then split the blocks of 256 page frames into two. One use, one linked list of 128 page frames. If not, check the 512 page frame list, if it is split into 128, 128, 256, one 128 is used, and the remaining two are inserted into the corresponding linked list. If it is not found at 512, an error signal is returned. Using this method to allocate page frames, the reliability of the Linux kernel is known.

In contrast to the recycling process, the kernel attempts to merge the free partners of size b into a single block of size 2b. Two blocks that satisfy the following conditions are called partners: two blocks have the same size, denoted as b; their physical addresses It is continuous; the physical address of the first page frame of the first block is a multiple of 2b×212. The algorithm iterates that if the released block is successfully merged, it will attempt to merge the 2b blocks to form a larger block. In this scenario, it suffices to satisfy the first two conditions.

1 Modify the structure of the memory control block OS_MEM, remove the OS_MemAddr, OS_MemNFree member, add a memory block chain end pointer OSMemBlkTail, so the OS_MEM structure also contains four members: OSMemFreeLiST, OSMemBlkSize, OSMemNBlks, OSMemBlkTail. The improved memory control block structure is shown in Figure 3.

Figure 3 Memory management organizational structure in the improved scheme

2 First initialize a memory control block structure array struct OS_MEM [], its subscript is the logarithm of the memory block size, the purpose of the introduction of the structure array is to quickly locate when applying for memory blocks, play the role of index. The actual size of the memory block is the product of the size of the memory block and the granularity of the memory block. Then, the memory block is hanged from small to large on the linked list pointed to by different structure arrays, and the memory block address on the same linked list is not continuous after initialization. In the application memory block, quickly locate the memory block list through the subscript of the memory control structure array, and check whether the OSMemFreeList member pointer in the memory block control structure field is empty. If it is not empty, take a memory block from the header and return the address of the memory block; otherwise, search the array backwards to see if there are free memory blocks. If there is, the memory block is divided into two, the block with the lower address is assigned to the applicant, and the block with the high address is hung to the header of the previous structure array for other applicants to apply. Similarly, when the memory block is released, it is also quickly positioned to the concrete structure array through the structure array, and then it is checked whether there is a memory block in the memory block linked list of the structure array that is continuous with the memory block address to be released. If so, merge the two memory blocks and hang them into the next structure array, and check if the address is continuous until there is no such; if not, the memory block is hung to the end of the memory block list. The improved memory management organization structure is shown in Figure 3.

1 Improve the function OS_MemInit(void). This function is originally to initialize the free memory control block list. After the improvement, this function can be used to initialize the OS_MEM structure array. The number of array elements is determined according to the macro OS_MAX_MEM_PART in the OS_CFG.H file.

2 Improved function OSMemCreate(void *addr, INT32U nblks, INT32U granularity, INT8U *err). Create memory blocks horizontally according to Buddy's rules. Each time a memory block is created, it is chained to the corresponding structure array, as shown in Create Direction in Figure 3. This ensures that the same size memory block address on each structure array is not continuous. , thus avoiding the phenomenon of merging all memory blocks. The memory block organization structure created is shown in Figure 3.

3 Improved function OSMemGet (INT32U size, INT32U granularity, INT8U *err). Because the structure array name is defined in the OS_CFG.H file macro, the parameters of this function only include the required memory block size and memory block granularity. Divide the memory block size by the memory block granularity. First, determine whether the obtained value is a power of 2. If the logarithm is taken directly, the subscript of the structure array is obtained. If not, the logarithm is taken and rounded up. If there is a memory block after getting the specified array element, take the next memory block and move the pointer down. If there is no memory block, continue to search for the next structure array. If the array has free memory blocks, it is divided into two blocks, one is allocated, and one is linked to the previous structure array linked list. This always searches for the last array of structures. If there is no memory block, it will return an error.

4 Improved function OSMemPut (INT32U size, INT32U granularity). How to get the structure array subscript value with the OSMemGet() function. After finding the array of structures to be reclaimed, it is determined whether there is a consecutive address on the linked list of memory blocks of the array. If there is a combination and hangs to the next memory block structure array memory block list, so that until the last structure array, the purpose is to ensure that there is a larger memory block to meet the application application, improve the reliability of memory management.

On the basis of improving the above functions, it is also possible to selectively use OSMemQuery() to query whether there is a memory block in the memory that satisfies the need before applying for the memory block. If not, make appropriate evasive measures to further improve the reliability of memory management and make the system more stable.

Aiming at the characteristics of the improved μC/OSII memory management strategy before and after, a set of representative test cases are designed to analyze the reliability and flexibility of the memory management of the μC/OSII system before and after improvement. The experimental environment is ARM Develop Suit V1. 2 and Samsung S3C2440 microcontroller. Since the S3C2440 contains the MMU module on the chip, the C1 register 0 of the coprocessor CP15 needs to be set to 0 to disable the MMU function.

Assume that the memory initialization of the two schemes creates five partitions, each of which contains 10 memory blocks, and the memory blocks in the five memory partitions are 16 B, 32 B, 64 B, and 128 B, respectively. 256 B. The OSMemCreate() function is called 5 times when the original scheme creates the partition, and the improvement scheme only needs to be called once. Table 1 shows the relationship between the size of the application memory block and the number of times the two schemes can be satisfied.

Table 1 Comparison of the number of times the memory block is applied and the number of times the two schemes can be satisfied.