1
votes

As part of an assignment we have to implement a (basic) malloc function(we should somehow simulate dynamic memory allocation). I already implemented a solution based on implicit free list,but the problem is that i get a utilization of 50% and a throughput of 9% only(I have to get a 90% utilization+throughput). The problem with implicit free list is that it takes alot of time searching for free blocks. So i wanted to implement explicit free list to see how much can the program improve. now the problem is that i have to keep track of next/prev pointers for free blocks. And since I can only use scalar variables and cannot use any kind of data structures e.g:linked list,struct,.., i couldnt implement it. Can someone point out how can i keep track of (virtual) pointers in C?

thanks,

1
what do you mean "cannot use any kind of data structures e.g: linked list" but somehow you can have "next/prev pointers"? Something doesn't make sense. - luser droog
@luserdroog so we are not allowed to use any kind of data structures. BUT the explicit free lists keep track of next/prev free blocks. in other words, explicit free lists is an algorithm, and i have to implement it.explicity free lists - aaa
Ok. So you cannot "use (a pre-written) linked-list", because this is a linked-list. Right? - luser droog
@luserdroog yes. I think i got it now, i just have to have a normal pointer with the an address(next or previous block) save in it ? - aaa
Added an answer. I'm in favor of structs. - luser droog

1 Answers

0
votes

From the images in the slides (linked in the comments), I think you're expected to store the links as integer offsets.

In C, this really is best described as a struct.

struct alloc_cell {
    int size;
    int forward;
    int back;
    int data[];
};

Now, he also has the size repeated at the end, and that is much harder to describe with a struct. It's not clear how necessary it is. It's used for boundary coalescing.


Edit: much later, considering comment.

Even if you can't use structs in the code, you can still use them in the pseudocode to help organize your thinking. The struct fields, being all the same type, map naturally to an array represention which can be accessed by a pointer to the the first member/element.

struct alloc_cell {    // int *cell;
    int size;          // cell[0] // *cell
    int forward;       // cell[1]
    int back;          // cell[2]
    int data[];        // (cell+3)[...] // &cell[3]
};

You could even go so far as to give these offsets mnemonic names (but this may be considered overkill and unnecessary obfuscation).

enum { SIZE, FORWARD, BACK, DATA };

cell[SIZE];                   // alloc_cell.size
cell[FORWARD];                // alloc_cell.forward
cell[BACK];                   // alloc_cell.back
cell+DATA; // &cell[DATA]     // alloc_cell.data