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 virtual memory and operating system module.
In the previous segment, we have introduced our page memory system and introduced page tables as a way of managing that virtual memory system.
We also talked about the analogy of going to a library, and instead of when we walk into a library, instead of just going straight for the bookshelves, trying to find a book that we want based on the title that we have jotted down, we go to the catalog first.
If we went to straight to the stacks to the bookshelves, it would take us a very long time to find our title.
We really don't know where to start, so we would have to search for a long time.
If you go for the catalog or a database on a computer, by searching for the title that we care about, we would immediately exactly get pointed to the location on the shelves where our book title would be.
So that is what got us to our page tables and page table entries.
But there are some really important differences in how does this get implemented in a compute system, where the size of the memory matters that is allocated to this page tables.
So we started talking about how big are these page tables.
So in our 32-bit system with a 32-bit virtual address, we decided to go with 4-KiB, which is a common choice.
So we took our 32-bit address space and split it into the portion that is going to give us a virtual address to the page, which was 20 bits and a 12-bit offset that would allow us to address data within 4-KiB page.
Now, these 20 bits result in a single page table size that is 4 bytes times 2 to the 20 entries, which is 4 maybe.
So we are allocating to a single page size 4 megabytes of our memory.
That is way too much for the cache, but it is totally acceptable for a 4-GiB DRAM in a modest laptop nowadays.
That's just 0.1% of its DRAM capacity. But modern operating systems can have hundreds of processes running concurrently.
So total size for 256 processes, which can be supported by modern operating systems, where each process will need page table would be huge.
So if we take a look at that, we will have 256 processes times 4 bytes times 2 to the 20 entries so that we 256 times for maybe, which is 1-GiB.
1 gigabyte out of 4 gigabytes of the laptop memory would be gone to page tables. That's a lot.
I mean, that really restricts the amount of memory that our processes can actually use for storing program in the data.
And that's not all.
Most computers nowadays have 64-bit addresses, and that would really result in exploding size for the page tables.
So we need a better way to manage these page tables and keep the size of page tables more reasonable. So there are a few options that we can consider.
The first one is to increase the page size. So doubling the page table size from 4-KiB to 8-KiB would cut the size in half.
But that will result in more wasted memory if our program uses less than 8-GiB chunks, whatever it does not use would end up being wasted.
So there is a trade-off there.
More commonly, we are going to see something that is called hierarchical page tables, where one level of page tables will be addressing a larger chunk of a memory and then the next level of page tables will be zooming in onto a smaller chunk of our memory.
And that works very well with many of the programs that we counter these days. Most of the programs that we see use only a fraction of the memory.
Remember, our program has an area for the code, for the static data, and heap and the stack that are growing in the opposite directions.
So typically, in our virtual memory, we have this large empty donut hole in the middle. Very few programs are going to fully use all the memory.
Most of them are going to have this giant donut hole that is empty.
So the idea here is, when we split our page tables into multiple parts, then the pointers from the first level page tables would be — in most cases — pointing to nothing.
To that empty space that does not need to be allocated.
Some of them are going to be pointing to the valid places where we would find the stack and the heap and static data and the code, but majority will be pointing to unused space, and as a result, we can save a lot of space that we put for our page tables.
And this is basically what is done in RISC-V. So let's take a look at how does hierarchical page table look like.
So our virtual address is going to be now split into three parts instead of two parts.
We are still going to have an offset, and in this case, if we are working with 4-KiB pages, we are going to keep a 12-bit offset.
So we can index within the page table, and then instead of using one monolithic chunk of 20 bits to address page tables, we can split it into two 10-bit parts.
So we would point to the root of the current page table, and then we are going to have 1,024 possible level 1 page tables that are each pointing 2,024 times 4-KiB or 4 midi
chunks in the memory. Now, they would be pointing to level 2 page tables, where each one of them would be pointing to 4-KiB.
Now, the main catch here is that most of those — a huge majority of these second level page tables — will be pointing to nothing.
A small number of them will be pointing to the data that actually to the either DRAM or disk that contains real allocated memory.
And therefore, we really can compress this dramatically.
The amount of space that we use for page tables is going to be dramatically lower than if we were to use a monolithic 20-bit address for them.
Now, you may start to worry about is this how are we going to store this huge data structure? This looks like we're building a data structure.
Generally, it is not that big of a deal. The key thing that we care to store bought is this root of the current page table.
The pointer to the very first entry into the level 1 page table. That is the only thing that sets everything up.
Since the paging system is set in a very rigid way where we actually really allocated exact number of bits for the offset and each of the levels of the page tables, then just by knowing where to start sets up this whole tree.
So in RISC-V, there is a supervisor page table based register that points to that, and that is all.
On the context switch, when we would like to switch in a new process, all what we need to do is to restore the — save the state of a previous process, restore the state of a new process, and by just pointing this SPTBR to where
the new process has its data structures makes it ready to go. Let's take a look just an example of how does RISC-V do it in 32-bit space.
One thing to mention here. With 32-bit address spaces, we usually see two level hierarchical page tables.
When you go to 64-bit address spaces, in order to exploit further this sparsity and not explode, again, the size of page tables, we'll typically see four layers of hierarchy.
That's what RISC-V does. In 64 bits, so does the x86, for example.
So in 32-bit version of RISC-V, 32-bit virtual addresses are specified, and 34-bits physical addresses are specified.
And 32-bit virtualized spaces split into a 12-bit offset for 4-KiB pages, and two parts of virtual addresses that are each 10-bits wide.
So these virtual page numbers point to physical page numbers, and there are page table entries that are 32 bits wide each.
They are going to contain our physical page numbers, upper and lower, and then there is a whole bunch of status bits that we have referenced in passing and force.
We are not going to test you on something like that — that's how you memorizing this, but here is a bunch of bits that are essentially setting access control and also helping us with the replacement policies.
Most notably, there are read, write, and execute axis bits. That tells us whether we can read, write, read from that page, write to that page, or execute code from that page.
And what is interesting here by convention, if all of these are zero, we cannot either read or write, or execute a page.
That means that pages point to the next level of the page stable. Otherwise, it's a leaf PTE, that's the page that we should be accessing.
So that's a convention how that implements this multi-level page hierarchy.
Then the other bits, basically, are going to tell us whether the page is valid and has it been released recently so we can use that data in our replacement policy.
Well, that's it about the hierarchy on page tables. When we come back after the break, we are going to talk about how do we accelerate this in hardware.
See you then.
Đă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.