I have to write a memory manager for class (I've read the FAQ, but bear with me :)) and was wondering if I could get some comments on a design that I am proposing; I'm not looking for someone to solve the problem for me. Basically the task is to implement our own memory manager to simulate new/delete and accesses to the memory we've allocated. Invalid accesses should throw an exception. A file of allocations, deletions, and accesses is read from a file and tested against our program. A process # is given for each operation as well, so if memory is accessed by a process it doesn't belong to, that process should be terminated. Anyway, one of the big issues is some how to express memory in some data structure. My initialy attempt involved a vector, and I would allocate blocks from that structure by changing all elements in a requested block to that of the process; I could test access by checking an address, and seeing if it belonged to the accessing process. Unfortunately, the program has two metrics -- the speed of the manager and the RAM it uses; representing all of memory takes up far too much RAM in a vector. So here is my second proposal, and I'd like to get some feedback on it. I'm trying to optimize both speed, and memory usage. --------------------------------- Allocations are first done by looking on the "free pool". The free pool is something I thought up that will be a vector of queues, containing starting addresses in memory of blocks of a certain size. For example, if I recently deallocated a block of size 4, I add it to the free table and the next allocation of size 4 could find that block quickly and use it (helps me avoid fragmentation and wasted space). If no such block exists, I simply use the memory after the last ever used address. Once I have a starting address, I add this information to a vector of linked lists representing the processes, and all the blocks currently allocated to them. To clarify, the 0th element of the vector corresponds to process 0, and each element in the linked list contains a struct with the starting and ending address of the memory allocated to it. (A "process" vector, with a linked list of start/end address of memory pairs. The indexes of the vector correspond to a process-id of sorts)

Process Vector
[0][0, 15][50,434]
[1][30, 56]
[2]
[3][5,25]

Since allocations compromise the majority of the operations, they need to be fast. I figure that allocations can be done in O(1) time with this implementation. Memory usage should be much lower than representing every single block in memory, as compared to a vector. Accesses are simply a matter of finding the process in the vector (jumping to its index) and looping through the linked list to check if the accessed memory is in range. If it is, great, return success; if not, end the offending process. Though going through the linked list requires O(n) time for a given process, the number of blocks each process has at any given time is relatively small, and with the large size of our data set (300,000+ operations), a small price to pay. Deallocation instructions receive a process and a starting address from the file, so simply index into the process vector, loop through its corresponding linked list to find the starting address, and remove it from the vector. If the block of memory just allocated is fairly small, add it directly to the free pool so that it can be used again. If it's fairly large, we probably won't need another block of that exact size, so I'm thinking of chopping it up into smaller, more usual portions since the memory allocations run on the small side. Again, if I'm thinking about this right, I should be able to deallocate in O(1) time (of course there is the small cost of going through the linked list, but it should be small) Anyway, I realize this is quite long and drawn out and probably too confusing for anyone to read (not to mention possibly in violation of the rules :P) but if anyone can offer some feedback perhaps on my expression of the memory and how I plan to handle the various memory management operations, that would be greatly appreciated :) Thanks in advance!

(please note thast i'm being very misleading and vague in some areas, this is to force you to think for yourself.)

ok, you have a vector of vectors.

Vector(0) will be the first processes vector, up ntil vector(n).

You also have a vectors of arrays. those are arrays which are 2^16 entries big.

When acessing, you look at vector(0), you then check vector(0).vector(0) up to vector(0).vector(n), you look at
*arr[0] and
*arr[2^16]

you represent the memory using a pointer.

If it is >= arr[0] and is <= arr[255], then, you simply acess
arr[pointer - &arr[0]]

And output it.

if it is > arr[255], then search further along (look up Binary Search which you can use to get this into log2n n time).
if it is < arr[0], then saearch closetr to the beginning.

in the vectors, you keep an int, which stores how much of the array has been allocated (or 2^16 if it is all allocated).

What you do, is, if process(n) is requesting memory,
you look at vector(n).vector(up), where up is the last entry in the vector.

If its int is < 2^16, then you simply increment it, and hand back
*arr[pointer++]

deallocation would work, by "handing back", the pointer, and having another two vectors, which are sorted, and which swap the pointers arround.
so if *pointer == &switcha[n], then *pointer = &switchb[n]

This allows you to deallocate memory, by simply shoving it on the list, and having it return a null pointer. you also add an entry, in which the deleated pointer now represents a new spot on the array. (these pointers get swapped forward and backward, on i/o).

Please use your head, if you do, then you should get this in a few minutes.

From,
Nice coder (sorry, i'm not more specific, but it is you homework).