08-Virtual Memory

1 .Operating Systems 1 8. Virtual Memory 8.1 Principles of Virtual Memory 8.2 Implementations of Virtual Memory Paging Segmentation Paging With Segmentation Paging of System Tables Translation Look-aside Buffers 8.3 Memory Allocation in Paged Systems Global Page Replacement Algorithms Local Page Replacement Algorithms Load Control and Thrashing Evaluation of Paging

2 .Operating Systems 2 Principles of Virtual Memory For each process, the system creates the illusion of large contiguous memory space(s) Relevant portions of Virtual Memory (VM) are loaded automatically and transparently Address Map translates Virtual Addresses to Physical Addresses

3 .Operating Systems 3 Principles of Virtual Memory Every process has its own VM Single-segment VM: One area of 0..n-1 words Divided into fix-sized pages Multiple-Segment VM: Multiple areas of up to 0..n-1 (words) Each holds a logical segment (e.g., function, data structure) Each logical segment may be contiguous , or may be divided into pages

4 .Operating Systems 4 Main Issues in VM Design Address mapping How to translate virtual addresses to physical addresses Placement Where to place a portion of VM needed by process Replacement Which portion of VM to remove when space is needed Load control How much of VM to load at any one time Sharing How can processes share portions of their VMs

5 .Operating Systems 5 Paged Virtual Memory VM is divided into fix-sized pages : page_size = 2 |w| PM (physical memory) is divided into 2 |f| page frames : frame_size = page_size = 2 |w| Virtual address: va = ( p,w ) Physical address: pa = ( f,w ) | p| determines number of pages in VM, 2 |p| |f| determines number of frames in PM, 2 |f| |w| determines page/frame size , 2 |w| System loads pages into frames and translates addresses

6 .Operating Systems 6 Paged VM Address Translation How to keep track of loaded pages and translate addresses ?

7 .Operating Systems 7 Paged VM Address Translation One solution: Frame Table : One entry, FT[i] , for each frame records which page it contains FT[i]. pid records process ID FT[i].page records page number p Address translation: Given ( id,p,w ) , search for FT[f] where ( id,p ) matches if matching entry is found then index f is frame number pa = f + w;

8 .Operating Systems 8 Address Translation via Frame Table Drawbacks Costly : Search must be done in parallel in hardware Sharing of pages: not possible

9 .Operating Systems 9 Address Translation via Page Table Page Table (PT) one for each VM (not PM) Think of PT as array: PT[p]=f p age p resides in frame f Implementation: PT register points at PT at run time Address translation: pa = *( PTR+p )+w; Drawback: Extra memory access

10 .Example: address translation Assume: page size = 512 words |VA| = 32 bits |PA| = 24 bits Translate the following virtual addresses to physical: 512, 30, 1024 Operating Systems 10 Page# Frame# 0: 8 1: 4 2: 0 … …

11 .Operating Systems 11 Demand Paging All pages of VM loaded initially Simple, but maximum size of VM = size of PM Pages are loaded as needed: on demand Additional bit in PT shows presence/absence in memory Page fault occurs when page is absent OS is invoked: If there is a free frame: load page, update PT If none available: replace one (which one? – replacement policy) save replaced page (if modified) load new page, update PTs

12 .Operating Systems 12 VM using Segmentation Multiple contiguous spaces: segments More natural match to program/data structure Easier sharing (Chapter 9) Virtual addresses ( s,w ) must be translated to physical addresses pa (but no frames) Where/how are segments placed in physical memory? Contiguous Paged

13 .Operating Systems 13 Contiguous Allocation Each segment is contiguous in physical memory Segment Table (ST) records starting locations Segment Table Register STR points to ST Address translation: ( s,w ) pa = *(STR+s)+w; Drawbacks : Extra memory reference Must also check for segment length |w| is only the maximum segment length External fragmentation (variable partitions)

14 .Operating Systems 14 Paging with segmentation To have multiple segments and fixed partitions : each segment is divided into pages va = ( s,p,w ) |s| : # of segments (size of ST) |p| : # of pages per segment (size of PT) |w| : page size pa = *(*(STR+s)+p)+w Drawback: 2 extra memory references

15 .Operating Systems 15 Paging of System Tables ST or PT may be too large to keep in PM Divide ST or PT into pages Keep track by additional table Paging of ST ST divided into pages Segment directory keeps track of ST pages va = (s1,s2,p,w) pa=*(*(*(STR+s1)+s2)+p)+w Drawback: 3 extra memory references

16 .Operating Systems 16 Translation Look-aside Buffer TLB avoids some memory accesses Keep most recent address translations in associative memory: ( s,p ) | f Bypass translation if match on ( s,p ,*) If no match, replace one entry TLB ≠ cache TLB keeps frame #s Cache keeps data values

17 .Operating Systems 17 Memory Allocation with Paging Placement policy: Any free frame is OK Replacement : There are many algorithms Main goal: minimize data movement between physical memory and secondary storage How to compare different algorithms: Count number of page faults Use Reference String (RS) : r 0 r 1 ... r t … r t is the (number of the) page referenced at time t Two types of replacement strategies: Global replacement: Consider all resident pages, regardless of owner Local replacement: Consider only pages of faulting process

18 .Operating Systems 18 Global page replacement Optimal (MIN) : Replace page that will not be referenced for the longest time in the future Time t | 0| 1 2 3 4 5 6 7 8 9 10 RS | | c a d b e b a b c d Frame 0| a| a a a a a a a a a d Frame 1| b| b b b b b b b b b b Frame 2| c| c c c c c c c c c c Frame 3| d| d d d d e e e e e e IN | | e d OUT | | d a Problem: Need entire reference string (i.e., need to know the future )

19 .Operating Systems 19 Global Page Replacement Random Replacement : Replace a randomly chosen page Simple but Does not exploit locality of reference Most instructions are sequential Most loops are short Many data structures are accessed sequentially

20 .Operating Systems 20 Global page replacement First-In First-Out (FIFO) : Replace oldest page Time t | 0| 1 2 3 4 5 6 7 8 9 10 RS | | c a d b e b a b c d Frame 0|>a|>a >a >a >a e e e e >e d Frame 1| b| b b b b >b >b a a a >a Frame 2| c| c c c c c c >c b b b Frame 3| d| d d d d d d d >d c c IN | | e a b c d OUT | | a b c d e Problem: Favors recently accessed pages, but Ignores when program returns to old pages

21 .Operating Systems 21 Global Page Replacement LRU : Replace Least Recently Used page Time t | 0| 1 2 3 4 5 6 7 8 9 10 RS | | c a d b e b a b c d Frame 0| a| a a a a a a a a a d Frame 1| b| b b b b b b b b b b Frame 2| c| c c c c e e e e e d Frame 3| d| d d d d d d d d c c IN | | e c d OUT | | c d e Q.end | d| c a d b e b a b c d | c| d c a d b e b a b c | b| b d c a d d e e a b Q.head | a| a b b c a a d d e a

22 .Operating Systems 22 Global page replacement LRU implementation Software queue : too expensive Time-stamping Stamp each referenced page with current time Replace page with oldest stamp Hardware capacitor with each frame Charge at reference Charge decays exponentially Replace page with smallest charge n -bit aging register with each frame Shift all registers to right periodically Set left-most bit of referenced page to 1 Replace page with smallest value Simpler algorithms that approximate LRU algorithm

23 .Operating Systems 23 Global Page Replacement Second-chance algorithm Approximates LRU Implement use-bit u with each frame Set u=1 when page referenced To select a page: if u==0 , select page else, set u=0 and consider next frame Used page gets a second chance to stay in memory

24 .Operating Systems 24 Global page replacement Second-chance algorithm … 4 5 6 7 8 9 10 … b e b a b c d … >a/1 e/1 e/1 e/1 e/1 >e/1 d/1 … b/1 >b/0 >b/1 b/0 b/1 b/1 >b/0 … c/1 c/0 c/0 a/1 a/1 a/1 a/0 … d/1 d/0 d/0 >d/0 >d/0 c/1 c/0 … e a c d

25 .Operating Systems 25 Global Page Replacement Third-chance algorithm Second chance algorithm does not distinguish between read and write access write access is more expensive Give modified pages a third chance: use-bit u set at every reference (read and write) write-bit w set at write reference to select a page, cycle through frames, resetting bits, until uw ==00 : u w  u w 1 1 0 1 1 0 0 0 0 1 0 0 * (remember modification) 0 0 (select page for replacement)

26 .Operating Systems 26 Global Page Replacement Third-chance algorithm Read → 10 → 00 → Select Write → 11 → 01 → 00* → Select … 0 | 1 2 3 4 5 6 7 8 9 10 . … | c a w d b w e b a w b c d . >a/10 |>a/10 >a/11 >a/11 >a/11 a/00* a/00* a/11 a/11 >a/11 a/00* … b/10 | b/10 b/10 b/10 b/11 b/00* b/10* b/10* b/10* b/10* d/10 … c/10 | c/10 c/10 c/10 c/10 e/10 e/10 e/10 e/10 e/10 >e/00 … d/10 | d/10 d/10 d/10 d/10 >d/00 >d/00 >d/00 >d/00 c/10 c/00 . … IN | e c d … OUT | c d b

27 .Operating Systems 27 Local Page Replacement Measurements indicate that every program needs a minimum set of pages to be resident in memory If too few , thrashing occurs (program spends most of its time loading/saving pages) If too many , page frames are wasted Goal: maintain an optimal set of pages for each process in memory Size of optimal set changes over time Optimal set must be resident

28 .Operating Systems 28 Local Page Replacement Optimal (VMIN) Define a sliding window (t, t+ )  is a parameter (constant) At any time t , maintain as resident all pages visible in window Guaranteed to generate minimum number of page faults Requires knowledge of future

29 .Operating Systems 29 Local page replacement Optimal (VMIN) with =3 Time t | 0| 1 2 3 4 5 6 7 8 9 10 RS | d| c c d b c e c e a d Page a | -| - - - - - - - - x - Page b | -| - - - x - - - - - - Page c | -| x x x x x x x - - - Page d | x| x x x - - - - - - x Page e | -| - - - - - x x x - - IN | | c b e a d OUT | | d b c e a Unrealizable without entire reference string (knowledge of future)