DLV101@psuvm.psu.edu (Dwaine VanBibber) (12/13/90)
A while back there was some discussion about DOS's inability to coalesce freed memory and several people posted solutions. I have a couple of questions regarding this. First, what is "coalescing"? Why is it needed? When is it need (ie, when freeing objects from dynamic data structures?)? Lastly, how is it done? Examples in C and/or assembly would be appreciated. Thank you. --Dwaine
Ralf.Brown@B.GP.CS.CMU.EDU (12/13/90)
In article <90346.130938DLV101@psuvm.psu.edu>, DLV101@psuvm.psu.edu (Dwaine VanBibber) wrote: }A while back there was some discussion about DOS's inability to coalesce }freed memory and several people posted solutions. I have a couple of questions }regarding this. First, what is "coalescing"? Why is it needed? When is it }need (ie, when freeing objects from dynamic data structures?)? Lastly, how }is it done? Examples in C and/or assembly would be appreciated. Thank you. Coalescing is the process of combining adjacent free blocks into a single, larger free block. If you didn't do that, a sequence of allocations and frees would eventually fragment the memory to the point where even a small allocation would fail even though there are hundreds of K available--but none of the free blocks large enough for the request. -- UUCP: {ucbvax,harvard}!cs.cmu.edu!ralf -=- 412-268-3053 (school) -=- FAX: ask ARPA: ralf@cs.cmu.edu BIT: ralf%cs.cmu.edu@CMUCCVMA FIDO: 1:129/3.1 Disclaimer? | I was gratified to be able to answer promptly, and I did. What's that? | I said I didn't know. --Mark Twain
dougs@videovax.tv.tek.com (Doug Stevens) (12/15/90)
In article <90346.130938DLV101@psuvm.psu.edu>, DLV101@psuvm.psu.edu (Dwaine VanBibber) writes: > ... what is "coalescing"? Why is it needed? ... how is it done? Coalescing is the merging of adjacent free blocks of memory. Most operating systems include memory managers that maintain a linked list of free memory blocks (usually called the 'free list'). Each block of memory in the list contains information about how large the block is, and a link to the next block in the list. When the system starts up, the free list pointer points to one large contiguous block of free memory. A request for a memory block will return a pointer to the start of this area, and the free list pointer will be re-adjusted to point to the memory following the allocated block. As blocks are freed (de-allocated), they are re-inserted in the linked list of free memory blocks. Now let's assume that all of memory has been consumed by mallocs for 1K blocks, and then all the blocks are freed. If the free blocks were not coalesced, and a request for a block of 2K was made, the operating system could not honor it (since there is a block header between each 1K of memory). In order to coalesce, the system must traverse the linked list of free memory blocks, locate all blocks which are contiguous, revise the header in the first block to reflect the size of the coalesced blocks, and remove the header in the second block (by revising the header in the first block to point to the next non-coalesced block). This can be done either when a block is freed, when a malloc is done, or only when a malloc is done for which there is not a large enough free block. There are performance trade-offs for each of the above.