COMP 3430 Operating Systems – Chapter 21 and 22 reading notes
Winter 2022
About these reading notes
Chapter 21: Beyond Physical Memory: Mechanisms
Copyright By PowCoder代写 加微信 powcoder
SwapSpace…………………
ThePresentBit ………………. Thepagefault……………….. Whatifmemoryisfull?……………
Pagefaultcontrolflow ……………………………….. 4 Whenreplacementsreallyoccur…………………………… 5
Chapter 22: Beyond Physical Memory: Policies 5 CacheManagement ………………………………… 5 Theoptimalreplacementpolicy…………………………… 6 Asimplepolicy:FIFO………………………………… 6
Aside:Belady’sAnomaly……………………………. 7 Anothersimplepolicy:random …………………………… 7 Usinghistory:LRU …………………………………. 7 WorkloadExamples…………………………………. 7 Implementinghistoricalalgorithms…………………………. 8 ApproximatingLRU…………………………………. 8 Consideringdirtypages ………………………………. 9 OtherVMpolicies………………………………….. 9 Thrashing……………………………………… 9
…… …… …… ……
…………….. 2 …………….. 3 …………….. 3 …………….. 4
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
About these reading notes
These are my own personal reading notes that I took (me, Franklin) as I read the textbook. I’m pro- viding these to you as an additional resource for you to use while you’re reading chapters from the textbook. These notes do not stand alone on their own — you might be able to get the idea of a chap- ter while reading these, but you’re definitely not going to get the chapter by reading these alone.
These notes are inconsistently all of the following:
• Mesummarizingpartsofthetext.
• Mecommentingonpartsofthetext.
• Measkingquestionstomyselfaboutthetext.
– …andsometimesansweringthosequestions.
The way that I would expect you to read or use these notes is to effectively permit me to be your in- ner monologue while you’re reading the textbook. As you’re reading chapters and sections within chapters, you can take a look at what I’ve written here to get an idea of how I’m thinking about this content.
Chapter 21: Beyond Physical Memory: Mechanisms
So, uh, surprise! Turns out that assuming address spaces fit into memory is not a valid assumption to be making about how real processes run.
Our goal here is to now permit using (at least part of) our hard drive to supplement the physical mem- ory that we have available. The idea is that we want to be able to oversubscribe physical memory.
Aside: Can we make observations about how absurdly big 64 bits of address space actually is? Swap Space
Swap space is space that we reserve on a disk for writing out pages from memory when we’re not using them or need more space.
We’re going to need another mapping here (do we need another mapping, or just a different kind of mapping?) to map virtual page numbers to disk addresses.
Aside: What is a disk address? How is it different from memory? How is it different from a sector number?
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
The amount of space we reserve for a swap space tells our system exactly how much addressable space we have in total.
Aside: Some real world details about swap space:
• On a Linux system, this can be a partition on a physical disk or a file on a volume with a file system.
• OnaWindowssystemthisisC:\swapfile.sys
• On a macOS system these are in /private/var/vm/swapfile*, and there are possibly
many of them(?). My macOS system only has one.
Think about it: Where would be the best place to put a swap space: in a file on a file system, or as its own partition (physical access directly to the disk)?
The Present Bit
Let’s start by reviewing how an address lookup works with a page table and a TLB. 1. LookupvirtualaddressinTLB,
• Ifit’sthere(hit),great,proceed.
• Ifnot(miss),thenlookforthepageinphysicalmemory.
2. Lookupinphysicalmemory
• FindthepagetableinmemoryusingthePTBR(pagetablebaseregister) • Findtheappropriatepageentrymappingwiththevirtualpagenumber.
Also remember that there’s more to a virtual address mapping in a page table entry than just an ad- dress to address (refer back to chapter 18).
The present bit can tell us if the page is in physical memory or if it’s been swapped to disk. The hard- ware must defer to the OS here to load that page into memory, since the hardware has no idea how or what the swap file is (this is an OS-specific thing).
The hardware can inform tell the OS “I need you to load this page into memory from disk, please do it now before I can keep going.” by issuing a page fault.
The page fault
… even with a hardware-managed TLB, the hardware trusts the OS to manage this important duty.
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
Aside: “Trusts” the OS? What would the hardware even do in this case? How would it kill a process? I think a better word here would be “defers to” rather than “trusts”.
So what does the OS do? How does it know where to find the page on disk? One idea proposed by the book is to just straight-up use the physical frame number part of the page table entry. The hardware won’t try to do anything with that part because it’s going to check the present bit first, then bail out with a page fault. After the OS has finished handling the page fault, then it will change the PFN in the page table entry to reflect the actual place where it put the page.
Whenever we’re loading a page from disk, the OS will mark the process as “blocked” (in the minimal book states).
Aside: Would this be interruptible sleep or uninterruptible sleep? What if memory is full?
Swapping is called swapping for a reason: we may have to swap one page entry for another in physical memory. We may have to page out a page into the swap space so that we can page in a different page.
With TLB caching (check out chapter 19), we had a couple of basic options:
1. Usethenuclearoption,justflushtheentirecache
2. Use an algorithm, though there are counter-intuitive side effects of choosing what seem to be
sane algorithms (like LRU).
Even the nuclear option is not so bad with the TLB because putting those entries in, even from main memory, is not very expensive (relatively).
We have to actually think about which page to swap out when we’re going to select one to be evicted. (see chapter 22).
Page fault control flow
So now we have a few different possible cases when trying to load a page from memory:
1. ThepageentryisintheTLBandit’sarealpage,sogoforit
2. ThepageentryisnotintheTLB,findtheentryinthepagetable,then
• Checkafewbitstoseeifwecanactuallyaccessthememory,thenaccessthememoryand cache the mapping.
• Checkiftheentryisnotpresent,thenraiseapagefaultandlettheOStakeover.
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
When replacements really occur
So far we’ve assumed that we just blindly fill memory until there’s no memory left, then start swap- ping.
But… that doesn’t make a lot of sense. When a new process is launched, we’d rather have free memory to load it into immediately rather than having to do all the swapping out nonsense.
Most OSs (Linux included) have this concept of a “high watermark” and a “low watermark” to help them decide when idle swapping should start to happen. That is, nothing else is happening right now, so I’m going to start swapping some pages out to disk that haven’t recently been used so that when a new process starts it can start occupying pages in memory immediately.
This whole process is handled by thread or process running entirely in kernel space called a swap daemon. On Linux, this is called kswapd.
Since swap space itself isn’t a file system, the OS can do what it wants with ordering writes to disk. The OS can take advantage of its knowledge of the disk to decide how to write the pages to disk.
The summary of this part is that the OS doesn’t actually conduct swapping out operations immedi- ately when the page is requested, but rather does swapping activities in the background and possibly in bulk.
Chapter 22: Beyond Physical Memory: Policies
Remember that time in chapter 21 when we said we’d talk about policies for swapping out pages later? Guess what! That time is now!
Memory pressure is this nebulous term that we can use to describe when our efforts to oversubscribe memory are coming to a head.
We use a replacement policy to decide which page(s) to page out to swap space. Similar to the TLB eviction policies (see chapter 19), this is a caching problem, but at a different scale – GBs vs KBs or MBs.
Cache Management
Hey, what do you know? The first subtitle is called “Cache management”. Oh hey, look at that: again, we’re using terms like hit and miss! What a familiar sounding problem!
The metric we’re going to use to evaluate these policies is the average memory access time (AMAT).
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
Aside: Why didn’t we discuss this when we were looking at TLBs? Is the speed difference negligible enough that we don’t care? Is it because this is not something we have control over (the hardware has the responsibility for managing the TLB)?
Our metric is formalized as:
AMAT = 𝑇𝑀 + (𝑃Miss × 𝑇𝐷)
• 𝑇𝑀 is the cost of accessing memory. When we want to access a page we always have to refer to memory. (do we?)
• 𝑃Miss is the probability that we will miss the cache.
• 𝑇𝐷 is the cost of accessing disk when we do miss the cache.
The example the authors then show is calculating the probability of missing experimentally rather than proving something. They contrive an example where the process would load a sequence of ad- dresses that are each in different pages.
The main takeaway here is that any disk access quickly dominates the cost because disk accesses (𝑇𝐷 ) are orders of magnitude bigger than memory accesses (𝑇𝑀 ).
The optimal replacement policy
The optimal replacement policy is to swap out the page that’s going to be the one that we use the longest time from now.
We have an important term introduced here: “Cold-start miss” or “compulsory miss”, referring to the cache misses that happen when we’re initially populating the cache. The authors describe calculating the hit or miss rate by excluding these misses.
The authors state that this is pretty self explanatory, and it pretty much is…
But… yeah. We can’t predict that. Our replacement policy is not an omniscient oracle.
A simple policy: FIFO
So, uh, huh. This sounds real familiar. Well, it might, if you read chapter 19.
Aside: The authors have picked this specific sequence of page accesses to evaluate the algorithms.
Is this a fair evaluation of the overall performance of a replacement policy?
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
Aside: Belady’s Anomaly
This is actually sort of interesting, and describes why something like LRU could actually be good and how increasing cache size may make some policies behave worse.
Another simple policy: random
So, uh, huh. This sounds real familiar. Well, it might, if you read chapter 19.
There’s not anything really to explain here beyond that experimentally we can show that sometimes
it does good and sometimes it does bad. Luck of the draw. Using history: LRU
So, uh, huh. This sounds real familiar. Well, it might, if you read chapter 19.
When we looked at LRU with the TLB we decided that under certain circumstances it could be a bad
replacement policy.
The issue that we had with LRU and TLB is that we were dealing with addresses (not pages). The way that code usually works (in its loopy manner) is that the least recently used atomic address might ac- tually be coming back pretty soon. But with an entire page of data, we’re now thinking about different scales.
Now we’re looking at two measurements that we can use to decide what “recent” means:
1. Frequency:howmanytimeshasthispageeverbeenaccessed? 2. Recency:whendidwelastaccessthispage?
Collectively, policies that consider things like this are referred to as policies that follow the “principle of locality”. We care here about spatial (pages nearby this one that’s used frequently may also be used frequently) and temporal locality (if I just accessed this page, it’s likely I’ll access it again).
An important tiny thing is that LRU is stateful where FIFO (and random, of course) are stateless. LRU is complemented with Least frequently used (LFU), and they are different!
Workload Examples
OK. Yes. Contrived workload for examples above is contrived.
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
So now we’re going to contrive more example workloads, but they’re going to be slightly more com- plicated than 3 pages of data. We’re also going to contrive them so that they showcase extreme work- loads.
The first workloads is one that will use a randomness to try and load completely random pages from memory. The idea here is that we’re building a workload with no locality.
In this workload, all policies behave effectively the same in terms of hit rate (except for optimal, which is all knowing).
The next workload is “80-20”, where we will make most references to a small number of pages and a small number of references to most pages. (80% of references are to 20% of pages). This is arguably a more realistic workload for running a single interactive application among many inactive applica- tions.
Optimal, of course, works best. Least recently used also performs well (as you might expect, we’ve contrived a workload that has locality properties).
Final workload is “looping sequential”, where we repeatedly loop over 𝑛 pages 𝑚 times, in se- quence.
Surprise! Just like with our TLB, LRU does poorly here. So does FIFO because LRU basically becomes a FIFO when the workload is sequential. Random (again, as with TLB) does pretty well.
Implementing historical algorithms
Managing a queue is not a trivial operation when you have to do it constantly. So let’s add some hardware support!
… Well, even with hardware support, finding the least recently used page involves searching and sort- ing, and with large numbers of pages, it’s going to quickly get expensive.
Approximating LRU
We can work with the hardware: let the hardware set a bit in a page table entry when a memory refer- ence is made, then we as the OS can use some algorithm to reset the bits over time.
The book here describes the clock algorithm, where we imagine that all of the pages are in a circle, and we have a clock hand that scans through until it finds one that’s not set. As the clock hand is scanning, it’s resetting the bits to 0.
Figure 22.9 shows that this algorithm approximates LRU pretty closely.
COMP 3430 Operating Systems – Chapter 21 and 22 reading notes Winter 2022
Considering dirty pages
A “dirty” page is one that has been written to during execution. If a page has never been written to, it’s “free” to evict it from the cache because we don’t have to write it back to disk when we page it out. On the other hand, a dirty page needs to be written back to disk when it’s evicted.
Other VM policies
We don’t just have to decide when to page things out, we also have to decide when to page things in, a page selection policy.
The obvious thing to do is to page in when a page is requested (i.e., when we’re handling a page fault). It may also be reasonable to fetch nearby pages while we’re handling a page fault (prefetching).
We also have policies for writing pages back to disk. It could either be on demand, but would prefer- ably be clustering pages together to take advantage of large writes.
We oversubscribed memory by telling many processes that they all had lots of memory. Sometimes processes will actually try to use all of that memory, and we wind up constantly swapping pages in and out – thrashing.
We could write complex systems to try and suspend processes for a while, or we could take the OOM killer approach and just kill processes willy-nilly.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com