Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени
Сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

Unit 6.5: Heap Management

Loading...

Build a Modern Computer from First Principles: Nand to Tetris Part II (project-centered course)

Еврейский университет в Иерусалиме

5 (оценок: 226) | Зарегистрировано учащихся: 17K

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.

Просмотреть программу курса

Получаемые навыки

Computer Architecture, Compiler Construction, Compiler, Operating System

Рецензии

5 (оценок: 226)

5 stars
216 ratings
4 stars
10 ratings

RR

Jul 16, 2017

This is an excellent course giving good view of operating system, compiler and fitting the pieces together. Highly recommended

AD

Sep 02, 2018

One of the best computer science courses I ever had. You start understand how actually things like heap, stack, etc. works.

Из урока

Operating System

Unit 6.1: Operating System15:23

Unit 6.2: Efficiency Matters17:39

Unit 6.3: Mathematical Operations21:27

Unit 6.4: Memory Access12:32

Unit 6.5: Heap Management30:47

Unit 6.6: Graphics15:01

Unit 6.7: Line Drawing25:17

Unit 6.8: Handling Textual Output18:46

Unit 6.9: Input16:58

Unit 6.10: String Processing17:34

Unit 6.11: Array Processing6:09

Unit 6.12: The Sys Class12:48

Unit 6.13: Project 12: Building the OS11:52

Unit 6.14: Perspective7:32

Преподаватели

Shimon Schocken
Professor

Текст видео

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., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы