Heap Management. We continue to talk about how our operating system manages the main memory resource of the host platform. And in particular, we are talking about the memory class of the Jack operating system. We already discussed the peak and poke which are two classical OS operations. And in this unit, we'll talk about alloc and deAlloc. Another two classical operations that every operating system out there implements in one way or another. So let us start with the need. Well, as you know, during run-time, the program that you write.I'm talking about high level programs typically creates. Possibly many objects and arrays. And we discussed many times this nice architecture in which every object and every array is implemented using a pointer that leads from some variable which typically resides in the stack. And this pointer points at some block in the memory that holds the actual data of the object or the array. Now, this area where we put the data of all the objects and arrays that application programs create is called heap, following applied computer science terminology. So the challenge is to manage this memory resource, which we call heap, to manage it efficiently. In particular, we have to know how to allocate memory whenever we're asked to do it. And we have to know also how to recycle memory of objects and arrays that are no longer necessary. Now, we're going to do all this using an OS class called Memory. And in particular, we'll have one function called alloc, that gets the size of the memory block that it has to allocate as an argument, and then it goes to the RAM, it finds the block that has this required size, and returns the address of this block to the caller. The sister of this function is deAlloc, that does kind of the opposite. It takes the address of a certain object or array and simply recycles the RAM space that was allocated to this object or array on the RAM. So I wish to remind you that if we want to manage the computer RAM, we typically divided into a certain area that we call stack, another area that we call heap. And let me give you kind of a high level perspective of what's going on. So let's put the operating system for a minute on the back burner, and let's discuss what the Jack programmer, or the Java programmer for that matter, sees. So the high-level programmer begins by creating some object variable, let's say that it's an object of type Point. And in response, what will happen is that a variable will be allocated somewhere on the stack and the label p will be associated with this variable. And this variable, at the beginning, is going to be reset to 0, or initialized to 0. Then, at a certain point of time, the high-level program may or may not call a constructor to actually build an object of type point. And associated with this p variable that has been declared before. What we'll get is something like this. I picked up an address from the heap arbitrarily, 8,012, and we allocate the block of the two words in this particular address, and then we create the link between p and this blank, as you see now, the contents of the p variable is the base address of the block that was assigned to represent this object. So that's how the high level programmer thinks about this act of creating a new object and as you know someone has to deliver this functionality. So if we still stick to be a high level view, this someone is the constructor because when we call point.new we invoke a constructor for its effect and as you see the constructor which resides in some, in the point class does all sorts of things, which are high level. But perhaps the most important thing that he does is something that you don't get to see. Because what happens is that when the compiler compiles this constructor code here. It is going to inject low level code that affects the operation, this = Memory.alloc(2). In other words, the constructor is going to take care of asking the operating system to allocate space for the new object. And by the way, knows that we need two words because it can look up the symbol table and realize that object of type point have two fields x and y. And because in our computer everything is 16-bit, both the data types at the high level and the width of the words in the memory, there's a one-to-one correspondence between the number of fields that an object necessitates and the size that you're going to pass to the Outlook OS function. So that's how the constructor is going to handle the allocation of space for the new object. Now, what about object destruction? Well, in object destruction, once again, if we take the high-level view of the Jack programmer, when an object is no longer necessary, like this object p that we created before, we have to say p.dispose(). We don't have to, but if we want to reclaim the memory that this object holds, we have to say p.dispose(). And likewise just like we had the constructor in the point class we should have also a disposer a function or a method called dispose and as you see unlike the constructor which implicitly created a new space on the RAM for the new object, the disposer explicitly recycles the memory block which is associated with this object. It explicitly does so by calling memory dot dialogue. Now, some of you have experience writing code in language like Java and C#, may wonder because you were never asked to actually deal with these things explicitly. And that's because languages like Java and C# has something called garbage collector, which is a process that runs always in the background, and does this thing for you automatically. In other words, the garbage collector keeps track of all the references that are being made to every object that your program creates. These references happen when more variable point to this object. And also at some point, you get all sorts of dereferences happening in your high level program. So when the number of references that point to a particular pointer, an object goes down to 0. The garbage collector kicks in, and calls deAlloc implicitly. So you don't have to take care of it yourself. We decided that we are not going to implement this goody inject. It's a very interesting algorithm and a very nice exercise, but inject, we don't have it, and therefore, we expect programmers to dealloc the memory associated with their objects explicitly. So we talked about object construction and destruction and we did everything from the high level of the programmer. Now let us take one step downward and talk about how we actually have to implement these things at the OS level. How do we do it? Well, we do it using an ingenious technique called heap management. And that's what we're going to discuss next. So let me begin with a simple approach or a simple solution to heap management and later on we'll present a more sophisticated approach. So it all begins with the bare bone RAM. And as you know, at some point, we're going to create some logical space in this RAM which we call stack. Another logical address space that we call heap, and each one of these spaces is going to have a base address, which we may call in our operating system, we may call it stackBase and heapBase. All right, so given this scenario, how do we do heap management? Well at the beginning, we take a variable called a free and assign it to heapBase. Now this variable, free is going to serve as the base address of all the memory which is freely available for new objects. So when we begin this program, when we begin the life cycle of the current program. Three points to heapBase, which means that the entire heap is now game. We can use, the whole heap is ready for our disposal. So, the next thing that we're going to talk is alloc. Alloc size, which allocates the memory block of size words. So let us assume that some client comes along and says alloc(3), I need a block of size 3. How are we going to do it? Well here is a small little simulation. As you see we have carved the top three words from our free area and we are giving it to the caller. And in order to do it, or as a side effect of doing it, we have to first of all, assign it a certain pointer, so that we will be able to tell the caller where this block begins, and we call this, Base address block. Another thing that we have to do, is we have to, as you just saw, we have to update free, right? Free before used to point at heap base and now we have to do free equals free plus 3 to reflect the fact that we have 3 less words available in heap. And finally, we have to return block to the caller. So everything that I've just described by waving my hands and with this little animation is shown here in the code, block equals free. Free equals free plus size, return block. Now, these three things taken together will handle the act of carving out and allocating a block of sized size. Now, at some point, the user who is a high level programmer may decide to deAlloc a certain object. How do we do this? Well, I promised you that my algorithm and my approach are going to be simple. So, if someone says deAlloc block, we simply do nothing. We don't bother, okay? Well, this will work for awhile until at some point we'll run out of memory, right? Because we only go down, right? We never recycle, we never put memory back into the pool. So this is appropriate for optimistic people, who hope that the execution of their programs will terminate before the memory does, right? But in reality if you have a program that creates thousands, and millions of objects, which happens every once in awhile, then you need something more clever, right? You have to work a little bit harder to manage your resources in a less wasteful and more responsible manner. And that's what we're going to do next. So here's a more realistic solution. We're going to use a linked list to keep track of all the heap segments, which are presently available to us. So what do you see here is a snapshot of how this link list would appear after we already created the few objects and arrays in our program. So we have a free list and these are all the memory sources which are presently available to us. This is something which is managed by the operating system. Now, every element of this list has the following anatomy which I describe below. So once again, what you see below is, sort of a more detailed description of the segment that sits in the middle. So a typical segment has a data part, which contains all the words which are available to store the actual data of the object of the array. As well as two overhead words, which include, first of all the size of the data block and a pointer or reference to the next segment in the freeList. That's the anatomy of everyone of these segments. So with that in mind, what do we do when someone says alloc(size)? Well, we start going through our linked list, and we look for a block that has the right size. And once we find this block, we can remove it from the linked list and give it to the caller. What do we do with dealloc? If someone says dealloc(object) and gives us some address in memory. We can take the block of which this address is the base address. And simply append it to the end of the freeList. So that's the basic idea of what we're going to discuss next in detail. All right, so let's start with alloc. Suppose that someone comes along and says alloc(3). Give me a RAM block of size three. How do we service this call? Well, let me start with some terminology. If the segment size is greater than size+2, we say that the segment is possible. So if you look at this freeList right here, you will see that the first segment is not possible, right? Because the size of this segment is 6, and, in fact, we need. I'm sorry, the the data size of this segment is 4. And, in fact, we need 5, because we just decided that we need 3 + 2. The 2, of course, are for the overhead fields which are absolutely necessary. However, the last two segments are possible, so we can use them to service this call. So we're going to search the freeList for one of two different possibilities. There's one algorithm which is called first fit. And this algorithms marches through the freeList and it looks for the first possible segment that is found. And then there's another algorithm, very similar, which is called best fit. Which looks not necessarily for the first segment but rather for the smallest possible segment. So here is first fit. In this example, it will hit on the second segment and the best fit happens to hit on the last one. Now the benefit of first fit is that it's kind of a greedy algorithm that gives you an answer as quickly as possible. The benefit of best fit is that it manages the linked list in a more efficient way. And which algorithm to use is a matter of all sorts of considerations that I'm not going to get in to. So we don't care if you'll implement first fit or best fit, it's up to you. All right, so let us assume that we use the first fit algorithm. We found this segment. What do we do next? Well, we are going to carve a block of size size+2 from this found segment. And we'll return the base address of this block the caller. So, this will be the situation after the allocation. What you see at the bottom is the block that we hand to the caller. And what you see on top of it is the freeList following the allocation. As you see we have updated the freeList in order to account for this allocation that just took place. Now what about deAlloc? Well, suppose that we have this object here. The handle to this object is block. And we want to recycle it. We want to put it back into the pool of freely available memory. Well we do it using a call to deAlloc(object). And so for example, if someone says deAlloc(block). What we do is we append this object to the end of the freeList. So we'll end up with this situation here at the bottom. You see that the block which is no longer necessary was appended to the end of the freeList. And now the data that the array contains is no longer relevant. But it may well serve objects and arrays that will be created later on. So that's how deAlloc is implemented. Now notice that the more we recycle, the more the freeList will become fragmented. And by fragmented we mean that it will contain many segments which are rather short. And this is going to be a little bit frustrating. Why? It will be frustrating for alloc. Why is that? Well,one way to describe it is the following. Suppose you drive your car and you want to park it somewhere. And I bet you know this feeling. That you drive along the road and there are quite a few parking spaces available. But all of them are too small. All of them are half a meter smaller than the size of your car, or one meter smaller or a quarter or just a centimeter smaller. See, that's a fragmented situation. And I bet that you had this feeling that I have all the time. That wouldn't it be nice if we could take a few cars and sort of push them forward? And close all these fragmented gaps so that we can create one gap that would be sufficiently large to fit our car in. Well, that's exactly what we want to do here. If you want to create a new object or a new array which is larger than any one of these blocks. It would be nice if we could take a few of these blocks and put them together, merge them, to create some larger blocks. This process is done by an algorithm called defrag, standing for defragmentation. And indeed, in every operating system every once in a while defrag kicks in. It goes through the entire freeList. And it tries to merge as more small segments that it can into continuous segments in the memory. And this is something that we have not included in our operating system. And once again if you want to implement it, you're welcome to do it, but you're not required. It's a nice extension project. So let's talk about some implementation tips, which in this particular case, are kind of interesting and important. So this is a snapshot of our memory map, and we're implementing the memory class of the operating system. And in particular, we want to implement this freeList, right? We want to create and manage it somehow. So we propose to create a static array that you can call heap, that's quite a natural choice. And we propose that, somewhere in your Memory.init function, you will do the following things. First of all, you set heap, which is the base address of this array, to the agreed upon base address of the heap. Which is a convention, that in the Hack computer happens to be 2048. Then, you set freeList to this very same heap base, so at the beginning the freeList begins at the beginning. We also set heap[0] to 0, because currently or presently at the beginning, the freeList contains one segment only. And the size of this segment is the size of the entire heap. 14,000 and something, something 16,000 and something minus 2,048. Which on the Hack computer happens to be this number here. So, at the beginning, when we just get started, as you see in the initial state, the entire heap is available. freeList contains one long segment, and it kind of degenerates to the simple setting that we had before. Now what happens next? Well, by the way, I have to say something about Memory.init. I did not include it in the public API that I showed you, because clients of the OS are not supposed to mess up with it. But we do need an init function at the OS level, and that's exactly what this init function does. It sets up the free list for us. All right, so here is the situation, after a few alloc and deAlloc operations took place. What you see in the middle is the abstraction of the freeList, and what you see on the right is how this freeList is actually implemented in memory. And if you don't see it very well, I will add some color, and now things become a little bit more obvious. If we look at the top of ram, we see that the freeList contains the number 8012, so that's where the first segment is located. And then this segment points at 7513, so that's where the pink segment starts. This segment points at the 9576, that's where the blue segment starts, and the last one. And indeed, we see that this segment points at 0, which is the end of list value. So that's how the freeList is implemented in memory. Now, as I said, we can realize this freeList using the heap array. [LAUGH] And one thing which you have to realize is that, although we declare this array, as you see, static Array heap, we never call array new for it right? Because first of all, we cannot do it, because array new is going to call alloc and we're implementing alloc. So, this is unacceptable, but even if we did, this array would be too large to fit into memory. So this is yet another example of a little hack that we use of using an array not really as an array, but rather as some collection of pointers. Which we use for our benefit in order to create this freeList for us. And the next, and the size properties of every memory segment are realized, or can be realized, using heap[addr-1] and heap[addr-2]. If you don't completely understand it, just when you start building it in project 12, you will realize that things will kind of fall into place, believe me. If we have all these thing represented for us, then deAlloc, and the alloc, and deFrag can be realized as operations on this heap array. So to recap, init is going to be implemented using this psuedocode here. alloc(size) will be implemented using this psuedocode here, which we discussed before. We are looking for either best fit or first fit, first fit is probably easier to implement. And if we find this block, great, if we don't find such a block in the freeList, then we can try to do a defragmentation. And then we have to update the freeList to reflect the allocation, and return the handler to the newly-assigned object. And deAlloc is much easier to implement, all we have to do is take this object and append it to the end of the freeList. So that's it, we finished implementing the memory class. We implemented peek and poke in the previous unit, and we've implement alloc and deAlloc in that unit. All these functions are classical, you can find them in any operating system out there. And now, we actually understand how they work. So that's it, we are done with the memory class, and in the next unit, we're going to delve into graphics.
