YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 30.1 - Virtual Memory II: Hierarchical Page Tables

[CS61C FA20] Lecture 30.1 - Virtual Memory II: Hierarchical Page Tables — Transcript

by CS 61C Departmental · 1,694 words · 309 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00[Music]
0:11hello
0:12and welcome back to our virtual memory
0:15and operating
0:16system module in the previous segments
0:19we have introduced our page memory
0:20system and introduced
0:22page tables as a way of managing
0:25that virtual memory system we also
0:27talked about the analogy
0:29of going to a library and instead of
0:32when we walk into a library instead of
0:34just going straight for the bookshelves
0:36trying to find
0:38a book that we want based on the title
0:40that we have jotted down
0:43we go to the catalog first if we
0:46went to straight to the stacks to the
0:50bookshelves
0:51it would take us a very long time to
0:53find our title we really don't know
0:55where to start
0:56we so we would have to search for a long
0:58time
0:59if you go for a catalog or a database on
1:02a computer
1:02you would by searching for the title
1:07that we care about you would
1:10immediately exactly get pointed to the
1:13to the location
1:16on the shelves where our book title
1:18would be
1:20so that is what got us to our page
1:23tables
1:24and page table entries but there are
1:26some
1:27really important differences in how does
1:30this get
1:30implemented in a compute system where
1:34the size of the memory matters that is
1:37allocated to these page tables so
1:40we started talking about the how big are
1:43these
1:43page tables so in our 32-bit uh
1:48system with the 32-bit virtual address
1:51we decided to go with four kb pages
1:54which is a common choice
1:56so we took our 32-bit address space and
1:59split it into the the portion
2:03that is going to give us a virtual
2:04address uh to the page
2:07which was 20 bits and a 12-bit offset
2:10that would allow us to address data
2:13within
2:14a 4kb page
2:17now these 20 bits um result
2:22in a single page table size that is
2:264 bytes times 2 to the 20
2:29entries which is 4 maybe
2:33so we are allocating to a single page
2:36size
2:36four megabytes of our memory that is way
2:39too much for the
2:40cache but it is totally acceptable
2:43for a for gibby dram
2:47in a modest laptop nowadays that's just
2:500.1 percent
2:52of its d-run capacity
2:55but modern operating systems can have
2:59hundreds of processes running
3:00concurrently so um total
3:04size for 256 processes which are
3:09can be supported by modern operating
3:11systems
3:12where each process would need a page
3:15table
3:16would be huge so
3:19if we take a look at that we would have
3:21256 processes
3:23times 4 bytes times 2 to the 20
3:26entries so that will be 256 times 4
3:30maybe which is 1 gibby
3:32one gigabyte out of or four gigabytes of
3:34the laptop memory would be
3:36gone to page tables that's a lot and
3:39that really restricts the amount of of
3:41of of memory that our
3:45processes can actually use for storing
3:48program and the data
3:51and that's not all most computers
3:54nowadays are 64 bits
3:56have 64-bit addresses and that would
4:00really result in in exploding
4:03um size for the
4:06page tables so we need a better way to
4:09manage these page tables
4:12and keep the the size of page tables
4:14more reasonable
4:16so there are a few options that we can
4:18consider the first one
4:19is to increase the page size so double
4:23the doubling the page table size from 4
4:25kb to 8 kb
4:27would cut the pt size in half
4:31but that would result in more wasted
4:34memory if we
4:34really if our program uses less than
4:388 kb chunks well that
4:41you know whatever it does not use would
4:42end up being wasted so there is a
4:44trade-off there
4:45more commonly we are going to see
4:47something that is called hierarchical
4:49page tables where one level of page
4:52tables will be
4:53addressing a larger chunk of memory and
4:55then the next level of page tables will
4:57be zooming in onto
4:59a smaller chunk of a memory and that
5:02is very
5:06works very well with many of the
5:07programs that we encounter these days
5:10most of the programs that we see use
5:13only a fraction
5:14of the memory remember our program has
5:17an area for the code
5:18for the static data and heap and the
5:21stack that
5:22are growing in the opposite directions
5:24so typically
5:26in our virtual memory we have
5:30this large empty donut hole in the
5:32middle very few programs are going to
5:34fully
5:35use that that um all the memory
5:39most of them are going to have this
5:40giant donut hole that is empty
5:42so the idea here is when we split our
5:45face tables
5:47uh page tables
5:50into multiple parts
5:54then the pointers from the first level
5:58page tables would be
6:01in most cases pointing to nothing to
6:04that empty space that does not need to
6:06be allocated
6:07some of them are going to be pointing to
6:09the valid places where we
6:11would find the stack and the heap and
6:13static data in the code
6:14but majority will be pointing
6:18to unuse paste and
6:21as a result we can save a lot of space
6:24um that we for our page tables
6:28and this is basically what is done in
6:31risk five
6:33so let's take a look at how does a
6:36hierarchical page table
6:38look like so our virtual address
6:41is going to be now split into three
6:43parts instead of two parts
6:46we are still going to have an offset and
6:47in this case we can if we
6:49are working with a four kb pages we are
6:51going to keep a 12-bit offset
6:53so we can index within the
6:57the page table and then instead of using
7:00one monolithic
7:02chunk of 20 bits to
7:06address page tables we can split it into
7:08two 10-bit
7:09parts so
7:13we would point to the root of the
7:15current page table
7:16and then we are going to have
7:211024 possible
7:23level one page tables that are each
7:26pointing 2024 times
7:29kb or 4
7:32mb chunks in the memory now they would
7:35be pointing
7:36to level 2 page tables where each one of
7:39them
7:40would be pointing to 4kb
7:44now the main catch here is that most of
7:48those a
7:49huge majority of these
7:52second level page tables will be
7:55pointing to nothing
7:56a small number of them will be pointing
7:58to the
8:00data that actually to the to the either
8:03dram or disk that
8:07contains real allocated memory
8:11and therefore we really can compress
8:14this
8:15dramatically the the the amount
8:18of space that we use for page tables is
8:21going to be dramatically
8:24lower than if we were to use a
8:27monolithic
8:2820-bit address for them
8:32now you are start you may start
8:36to worry about is
8:40this how are we going to store this huge
8:42data structure this looks like we're
8:44building a data structure
8:45generally it is not that big of a deal
8:49the key thing that we care to store
8:52about
8:53is this root of the current page table
8:56you know the pointer to the very first
9:01entry into the level one page table
9:04that is the only thing that sets
9:06everything up since
9:08the paging system is set in a very rigid
9:10way where we
9:12actually really allocated exact number
9:15of bits for
9:16the offset and each of the levels of the
9:19page table
9:20tables then just by
9:24knowing where to start sets up this
9:27whole three
9:31so in risk five there is a supervisor
9:34page table base register
9:36that points to that and that is all on a
9:39context
9:40context switch when we would like to
9:45switch in a new process all what we need
9:47to do
9:48is to restore the you know save the
9:51state of a previous
9:52process restore the state of a new
9:54process and by
9:55just pointing this sp
9:59tbr to where the new process
10:02the new process has its data structures
10:07makes it ready to go let's take a look
10:09at
10:10just an example of how does risk 5 do it
10:13in 32-bit space one thing to to mention
10:16here
10:17in you know 32-bit with 32-bit address
10:19spaces
10:20we usually see two-level hierarchical
10:22page tables
10:23when we go to 64-bit address spaces in
10:26order to
10:27exploit further the sparsity and not
10:29explode again
10:30the size of page tables will typically
10:32see four layers of hierarchy
10:34that's what risk 5 does in 64 bits
10:38and so does the x86 for example
10:42so in 32-bit version of risc-5 32-bit
10:46virtual addresses are specified and
10:4834-bits physical addresses are specified
10:52a 32-bit virtual address space is split
10:54into a 12-bit offset
10:55for 4 kb pages and
10:59two parts of virtual addresses that are
11:02each 10 bits wide so these virtual
11:06page numbers point to physical page
11:08numbers
11:09and there are
11:13page table entries that are 32 bits
11:16wide each they are going to contain our
11:20physical page numbers
11:26upper and lower and then there is a
11:28whole bunch of status bits that we have
11:30refreshed in passing of course we are
11:32not going to test you on something like
11:33that
11:34this how are you memorizing this but
11:37here is a bunch
11:38of bits that are essentially setting
11:40access control and also helping us
11:43with the replacement policies most
11:46notably there are
11:47read write and execute access bits
11:51that tells us whether we can read write
11:55read from that page write to that page
11:58or execute
11:58code from that page um
12:03and you know what is interesting here by
12:05convention
12:06if all of these are zero we cannot
12:08either
12:09read or write or execute
12:12a page that means that that page is
12:14pointing to the next level
12:16of the page table otherwise
12:19it's a leaf pt that's the page that we
12:22should be accessing
12:23so that's a convention how that
12:26implements this multi-level
12:29page hierarchy then the other bits
12:32basically are going to tell us whether
12:34the page is valid
12:35and has it been raised decently so we
12:38can
12:39use that data in our replacement policy
12:46well that's it about hierarchical page
12:48tables
12:49when we come back after a break we're
12:51going to talk about
12:53how do we accelerate this in hardware
12:56see you then

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 30.1 - Virtual Memory II: Hierarchical Page Tables by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 1,694 words across 309 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.