YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 29.5 - Virtual Memory I: Page Faults

[CS61C FA20] Lecture 29.5 - Virtual Memory I: Page Faults — Transcript

by CS 61C Departmental · 1,831 words · 319 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:14and operating system support module
0:16we introduced a system the page memory
0:19system
0:20and seen how our pages
0:23work they can reside either in dram
0:26or on the disk and we have a page table
0:30that tells us whether the pages have
0:32been allocated
0:33and whether they are in dram or on the
0:36disk
0:38we're going to take a little bit more
0:41detail look into how does the system
0:43actually work but before
0:45that let's recap some things and
0:49you know remove any confusions that we
0:50might have caused
0:52first let's make sure that you
0:55understand
0:56what are these blocks and pages and
0:58understand that there are
0:59generally just different ways of
1:01measuring how many
1:02bytes are we working with like in the
1:05metric system where we use kilos and
1:07millis
1:08to tell us how much of grams are we
1:12dealing with in weight here we are using
1:16different metrics for some amount of
1:18bytes that we
1:19are moving around so in general
1:22in caches we deal with individual blocks
1:25and blocks are
1:26you know 64 bytes in most modern systems
1:30some of them may be 128. um
1:33the the thing uh also to make sure here
1:36is don't confuse this block
1:38with the size of a block that sometimes
1:41is referred to in storage in ssds
1:45and disks cache
1:49blocks are 64 bytes in our case
1:53in virtual memory we generally deal with
1:55pages
1:56and pages in our case are for kiwi
2:00and in most other modern systems they're
2:02also
2:044kb so um don't confuse bytes words
2:09blocks and pages they're just different
2:11ways
2:11of measuring the amount of data that we
2:15have in the memory
2:16let's take a look at a quick example
2:18let's say that we have a really really
2:19simple computer it just has a you know
2:21tiny amount of dram
2:23the total 16 kb
2:26the 16 kb will be organized into four
2:30pages for each page is uh 4 kb
2:33in a simple virtual memory system they
2:36would have
2:37it will have 128 byte blocks
2:40for caches and four byte words
2:43for loads and stores so
2:47our memory system here would have 16
2:51kiwi uh those 16 kb would be organized
2:55into four
2:564 kb pages each page
2:59would have 32 blocks each
3:04block would have 32
3:07words each word would have four bytes
3:11so to recap all of that we can think of
3:13the entire memory
3:14as four pages 128 blocks
3:184096 words or 16
3:22384 bytes we can think of a page
3:25as having 32 blocks or 1024 words
3:30and finally each block can have 32 words
3:34or 128
3:38bytes
3:41the other analogy that we would like to
3:44recall now since we have seen how does
3:45the page memory system work
3:47is the library analogy um
3:51we generally in our heads we keep
3:53library
3:54we keep book titles so all what we
3:57remember is a book title we don't
3:58remember the
3:59library or congress call number so when
4:02we
4:03refer to a book we refer to it by
4:06the bytes title but going
4:10to the library straight for the
4:13bookshelves
4:14to try to find that book is usually not
4:17going to
4:18you know
4:19[Music]
4:23yield the reasonable result we may not
4:25find the book just going straight for
4:27the stacks
4:30books are organized in different ways
4:32and generally we would have to go
4:34for the card catalog like the page table
4:37uh
4:38what is in our virtual memory
4:40equivalence
4:41that maps the titles to the
4:44library or congress call numbers on
4:48that card entry that is in our catalog
4:53we would find out a valid bit whether
4:56the
4:57book exists in this library system
5:00and where is it is it in the main memory
5:03or is it on the disk
5:04meaning some external storage or some
5:06other library some other facility
5:09finally there may be a reservation bit
5:11on that
5:13entry that tells us you know for how
5:15long we can check out that book and can
5:17we check it out at all
5:20another important thing here that should
5:22be brought up is when the library
5:24brings a new book to its collection it
5:26doesn't just go and
5:27shove it onto on the library stacks
5:30every time a new book is brought
5:32a new page is brought in our virtual
5:34memory system we need to create a
5:36catalog page for it we need to
5:38create create a catalog card for it and
5:42place it in in the collection
5:46all right so back to our page memory
5:49system
5:50in our page memory system what we have
5:52seen is that
5:53each process works with its own
5:57page table a page table has multiple
6:00entries that are pointing
6:01to the pages that may reside in dram
6:04or on the disk now
6:07in addition to these references to the
6:10dram or the disk
6:12there are some of the status bits that
6:14are associated with each page table
6:16entry
6:16we have seen that we need to have a
6:18valid whether the page
6:20is allocated you know whether it exists
6:24but also we are seeing that there is a
6:25need for another one we need to know
6:27whether that page is
6:28in dram or is on the disk
6:32this is just conceptual what we'll find
6:34out is
6:35that virtual memory systems are specific
6:39to the isa
6:40and have uh you know a bit longer
6:43uh you know number or larger number of
6:46these control bits
6:47that are telling us you know what is uh
6:51what's the status of of each page table
6:53entry we'll see some of those
6:55a bit later but conceptually we need to
6:58know whether the page is valid
6:59and whether it resides in dram or it's
7:02on the disk
7:04now there is an important mechanism
7:08that gets invoked every time we would
7:11like
7:11to perform this translation would like
7:14we see a virtual address
7:16and then we would like to find out we
7:19would like to get our data
7:20we need to find out whether we want to
7:22get it from the drum or the disk
7:24or we actually need to create a new page
7:27table entry
7:28so on each memory reference
7:31loads and stores we are going to check
7:35the page table entry
7:36if it is valid we are going to proceed
7:40with checking where is that page if it
7:44is in dram
7:44that's great we're just going to go
7:46ahead and rewrite the data
7:50if it is on a disk that may be a lengthy
7:53procedure
7:54of getting that data into the dram
7:58so we have to going to allocate a new
8:00page in dram if there is
8:01rom that's great if there is no room in
8:04if all
8:04of the the dram has been allocated there
8:07is no free space in dram
8:09we would have to evict a page from dram
8:12uh store this evicted page to disk so
8:15move
8:15that page from that that is being
8:18evicted and that's usually the one that
8:20was
8:20least recently used would be moving to
8:23the disk
8:24it would read the page from the disk
8:25into the memory and then proceed with
8:27reading and writing the data
8:31in other case if the page is
8:34page table entry is not valid we
8:38that means that we haven't referenced
8:39that data before
8:41so we are going to allocate a new page
8:42in dram uh if you're out of memory we're
8:45going to do like we did before we're
8:46going to edit the page
8:47and move it to to disk and then read and
8:51write data
8:52to the newly created page indira
8:55in these two cases if the data is not on
8:58disk
9:00or not valid we
9:03need an os intervention os needs to
9:06handle all of that and it does it run
9:09mechanism
9:10of a page fault
9:14what is a page fault well page fault
9:18is a special exception
9:22that is invoked when
9:25we are handling one of these two
9:26conditions
9:28so it is handled by the same mechanism
9:31that we have seen before that we have
9:33outlined before of mechanism
9:36of handling the exceptions
9:39[Music]
9:41it does all the page table updates and
9:44initiates transfer from the dram to disk
9:46and this this to dram
9:47and updates the status bits
9:51this is something that is done by the os
9:54in the supervisor mode now
9:58if this procedure involves moving
10:02the data to and from to the disk
10:04essentially a swap of a page
10:06with uh with a disk it will often
10:10generally perform the context switch
10:11because that's a lengthy procedure that
10:13means that this process needs something
10:15from pluto or mars and it's going to
10:18take a while
10:19so processor going to be idle
10:22for tens of milliseconds it's a perfect
10:25time to
10:26initiate a context switch and have some
10:28other process
10:29use the processor while the data is
10:32coming in
10:35then following the page fault the
10:37instruction is re-executed remember
10:39when we raise the exec exception we
10:42are cancelling that instruction that is
10:45being in flight loader store
10:47it has no hope of you know finishing
10:50then if the data is not
10:52valid so it will wait for the data to
10:56be valid in the memory and complete the
10:59instruction a few
11:03other things even though our virtual
11:05memory system appears to be huge it is
11:07not
11:07infinite so if you try to allocate
11:10something that is
11:10just really really big like try to
11:13allocate
11:14an array that is thousand twenty four
11:16times twenty thousand twenty four times
11:18thousand twenty four times the word
11:20length
11:21um we may run out of memory we're gonna
11:23get this kind of an
11:25exception fail to allocate 131
11:28terabytes we are out of memory
11:31so if we don't have that much memory or
11:33that much
11:34and that much list together we are
11:37we can do it we can complete this
11:40um another point here that we would like
11:43you know that is fairly straightforward
11:45but we just want to make sure that
11:47it is clear unlike caches where we had
11:50different policies how do we want to
11:53write data back to the
11:56memory from the cache we
12:00you know discuss the right through or
12:02write back policies
12:04when we are dealing from
12:07data transfers updates to the disk
12:10we really have only one option the cost
12:13of mov of writing data back to a disk is
12:16so huge
12:17that the only option that we can do is
12:20right back
12:20right through is uh you know really not
12:24an option because it's going to be
12:25really really slow so we
12:27the only policy here is going to be
12:29right back on the least recently used
12:32page
12:33so um you know write policies in virtual
12:36memory systems are significantly simpler
12:38than what we encounter
12:40in caches
12:44i think it's a good time now to pause we
12:46are going to continue
12:47with some other interesting
12:50aspects of the virtual memory after
12:54the break

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 29.5 - Virtual Memory I: Page Faults by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 1,831 words across 319 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.