CN107515788A - Method and device for allocating memory - Google Patents

Abstract

The invention discloses a memory allocation method, which divides the total memory into a local pool and an upper-level memory pool, and in the local pool there are multiple linked lists corresponding to threads, and the threads correspond to the linked lists, which solves the problem of slow memory allocation; and The memory size of each thread is determined according to the thread that occupies the smallest memory. When allocating memory, the linked list in the local pool will not be wasted; The memory of the difference value is split in the upper memory pool, merged into this linked list and then allocated. Therefore, when implementing memory allocation, if the thread's demand for memory exceeds the memory of its corresponding linked list, then in the upper memory The size of the excess memory is split from the pool. It can be seen that memory is allocated on demand, which effectively solves the problem of resource waste. The invention also discloses a device for allocating memory, which can also achieve the above-mentioned technical effect.

Description

Method and device for allocating memory

technical field

The present invention relates to the technical field of computers, and more specifically, to a memory allocation method and device.

Background technique

In computers, it often involves allocating memory for threads and freeing memory after allocation. Some systems may frequently allocate and release memory of various sizes. However, the process of memory allocation and release is very slow, especially in the case of multi-threaded systems. Each thread will compete with each other for memory, so it is necessary to Locking is performed to make memory allocation less efficient.

To solve this problem, memory units corresponding to threads are respectively established for each thread in the memory. When allocating memory, it is only necessary to assign the corresponding memory unit to the corresponding thread. However, allocating a memory unit for each thread will cause waste of memory resources.

Therefore, how to reduce waste of memory resources while improving memory allocation efficiency is a problem to be solved by those skilled in the art.

Contents of the invention

The object of the present invention is to provide a memory allocation method and device, so as to reduce waste of memory resources while improving memory allocation efficiency.

In order to achieve the above object, the embodiment of the present invention provides the following technical solutions:

A method of memory allocation, comprising:

Obtain the required memory value of the thread to be allocated memory;

Judging whether the required memory value is less than or equal to the first memory value of the first linked list corresponding to the thread in the local pool; wherein, a linked list in the local pool corresponds to a thread, and the memory value of the linked list is based on the occupied The thread with the smallest memory is determined;

If so, use the first linked list to allocate memory for the thread;

If not, then obtain the first remaining memory value; the first remaining memory value is the difference between the required memory value and the first memory value;

Split the memory with the size of the first remaining memory value in the upper memory pool, merge the memory into the first linked list, and use the merged first linked list to allocate memory for the thread.

Wherein, said splitting the memory of the size of the first remaining memory value in the upper memory pool, merging the memory into the first linked list, and using the merged first linked list to allocate memory for the thread, include:

Splitting the memory with the size of the first remaining memory value in the common pool, merging the memory into the first linked list, and using the combined first linked list to allocate memory for the thread.

Wherein, said splitting the memory of the size of the first remaining memory value in the upper memory pool, merging the memory into the first linked list, and using the merged first linked list to allocate memory for the thread, include:

judging whether the first remaining memory value is less than or equal to the second memory value of the common pool;

If so, then split the memory of the first remaining memory value size in the public pool, merge into the first linked list, and use the merged first linked list to allocate memory for the thread;

If not, then acquire a second remaining memory value; the second memory value is the difference between the first remaining memory value and the second memory value;

Splitting the memory page corresponding to the second remaining memory value in the memory page heap, and merging the memory page into the common pool;

Continue to execute the step of splitting the memory with the size of the first remaining memory value in the public pool, merging it into the first linked list, and using the merged first linked list to allocate memory for the thread.

Wherein, the splitting the memory page corresponding to the second remaining memory value in the memory page heap, and merging the memory page into the public pool includes:

determining the number of memory pages by using the second remaining memory value;

Using the number of memory pages to determine a second linked list in the memory page heap; wherein the memory page heap includes a plurality of linked lists, each linked list includes a plurality of intervals, and each interval is a preset number of continuous memory pages, The number of memory pages in each interval in the same linked list is the same;

All the memory pages of a range are split in the second linked list, and the split memory pages are merged into the common pool.

Wherein, splitting a range of memory pages in the second linked list, and merging the split memory pages into the common pool includes:

Determine the pageID according to the thread, use the radix tree to determine the section corresponding to the pageID, split the memory pages of the section in the second linked list, and merge the split memory pages into the common pool.

Wherein, the first linked list includes at least one memory block.

A device for memory allocation, comprising:

The required memory value acquisition module is used to obtain the required memory value of the thread to be allocated memory;

A judging module, configured to judge whether the required memory value is less than or equal to the first memory value of the first linked list corresponding to the thread in the local pool; wherein, a linked list in the local pool corresponds to a thread, and the linked list The memory value of is determined according to the thread that occupies the smallest memory;

An allocation module, configured to use the first linked list to allocate memory for the thread when the required memory value is less than or equal to the first memory value of the first linked list corresponding to the thread in the local pool;

The first remaining memory value acquisition module is used to obtain the first remaining memory value when the required memory value is greater than the first memory value of the first linked list corresponding to the thread in the local pool; the first remaining memory value is the difference between the required memory value and the first memory value;

The second allocating module is configured to split the memory of the first remaining memory value size in the upper memory pool, merge the memory into the first linked list, and use the combined first linked list for the thread Allocate memory.

Wherein, the second allocation module is specifically configured to split the memory with the size of the first remaining memory value in the common pool, merge the memory into the first linked list, and use the merged first The linked list allocates memory for said thread.

Wherein, the second distribution module includes:

A judging unit, configured to judge whether the first remaining memory value is less than or equal to the second memory value of the common pool;

The first merging unit is used for splitting the memory with the size of the first remaining memory value in the common pool when the first remaining memory value is less than or equal to the second memory value of the public pool, and merging it into the first linked list , and utilize the combined first linked list to allocate memory for the thread;

A second remaining memory value obtaining unit, configured to obtain a second remaining memory value when the first remaining memory value is greater than a second memory value of the public pool; the second remaining memory value is equal to the first remaining memory value a difference between said second memory value;

The second merging unit is configured to split the memory page corresponding to the second remaining memory value in the memory page heap, and merge the memory page into the common pool; continue to call the first merging unit.

Wherein, the second merging unit includes:

a subunit for determining the number of memory pages, configured to determine the number of memory pages by using the second remaining memory value;

The second linked list determination subunit is used to determine the second linked list in the memory page heap by using the number of memory pages; wherein the memory page heap includes a plurality of linked lists, and each linked list includes a plurality of intervals, and each interval is The preset number of continuous memory pages, the number of memory pages in each interval in the same linked list is the same;

The merging subunit is used to split all the memory pages of a range in the second linked list, and merge the split memory pages into the common pool.

It can be seen from the above scheme that the method of memory allocation provided by the embodiment of the present invention divides the total memory into a local pool and an upper memory pool, and there are multiple linked lists corresponding to threads in the local pool, and threads correspond to linked lists, which solves the problem of The problem of slow memory allocation; the memory size of each thread is determined according to the thread that occupies the smallest memory. When allocating memory, there will be no waste in the linked list in the local pool; The difference of the existing memory, split the memory of the size of the difference in the upper memory pool, merge it into this linked list and then allocate it. Therefore, when implementing memory allocation, if the thread's demand for memory exceeds its corresponding linked list Memory, then the size of the excess memory is split in the upper memory pool. It can be seen that allocating memory on demand effectively solves the problem of resource waste. The embodiment of the present invention also provides a device for allocating memory, which can also achieve the above-mentioned technical effect.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is a method for memory allocation disclosed by an embodiment of the present invention;

FIG. 2 is a specific memory allocation method disclosed by an embodiment of the present invention;

FIG. 3 is a specific memory allocation method disclosed by an embodiment of the present invention;

FIG. 4 is a schematic diagram of a memory page heap structure disclosed by an embodiment of the present invention;

Fig. 5 is a schematic structural view of a pool disclosed in an embodiment of the present invention;

FIG. 6 is a schematic structural diagram of a device for memory allocation disclosed by an embodiment of the present invention.

detailed description

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

The embodiment of the invention discloses a memory allocation method and device, so as to reduce waste of memory resources while improving memory allocation efficiency.

Referring to FIG. 1, a memory allocation method provided by an embodiment of the present invention specifically includes:

S101, acquiring the required memory value of the thread to be allocated memory;

Specifically, when a thread needs to allocate memory, first obtain the size of the memory required by the thread.

S102, judging whether the required memory value is less than or equal to the first memory value of the first linked list corresponding to the thread in the local pool; wherein, a linked list in the local pool corresponds to a thread, and the memory value of the linked list Determined according to the thread that occupies the smallest memory;

It should be noted that for a system with high concurrency, if you need to allocate and release memory more frequently, you need to consider the competition of county lock building and memory allocation efficiency. Therefore, when allocating memory, give priority to allocating it from the local pool. The local pool is a memory pool with multiple linked lists. One linked list corresponds to one thread. When memory needs to be allocated to a thread, it is first allocated from the linked list corresponding to the thread in the local pool, so that there will be no memory between threads. Competition means there is no need to add locks, which effectively reduces the competition for locks and improves the efficiency of memory allocation.

S103, if so, using the first linked list to allocate memory for the thread;

Specifically, if the memory required by a thread is less than or equal to the memory that its corresponding linked list can provide, then directly use this linked list to allocate memory for the thread.

S104. If not, acquire a first remaining memory value; the first remaining memory value is a difference between the required memory value and the first memory value;

Specifically, if the memory of the linked list corresponding to the thread is not enough for the thread, then calculate how much memory is needed, that is, calculate how much memory the linked list in the local pool still needs to allocate memory for the corresponding thread.

S105. Split the memory with the size of the first remaining memory value in the upper memory pool, merge the memory into the first linked list, and use the merged first linked list to allocate memory for the thread.

Specifically, after calculating the value of the first remaining memory, "ask" for the memory that is still needed from the upper-level memory pool, and the upper-level memory pool splits out the memory of the size of the first remaining memory, and then merges this part of memory into the memory that needs to be allocated. In the linked list corresponding to the thread of the memory, and then use this linked list that merges part of the memory in the upper memory pool to allocate memory for it.

It can be seen from the above scheme that the memory allocation method provided by the embodiment of the present invention divides the total memory into a local pool and an upper memory pool, and there are multiple linked lists corresponding to threads in the local pool, and threads correspond to linked lists, which solves the problem of memory allocation. The problem of slowness; while the memory size of each thread is determined according to the thread with the smallest memory usage. When allocating memory, there will be no waste in the linked list in the local pool; For the memory difference, the memory with the size of the difference is split in the upper memory pool, merged into this linked list and then allocated. Therefore, when implementing memory allocation, if the thread's demand for memory exceeds the memory of its corresponding linked list, Then the size of the excess memory is split in the upper memory pool. It can be seen that allocating memory on demand effectively solves the problem of resource waste.

The embodiment of the present invention provides a specific memory allocation method. The embodiment of the present invention further defines and explains S105 in the above-mentioned embodiment. The content of other steps is roughly the same as that of the above-mentioned embodiment. For details, please refer to the above-mentioned embodiment. The corresponding content will not be repeated here. Specifically, S105 includes:

Splitting the memory with the size of the first remaining memory value in the common pool, merging the memory into the first linked list, and using the combined first linked list to allocate memory for the thread.

It should be noted that when the local pool is not enough to allocate memory for the thread, it will be allocated from the public pool, and the memory of the corresponding size will be split in the public pool and merged into the corresponding linked list of the local pool, and then memory will be allocated for the thread.

The embodiment of the present invention provides a specific memory allocation method. The embodiment of the present invention further defines and explains S105 in the above-mentioned embodiment. The content of other steps is roughly the same as that of the above-mentioned embodiment. For details, please refer to the above-mentioned embodiment. The corresponding content will not be repeated here. Specifically, referring to FIG. 2, S105 includes:

S201, judging whether the first remaining memory value is less than or equal to the second memory value of the common pool;

Specifically, it is judged whether the first remaining memory value that the local pool is not enough to allocate memory to the thread is less than or equal to the memory value of the public pool, that is, it is necessary to judge whether the memory of the public pool can meet the needs of the local pool.

S202, if yes, split the memory with the size of the first remaining memory value in the public pool, merge it into the first linked list, and use the merged first linked list to allocate memory for the thread;

Specifically, if the memory in the common pool can meet the insufficient memory size allocated for the thread in the local pool, then directly split the memory in the public pool into the corresponding linked list in the local pool, so as to use the linked list to allocate memory for the thread.

S203. If not, acquire a second remaining memory value; the second memory value is a difference between the first remaining memory value and the second memory value;

If the memory required by the local pool is not enough for the public pool, calculate the insufficient part of the public pool as the second remaining memory value, so as to "request" like the memory page heap.

S204. Split the memory page corresponding to the second remaining memory value in the memory page heap, and merge the memory page into the common pool;

Specifically, the memory page heap includes multiple linked lists, each linked list includes multiple intervals, each interval is a preset number of continuous memory pages, and the number of memory pages in each interval in the same linked list is the same. Split the memory required by the public pool in the memory page heap, and then merge this part of memory into the public pool.

S205. Continue to execute the step of splitting the memory with the size of the first remaining memory value in the public pool, merging it into the first linked list, and using the merged first linked list to allocate memory for the thread.

The memory of the public pool combined with part of the memory in the memory page heap plus the memory of the corresponding linked list in the local pool are sufficient for thread allocation. It should be noted that the link list corresponding to the thread in the local pool is the one that allocates memory for the thread. It just merges the memory in the memory page heap into the common pool, and further merges the memory of the common pool into the linked list corresponding to the local pool. Thus, memory is allocated using a linked list.

It should be noted that when the memory is released, it will compare whether the current number of free blocks is greater than the maximum value in the local pool. If it is greater than the maximum value, it will be released to the public pool. If the public pool is also greater than the maximum value, it will be released back to the page heap. When all the range of a page is released, it will be released back to the system.

It can be seen that it can not only solve the competition of memory allocation for locks in the case of high concurrency, but also allocate memory according to the amount to avoid unnecessary waste.

The following is a specific memory allocation method provided by the embodiment of the present invention. The embodiment of the present invention further defines and explains S204 in the above embodiment. The content of other steps is roughly the same as that of the above embodiment. For details, please refer to The content corresponding to the embodiment will not be repeated here. Specifically, referring to FIG. 3, S204 includes:

S301. Determine the number of memory pages by using the second remaining memory value;

Specifically, according to the memory value still required by the public pool, it is determined how many pages of memory this memory value is.

S302, using the number of memory pages to determine a second linked list in the memory page heap; wherein the memory page heap includes multiple linked lists, each linked list includes multiple intervals, and each interval is a preset number of continuous memory page, the number of memory pages in each interval in the same linked list is the same;

Specifically, refer to Figure 4, which is a schematic diagram of the structure of the memory page heap. There are linked lists of 1 page, 2 pages, etc., in the linked list of 1 page, each interval has only 1 page, and in the linked list of 2 pages, each interval is are 2 consecutive pages, and so on.

If the public pool needs several pages of memory, take out the memory pages of the corresponding number of pages from the corresponding linked list; for example, if the public pool needs 2 pages of memory, then determine in the memory page heap that the interval should be split in the linked list of 2pages.

S303. Split all memory pages of a section in the second linked list, and merge the split memory pages into the common pool.

Specifically, after the second linked list is determined, the corresponding section is split in the second linked list, and all memory pages in the section are merged into the public pool, so that the public pool can be further split into the linked list of the local pool, so that the corresponding The thread allocates memory.

Since the memory pages in the range are continuous, when a certain amount of continuous memory is needed, it is allocated from the most satisfying page range, reducing the number of memory fragments.

The embodiment of the present invention provides a specific memory allocation method. The embodiment of the present invention further defines and explains S303 in the above-mentioned embodiment. The content of other steps is roughly the same as that of the above-mentioned embodiment. For details, please refer to the above-mentioned embodiment. The corresponding content will not be repeated here. Specifically, S303 includes:

Determine the pageID according to the thread, use the radix tree to determine the section corresponding to the pageID, split the memory pages of the section in the second linked list, and merge the split memory pages into the common pool.

Specifically, in order to quickly find the range of the memory required by the public pool according to the pageID, a two-layer radix tree is used to maintain these mapping relationships.

For example, the x86-64 system only uses 48-bit memory, and the page size we use is twice the size of the Linux memory page, that is, 8K, so the page number we need to maintain is 48-13=35 bits. We divide it into two layers, one layer is 18, and the other is 17. The specific implementation is as follows:

In this way, we can maintain all the pages, and only when some pages have been allocated, the leaf nodes will be established, without spending too much memory for managing these mapping relationships.

When given a pageID, such as k, we can look up the range of the memory page as follows:

i1=k>>LEAF_BITS;

i2=k&(LEAF_LENGTH–1);

range=root[i1]->values[i2];

The embodiment of the present invention provides a specific memory allocation method. The embodiment of the present invention further defines and explains the first linked list in the above embodiment. The content of other steps is roughly the same as that of the above embodiment. For details, please refer to the above The content corresponding to the embodiment will not be repeated here. Specifically, the first linked list includes a first linked list.

Specifically, referring to FIG. 5 , the pool is a free linked list maintained according to the size of the memory block. A free list of memory blocks of a series of sizes maintained by 8 bytes 16, 24, 32..., 128,..., 1024. When it is necessary to allocate memory of a specific size, it will find a block from the linked list of the corresponding size for allocation. When released, it will be put back into the table. When a block of a certain size is not enough, it will be allocated from a linked list of a larger block, and the rest will be split into a free list of smaller memory blocks. When the larger block list is still not enough, several blocks of this size will be allocated from the public pool and added to the local pool.

A memory allocation device provided by an embodiment of the present invention is introduced below, and the memory allocation device described below and the memory allocation method described above may refer to each other.

Referring to Figure 6, a memory allocation device specifically includes:

The required memory value obtaining module 401 is used to obtain the required memory value of the thread to be allocated memory;

Specifically, when a thread needs to allocate memory, the required memory value obtaining module 401 obtains the size of the memory required by the thread.

A judging module 402, configured to judge whether the required memory value is less than or equal to the first memory value of the first linked list corresponding to the thread in the local pool; wherein, a linked list in the local pool corresponds to a thread, and the The memory value of the linked list is determined according to the thread that occupies the smallest memory;

It should be noted that for a system with high concurrency, if you need to allocate and release memory more frequently, you need to consider the competition of county locks and memory allocation efficiency. Therefore, when allocating memory, give priority to allocating it from the local pool. The local pool is a memory pool with multiple linked lists. One linked list corresponds to one thread. When memory needs to be allocated to a thread, it is first allocated from the linked list corresponding to the thread in the local pool, so that there will be no memory between threads. Competition means there is no need to add locks, which effectively reduces the competition for locks and improves the efficiency of memory allocation.

An allocation module 403, configured to use the first linked list to allocate memory for the thread when the required memory value is less than or equal to the first memory value of the first linked list corresponding to the thread in the local pool;

Specifically, if the memory required by a thread is less than or equal to the memory that its corresponding linked list can provide, then the allocation module 403 directly uses this linked list to allocate memory for the thread.

The first remaining memory value acquisition module 404 is used to obtain the first remaining memory value when the required memory value is greater than the first memory value of the first linked list corresponding to the thread in the local pool; the first remaining memory value The value is the difference between the required memory value and the first memory value;

Specifically, if the memory of the linked list corresponding to this thread is not enough for this thread, then the first remaining memory value acquisition module 404 calculates how much memory is still needed, that is to say, calculates how much memory is still needed for the linked list in the local pool. The corresponding thread allocates memory.

The second allocating module 405 is configured to split the memory with the size of the first remaining memory value in the upper memory pool, merge the memory into the first linked list, and use the merged first linked list for the Threads allocate memory.

Specifically, after calculating the value of the first remaining memory, the second allocating module 405 "asks" for memory that is still needed from the memory pool of the upper layer, and the memory pool of the upper layer splits out the memory with the size of the first remaining memory, and then allocates this part The memory is merged into the linked list corresponding to the thread that needs to allocate memory, and then the linked list that merges part of the memory in the upper memory pool is used to allocate memory for it.

It can be seen from the above scheme that the memory allocation method provided by the embodiment of the present invention divides the total memory into a local pool and an upper memory pool, and there are multiple linked lists corresponding to threads in the local pool, and threads correspond to linked lists, which solves the problem of memory allocation. slow problem; and the memory size of each thread is determined according to the thread that occupies the smallest memory. When allocating memory, the linked list in the local pool will not be wasted; if the memory of the linked list is not enough, the second distribution module 405 can be utilized to total The difference between the memory and the existing memory in the linked list, the memory of the size of the difference is split in the upper memory pool, merged into this linked list and then allocated. Therefore, when implementing memory allocation, if the thread's demand for memory exceeds It corresponds to the memory of the linked list, then the size of the excess memory is split in the upper memory pool. It can be seen that allocating memory on demand effectively solves the problem of resource waste.

The embodiment of the present invention provides a specific memory allocation device. The embodiment of the present invention further defines and explains the second allocation module 405 in the above embodiment. The content of other modules is roughly the same as that of the above embodiment. The specific content can be Refer to the content corresponding to the foregoing embodiments, and details are not repeated here. Specifically, the second allocating module 405 is specifically configured to split the memory with the size of the first remaining memory value in the public pool, merge the memory into the first linked list, and use the merged first linked list Allocate memory for said thread.

It should be noted that when the local pool is not enough to allocate memory for the thread, the second allocation module 405 will allocate from the public pool, split the memory of the corresponding size in the public pool and merge it into the linked list corresponding to the local pool, and then allocate memory for the thread .

The embodiment of the present invention provides a specific memory allocation device. The embodiment of the present invention further defines and explains the second allocation module 405 in the above embodiment. The content of other modules is roughly the same as that of the above embodiment. The specific content can be Refer to the content corresponding to the foregoing embodiments, and details are not repeated here. Specifically, the second allocation module 405 includes:

A judging unit, configured to judge whether the first remaining memory value is less than or equal to the second memory value of the common pool;

Specifically, the judging unit judges whether the first remaining memory value that the local pool is not enough to allocate memory to the thread is less than or equal to the memory value of the public pool, that is, judges whether the memory of the public pool can meet the needs of the local pool.

The first merging unit is used for splitting the memory with the size of the first remaining memory value in the common pool when the first remaining memory value is less than or equal to the second memory value of the public pool, and merging it into the first linked list , and utilize the combined first linked list to allocate memory for the thread;

Specifically, if the memory in the public pool can satisfy the memory size that is not enough for the thread allocation in the local pool, then the first merging unit directly splits the memory in the public pool into the corresponding linked list in the local pool, so as to use the linked list as a link for the thread. Allocate memory.

A second remaining memory value obtaining unit, configured to obtain a second remaining memory value when the first remaining memory value is greater than a second memory value of the public pool; the second remaining memory value is equal to the first remaining memory value a difference between said second memory value;

If the public pool of memory required by the local pool is not enough to provide, the second remaining memory value obtaining unit calculates the insufficient part of the public pool as the second remaining memory value, so as to "request" like the memory page heap.

The second merging unit is configured to split the memory page corresponding to the second remaining memory value in the memory page heap, and merge the memory page into the common pool; continue to call the first merging unit;

Specifically, the memory page heap includes multiple linked lists, each linked list includes multiple intervals, each interval is a preset number of continuous memory pages, and the number of memory pages in each interval in the same linked list is the same. The second merging unit splits memory required by the common pool in the memory page heap, and then merges this part of memory into the common pool. The memory of the public pool combined with part of the memory in the memory page heap plus the memory of the corresponding linked list in the local pool are sufficient for thread allocation.

It should be noted that the link list corresponding to the thread in the local pool is the one that allocates memory for the thread. It just merges the memory in the memory page heap into the common pool, and further merges the memory of the common pool into the linked list corresponding to the local pool. Thus, memory is allocated using a linked list.

When releasing memory, it will compare whether the current number of free blocks is greater than the maximum value in the local pool. If it is greater than the maximum value, it will be released to the public pool. If the public pool is also greater than the maximum value, it will be released back to the page heap. When all the range of a page is released, it will be released back to the system.

It can be seen that it can not only solve the competition of memory allocation for locks in the case of high concurrency, but also allocate memory according to the amount to avoid unnecessary waste.

The following is a specific memory allocation device provided by the embodiment of the present invention. The embodiment of the present invention further defines and explains the second merging unit in the above embodiment. The other contents are roughly the same as the above embodiment, and the specific content can be Refer to the content corresponding to the foregoing embodiments, and details are not repeated here. Specifically, the second merging unit includes:

a subunit for determining the number of memory pages, configured to determine the number of memory pages by using the second remaining memory value;

Specifically, the subunit for determining the number of memory pages determines how many pages of memory this memory value is according to the memory value still required by the public pool.

The second linked list determination subunit is used to determine the second linked list in the memory page heap by using the number of memory pages; wherein the memory page heap includes a plurality of linked lists, and each linked list includes a plurality of intervals, and each interval is The preset number of continuous memory pages, the number of memory pages in each interval in the same linked list is the same;

Specifically, the public pool needs several pages of memory, and the second linked list determination subunit determines the corresponding linked list so as to take out the memory pages of the corresponding number of pages; for example, if the public pool needs 2 pages of memory, then it is determined in the memory page heap that the Split the interval in the linked list of 2pages.

The merging subunit is used to split all the memory pages of a range in the second linked list, and merge the split memory pages into the public pool.

Specifically, after the second linked list is determined, the merging subunit splits the corresponding interval in the second linked list, and merges all the memory pages in the interval into the public pool, so that the public pool can be further split into the linked list of the local pool, So as to allocate memory to the corresponding thread.

Since the memory pages in the range are continuous, when a certain amount of continuous memory is needed, it is allocated from the most satisfying page range, reducing the number of memory fragments.

Each embodiment in this specification is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other.

The above description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be implemented in other embodiments without departing from the spirit or scope of the invention. Therefore, the present invention will not be limited to the embodiments shown herein, but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims (10)

1. A kind of 1. method of Memory Allocation, it is characterised in that including：

   Obtain the required memory value of the thread of internal memory to be allocated；

   Judge whether the required memory value is less than or equal to the first internal memory of the first chained list corresponding with the thread in local pond Value；Wherein, the corresponding thread of a chained list in the local pond, the memory value of the chained list is according to committed memory minimum Thread determines；

   If so, it is then the thread storage allocation using first chained list；

   If it is not, then obtain the first free memory value；The first free memory value is in the required memory value and described first Deposit the difference of value；

   The internal memory of the first free memory value size is split in the memory pool of upper strata, the internal memory is merged into first chain In table, and it is the thread storage allocation using the first chained list after merging.
2. 2. according to the method for claim 1, it is characterised in that described to be split in the memory pool of upper strata in first residue The internal memory of value size is deposited, the internal memory is merged into first chained list, and is the line using the first chained list after merging Journey storage allocation, including：

   The internal memory of the first free memory value size is split in common pool, the internal memory is merged into first chained list In, and be the thread storage allocation using the first chained list after merging.
3. 3. according to the method for claim 2, it is characterised in that described to be split in the memory pool of upper strata in first residue The internal memory of value size is deposited, the internal memory is merged into first chained list, and is the line using the first chained list after merging Journey storage allocation, including：

   Judge whether the first free memory value is less than or equal to the second memory value of common pool；

   If so, then splitting the internal memory of the first free memory value size in common pool, it is merged into first chained list, and It is the thread storage allocation using using the first chained list after merging；

   If it is not, then obtain the second free memory value；Second memory value is in the first free memory value and described second Deposit the difference of value；

   Split corresponding with the second free memory value page in page heap, and described in the page is merged into In common pool；

   The internal memory that the first free memory value size is split in common pool is continued executing with, is merged into first chained list In, and using using merge after the first chained list be the thread storage allocation the step of.
4. 4. according to the method for claim 3, it is characterised in that it is described in page heap split with second residue in Page corresponding to value is deposited, and the page is merged into the common pool, including：

   Internal memory number of pages is determined using the second free memory value；

   Deposited inside using the internal memory number of pages and the second chained list is determined in page heap；Wherein described page heap includes multiple chained lists, Each chained list includes multiple sections, and each section is the contiguous memory page of predetermined number, and each section is interior in same chained list It is identical to deposit number of pages；

   All pages in a section are split in second chained list, and the page of fractionation is merged into the common pool In.
5. 5. according to the method for claim 4, it is characterised in that the page in a section is split in second chained list, And the page of fractionation is merged into the common pool, including：

   PageID is determined according to the thread, section corresponding to the pageID is determined using radix tree, in second chained list It is middle to split the page in the section, and the page of fractionation is merged into the common pool.
6. 6. method as claimed in any of claims 1 to 5, it is characterised in that first chained list includes at least one Individual memory block.
7. A kind of 7. device of Memory Allocation, it is characterised in that including：

   Required memory value acquisition module, the required memory value of the thread for obtaining internal memory to be allocated；

   Judge module, for judging whether the required memory value is less than or equal to the first chain corresponding with the thread in local pond First memory value of table；Wherein, the corresponding thread of a chained list in the local pond, the memory value of the chained list is according to accounting for Determined with the minimum thread of internal memory；

   Distribute module, it is less than or equal to first of the first chained list corresponding with the thread in local pond for the required memory value It is the thread storage allocation using first chained list during memory value；

   First free memory value acquisition module, it is more than for the required memory value corresponding with the thread first in local pond During the first memory value of chained list, the first free memory value is obtained；The first free memory value is the required memory value and institute State the difference of the first memory value；

   Second distribute module, will be described interior for splitting the internal memory of the first free memory value size in the memory pool of upper strata Deposit and be merged into first chained list, and be the thread storage allocation using the first chained list after merging.
8. 8. device according to claim 7, it is characterised in that second distribute module, be specifically used for, in common pool The internal memory of the first free memory value size is split, the internal memory is merged into first chained list, and after utilization merging The first chained list be the thread storage allocation.
9. 9. device according to claim 8, it is characterised in that second distribute module, including：

   Judging unit, for judging whether the first free memory value is less than or equal to the second memory value of common pool；

   First combining unit, when being less than or equal to the second memory value of common pool for the first free memory value, in common pool The middle internal memory for splitting the first free memory value size, is merged into first chained list, and using utilizing the after merging One chained list is the thread storage allocation；

   Second free memory value acquiring unit, for the first free memory value be more than common pool the second memory value when, Obtain the second free memory value；Second memory value is the first free memory value and the difference of second memory value；

   Second combining unit, for splitting corresponding with the second free memory value page in page heap, and by institute Page is stated to be merged into the common pool；Continue to call first combining unit.
10. 10. device according to claim 9, it is characterised in that second combining unit, including：

    Internal memory number of pages determination subelement, for determining internal memory number of pages using the second free memory value；

    Second chained list determination subelement, the second chained list is determined in page heap for being deposited inside using the internal memory number of pages；It is wherein described Page heap includes multiple chained lists, and each chained list includes multiple sections, and each section is the contiguous memory page of predetermined number, The internal memory number of pages in each section is identical in same chained list；

    Merge subelement, for splitting all pages in a section in second chained list, and by the page of fractionation It is merged into the common pool.