What happens after first alloc() call?

[kraftwerk1611]

Hi,

I have been trying to implement alloc() and dealloc() subroutines but I am finding it difficult to find out where to start and how to start.

Following are my questions,

* How many static arrays do we need to implement these surboutines? The book chapter 12 and lectures refer to several arrays. Are ram, heap, freelist, block are all arrays? Are freelist and heap different names for same array?

*The linked list in book as size as the first element of memory segment, while lecture  have 'next' pointer as first element of memory segement? Does it matter, which one we choose? The commands like

let heap[0]=0;
let heap[1]=14335;

show that first element in linked list is next pointer.

*Is it right that value stored in variable 'heap' on stack will remain fixed at 2048 but value stored in 'freelist' on stack will keep changing?

Is it so that initially freelist=2048 but it will keep changing?

*Do we have to use an array named 'ram' that is initialised as

let ram=0;

Why do we need this array?

*Should we think of 'heap' array as something different from the actual Heap memory segment [2048...16383] and one that is managed separately as a linked list only?

*My main confusion is about what happens after ver first call to alloc(). The book page 255 show state of memory after several alloc() and dealloc() calls.

If at the very beginning we have

heap[0]=ram[2048]=0
heap[1]=ram[2049]=14335

Then if the firt allocation request is alloc(2), then what happens to the heap memory segement and heap array?

Is it so that now first 4 memory addresses in heap memory area[2048...2051] will not be available anymore? Will the values stored in array heap, heap[0] and heap[1] need to be updated now to heap[0]=2052 and heap[1]=14331 or do we leave heap[0] and heap[1] untouched and update some other variable or heap array elements.


*If 'heap' array is something different from heap memory and is maintained separately does it only start building up after first dealloc() is called as before that whole memory is available for use and we can simply keep allocating memory blocks to alloc() calls.

* The last element of linked list should point to 'null'. Does it also apply only when first dealloc() has been called?

* Which address is returned by alloc()? Is this the first address of whole memory segment  including size and next pointer or is it the address after size and next elements?
In case of alloc(2) as the very first call, will the returned value be 2048 or 2050?


I am sorry if these questions sound too simple but I am really not clear how to visualise this problem and should I see heap memory and heap array as two different things.

Thanks.

[cadet1620]

kraftwerk1611 wrote

* How many static arrays do we need to implement these surboutines? The book chapter 12 and lectures refer to several arrays. Are ram, heap, freelist, block are all arrays? Are freelist and heap different names for same array?

*Do we have to use an array named 'ram' that is initialised as

let ram=0;

Why do we need this array?

There are no static arrays used in implementing the heap. It is convenient, however, to have a single "static Array ram" that is initialized to 0 as the first thing in Memory.init(). Doing this effectively extends the Jack language so that you can use
    ram[addr]
to read and write directly to the RAM memory.

*The linked list in book as size as the first element of memory segment, while lecture  have 'next' pointer as first element of memory segement? Does it matter, which one we choose? The commands like

let heap[0]=0;
let heap[1]=14335;

show that first element in linked list is next pointer.

To make things clearer, refer to the two parts of the heap segments as the segment header and the user data.
It does not matter which order the two values in the segment header. It also does not matter if the size in the segment header is the total segment size or the user data size, as long as your code is self-consistent.

The book uses size first/segment size, and the videos present next first/user size.

NOTE: There is a typo in the videos. heap[1] should be set to 14334, the total size of the heap - 2 words for the header.

*Is it right that value stored in variable 'heap' on stack will remain fixed at 2048 but value stored in 'freelist' on stack will keep changing?

Is it so that initially freelist=2048 but it will keep changing?

*Should we think of 'heap' array as something different from the actual Heap memory segment [2048...16383] and one that is managed separately as a linked list only?

*My main confusion is about what happens after ver first call to alloc(). The book page 255 show state of memory after several alloc() and dealloc() calls.

If at the very beginning we have

heap[0]=ram[2048]=0
heap[1]=ram[2049]=14335

Then if the firt allocation request is alloc(2), then what happens to the heap memory segement and heap array?

Is it so that now first 4 memory addresses in heap memory area[2048...2051] will not be available anymore? Will the values stored in array heap, heap[0] and heap[1] need to be updated now to heap[0]=2052 and heap[1]=14331 or do we leave heap[0] and heap[1] untouched and update some other variable or heap array elements.


*If 'heap' array is something different from heap memory and is maintained separately does it only start building up after first dealloc() is called as before that whole memory is available for use and we can simply keep allocating memory blocks to alloc() calls.

freeList needs to be a static variable so that both alloc() and deAlloc() can use it.

heap is a local variable only used in init().

segment is a local variable used in alloc() and deAlloc().

Since the values stored in freeList and the next pointer in the segment header are RAM addresses, there is no need for the heap variable in alloc() or deAlloc().

* The last element of linked list should point to 'null'. Does it also apply only when first dealloc() has been called?

* Which address is returned by alloc()? Is this the first address of whole memory segment  including size and next pointer or is it the address after size and next elements?
In case of alloc(2) as the very first call, will the returned value be 2048 or 2050?

The link in the last element of a linked list should always be null. There is a special case when the list is empty, then the freeList value itself will be null.

The values returned by the alloc() call are the address of the user data, so in this case that would be 2050.

Note that since deAlloc is called by the user with the address that was returned by alloc(), that address needs to be adjusted to get the heap segment address that is to be freed:
    deAlloc(object) {
            var Array segment;
                let segment = object-2; // size of segment header

Also note in deAlloc() that it makes no difference if the deallocated segment is added to the beginning or the end of the free list.  The book and video show adding it to the end, but it is easier to add it to the beginning of the free list.

[kraftwerk1611]

Thank you,

Referring to your sentence 'heap is a local variable only used in init(). ', is it so that heap array initialised in init() function as

heap[0]=0;
heap[1]=14334;

is not used outside the init() function?

[cadet1620]

kraftwerk1611 wrote

Thank you,

Referring to your sentence 'heap is a local variable only used in init(). ', is it so that heap array initialised in init() function as

heap[0]=0;
heap[1]=14334;

is not used outside the init() function?

Like all object variables, heap is a pointer. It needs to be initialized to what it points to:

function void init() {
    var Array heap;
    // Initialize heap as a single segment
    let heap = 2048;        // heapBase
    let heap[0] = 0;        // segment.next
    let heap[1] = 14334;    // segment.userSize
    // Put the segment on the free list
    ...

Using heap this way makes the code more understandable. This could have been written as:

function void init() {
    // Initialize heap as a single segment
    let ram[2048] = 0;
    let ram[2049] = 14334;
    // Put the segment on the free list
    ...

[Sai krishna]

Hi, I have a question about the alloc algorithm. When a segment of suitable block size is found, is the block to be allocated carved out at the bottom of the free segment or at the top of the free segment(from just below the header of the free segment)? Which is better implementation?

[WBahn]

How this is done is entirely up to you. Various approaches have different pros and cons under different use cases, so someone that is writing a memory manager for a program that seldom frees up memory once it is allocated might do it very differently than one intended for programs that frequently free up memory shortly after it is allocated, versus the case where it is assumed that allocation and deallocation are happening more or less randomly.

It also depends on how you plan to handle defragmentation of your heap (this is, IF you are planning to do so).

Way too many possibilities to give a definitive answer.

[nemethda]

Sorry Mark, may I have a question about your screenshot depicting the memory's state after calling Memory.alloc(2)?

I don't understand the values in 2048 and 2052: you have both of them showing 0. But shouldn't these show the 'next' memory block's address? In my understanding after the allocation of the first block, ram address 2048 has to show 2052, as that's the address of next block.. or am I missing something?

Thanks very much!

[WBahn]

The memory block at 2048 is an allocated block of memory, so it doesn't have a "next" block because it is no longer a member of the list of free memory blocks. In fact, you can get rid of this cell altogether and just have a single cell in the block overhead that says how much memory the allocated block has. That can be valuable if your application allocates a lot of very small blocks of memory because your block overhead becomes a limiting factor on how much memory you can successfully allocate. But changing the size and interpretation of the block overhead has costs, though if you do it thoughtfully it is pretty minimal. One way is to have the first cell be the size of the block and the second be the pointer to the next block. You can do it many different ways, you just have to make sure that the bookkeeping that has to be done is done consistently.

[nemethda]

Thanks WBahn for the response! I guess I'm confused by Slide 44 (of the Jack OS pdf) where for an allocated segment the top cell shows the address of the next allocated memory block, at least that's how I understood it so far. I'll think about this...



Oh now that I'm writing this answer and staring at the slide I just realized that freeList is set to 8012 in this example, so taking your comments on board: I guess that's where the next available (not allocated) memory located at - and then next free block with a size of 7 is @7513 and so on? This way your comment makes sense!
 
To be honest right now I have the very simple solution that passes the test and now I'm just concentrating on passing the last hurdles so I can complete the course. I'm loving it but it is taking forever already for me :) Then when I'm done hopefully I can revisit this topic.

[nemethda]

Apologies for the giant screenshot, not sure how to reduce its size..

[WBahn]

The screenshot is fine.

As you can see, by trying to clearly explain the problem and your thinking about it, you had to deal with the issues at a level of detail that brought everything into focus. That is very commonly the case.

I must have one the best educated dogs on the planet, because when I'm really struggling with something I explain it to her like she's a total blithering idiot (which she is) and that forces me to operate at that level. It works!

[nemethda]

:) Thanks WBahn! Maybe I need to get a dog then ;)