Page replacement algorithms

OS 2009-10

When a page fault occurs

2

OS has to choose a page to evict from memory If the page has been modified, the OS has to schedule

a disk write of the page The Th page j just t read d overwrites it a page i in memory ( (e.g. 4Kbytes) Clearly, Clearly its it s better not to pick a page at random Same problem applies to memory caches

OS 2009-10

Benchmarking
3

Tests are done by y generating g gp page g references ( (either

from real code or random) Sequences of page numbers (no real address, no offset) Example:

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
OS 2009-10

Optimal page replacement

4

At the moment of page fault: Label each page in memory is labeled with the number of instructions that will be executed before that page is first referenced Replace the page with the highest number: i.e. postpone as much as possible the next page fault Nice Nice, optimal, optimal but unrealizable The OS cant look into the future to know how long itll take to reference every page again

OS 2009-10

Example: optimal
5

Sequence

PF

6 page faults

OS 2009-10

Beladys anomaly
6

Try this sequence

With 3 page frames With 4 page frames With FIFO, with the optimal algorithm, (later) with the LRU

OS 2009-10

Not recently used algorithm

7

Use Referenced and Modified bits R&M are in hardware, potentially changed at each

reference to memory

R&M are zero when process is started

On clock interrupt the R bit is cleared On page fault, to decide which page to evict: Classify:
Class 0 R=0,M=0 Class 1 R=0,M=1 Class 2 R=1,M=0 Class 3 R=1,M=1

Replace a page at random from the lowest class

OS 2009-10

FIFO replacement
8

FIFO, , first in first out for pages p g Clearly not particularly optimal It might g end up p removing gap page g that is still

referenced since it only looks at the pages age Rarely used in pure form

1 Next removal
OS 2009-10

Latest load

Example (FIFO)
9

Sequence

PF

12 page faults

OS 2009-10

Second chance algorithm

10

Like FIFO but Before throwing out a page checks the R bit: If 0 remove it If 1 clear it and move the page to the end of the list (as it were just been loaded) If all pages have R R=1 1, eventually the algorithm degenerates to FIFO (why?)

1
OS 2009-10

2 Latest load

Clock page algorithm

11

Like second second chance chance but implemented differently: Check starting g from the latest visited page More efficient: doesnt doesn t have to move lists entries all the time

a h g f

b c d e

OS 2009-10

Least recently used (LRU)

12

Why: pages recently used tend to be used again

soon (on average)

List i of f all ll pages i in memory ( (most recently l i in the h

head, least recently used in the tail) List update at each memory reference! List operations are expensive (e.g. find a page)
So, difficult

OS 2009-10

Least recently used (LRU)

13

Idea! Get a counter, maybe a 64bit counter The counter is incremented after each instruction

and stored into the page entry at each reference Store the h value l of f the h counter i in each h entry of f the h page table (last access time to the page) When is time to remove a page, page find the lowest counter value (this is the LRU page)
Nice & good but expensive: it requires dedicated

hardware

OS 2009-10

Example LRU
14

Sequence

PF 9 page faults

OS 2009-10

NFU algorithm
15

Since LRU is expensive p NFU: Not Frequently Used algorithm At each clock interrupt p add the R bit to a counter for

each page: i.e. count how often a page is referenced Remove page with lowest counter value Unfortunately, this version tends not to forget anything

OS 2009-10

Aging (NFU + forgetting)

16

Take NFU but At each clock interrupt: Right g shift the counters (divide by y 2) Add the R bit to the left (MSB) As for NFU remove pages with lowest counter Note: this is different from LRU since the time

granularity is a clock tick and not every memory reference!

OS 2009-10

NFU+ageing
17

OS 2009-10

Process behavior
18

Locality of reference: most of the time the last k

references are within a finite set of pages < a large address space The set of pages a process is currently using is called the working set (WS) of the process Knowing g the working g set of p processes we can do very y sophisticate things (e.g. pre-paging) Pre-paging: load pages before letting the process to run so th that t th the page-fault f lt rate t i is l low, also, l if I k know the WS when I swap the process then I can expect it to be the same in the future time when I reload the process in memory
OS 2009-10

Working set
19

Working set

k-most-recent memory references

OS 2009-10

WS based algorithm
20

Store execution time information in the table

entries (storing reference is too expensive!) At clock interrupt handle R bits as usual (clear them) At page fault, scan entries:
If R=1 just store current time in the entry If R=0 compute current-last time page was referenced and if > threshold the page can be removed since its it s no longer in the working set (not used for threshold time)

Note: were using g time rather than actual

memory references

OS 2009-10

e.g.: WS based algorithm

21

OS 2009-10

WSClock algorithm
22

Use the circular structure (as seen earlier) At page fault examine the page pointed by the handle R=1, page in the WS dont remove it (set R to zero) R=0, R=0 M=0 no problem (as before, before check age age, page clean

and decide depending on age) If M=1, schedule disk write appropriately to procrastinate as long l as possible ibl a process switch it h

If return to starting point, then one page will eventually be clean (maybe after a context switch) S h d li multiple Scheduling l i l di disk k write i can b be efficient ffi i i in efficient ffi i systems (with disk scheduling and multiple disks) No write is schedulable (R=1 always), just choose a clean page N clean No l page, use s th the current t page under d th the h handle dl

OS 2009-10

WSClock
23

R=1

R=0

OS 2009-10

Summary
24 Algorithm
Optimal NRU (Not recently used) FIFO Second chance Clock LRU (Least Recently Used) NFU Aging Working set WSClock
OS 2009-10

Comment
Not implementable, useful for benchmarking Very crude Might throw out important pages Big improvement over FIFO Realistic (better implementation) Excellent but difficult to implement Crude approx to LRU Efficient in approximating LRU Expensive to implement Good and efficient

25

Design issues

OS 2009-10

Design issues
26

Local vs. g global allocation p policy y When a page fault occurs, whose page should the OS evict? Which process should get more or less pages? Monitor the number of page faults for every process (PFF page fault frequency) For many page replacement algorithms algorithms, the more pages the less page faults

OS 2009-10

Page fault behavior

27

Page e faults/sec c

Thrashing

Optimal (fair to others)

Too many pages

Number of page frames assigned

OS 2009-10

Load control
28

If the WS of all p processes > memory, y, theres

thrashing E.g. the PFF says a process requires more memory but none require less Solution: swapping swap a process out of memory and d re-assign i it its pages t to others th

OS 2009-10

Page size
29

Page g size p, n p pages g of memory y Average process size s, in pages s/p Each entry in the page table requires e bytes On average p/2 is lost (fragmentation) Internal fragmentation: how much memory is not

used within pages Wasted memory: p/2 + se/p Minimizing it yields the optimal page size (under simplifying p y g assumptions) p )
OS 2009-10

Two memories
30

Separate p data and p program g address spaces p Two independent spaces, two paging systems The linker must know about the two address spaces p

OS 2009-10

Other issues
31

Shared p pages, g , handle shared p pages g ( (e.g. g p program g

code)

Sharing data (e.g. shared memory)

Cleaning policy Paging algorithms work better if there are a lot of free pages available il bl Pages need to be swapped out to disk Paging daemon (write pages to disk during spare time and evict pages if there are to few)

OS 2009-10

Page fault handling

32
1. Page fault, the HW traps to the kernel 1 1. Perhaps registers are saved (e.g. (e g stack) 2. Save general purpose microprocessor information (registers, PC, PSW, etc.) 3. The OS looks for which page caused the fault (sometimes this information is 4 4. 5. 6 6. 7. 8. 8 9.

already somewhere within the MMU) The system checks whether the process has access to the page (otherwise a protection fault is generated, and the process killed) The OS looks for a free page frame, if none is found then the replacement algorithm is run If the selected page is dirty (M=1) (M 1) a disk write is scheduled (suspending the calling process) When the page frame is clean, the OS schedules another transfer to read in the required page from disk When the load is completed, completed the page table is updated consequently The faulting instruction is backed up, the situation before the fault is restored, the process resumes execution

OS 2009-10

33

Segmentation

OS 2009-10

Why?
34

Many separate address spaces (segments) (e.g. data, stack,

code, d and d many others h if needed) d d) Each segment is separate (e.g. addresses from 0 to some MAX) ) Segments might have different lengths Segment number + address within segment Li ki is Linking i simplified i lifi d (libraries (lib i within ithi diff different t segments t can assume addresses starting from 0) e.g. if a part of the libraries is recompiled the remainder of the code is unaffected ff t d Shared library (DLLs) implementation is simpler (the g is simpler) p sharing

OS 2009-10

Comparing paging and segmentation

35
Consideration
Need the programmer be aware that this technique is being used? How many linear address spaces are there? Can the total address space exceed the size of physical memory Can procedures and data be distinguished and separately protected? Can tables whose size fluctuate be accommodated easily? Is sharing I h i of f procedures d between b t users facilitated? Why was this technique invented? No

Paging
Yes

Segmentation

1 Yes No

Many Yes Yes

No N No To get a large linear address space without having to buy more physical y memory

Yes Y Yes To allow programs and data to be broken up into logically independent p and to aid sharing g address spaces and protection

OS 2009-10

Pure segmentations
36

Operating system

Operating system

Operating system

Operating system

OS 2009-10

Fragmentation
37

External fragmentation: Memory fragments not used (weve already seen this) Memory wasted in unused holes

OS 2009-10

Segmentation + paging (Pentium)

38

16K segments g 1G 32bit words (DoubleWords) Two tables: LDT, GDT Local (to the process) and

global (to the processor) descriptor table To work with a segment g the machine loads the segment number into a special register (CS, DS, etc.) CS, DS are 16 bit registers The descriptor of the segment (see next slide)

OS 2009-10

The segment descriptor

39

This is used by the microcode within the Pentium

to work with segments

Limit in pages/bytes 16/32 bit segment Privilege level
DPL S Type Limit 0-15 Base 16-23

Segment type protection

Base 24-31

Limit 16-19

Base 0-15

8 bytes

Page size is 4K

System/application Segment present in memory Limit (20 bits)

CS/DS
OS 2009-10

I d Index

G/L

P i il Privilege

Selector

Getting the address

40

Selector

Offset

Base address Limit Oth fi Other fields ld

Descriptor 32 bit linear address 32-bit

OS 2009-10

Paging on the Pentium

41

2-level p page g table in memory y

10 bits
Dir

10 bits
Page Offset

12 bits

1023

1023 5 4 3 1023 5 4 3 2 1 0 1023 5 4 3 2 1 0 1023 5 4 3 2 1 0 1023 5 4 3 2 1 0

Address to the page

Dir

5 4 3 2 1 0

Page

2 1 0

Offset

Each points to 4Mbytes of pages

OS 2009-10

More on the Pentiums

42

TLB, , to avoid repeated p accesses to memory y The whole thing can be used with just a single

segment to obtain a linear 32bit address space Set base and limit appropriately Protection (a few bits)

OS 2009-10