Good afternoon. Let's get started.
So today, we are going to be continuing our quest into Computer Architecture.
And we're going to be talking about virtual memory and address translation.
Together with how you do virtual memory protection, on top of that.
So this is a crossover between architecture and operating systems topic.
So, your operating systems, many times, has to worry about how to manage memory.
Also, many times, you have to worry about how to manage who can access memory.
You have to worry about how much memory different users could possibly have.
But even in a uni-processor system, this becomes an important thing.
That a uniprocessor system and a uniuser system,
Not a multiprogram system and not a multiuser system,
But just a single user system also has to worry about layout of memory.
And worrying about running different libraries, different portions of programs,
And how to lay that out effectively in memory.
So, we're going to continue videotaping our lecture today, put online so you guys
can go look at later. And so let's get off by starting to talk
about memory management. And we're going to talk about a couple
different schemes today which aren't very popular.
[laugh] We're going to talk about some schemes that have some historical basis
that are still important in, important to understand and there's some vestiges in
today's architectures. So, for instance, one of the things we're
going to be talking about today is called segmentation or base and bound registers
which still shows up in X86 processors today,
But is not very common as a memory protection system.
But it was designed as a memory protection system when it first got started.
And then, we're going to go, and at the end of today's lecture, we're going to
talk about fancier virtual memory systems that are used in modern day computers, how
your operating system goes about managing memory with that, how it pro, provides
efficient use of memory, and how it protects different accesses.
So, we can broadly separate memory management into three really important and
orthogonal functions. First of all, translation.
So, in translation, what we're doing is we're taking one address and we're turning
it into some other address. So, we're able to remap addresses.
Now, you might say, Why do we want to do that?
Well, By doing that, we can have more flexible
memory layouts and prevent things like fragmentation.
So, fragmentation, we'll talk about that more later in today's lecture.
But fragmentation basically is the problem that you have lots of little pieces of
data or code that get loaded. And then some of them completes or go
away. You're going to end up with holes in your
memory space. And it's very hard to reclaim that unless
you try to compress or re-layout the memory.
And lots of program models don't allow you to go and recompress the memory.
This is familiar if you've ever taken a, a basic data structures course, where you
had to go deal with managing something like a heap.
In a heap, you have pretty common to, it's pretty common to allocate different sized
objects on your heap, and then you free up those different sized objects, and if you
happen to free them in a bad order, you end up with little chunks of memory that
are really hard to go use for something else.
Especially if you want to go allocate something very large, you might have
enough memory in your system, but it's just not contiguous.
So, what approached to this is to have things like garbage collectors which is
what Java and a lot of the managed programming languages do.
But something like C or C+++ does not a notion of garbage collectors.
So, we're going to look at more not from a heap perspective but from a perspective of
the entire memory system. So, sort of one level out from a heap.
So, interprogram fragmentation and interprogram garbage collection.
The second important function of our memory management here is we want to
restrict access or protect access to memory and allow only users who are
supposed to be able to touch a certain piece of memory to be able to touch that
certain piece of memory. And this is important if, for instance,
you have one system which has someone's bank records on it.
And on that same system, someone else can log in, they can telnet or SHS into it or
remotely log into it. And you don't want one user to be able to
go read some other user's bank records that just happen to be laying in memory.
So, we need some way to protect that and memory protection gets us there.
It allows us to have different users using the same system, different processes using
the same system, and we can restrict the access to different locations in memory or
protect the access to different locations in memory.
Finally, memory management. One of the important sort of points in
memory management is that you can actually think about having more memory than your
machine has memory. Now, you might say, that doesn't make any
sense. No, it doesn't make any sense.
But if you have a flexible enough hardware system, you can think about using other
things to look like memory. So, for instance, if you have a hard drive
in your computer, you can use that hard drive which is very, very large to
effectively increase your memory size by taking the data which is laying in memory
and put it onto the disk. And sometime later in the future, take it
off the disk, and put it back into memory and trick the user into thinking they have
a larger memory space, and this is virtual memory so it allows us to have transparent
extension of the memory space using something slower.
I mean, could be disk, it could be in the older days some drum that spins where you
sort of store things on the drum you could even, I could even, nowadays, you can even
swap on flash. If you ever go look in or something like
that, this is called your swap partition. Sometimes called a backing store, a couple
different names it goes by, but it's a virtual manage virtual memory storage
location. Nowadays,
Most systems provide us with some sort of page based system, which we'll be talking
about. But there, these ideas are all orthogonal,
and you can have different mechanism is to solve all of them in different ways.
And we'll be talking about some of the historical aspects of that.
Okay, so, let's start off in the beginning.
Well, in the beginning, we didn't have fancy memory management.
Instead, we had addresses. You want to go access some piece of
memory, you come up with an address. And that directly indexes into our memory,
and you get back the data. Well, that's okay if you're running one
program at a time. So if you go back and look at EDSAC, which
is one of the original, probably the second computer, I think.
Maybe the first computer. Oh, the first sort of, modernish looking
computer. It only had physical memory addresses.
So, what this really meant is only one program can run at a time.
And, it had all of memory. And the addresses that were used,
basically didn't move around because there was only one program running and it owned
everything. An IO could directly touch memory.
Main processor could directly touch memory.
And life was simple and okay. But, unfortunately you couldn't really run
multiple programs, you couldn't protect multiple programs.
You could definitely not take memory off of disk and put it into memory, cuz you
had no way to sort of remap things. So, it did not fulfill those sort of three
requirements that we were talking about. We didn't, it didn't do any translation.
It didn't do any ability to protect, and it didn't have any notion of virtual
memory. One thing that did happen is that users
still wanted to be able to write sub-routines that were location
independent. So, what I mean by that is you write a
subroutine, and this was back in the days when people were writing these subroutines
in machine code or assembly code, And you still want to do the regular, one
subroutine and use it and call it, and use it in different portions of your programs.
So, one of the trick that people sort of thought about is, how can you still have
location independence even when you only have one physical address space, so you
can't remap things, there's no translation going on here.
Well, In fact, you can actually use the linker
or the loader to be able to go do this. So, actually, quick show of hands here who
knows what a loader is? Who knows what a linker is?
Okay, so we've got a little bit of coverage with linker. linker,
What it does is it takes multiple different compilation objects or
compilation units. So if you take a computer program that's
made out of a bunch of little files, a bunch of different source files,
You compile up each of those separately. And when you link it, you take them and
you put them all together into one program, and you resolve all the
addresses, all the jumps, and the data accesses across that one program.
So, that's linking. That's static linking.
Now, dynamic linking. You guys might have seen, DLLs.
Did I make dynamically linkable loadable objects.
So, what happens with DLLs is, you'll actually do that linking step of resolving
the addresses at runtime. So, you could actually do either,
You can either do it dynamically or statically.
And the loader is the piece of code which actually takes a binary off a disc, and
puts it into memory somewhere. And typically, the loader will go and do a
last level linking step at the end. So, on a modern day Linux system, your
linker, Or excuse me, your loader,
When you type a when you go to execute a program and you type I don't know,
You run LS or something like that on your Linux system.
First thing it does is it goes and finds the LS bits on the disk and it takes that
and copies it up into RAM, Somewhere.
So, you could do this on this absolute addressing system.
And then what it does is it goes and it figures out all of the dynamic vibrates
that are needed. And it goes and takes those off disk and
puts them into RAM somewhere. And then, it's going to, last step here is
the original program had pointers to address that didn't actually exist yet.
Cuz it didn't know where the respective loaders, respective libraries are going to
be loaded. So, it has to patch the program up.
It has to rewrite addresses to make sure that the newly load program points up the
correct location. So, that's a runtime linker doing its job.
The static linker can do that same sort of thing but at a compile time could be an
assembly time or linking time in your program.
Okay. So, that's absolute addresses and if you
have the physical hardware for an absolute address machine, it's simple.
It's kind of what we have been looking at, at this point.
You have your program counter, you stick it in your cache, it gets, the instruction
cache gets an instruction out. You take your address if you're doing
memory access, you stick it into your data cache, and it gets some data out.
If you take misses everything to physical address, it goes into the memory control
and goes out to DRAM. Seems, seems simple.
It is. But, like I said, it doesn't solve all the
problems we want to solve. Okay, so now, let's start talking about
stuff that's a little bit more, more complex if we actually want to do address
translation. So, address translation, actually before
we leave this, we're going to call addresses that touch main memory, physical
addresses. And we're also going to talk about this
notion of a virtual address. A virtual address is actually just an
address that the main processor uses which might be translated somehow into an
address which is out in main memory.