1
00:00:03,400 --> 00:00:07,140
Good afternoon.
Let's get started.

2
00:00:07,860 --> 00:00:12,810
So today, we are going to be continuing
our quest into Computer Architecture.

3
00:00:12,810 --> 00:00:17,500
And we're going to be talking about
virtual memory and address translation.

4
00:00:17,500 --> 00:00:21,800
Together with how you do virtual memory
protection, on top of that.

5
00:00:22,569 --> 00:00:27,597
So this is a crossover between
architecture and operating systems topic.

6
00:00:27,597 --> 00:00:32,974
So, your operating systems, many times,
has to worry about how to manage memory.

7
00:00:32,974 --> 00:00:38,281
Also, many times, you have to worry about
how to manage who can access memory.

8
00:00:38,281 --> 00:00:43,588
You have to worry about how much memory
different users could possibly have.

9
00:00:43,588 --> 00:00:48,266
But even in a uni-processor system, this
becomes an important thing.

10
00:00:48,476 --> 00:00:51,811
That a uniprocessor system and a uniuser
system,

11
00:00:51,811 --> 00:00:54,932
Not a multiprogram system and not a
multiuser system,

12
00:00:54,932 --> 00:00:58,962
But just a single user system also has to
worry about layout of memory.

13
00:00:58,962 --> 00:01:03,389
And worrying about running different
libraries, different portions of programs,

14
00:01:03,389 --> 00:01:06,000
And how to lay that out effectively in
memory.

15
00:01:07,100 --> 00:01:12,395
So, we're going to continue videotaping
our lecture today, put online so you guys

16
00:01:12,395 --> 00:01:16,698
can go look at later.
And so let's get off by starting to talk

17
00:01:16,698 --> 00:01:20,670
about memory management.
And we're going to talk about a couple

18
00:01:20,670 --> 00:01:23,891
different schemes today which aren't very
popular.

19
00:01:23,918 --> 00:01:27,925
[laugh] We're going to talk about some
schemes that have some historical basis

20
00:01:27,925 --> 00:01:32,731
that are still important in, important to
understand and there's some vestiges in

21
00:01:32,731 --> 00:01:36,410
today's architectures.
So, for instance, one of the things we're

22
00:01:36,410 --> 00:01:41,156
going to be talking about today is called
segmentation or base and bound registers

23
00:01:41,156 --> 00:01:43,826
which still shows up in X86 processors
today,

24
00:01:43,826 --> 00:01:46,970
But is not very common as a memory
protection system.

25
00:01:46,970 --> 00:01:51,480
But it was designed as a memory protection
system when it first got started.

26
00:01:52,080 --> 00:01:56,008
And then, we're going to go, and at the
end of today's lecture, we're going to

27
00:01:56,008 --> 00:02:00,721
talk about fancier virtual memory systems
that are used in modern day computers, how

28
00:02:00,721 --> 00:02:05,154
your operating system goes about managing
memory with that, how it pro, provides

29
00:02:05,154 --> 00:02:08,690
efficient use of memory, and how it
protects different accesses.

30
00:02:08,690 --> 00:02:16,000
So, we can broadly separate memory
management into three really important and

31
00:02:16,000 --> 00:02:19,566
orthogonal functions.
First of all, translation.

32
00:02:19,566 --> 00:02:24,899
So, in translation, what we're doing is
we're taking one address and we're turning

33
00:02:24,899 --> 00:02:28,850
it into some other address.
So, we're able to remap addresses.

34
00:02:28,850 --> 00:02:32,115
Now, you might say,
Why do we want to do that?

35
00:02:32,115 --> 00:02:34,865
Well,
By doing that, we can have more flexible

36
00:02:34,865 --> 00:02:38,012
memory layouts and prevent things like
fragmentation.

37
00:02:38,012 --> 00:02:42,466
So, fragmentation, we'll talk about that
more later in today's lecture.

38
00:02:42,466 --> 00:02:47,336
But fragmentation basically is the problem
that you have lots of little pieces of

39
00:02:47,336 --> 00:02:51,315
data or code that get loaded.
And then some of them completes or go

40
00:02:51,315 --> 00:02:53,928
away.
You're going to end up with holes in your

41
00:02:53,928 --> 00:02:57,194
memory space.
And it's very hard to reclaim that unless

42
00:02:57,194 --> 00:02:59,807
you try to compress or re-layout the
memory.

43
00:02:59,807 --> 00:03:04,440
And lots of program models don't allow you
to go and recompress the memory.

44
00:03:04,440 --> 00:03:13,283
This is familiar if you've ever taken a, a
basic data structures course, where you

45
00:03:13,283 --> 00:03:16,133
had to go deal with managing something
like a heap.

46
00:03:16,133 --> 00:03:20,938
In a heap, you have pretty common to, it's
pretty common to allocate different sized

47
00:03:20,938 --> 00:03:25,576
objects on your heap, and then you free up
those different sized objects, and if you

48
00:03:25,576 --> 00:03:30,102
happen to free them in a bad order, you
end up with little chunks of memory that

49
00:03:30,102 --> 00:03:32,616
are really hard to go use for something
else.

50
00:03:32,616 --> 00:03:36,639
Especially if you want to go allocate
something very large, you might have

51
00:03:36,639 --> 00:03:39,880
enough memory in your system, but it's
just not contiguous.

52
00:03:39,880 --> 00:03:44,650
So, what approached to this is to have
things like garbage collectors which is

53
00:03:44,650 --> 00:03:48,427
what Java and a lot of the managed
programming languages do.

54
00:03:48,427 --> 00:03:52,801
But something like C or C+++ does not a
notion of garbage collectors.

55
00:03:52,801 --> 00:03:58,433
So, we're going to look at more not from a
heap perspective but from a perspective of

56
00:03:58,433 --> 00:04:02,627
the entire memory system.
So, sort of one level out from a heap.

57
00:04:02,627 --> 00:04:07,018
So, interprogram fragmentation and
interprogram garbage collection.

58
00:04:07,018 --> 00:04:12,093
The second important function of our
memory management here is we want to

59
00:04:12,093 --> 00:04:17,101
restrict access or protect access to
memory and allow only users who are

60
00:04:17,101 --> 00:04:22,588
supposed to be able to touch a certain
piece of memory to be able to touch that

61
00:04:22,588 --> 00:04:26,361
certain piece of memory.
And this is important if, for instance,

62
00:04:26,361 --> 00:04:30,340
you have one system which has someone's
bank records on it.

63
00:04:30,340 --> 00:04:35,664
And on that same system, someone else can
log in, they can telnet or SHS into it or

64
00:04:35,664 --> 00:04:39,755
remotely log into it.
And you don't want one user to be able to

65
00:04:39,755 --> 00:04:44,884
go read some other user's bank records
that just happen to be laying in memory.

66
00:04:44,884 --> 00:04:49,560
So, we need some way to protect that and
memory protection gets us there.

67
00:04:49,560 --> 00:04:55,079
It allows us to have different users using
the same system, different processes using

68
00:04:55,079 --> 00:05:00,663
the same system, and we can restrict the
access to different locations in memory or

69
00:05:00,663 --> 00:05:04,040
protect the access to different locations
in memory.

70
00:05:04,040 --> 00:05:09,137
Finally, memory management.
One of the important sort of points in

71
00:05:09,137 --> 00:05:15,251
memory management is that you can actually
think about having more memory than your

72
00:05:15,251 --> 00:05:19,062
machine has memory.
Now, you might say, that doesn't make any

73
00:05:19,062 --> 00:05:21,580
sense.
No, it doesn't make any sense.

74
00:05:21,580 --> 00:05:27,811
But if you have a flexible enough hardware
system, you can think about using other

75
00:05:27,811 --> 00:05:32,472
things to look like memory.
So, for instance, if you have a hard drive

76
00:05:32,472 --> 00:05:37,475
in your computer, you can use that hard
drive which is very, very large to

77
00:05:37,475 --> 00:05:43,164
effectively increase your memory size by
taking the data which is laying in memory

78
00:05:43,164 --> 00:05:47,687
and put it onto the disk.
And sometime later in the future, take it

79
00:05:47,687 --> 00:05:54,314
off the disk, and put it back into memory
and trick the user into thinking they have

80
00:05:54,314 --> 00:06:00,174
a larger memory space, and this is virtual
memory so it allows us to have transparent

81
00:06:00,174 --> 00:06:03,829
extension of the memory space using
something slower.

82
00:06:03,829 --> 00:06:09,482
I mean, could be disk, it could be in the
older days some drum that spins where you

83
00:06:09,482 --> 00:06:13,136
sort of store things on the drum you could
even, I could even, nowadays, you can even

84
00:06:13,136 --> 00:06:17,342
swap on flash.
If you ever go look in or something like

85
00:06:17,342 --> 00:06:23,335
that, this is called your swap partition.
Sometimes called a backing store, a couple

86
00:06:23,335 --> 00:06:29,726
different names it goes by, but it's a
virtual manage virtual memory storage

87
00:06:29,726 --> 00:06:31,830
location.
Nowadays,

88
00:06:31,830 --> 00:06:36,173
Most systems provide us with some sort of
page based system, which we'll be talking

89
00:06:36,173 --> 00:06:38,632
about.
But there, these ideas are all orthogonal,

90
00:06:38,632 --> 00:06:42,766
and you can have different mechanism is to
solve all of them in different ways.

91
00:06:42,766 --> 00:06:46,220
And we'll be talking about some of the
historical aspects of that.

92
00:06:46,620 --> 00:06:49,480
Okay, so, let's start off in the
beginning.

93
00:06:49,480 --> 00:06:53,736
Well, in the beginning, we didn't have
fancy memory management.

94
00:06:53,736 --> 00:06:57,993
Instead, we had addresses.
You want to go access some piece of

95
00:06:57,993 --> 00:07:03,365
memory, you come up with an address.
And that directly indexes into our memory,

96
00:07:03,365 --> 00:07:08,361
and you get back the data.
Well, that's okay if you're running one

97
00:07:08,361 --> 00:07:13,034
program at a time.
So if you go back and look at EDSAC, which

98
00:07:13,034 --> 00:07:17,283
is one of the original, probably the
second computer, I think.

99
00:07:17,283 --> 00:07:22,240
Maybe the first computer.
Oh, the first sort of, modernish looking

100
00:07:22,240 --> 00:07:25,568
computer.
It only had physical memory addresses.

101
00:07:25,568 --> 00:07:30,100
So, what this really meant is only one
program can run at a time.

102
00:07:30,520 --> 00:07:36,847
And, it had all of memory.
And the addresses that were used,

103
00:07:36,847 --> 00:07:43,512
basically didn't move around because there
was only one program running and it owned

104
00:07:43,512 --> 00:07:47,120
everything.
An IO could directly touch memory.

105
00:07:47,590 --> 00:07:51,119
Main processor could directly touch
memory.

106
00:07:51,119 --> 00:07:56,629
And life was simple and okay.
But, unfortunately you couldn't really run

107
00:07:56,629 --> 00:08:00,404
multiple programs, you couldn't protect
multiple programs.

108
00:08:00,404 --> 00:08:05,902
You could definitely not take memory off
of disk and put it into memory, cuz you

109
00:08:05,902 --> 00:08:11,201
had no way to sort of remap things.
So, it did not fulfill those sort of three

110
00:08:11,201 --> 00:08:16,433
requirements that we were talking about.
We didn't, it didn't do any translation.

111
00:08:16,433 --> 00:08:21,930
It didn't do any ability to protect, and
it didn't have any notion of virtual

112
00:08:21,930 --> 00:08:25,242
memory.
One thing that did happen is that users

113
00:08:25,242 --> 00:08:29,795
still wanted to be able to write
sub-routines that were location

114
00:08:29,795 --> 00:08:33,317
independent.
So, what I mean by that is you write a

115
00:08:33,317 --> 00:08:39,375
subroutine, and this was back in the days
when people were writing these subroutines

116
00:08:39,375 --> 00:08:44,223
in machine code or assembly code,
And you still want to do the regular, one

117
00:08:44,223 --> 00:08:49,657
subroutine and use it and call it, and use
it in different portions of your programs.

118
00:08:49,657 --> 00:08:54,897
So, one of the trick that people sort of
thought about is, how can you still have

119
00:08:54,897 --> 00:09:00,073
location independence even when you only
have one physical address space, so you

120
00:09:00,073 --> 00:09:03,696
can't remap things, there's no translation
going on here.

121
00:09:03,696 --> 00:09:07,357
Well,
In fact, you can actually use the linker

122
00:09:07,357 --> 00:09:14,200
or the loader to be able to go do this.
So, actually, quick show of hands here who

123
00:09:14,200 --> 00:09:18,924
knows what a loader is?
Who knows what a linker is?

124
00:09:18,924 --> 00:09:25,220
Okay, so we've got a little bit of
coverage with linker. linker,

125
00:09:25,600 --> 00:09:30,179
What it does is it takes multiple
different compilation objects or

126
00:09:30,179 --> 00:09:34,211
compilation units.
So if you take a computer program that's

127
00:09:34,211 --> 00:09:38,996
made out of a bunch of little files, a
bunch of different source files,

128
00:09:38,996 --> 00:09:44,366
You compile up each of those separately.
And when you link it, you take them and

129
00:09:44,366 --> 00:09:48,759
you put them all together into one
program, and you resolve all the

130
00:09:48,759 --> 00:09:53,490
addresses, all the jumps, and the data
accesses across that one program.

131
00:09:53,490 --> 00:09:56,194
So, that's linking.
That's static linking.

132
00:09:56,194 --> 00:09:59,573
Now, dynamic linking.
You guys might have seen, DLLs.

133
00:09:59,573 --> 00:10:04,249
Did I make dynamically linkable loadable
objects.

134
00:10:04,249 --> 00:10:10,697
So, what happens with DLLs is, you'll
actually do that linking step of resolving

135
00:10:10,697 --> 00:10:15,204
the addresses at runtime. So, you could
actually do either,

136
00:10:15,204 --> 00:10:18,855
You can either do it dynamically or
statically.

137
00:10:18,855 --> 00:10:25,149
And the loader is the piece of code which
actually takes a binary off a disc, and

138
00:10:25,149 --> 00:10:31,006
puts it into memory somewhere.
And typically, the loader will go and do a

139
00:10:31,006 --> 00:10:35,624
last level linking step at the end.
So, on a modern day Linux system, your

140
00:10:35,624 --> 00:10:37,594
linker,
Or excuse me, your loader,

141
00:10:37,594 --> 00:10:42,581
When you type a when you go to execute a
program and you type I don't know,

142
00:10:42,581 --> 00:10:45,968
You run LS or something like that on your
Linux system.

143
00:10:45,968 --> 00:10:51,079
First thing it does is it goes and finds
the LS bits on the disk and it takes that

144
00:10:51,079 --> 00:10:53,750
and copies it up into RAM,
Somewhere.

145
00:10:53,750 --> 00:10:57,283
So, you could do this on this absolute
addressing system.

146
00:10:57,283 --> 00:11:02,330
And then what it does is it goes and it
figures out all of the dynamic vibrates

147
00:11:02,330 --> 00:11:05,852
that are needed.
And it goes and takes those off disk and

148
00:11:05,852 --> 00:11:10,292
puts them into RAM somewhere.
And then, it's going to, last step here is

149
00:11:10,292 --> 00:11:15,352
the original program had pointers to
address that didn't actually exist yet.

150
00:11:15,352 --> 00:11:20,612
Cuz it didn't know where the respective
loaders, respective libraries are going to

151
00:11:20,612 --> 00:11:23,541
be loaded.
So, it has to patch the program up.

152
00:11:23,541 --> 00:11:29,067
It has to rewrite addresses to make sure
that the newly load program points up the

153
00:11:29,067 --> 00:11:33,061
correct location.
So, that's a runtime linker doing its job.

154
00:11:33,061 --> 00:11:38,387
The static linker can do that same sort of
thing but at a compile time could be an

155
00:11:38,387 --> 00:11:41,450
assembly time or linking time in your
program.

156
00:11:41,450 --> 00:11:43,927
Okay.
So, that's absolute addresses and if you

157
00:11:43,927 --> 00:11:48,002
have the physical hardware for an absolute
address machine, it's simple.

158
00:11:48,002 --> 00:11:51,085
It's kind of what we have been looking at,
at this point.

159
00:11:51,085 --> 00:11:55,545
You have your program counter, you stick
it in your cache, it gets, the instruction

160
00:11:55,545 --> 00:11:59,289
cache gets an instruction out.
You take your address if you're doing

161
00:11:59,289 --> 00:12:03,363
memory access, you stick it into your data
cache, and it gets some data out.

162
00:12:03,363 --> 00:12:07,713
If you take misses everything to physical
address, it goes into the memory control

163
00:12:07,713 --> 00:12:10,362
and goes out to DRAM.
Seems, seems simple.

164
00:12:10,362 --> 00:12:14,290
It is.
But, like I said, it doesn't solve all the

165
00:12:14,290 --> 00:12:19,789
problems we want to solve.
Okay, so now, let's start talking about

166
00:12:19,789 --> 00:12:25,917
stuff that's a little bit more, more
complex if we actually want to do address

167
00:12:25,917 --> 00:12:30,717
translation.
So, address translation, actually before

168
00:12:30,717 --> 00:12:36,287
we leave this, we're going to call
addresses that touch main memory, physical

169
00:12:36,287 --> 00:12:41,369
addresses.
And we're also going to talk about this

170
00:12:41,369 --> 00:12:46,003
notion of a virtual address.
A virtual address is actually just an

171
00:12:46,003 --> 00:12:51,551
address that the main processor uses which
might be translated somehow into an

172
00:12:51,551 --> 00:12:54,080
address which is out in main memory.