In this project-centered course you will build a modern software hierarchy, designed to enable the translation and execution of object-based, high-level languages on a bare-bone computer hardware platform. In particular, you will implement a virtual machine and a compiler for a simple, Java-like programming language, and you will develop a basic operating system that closes gaps between the high-level language and the underlying hardware platform. In the process, you will gain a deep, hands-on understanding of numerous topics in applied computer science, e.g. stack processing, parsing, code generation, and classical algorithms and data structures for memory management, vector graphics, input-output handling, and various other topics that lie at the very core of every modern computer system. This is a self-contained course: all the knowledge necessary to succeed in the course and build the various systems will be given as part of the learning experience. The only prerequisite is knowledge of programming at the level acquired in introduction to computer science courses. All the software tools and materials that are necessary to complete the course will be supplied freely after you enrol in the course. This course is accompanied by the textbook "The Elements of Computing Systems" (Nisan and Schocken, MIT Press). While not required for taking the course, the book provides a convenient coverage of all the course topics. The book is available in either hardcopy or ebook form, and MIT Press is offering a 30% discount off the cover price by using the discount code MNTT30 at https://mitpress.mit.edu/books/elements-computing-systems. The course consists of six modules, each comprising a series of video lectures, and a project. You will need about 2-3 hours to watch each module's lectures, and about 15 hours to complete each one of the six projects. The course can be completed in six weeks, but you are welcome to take it at your own pace. You can watch a TED talk about this course by Googling "nand2tetris TED talk". *About Project-Centered Courses: Project-centered courses are designed to help you complete a personally meaningful real-world project, with your instructor and a community of learners with similar goals providing guidance and suggestions along the way. By actively applying new concepts as you learn, you’ll master the course content more efficiently; you’ll also get a head start on using the skills you gain to make positive changes in your life and career. When you complete the course, you’ll have a finished project that you’ll be proud to use and share.
Unit 6.5: Heap Management
Loading...
From the course by Hebrew University of Jerusalem
Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)
144 оценки
Hebrew University of Jerusalem
144 оценки
From the lesson
Operating System
Meet the Instructors
Shimon SchockenProfessor
Computer Science
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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
