FORM 2
The Patent Act 1970
(39 of 1970)
&
The Patent Rules, 2005

COMPLETE SPECIFICATION
(SEE SECTION 10 AND RULE 13)

TITLE OF THE INVENTION

“Dynamic Memory Allocation”

APPLICANTS:

Name Nationality Address
Alcatel Lucent France 54 rue de la Boétie, 75008 Paris, France

The following specification particularly describes and ascertains the nature of this invention and the manner in which it is to be performed:-

FIELD OF INVENTION
[001] This invention relates to memory allocation systems and, more particularly but not exclusively, to dynamic memory allocation in memory allocation systems.

BACKGROUND
[002] This section introduces aspects that may be helpful in facilitating a better understanding of the invention. Accordingly, the statements of this section are to be read in this light and are not to be understood as admissions about what is in the prior art or what is not in the prior art.
[003] Dynamic memory allocation is the allocation of memory for use by an application during the runtime of that application. Dynamic memory allocation is a way of distributing ownership of the limited memory resources among many sub-modules of the application. Problems that may arise during fulfilling memory allocation requests include data fragmentation and the time taken for allocating and de-allocating memory. Fragmentation is a phenomenon in which memory space is used inefficiently, reducing storage capacity and performance. Fragmentation is also denotes the memory space that is wasted by not being used for long periods of time. Fragmentation should be avoided while allocating memory to applications. Also, the time taken for allocating and de-allocating memory should be bounded. The application requesting for memory should be allocated the required memory as soon as possible. Once the need for memory is satisfied, the memory should be freed as soon as possible so that the de-allocated memory can be allocated to other applications needing memory.
[004] Present memory allocation systems cause fragmentation to occur in the memory when the requested memory is a little larger than a small block of available memory, but the requested memory is smaller than a large block of available memory. For example, an application that requests 74KB of memory would be allocated 128KB even though 64 KB of memory is available, thereby resulting in a waste of 54KB of memory. Fragmentation can occur when memory greater than required is allocated to satisfy a request. Fragmentation may also occur when memory is free to satisfy a request, but the memory is split into two or more distinct chunks, none of which is big enough to satisfy the request alone. The present memory allocation systems are not suitable for use in real time environments requiring efficient dynamic memory allocation since present systems causes fragmentation and memory allocation and de-allocation time are not bounded. The time taken for allocating and de-allocating memory cannot be pre-determined and the time varies based on the load of the computing system.

SUMMARY
[005] These and other aspects of the embodiments herein will be better appreciated and understood when considered in conjunction with the following description and the accompanying drawings.
[006] In view of the foregoing, an embodiment herein provides a method for memory allocation in a computing system comprising steps of searching a cache memory for a required memory, and the no. of memory blocks present in the cache is based on memory access frequency. If the required memory is not present in the cache memory, a heap memory is searched for the required memory in the corresponding partition where the memory block are grouped based on memory access frequency. If the required memory is not available in the heap memory then memory from the cache is freed to obtain the required memory. If the required memory is not freed from the cache, then the required memory is obtained from the plurality of heap memories. The size of the memory searched in the cache and heap memory is equal to twice the frequency of memory access. The located memory is allocated to the requesting application. The cache memory is partitioned into two parts and memory is freed from the cache by removing data from the cache based on recency of access of data in the cache. The heap memory may be partitioned into multiple parts and the required memory grouped into multiple groups, wherein size of the multiple partitions change dynamically depending on the frequency of memory access and individual partitions satisfy memory requirement of individual group of the required memory.
[007] In view of the foregoing, an embodiment herein provides a module for performing memory allocation comprising steps of searching a cache memory for a required memory, based on memory access frequency. If the required memory is not present in the cache memory, a heap memory is searched for the required memory, based on memory access frequency. If the required memory is not available in the heap memory then memory from the cache is freed to obtain the required memory. If the required memory is not freed from the cache, then the required memory is obtained from the plurality of heap memories. The located memory is allocated to the requesting application. The module is adapted to maintain statistics of the allocated memory, wherein the statistics comprise address of the allocated memory, size of the allocated memory and the memory access frequency. The size of the memory searched is equal to twice the frequency of memory access. The module is adapted to free memory from the cache by removing data from the cache based on recency of access of data in the cache.
[008] In view of the foregoing, an embodiment herein provides a method for freeing memory in a computing system, the computing system further comprising of a cache memory and a heap memory. The method comprising steps of searching the cache memory to free specific blocks of memory and releasing the freed memory from the cache memory to the heap memory, depending on memory access duration value. The predetermined blocks of memory are released to the heap memory when the memory access duration value reaches a predetermined value. The predetermined blocks of memory are also released to the heap memory when percentage of memory usage reaches a predetermined value.
[009] In view of the foregoing, an embodiment herein provides a memory releasing module for freeing memory in a computing system, the computing system further comprising of a cache memory and a heap memory. The memory releasing module comprises atleast one means adapted for searching the cache memory to free specific blocks of memory and releasing the freed memory from the cache to the heap memory, depending on memory access duration value. The module is adapted to release predetermined blocks of memory to the heap memory when the memory access duration value reaches a predetermined value. The module is also adapted to release predetermined blocks of memory to the heap memory when percentage of memory usage reaches a predetermined value.

BRIEF DESCRIPTION OF THE FIGURES
[0010] Some embodiments of apparatus and/or methods in accordance with embodiments of the present invention are now described, by way of example only, and with reference to the accompanying drawings, in which:
[0011] Figure 1 schematically illustrates a processor connected to cache and heap memory, according to an embodiment herein;
[0012] Figure 2 schematically illustrates a flowchart depicting a method for allocation of memory, according to an embodiment herein;
[0013] Figures 3a and 3b schematically illustrate a flowchart depicting a method for searching and allocating memory dynamically, according to an embodiment herein; and
[0014] Figure 4 schematically illustrates a flowchart depicting a method to de-allocate memory and release memory to heap, according to an embodiment herein.

DESCRIPTION OF EMBODIMENTS
[0015] The embodiments herein and the various features and advantageous details thereof are explained more fully with reference to the non-limiting embodiments that are illustrated in the accompanying drawings and detailed in the following description. Descriptions of well-known components and processing techniques are omitted so as to not unnecessarily obscure the embodiments herein. The examples used herein are intended merely to facilitate an understanding of ways in which the embodiments herein may be practiced and to further enable those of skill in the art to practice the embodiments herein. Accordingly, the examples should not be construed as limiting the scope of the embodiments herein.
[0016] The embodiments herein achieve adaptive memory allocation by using a combination of cache memory and heap memory. The cache memory performs memory allocation and de-allocation requests, and the heap memory prevents data in the memory from being fragmented. After the allocated memory is used, the memory is released from the cache to the heap. Referring now to the drawings, and more particularly to FIGS. 1 through 4, where similar reference characters denote corresponding features consistently throughout the figures, there are shown embodiments.
[0017] Figure 1 schematically illustrates a processor connected to cache and heap memories, according to an embodiment herein. When the processor 104 needs to read from or write to a location in the main memory 106, the processor 104 first checks whether the required data is present in the cache memory 101. If the data is present in the cache memory 101, the processor 104 immediately reads the data from cache memory 101. A heap memory 102 is an internal memory pool used to dynamically allocate memory as needed. In various embodiments, a plurality of heap memories may also be present. The heap memory 102 is the memory used by applications to store data used by operations in the application. The memory allocator 103 takes memory requests from applications and allocates the available memory to the particular application. Applications send requests to the memory allocator 103 for memory allocation. On receiving a request for memory, the memory allocator 103 checks the cache memory 101 and the heap memory 102 to determine if the required memory is present. On locating the required memory, the memory allocator 103 calculates the access frequency of the corresponding memory block. If the memory block size is equal to 2 * frequency of memory access, then the memory allocator 103 allocates the required memory to the particular application. If the memory block size is less than 2 * frequency of memory access, then the memory allocator 103 issues a request to the heap memory 102 for the required memory. For example, if an application performing mathematical operations needs 1 Megabyte (MB) of memory, then the application requests the memory allocator 103 for 1 MB of memory. The memory allocator 103 checks the cache memory 101 and the heap memory 102 to determine if 1 MB of memory is available. If the memory allocator 103 finds the required memory in the cache memory 101, then the memory allocator 103 calculates the access frequency of the corresponding memory block. If the memory block size is equal to 2 * frequency of memory access, then the memory allocator 103 allocates the required memory to the particular application. For example, if the access frequency is 5 then the cache memory 101 should have 10 blocks of 1MB memory. If there are 10 blocks of 1MB memory, then the memory allocator 103 allocates the required memory to the application from the cache memory 101. If 10 blocks of 1MB memory is not available in the cache memory 102, then the memory allocator 103 searches for the required memory in the heap memories 102. For example, if 10 blocks of 1MB memory is required and there are only 8 blocks of 1MB memory in the cache memory 101, then the memory allocator 103 requests for the remaining 2MB of memory from the heap memory 102. The heap memory 102 may also be partitioned into multiple parts. The size of each partition depends on the frequency of memory access. For example, the heap memory 102 may be partitioned into a partition H1, a second partition H2 and a third partition H3. Then, the blocks of required memory is also split into three groups. Here the first group of required memory is assigned from H1, the second group of required memory is assigned from H2 and the third group of required memory is assigned from H3. If any partition in the heap memory 102 does not have the required memory, then memory is taken from adjacent heap memory 102 based on the frequency of memory access. Once the required memory has been allocated to the requesting application the memory allocator 103 maintains the statistics of the partitioned heap memory 102 and the grouped required memory. After the application has completed performing an operation, the application sends a request to free the memory allocated to the application. The memory releasing module 105 releases the memory that was requested to be freed.
[0018] Figure 2 schematically illustrates a flowchart depicting a method to allocate memory to applications. Applications send (201) a request for memory to the memory allocator 103. On receiving a request for memory, the memory allocator 103 checks (202) the cache memory 101 to determine if the required memory is present in the cache memory 101. The cache memory 101 may be partitioned into a first partition (P1) and a second partition (P2). The first partition (P1) and the second partition (P2) may be of equal sizes or unequal sizes. For example, if the total cache memory 101 is of size 10 MB with memory blocks of different sizes, then the cache memory 101 may be partitioned into P1 of size 4 MB and P2 of size 6 MB. The memory allocator 103 first checks in P1 for the required memory based on the memory access frequency. If the memory blocks present in P1 is equal to 2 * frequency of memory access, then the memory allocator 103 allocates the required memory from P1 to the particular application. If the required memory is not present in P1, then the memory allocator 103 checks for the required memory in P2. If the memory blocks present in P2 is equal to 2 * frequency of memory access, then the memory allocator 103 moves the required memory blocks from P2 to P1. In another embodiment the cache may be partitioned into more than two partitions. On locating the required memory, the memory allocator 103 allocates (205) the required memory to the particular application. If the required memory is not present in the cache memory 101, then the memory allocator 103 checks (203) for the required memory in the heap memory 102 based on the memory access frequency. On locating the required memory in the heap memory 102, the memory allocator 103 allocates (205) the required memory to the particular application and the remaining memory is cached. If the required memory is not present in the heap memory 102, then the memory allocator 103 allocates (204) the required memory to the application from other adjacent heap memories 102 or by freeing memory from the cache memory 101. The various actions in the method 200 may be performed in the order presented, in a different order, or simultaneously. Further, in some embodiments, some actions listed in FIG. 2 may be omitted.
[0019] Figures 3a and 3b schematically illustrate a flowchart depicting a method for searching and allocating memory dynamically. Applications send a request for memory to the memory allocator 103. On receiving (301) a request for memory, the memory allocator 103 checks the cache memory 101 to determine if the required memory is present. The memory allocator 103 first checks (302) in P1 for the required memory. The exact memory needed by the application may be determined using the frequency of memory access. If the required memory is present in P1, then the memory allocator 103 allocates (305) the required memory from P1 to the particular application. P1 could be searched to determine if there is twice the frequency of memory access blocks of free memory available. If the available memory is equal to or greater than twice the frequency of memory access, then the required memory is allocated by the memory allocator 103 to the particular application. The memory allocator 103 would store statistics of the allocated memory location, wherein said statistics comprise of the pointer to the address of the memory location, the size of the allocated memory location and access time. If the required memory is not present in P1, then the memory allocator 103 checks (303) for the required memory in P2. The exact memory blocks required in P2 is determined by using the frequency of memory access. If the required memory is present in P2, then the memory allocator 103 moves the required memory from P2 to P1. The memory allocator 103 stores the statistics of the memory. For example, P2 could be searched to determine if there are 2 * frequency of memory access blocks of free memory. If the available memory is equal to or greater than 2 * frequency of memory access, then the required memory is moved to P1. The memory blocks moved to P1 would be equal to 2 * frequency of memory access – memory blocks available in P1. The memory allocator 103 would store statistics such as the pointer to the address of the memory, size of the allocated memory and memory access time in P1 and P2. If the required memory is not present in P1 and P2, then the memory allocator 103 searches (304) for the required memory in the heap memory 102 based on the frequency of memory access. If the required memory is present (306) in the heap memory 102, then the memory allocator 103 moves the required memory from the heap 102 to the cache. The moved memory is then allocated (309) to the particular application. The memory allocator 103 stores the statistics of the memory location. For example, the heap memory 102 could be searched to determine if there are 2 * frequency of memory access blocks of free memory. If the available memory is equal to or greater than 2 * frequency of memory access, then the required memory is moved to the cache memory 101 by the memory allocator 103. The moved memory is then allocated to the particular application. The memory blocks moved to the cache memory 101 would be equal to 2 * frequency of memory access – memory blocks available in the cache memory 101. The memory allocator 103 would store statistics such as the pointer to the address of the memory, size of the allocated memory and memory access time. If the required memory is not present in the heap memory 102, then the memory allocator 103 tries to free memory from the cache memory 101 by removing (307) data from the cache memory 101. The time of access of data in the cache memory 101 is noted by the memory allocator 103 to determine the data to be removed from the cache memory 101. The free memory block that has not been accessed for the longest time is removed first from the cache memory 101. If the required memory is obtained (308) after freeing the cache, then the memory is allocated (309) to the particular application by the memory allocator 103. The memory allocator 103 stores the statistics of the memory location. After freeing the cache, if the memory required by the application is not available, then the memory allocator 103 obtains (3010) the required memory from adjacent heap memories 102. The memory allocator 103 then allocates (309) the memory to the particular application and stores the statistics of the memory location. The various actions in the method 300 may be performed in the order presented, in a different order, or simultaneously. Further, in some embodiments, some actions listed in Figures 3a and 3b may be omitted.
[0020] Figure 4 schematically illustrates a flowchart depicting a method to de-allocate memory and release memory to heap. After the application has completed performing an operation, the application sends (401) a request to free the memory allocated to the application. The application may send the request for freeing the memory to the memory allocator 103. For example, the request for freeing the memory may be sent by the application using the “Free” command. When the memory allocator 103 receives the request, the memory allocator 103 calculates the frequency of memory access and searches the cache memory 101 to locate the memory to be freed. If the number of free memory blocks is greater then 2 * frequency of memory access, then the memory allocator 103 frees the excess blocks of memory in the cache memory 101. If the cache memory 101 has been partitioned into P1 and P2, then the memory is freed from P1 and moved to P2. When the frequency of memory access reaches a pre-determined value, memory blocks will be freed from P2. The freed memory blocks are then released to the heap memory 102 by the memory releasing module 105. The releasing of memory to the heap memory 102 may also be done based on the percentage of use of the total available memory. If the memory usage reaches (402) a predetermined percentage 1 (R1), then blocks of memory in the cache memory 101 having memory access duration greater than a predetermined value 1 (V1) is released (403) to the heap. Memory is released to the heap memory 102 until the total available memory usage is below R1. For example, if the memory usage reaches one fourth of the total available memory, then memory blocks in the cache memory 101 having access duration of greater than or equal to 2000 clock tics is released to the heap memory 102. Here R1 is equal to one fourth of the total available memory and V1 is equal to 2000 clock tics. Memory is released to the heap memory 102 until the total available memory usage is below one fourth the total available memory. If the memory usage reaches (404) a predetermined percentage 2 (R2), then blocks of memory in the cache memory 101 having memory access duration greater than a predetermined value 2 (V2) is released (405) to the heap. Memory is released to the heap memory 102 until the total available memory usage is below R2. For example, if the memory usage reaches half of the total available memory, then memory blocks in the cache memory 101 having access duration of greater than or equal to 1000 clock tics is released to the heap memory 102. Here R2 is equal to half of the total available memory and V2 is equal to 1000 clock tics. Memory is released to the heap memory 102 until the total available memory usage is below half the total available memory. If the memory usage reaches (406) a predetermined percentage 3 (R3), then blocks of memory in the cache memory 101 having memory access duration greater than a predetermined value 3 (V3) are released (407) to the heap. Memory is released to the heap memory 102 until the total available memory usage is below R3. For example, if the memory usage reaches three fourth of the total available memory, then memory blocks in the cache memory 101 having access duration of greater than or equal to 500 processor 101 clock tics is released to the heap memory 102. Here R3 is equal to three fourth of the total available memory and V3 is equal to 500 processor 101 clock tics. Memory is released to the heap memory 102 until the total available memory usage is below three fourth the entire available memory. The freed memory can then be used by the memory allocator 103 to allocate to other applications requesting memory. The various actions in the method 400 may be performed in the order presented, in a different order, or simultaneously. Further, in some embodiments, some actions listed in FIG. 4 may be omitted.
[0021] Embodiments disclosed herein achieve memory allocation and de-allocation in lesser time. Lesser allocation and de-allocation time helps applications use dynamic memory allocation more efficiently. The internal and external data fragmentation is reduced and the entire available memory is used efficiently. The memory releasing module 105 reclaims unused memory blocks periodically improving memory usage. History of memory usage is maintained, helping in efficient tracking of allocation and de-allocation of memory. Embodiments disclosed herein can be used in computers, servers or in any instruction processing devices requiring use of memory.
[0022] A person of skill in the art would readily recognize that steps of various above-described methods can be performed by programmed computers. Herein, some embodiments are also intended to cover program storage devices, e.g., digital data storage media, which are machine or computer readable and encode machine-executable or computer-executable programs of instructions, wherein said instructions perform some or all of the steps of said above-described methods. The program storage devices may be, e.g., digital memories, magnetic storage media such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. The embodiments are also intended to cover computers programmed to perform said steps of the above-described methods.
[0023] The description and drawings merely illustrate the principles of the invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the invention and are included within its spirit and scope. Furthermore, all examples recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass equivalents thereof.
[0024] The functions of the various elements shown in the FIG. 1, including any functional blocks labeled as “processors”, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” or “controller” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non volatile storage. Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the FIGS. are conceptual only. Their function may be carried out through the operation of program logic, through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context.
[0025] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.

CLAIMS
What is claimed is:
1. A method for memory allocation in a computing system comprising steps of
searching a cache memory for a required memory based on memory access frequency;
searching a heap memory for said required memory, based on memory access frequency, if said required memory is not present in said cache memory;
freeing memory from said cache to obtain said required memory if said required memory is not available in said heap memory;
obtaining required memory from said plurality of heap memories if said required memory is not freed from said cache; and
allocating said searched memory to said application.
2. The method, as claimed in claim, wherein said memory access frequency is twice the frequency of memory access.
3. The method, as claimed in claim, wherein said cache memory is partitioned into two parts.
4. The method, as claimed in claim, wherein said heap memory is partitioned into multiple parts and said required memory is grouped into multiple groups, wherein size of said multiple partitions change dynamically depending on the frequency of memory access and individual said partitions satisfy memory requirement of individual group of said required memory.
5. The method, as claimed in claim, wherein memory is freed from said cache by removing data from said cache based on recency of access of data in said cache.
6. A module for performing memory allocation comprising atleast one means adapted for
searching a cache memory for a required memory on memory access frequency;
searching a heap memory for said required memory, based on memory access frequency, if said required memory is not available in said cache;
freeing memory from said cache to obtain said required memory if said required memory is not available in said heap memory;
obtaining required memory from said plurality of heap memories if said required memory is not freed from said cache;
allocating said searched memory to said application.
7. The module, as claimed in claim 6, wherein said memory access frequency is twice the frequency of memory access.
8. The module, as claimed in claim 6, wherein said module is adapted to maintain statistics of said allocated memory, wherein said statistics comprise address of said allocated memory, size of said allocated memory and said memory access frequency.
9. The module, as claimed in claim 6, wherein said module is adapted to free memory from said cache by removing data from said cache based on recency of access of data in said cache.
10. A method for freeing memory in a computing system, said computing system further comprising of a cache memory and a heap memory, said method comprising steps of
searching said cache memory to free specific blocks of memory; and
releasing said freed memory from said cache memory to said heap memory, depending on memory access duration value.
11. The method, as claimed in claim 11, wherein predetermined blocks of memory are released to said heap memory when said memory access duration value reaches a predetermined value.
12. The method, as claimed in claim 11, wherein predetermined blocks of memory are released to said heap memory when percentage of memory usage reaches a predetermined value.
13. A memory releasing module for freeing memory in a computing system, said computing system further comprising of a cache memory and a heap memory, said memory releasing module comprising atleast one means adapted for
searching said cache memory to free specific blocks of memory; and
releasing said freed memory from said cache memory to said heap memory, depending on memory access duration value.
14. The module, as claimed in claim 13, wherein said module is adapted to release predetermined blocks of memory to said heap memory when said memory access duration value reaches a predetermined value.
15. The module, as claimed in claim 13, wherein said module is adapted to release predetermined blocks of memory to said heap memory when percentage of memory usage reaches a predetermined value.

Dated this 26th August 2009

Dr. Kalyan Chakravarthy
Patent Agent