1 of 51

​

OS & Paging

CS-446/646

C. Papachristos

Robotic Workers (RoboWork) Lab

University of Nevada, Reno

2 of 51

OS & Paging

Remember: “Swapping”(/“Paging”)

​

“Swapping”(/“Paging”) from the OS perspective:

  • Pages are evicted –“Swapped(/Paged)-Out” – to Disk when Memory is full
  • Pages reloaded –“Swapped(/Paged)-In” – from Disk when referenced again
  • References to evicted Pages cause a TLB Miss
  • Page Table Entry indicates it is Invalid, an attempt to access triggers a Page Fault
  • OS Page Fault Handler executed, OS allocates a Physical Page Frame, reads Page from Disk
  • When I/O completes, the OS fills-in Physical Page Frame, marks it as Valid, and restarts the Faulting Instruction

​

Dirty vs Clean Pages

  • Actually, only Dirty (/Modified) Pages need to be written to Disk
  • Clean Pages do not – But we need to know where they are on Disk to read them again

CS446/646 C. Papachristos

3 of 51

OS & Paging

Restarting Fault-ing Instructions

​

  • Hardware provides Kernel with information about Page Fault
    • Page-Faulting Virtual Address (In %CR2 Register on x86 – e.g. would see it if modifying Pintos page_fault and use fault_addr)
    • Additional information about: PCID (if enabled)? Was the access a read or write? Was it an Instruction fetch? Was it caused by User-level access to Kernel-level mapped Memory?

​

  • Hardware must allow resuming after a Fault
    • Idempotent Instructions are easy to restart
      • e.g. simple load or store Instruction can be restarted immediately
      • Just re-execute any Instruction that only accesses one Address

​

    • Complex Instructions must be restarted, too
      • e.g. x86 movs (move string) Instruction
      • Specify src, dst, count in %esi, %edi, %ecx Registers
      • On Fault, CPU Registers adjusted to resume where move left off

CS446/646 C. Papachristos

4 of 51

OS & Paging

“Swapping”(/“Paging”) Challenges

​

1) How to resume a Process after a Fault?

  • Need to save State and restart

​

2) Page Replacement Policy

​

  • a) What to fetch (from Disk)?
    • Just needed Page or more?

​

  • b) What to evict?
    • How to allocate Physical Pages amongst Processes?
    • Which of a particular Process’ Pages to keep in Memory?
    • Poor choices can lead to horrible Performance

CS446/646 C. Papachristos

5 of 51

OS & Paging

Locality

​

  • All “Swapping”(/“Paging”) schemes employ the concept of Locality
    • Processes reference Pages in localized patterns

​

  • Temporal Locality
    • Concept: Locations referenced recently likely to be referenced again

​

  • Spatial Locality
    • Concept: Locations near recently referenced ones are likely to be referenced soon

​

  • Although the cost of “Swapping”(/“Paging”) is high, if it is infrequent enough it becomes acceptable
    • Processes usually exhibit both kinds of Locality during their execution, making “Swapping”(/“Paging”) practical

CS446/646 C. Papachristos

6 of 51

OS & Paging

Working Set Model (more later)

​

​

​

​

​

​

​

​

  • Disk much slower than Memory
    • Goal: Run mostly at Memory speed, don’t get throttled by Disk speed

​

  • “80/20 Rule”: 80% of Memory accesses happen on 20% of Memory
    • Keep the Hot 20% in Memory
    • Keep the Cold 80% on Disk

CS446/646 C. Papachristos

7 of 51

OS & Paging

Working Set Model (more later)

​

​

​

​

​

​

​

​

  • Disk much slower than Memory
    • Goal: Run mostly at Memory speed, don’t get throttled by Disk speed

​

  • “80/20 Rule”: 80% of Memory accesses happen on 20% of Memory
    • Keep the Hot 20% in Memory
    • Keep the Cold 80% on Disk

CS446/646 C. Papachristos

8 of 51

OS & Paging

“Swapping”(/“Paging”) Challenges (continued)

​

2-a) What to fetch?

​

  • Bring in Page that caused Page Fault

​

  • Pre-fetch surrounding Pages?
    • Reading two Disk Blocks approximately as fast as reading one
    • As long as no Track/Head switch needed, Disk Seek Time is what dominates
    • If application exhibits Spatial Locality, then big win to store and read multiple contiguous Pages

​

  • Note: Also Pre-Zero–ing of unused Pages in CPU Idle loop
    • Need 0-filled Pages for Stack, Heap, Anonymously mmapp()ed Memory
    • Zeroing them only on-demand is slower
    • Hence, many OSes will Pre-Zero freed Pages while CPU is Idle

CS446/646 C. Papachristos

9 of 51

OS & Paging

Page Replacement

​

2-b) What to evict?

​

  • When a Page Fault occurs, the OS loads the Faulted Page from Disk into a Page Frame of Physical Memory
  • At some point, the Process will have used all the Page Frames it is allowed to use
    • This is likely (much) less than all of available Memory
    • Remember: OS usually keeps a Pool of Free Pages around so that allocations do not immediately cause evictions
  • When this happens, the OS must replace a Page for each Page Faulted-In
    • It must evict a Page to free-up a Physical Page Frame

​

The Page Replacement Algorithm determines how this is done

  • Greatly affects performance of “Swapping”(/“Paging”)
    • Requires Virtual Memory Management
  • Also called the Page Eviction Policy

CS446/646 C. Papachristos

10 of 51

OS & Paging

Selecting Physical Pages

​

CS446/646 C. Papachristos

11 of 51

OS & Paging

First-In First-Out (FIFO) Page Replacement

​

  • Evict oldest fetched Page

​

  • Example: Page Referencing string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • 3 Physical Pages available: 9 Page Faults

CS446/646 C. Papachristos

Phys

Page

1

2

3

4

1

2

5

1

2

3

4

5

0

1

1

1

4

4

4

5

​

​

5

5

✔

1

​

2

2

2

1

1

1

✔

​

3

3

​

2

​

​

3

3

3

2

2

​

✔

2

4

​

12 of 51

OS & Paging

First-In First-Out (FIFO) Page Replacement

​

  • Evict oldest fetched Page

​

  • Example: Page Referencing string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • 4 Physical Pages available: 10 Page Faults

CS446/646 C. Papachristos

Phys

Page

1

2

3

4

1

2

5

1

2

3

4

5

0

1

1

1

1

✔

​

5

5

5

5

4

4

1

​

2

2

2

​

✔

2

1

1

1

1

5

2

​

​

3

3

​

​

3

3

2

2

2

2

3

​

​

​

4

​

​

4

4

4

3

3

3

13 of 51

OS & Paging

Belady’s Anomaly

​

  • More Physical Memory does not necessarily mean fewer Faults

CS446/646 C. Papachristos

14 of 51

OS & Paging

Optimal Page Replacement

​

  • What is Optimal (if we knew the future)?
    • Replace Page that will not be used for longest time in the future

​

  • Example: Page Referencing string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • 4 Physical Pages available: 6 Page Faults

CS446/646 C. Papachristos

Phys

Page

1

2

3

4

1

2

5

1

2

3

4

5

0

1

1

1

1

✔

​

1

✔

​

​

5

✔

1

​

2

2

2

​

✔

2

​

✔

​

2

​

2

​

​

3

3

​

​

3

​

​

✔

3

​

3

​

​

​

4

​

​

5

​

​

​

4

​

15 of 51

OS & Paging

Belady’s Algorithm

​

  • Known as the Optimal Page Replacement Algorithm
    • Rationale: The best Page to evict is the one never touched again
    • Never is a long time, so picking over a future Time Horizon is the next best thing
    • Proven by Belady

​

  • Problem: Have to be able to predict the future

​

  • Why is Belady’s Algorithm useful then? As a comparative metric
    • Compare implementations of Page Replacement algorithms with the Optimal to gauge room for improvement
      • If Optimal is not much better, then our Algorithm is pretty good
      • If Optimal is much better, then our Algorithm could use some work
        • Random Replacement Algorithm is often the lower-bound

CS446/646 C. Papachristos

16 of 51

OS & Paging

Least Recently Used (LRU) Page Replacement

​

  • “Estimate” Optimal via Least Recently Used (LRU)
    • Rationale: Because past often predicts the future
    • Evict the Page that has not been used for the longest time in the past

​

  • Example: Page Referencing string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • 4 Physical Pages available: 8 Page Faults

CS446/646 C. Papachristos

Phys

Page

1

2

3

4

1

2

5

1

2

3

4

5

0

1

1

1

1

✔

​

1

✔

​

1

1

5

1

​

2

2

2

​

✔

2

​

✔

2

2

2

2

​

​

3

3

​

​

5

​

​

5

4

4

3

​

​

​

4

​

​

4

​

​

3

3

3

17 of 51

OS & Paging

Least Recently Used (LRU) Page Replacement

​

  • “Estimate” Optimal via Least Recently Used (LRU)
    • Rationale: Because past often predicts the future
    • Evict the Page that has not been used for the longest time in the past

​

  • Example: Page Referencing string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
    • 4 Physical Pages available: 8 Page Faults

​

  • Problem 1: Can be pessimal
    • e.g. when looping over Memory, we actually want Most Recently Used (MRU) eviction

​

  • Problem 2: Implementation

CS446/646 C. Papachristos

18 of 51

OS & Paging

 

CS446/646 C. Papachristos

19 of 51

 

OS & Paging

CS446/646 C. Papachristos

20 of 51

 

OS & Paging

CS446/646 C. Papachristos

21 of 51

 

OS & Paging

CS446/646 C. Papachristos

22 of 51

 

OS & Paging

CS446/646 C. Papachristos

23 of 51

 

OS & Paging

CS446/646 C. Papachristos

24 of 51

 

OS & Paging

CS446/646 C. Papachristos

25 of 51

OS & Paging

CS446/646 C. Papachristos

 

26 of 51

OS & Paging

Other Page Replacement Algorithms

​

Random Eviction

  • Dirt-simple to implement
  • Not overly horrible (avoids Belady’s Anomaly & pathological cases)

​

Least Frequently Used (LFU)

  • Instead of just 1 Accessed bit, have a proxy count # of times each Page accessed
  • At the same time, decay usage counts over time (for Pages that fall out of usage)
    • Remember: count = (A << (n − 1)) | (count >> 1) ,and on sweep: count >>= 1

​

Most Frequently Used (MFU)

  • Rationale: Page with smallest count was probably just brought in and has yet to be used
  • Neither LFU nor MFU used very commonly

CS446/646 C. Papachristos

27 of 51

OS & Paging

“Swapping”(/“Paging”) Methods

​

Naïve Page Replacement:

    • 2 Disk I/Os per Page Fault

CS446/646 C. Papachristos

28 of 51

OS & Paging

“Swapping”(/“Paging”) Methods

​

Page Buffering

  • Idea: Reduce # of I/Os on the critical path

​

  • Use “Free Pool” – keep a Pool of Free Physical Page Frames
    • On Page Fault, still select victim Page to be Evicted
    • But read newly fetched Page into an already Free Physical Page Frame (from the “Free Pool”)
    • Can resume execution while writing-out victim Page
    • When done writing-out victim Page, add it to “Free Pool”

​

  • Allows to also yank Pages back from “Free Pool”
    • Contains only Clean Pages, but may still have their data (not Pre-Zero’ed yet)
    • If Page Faults on a Page that is still in the “Free Pool”, recycle it

CS446/646 C. Papachristos

29 of 51

OS & Paging

Fixed vs Variable Space

​

How to determine how much Memory to allow for each Process?

​

1) Fixed Space Algorithms

  • Each Process is given a fixed limit of Pages it can use
  • When it reaches the limit, it replaces from its own Pages
  • Local Replacement Policy
    • Some Processes may do well while others suffer

​

2) Variable Space Algorithms

  • Each Process’ set of Pages grows and shrinks dynamically
  • Global Replacement Policy
    • One Process could end up ruining it for the rest

CS446/646 C. Papachristos

30 of 51

OS & Paging

Working Set (WS) Model

​

  • A Working Set of a Process is used to model the Dynamic Locality of its

Memory usage

    • Defined by Peter Denning in 60s, published at the first SOSP Conference

​

Definition

  • 𝑊𝑆(𝑡, 𝑤) = {Pages P such that P was referenced in the time interval (𝑡-𝑤, 𝑡)}
  • 𝑡: time, 𝑤: Working Set window (measured in Page Refs)

​

  • I.e. a Page is in the Working Set (WS) only if it was referenced inside the last 𝑤 Page References

CS446/646 C. Papachristos

31 of 51

OS & Paging

Working Set (WS) Size

​

Definition

  • The # of unique Pages in the Process’ Working Set
    • The number of unique (grows, shrinks) Pages referenced in the interval (𝑡, 𝑡 − 𝑤)

​

  • The Working Set Size changes with program Locality
    • During periods of poor Locality, you reference more unique Pages
    • Within that period of time, the Working Set Size is larger

​

  • Intuitively, want the Working Set to be the set of Pages a Process needs to be Resident in Memory to prevent heavy Page-Faulting
    • Each Process has a param 𝑤 that determines a Working Set with few Page Faults
    • Denning: Don’t run a Process unless its Working Set exists/is restored in Memory

CS446/646 C. Papachristos

32 of 51

OS & Paging

Working Set (WS) Size

​

Example: gcc Working Set

CS446/646 C. Papachristos

33 of 51

OS & Paging

Working Set Problems

​

Problems

  • How do we determine Working Set window 𝑤 ?
  • How do we know when the Process’ Working Set changes, i.e. undergoes a “Phase Transition” ?

​

  • Too hard to answer
    • So, Working Set is not used in practice as a Page Replacement Algorithm

​

  • However, it is still used as an abstraction
    • The intuition is still valid
    • When people ask, “How much Memory does Firefox need?”, they are in effect asking for Firefox’s Working Set Size

CS446/646 C. Papachristos

34 of 51

OS & Paging

Working Set Changes across Phases

​

​

​

​

​

​

​

​

​

​

  • Working Set Size balloons across Phase transitions

​

​

CS446/646 C. Papachristos

35 of 51

OS & Paging

 

CS446/646 C. Papachristos

36 of 51

OS & Paging

An “Indirect” Approach: Page Fault Frequency (PFF)

​

  • Page Fault Frequency is a Variable Space Algorithm (to dynamically determine how many Pages of Memory are allowed to a Process) with a more ad-hoc approach

​

Definition

  • Page Fault Frequency (PFF) = Page Faults / Instructions executed
    • Monitor the Fault Rate for each Process
    • If the Fault Rate is above a high threshold, give it more Memory
      • So that it Faults less (but not always – e.g. FIFO, Belady’s Anomaly)
    • If the Fault Rate is below a low threshold, take away Memory
      • Expected to lead to more Faults (but not always)

​

  • But! Hard to use Page Fault Frequency to distinguish between changes in Locality and changes in Working Set Size
    • I.e. does the Process really actively need more “Hot” Memory to do its work? Or is it temporarily transitioning to working on a different Memory region?

CS446/646 C. Papachristos

37 of 51

OS & Paging

Thrashing

​

  • Page Replacement Algorithms avoid the problem of Thrashing

​

Thrashing

  • When OS spends most of its time Paging data back and forth to Disk

​

  • Little time spent doing useful work (Process progress)

​

  • In this situation, the system is Overcommitted
    • OS has no idea which Pages should be in Memory to reduce reoccurring Faults

CS446/646 C. Papachristos

38 of 51

OS & Paging

Reasons for Thrashing

​

  • Access pattern has no Temporal Locality
    • past ≉ future

​

​

  • “Hot” Memory does not fit in Physical Memory

​

​

​

  • Each Process fits individually, but too many for system

CS446/646 C. Papachristos

80/20 Rule has broken

39 of 51

OS & Paging

Thrashing & Multiprogramming

​

​

CS446/646 C. Papachristos

40 of 51

OS & Paging

Dealing with Thrashing

​

  • Approach 1): Working Set (WS)-based
    • Thrashing viewed from a caching perspective: Given Locality of References, how large of a cache does the Process need?

​

    • I.e. how much Memory does the Process need in order to make reasonable progress?
      • What is its Working Set Size, which needs to be estimated?
    • Only run Processes whose WS-inferred Memory requirements can be met

​

  • Approach 2): Page Fault Frequency (Remember: PFF = Page Faults / Instructions executed)
    • Thrashing viewed as poor ratio of fetching –to– actual work done

​

    • If Page Fault Frequency rises above a high threshold, Process needs more Memory
      • If not enough Memory on the system, “Swap-it-Out” (the Process)
    • If Page Fault Frequency sinks below a low threshold, Memory can be taken away

CS446/646 C. Papachristos

41 of 51

OS & Paging

 

CS446/646 C. Papachristos

42 of 51

OS & Paging

Complications of “Swapping”(/“Paging”)

​

  • Total available Memory
    • Some Physical Memory remains tied up by Kernel Virtual Memory structures

​

  • User/Kernel-Level crossings
    • More crossings into Kernel-Level may be triggered (to handle “Swapping-In/Out”)
      • Obviously can’t just kill a Process if a Page is not present – Might need to “Swap-it-In”
    • Pointers in System Call arguments must be checked (for Security & Reliability)

​

  • Inter-Process Communication (IPC)
    • Must apply changes to Hardware Address Space (Remember: IPC through Memory-Mapped Files)
      • Deciding to Swap-Out a mmap-ed Virtual Address region, also means having to write-out Dirty Pages
    • Must apply change to other Process’ Virtual Memory Mappings – Increases TLB Misses
      • Note: Context Switch flushes TLB entirely on old x86 machines (forced on each %CR3 write)
        • But not on MIPS – Remember: Flexible Software-managed TLB
          • MIPS tags TLB entries with Process Context IDentifier (PCID)
          • Remember: invlpg & invpcid Instructions

C. Papachristos

43 of 51

OS & Paging

 

CS446/646 C. Papachristos

44 of 51

OS & Paging

The User-Level Perspective

​

Memory-Mapped Files

​

  • Other Memory objects may be placed�between the Heap and the Stack�Virtual Memory Address regions

CS446/646 C. Papachristos

45 of 51

OS & Paging

The User-Level Perspective

​

The mmap() System Call

​

​

void *mmap (void *addr, size_t len, int prot,

int flags, int fd, off_t offset);

​

  • Map File specified by fd at Virtual Address addr
    • If addr is null, let Kernel choose the Virtual Address

​

  • prot : Protection of region
    • Binary OR of: PROT_EXEC (can be used to store Instructions), PROT_READ, PROT_WRITE, PROT_NONE (reserved –e.g. for future use– with no access allowed)

​

  • flags
    • MAP_ANON : Anonymous Memory – Non-File-Backed (fd should be -1)
    • MAP_PRIVATE : Modifications are private
    • MAP_SHARED : Modifications seen by everyone

CS446/646 C. Papachristos

46 of 51

OS & Paging

The User-Level Perspective

​

More Virtual Memory System Calls

​

int msync(void *addr, size_t len, int flags);

​

  • Flush changes of Memory-Mapped File to Backing Store

​

int munmap(void *addr, size_t len)

​

  • Removes Memory-Mapped object

​

int mprotect(void *addr, size_t len, int prot)

​

  • Changes Protection on Process’ Virtual Memory address range (PROT_...)

​

int mincore(void *addr, size_t len, char *vec)

​

  • Populates vector vec to contain the Memory Residency status of a Process’ Virtual Memory address ranges (corresponding Pages are Present (or not), will not (or will) generate Page Fault)

CS446/646 C. Papachristos

47 of 51

OS & Paging

The User-Level Perspective

​

Exposing information of Page Faults to the User-Level

​

​

​

​

​

​

​

​

​

​

  • E.g. can specify/register a Process (User-Level) callback function to run on SIGSEGV
    • Unix Signal raised on Invalid Memory access

CS446/646 C. Papachristos

struct sigaction {

union { /* signal handler */

void (*sa_handler)(int);

void (*sa_sigaction)(int, siginfo_t *, void *);

};

sigset_t sa_mask; /* signal mask to apply */

int sa_flags;

};

​

int sigaction (int sig,

const struct sigaction *act,

struct sigaction *oact);

48 of 51

OS & Paging

The User-Level Perspective

​

Exposing information of Page Faults to the User-Level

​

Example: OpenBSD/i386 siginfo

​

​

​

​

​

​

​

​

​

​

​

  • Linux uses ucontext_t (Remember: Homework 3) – same idea,�just uses nested structures that don’t all fit on one slide

CS446/646 C. Papachristos

struct sigcontext {

int sc_gs; int sc_fs; int sc_es; int sc_ds;

int sc_edi; int sc_esi; int sc_ebp; int sc_ebx;

int sc_edx; int sc_ecx; int sc_eax;

​

int sc_eip; int sc_cs; /* instruction pointer */

int sc_eflags; /* condition codes, etc. */

int sc_esp; int sc_ss; /* stack pointer */

​

int sc_onstack; /* sigstack state to restore */

int sc_mask; /* signal mask to restore */

​

int sc_trapno;

int sc_err;

};

49 of 51

OS & Paging

The User-Level Perspective

​

User-Level Virtual Memory “Tricks”

​

Combination of mprotect()/sigaction() very powerful

  • e.g. Fault, Unprotect Page (via User-Space available System Call), return from Signal Handler

​

  • Technique used in Object-Oriented Databases
    • Bring in objects on-demand
    • Keep track of which objects may be Dirty
    • Memory is managed and acts as a cache for a much larger Object Database

​

  • Other interesting applications
    • Some Garbage Collection Algorithms
    • Efficient snapshots of Processes (Copy-on-Write)

CS446/646 C. Papachristos

50 of 51

Next Lecture Reading Preparation

Operating Systems – Three Easy Pieces (https://pages.cs.wisc.edu/~remzi/OSTEP/)

​

Virtualization

  • 14. Interlude: Memory API
    • Beginning of Chapter
    • 14.1 Types of Memory
    • 14.2 The malloc() Call
    • 14.3 The free() Call
    • 14.4 Common Errors
    • 14.5 Underlying OS Support
    • 14.6 Other Calls
  • 17. Free-Space Management
    • Beginning of Chapter
    • 17.1 Assumptions
    • 17.2 Low-level Mechanisms
    • 17.3 Basic Strategies
    • 17.4 Other Approaches

CS446/646 C. Papachristos

51 of 51

Time for Questions !

CS-446/646

CS446/646 C. Papachristos