Search code examples
cmallocheap-memorydynamic-memory-allocationvirtual-memory

(Dynamic Memory Allocation) why maximize peak utilization?

I was reading a textbook which says that: enter image description here

I'm totally lost, let's says:

n = 10 and p (required payload) = 800 bytes,

Does it mean that on the n = 9 which is 9th allocate request, P9 needs to be 792 bytes( suppose a single minimum allocate is 8 bytes)? Is my understanding correct?

Solution

  • As far as I understand the text, that allocator objective is to maximize Pi (sum of allocated memory at instant i). The peak utilization up to k is the ratio of the max of what could be allocated divided by the heap size at k.

    Since there is a number of alloc and free at i, if the allocator is too basic and does not handle well the requests, it might be unable to answer another allocation request (for instance due to heap fragmentation, see exemple below).

    A smart allocator might allow a maximal payload, at the expense of a slower response.

    On the opposite you might have a fast allocator that might not be able to maximize the aggregate payload Pk after a number of requests.

    To give a (simple) exemple, having that chain of requests

    R1: alloc(1000)
R2: alloc(2000)
R3: alloc(1500)
R4: free(R1)
R5: free(R2)
R6: alloc(3000) => use space from R1+R2?

    At R6 a basic allocator might not be able to understand it could reuse the space freed from R1 and R2, giving a low peak ratio, and the heap size is unnecessary higher than it should.

    A smarter one might do, but at the likely expense of more CPU /resources.