On Sun, Jan 31, 2016 at 02:28:57PM +0100, Edward Bartolo wrote:
> Hi,
>
> Lately, I have been pondering how memory managers deal with a
> situation, when memory is fragmented with scattered allocated blocks,
> in the event a memory allocation request, is made for a memory chunk,
> whose size is bigger than the biggest unallocated contiguous memory
> chunk.
>
> In a situation similar to the one mentioned, my temptation is to opt
> to using linked lists, so as to avoid requiring large unallocated
> contiguous memory blocks. However, this increases the overall
> processing load which tends to slow whatever program using such a
> model.
>
> The question is how do memory managers succeed to remain efficient and
> yet cope with memory allocation of so many different sizes?

There re a variety of possible strategies.

First, for very large blocks of memory, it's not a question of
fragmenting memory, but of fragmenting address space -- the page table
takes care of keeping track of the physical memory. There's never a
reason to consider a page of physical memory as being in one fragment
or an other, since it can be anywhare in the address space. If your
address space is much larger than your memory, as it is on today's
64-bit hardware, it's rather difficult to run out of addresses.

Second, for smaller chunks, it's possible to have different regions of
address space devoted to different sizes of storage allocation. If
there are too many different sizes, the system may pick a smaller nuber
of standard sizes and round requests up to the smallest standard block
it will fit in.

After thet there are probably a variety of data structures that can
keep track of all the allocations and free spaces. on the Lnuxes I've
been using, malloc seems to keep its administrative data far removed
from the memory it is allocating. So although it's easy to clobber
one's data structures by indexing slightlly out of bounds one is
less likely to clobber malloc's administrative data.

>
> Edward
> _______________________________________________
> Dng mailing list
> Dng@???
> https://mailinglists.dyne.org/cgi-bin/mailman/listinfo/dng