By: Adrian (a.delete@this.acm.org), July 1, 2022 9:58 pm
Room: Moderated Discussions
Foo_ (foo.delete@this.nomail.com) on July 1, 2022 3:21 am wrote:
> Adrian (a.delete@this.acm.org) on June 30, 2022 9:43 am wrote:
> >
> > When all the allocation and free requests are done from stacks, each stack corresponding
> > to a certain size class, nothing ever changes from the point of view of fragmentation.
>
> This is delusional. Allocation may be done "from stacks", but given that deallocations
> happen in random order (random from the POV of the allocator, of course), they
> cannot be done in a simple stack-like (i.e. LIFO) fashion.
When the size is variable, you are right.
But when the size of a memory block is fixed (being used to satisfy any allocation requests between 2 thresholds), the allocations and deallocations are really done as LIFO from the stack containing the free memory blocks.
A "malloc" pops a free memory block from the stack and a "free" pushes the used memory block back in the stack, regardless how many other "malloc" and "free" have happened meanwhile.
You are probably confused by thinking about a stack implemented as an array with a stack pointer. For this application, the stacks are implemented as linked lists, not as arrays.
> Adrian (a.delete@this.acm.org) on June 30, 2022 9:43 am wrote:
> >
> > When all the allocation and free requests are done from stacks, each stack corresponding
> > to a certain size class, nothing ever changes from the point of view of fragmentation.
>
> This is delusional. Allocation may be done "from stacks", but given that deallocations
> happen in random order (random from the POV of the allocator, of course), they
> cannot be done in a simple stack-like (i.e. LIFO) fashion.
When the size is variable, you are right.
But when the size of a memory block is fixed (being used to satisfy any allocation requests between 2 thresholds), the allocations and deallocations are really done as LIFO from the stack containing the free memory blocks.
A "malloc" pops a free memory block from the stack and a "free" pushes the used memory block back in the stack, regardless how many other "malloc" and "free" have happened meanwhile.
You are probably confused by thinking about a stack implemented as an array with a stack pointer. For this application, the stacks are implemented as linked lists, not as arrays.
