What happens after first alloc() call?

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

What happens after first alloc() call?

kraftwerk1611
This post was updated on .
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.
Reply | Threaded
Open this post in threaded view
|

Re: What happens after first alloc() call?

cadet1620
Administrator
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().

Heap after alloc(2)

* 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.
Reply | Threaded
Open this post in threaded view
|

Re: What happens after first alloc() call?

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?

Reply | Threaded
Open this post in threaded view
|

Re: What happens after first alloc() call?

cadet1620
Administrator
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
    ...