Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[MUSIC PLAYING] PROFESSOR: Hello, and welcome back to our operating system and virtual memory module.
By now we know pretty well how does the virtual memory system work. And we even know how to implement it. So all that is left is to evaluate its performance.
And we even actually know that, because we are going to be using the same set of principles that we have used for evaluating the performance of our cache.
So to get started, let's compare cache and virtual memory system.
So in the cache version, whatever we used to call a block or the line is going to correspond to a page in a virtual memory system. Cache misses correspond to page faults.
Block sizes and caches are 32 to 64 bytes. Typical page size that we are dealing with is 4 KB.
Sometimes page sizes are a little bit smaller, 2 KB, can be larger, 8 or 16 KB. But we typically deal with 4 KB pages.
Placement in cache can be direct-mapped or N-way set associative. Generally in virtual memory systems, our pages are fully associative.
TLBs are fully associative. Replacement policy in cache can be least recently used, or random, or anything in between those two.
In virtual memory system, we generally would like to go with the least recently used. But sometimes we'll approximate it at something that may end up being either a FIFO or a random.
When we talk about write-back policy, writing back to the DRAM in case of a cache, we have options for write through and write back.
In virtual memory systems, we only write back because the penalty of writing through to the disk is so high.
So we're ready to evaluate the performance. Performance in a virtual memory system is going to be evaluated in the same way how we evaluate the performance of our cache system.
Virtual memory is the level of memory that is below the main memory. In our previous calculations, everything stopped at the main memory, at the DRAM level.
Now, our virtual memory extends the DRAM into a disk by using paging.
So although TLB becomes before the cache, it affects the data transfers from the disk to the main memory.
So in our previous calculations, main memory was the lowest level.
We just need to account for cases where our data is actually not in the DRAM, but we have to go all the way to a disk to retrieve it.
So same metrics of cycles per instruction and average memory access times are going to apply.
But this time we are going to treat our main memory as some kind of an intermediate-level cache.
So we are going to go through L1 cache, hit/misses speculations, then our calculations, then L2 hits and misses, then we are going to hit into the DRAM or miss, and end up in the disk.
So here are some of the parameters that we care about. So in our calculations, we had CPU cache and the primary memory.
Now we are going to have CPU primary memory and the secondary memory. So when we are talking about the caches, we talked about the cache entry.
In demand paging, we are dealing with page frames. Cache blocks are 32 to 64 bytes, as we said before. Pages are 4 KB.
When we talk about cache miss rate, we were generally happy when we get something that was in single digits.
So it would be typically L1 caches would be like 1% hits and 20%, perhaps, 10%, 20% in L2.
Now, page misreads have to be much, much slower, typically 1 in 10,000 or 1 in 100,000 or lower than that.
Cache hits would — our cache was designed so well that — and in most processor it will be — that basically we get the data out of cache in one cycle.
Cache miss corresponds to the page hit in DRAM. So that will be from a few tens of cycles to 100 cycles. Now, page miss corresponds to, say, 5 million clock cycles.
Because that's how much does it take us to go to the disk and corresponds to Jim Gray's analogy of going to Pluto.
So let's find out what is the impact of paging on average memory access time. So let's assume that we have the following memory parameters that are reasonably common.
And we can plug in any other numbers that you like. Commonly we get to do that in our exams.
So let's say that L1 cache hit is accomplished in one clock cycle. And we do that with 95% of accesses.
L2 cache, it takes 10 clock cycles and the hit rate is 60% of L1 misses.
DRAM takes 200 clock cycles, say, 100 nanoseconds — that's kind of pessimistic for modern systems. Usually would be less. But that's OK for the current calculation.
And finally, disk takes 20 million clock cycles, say, 10 milliseconds. Probably be faster if you plug in an SSD.
So the average memory access time without paging is calculated as this time that if we don't have a miss, if we have a hit, we can do everything in one clock cycle.
We get data out of the L1 cache in one clock cycle. And then we need to add the penalty of missing. So we will miss with 5% probability L1.
And that's going to cost us 10 clock cycles.
And then we miss in L2, that would be 5% of a miss in L1, times 40% of a miss in L2, times 200 cycles that it's going to take us to get to DRAM.
So that evaluates to 5.5 clock cycles. All right, this is a bit pessimistic. Modern systems are going to be a little bit faster than that.
But let's see how do we modify this to our account for the page memory system.
So to add paging, what we need to do, we need to take this 5.5 AMAT and add the impact of paging.
And so let's do that.
So Average Memory Access Time with paging equals to our 5.5 cycles plus 5% times 5% probability that we're going to miss in L1, 40% that we're going to miss L2, times 1 minus the hit rate into the memory that our data is not going to be in DRAM,
we are going to have to go all the way to a disk. And that's going to cost us 20 million cycles.
Now, keep in mind, 20 million is a huge number compared to any other numbers. So this hit rate into memory better be very close to 1.
So we mentioned it has to be better than 99%. But let's just take a look at what happens if it is just 99%. So we plug that in.
5.5 plus 0.2 times 0.01, that is 1 minus 99% times 20 million. We have AMAT of 4,000. That's like 700 times slower machine.
That's terrible. It's a horrendous performance. By the way, this does happen in practice.
If we continuously end up swapping pages, which happens if we are running out of physical memory, there are too many processes, too many classes, perhaps, sharing a machine, the machine continuously swaps.
Every 100 cycles or so, it is going to go to swap a page with the disk. And that is called thrashing.
And typically, when a machine is thrashing, it's like 100 to 1,000 times slower than it normally is.
So let's see what happens if you have a little bit better hit rate.
So this is what we have seen. This is what happens when our program is — if too many people are sharing a machine, a 10-second program can take two hours.
So what if the hit rate is 99.9%? Well, things get a little bit better, but not much better.
It's still AMAT is 400, a lot worse than what we have had before.
Finally, let's see what if it is a more reasonable number, if our miss into the DRAM is 1 in 10,000.
Then our AMAT gets increased from 5.5 to 5.9, which is more reasonable.
And this is something that we will often encounter. That's basically it what we need to do in this module.
We can take a quick break, and then we are going to see how can we incorporate I/O devices into this. See you a bit later.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.