• Offline dynamic memory allocation

    From Steve Keller@21:1/5 to All on Tue Apr 6 16:59:54 2021
    I need an offline dynamic memory allocation algorithm. That is, I
    have a number of memory allocation requests each with size (in bytes), allocation time and release time that I want to satisfy with one
    contiguous memory segment of a given fixed size. All allocation
    requests are known at program start time.

    The allocation algorithm should give the memory allocation, i.e. the
    memory address for each allocation request.

    In the case that not all requests can be satified with the given
    memory size I'd like to get a list of allocation that maximizes the
    memory allocation, i.e. the sum of the products of used memory size
    and time of usage should be maximal (as this would probably maximize performance).

    AFAIK, this is the offline dynamic memory allocation problem. Since
    the number of requests can be up to 1000 I cannot try all
    combinations. Also, AFAIK, the problem is NP complete.

    So my question is: Is there an algorithm that computes an optimal
    allocation in short time, say a few seconds or a minute (probably not
    since NP completeness), and otherwise, is there an algorithm that
    computes a good approximation in that time frame?

    If have thought about variants of First-Fit and Best-Fit but I don't
    know in which order to process the requests. Since I know all
    requests in advance, I could sort by size first and then by allocation
    time or vice-versa. If sorting by size, is ascending or descending
    order better? Or are there better approaches?


    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)