Improved Mem Alloc Algorithm Issue with using LinkedList?

[peterxu422]

Following the suggestion from the book of using a LinkedList for the improved memory allocation algorithm, the way I envisioned the implementation would be to implement our own LinkedList.jack and Node.jack class and create instances of these objects in the Memory.jack class.

However, if these objects were instantiated in Memory class, they would be stored on the heap right? And wouldn't that interfere with the Memory class heap management operations? For instance, the heap occupies RAM addresses 2048 - 16383. If LinkedList and Node objects were created, they would take up some of these addresses. Could that cause issues for the Memory class and alloc() function in terms of keeping track which addresses are taken and which are not?

It also seems that this approach would cause some recursive/circular definition of the alloc() function since you're trying to implement alloc(), but in the implementation you will make a call to alloc() again since you'd have to allocate space for LinkedList and Node(s).

Are these issues something I should worry about?

[cadet1620]

I would advise against using additional Jack classes to support the Memory class for several reasons.

You would not get into dependency problems using LinkedList and Node classes as long as the classes had no constructors or methods -- they would, in effect, just be structures and collections of functions.

The problems I see are:
  1)  The .vm files for these additional classes would need to be included with the other OS .vm files and copied into all applications before VM translation.
  2)  The Jack language does not explicitly specify the order and location of field variables within an object's instance data. You will need to make assumptions about how the supplied compiler allocates classes.
  3)  There is significant overhead calling and using objects.

What you can do is use Array variables which have the documented behavior that given:
    var Array a;
    var int i;
    let a = an_address;
    let i = an_offset;
then,
    a[i]
will access RAM[address + offset]

You can define a static Array class member to hold the head pointer for the free list.
You can implement the data structures shown in figure 12.6b by using an Array variable, block, and using block[0] for the block size and block[1] for the free list forward link.

--Mark

[Rather Iffy]

Some tips.

1. 1000 is the address of the 1001 -th memory cell. So because the memory array starts at 0 the offset should be 1000 + 1.
2. When searching the freeList in alloc() accessing and using the first node of the list needs special attention and probably makes necessary a special starting reference pointer arrangement depending on your list implementation.

--Chrit