Linked List and alloc

[pawdwanlearner]

Have a question on the alloc function for the operating system. The video says to keep track of the available memory segments in the heap. How does that correspond to its use. I have made the a class that implements a linked list. So after the first allocation the most of the list is still avialable. Then another allocation uses that memory. So are we keeping track of what has been allocated or are we keeping track of what is available.

[cadet1620]

You are keeping a list of what is available.  The list starts with one member -- the entire heap.

When an alloc() call is made, the block is split into two blocks (if possible) and part of it is given to the user.  You can return the upper or lower part to the user; it is easier to return the upper block since that does not require any changes to the links in the free list.

The returned block includes a header, but the address returned by alloc() is for the beginning of the data area.  (I like to set the link in the returned block to -1 to indicate that it is not a member of a list.)

When deAlloc() is called, the user block is relinked into the free list so that it can be reused.

Realize that your LinkedList class can not have constructors or destructors since those would need to use alloc() and dealloc().

--Mark

[pawdwanlearner]

Thanks for busting my bubble . Ill have to rethink my linked list implementation. I forgot i cant use something i don't have yet lol. Thank again Cadet

[cadet1620]

It is definitely a good idea to have routines that manipulate the linked list, just put them in Memory.jack.

If you want to write code that is a bit easier to read, define the offsets into the block header as static int in Memory and set them at the top of Memory.init

static int BLOCK_SIZE;   // = 0
static int NEXT_BLOCK;  // = 1;
...

function void init() {
    let BLOCK_SIZE = 0;
    let NEXT_BLOCK = 1;
    ...
}

function Array insertBlock (Array block) {
    let block[NEXT_BLOCK] = freeList;
    let freeList = block;
    return block;
}

The generated ASM will not be as efficient, but the source is much easier to read than hard coding numbers all over the code.

--Mark

[pawdwanlearner]

Thanks for the tip. I am wondering about the notion of dealloc(object base addr). The prof says to put the selected block at the end of the free list to denote its deleted. However, what happens when you delete the next one and the next. How are you going to be able to tell if the second and third from the last before null is actually deleted or another segment.

Note: unfortunately my linked list class methods manipulate a link list object created by using alloc(size).

like this

class Node{

   field int NodeData;
   field Node newNode;


   constructor Node new(data){
       let NextNode = newNode;
       let NodeData = data;      

       return this;

  }

}





class LinkedList
field int size;
field Node nextNode;

constructor LinkedList new(){
      let nextNode = null;
      let size = 0;

      return this;

}

[cadet1620]

The general concept of the free list is that it is a linked list of available blocks of free memory.  It starts as a single block that is the size of the entire heap and ends up being broken into multiple pieces.

The allocated blocks belong to the users who called alloc(), so they don't appear on the free list.

Here's an example that may help you see what's happening.

freeHead -> block -> 0
             14K

After a few alloc() calls with no dealloc() calls yet, the free list will still only have one block, and there will be a few blocks that Memory has given to users.

freeHead -> block -> 0
            12.5K

(user1)     block -> 0
             1K

(user2)     block -> 0
             500

Now (user1) is deallocated, so it goes on the free list.

freeHead -> block -> block -> 0
            12.5K     1K

(user2)     block->0
             500

The next alloc is a memory hog 8-)

freeHead -> block -> block -> 0
             2.5K     1K

(user2)     block->0
             500

(user3)     block->0
             10K

But it wasn't in use very long and is deallocated so it goes on the end of the free list.

freeHead -> block -> block ->block -> 0
             2.5K     1K      10K

(user2)     block->0
             500

Alloc() calls can use any of the blocks in the free list that are large enough to satisfy the request.  (The algorithm that is in the videos is "first fit" so it finds the first block that is big enough.)

---------------

The other problem with writing a LinkedList class in Jack is that for Memory, the list elements (the blocks) are variable sized.  Each block should be something like

int next;       // pointer to next block
int size;       // size of *data*
int data[size]; // user data

--Mark

[pawdwanlearner]

Okay i get it now. Im sure your students miss you. You have a way of making things more understandable.