Video
Đăng bởi Quản trị viên OpenER ·
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 module that deals with operating systems and virtual memory.
So far, we understood, reasonably well, what are the basic principles of operation of the virtual memory system. And we have seen that the processor or our process uses virtual addresses.
We translate those virtual addresses to physical addresses by using page tables.
Now, these page tables do reside in DRAM, and now our memory references get a lot more complicated and a lot slower.
What do I mean by that? Well, instead of just doing a load or a store to the memory, we actually have to make multiple trips to the memory.
If we are using a single-level page table, we have to make two trips to the memory in order to do a load or a store.
First, we need to go access the page table, and then the actual memory location where we would perform a load or a store.
If it is a two-level page table implemented in the system, we would have to make three trips to the memory — two to access page tables and the third one to actually do a load or a store.
And finally, if it is a four-level page table that we would encounter in a modern 64-bit processor, that would require us to make five trips to the memory.
That's slow.
Remember, we said memory accesses are — if compared to the access to the registers that are across the room, memory accesses are like trips to Sacramento.
Now we need to make five trips to Sacramento in order to get our data. That's expensive. We need to speed that up.
And that's what we are going to cover in this module — a method for speeding up these memory references. First, let's recap what we would like to do.
Our processor or process uses virtual addresses that consist of a virtual page number — VPN — and the offset. If you are working with 4KB pages, the offset will be 12 bits.
The virtual page number is the remaining 20 bits in 32-bit systems.
When we would like to access a new page, we need to go through the address translation to obtain a physical page number VPN, and we would append it to our offset to get the actual memory location that you would like to work with.
But before that, or concurrently with that, we need to do a protection check.
Whether this reference has been issued by a user-level process or a supervisor, and do we have access to those memory locations, are we allowed to read, or write, or execute?
And if the answer to any of those is no, then we throw an exception and let the operating system handle that.
And so every instruction and data access, for both instruction and data memories, needs address translation and protection checks.
This looks kind of complicated, and we would like all of this to happen, actually, in one cycle, not in many cycles that we referred to previously.
So let's see how do we speed this up. We generally will speed this up by using a hardware structure that lives inside the processor. This is called translation lookaside buffers — or a TLB.
It's like a little cache that we're using for this. We are caching these page access table references as we make them. Why is it called a buffer, not a cache?
Well, because it predates cache. So people who designed first the translation lookaside buffers did not know about caches, so they just used the word buffer, and that stuck.
All right. So we are still using TLBs.
So in order to speed up these address translations that are very expensive, we use the following caching mechanism.
We will cache some of the memory translations in the TLB. And TLB is a structure that has a relatively small number of entries that have been recently referenced.
So our VPN — instead of going to the memory, we are going to take the VPN to associatively check the locations here in the TLB and see if we have a match.
If you have a match, the physical page number is going to come out from the TLB.
And you are going to use it to append it to the offset to access the actual memory location. This is what will be called a TLB hit.
If we have a TLB miss — meaning that we cannot find a tag that corresponds to this virtual page number in our TLB — we need to go and walk our page tables, depending how many levels of hierarchy are there,
and update our TLB with a new reference. And then proceed with that. A few things here.
The TLB has to inherit many of the bits that we care about, the status bits that correspond to the actual page table entries.
We would like to know if it is valid, which is usually a reference to whether it exists in DRAM and whether it is dirty. What does dirty mean?
If it has been written to, and does it need to be written back to the disk in case we have to swap it.
But other bits are going to be there that are going to help us with checking the protection. Okay. So how is this TLB actually being designed in processors?
So typical TLBs nowadays can be either small and quick — 32 to 128 entries — and are usually fully associative.
Since each entry maps a large page, there is less spatial locality across pages and there is more likely the two entries will conflict.
So full associativity does make sense.
There are some large TLB designs that may have 256 to 512 entries, but they're made four to eight way set-associative.
And that is still done to make sure that we can exercise them in approximately one clock cycle. So the complexity here is balanced between the associativity and the size of the TLB.
The replacement policy is most commonly FIFO — the first one. The first entry that gets written in is the first one that is going to come out.
Because we would like to keep the freshest ones in our TLB — the freshest memory translations inside the TLB. Or it could be random.
Generally, a full LRU is perhaps a bit expensive to do to fully implement in one clock cycle, so people will implement some kind of approximation of that.
Another term that we'll typically find being used is something that's called the TLB Reach. And that corresponds to a size of largest virtualized space that can be simultaneously mapped by TLB.
So if we have 64 entries in the TLB and it is referring to 4KB pages, what is our TLB Reach? Well, you got it.
It's 64 times 4, or a quarter of a megabyte. All right. That's how much of a memory we can access straight out of a TLB.
The next question is — well, we know what the TLB is supposed to do, how do we actually implement it?
The first answer to that — first, we should ask ourselves, where should it be located, and where in our data path we should have the TLBs?
To answer that, let's first ask ourselves, which should we check first for our fresh contents — caches or TLBs?
Can cache hold requested data if corresponding page is not in physical memory? That gives us an answer — no. So the TLB has to come first.
The other question, then, is, if TLB precedes caches, does cache receive virtual or physical addresses? And now that's very simple. Cache has to contain physical addresses.
Okay. So here is a straightforward structure that we have been talking about. The CPU will issue virtual addresses. These virtual addresses go to the TLB.
TLB, in case of a hit, produces a physical address, and that goes to the cache.
If that physical address exists in the cache, if you have a cache hit, we send back that data to the CPU. And we are done.
If you have a cache miss, we go get that data from the main memory. We update the cache, and send it back to the CPU.
Now, one more thing can happen here — we can have a TLB miss. What happens on a TLB miss?
We generally have to walk — so-called — walk our page tables, update the page tables, and then proceed with the memory access.
The key thing here is that the TLBs do the translation of virtual to physical addresses, not the page table.
These page tables do reside in the main memory, and only if you have a TLB miss, we go to the main memory.
Now, TLBs are generally designed such that we have a very, very high hit rate.
Our hit rates typically into TLBs are better than 99%, or much better than 99%.
Typical numbers that you'll hear are 99.9% or 99.999%.
So let's see, actually, how is this address translation being implemented by using a TLB?
So we have our VPN and the page offset that our virtual address is composed of. Now, let's take a look at this.
We are going to make a split of our virtual page number into two parts. We are going to separate it into a tag and index.
And that is in case we may not be using full associativity.
Then that is going to point to the TLB. Inside the TLB, the TLB index is going to point to the tag.
And it is done in the exact same way as we will do it in the cache. If there is a hit, a physical page number is going to exist inside our TLB.
It will come out of the TLB, and we will compose our physical address by concatenating the PPN from the TLB with the page offset from the virtual address.
Now, we are going to split it again in a different way. We are going to break it up into our format that is used for accessing caches — tag index offset, or TIO.
So we are going to use our TIO to reference the data cache.
So if data is in the cache, it is going to be — we are going to have a hit. If not, we are going to have to update it.
And that is basically it. We can pause now. And after a quick break, we are going to see how is this actually implemented in a microprocessor data path.
See you in a sec.
Đă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.