dan-hankins@cup.portal.com (10/09/88)
I am considering writing a utility to take the free memory heap and defragment it. This would involve looking at each of the nodes, reading them out into a linked list, sorting the linked list, and then concatenating all the adjacent blocks and then rebuilding the heap. This seems like such a simple idea, it amazes me that it has not occurred to anyone before. Has it? Would I be re-inventing the wheel? If so, where could I find this utility? I have a need for it. If no one has written one before, is there some quirk of the opsys that would prevent me from doing it? I already envision that the second version would intercept calls to the system allocation and de-allocation functions and run in the background, only doing the de-fragmentation when a block is returned to the heap or when an allocation request fails. Do too many programs fiddle with the heap themselves for this to be of any practical value? Dan Hankins
page@swan.ulowell.edu (Bob Page) (10/12/88)
I'm not sure what you mean by "free memory heap". Somebody once wrote a utility called SWEEP to coalesce adjacent free memory hunks. I think this is what you're trying to do. Exec already does this. ..Bob -- Bob Page, U of Lowell CS Dept. page@swan.ulowell.edu ulowell!page "I can't tell the difference between ABC News and Hill Street Blues" -Bono
dillon@CORY.BERKELEY.EDU (Matt Dillon) (10/12/88)
Dan Hankins Writes:
:I am considering writing a utility to take the free memory heap and
:defragment it. This would involve looking at each of the nodes, reading
:them out into a linked list, sorting the linked list, and then
:concatenating all the adjacent blocks and then rebuilding the heap.
:
:This seems like such a simple idea, it amazes me that it has not occurred
:to anyone before. Has it? Would I be re-inventing the wheel? If so,
:where could I find this utility? I have a need for it.
:
:If no one has written one before, is there some quirk of the opsys that
:would prevent me from doing it?
You can't re-arrange memory... task X allocates a chunk of memory
and has lots of pointers to it lying around. You cannot simply move that
chunk somewhere else!
The fragmentation is due solely to situations where programs
allocate long-term memory like this:
A allocates lots of short term memory, say, 64K
B allocates a little long term memory, say, 8 bytes
A deallocates its memory
So now you have 64K freespace, 8 bytes allocate, and the rest free.
Thus, your original memory space is now fragmented. BUT you cannot move
those 8 bytes somewhere else ... B has to do it by free'ing and re-allocating
it.
:I already envision that the second version would intercept calls to
:the system allocation and de-allocation functions and run in the background,
:only doing the de-fragmentation when a block is returned to the heap or
:when an allocation request fails.
De-fragmentation is done automatically by FreeMem(). That is,
if you FreeMem() a block of memory which is adjacent to another free block,
those blocks are combined.
:Do too many programs fiddle with the heap themselves for this to be of any
:practical value?
Well, it really isn't a heap technically. I agree that fragmentation
is a problem, but not a big problem. The problem occurs on machines that
have little memory to begin with (512K). Once you get some extended
memory installed, the problem is essentially removed for the CHIP memory
section and only remains in the extended memory. If you have enough extended
memory then this goes away too.
With 2Meg of external memory I still have problems with some programs,
like the 16 bit version of compress. Actually, that is the only program I
have problems with.
Though I haven't done this much myself, it is always a good idea
to think about memory fragmentation when you intend to allocate long-term
storage. For instance, if I write a little clock program that allocates
long term memory I should, every once in a while, reallocate it so the system
can compact the storage. Other examples come to mind. To be a solution,
though, the system software would also have to do this sort of thing.
-Mattjimm@amiga.UUCP (Jim Mackraz) (10/12/88)
In article <9887@cup.portal.com> dan-hankins@cup.portal.com writes:
)I am considering writing a utility to take the free memory heap and
)defragment it. This would involve looking at each of the nodes, reading
)them out into a linked list, sorting the linked list, and then
)concatenating all the adjacent blocks and then rebuilding the heap.
The list is sorted, and adjacent blocks are concatenated, all of the
time.
)This seems like such a simple idea, it amazes me that it has not occurred
)to anyone before. Has it? Would I be re-inventing the wheel?
I think Carl thought of it, too.
)If so, where could I find this utility? I have a need for it.
It is called FreeMem(), a function of the Exec in ROM. ;^)
)If no one has written one before, is there some quirk of the opsys that
)would prevent me from doing it?
You could call it a quirk, I guess.
)I already envision that the second version would intercept calls to
)the system allocation and de-allocation functions and run in the background,
)only doing the de-fragmentation when a block is returned to the heap or
)when an allocation request fails.
FreeMem().
)Dan Hankins
jimm
By the way: memory fragmentation on the Amiga occurs because there are
actually allocated sections of memory between the freed chunks. There's
been a lot of discussion on this already.
Note that you can't concatenate two non-adjacent chunks.
If you think you have identified a condition where there are adjacent
free chunks in the free list (or an unsorted free list), please reproduce
and mail in a floppy. I don't think so, though.
--
Jim Mackraz, I and I Computing
amiga!jimm BIX:jmackraz
Opinions are my own. Comments regarding the Amiga operating system, and
all others, are not to be taken as Commodore official policy.dan-hankins@cup.portal.com (10/13/88)
In article <3009@amiga.UUCP> jimm@amiga.UUCP (Jim Mackraz) writes: >By the way: memory fragmentation on the Amiga occurs because there are >actually allocated sections of memory between the freed chunks. There's >been a lot of discussion on this already. > >Note that you can't concatenate two non-adjacent chunks. Ah. So what we need is an MMU (i.e. virtual memory). Hmmm. What would happen if the ALLOCATE and DEALLOCATE functions were re-written in such a way that all memory would be allocated in 1k chunks? Then successive calls to ALLOCATE would check to see if part of an already-allocated chunk was available for allocation, and use that if it could. That is, first call (100 bytes) results in a 1k chunk being allocated. Second call results in a second pointer into the same 1k chunk. This might reduce the problem you spoke of without as much need to resort to an MMU. If we could keep track of all pointers to a memory chunk, we could rearrange them no problem. But then the Amiga OS isn't quite *that* object-oriented. Dan Hankins
haitex@pnet01.cts.com (Wade Bickel) (10/13/88)
If you want to do something useful, write a routine to crunch memory
so as to create the largest possible free block (or has this been done too?).
Wade.
UUCP: {cbosgd, hplabs!hp-sdd, sdcsvax, nosc}!crash!pnet01!haitex
ARPA: crash!pnet01!haitex@nosc.mil
INET: haitex@pnet01.CTS.COM
Opionions expressed are mine, and not necessarily those of my employer.daveb@cbmvax.UUCP (Dave Berezowski) (10/17/88)
In article <10003@cup.portal.com> dan-hankins@cup.portal.com writes: >In article <3009@amiga.UUCP> jimm@amiga.UUCP (Jim Mackraz) writes: > >>By the way: memory fragmentation on the Amiga occurs because there are >>actually allocated sections of memory between the freed chunks. There's >>been a lot of discussion on this already. >> >>Note that you can't concatenate two non-adjacent chunks. > >Ah. So what we need is an MMU (i.e. virtual memory). > >Hmmm. What would happen if the ALLOCATE and DEALLOCATE functions were >re-written in such a way that all memory would be allocated in 1k chunks? >Then successive calls to ALLOCATE would check to see if part of an >already-allocated chunk was available for allocation, and use that if it >could. > >That is, first call (100 bytes) results in a 1k chunk being allocated. >Second call results in a second pointer into the same 1k chunk. This might >reduce the problem you spoke of without as much need to resort to an MMU. > >If we could keep track of all pointers to a memory chunk, we could >rearrange them no problem. But then the Amiga OS isn't quite *that* >object-oriented. > Well you could keep ptrs to all your variables in one structure (sort of like a freelist) and periodically call a system routine like 'UnFragMemory' which would attempt to un-fragged memory by re-working all your variables (ie. all your memory use); copying the data as it needed to. Of course this scheme relies on the application writer; and we all know how dependable they are! :^) Regards, David Berezowski
cmcmanis%pepper@Sun.COM (Chuck McManis) (10/18/88)
In article <5005@cbmvax.UUCP> (Dave Berezowski) writes: > Well you could keep ptrs to all your variables in one structure >(sort of like a freelist) and periodically call a system routine >like 'UnFragMemory' which would attempt to un-fragged memory by re-working >all your variables (ie. all your memory use); copying the data as it >needed to. > Regards, David Berezowski Yes you could, this is sort of what the Macintosh does and it helps a lot. Unfortunately it gets a bit weirder to program when AllocMem returns a (void **) rather than a (void *) [char * for you K&R folks]. There is a simpler way to minimize the damage and that is to build a "small memory" manager. (I believe it was mentioned here before). Essentially, you add a could of "small" allocation routines AllocSmallMem and FreeSmallMem which use a reserved "chunk" of memory. [You can reserve the memory by using AllocMem() to get the chunk.] This keeps many of the problems associated with fragmenting memory with an 8 byte Alloc in the middle. Note that it would not be as effective as it would if the system managed it's own small memory pool (which Bryce has hinted it will). There is of course SetFunction() for those of you who can't wait :-). --Chuck McManis uucp: {anywhere}!sun!cmcmanis BIX: cmcmanis ARPAnet: cmcmanis@sun.com These opinions are my own and no one elses, but you knew that didn't you.
dan-hankins@cup.portal.com (Daniel B Hankins) (10/19/88)
In article <73227@sun.uucp> cmcmanis%pepper@Sun.COM (Chuck McManis) writes: >In article <5005@cbmvax.UUCP> (Dave Berezowski) writes: >> Well you could keep ptrs to all your variables in one structure >>(sort of like a freelist) and periodically call a system routine >>like 'UnFragMemory' which would attempt to un-fragged memory by re-working >>all your variables (ie. all your memory use); copying the data as it >>needed to. >> Regards, David Berezowski > >Yes you could, this is sort of what the Macintosh does and it helps a lot. >Unfortunately it gets a bit weirder to program when AllocMem returns a >(void **) rather than a (void *) [char * for you K&R folks]. There is a >simpler way to minimize the damage and that is to build a "small memory" >manager. (I believe it was mentioned here before). Essentially, you >add a could of "small" allocation routines AllocSmallMem and FreeSmallMem >which use a reserved "chunk" of memory. [You can reserve the memory by >using AllocMem() to get the chunk.] This keeps many of the problems >associated with fragmenting memory with an 8 byte Alloc in the middle. >Note that it would not be as effective as it would if the system managed >it's own small memory pool (which Bryce has hinted it will). There is >of course SetFunction() for those of you who can't wait :-). What is SetFunction? Would garbage collection techniques help? For instance, memory could be divided into two huge chunks. All allocations would come from chunk A until chunk A is full. Then all allocations would come from chunk B, until chunk B fills up. Then back to A, and so on. Of course this would be a user-selectable option. Could even allow more than two chunks. Dan Hankins
mlelstv@faui44.informatik.uni-erlangen.de (Michael van Elst ) (10/20/88)
In article <9887@cup.portal.com> dan-hankins@cup.portal.com writes: >I am considering writing a utility to take the free memory heap and >defragment it. This would involve looking at each of the nodes, reading >them out into a linked list, sorting the linked list, and then >concatenating all the adjacent blocks and then rebuilding the heap. > I am pretty sure that this IS done with a normal FreeMem call since the nodes in the memory free list ARE sorted and we get big chunks of free memory if we free small adjacent blocks before. The problem of fragmentation is another one. It is not small adjacent blocks that aren't concatenated BUT small NOT adjacent blocks that can't be concatenated. The only thing to come around with this, is to collect garbage in memory. But if you do this, you have to correct any absolute memory address in your program and any pointer that refers to a shifted memory block. The MAC OS does this kind of thing as they don't use actual pointers to memory BUT so called 'handles'. These are double referenced pointers. So they only have to held these handles at fixed locations and the OS can easily correct them if the garbage collector has moved memory blocks. Of course, on a multi-tasking machine without MMU, this job is rather difficult as you have to arbitrate access to those handles. The MAC OS simply divides the memory space into large blocks for each application. Thus the amount of memory for each application is fixed. Michael van Elst E-mail: UUCP: ...uunet!unido!fauern!faui44!mlelstv
hansel@amy.uucp (Steve Hansel) (10/23/88)
> I am pretty sure that this IS done with a normal FreeMem call since > the nodes in the memory free list ARE sorted and we get big chunks > of free memory if we free small adjacent blocks before. > The problem of fragmentation is another one. It is not small adjacent > blocks that aren't concatenated BUT small NOT adjacent blocks that > can't be concatenated. How about allocating 'small' chunks from the top of memory downward and 'large' chunks from the bottom of memory upward. This would mean that, unless your memory was very full,the fragmentation would only occur between small chunks. I bet this could be done with a minimum of overhead. The biggest impact would probably be that the free list would be comprised of 12 byte blocks because it would be doubly linked. This shouldn't be a problem because there was never any guarantee on the minimum size of alloced blocks. Also future releases of the O.S. could have optional MEMF_PERM (or MEMF_LONGTERM) flag that would force the OS to allocate from the small chunk area (Top). This flag would be used by Clock programs, system monitors, shells, etc, when they AllocMemed because they tend to keep their memory for long periods of time. I think this approach is much easier than allocing larger chunks to hold smaller chunks, or using pointer handles. Just a thought Steve Hansel gryphon.cts.com!amy!hansel oberon.usc.edu!amy!hansel rutgers!amy!hansel