rtm@grenada.UUCP (Richard Minner) (10/21/89)
From Doug Gwyn: |In article <1175@svx.SV.DG.COM> gary@svx.SV.DG.COM () writes: |>The correct answer is "malloc/free is somewhat broken in Sunos 4.0.1-3". |>This has been mentioned before, in a Feb. Sun Spots article - here it is... | | That sounds more like a "buddy system" allocator working normally. I'll bite, how does a "buddy system" allocator work, normally? I can imagine why free'd blocks might "shrink" a bit but I'd appreciate an overview from someone who actually knows. Also, if such a system can normally produce what I consider to be counter-intuitive results (and gary@svx.SV.DG.COM considers "somewhat broken"), what are its advantages? If it's overly complex, a good reference would be nice. Thanks. -- Richard Minner || {uunet,sun,well}!island!rtm (916) 447-7081 || || Island Graphics Corporation Sacramento, CA ||
moraes@cs.toronto.edu (Mark Moraes) (10/22/89)
rtm@grenada.UUCP (Richard Minner) writes: >I'll bite, how does a "buddy system" allocator work, normally? It maintains free lists of blocks in sizes of powers of two. When satisfying a request, it finds the smallest power of two larger than the request and returns that block. If it can't find a block in that free list, it goes to the free list for the next higher size and splits a block there into two "buddies" and returns one, putting the other in the appropriate free list. (The process recurses to higher sizes if till a free list with a free block is found or till it becomes necessary to get more memory from the system). The buddy's address can be computed cheaply. When you free a block, it is easy to coalesce -- check if the block's buddy is free, if so, coalesce them, check if the resulting coalesced block's buddy is free and so on. Since all blocks are powers of two, this can waste a fair bit of memory for large blocks. (Especially as most people seem to malloc(power of 2), which gets rounded up to the next power of two since the allocator stores some size and debugging information in the block as well) The BSD4.3 malloc (Chris Kingsley's malloc, Caltech malloc -- it goes by various names) is often called a buddy system allocator since it splits blocks by powers of two when allocating, even though it doesn't do the coalescing on free. (This lack of coalescing can lead to nasty behaviour under some allocation patterns -- for the usual allocation pattern where a program continuously allocates blocks in a few sizes, this is not a problem. For applications that handle dynamically allocated strings that vary in size over a wide range, this allocator sometimes runs the machine out of memory) >If it's overly complex, a good reference would be nice. It's not overly complex, but anyway: %V 1 %A Knuth, Donald E. %T The art of computer programming: Fundamental Algorithms %C Reading, Mass. %I Addison-Wesley Pub. Co. %D [1968-] There's a section devoted to dynamic memory allocation -- describes a simple first fit algorithm, a boundary tags first fit algorithm and a buddy system. I usually prefer the boundary tags algorithm with some of the mods he describes suggests in the Exercises --it gives good performance over a wider range of allocation patterns and wastes less space, something I think is important for any application doing a lot of allocation. He's got a simple random simulation that stresses allocators. A good comparative study of mallocs is: %A David G. Korn %A Kiem-Phong Vo %T In search of a better malloc %J Proceedings of the USENIX 1985 Summer Conference %C Portland, Oregon %D June 1985 %K usenix85s %P 489-506 They implement the simulation Knuth describes and test numerous mallocs with it.
gwyn@smoke.BRL.MIL (Doug Gwyn) (10/23/89)
In article <426@grenada.UUCP> rtm@grenada.UUCP (Richard Minner) writes: >If it's overly complex, a good reference would be nice. Knuth Vol. 1.
gwyn@smoke.BRL.MIL (Doug Gwyn) (10/23/89)
In article <89Oct22.120811edt.3343@neat.cs.toronto.edu> moraes@cs.toronto.edu (Mark Moraes) writes: >I usually prefer the boundary tags algorithm with some of the mods >[Kunth] describes suggests in the Exercises ... That's also the one I usually choose when I have to implement a general memory allocator. If anyone is going to implement this, note that the solution to exercise 2.5-19 given in the Second Edition has a bug in it: upon allocation failure, one must not leave ROVER pointing to the collapsed tail; set it to LOC(AVAIL). Also, the algorithm given in the solution to exercise 1.5-12 can be improved upon. I won't say how, since you should study this stuff before implementing it, to the point that you should be able to figure it out yourself.