Skip to main content
Loading Explore guides…
Virtual Memory Management · Acedra
Home
Explore
Computer Science
Virtual Memory Management
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
512 segments
Copy
Hide video
0:12
OK, that's the recording started. Just a reminder that all the lectures are on. The YouTube channel.
0:24
Remember, was a tab for that.
0:27
And teams.
0:33
And there's also a link in the in notes. I haven't updated only to put the 2022. No, there's yeah. So there's the playlist for my Shields, like cheers.
0:47
If you subscribe.
0:50
To all the YouTube things and you'll get updates.
0:57
Plus, you boost my self-esteem, just like rebet to know that somebody subscribed to my channel.
1:05
What was it? Smash that like button smash that subscribe button and come back again and again.
1:15
Alright.
1:17
So as you saw on the syllabus, we're up to this week, which means we're talking about virtual memory management for moving on from.
1:28
I think 2, but we're talking about last week with memory management strategies that you all picked up frosting around and didn't need to go back and check again because it wasn't that complicated, was it?
1:41
That's impressive that you can just do one every corner. That's that's that's skill. You could be James Bond in the future.
1:53
I'm a wheel that memory management boys tricky, so I hope you have gone to look at it because this is The thing is an extension of what we're talking about last week. Can you remember last week we were talking about how we could make.
2:07
The idea that we bring stuff in. Uh from backing storage and figured out how we were going to organize it. And we went for all. Pulling everything and chucking it and in the post hole phoned to.
2:24
Debating memory and processes up into pages and dreams and swapping those in.
2:31
Well, today we're going to kind of continue that thought in that.
2:38
We have now got the idea that.
2:42
We've got our.
2:46
We have no got in place. A system.
2:52
We're stuff is built in as we need it.
2:56
That.
2:59
We can bring in any parts of a process. That they can be anywhere in memory.
3:07
So the logical next step is to think, well, if we can already do that. Why are we limited to the amount of memory that we have?
3:18
Can't we just pretend that we have unlimited memory?
3:23
And if we have unlimited memory, we could load an unlimited processes and run unlimited programs.
3:33
The only twist being that when we actually use them when we actually bring them to the foreground and use them, they would have to be brought and grown memory like drew backing storage into memory. That's what we want to talk about today. The idea that we could have virtual memory.
3:54
The idea that we could have.
3:58
As much space as we want, and only bring in what we need.
4:03
Eyes and queen use it because remember, we have to have stuff in memory. To we can't run it from backing. Storage has to be a memory.
4:13
Look between always use the whole program.
4:16
OK, PowerPoint running. You're watching that PowerPoint right now.
4:21
Think of how many options there are in PowerPoint.
4:26
And if you don't remember how many options there are in PowerPoint. Let me show you.
4:36
Look at all these menus at the top.
4:40
With all these different functions in the.
4:45
We'll go with things that you can do with PowerPoint.
4:53
And of course, a lot of these subfunctions, a lot of these functions. You have subfunctions that once you go into them, you can do other things.
5:03
Are going here and click on this.
5:08
I can't do it because I'm running it.
5:18
But we're not using PowerPoint to do any of those functions right now.
5:23
What we doing?
5:27
You're doing a slide show.
5:30
To appear on the screen, none of those functions, none of that code that they've gone to the trouble of writing. Is actually being used.
5:39
So the question becomes.
5:42
Why would you have it in memory?
5:45
Probably we have the code that does a spell check. Why would we have the code that does that allows you to use pens on a slide while to have the code that runs the help? Why would to have any of that stuff when all you're doing? It's showing a screen.
6:02
So maybe actually.
6:05
We can pertain to have the full program in this massive virtual memory.
6:11
But Anna real memory, we just have to be bets that you're in. The pages that are running.
6:19
And when you think about it, that tends to be a lot of how you use programs. So here we are using the bit of PowerPoint that shows a slide.
6:29
And I'll stay in that we bit of code can round that we better code again and again.
6:34
If you're in what you're mostly in the type, stuff in bit of code. Type stuff and and update the screen.
6:44
95% of your time, that's what you're doing.
6:48
So maybe just have the type stuff in and update the screen part of code? Part of the code in there.
6:55
And we can extend that out to all of the other systems that we have.
7:01
So that we can say, right?
7:05
Let's have. Just the bet that we need.
7:11
And only partially load the program.
7:16
It means we can have programs that are as big as we need them to be.
7:21
Because they'll have it if there's no limit to virtual memory. Now I'm going to keep saying that it's not true. Of course, there's always going to be limits, cause even virtual memory has to be stored somewhere.
7:32
If you look on your Windows system, you get ahead and fail. With your virtual memory on it and it's basically just a big fail on their desk so that as I love it. But.
7:42
What's pertained, we'll get as much space as we need.
7:52
There's a question the chat about.
7:55
I didn't in memory and I'll talk about it when we get to it, cause I've already talk about adding in memory later.
8:03
So we'll talk about it in real terms and talking about it and really just terms.
8:10
OK, so if we're deciding we'll only need to use the bits that we need, we can have more things running, more running at the same time.
8:19
Which means that we can increase the CPU utilization. We talked about that a few weeks ago in terms of one of the. Criteria that we might want to use as being a good system.
8:35
And of course, we speed things up because if we don't have to load in the whole.
8:41
5 gigabytes of a program.
8:44
From help desk we just need to load in one page that will speed things up getting started.
8:51
So that's what we want to talk about today. We're going to call it virtual memory. The idea that we've got a logical memory space.
9:00
As distinct from the amount of physical memory that we actually have in the computer.
9:06
And we're gonna do all those things. We're gonna allow only parts to come in. We're going to allow.
9:14
Processes to share addresses because we talked about that in terms of DL in terms of shared code as shared spell checker, whatever happens to be.
9:29
So if you're gonna virtual memory, we need to have a virtual address space. In other words, we need to think about.
9:36
How memory is in our virtual memory?
9:41
And then essence, we're going to think about it in the same way as we would do physical memory.
9:46
The virtual address space will start at 0. Until the end, whatever that happens to be.
9:54
Remember, we've already got over.
9:56
Physical memories split up.
9:59
And the streams. So what we are going to do is put up our virtual memory and to frames as well.
10:06
So we're gonna need to have something else we're gonna need to have. A map and there.
10:13
And the map is simply. Here's our virtual memory split up into pages.
10:19
Which of these pages is actually in real memory?
10:26
And which of these pages is in?
10:29
Gotcha memory which is.
10:32
Shown here as being on a help desk.
10:36
How does?
10:37
SSD. Whatever, doesn't matter. Point has. It's not main memory. So we've got an extra main room up and here that's going between our virtual memory and our physical memory.
10:51
No, a few things that we need to take care of when we're doing this. And.
10:57
And I've said before about.
11:00
You're grams meeting some local storage to run, and we've talked about stacks. The goal from.
11:08
The top down.
11:11
And keep going from the bottom up.
11:15
Before we continue with that thought, I've got a question about. Virtual memory and swap space.
11:23
So his virtual memory swap space? Or is that a separate thing?
11:29
The swap space is how you enable your child memory. So we were looking at this slide here. All of these things here are announced small space.
11:43
So when we load our. Program into virtual memory. Some of it goes into real memory and some of it goes into.
11:51
Virtual memory, which is sometimes known as swap space.
11:56
So it's an enable.
12:04
OK, so first starting this local storage for all of our programs, remember what code and get data, but we'll get transient data. So if you're typing stuff into word.
12:16
That data is going to increase as you go along.
12:21
So what we do is we start them at different ends to leave all the space in the middle. To see you. OK, we will. Excuse me. Start that at a particular page.
12:36
Or to be precise, because it's in physical memory, free.
12:41
And Isaac Gates, bigger will take extra space for it as we need it. Fazio, what document gets bigger will take extra frames to store the data.
12:56
We can also manage it so that we can have shared pages, so these shared libraries can also be in there somewhere.
13:08
OK, so these are the sorts of things that we want to have. So let's think about how we might go about making that happen in the 1st way that we can do is something called demand paging. So let's think about what happens when we run a process.
13:26
Traditionally, what we've said is the process is stored on a disk. It needs to run from memory. Later is go to the desk, will load in the whole process into memory, and let's get started.
13:40
And that's what you've got here.
13:43
Program loads in here.
13:46
You know that program here.
13:49
So we're bringing in the whole process.
13:53
But we don't use the whole process. Like I said, we don't use all those functions and PowerPoint. We don't use the spell check. Why are we bringing the spell check page?
14:04
And to memory.
14:06
Why do we need it there?
14:09
And the answer, of course, is we don't.
14:19
So why would we bring that in at the start Lees instead think about bringing things in only as them needed only on demand when they're asked for.
14:33
That brings in some problems of its own. So with load in the first part of the program.
14:41
And then that first part of the program will start running and it may reference other parts of the program.
14:49
They may or may not be a member.
14:53
So.
14:57
If it's not in memory, we would need to go out and bring it in. We also need to remember that the meat then error happening because programs can meet.
15:06
And. Make mistakes and they can ask for bits of memory that they shouldn't even have access to.
15:13
So we need to the airport, but we also need to not in memory part.
15:23
Doing it that way is called lazy swapping. We basically don't load anything until absolutely positively is required.
15:36
We also need to put in some functionality there. The operating system needs to have something that says, OK, it's time to go and get a page and bring it in and that.
15:45
Has given this stunningly original name of Apache.
15:50
So how does the pager work well.
15:56
We need to think about what we're doing. We need to think about what pages we want.
16:02
So we've got a list of pages that are in the process. Some of them are in memory. They have valid pages, some of them aren't in memory, they are invalid. And remember, we saw that last week. Where we had the frame.
16:17
We have the page table with the frame number and whether it was valid or invalid.
16:23
So we can continue that thought now with the pedia.
16:29
If they're in memory, we're fine.
16:33
They're not many resident. We need to figure that out. So we use our invalid bit to say OK.
16:42
And valid not in memory. We need to go and do something here. Specifically, we need to go and get this page and bring it in.
16:54
So here's an example. Here's the logical memory now.
17:01
Rather annoyingly.
17:03
The logical memory in this example seems to be smaller than the physical memory.
17:09
So what I'm seeing at the moment is the logical memory is just a part of what it has now been shown at all.
17:15
Regardless of that, you can see that we have a page table.
17:21
It says frame 0.
17:25
Term 0.
17:27
Which is E.
17:30
Is in physical memory. Application 4 there's eight.
17:37
Good 266 is GG. Is that?
17:53
Them to see.
17:56
See is at 6.
18:00
Five is F and that's that night. So those they are valid.
18:07
The other ones are involved. Now look at what we've got and that's relevant to. The question about the swap space.
18:19
Because our process is completely in backing storage here BCDEFGH the it's all in there. The parts of it are in physical memory.
18:31
So we store all in our swap space.
18:37
And that's all that and physical memory.
18:43
The ones are in physical memory are put the valid bit set the ones that aren't are invalid.
18:51
So if we try and load in.
18:56
B.
19:02
B is invalid. It's still outside memory.
19:07
Technical term for that is a page fault.
19:13
Remember has to be in memory to run if it's not in memory, that's a page fault. Need to bring it into memory so that we can run it so. We make sure that it's not an invalid reference. First of all, and if it's not, we just say, OK, it's not in memory, we need to do a few things. We need to find a frame that's free, in other words.
19:35
What doesn't have anything in it 13467 year?
19:42
And then we need to say, OK, we won't be, we need to go and swap that. And two memory and update our Page 3. To see their page table to see that that frame is now is valid.
19:55
We're just going to drop it in from desk.
19:59
And that happens like this.
20:03
So you've got your. Pearl says running here.
20:07
It asks for a piece of memory.
20:13
That goes to the page table.
20:16
The peace table says Nope, that's invalid. I don't have that page in memory.
20:23
That's trapped. That's the page fault. The operating system says. OK, well, I know where that is. Let me go and ask. The helpdesk for that piece of memory.
20:35
Would it back into a free frame and physical memory?
20:40
Update our page table to say yes, we now know where it is and it's valid.
20:45
And we'll get this one here. That says restart construction. So poopak. And redo the instruction and the reason for that is.
20:59
We don't want to hang a boat.
21:03
We don't want the CPU to be hanging about. Well, it notices it doesn't have a bit of memory and the operating system takes over and goes to the hard disk and loads up the hard disk and brings that into memory and update speed. The CPUs get better things to be doing so in the same way as we go through our.
21:22
Member of purses stuff where it went from ready to running to waiting.
21:27
In essence, this process will go into the week Q.
21:31
Until it's loaded.
21:33
And then once it's loaded, it can go back into the.
21:37
Ridicule and restart again, so the process here is similar to when a process gets swapped out. We stores state wait until it's all ready to go. Because this is just another type of Israel. And then once it has, it goes back into the ready queue ready to restart that instruction.
21:59
Is that OK?
22:01
We'll move on.
22:05
Yeah, couple of nods.
22:08
Couple of thumbs up OK.
22:15
So let's think about how this is going to work in practice.
22:20
So those.
22:24
You've got. As with all these things, it's up to you how you implement this stuff, so at one end you could say that let's not bring in anything. We don't know what we're going to have. Let's not drink any pages. And stead, let's just start.
22:42
Go to the first post instruction and if the first instruction isn't in there then it will create a fault and it will go and bring the page in.
22:53
And that will happen with every process when it's first access that's called pure demand paging. Wait until it starts and then go get.
23:04
However, those of you who think back to your little man computer. It wasn't just a bit annoying you and doing a assembler. Used to think about what's happening inside the computer. Now think about how some of you wrote it. Not everybody, but some of you.
23:28
Some of you. Said.
23:35
Hang on a second, just to bring it up.
23:52
Cook.
23:54
Some of you.
23:56
Hide.
23:58
Cool.
23:59
Remember the code. Just shows his numbers and the mailboxes.
24:05
But you also decided that you're gonna store your inputs somewhere. This program does the same thing it's stores. The input.
24:16
And Manuel location night to night.
24:21
So the instruction is up here.
24:26
The data is here.
24:30
That made them more than one page.
24:33
So that instruction.
24:35
Could actually. Need 2 pages.
24:41
One for the data. One for the instruction.
24:49
And if you extend that out, you can easily imagine how you might need more than one page.
24:55
If you had a simple ad.
25:00
With two.
25:03
Values that were in different parts of memory. You might need 3 pages, one for the instruction and one for each. Piece of data.
25:13
So you may actually have multiple pages that you require, so you might have multiple page fault.
25:22
No, we're lucky in that it doesn't happen a lot because I thing it that we call locality of reference. And again, you've seen it when you did your little man computer. Code stains taste the stain its own be loops and its own be block.
25:39
So it might move about for a while, so you maybe had a block that got all your inputs. And then we block that did all the sorting.
25:48
But the code tended to stay within that. That's called locality of reference, so it's not quite as bad as that, but it can happen.
25:59
So maybe what we need to do is add in some hardware support to speed all this up.
26:04
It's going to take time and that's gonna slow us down.
26:17
And if those blocks are even more complicated.
26:23
We may have issues.
26:25
Because remember what we've got to do.
26:29
And the worst case we stop.
26:32
Save the process state.
26:36
Run an interrupt because it was a page fault.
26:39
Make sure that the page is actually legal.
26:43
Check whether it's on the disk.
26:46
Read it from the desk. So do the I/O.
26:50
When the eye was done.
26:53
Move it back into ready and then. Run your process again by restoring the registers. Making getting it and.
27:04
Correct memory location that it's in memory.
27:08
And then resuming.
27:12
There's a lot of things that you have to do here.
27:16
Some of them are Fust. You know the fast. We've done them all the time.
27:23
Saving their ages, those in the process state, but we do that all the time when we're moving around the processes. But going out to ion and bringing in some memory that's gonna be slow.
27:34
O the more page folks, we have the slower the system is going to be making start to work that out.
27:46
She. Here is dance with probability.
27:52
If we don't have any page faults.
27:55
Then the effect of access time is just the access team from memory.
28:00
If we know that we're going to have a page fault, then every access time is the amount of time to access memory plus the time to go and get the page. From dusk.
28:12
Bring it in and also quite possibly swapping a page out and make the two iOS here, because if you're we've been looking at the case where.
28:26
You have a fever. What if that's filled up?
28:30
You might need to swap something out before you can swap something else, and so you might have two input outputs to the.
28:41
So you're access time as your memory access plus the page fault +2 swaps.
28:51
And as I see the the stopping and starting would do that all the time. It doesn't take a lot of time but. Reading the page, saving the page that takes lots and lots of time.
29:01
And you guys have come across this before? You guys have come across this when you have run too many programs on your system.
29:10
You go to move from one to the other.
29:13
And this is what's happening. Hosting realizes that your physical memories full.
29:20
You want something that's not in physical memory it Aussies. It takes something out of physical memory, loads what you need. Runs that. And then your system goes oh, but now we're back to this other process. Which you have just swapped out of physical memory, so it pauses, takes out a page. Brings in another page, runs that and all of a sudden very quickly your system just slows down and down and down and down until what it's doing is spending all its time swapping
29:50
stuff in and out and very little time actually doing anything.
29:55
There's actually a term for that. It's called thrashing, where you spend all your time swapping stuff in and out of memory rather than doing things.
30:04
So whenever not gonna have page faults but we want to make them as few as possible.
30:13
Because we can very quickly.
30:17
Slow down now system.
30:21
You've got an example here. After access time, is nanoseconds in the page fault. Is in. Milliseconds.
30:33
Then working all out your system can slow down by a factor of 40.
30:40
Wildly faster CPUs.
30:45
I mean that the factors gone not because how this speeds haven't increased that much. But your memory access taking for all the house.
30:53
So the slowdown is actually more noticeable.
30:57
So what we need to do is make sure that we have as few page faults as we possibly can, and we can turn this equation around to say, well, if we can work out how much the slowdown is. We can see if we want to have a slowdown of no more than.
31:16
And here we see less than 10% we can work that out that we only can afford to have one page fault. And every 400,000 memory accesses.
31:30
OK.
31:37
Don't worry if you don't follow the sums. Just remember that there is an effective access time and it's a boot. The probability of whether you have a pitch bolt.
31:49
So how do we make this faster?
31:52
How do we optimize this?
31:57
Well.
32:00
Maybe we can have.
32:03
A swap speaks, which goes back to three sales point.
32:07
Instead of just having a straight fail system.
32:13
Let's have some swap space.
32:18
In other words, dedicated space that's for our swap file for our virtual memory. Rather than just a standard fail system.
32:28
Access.
32:30
Because of allocated it because it's contiguous in memory. One huge chunk of memory. We can get faster access.
32:40
We can also use this locality thing.
32:44
So we'll say that we, Steve. Round about the same place and a program.
32:50
Some quite often what happens is. If you want Page 1.
32:55
Chances are you'll get on to page 2 and then Page 3 and page 4 cause you run through stuff.
33:02
Maybe we could optimize it by not just getting page one, but getting pages 2-3 and four.
33:08
Because we're going to, we're going to a very slow device anyway. Let's have a whole chunk of memory. And bring those in on the off chance.
33:18
Which means it can forget there that already there.
33:30
We still need to rate that so when we start the process which goes from the part of disk, we are.
33:37
The program stored we need to save it into the swap space, but that's a one off.
33:49
We could.
33:53
But we should.
33:57
This said about.
34:02
This part as well because you'll see if we don't have any space, we need to swap stuff out. So we need to. Take the page, swap it back out to our.
34:17
White space.
34:21
So we need to free up some space, take that in, and take it back.
34:28
What if we didn't have to? Like we already have it on the desk.
34:34
Do we need to actually rate it back out? And the answer is, as with most of these things, it depends.
34:41
What does it depend on?
34:45
And the thoughts would it make depend on?
34:52
We're good. He's asked us a question or no. Which?
34:57
Paul and I can see you're unmuted. You're not coming through. I I was gonna say I just did you say there? Oh no, he's asked. The question is it today way when you you're using a program like you'll send me a PowerPoint, the part you're actually using?
35:12
I am well. That's true for bringing in the missing page. What is? Like what?
35:17
The what about? Saving. So if we don't have any free frames, we need to swap out one of the frames that we have in memory back into swap space before we can bring in a new one. Do we always have to swap it back out? And if not, why not?
35:36
No bugs. You can just save it. You can save it directly to the hard drive outside of swap space. No, that's not what I mean. And you wouldn't do that either because the hard drive slower and that would just add in an extra layer of complication.
35:53
Are there any teams where you wouldn't need to save it back?
35:57
Well, why would you need to save it back?
36:06
You only need to save it if it's changed.
36:10
If it's data something that you've updated.
36:14
The code hasn't changed to. Why would you bother saving it back when you've already put it all into swap space and 1st place? So maybe we don't need to swap out.
36:25
Maybe we only need to do it? Umm.
36:30
If it's modified, if it's changed so we can keep a record of where pages have been changed.
36:38
The same ways have valid and invalid. We can see. Have we changed anything? Have we written to this part of memory? And if you haven't written to it, we can say oh fine, we can just kill that without even thinking about it. Nothings changed.
36:57
Umm.
36:59
What would be nice though, is if we could keep some food frames, you know, it's not always easy to do, particularly as load goes up when you have more processes running. But it would be nice if we had a pool of.
37:12
I'm going to mind.
37:15
If we had a pool of three frames so that we could bring in.
37:29
Member one of the things we should be doing is thinking about how we save the changes. So here we have process. With PCP's. In memory.
37:44
On their shield with another process.
37:47
Maybe it's the spell check stuff.
37:52
So the spell check code is here. True, says one runs a spell check, so those results. So there's some data needing to be stored and they are stored here.
38:04
Process two hasn't.
38:06
So we can get even more complicated. Process one is got a copy of page AC cause it's updated it process 2's, got the original page C because it hasn't changed anything yet.
38:17
So we're using the same spell check code.
38:20
But one of them has changed.
38:24
So it starts. There's an awful lot of work that the operating system has to do to keep track of these things, figure out what's changed, what hasn't, what needs to be updated and what doesn't.
38:37
Everyone happy with that? Before we move on?
38:43
Yeah. OK. Umm.
38:50
OK. We are roughly halfway through the slides that I have.
38:56
So I think that's and you've all concentrated for about 50 minutes. So I think that's probably a good thing to have a break.
39:06
Yeah. OK. We shall have a great then, and I will see you back here in 10 minutes.
39:18
OK.
49:36
OK. And we are back.
49:44
Anybody got any questions?
49:49
That's a cut to them. While we're taking our brick.
50:17
Yeah, I have to leave early to.
50:20
Well, the sun's going to dress up as a horrible lecturer for his Halloween party.
50:27
Assume that's going to be the question and.
50:30
OK, I'm not seeing any questions.
50:34
So we left it that we're talking about.
50:38
Moving stuff in and out of memory.
50:43
To get a feel free.
50:47
But what if we don't have any 3 frames? What if memories all been used up by all the processes?
50:57
And of course, there's a question there already. Memory has been used up. How did we decide to use up that memory? Did we split it up between the processes? Did we give it on demand? What was the choice?
51:16
I'm laughing. If you're not watching the chat, that's why I'm laughing.
51:22
It's actually quite impressive. I have to say there's a dinosaur doing a front flip into a boat and it's it's quite dress.
51:36
Of course, the.
51:39
I'm not seeing that the the costume isn't a stressed out whitrock. Instead, it's a dinosaur inspired by the operating system. That excellent phone? That's what I like to see. Engagement with the module.
51:57
OK so. How did we decide who was getting all the space in memory? And what are the point? Know that we're filled up the space. Who loses? How do we decide which pages come out?
52:17
We could find something that's not in use, but how do we know it's not in use? How do we how do we make that determination?
52:26
And.
52:28
Do we just swap it out? Do we replace the? To terminate the process. What's up?
52:35
What's the weather? Reasoning and of course for algorithm do we use? To to allow us to do that.
52:50
First thing we want to do is the one that I pointed out earlier. So. We want to.
52:57
Minimize our IO.
52:59
So we will introduce an extra bit of already got. And memory and not valid or invalid. So let's add in an extra way note to say.
53:12
Has this piece of memory changed?
53:15
We call it. Isn't memory duty.
53:20
And if the memory is doctor then we need to save it because we need to save that change.
53:25
I need to do that for swapping out of memory.
53:28
So that might be one of the things we use. Maybe doctor pages or things that we shouldn't be smoking out as much if we can. If we can.
53:36
Arrange it that way.
53:52
Regardless, we're going to have the.
53:55
The situation where we've got.
53:58
Multiple users.
54:00
Looking at the same logical at looking at different logical memory, as far as they're concerned, they're process is just running. It's only logical memory space.
54:09
But that has to fit into physical memory and you will get 2 processes.
54:14
That take 4 pages.
54:16
I have a physical memory is 8 pages but we can't use it all because the operating system has to go somewhere. That's where it's monitor thing means.
54:26
So we can't fit everything in. There's going to be.
54:30
Our fate.
54:33
Probably B&M.
54:35
Aunt and physical memory. They're in the swap space.
54:40
But the program counter for this process is in here, so we need to load in. Problem is.
54:52
Wasn't going to go.
54:55
This process is going through this process is good. Three who loses?
55:05
I hope before we do that, let's figure out how we're going to do it we. We need to get it from desk so we know that we want. PGM, we know that's there one disk and swap space.
55:19
If we have free space, that's easy, Chuck it into the free space. If not, we need to select a victim from all the places here.
55:30
No, we're going to have a victim. We're going to swap something out. We also need to check one of the. That piece of memory is Duffy. No, that's has it changed? If so, we need to swap it back out.
55:42
And then we need to bring the one that we want in this case AM into memory somewhere.
55:50
To here.
55:53
We're going to have it loaded.
55:57
In this speech.
56:00
And then we restart.
56:03
Of course, because memory was full, will get two page transfers.
56:08
Treating you and bringing back here. So I would please the effect of access time.
56:17
OK.
56:18
So we just swap out the victim page and bring back, ending your page 2 anyways and that's not good.
56:27
So we'll let's think about how we might approach our replacement.
56:33
Before we do that, remember the difference between a page. I'm afraid. Once physical memory ones for the process.
56:45
One of the things we have to think about is how many frames to give a particular process. Do you split up? Do we?
56:56
Just said everything gets the same. Do we give somethings more space than others? What's what's the algorithm that we're going to do?
57:04
And then we need to decide on a page replacement algorithm. Which ones are we going to swap out when we need to move things around?
57:15
So what we're gonna do is think about some different algorithms that we might use. In fact, algorithms that are being used. And operating systems may not know, but certainly in the past.
57:27
So let's.
57:31
Figure out what would happen using these algorithms. Now all we're going to do is have a string and this string here is just a list of numbers.
57:42
These are the pages that we want.
57:47
We want Page 7 followed by zero followed by 1 followed by two and so on.
57:56
And we can do a couple of things. We can model that based on the number of frames that we have, in other words, so much space we have in real memory.
58:05
And then once we've done that, we can figure it how many Peach folks.
58:13
It's going to generate another one. So many things. Do you have to swap it? So if we only had 1/3?
58:19
We would on page 7, then we won't page 0, so we have to swap out page 7.
58:26
And mould and page 0 because we've only got one trip and then have to swap out zero and more than one. Then we have to swap out one and load and two and so on.
58:38
So the number of page folks is the number of times this number changes. And we can start to model that based on the number of frames that they have and then we can see what happens with the number of page folks.
58:53
Versus the number of frames that we have now. Just as an aside.
58:58
One of the things you're always told us if you want to speed up your computer.
59:03
Add more real memory. And then he since This is why.
59:08
The more real memory you have, the larger the number of frames that you have. If you're page folks, you'll generate because you can get more things into memory at once.
59:18
And if you have fewer page folks, you'll speed things up because you reduce the eye or required.
59:24
So in general terms and that's why the best thing you can do to computer is I didn't want memory.
59:32
OK, so let's think of some algorithms and actually the algorithms are probably going to be familiar to you. From when the processes phosphine gonna look at his Boston forced out?
59:49
So here's a list.
59:52
Of pages. We will assume that we have 3 frames and we can start working our way through.
1:00:00
So we need 7. That's Moody then.
1:00:04
No problem, because we've got these three spaces and just going then we need zero. Then we need one and they'll just loaded up.
1:00:13
However, within need to. So our algorithm is Foster and foster frost one and was seven. So we swap out seven and two and two.
1:00:24
Next one we need to 0 or we don't have to do anything here Cause 0 already exists.
1:00:31
Next one is 3. Well, the last one that we put in was zero, so zero gets loaded out and see gets put in, which is a bit of a shame because the next one we need is 0. So we'll just swapped it out and we immediately have to swap it back into this space here. And you can go through that whole. String. Seeing we are.
1:00:54
The pages have been rooted on.
1:00:57
And they can then count out that there have been 15 page faults.
1:01:03
And of course it will. It depends which pages we have when you can work that through, and one of the things that you can do is try this string later on your own.
1:01:15
Was also some weird stuff that can happen.
1:01:18
With this algorithm, turns out that adding more memory, more frames. Can actually cause more page faults to pending on which pages you ask for.
1:01:29
That's called Bilitis are normally.
1:01:36
And you can see it here.
1:01:39
There's a point where we go from 3 to 4 frames, so we actually increase the page faults before they come down again.
1:01:51
So that's a fairly.
1:01:55
Straightforward one, which means it's easy to implement. So basic operating systems do use it.
1:02:05
But we would like to be a wee bit smarter about it. We might want to optimize it.
1:02:13
Maybe we could decide to swap out the one that won't be used for the longest time.
1:02:23
Except we're back into the same problem that we had when we suggested that we optimize our process replacement algorithm. How can we know what pages we're going to need in the future?
1:02:36
On the other hand, as would have the processes that gives us a yardstick. If this is the optimal algorithm.
1:02:42
Then we can work out how many page faults that we get and we can test them against our other algorithms. To see how well they perform against this optimal 1.
1:02:56
So I will next approach isn't about. What came in first? It's about what was used last.
1:03:09
Which is the least. Recently used page which one didn't we bother having? So it's in memory, but we're not been to in the longest time.
1:03:21
So same string Sam Foster Lee.
1:03:26
Singh Phosphora actually because our least recently used as the one that's been in there for longest at 7. Because we used seven them, we use zero them. We use one, so we swap out at least recently used which is 7 and that goes to two.
1:03:42
Next one is 0.
1:03:46
0 still there. Next one is 3. Now before we swapped out the zero because it was just a strict first and first out that here we're saying no, actually we'll we used zero. So let's not swap out zero. The least recently used of the ones we have in memory 201. We walk away by can go zero to, OK. There's at least listen least recently used as one. So that's what we'll swap out for three.
1:04:14
Next one is 0 same thing, it's there. Don't need to do anything. Next one is 4 and again we'll work our way back. Go for IT20 and three we'll review 0. We've used three, so at least recently used this two, so we swap out to for four.
1:04:31
And you can work your way through.
1:04:34
To the end of that string.
1:04:38
Works out that for this particular string in this number of frames we get 12 volts for better than first in first out, but not as good as our optimal 1.
1:04:49
Which hide 123456789, so it's pretty much in the middle. Lost in Foster had 15, I think. Optimal has nine. This hits in the middle with twin.
1:05:09
I do implement it. We just keep a note.
1:05:12
We've got a clock in the computer we.
1:05:16
Take a note of the last time we used it.
1:05:21
Smallest value.
1:05:23
As at least recently used.
1:05:28
It's gonna be a bit slow though, because we've got a list of names and we need to go through with this the slowest. Was this the slowest was this and it takes a while to go through things, so we could maybe.
1:05:40
Optimize that. Who's over? You know about programming rule to US stack.
1:05:45
So we could have a stack. Of page numbers.
1:05:50
With that, and a double linked list.
1:05:54
And the program is going and the non programmers are good.
1:05:58
Again, it doesn't matter. We can't organize it, so it making optimize it. Simply so that every time we had one and we can change the list and it's simply puts the least recently used at the front.
1:06:16
The other nice thing is a about least recently used. Is that as we add more frames, we do get a better performance. We don't know that and normally.
1:06:29
So here's a stack in the frame, so it's simply puts in.
1:06:36
The least recently used and Alto.
1:06:39
And again, you don't want know what stacks. Don't worry about it. It's just remember that somebody have optimizing.
1:06:49
As I've mentioned earlier, if we have to do this a lot.
1:06:54
We can stop thrashing the system and that's where we get to the point that was no free frames. We need pages. We load them in. But before we do that, we have to unload it. And then we find it. We need it again.
1:07:12
This thing here we unload it simply to find it. We have to load it in again.
1:07:18
So we can get to this point where we're spending more time.
1:07:24
Getting page faults and having to swap things that we are actually doing any work.
1:07:34
And a graph form.
1:07:36
It looks like this.
1:07:40
We're doing lots and lots of work, lots and lots of work and to all of a sudden we're spending so much time swapping. Could we do nothing? Other than swap.
1:07:55
As you say, this works because code tends to stay in one place.
1:08:01
We will do the best where we edit, then we'll do the bit where we build, then we'll do the bit where we add it again, then we'll do the spell check. So things move about that the stay in specific chunks, which is what that means when it says that the process migrates from 1 locality to another, it means that in the code we're doing this but and then we'll do that but and then we'll do that. But but within that it stays in the same small bit.
1:08:29
And that can be an issue where we're doing.
1:08:33
I know lots of people successes or processes that move within their own.
1:08:39
Could.
1:08:42
Quickly, so it might go to 1 bit, come back, go to another vet, come back. See you are. I don't know. See you are rendering an image.
1:08:52
You take out that. And then you go to the render.
1:08:56
Which goes to the colour check. Which goes to the shadowing and then you go back and do the next one and then works its way through the program, jumping about all over the place. That can cause the rating as well.
1:09:11
And what we really want to have. Is.
1:09:16
The locality, the pop and the program.
1:09:20
That you're going with an. To be.
1:09:24
Less than the memory size that you get.
1:09:29
That way you don't have to swap things out. So there's some size of the locality should be. Lace and the total memory size but greater than the total memory size we get thrashing cause it has to go in and out.
1:09:45
There's a diagram of locality and you can see what's happening here. This is an execution time and you can start seeing that things stay in the same place in terms of memory addresses.
1:09:57
They tend to be in the same place and then when the swap, they'll swap from one to the other. So here we were doing it and here and then it swaps here but will stop doing it here. OK, so things tend to stay in the same place.
1:10:13
What that gives us is the idea that.
1:10:17
Well, the bets that we need to run, that's our working set that's that's a bit of me. That's a set of memories that we are actually using in the role we need.
1:10:31
Maybe we can start to work out what that working set is.
1:10:37
Using all the processes that we have.
1:10:41
Look at the number of pages that were referenced. And those purchases and try and ensure. That we keep all those processes within our real working memory, if we can, we are fine.
1:10:55
Everything comes in, everything stays in memory and we just do what we do. We work our way through memory. But as soon as we have.
1:11:04
Too many processes or a process that. Is jumping about within its own working memory.
1:11:14
The working set. 4 pages becomes larger than the memory that we have.
1:11:21
And.
1:11:23
We stopped to get thrashed.
1:11:25
OK, that's simple terms. That's when we have just too much going on.
1:11:36
If we keep track of the working set, though, what we can see is, OK, well, we're having a problem here. Things are just slowing down and every time we try and do anything or swapping stuff in and out, maybe what we can do is.
1:11:52
Always something. Allow one of the purchases to finish whatever it's doing.
1:12:00
And then we can bring the other process back in and let do that.
1:12:05
So we can see if.
1:12:08
The number of frames that we need.
1:12:12
Is large on the amount of memory.
1:12:16
Suspended of yourself? Just say. We're not doing that just now.
1:12:22
And you can do that and. One of the ways that we've looked at before.
1:12:28
But the one that's least to go, the one that's get the highest priority, you know, whatever happens to be.
1:12:37
So we just suspend one so we can stop the thrashing. Until we can free up some more memory, hopefully by one of the other processes finishing off. Of course, we need to keep track of that working set.
1:12:51
Five. Saving it somewhere so that we can know which ones we are using.
1:13:00
That starts to get me a bit complicated, so maybe we can just say, well, let's forget that rather than keep in track, let's just say if the number of page faults is bigger than N.
1:13:13
Let's pause stuff.
1:13:16
In other words, we can set an acceptable page fault frequency.
1:13:26
If it's too much, we just don't take on anymore work. We stop processes being created already or as others, or do both.
1:13:38
And what we tend to find when we analyze these things that there's a direct relationship here.
1:13:44
The direct. Relationship between the working set and the page fault.
1:13:50
Not surprisingly.
1:13:52
Eyes were doing more work. Eyes were loading in more the page. Folks go up and then the processes might finish.
1:14:00
And the page folks go down again and it runs along. We'll start to do more work.
1:14:06
More page folks and tell whatever we were doing the finishes and it trundles down again. And that's exactly what you've seen when you've been working on your own machines. You start up stuff.
1:14:19
It can slow down. Do you think? Oh no. Stuff that's we're giving soldiers and you kill a program. Just nice. Stop that one just now into your system. Settles down again. Some operating systems decide well, I don't need you to kill it. I'm just going to pause it and I'm not going to do anything with it.
1:14:39
That becomes easier dependent on the type of system it is. You tend to work on systems that are very much user focused. And other words, it's just you and your computer, so it wants to give you a good response. Other systems might be focused on working on batch jobs or doing a workload, so it's easy to say, oh, no, this this was just too far. Let's pause this one until we're done.
1:15:08
As an example, here's what windows does. It uses demand paging with clustering, by which I mean.
1:15:16
That thing that was seen right at the start, if we want page one, we'll maybe we'll bring in pages 2-3 and four as well.
1:15:24
Because the chances are will need them because of this locality thing.
1:15:30
You have a minimum and maximum for the working set that you can have, so we guarantee your process that you can have a minimum set of pages.
1:15:40
Up to a certain. Maximum after that you don't get anymore.
1:15:47
And eyes memory. And the free memory falls that amount that you're allowed gets trimmed, gets smaller and smaller and smaller so that you can get some free memory.
1:16:04
And that is virtual memory management.
1:16:09
Questions.
1:16:15
Always happy it's over.
1:16:28
No, I'm not seeing any questions.
1:16:41
OK, I'm not seeing any questions, so let me stop the recording.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat