Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-01-25
2003-11-04
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S173000, C711S203000
Reexamination Certificate
active
06643753
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates to the field of memory management. In particular, the present invention relates to the methods and systems for managing heap creation and allocation in a manner that improves memory usage and reduces the risk of virtual memory fragmentation.
2. Background and Related Art
Computers have transformed the lives of many in this modern era. The ability to store and retrieve instructions and data is fundamental to computer operation. Modern computer systems access physical memory through a virtual memory manager that maps virtual memory addresses to physical memory addresses. During run time, applications identify the virtual memory address that is to be operated on. Typical operations might include reading information from the identified virtual memory address, writing information to that address, allocating the address, releasing the address for further use, and so forth. The virtual memory manager then converts the virtual memory address into a corresponding physical memory so that the appropriate operation may be performed on the appropriate physical address.
The amount of available virtual memory is not limited to the amount of available physical memory. When the physical memory is full, the virtual memory manager transfers or “pages” some of the memory contents to disk. When a virtual memory address that has been paged to disk is accessed, the virtual memory manager loads the corresponding information from the disk back into the physical memory. The process of transferring memory between the physical memory and the disk is called “swapping”. This process allows the virtual memory to be much larger than the physical memory.
The number of virtual memory addresses is, however, limited by the bit size of the address space used to address virtual memory. For example, in an operating system that uses 32-bit virtual memory addressing, the number of virtual memory addresses is limited to 2
32
or 4 Gig, where 1 Gig is equal to 1024 Meg, where 1 Meg is equal to 2
20
or 1048,576. Since each address contains one byte of information, the virtual memory size is limited to 4 Gigabytes (GB). Typically, an operating system will internally reserve 1 or 2 GB of virtual memory for the operating system leaving only 2 or 3 GB of virtual memory for non-system processes to use. While this may seem like a lot of memory, as software applications are becoming more complex, virtual memory allocations may use the entire available virtual memory.
The virtual memory manager allocates virtual memory segments at a relatively large granularity. In this description and in the claims, a “virtual memory segment” is defined as a group of contiguous virtual memory addresses. For example, a typical granularity of a virtual memory segment allocated by the virtual memory manager is 64 kilobytes (KB). In this case, the smallest virtual segment that could be allocated by the virtual memory manager would be 64 KB. However, many applications require much less virtual memory than 64 KB. It would be an inefficient usage of virtual memory to allocate an entire segment of 64 KB for an application that requires much less than 64 KB of virtual memory since a large portion of the 64 KB would remain unused. For example, if the application only needed 2 KB of virtual memory, 62 KB of the virtual memory segment would remain unused.
Conventional heap managers allow for the allocation of virtual memory segments at a much finer granularity. A typical heap manager may allocate segments in a heap at a granularity of merely 8 bytes. In order to accomplish a more efficient usage of virtual memory, a heap manager instructs the virtual memory manager to allocate a relatively large virtual memory segment called a “heap”. As various applications require relatively small allocations of virtual memory, the heap manager makes the relatively small allocation of virtual memory from within the relatively large heap. The heap manager then keeps track of the location of the smaller segments within the larger heap as well as the process associated with that smaller allocation.
The conventional heap manager is very helpful in allowing for the more efficient use of memory space since the heap manager may allocate smaller increments of virtual memory within a heap. However, whenever a thread performs an allocation, a reallocation, or a deallocation of virtual memory within the heap, the entire heap is locked thereby prohibiting memory operations by other threads that also would use the heap. This locking operation often forces threads to wait until the heap is unlocked before operating on the heap.
One improvement to this conventional heap manager is implemented by a heap optimization module that causes the heap manager to create more than one heap. For example, the heap optimization module may cause the heap manager to create three more heaps than the number of processors in the system. Thus, in a two-processor system, the heap optimization module would cause the heap manager to create five heaps.
If a thread is to make a smaller allocation within a heap, the heap optimization module determines which heap is to receive the allocation. Specifically, the heap optimization module identifies a heap that is not locked. Then, the heap optimization module locks the identified heap and instructs the heap manager to make the smaller allocation in the identified heap. After the heap manager responds to the instruction by reporting the success or failure of the instructed allocation, the heap optimization module unlocks the identified heap. Thus, even if one of the heaps is locked, other threads may continue to make allocations within other unlocked heaps. In this manner, the heap optimization module distributes allocation to one of multiple heaps depending on which heaps are locked. This improves the speed of the system as compared to the conventional heap manager that only allocates a single heap in virtual memory.
In this manner, the heap optimization module identifies a specific heap in which to make an allocation. If the specific heap does not contain enough contiguous virtual memory addresses to make the requested allocation, the heap manager “expands” the heap. The heap manager increases the heap size by allocating an additional segment from virtual memory and assigning that segment to be part of the heap. The additional segment need not be contiguous with the initial heap segment since the heap manager is capable of tracking the location of the additional segments within virtual memory and associating those additional segments with the initial heap segment regardless of whether the heap segments are contiguous or not.
If further expansions for this heap were needed, then the added segment size would be doubled so long as there was sufficient contiguous space in virtual memory to do so.
For example, suppose the initial size of the heap was 16 MB and that the first expansion was 1 MB. The size of the heap would be initially expanded to 17 MB. The next expansion segment would be 2 MB thus increasing the heap size to 19 MB. The next expansion segment would be 4 MB, the next 8 MB, 16 MB, 32 MB, 64 MB, 128 MB, and so forth. Thus, the heap expansion algorithm in the heap manager may allocate extremely large additional segments.
Very little of the final very large expansion segment may, in fact, be used. For example, suppose that the final additional segment for a heap was 256 MB. It may be that only 1 MB of this segment is actually used to make allocations. This wastes a large amount of virtual memory, which cannot now be used by other threads within the process. This is compounded by the fact that the other heaps may be doing exactly the same sort of expansions.
Such wasting of virtual memory may be quite acceptable if there is sufficient virtual memory available. However, as mentioned above, in a 32-bit virtual memory addressing scheme, virtual memory is limited to 2 or 3 GB depending on how much virtual memory the operating system uses. In additional, the amount of physic
Avner Jon B.
Terek Soner
Baker Paul
Microsoft Corporation
Sparks Donald
Workman Nydegger
LandOfFree
Methods and systems for managing heap creation and allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and systems for managing heap creation and allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for managing heap creation and allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136545