CN1327348C - Method for resolving frequently distributing and releasing equal size internal memory - Google Patents

Abstract

The present invention discloses a method for resolving frequently distributing and releasing memories with the same size. The method of the present invention maintains a chain list of which the memory pools can be expanded, and uses a function to dynamically control the size and the number of the memory pools in the memory pool chain list. The chain list is used to manage the memory pools to avoid the condition that memory fragmentation is increased because a general memory pool distributing manner re-distributes bigger memory blocks as memory pools to meet the requirement for expanding the original memory pools which can not be extended under the condition that the memory pools are not big enough, and avoid the situation of frequently distributing memories caused by continuously extending the memory pools. The function is used to control the size and the number of the distributed memory pools so that an application program can more effectively utilize the memory and save the memory, and improves the customizability of the memory of the application program.

Description

Solution to frequent allocation and release of memory of the same size

technical field

The invention relates to application program memory management technology, in particular to a method for solving the problem of frequently allocating and releasing memory of the same size.

Background technique

Memory is an important hardware facility of computer products, and the memory allocation and release of application programs are all based on the management of memory by the operating system. The operating system provides interfaces such as malloc, free and other functions for the application program to perform memory-related operations, and the operating system itself manages the memory usage of the application program.

The memory management mechanism of the operating system can produce several situations of memory waste: internal fragmentation and external fragmentation.

The memory management mechanism of the operating system follows some basic memory allocation rules. For example, all memory allocations must start at addresses divisible by 4, 8, or 16. The memory management mechanism allocates only blocks of memory of a predetermined size to applications. When an application requests a 43-byte memory block, the memory management mechanism may allocate 44 bytes, or 48 bytes or even more memory that meets the memory allocation rules. The extra space created by rounding off the desired size is called internal fragmentation.

External fragmentation occurs when there is an unused gap between allocated memory blocks. For example, an application allocates three contiguous blocks of memory and then frees the middle block of memory. The operating system's memory management mechanisms can reuse intermediate memory blocks for future memory block allocations. But it is unlikely that the size of the memory block allocated in the future will be as large as all free memory blocks of the operating system. Then the memory management mechanism can only divide small memory blocks that meet the requirements of the application program from the middle of the large free memory block, and this continues, and eventually there will be fragments between many small memories, which cannot meet any of the application programs. Memory requests, these are external fragments.

When frequently allocating and releasing memory of the same size, the operating system will generate a large number of external memory fragments and affect the efficiency of the operating system. The traditional solution is to use memory pools. However, a single memory pool has defects such as poor customization, memory waste, and possible memory fragmentation when expanding the memory pool. Therefore, transforming the traditional method of frequently allocating and releasing memory of the same size can increase the availability of application memory. Customization, improve the efficiency of system memory usage, and improve system performance.

A memory pool is a piece of continuous memory pre-applied by the application program from the operating system. The attributes of the memory pool include the size of the memory pool, the start address, the end address, the size of the memory block, the number of memory blocks, and the symbol of the memory block , other information about the memory block, etc. The size of the memory pool is the sum of the number of memory blocks multiplied by the size of the memory block, the size of the flag of the memory block, and the size of other information of the memory block.

The application program allocates the memory size according to the need, takes the address of the free memory block from the corresponding memory pool for use, and returns it to the memory pool after use.

When the memory pool has no free memory blocks, the application program expands the memory pool, and the operating system is responsible for expanding the memory pool or reallocating a larger memory pool according to the memory management mechanism of the operating system, and copying the original memory pool information to the new memory pool. pool.

The existing memory pool management method limits the size of the memory pool at the beginning of the application, and the customizability is poor. Although the memory pool can be expanded when the memory pool is not large enough, it may also generate external memory fragments , and when the memory pool has been expanding, continuous expansion of the memory pool is equivalent to frequent allocation of memory, which has a significant impact on system efficiency.

Therefore, if a more effective solution to frequent allocation of the same size can be proposed, the customizability of the entire application memory can be improved, the memory can be used and saved more effectively, the running speed of the application can be improved, and the response time can be reduced.

Contents of the invention

The purpose of the present invention is to provide a method for solving the problem of frequently allocating and freeing memory of the same size.

The technical scheme that the present invention adopts is as follows:

1) Note that the size of frequently allocated and released memory of the same size is msize, the pointer of the memory pool list is plist, the nth memory pool is mpn, the start address of the memory pool is psn, the end address is pen, the first memory pool is The memory of the free flag is free at the location of the memory pool;

2) Define a function f(n) to determine the number of memory blocks in the nth memory pool. If the value of f(n) is equal to 0 or less than 0, it means that the application program has set the number of memory blocks whose size is msize. The upper limit of the number, the size is the sum of the number of memory blocks allocated in the previous n-1 times;

3) When the application program needs memory with a size of msize, start from the first memory pool in the memory pool linked list, and judge whether the freen of the memory pool is greater than f(n); if freen is less than or equal to f(n), it means that the The memory pool has free memory that can be allocated, and returns the memory pool; if freen is greater than f(n), it means that the memory pool has no free memory to use, and judges the next memory pool; if there is no next memory pool, and f(n) > 0, then create a new memory pool with a size of F(n), where F(n)=(msize+flag size)*f(n); at the same time, initialize all flags to free, initialize free to 1, and then return the Memory pool; if f(n)<=0, notify the application that the memory limit has been reached;

4) After obtaining a memory pool with free memory available for use, use the memory whose location is free for the application program, and at the same time set the flag of the memory whose location is free to used, and then start from the location free+1, one by one Determine whether the memory flag of the memory pool is free. If the memory marked as free is found before the end of the memory pool, the free of the memory pool is equal to the location of the found memory marked as free. If no memory marked as free is found memory, then make the freen of the memory pool equal to f(n)+1;

5) When the application releases the memory with the size of msize, set the flag of the memory to free, and at the same time judge whether the location of the memory in the memory pool is greater than the free of the memory pool, if it is smaller than free, then make free equal to the The location of the memory in the memory pool;

6) When the application exits, all memory pools in the memory pool linked list are destroyed.

Compared with the prior art, the present invention has the beneficial effects of: replacing a single memory pool with a memory pool linked list, and using functions to control the number and size of the memory pool, thereby improving the customizability of the entire application program memory and making it easier Effective use of memory and save memory, improve the running speed of applications, reduce response time.

Description of drawings

Figure 1 is a memory pool structure diagram;

Fig. 2 is a general structure diagram of the memory pool linked list;

Figure 3 is a memory pool linked list with 1 new memory pool;

Figure 4 is the memory pool linked list after the application allocates a block of memory with a size of 32;

Figure 5 is the memory pool linked list after the application has continuously allocated 5 blocks of memory with a size of 32 in the state of Figure 4;

FIG. 6 is the state of the memory pool list after the application program releases the memory block at the second position of the memory pool mp1 in the memory pool list in the state of FIG. 5 .

Detailed ways

In the following, an embodiment is used to illustrate how to use the present invention to solve the situation of frequently allocating and releasing memory of the same size in conjunction with the accompanying drawings.

Note that the size of frequently allocated and released memory of the same size is msize, the pointer of the memory pool list is plist, the nth memory pool is mpn, the start address of the memory pool is psn, the end address is pen, and the first free flag of the memory pool The location of the memory in the memory pool is free; define a function f(n) to determine the number of memory blocks in the nth memory pool, and the value of f(n) is equal to 0 or less than 0, which means that the application program The upper limit of the number of memory blocks whose size is msize is set, and the size is the sum of the number of memory blocks allocated for the previous n-1 times, as shown in Figure 1 and Figure 2.

Step 1: adopt technical scheme 1) initialization frequent allocation releases the size msize=32 of memory of the same size, and the pointer of the memory pool linked list is empty for plist;

Step 2: adopt technical solution 2) to initialize function f, make f(1)=5, f(2)=7, f(3)=0, it means that the application program has set the number of memory blocks whose memory size is 32 The upper limit is 5+7=12;

Step 3: adopt technical scheme 3) to obtain memory pool mp1 with free memory, the signs of 5 memory blocks of memory pool mp1 are all free (abbreviated with F), the position free1=1 of the first free memory block of memory pool . (See Figure 3)

Step 4: After obtaining the memory pool with free memory blocks, adopt technical solution 4) to use the memory block at position 1 for the application program, and change the sign of the memory block at position 1 to used (abbreviated with U), and the memory pool The position free1=2 of the first free memory block of mp1. (See Figure 4)

Step 5: adopt technical scheme 3) and 4) to allocate 5 blocks of memory whose size is 32 to the application program, at this moment, the position free1=6 of the first free memory block of memory pool mp1, and the first free memory block of memory pool mp2 The location free2=2 of the free memory block. (See Figure 5)

Step 6: adopt technical solution 5) to release the memory block whose position of memory pool mp1 is 2, at this moment change the sign of this memory block to free, and make the position free1=2 of the first free memory block of memory pool mp1 simultaneously.

(See Figure 6)

Step 7: adopt technical solution 6) to destroy the memory pools mp1 and mp2 in the memory pool linked list plist. At this time, the plist is empty.

Claims (1)

1 one kinds of methods that solve frequently distributing and releasing equal size internal memory is characterized in that:

1) size of note frequently distributing and releasing equal size internal memory is msize, the pointer of memory pool chained list is plist, and n memory pool is mpn, and the start address of memory pool is psn, the end address is pen, and the position of interior this memory pool of existence of first free sign of memory pool is freen;

2) function f of definition (n) number that decides memory block in n the memory pool, f (n) value equals 0 or less than 0, the number upper limit of size of then having represented application setting, size for the memory block of msize be front n-1 sub-distribution memory block number with;

3) when application program needed size to be the internal memory of msize, then from first memory pool of memory pool chained list, whether the freen that judges memory pool one by one was greater than f (n); If freen, represents that this memory pool has free memory to distribute, and returns this memory pool smaller or equal to f (n); If freen, represents that this memory pool does not have free memory to use, and judges next memory pool greater than f (n); If there is not next memory pool, and f (n)＞0, a so newly-built memory pool that size is F (n), wherein F (n)=(msize+ zone bit size) * f (n); The all zone bits of initialization simultaneously are free, and initialization freen is 1, returns this memory pool then; If f (n)＜=0, then notification application has reached the internal memory upper limit;

4) obtained after the operable memory pool of free memory, is the position of this memory pool that the internal memory of freen uses to application program, be the position that the sign of the internal memory of freen is made as used simultaneously, then from position freen+1, whether the sign of judging the internal memory of memory pool one by one is free, if before memory pool finishes, find the internal memory that is masked as free, then make the position at the internal memory place that is masked as free that the freen of this memory pool equals to find, if do not find the internal memory that is masked as free, then make the freen of this memory pool equal f (n)+1;

5) when application program release size is the internal memory of msize, then the sign of this internal memory is made as free, judge that simultaneously the position that has the place memory pool in this whether greater than the freen of place memory pool, if less than freen, then makes freen equal to exist in this position of place memory pool;

When 6) application program withdraws from, destroy all memory pools in the memory pool chained list.

Images