程序代写代做 data structure kernel algorithm go cache Virtual Memory, Demand Paging, Intro Page Replacement

Virtual Memory, Demand Paging, Intro Page Replacement
1

Reading
 Dinosaur: Chapter 8, 9  Comet: Ch 21 22
2

Virtual Memory
3

Virtual Memory
 Definition: Virtual memory permits a process to run with only some of its virtual address space loaded into physical memory
 Key idea: Virtual address space translated to either  Physical memory (small, fast) or
 Disk (backing store), large but slow
 Deep thinking – what made above possible?
 Objective:
 To produce the illusion of memory as big as necessary
4

Virtual Memory
 “To produce the illusion of memory as big as necessary”
 Without suffering a huge slowdown of execution
 What makes this possible?
 Principle of locality
 Knuth’s estimate of 90% of the time in 10% of the code  There is also significant locality in data references
5

Virtual Memory Implementation
 Virtual memory is typically implemented via demand paging
 demand paging:
 Load memory pages (from storage) “on demand”
 paging with swapping, e.g., physical pages are swapped in and out of memory
6

Demand Paging
(paging with swapping)
 If not all of a program is loaded when running, what happens when referencing a byte not loaded yet?
 How to detect this?  In software?
virtual address
physical address
CPU
Translation (MMU)
Physical memory
I/O device
7

Demand Paging
(paging with swapping)
 If not all of a program is loaded when running, what happens when referencing a byte not loaded yet?
 Hardware/software cooperate to make things work
 Extend PTEs with an extra bit “present” (valid bit)
 Any page not in main memory right now has the “present” bit cleared in its PTE
 If “present” isn’t set, a reference to the page results in a trap by the paging hardware, called page fault
 What needs to happen when page fault occurs?
8

x86 Page Table Entry
Page frame number
U
P
Cw
Gl
L
D
A
Cd
Wt
O
W
V
31 12 Reserved
Valid (present) Read/write
Owner (user/kernel) Write-through
Cache disabled Accessed (referenced) Dirty
PDE maps 4MB Global
9

What is happening before and after malloc()?
 Before malloc()?
 After malloc()?
 Upon first access?
 How to capture the first write to a virtual page?  e.g. want to trap into page fault handler
 Use valid bit
 In handler, check if vpage is allocated (and access permitted)
 If not, segmentation fault
 Else allocate physical page
10

Page Fault Handling in Demand Paging
mem ref
Load M
fault
vi
vi
Inst seq.
Page Table (TLB)
VM subsystem
physical pages
11

Page fault handling (cont)
 On a page fault
 Find an unused phy. page or a used phy. page (how?)
 If the phy. page is used
 If it has been modified (how to know?), write it to disk
 Invalidate its current PTE and TLB entry (how?)
 Load the new page from disk
 Update the faulting PTE and its TLB entry
 Restart the faulting instruction
 Supporting data structure
 For speed: A list of unused physical pages (more later)
 Data structure to map a phy. page to its pid(s) and virtual address(es)
 Sounds faimiliar?
12

Deep thinking:
Virtual Address vs. Virtual Memory
 Virtual address
 Supported with dynamic memory relocation  Segmentation
 Paging
 Virtual memory
 Dynamic memory relocation + swapping  Demand paging
 Demand segmentation
13

Tasks of the VM subsystem
 Once the hardware has provided basic capabilities for VM, OS must make two kinds of decisions
 Page selection: when to bring pages into memory
 Page replacement: which page(s) should be thrown out, and when
14

Page selection (when)
 Prepaging
 Allocate physical page and (if from swap) bring a page into memory
before it is referenced
 Hard to do without a “prophet”, may unnecessarily bring pages
 Request paging
 Let user say which pages are needed when  Users don’t always know best
 And aren’t always impartial
 Demand paging
 Start up process with no pages loaded
 Load a page when a page fault occurs, i.e., wait till it MUST be in memory
 Almost all paging systems are demand paging
15

Page replacement algorithms? (which)
mem ref
Load M
VM
fault
vi
vi
Page table
physical pages
16

The BIG picture:
Running at Memory Capacity
 Expect to run with all phy. pages in use
 Every “page-in” requires an eviction
 Goal of page replacement
 Maximize hit ratekick out the page that’s least useful
 Challenge: how do we determine utility?
 Kick out pages that aren’t likely to be used again
 Page replacement is a difficult policy problem
17

What makes finding the least useful page hard?
 Don’t know future!
 Past behavior is a good indication of future behavior! (e.g. LRU)
 temporal localitykick out pages that have not been used recently
 Perfect (past) reference stream hard to get
 Every memory access would need bookkeeping  Is this feasible (in software? In hardware?)
 Minimize overhead
 If no memory pressure, ideally no bookkeeping
 In other words, make the common case fast (page hit)
 Get imperfect information, while guaranteeing foreground perf  What is minimum hardware support that need to added?
18

Definitions
(or, jargons asked during interviews)
 Pressure – the demand for some resource (often used when demand exceeds supply)
ex: the system experienced memory pressure
 Eviction – throwing something out
ex: cache lines and memory pages got evicted
 Pollution – bringing in useless pages/lines ex: this strategy causes high cache pollution
19

More definitions
 Thrashing – extremely high rate of moving things in and out (usually unnecessarily)
 Locality – re-use – it makes the world go rounds!  Temporal Locality – re-use in time
 Spatial Locality – re-use of close by locations
20

Performance metric for page replacement policies
 Give a sequence of memory accesses, minimize the # of page faults
 Similar to cache miss rate
 What about hit latency and miss latency?
21

Optimal or MIN
 Algorithm (also called Belady’s Algorithm)  Replace the page that won’t be used for the
longest time
 Pros
 Minimal page faults (can you prove it?)
 Used as an off-line algorithm for perf. analysis
 Cons
 No on-line implementation
 What was the CPU scheduling algorithm of similar nature?
22

What can we do without extra hardware support?
23

First-In-First-Out (FIFO)
Recently Page loaded out
 Algorithm
 Throw out the oldest page
 Pros
 Low-overhead implementation
 Cons
 No frequency/no recencymay replace the heavily used pages
5
3
4
7
9
11
2
1
15
24

Belady’s anomaly
Belady’s anomaly states that it is possible to have more page faults when increasing the number of page frames while using FIFO method of frame management. Laszlo Belady demonstrated this in 1970. Previously, it was believed that an increase in the number of page frames would always provide the same number or fewer page faults.

Example
Page Requests 321032432104

Example (Page Faults in Red)
Page Requests – 3 frames
Frame 1 Frame 2 Frame 3
3
2
1
0
3
2
4
3
2
1
0
4
3
3
3
0
0
0
4
4
4
4
4
4
2
2
2
3
3
3
3
3
1
1
1
1
1
1
2
2
2
2
2
0
0

Example (Page Faults in Red)
 Page Requests – 4 frames
 Frame 1
 Frame 2
 Frame 3
 Frame 4
3
2
1
0
3
2
4
3
2
1
0
4
3
3
3
3
3
3
4
4
4
4
0
0
2
2
2
2
2
2
3
3
3
3
4
1
1
1
1
1
1
2
2
2
2
0
0
0
0
0
0
1
1
1

Ideal curve of # of page faults v.s. # of physical pages
29

FIFO illustrating Belady’s anomaly
30

Predicting future based on past
 “Principle of locality”  Recency:
 Page recently used are likely to be used again in the near future
 Frequency:
 Pages frequently used (recently) are likely to be used
frequently again in the near future
 Is this temporal or spatial locality?  Why not spatial locality?
31

How to record locality in the past?
 Software solution?
32

Exploiting locality needs some hardware support
 Reference bit
 A hardware bit that is set whenever the page is referenced (read or written)
33

FIFO with Second Chance
Recently loaded
 Algorithm
Page out
5
3
4
7
9
11
2
1
15
If reference bit is 1
 Check the reference-bit of the oldest page (first in)
 If it is 0, then replace it
 If it is 1, clear the referent-bit, put it to the end of the list, and continue searching
 Pros  Fast
 Frequencydo not replace a heavily used page
 Cons
 The worst case may take a long time
35

Related Posts