1 of 24

CSE 451

Operating Systems

L19 - Page Replacement,

Storage

Slides by: Tom Anderson

Rohan Kadekodi

2 of 24

MIN, LRU, LFU

MIN (optimal for page faults)

Replace the cache entry that will not be used for the longest time into the future
Optimality proof: if evict an entry used sooner, that will trigger an earlier cache miss

Least Recently Used (LRU)

Replace the cache entry that has not been used for the longest time in the past
Approximation of MIN

Least Frequently Used (LFU)

Replace the cache entry used the least often (recently)
Better than LRU when usage pattern is based on popularity, not history

Towards the end of the last lecture, we discussed about the different page replacement policies.

Specifically, the more popular policies, used in real, are the MIN, LRU, LFU.

Can anyone remind me what is the MIN policy? LRU? LFU?

We will learn an interesting anomaly w.r.t. these policies, called the Belady’s anomaly.

Basically, intuitively, given a certain number of page accesses, if you increase the number of page frames in which you can fit your pages (i.e., increase the memory size), then intuitively, you should be incurring fewer number of page faults. Does that make sense? Intuitively, it just means that you have more slots available overall, in which you can fit the same number of pages.

However, interestingly, this only holds true for MIN, and LRU. Breaks for FIFO, LFU. LFU: 3 frames vs 4 frames, 6 pages (A,B,C,D,.....,E,F,E,F,E,F,...)

3 of 24

Belady’s Anomaly

4 of 24

Question

How accurately do we need to track the least recently/least frequently used page?

If miss cost is low, any approximation will do

Hardware caches

If miss cost is high but number of pages is large, any not recently used page will do

Main memory paging with small pages

If miss cost is high and number of pages is small, need to be precise

Main memory paging with superpages

The question here is, now that we know the LRU algorithm, how do we implement it?

Basically, asking the question, what is the LRU page, is not a simple question to answer.

You could implement LRU, if, every time a page is accessed, I moved that page to the front of a list of pages. Then the page at the end of the list would be the least recently used page.

However, in software, I do not get control on every page reference. Doing that would require me to page fault on every page reference, which is too costly.

The only thing I am getting is that the hardware on a page reference, sets the accessed bit, saying it was accessed, without telling the software anything.

Can we build something that can be an approximation for LRU based on this hardware bit set?

How accurately do we need to track LRU. If miss cost is low, which means it is easy to kick something out, and bring it in, then I don’t need to care about what algorithm, any approximation will do. Like hardware cache, cost is low.

If miss cost is high and #pages is large, then large number of not very recently used pages. Just find a not recently used page, don’t need to find least recently used. Some not recently used page is good enough.

What is the likelihood that page is going to be used in near future, then you can somehow sort based on the accessed bit, and then take a page to be evicted from the tail of the distribution.

The pages that are hot / recently used, don’t evict. Then evict anything.

If you are in a world when miss cost is high and you have a lot of memory pressure, then you need to be precise. Find out which page is the best one. some approx algorithm might not be good enough.

Example, superpages, cost is high.

5 of 24

Clock Algorithm: Estimating LRU

Hardware sets use bit
Periodically, kernel sweeps through all physical page frames
If page is unused (by any process), reclaim

After flushing changes to disk

If page is used, mark as unused
Downside: modern servers can have 100M+ physical page frames

What algorithms do people use in practice?

One very old algo: clock algorithm.

Basic idea, you take all page frames, and you put them in a clock format, or just a list.

The hardware on a page access, sets the accessed bit of each page frame.

Then, in the software, you can periodically sweep through all the physical page frames, and look at their used bits.

If the used bit is 0, which means it wasn’t accessed since the last time you checked, reclaim it, by flushing data to disk.

If used bit is 1, clear the used bit, but do not reclaim.

So then the next time I again scan through the entire physical memory, if the used bit for this page 0, I just assume that it has not been recently used, then I will reclaim it.

Otherwise, again if it was used, I again mark it to 0, and don’t reclaim it.

Note that all is is being done in the background thread in the kernel, while program is running, so these bits may be changed by the hardware after we check, in which case we catch them in the next time we sweep.

Note thaat this clock goes through all page frames, hardware sets A bit in page table entries, pointing to page frame. So in the sweep, for each page frame, we look at all page table entries pointing to it, check their use bits, and then determine whether page was recently used.

6 of 24

Second Chance List

Periodically sweep through all page frames

if (page is dirty) {

flush to disk, mark page as clean, unused

} else if (page is used) { mark page as unused

} else {

mark as invalid; put at end of “second chance” list

if page is referenced, pull off “second chance” list, mark

page as valid

}

If need page, pull off front of second chance list

7 of 24

Recap

MIN is optimal

replace the page or cache entry that will be used farthest into the future

LRU is an approximation of MIN

For programs that exhibit spatial and temporal locality

Clock/Second Chance is an approximation of LRU

Bin pages into sets of “not recently used”

8 of 24

Working Set Model

Working Set: set of memory locations that need to be cached for reasonable cache hit rate
Thrashing: when system has too small a cache

There’s one final concept that I need to add to this.

Notion of: what is the rate of page faults that occur as a function of the number of page frames in my system.

Belady’s anomaly: increase page frames, increased page faults. Real systems: use LRU, doesn’t happen

Increase page frames, fewer page faults.

Looking at this from a cache point of view, not page frames.

If I had a cache that is 16KB of size, then how does the cache hit rate change as a function of the cache size.

I can replace this with page frames, on x-axis.

So ideally, if your memory size is the number of pages you access, you have no page faults or page misses, get hit rate of 100%.

There is a knee to the curve, which is the most effective strategy for cache size versus hit rate, after which you have diminishing returns.

If you are too low on the curve, below the knee, too small a cache, we end up with thrashing. System spends a lot of time doing page faults for cache misses.

This curve is just for a sample program, the shape of the curve and the slope may look different for different programs.

9 of 24

Phase change behavior

10 of 24

Question

What happens to system performance as we increase the number of processes?

If the sum of the working sets > physical memory?

# progs

Hit rate

11 of 24

Storage and File Systems

12 of 24

Main Points

Survey of physical storage hardware devices

SRAM, DRAM, Flash, magnetic disk

File systems

Useful abstraction on top of physical devices

File system usage patterns

Small files and large files are both commonplace

13 of 24

Volatile Memory: SRAM and DRAM

Individual word (8 byte) and cache line (64 byte) access
Data degrades without power; power proportional to storage capacity
Bit density scales with Moore’s Law
Static RAM (SRAM)

Typical uses: CPU registers, on chip cache, I/O device caches
Data stored in a transistor flip/flop
Access latency range: 1 – 20ns (smaller caches => faster)

Dynamic RAM (DRAM)

Typical use: main memory (8GB/chip with DDR5, usually sold as an array of chips)
Data stored in a capacitor, 2D/3D array for dense packing
Data degrades even when powered; bits need periodic refresh
Access latency: 50 - 100 ns

Tiered DRAM (CXL)

Rack-level extension to server DRAM (cache coherent, PCI)
Access latency: 300 ns

2 things about what we talked about today and the last couple of classes is Volatile Memory.

What technologies are used for volatile memory?

Volatile: turn power off, data goes away.

DRAM and SRAM are technologies for volatile memory. THey store data, but turn off power, bits disappear.

One type of memory: SRAM, used for processor caches.

In SRAM, transistor for every bit.

What DRAM does is that it uses a capacitor for every bit. Different technology. The fabrication facilities for SRAM and DRAM are different, completely different. Don’t share the two on individual chips.

DRAM = design a system for high density of bits per silicon. You are trying to pack bits as efficiently as possibly. One property of capacitor, compared to flip/flop. if as long as the system is powered, flip/flop is not using additional power to keep flip/flop charged relatively. Consequence: SRAM in static use (not reading/writing), not as much power is used, compared to DRAM.

DRAM: capacitor, charge degrades over time, loses data it has in it. Requires active refresh. Fair amount of power in datacenter, is active refresh in DRAM opposed to doing computing – to keep bits live in DRAM of system.

Important: DRAM and SRAM, you can address individual words, read/write individual words / cachelines in DRAM/SRAM. Unit of reading = arbitrary. Selectively read/write particular flip/flop. This is not true for storage.

Additional thing called tiered DRAM (new) called CXL, you put additional DRAM in a separate server. and connect it to your server for increased capacity.

14 of 24

Persistent Memory: Flash and Magnetic Disk

Block level (4KB) access (or larger); asynchronous request queues
Data valid even when unpowered
NAND Flash/Solid State Drive (SSD)

Bits stored in special silicon gate, densely packed in 2-D or 3-D array
10-50 us block level random read/write
Each block can only be written once, but can be erased
Limited number of erasures per physical block (10K depending on type)
Typical use: smartphones, laptops, servers, data centers

Magnetic “hard” disk drive (HDD)

Bits stored on magnetic surface: 1.5 Tbit per square inch
Physical motion (spinning disk) needed to read bits off surface
10 ms random access latency; 250MB/s max throughput
Typical use: data center bulk storage, backup

For persistent Memory, two alternatives.

Almost all have used both of it, whether you know or not.

If you have a backup system at home, almost all are Hard disks.

Almost all storage in laptops / phones are flash.

First we will talk about flash, then magnetic disks where we talk about backup.

In cloud you have a mixture of the two: some flash, some disks.

Servers in lab, local hard disk in them. Flash is more expensive per byte. If you want cheap, Hard disk, if you want something lightweight (cell-phone) you generally use flash.

Both of these are block-level operations: you read / write in a block, usually 4KB. Can be as small as 512B, generally page size that people use.

What if I only wanted little bit, to write few bytes, read old data in memory, update it, write the data back to disk.

1st part: how does flash work? Essentially, instead of storing those bits as a capacitor, or as a flip/flop, they are stored in a specially constructed thing that retains state even when turned off.

The block-level accesses are in the range of 10-50 microseconds - much much slower. SRAM is 1 ns per operation, DRAM = 100ns per operation, Tiered DRAM = 200 ns. This is couple of order of magnitude slower.

Page fault, go to disk, wildly expensive.

Magnetic disk, orders of magnitude even slower than flash.

15 of 24

5

[J. McCallum, jcmit.org]

DRAM

Flash

Disk

Graph over time of memory price per MB, and time on x-axis.

1955 to now.

Let’s look at trends – 3 lines.

DRAM, Flash, Disk.

Note the log-scale on the y-axis.

What this implies is that over time, exponential improvement in disk cost / capacity for all 3 technologies.

That exponential rate changed over time.

Disk: improving at exponential, still improving, but slower.

Flash, has been improving fast rate, slowing little bit.

DRAM is now much slower improvement.

Difference in cost of DRAM vs Flash = 30x, Flash vs Disk = 3x.

You can see that they are not smooth, some times DRAM is very expensive, sometimes not. Right now for example, expensive. Large scheme of things, not super important. DRAM chip shortage causes these blips.

Over time people get better at building these things, there is more competition, production is more streamlined. hardware gets cheaper.

It is unclear if you look 10 years from now, if Flash and Disk will converge. Flash has huge advantages. If converge, people will stop buying disks.

16 of 24

Flash Memory

17 of 24

Flash Memory Challenge

Writes must be to “clean” cells

Erasure required before block can be rewritten
Erasure is 20x slower than single block read/write
Erasure needs empty guard regions to avoid erasing useful data in nearby blocks
Limited number of erasures per physical block (10-35K for MLC, 1K for QLC)

Solutions?

18 of 24

Managing Wearout

Each flash block can only be written limited number of times

Depends on encoding: 1000 (QLC), 10-35K (MLC), 100K (SLC)

What if app repeatedly updates the same physical block?

1ms per write/erase cycle
Assume 10K write/erase cycles before wearout

⇒ Wearout (of one block) in 10 seconds !

⇒ Disk keeps getting smaller over time…

=> Can’t allow update in place

19 of 24

Flash Translation Layer (FTL)

Disk firmware exports a virtual block interface

Read/Write/Trim (block delete)

Firmware relocates each virtual block to physical location as needed

Overwrite to a previously written block goes to new empty location
Reads to the newly written block are redirected to its new location
Previous block is stale, unused, ready for erasure (reuse for other block writes)

Like putting the block into the trash - device firmware can still read the old data (until erasure)

FTL needs a map from virtual block # to physical location

Stored in SRAM for fast lookup
Written back to SSD on power failure (battery, capacitor)

20 of 24

FTL in Picture Form

Eventually we’ll run out of space…

21 of 24

Erasures

Erase many blocks at a time (erasure region)

Multi-block erasure region is always erased together at same time
Minimizes wasted area/density due to guard regions

Guard per multi-block erasure region

Prorate time spent erasing over more blocks

Device still appears to read/write individual 4KB blocks

Number of blocks in erasure region is an internal value, not visible to customers
Tens to hundreds 4KB blocks per erasure region

What if some of the data in the erasure region is still live?

Where do we put that data during the erasure?

22 of 24

FTL Compaction

23 of 24

Efficient Compaction

24 of 24

Wear Levelling

Each block can only be written a maximum number of times

FTL tracks # of erase/write cycles for each block
Unmap blocks if they can’t hold new data

To keep from losing blocks due to wear out

Write new data into regions with fewer update cycles
Put data that won’t change in blocks that are near the end of their lifetime