CN102866954A - Method and device for allocating internal memory - Google Patents
Method and device for allocating internal memory Download PDFInfo
- Publication number
- CN102866954A CN102866954A CN2012103169440A CN201210316944A CN102866954A CN 102866954 A CN102866954 A CN 102866954A CN 2012103169440 A CN2012103169440 A CN 2012103169440A CN 201210316944 A CN201210316944 A CN 201210316944A CN 102866954 A CN102866954 A CN 102866954A
- Authority
- CN
- China
- Prior art keywords
- chained list
- idle
- free memory
- idle chained
- memory block
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Memory System (AREA)
Abstract
The embodiment of the invention provides a method and a device for allocating an internal memory, wherein the method comprises the following steps: serially connecting idle internal memory blocks to a corresponding idle linked list, wherein a head indicator of the idle linked list is maintained in an idle linked list head array with the magnitude being N, an index of the corresponding idle linked list indicated by the head indicator in the idle linked list head array is n, and the idle linked list with the index being n is used for serially connecting the idle internal memory blocks with the magnitude being X; when the magnitude of the applied internal memory is Y, confirming a first nonblank idle linked list between the idle linked list with the index being m+1 and the idle linked list with the index being n by starting from the idle linked list with the index being m+1; and extracting a first idle internal memory block in the first nonblank idle linked list and allocating the first idle internal memory block according to the magnitude of the applied internal memory. The method provided by the invention has high property while has the characteristics of few fragments and capability of applying the internal memory at any magnitude.
Description
Technical field
The present invention relates to computer realm, in particular to method and the device of Memory Allocation.
Background technology
In the computer utility such as software programming, often relate to dynamic application and the release of memory source.Need to be that this thread distributes stack space during such as a thread of establishment, when this thread is deleted, need to reclaim corresponding stack space.About memory management, there has been many algorithms in industry, and its relative merits are respectively arranged.Estimate the quality of a internal memory algorithm, the key element such as mainly contain performance, utilization factor, reliability, can format.
The internal memory algorithm mainly is divided into static memory algorithm, piece internal memory algorithm, cuts apart several large classes such as combination type internal memory algorithm.The static memory algorithm performance is very high, but can only apply for memory source and can not the releasing memory resource, generally is used in initial phase.Piece internal memory algorithm performance is also very high, capable of dynamic application or releasing memory resource, but the size of its assignable memory source is subject to the restriction of internal memory block size, and utilization factor is also poor.Cut apart application or release that combination type internal memory algorithm can satisfy the memory source of arbitrary size, utilization factor is also high, but existing Algorithm Performance is poor.
For example, a kind of internal memory algorithm refers to memory pool is divided into several pages or leaves: during the application memory source, if the chained list of the block type of corresponding memory block is not then won a memory block for sky from this chained list, otherwise apply for the page of a free time, the page that this is idle carries out five equilibrium by the internal memory block size of correspondence, during the releasing memory resource, if all memory blocks in the page are all idle, then reclaim the chained list that this page and extension idle page.But this algorithm can cause page internal fragment and piece internal fragment, and the size of the maximum memory source that can apply for can not surpass the maximum memory block size.
For example, another kind of piece internal memory algorithm refers to that the block type of each memory block safeguards an idle chained list: during the application memory source, check first whether corresponding chained list is empty, if be not sky then from chained list, win a memory block, otherwise according to distributing pointer to divide again the memory block of a current size; During the releasing memory resource, directly the memory block with current release is suspended in the idle chained list of corresponding blocks type.But this algorithm causes the piece internal fragment easily, and the size of the memory source that maximum can be applied for can not surpass the maximum memory block size, and the memory block that has been divided out can not be formatted as other block type.
For example, a kind of combination type internal memory algorithm of cutting apart refers to and can divide memory block by arbitrary size, and can front and back next-door neighbour's free memory block be merged when memory block is released.In this algorithm, in order to find rapidly suitable memory block, all free memory blocks are maintained as a balanced binary tree.But, this algorithm relate to the binary tree node application, discharge, search and balancing run, so Performance Ratio is relatively poor.
Summary of the invention
The embodiment of the invention has proposed method and the device of Memory Allocation, is intended to solve the problem that can't have high-performance, high usage and any memory size of application in the existing Memory Allocation concurrently.
On the one hand, a kind of method of Memory Allocation has been proposed, comprise: free memory block is concatenated in the corresponding idle chained list, the head pointer of described idle chained list is maintained in size in the idle chain gauge outfit array of N, the index of the corresponding idle chained list that head pointer points in the described idle chain gauge outfit array is n, and wherein said N is positive integer, and described n is 0 to N-1 integer, index is that the idle chained list of n is the free memory block of X for the serial connection size, and wherein X is more than or equal to 2
nAnd be less than or equal to 2
N+1-1; When the size of internal memory of application is Y, the idle chained list of definite first non-NULL from the idle chained list that index is m+1, between the idle chained list that index is the idle chained list of m+1 with index is n, wherein said m is less than or equal to N-1, and Y is more than or equal to 2
mAnd be less than or equal to 2
M+1-1; Extract first free memory block in the idle chained list of described first non-NULL, distribute first free memory block according to the size of the internal memory of described application.
In the possible implementation of the first of first aspect, when the described size of internal memory when application is Y, from the idle chained list that index is m+1, between the idle chained list that index is the idle chained list of m+1 with index is n, determine that the idle chained list of first non-NULL comprises: when the size of the internal memory of applying for 2
mTo 2
M+1In the time of between-1, from the idle chained list that index is m+1, at index, be between the idle chained list of m+1 and the idle chained list that index is n, determine the idle chained list of first non-NULL by the bitmap corresponding with described idle chain gauge outfit array, whether each in the wherein said bitmap indicates idle chained list corresponding in the described idle chain gauge outfit array is empty.
In conjunction with the possible implementation of the first of first aspect or first aspect, in the possible implementation of the second, also comprise: if there is unappropriated residue free memory in described first free memory block, be concatenated in the corresponding idle chained list according to free memory block corresponding to the described residue free memory of the large young pathbreaker of described residue free memory.
In conjunction with the possible implementation of the first of first aspect or first aspect or the possible implementation of the second of first aspect, in the third possible implementation, described free memory block is concatenated in the corresponding idle chained list comprises: the form with doubly linked list is concatenated into described free memory block in the idle chained list.
In conjunction with the possible implementation of the second of the possible implementation of the first of first aspect or first aspect or first aspect or the third possible implementation of first aspect, in the 4th kind of possible implementation, described free memory block is concatenated in the corresponding idle chained list comprises: when internal memory discharges, merging the continuous free memory block in address is new free memory block, described new free memory block is concatenated in the corresponding idle chained list, and the address of wherein said free memory block is stored in the control head of free memory block.
Second aspect, a kind of device of Memory Allocation has been proposed, comprise: the serial connection unit, be used for free memory block is concatenated into corresponding idle chained list, the head pointer of described idle chained list is maintained in size in the idle chain gauge outfit array of N, and the index of the corresponding idle chained list that head pointer points in the described idle chain gauge outfit array is n, wherein said N is positive integer, described n is 0 to N-1 integer, and index is that the idle chained list of n is the free memory block of X for the serial connection size, and wherein X is more than or equal to 2
nAnd be less than or equal to 2
N+1-1; Determining unit, be used for when the size of the internal memory of applying for is Y, be the idle chained list of determining first non-NULL between the idle chained list of m+1 and the idle chained list that index is n from the idle chained list that index is m+1, at index, wherein said m is less than or equal to N-1, and Y is more than or equal to 2
mAnd be less than or equal to 2
M+1-1; Extraction unit is used for extracting first free memory block of the idle chained list of described first non-NULL, distributes first free memory block according to the size of the internal memory of described application.
In the possible implementation of the first of second aspect, described determining unit is used for: when the size of internal memory of application 2
mTo 2
M+1In the time of between-1, from the idle chained list that index is m+1, at index, be between the idle chained list of m+1 and the idle chained list that index is n, determine the idle chained list of first non-NULL by the bitmap corresponding with described idle chain gauge outfit array, whether each in the wherein said bitmap indicates idle chained list corresponding in the described idle chain gauge outfit array is empty.
In conjunction with the possible implementation of the first of second aspect or second aspect, in the possible implementation of the second, described serial connection unit also is used for: if there is unappropriated residue free memory in described first free memory block, be concatenated in the corresponding idle chained list according to free memory block corresponding to the described residue free memory of the large young pathbreaker of described residue free memory.
In conjunction with the possible implementation of the first of second aspect or second aspect or the possible implementation of the second of second aspect, in the third possible implementation, described serial connection unit is used for: the form with doubly linked list is concatenated into idle chained list with described free memory block.
In conjunction with the possible implementation of the second of the possible implementation of the first of second aspect or second aspect or second aspect or the third possible implementation of second aspect, in the 4th kind of possible implementation, described serial connection unit specifically is used for: when internal memory discharges, merging the continuous free memory block in address is new free memory block, described new free memory block is concatenated in the corresponding idle chained list, and the address of wherein said free memory block is stored in the control head of free memory block.
This shows, the embodiment of the invention is owing to adopt idle chain gauge outfit array to assist Memory Allocation, thereby free memory block is concatenated into idle chain gauge outfit array according to size, can find at short notice the free memory block that satisfies the application size, and be conducive to improve performance by chained list serial connection free memory block.In addition, the embodiment of the invention can have the high performance while, has the characteristics that fragment is few, can apply for any memory size concurrently.
Description of drawings
In order to be illustrated more clearly in the technical scheme of the embodiment of the invention, the below will do to introduce simply to the accompanying drawing of required use in the embodiment of the invention, apparently, below described accompanying drawing only be some embodiments of the present invention, for those of ordinary skills, under the prerequisite of not paying creative work, can also obtain according to these accompanying drawings other accompanying drawing.
Fig. 1 is the process flow diagram according to the method for the Memory Allocation of the embodiment of the invention.
Fig. 2 illustrates the relation of idle linked list head array and bitmap in the Memory Allocation according to the embodiment of the invention.
Fig. 3 shows the structural representation according to free memory block in the Memory Allocation of the embodiment of the invention.
Fig. 4 is the structural representation according to the device of the Memory Allocation of the embodiment of the invention.
Fig. 5 is the structural representation of the device of Memory Allocation according to another embodiment of the present invention.
Embodiment
Below in conjunction with the accompanying drawing in the embodiment of the invention, the technical scheme in the embodiment of the invention is clearly and completely described, obviously, described embodiment is a part of embodiment of the present invention, rather than whole embodiment.Based on the embodiment among the present invention, the every other embodiment that those of ordinary skills obtain under the prerequisite of not making creative work should belong to the scope of protection of the invention.
Describe the method for the Memory Allocation of the embodiment of the invention in detail below with reference to accompanying drawing.As shown in Figure 1, may further comprise the steps.
11, free memory block is concatenated in the corresponding idle chained list, the head pointer of described idle chained list is maintained in size in the idle chain gauge outfit array of N, the index of the corresponding idle chained list that head pointer points in the described idle chain gauge outfit array is n, wherein said N is positive integer, described n is 0 integer to (N-1), and index is that the idle chained list of n is used for the big or small X(2 of being of serial connection
nBit≤X≤2
N+1-1 bit) free memory block.
Particularly, have a plurality of idle chained lists in the system, the head pointer of this free time chained list is maintained in the idle chain gauge outfit array.For example, the size of this idle chain gauge outfit array is N, total N the idle chained list of namely explanation.Be that the idle chain gauge outfit array of N is according to from small to large serial number, for example from 0 to N-1 with size.Further, can be with the index of serial number n as idle chained list, to distinguish the free memory block that is connected in series in each idle chained list.Can be X(2 with its size
nBit≤X≤2
N+1-1 bit) free memory block is concatenated in the idle chained list that index is n.For example, size is that to be concatenated into index be in 0 the idle chained list for the free memory block of 1 bit; Size is that to be concatenated into index be in 1 the idle chained list to the free memory block of 2 or 3 bits; Size is that to be concatenated into index be in 2 the idle chained list to the free memory block of 4 to 7 bits; By that analogy, size is 2
nTo 2
N+1The free memory block of-1 bit is concatenated in the idle chained list that index is n.
Like this, all free memory blocks can be concatenated in the different idle chained lists, but by single the array unified management of idle chain gauge outfit and serial connection, the application of being convenient to search free memory block and arbitrary size free memory block.
In addition, free memory block can also doubly linked list form be concatenated in the idle chained list, like this when a certain free memory block inserts idle chained list or deletes from idle chained list, the relative free memory block that is serially connected in the same idle chained list can be connected in series fast, to avoid because the adverse effect that the movement of free memory block causes performance.
12, as the big or small Y((2 of the internal memory of applying for
mBit≤X≤2
M+1-1 bit) time, for the idle chained list of (m+1), at the idle chained list of index for definite first non-NULL between the idle chained list of (m+1) and the idle chained list that index is n, wherein said m is less than or equal to (N-1) from index.
Particularly, when the size of the internal memory that determine to need application 2
mBit to 2
M+1Between-1 bit when (wherein, m is less than or equal to (N-1)), can be from index for the idle chained list of (m+1), between index is for the idle chained list of (m+1) and idle chained list that index is n, search.For example, from index (m+1), according to the order of from small to large index, i.e. (m+2), (m+3) ..., until determine the idle chained list of first non-NULL.
Need to prove that the free memory block size that is connected in series in the idle chained list of index greater than m is necessarily greater than 2
M+1-1 bit.That is to say that the free memory block size that begins to find for the idle chained list of (m+1) from index can satisfy the size 2 of the internal memory of request
mBit to 2
M+1-1 bit.So, the free memory block that is connected in series the idle chained list of the non-NULL that obtains for the idle chained list of (m+1) begins to search one by one from index necessarily satisfies the requirement of the internal memory of request.
Further, in order to reduce the time of the idle chained list of determining first non-NULL, can introduce bitmap (bitmap), this bitmap has N position, identify respectively the state of N corresponding in a idle chain gauge outfit array idle chained list, for example " 0 " is empty idle chained list, the idle chained list of " 1 " expression non-NULL.Therefore, when the size of internal memory of application 2
mTo 2
M+1In the time of between-1 bit, from index for the idle chained list of (m+1), between index is for the idle chained list of (m+1) and idle chained list that index is n, whether determine the idle chained list of first non-NULL by each value among the bitmap corresponding with described idle chain gauge outfit array, be empty because each in the bitmap indicates idle chained list corresponding in the described idle chain gauge outfit array.For example, can begin to determine first " 1 " for the position bitmap corresponding to the idle chained list of (m+1) from index, the idle chained list that this value indicates for the position of " 1 " is exactly the idle chained list of first non-NULL of determining.
13, extract first free memory block in the idle chained list of described first non-NULL, distribute first free memory block according to the size of the internal memory of described application.
If there is unappropriated residue free memory in described first free memory block, be concatenated in the corresponding idle chained list according to free memory block corresponding to the described residue free memory of the large young pathbreaker of described residue free memory.
For example, the memory size Y of application is 10 bits, because 10 bits are 2
3Bit to 2
3+1Between-1 bit, namely m is 3.The method of determining according to step 12 is the idle chained list that 4 idle chained list begins to search first non-NULL from index.For example determine that index is 4 idle chained list for empty, index are that 5 idle chained list is non-NULL, then from index is 5 idle chained list, determine first free memory block, be assumed to be 32 bits.So, extract this 32 bit, give the content of application with 10 Bit Allocation in Discrete wherein, remain free memory this moment is 22 bits.This residue free memory is concatenated in the corresponding idle chained list as new free memory block, and for example 22 bits are 2
4Bit to 2
4+1Between-1 bit, namely m is 4, that is to say, it is in 4 the idle chained list that this new free memory block will be concatenated into index.As previously mentioned and since this index be before 4 the idle chained list for empty, after inserting this new free memory block, this index is that 4 idle chained list will be for not empty, therefore the position in the corresponding bitmap will become " 1 " from " 0 ".
Be appreciated that, when the new free memory block that forms after distributing internal memory is concatenated in the corresponding idle chained list, if idle chained list that should correspondence is former not to be empty (namely having free memory block), so this new free memory block just sequentially be concatenated into the idle chained list of this correspondence at last.
In addition, owing to preserve the start address of this free memory block and the information such as start address of the free memory block that front and back are close in the control head of each free memory block, therefore each when internal memory discharges, the free memory block that the address links to each other will be merged into new free memory block, and be concatenated in the corresponding idle chained list, the free memory block before merge this moment will be deleted from the idle chained list at original place.
This shows that the embodiment of the invention can find the free memory block that satisfies the application size at short notice, and be conducive to improve performance by chained list serial connection free memory block.In addition, the embodiment of the invention can have the high performance while, has the characteristics that fragment is few, can apply for any memory size concurrently.
The below is take maximum memory as the 4G bit as example, and the method for the Memory Allocation of the embodiment of the invention is specifically described.
Usually, adopt the size of the internal memory of binary representation application, 0b{0}1xxx for example, wherein { 0} represents that 1 front may have 0 or a plurality of zero.Understand easily, no matter what content the xxx of 1 back is, all becomes 0 if become 10, xxx with 1, and 10yyy is then always arranged〉1xxx(here yyy represent that the corresponding position of xxx all becomes 0).Be in the situation of 4G bit at maximum memory, the size of internal memory mostly is 32 bits most.
Leftmost 1 the subscript that usually, can directly obtain all free memory blocks by assembly instruction (for example, 0-31).In an idle chain gauge outfit array, safeguard the head pointer of idle chained list, with leftmost 1 subscript (in assembly instruction, from a high position to the low level, being followed successively by 31-0) of the free memory block array indexing as idle chained list in the idle chain gauge outfit array, be about to the identical free memory block of all subscripts of leftmost 1 and be articulated in the same idle chained list.As shown in Figure 2, index is that the free memory block size that 2 idle chained list can articulate is 4 bit to 7 bits; Index is that the free memory block size that the idle chained list of n can articulate is 2
nBit to 2
N+1-1 bit.
When the application size is the internal memory of uiSize, at first utilize assembly instruction to obtain leftmost 1 subscript, be assumed to m.For guaranteeing that first free memory block in the idle chained list just satisfies uiSize, be that m+1 begins search from index then.If index is the idle chained list of m+1 is not empty, then get first free memory block in this free time chained list.If index is the idle chained list of m+1 is empty, judge that then index is the idle chained list of m+2, the like, until find idle chained list or the index of non-NULL to reach 31.Here, m is less than or equal to 30.
For avoiding judging that step by step whether idle chained list is empty, considers the bitmap global variable (for example, its subscript value is followed successively by 0-31 from a high position to the low level) of one 32 of definition.If index is the idle chained list non-NULL of m, then bitmap lower be designated as m the position by set, otherwise reset.Bitmap lower is designated as 31 position and directly puts 1 when initialization.So be the idle chained list that the idle chained list of m+1 begins to search first non-NULL from index, for example can be at first with the copy of bitmap 0 to the equal reset in m position, then obtain leftmost 1 subscript of copy, if be not equal to 31, be the array indexing of the idle chained list of first non-NULL.If hardware supported, bitmap also can be processed by the mode of obtaining rightmost 1.
All free memory blocks all are serially connected in the idle chained list with the doubly linked list form.If first free memory block that obtains from idle chained list is larger, after namely being partitioned into a size and being the memory block of uiSize, remaining residue free memory still can be done one time smallest allocation at least, as shown in Figure 3, namely remain the size of free memory greater than the size of control head (CtrlHead), the new free memory block adjustment that then will remain free memory formation is concatenated in the corresponding idle chained list.
Generally speaking, free memory all carries control head, and this control head can be pointer or the index of physical memory control head or Memory control head.Owing to store start address and size, the state (such as taking or the free time) of this free memory block and the address of the free memory block that front and back are close to etc. of this free memory block in the control head, therefore can in the internal memory dispose procedure, free memory block can be merged according to address above mentioned information.
Below in conjunction with the device of Fig. 4 description according to the Memory Allocation of the embodiment of the invention.
In Fig. 4, the device 40 of Memory Allocation comprises serial connection unit 41, determining unit 42 and extraction unit 43.
Wherein, serial connection unit 41 is used for free memory block is concatenated into corresponding idle chained list, the head pointer of described idle chained list is maintained in size in the idle chain gauge outfit array of N, the index of the corresponding idle chained list that head pointer points in the described idle chain gauge outfit array is n, wherein said N is positive integer, described n is 0 to N-1 integer, and index is that the idle chained list of n is the free memory block of X for the serial connection size, and wherein X is more than or equal to 2
nAnd be less than or equal to 2
N+1-1.
Alternatively, there is unappropriated residue free memory if serial connection unit 41 also is used for described first free memory block, is concatenated in the corresponding idle chained list according to free memory block corresponding to the described residue free memory of the large young pathbreaker of described residue free memory.
Alternatively, serial connection unit 41 is used for the form of doubly linked list described free memory block being concatenated into idle chained list.
Alternatively, serial connection unit 41 is concrete for when internal memory discharges, merging the continuous free memory block in address is new free memory block, and described new free memory block is concatenated in the corresponding idle chained list, and the address of wherein said free memory block is stored in the control head of free memory block.
Determining unit 42 is used for when the size of the internal memory of application is Y, from the idle chained list that index is m+1, at index, it is the idle chained list of determining first non-NULL between the idle chained list of m+1 and the idle chained list that index is N, wherein said m is less than or equal to N-1, and Y is more than or equal to 2
mAnd be less than or equal to 2
M+1-1.
Further, determining unit 42 can be used for when the size of the internal memory of application is Y, from the idle chained list that index is m+1, at index, be between the idle chained list of m+1 and the idle chained list that index is n, determine the idle chained list of first non-NULL by the bitmap corresponding with described idle chain gauge outfit array, whether each in the wherein said bitmap indicates idle chained list corresponding in the described idle chain gauge outfit array is empty.
Extraction unit 43 is used for extracting first free memory block of the idle chained list of described first non-NULL, distributes described first free memory block according to the size of the internal memory of described application.
This shows that the embodiment of the invention can find the free memory block that satisfies the application size at short notice, and be conducive to improve performance by chained list serial connection free memory block.In addition, the embodiment of the invention can have the high performance while, has the characteristics that fragment is few, can apply for any memory size concurrently.
Fig. 5 is the schematic block diagram of device 50 another embodiment of Memory Allocation of the present invention.Device 50 comprises processor 51, storer 52, input equipment 53 and output device 54 etc., intercoms mutually by bus.Wherein, processor 51 calls the program of storer 52 storages, can carry out each step of above-mentioned memory allocation method embodiment.
Alternatively, the device 50 of Memory Allocation can also comprise input equipment 53 and output device 54.
For example, input equipment 53 can comprise any suitable devices such as keyboard, mouse, be used for to receive user's input or from the input of other equipment, and sends to processor 51.
For example, output device 54 is used for the result's output with the Bit Allocation in Discrete of sound signal, can be display, printer etc.
Should be understood that in embodiments of the present invention, term " and/or " only be a kind of incidence relation of describing affiliated partner, can there be three kinds of relations in expression.For example, A and/or B can represent: individualism A exists A and B, these three kinds of situations of individualism B simultaneously.In addition, character "/" represents that generally forward-backward correlation is to liking a kind of relation of "or" herein.
Those of ordinary skills can recognize, unit and the algorithm steps of each example of describing in conjunction with embodiment disclosed herein can be realized with the combination of electronic hardware or computer software and electronic hardware.These functions are carried out with hardware or software mode actually, depend on application-specific and the design constraint of technical scheme.The professional and technical personnel can specifically should be used for realizing described function with distinct methods to each, but this realization should not thought and exceeds scope of the present invention.
The those skilled in the art can be well understood to, and is the convenience described and succinct, and the specific works process of the system of foregoing description, device and unit can with reference to the corresponding process among the preceding method embodiment, not repeat them here.
In several embodiment that the application provides, should be understood that disclosed system, apparatus and method can realize by another way.For example, device embodiment described above only is schematic, for example, the division of described unit, only be that a kind of logic function is divided, during actual the realization other dividing mode can be arranged, for example a plurality of unit or assembly can in conjunction with or can be integrated into another system, or some features can ignore, or do not carry out.Another point, the shown or coupling each other discussed or direct-coupling or communication connection can be by some interfaces, indirect coupling or the communication connection of device or unit can be electrically, machinery or other form.
Described unit as separating component explanation can or can not be physically to separate also, and the parts that show as the unit can be or can not be physical locations also, namely can be positioned at a place, perhaps also can be distributed on a plurality of network element.Can select according to the actual needs wherein some or all of unit to realize the purpose of present embodiment scheme.
In addition, each functional unit in each embodiment of the present invention can be integrated in the processing unit, also can be that the independent physics of unit exists, and also can be integrated in the unit two or more unit.
If described function realizes with the form of SFU software functional unit and during as independently production marketing or use, can be stored in the computer read/write memory medium.Based on such understanding, the part that technical scheme of the present invention contributes to prior art in essence in other words or the part of this technical scheme can embody with the form of software product, this computer software product is stored in the storage medium, comprise that some instructions are with so that a computer equipment (can be personal computer, server, the perhaps network equipment etc.) carry out all or part of step of the described method of each embodiment of the present invention.And aforesaid storage medium comprises: the various media that can be program code stored such as USB flash disk, portable hard drive, ROM, RAM, magnetic disc or CD.
The above; be the specific embodiment of the present invention only, but protection scope of the present invention is not limited to this, anyly is familiar with those skilled in the art in the technical scope that the present invention discloses; can expect easily changing or replacing, all should be encompassed within protection scope of the present invention.Therefore, protection scope of the present invention should be as the criterion by described protection domain with claim.
Claims (10)
1. the method for a Memory Allocation is characterized in that, comprising:
Free memory block is concatenated in the corresponding idle chained list, the head pointer of described idle chained list is maintained in size in the idle chain gauge outfit array of N, the index of the corresponding idle chained list that head pointer points in the described idle chain gauge outfit array is n, wherein said N is positive integer, described n is 0 to N-1 integer, index is that the idle chained list of N is the free memory block of X for the serial connection size, and wherein X is more than or equal to 2
nAnd be less than or equal to 2
N+1-1;
When the size of internal memory of application is Y, the idle chained list of definite first non-NULL from the idle chained list that index is m+1, between the idle chained list that index is the idle chained list of m+1 with index is n, wherein said m is less than or equal to N-1, and Y is more than or equal to 2
mAnd be less than or equal to 2
M+1-1;
Extract first free memory block in the idle chained list of described first non-NULL, distribute described first free memory block according to the size of the internal memory of described application.
2. method according to claim 1, it is characterized in that, when the described size of internal memory when application was Y, the idle chained list of definite first non-NULL comprised from the idle chained list that index is m+1, between the idle chained list that index is the idle chained list of m+1 with index is n:
When the size of the internal memory of applying for is Y, from the idle chained list that index is m+1, at index, be between the idle chained list of m+1 and the idle chained list that index is n, determine the idle chained list of first non-NULL by the bitmap corresponding with described idle chain gauge outfit array, whether each in the wherein said bitmap indicates idle chained list corresponding in the described idle chain gauge outfit array is empty.
3. method according to claim 1 and 2 is characterized in that, also comprises:
If there is unappropriated residue free memory in described first free memory block, be concatenated in the corresponding idle chained list according to free memory block corresponding to the described residue free memory of the large young pathbreaker of described residue free memory.
4. each described method in 3 according to claim 1 is characterized in that described free memory block is concatenated in the corresponding idle chained list comprises:
Form with doubly linked list is concatenated into described free memory block in the idle chained list.
5. each described method in 4 according to claim 1 is characterized in that described free memory block is concatenated in the corresponding idle chained list comprises:
When internal memory discharged, merging the continuous free memory block in address was new free memory block, and described new free memory block is concatenated in the corresponding idle chained list, and the address of wherein said free memory block is stored in the control head of free memory block.
6. the device of a Memory Allocation is characterized in that, comprising:
The serial connection unit, be used for free memory block is concatenated into corresponding idle chained list, the head pointer of described idle chained list is maintained in size in the idle chain gauge outfit array of N, the index of the corresponding idle chained list that head pointer points in the described idle chain gauge outfit array is n, wherein said N is positive integer, described n is 0 to N-1 integer, and index is that the idle chained list of n is the free memory block of X for the serial connection size, and wherein X is more than or equal to 2
nAnd be less than or equal to 2
N+1-1;
Determining unit, be used for when the size of the internal memory of applying for is Y, be the idle chained list of determining first non-NULL between the idle chained list of m+1 and the idle chained list that index is n from the idle chained list that index is m+1, at index, wherein said m is less than or equal to N-1, and Y is more than or equal to 2
mAnd be less than or equal to 2
M+1-1;
Extraction unit is used for extracting first free memory block of the idle chained list of described first non-NULL, distributes described first free memory block according to the size of the internal memory of described application.
7. device according to claim 6 is characterized in that, described determining unit specifically is used for:
When the size of the internal memory of applying for is Y, from the idle chained list that index is m+1, at index, be between the idle chained list of m+1 and the idle chained list that index is n, determine the idle chained list of first non-NULL by the bitmap corresponding with described idle chain gauge outfit array, whether each in the wherein said bitmap indicates idle chained list corresponding in the described idle chain gauge outfit array is empty.
8. according to claim 6 or 7 described devices, it is characterized in that described serial connection unit also is used for:
If there is unappropriated residue free memory in described first free memory block, be concatenated in the corresponding idle chained list according to free memory block corresponding to the described residue free memory of the large young pathbreaker of described residue free memory.
9. each described device in 8 according to claim 6 is characterized in that described serial connection unit specifically is used for:
Form with doubly linked list is concatenated into described free memory block in the idle chained list.
10. each described device in 9 according to claim 6 is characterized in that described serial connection unit specifically is used for:
When internal memory discharged, merging the continuous free memory block in address was new free memory block, and described new free memory block is concatenated in the corresponding idle chained list, and the address of wherein said free memory block is stored in the control head of free memory block.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210316944.0A CN102866954B (en) | 2012-08-31 | 2012-08-31 | The method of Memory Allocation and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210316944.0A CN102866954B (en) | 2012-08-31 | 2012-08-31 | The method of Memory Allocation and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102866954A true CN102866954A (en) | 2013-01-09 |
| CN102866954B CN102866954B (en) | 2015-11-25 |
Family
ID=47445833
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201210316944.0A Expired - Fee Related CN102866954B (en) | 2012-08-31 | 2012-08-31 | The method of Memory Allocation and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102866954B (en) |
Cited By (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103970680A (en) * | 2014-04-28 | 2014-08-06 | 上海华为技术有限公司 | Memory management method and device and embedded system |
| WO2016192025A1 (en) * | 2015-06-01 | 2016-12-08 | SZ DJI Technology Co., Ltd. | Systems and methods for memory architecture |
| CN106776375A (en) * | 2016-12-27 | 2017-05-31 | 东方网力科技股份有限公司 | Data cache method and device inside a kind of disk |
| CN106980578A (en) * | 2017-04-01 | 2017-07-25 | 广东浪潮大数据研究有限公司 | A kind of memory block management method and system |
| CN108108307A (en) * | 2016-11-24 | 2018-06-01 | 中移（杭州）信息技术有限公司 | A kind of method for processing resource and terminal |
| CN108874532A (en) * | 2017-06-01 | 2018-11-23 | 北京旷视科技有限公司 | Memory allocation method and equipment |
| CN110532198A (en) * | 2019-09-09 | 2019-12-03 | 成都西山居互动娱乐科技有限公司 | A kind of method and device of memory allocation |
| CN112328389A (en) * | 2020-10-12 | 2021-02-05 | 长沙新弘软件有限公司 | Memory allocation method for adding and deleting nodes in binary tree |
| CN112380004A (en) * | 2020-11-04 | 2021-02-19 | 成都佰维存储科技有限公司 | Memory management method and device, computer readable storage medium and electronic equipment |
| CN113051081A (en) * | 2021-06-01 | 2021-06-29 | 广东省新一代通信与网络创新研究院 | Event state management method, system and storage medium based on memory pool |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1963788A (en) * | 2005-11-08 | 2007-05-16 | 中兴通讯股份有限公司 | A managing method for EMS memory |
| CN101266575A (en) * | 2007-03-13 | 2008-09-17 | 中兴通讯股份有限公司 | Method for enhancing memory pool utilization ratio |
| CN101382916A (en) * | 2007-09-06 | 2009-03-11 | 大唐移动通信设备有限公司 | Method for managing embedded system memory |
-
2012
- 2012-08-31 CN CN201210316944.0A patent/CN102866954B/en not_active Expired - Fee Related
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1963788A (en) * | 2005-11-08 | 2007-05-16 | 中兴通讯股份有限公司 | A managing method for EMS memory |
| CN101266575A (en) * | 2007-03-13 | 2008-09-17 | 中兴通讯股份有限公司 | Method for enhancing memory pool utilization ratio |
| CN101382916A (en) * | 2007-09-06 | 2009-03-11 | 大唐移动通信设备有限公司 | Method for managing embedded system memory |
Cited By (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103970680A (en) * | 2014-04-28 | 2014-08-06 | 上海华为技术有限公司 | Memory management method and device and embedded system |
| US10635633B2 (en) | 2015-06-01 | 2020-04-28 | SZ DJI Technology Co., Ltd. | Systems and methods for memory architecture |
| WO2016192025A1 (en) * | 2015-06-01 | 2016-12-08 | SZ DJI Technology Co., Ltd. | Systems and methods for memory architecture |
| CN108108307A (en) * | 2016-11-24 | 2018-06-01 | 中移（杭州）信息技术有限公司 | A kind of method for processing resource and terminal |
| CN106776375A (en) * | 2016-12-27 | 2017-05-31 | 东方网力科技股份有限公司 | Data cache method and device inside a kind of disk |
| CN106980578A (en) * | 2017-04-01 | 2017-07-25 | 广东浪潮大数据研究有限公司 | A kind of memory block management method and system |
| CN108874532B (en) * | 2017-06-01 | 2020-11-06 | 北京旷视科技有限公司 | Memory allocation method and device |
| CN108874532A (en) * | 2017-06-01 | 2018-11-23 | 北京旷视科技有限公司 | Memory allocation method and equipment |
| CN110532198A (en) * | 2019-09-09 | 2019-12-03 | 成都西山居互动娱乐科技有限公司 | A kind of method and device of memory allocation |
| CN110532198B (en) * | 2019-09-09 | 2023-08-08 | 成都西山居互动娱乐科技有限公司 | Storage space allocation method and device |
| CN112328389A (en) * | 2020-10-12 | 2021-02-05 | 长沙新弘软件有限公司 | Memory allocation method for adding and deleting nodes in binary tree |
| CN112328389B (en) * | 2020-10-12 | 2024-04-30 | 长沙新弘软件有限公司 | Memory allocation method for adding and deleting nodes in binary tree |
| CN112380004A (en) * | 2020-11-04 | 2021-02-19 | 成都佰维存储科技有限公司 | Memory management method and device, computer readable storage medium and electronic equipment |
| CN112380004B (en) * | 2020-11-04 | 2023-06-13 | 成都佰维存储科技有限公司 | Memory management method, memory management device, computer readable storage medium and electronic equipment |
| CN113051081A (en) * | 2021-06-01 | 2021-06-29 | 广东省新一代通信与网络创新研究院 | Event state management method, system and storage medium based on memory pool |
| CN113051081B (en) * | 2021-06-01 | 2021-10-29 | 广东省新一代通信与网络创新研究院 | Event state management method, system and storage medium based on memory pool |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102866954B (en) | 2015-11-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102866954B (en) | The method of Memory Allocation and device | |
| CN102707990B (en) | Container based processing method and device | |
| EP2288975B1 (en) | Method for optimizing cleaning of maps in flashcopy cascades containing incremental maps | |
| US11874815B2 (en) | Key-value storage device and method of operating the same | |
| CN105224237A (en) | A kind of date storage method and device | |
| US10802923B2 (en) | Method and apparatus for incremental backup based on file paths and a prefix tree | |
| US9280370B2 (en) | System structure management device, system structure management method, and program | |
| US10970254B2 (en) | Utilization of tail portions of a fixed size block in a deduplication environment by deduplication chunk virtualization | |
| CN103995855A (en) | Method and device for storing data | |
| CN103942292A (en) | Virtual machine mirror image document processing method, device and system | |
| CN108345433B (en) | Method, memory system and product for maximized deduplication memory | |
| CN102142032A (en) | Method and system for reading and writing data of distributed file system | |
| CN101826109A (en) | Large-capacity file splitting method, device and system | |
| CN102945275B (en) | File defragmentation method, device and equipment | |
| CN103902618A (en) | File search method and device | |
| CN103530206B (en) | A kind of method and apparatus of date restoring | |
| CN104750432A (en) | Data storage method and device | |
| US11287996B2 (en) | Method, device and computer program product for storing data | |
| US20160253119A1 (en) | Storage system, storage method, and recording medium | |
| EP4418119A1 (en) | Multi-data sending method, apparatus and device based on columnar data scanning, and multi-data receiving method, apparatus and device based on columnar data scanning | |
| CN103905310A (en) | Message processing method and forwarding device | |
| CN103559106B (en) | A kind of backup method of data, Apparatus and system | |
| CN104932982A (en) | Message access memory compiling method and related apparatus | |
| CN104246716A (en) | Method and device for processing storage space object | |
| CN105373421A (en) | A terminal and a method of processing data in the terminal |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20151125 Termination date: 20160831 |