程序代写代做 cache algorithm kernel clock Page Replacement

Page Replacement
1

Reading
 Chapter 9
 Lab 4 starts this week
2

Virtual Memory review
 What is Virtual Memory?
 Virtual address vs. virtual memory?
 How is Virtual Memory typically implemented?
 What is demand paging?
 It can also be implemented via demand segmentation
 In Virtual Memory, what will the virtual address space be translated to?
 What is a page fault?
 Page fault vs. TLB miss?
3

[lec16] Virtual Memory
 Definition: Virtual memory permits a process to run with only some of its virtual address space loaded into physical memory
 Virtual address space translated to either  Physical memory (small, fast) or
 Disk (backing store), large but slow
 Objective:
 To produce the illusion of memory as big as necessary
4

[lec16] Page Fault Handling in demand paging
VM
235
fault
6
4
Page table
mem ref 1
Load M
vi
vi
Physical pages
1. MMU(TLB)
2. Pagefault
3. Page replacement
4. Adjust PTE of victim pg
5. Swapinpagefromswap
6. Resumefaultingintr5

[lec16] The Policy Issue: Page selection and replacement
 Once the hardware has provided basic capabilities
for VM, the OS must make two kinds of decisions
 Page selection: when to bring pages into memory
 Page replacement: which page(s) should be thrown out  Try to kick out the least useful page
6

Page replacement problem
Definition:
Expect to run with all physical pages in use
Every “page-in” requires an eviction to swap space How to select the victim page?
Performance goal:
 Give a sequence of memory accesses, minimize the # of
 given a sequence of virtual page references, minimize the # of page faults
Intuition: kick out the page that is least useful
Challenge: how do you determine “least useful”?  Even if you know future?
page faults
7

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?
8

What can we do without extra hardware support?
9

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
10

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.

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

FIFO illustrating Belady’s anomaly
13

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?
14

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

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

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
17

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
18

Clock: a simple FIFO with 2nd
chance
Oldest page
 FIFO clock algorithm
 Hand points to the oldest page
 On a page fault, follow the hand to inspect pages
 Second chance
 If the reference bit is 1, set it to 0 and advance the hand  If the reference bit is 0, use it for replacement
 What is the difference between Clock and the previous one?  Mechanismvs.policy?
19

Clock: a simple FIFO with 2nd
chance
Oldest page
 What happens if all reference bits are 1?
 What does it suggest if observing clock hand is
sweeping very fast?
 What does it suggest if clock hand is sweeping very slow?
20

break
21

Names Every Systems Student Should Know

Why Are We Doing This?
 Really, you should know these people!  They did some great work!
 Their work (still) have influence now

How Are We Going to Do This?
 One to two per lecture
 Turing award winners related to systems
 Scientists who have made contributions comparable to a turing award
 People who are still active (and alive)  Mainly systems people, some other  Academia and industry
 Disclaimer: The list is definitely incomplete. I may miss some, doesn’t mean they are not important!

Alan Turing

Edsger Dijkstra
 Algorithms/systems  Father of algorithms  the “THE” OS

We’ve focused on miss rate. What about miss latency?
 Key observation: it is cheaper to pick a “clean” page over a “dirty” page
 Clean page does not need to be swapped to disk
 Challenge:
 How to get this info?
27

Refinement by adding extra hardware support
 Reference bit
 A hardware bit that is set whenever the page is
referenced (read or written)
 Modified bit (dirty bit)
 A hardware bit that is set whenever the page is written into
28

Enhanced FIFO with 2nd-Chance Algorithm (used in Macintosh VM)
 Same as the basic FIFO with 2nd chance, except that it considers both (reference bit, modified bit)  (0,0): neither recently used nor modified (good)
 (0,1): not recently used but dirty (not as good)
 (1,0): recently used but clean (not good)
 (1,1): recently used and dirty (bad)
 When giving second chance, only clear reference bit
 Pros
 Avoid write back
 Cons
 More complicated, worse case scans multiple rounds
30

Enhanced FIFO with 2nd-Chance
Algorithm – implementation
 On page fault, follow hand to inspect pages:
 Round 1:
 If bits are (0,0), take it
 if bits are (0,1), record 1st instance
 Clear ref bit for (1,0) and (1,1), if (0,1) not found yet
 At end of round 1, if (0,1) was found, take it
 If round 1 does not succeed, try 1 more round
31

Least Recently Used (LRU)
 Algorithm
 Replace page that hasn’t been used for the
longest time
 Advantage: with locality, LRU approximates Optimal
 Question
 What hardware mechanisms are required to implement exact LRU?
32

Implementing LRU: hardware
 A counter for each page
 Every time page is referenced, save system
clock into the counter of the page
 Page replacement: scan through pages to find the one with the oldest clock
 Problem: have to search all pages/counters!
33

Approximate LRU
Most recently used Least recently used
Exact LRU
Crude LRU
8-bit count
pages in order of last reference
N categories
2 categories (roughly)
256 categories
pages referenced since the last page fault
pages not referenced since the last page fault
. . .
0
1
2
3
254
255
Keep 8-bit counter for each page in a table in memory
34

Approximate LRU
Interval 1 Interval 2 Interval 3 Interval 4 Interval 5
00000000
00000000
10000000
01000000
10100000
00000000
10000000
01000000
 Algorithm
 At regular interval, OS shifts reference bits (in PTE) into
counters (and clear reference bits)
 Replacement: Pick the page with the “smallest counter”
 How many bits are enough?  In practice 8 bits are quite good
 Pros: Require one reference bit, small counter/page
 Cons: Require looking at many counters (or sorting) 35
10100000
01010000
10000000
11000000
11100000
01110000
00111000
00000000
00000000
00000000
10000000
01000000

Implementing LRU: software
 A doubly linked list of pages
 Every time page is referenced, move it to the
front of the list
 Page replacement: remove the page from back of list
 Avoid scanning of all pages  Problem: too expensive
 Requires 6 pointer updates for each page reference info
 High contention on multiprocessor
36

Not Recently Used (NRU)
 Algorithm
 Randomly pick a page from the following (in this order)
 Not referenced and not modified  Not referenced and modified
 Referenced and not modified
 Referenced and modified
 Pros
 Easy to implement
 Cons
 No frequencyNot very good performance  Takes time to classify
37

Page replacement algorithms: Summary
 Optimal  FIFO
 Random
 Approximate LRU (NRU)
 FIFO with 2nd chance
 Clock: a simple FIFO with 2nd chance
38

Related Posts