Operating System - Virtualization

CS537 - Operating System Summary Part 1 Virtualization

Virtualization

Process

What is a process

• A running program is a process
• Stream of executing instructions and their “context”

Thread

• Can have multiple threads within a single process
• Lightweight process
• Share an address space

Why do we need processes?

• Share CPU: Time sharing

OS Scheduler

• Scheduler save context when process is pause
• Restore context on resumption

Goals for CPU Virtualization

• Policy goals

  • Virtualize CPU resource using processes
  • Reschedule process for fairness? efficiency?

• Mechanism goals

  • Efficiency: Time sharing should not add overhead
  • Control: OS should be able to intervene when required

Mechanism

System call

• User mode and kernel mode

  • User processes run in user mode (restricted mode)
  • OS runs in kernel mode (not restricted)

• System call

  • Separate user mode from kernel mode for security
  • Use system call to invoke kernel mode functions

• Procedure for calling read()

  1. Set system call table index to 6 movl $6, %eax
  2. Call trap with id 64 int $64

Dispatch mechanism

• Dispatch loop

  while (1) {	
      run	process	A for some time-slice	
      stop process A and save its context	
      load context of another process B	
  }

• Cooperative Multi-tasking

  • Trust process to relinquish CPU through traps
  • Provide special yield() system call
  • Processes can misbehave

• Timer-based Multi-tasking

  • Hardware generates timer interrupt (CPU or separate chip)
  • User must not be able to mask timer interrupt

Policy

Vocabulary

• Workload: set of jobs (arrival time, run_time)
• Job ~ Current execution of a process
• Scheduler: Decides which ready job to run
• Metric: measurement of scheduling quality
• Turnaround time = completion time - arrival time
• Response time = first run time - arrival time

FIFO (First In, First Out)

• Disadvantage: Turnaround time suffers when short jobs must wait for long jobs (Convoy Effect)

SJF (Shortest job first)

• Disadvantage: Only schedule new job when previous job voluntarily relinquishes CPU

STCF (Shortest Time-to-Completion First)

• Preemptive: Schedule different job by taking CPU away from running job
• Always run job that will complete the quickest

Round Robin

• Goal: reduce response time
• Trade-off: increase turnaround time

I/O Aware Scheduling

• Goal: process won’t hold CPU when doing IO

Multilevel Feedback Queue

• Motivation: Run-time of each job is not known

• Approach

  • Multiple levels of round-robin
  • Each level has higher priority than lower level
  • Can preempt them

• Rules

  1. If priority(A) > Priority(B), A runs
  2. If priority(A) == Priority(B), A & B run in RR
  3. Processes start at top priority
  4. If job uses whole slice, demote process (longer time slices at lower priorities)

• Avoid starvation

  • Problem: Low priority job may never get scheduled
  • Solution: Periodically boost priority of all jobs (or all jobs thathaven’t been scheduled)

Memory Virtualization

Introduction

Goals

• Transparency: Process is unaware of sharing
• Protection: Cannot corrupt OS or other process memory
• Efficiency: Do not waste memory or slow down processes
• Sharing: Enable sharing between cooperating processes

Address space

• Stack: No fragmentation
• Heap: Consists of allocated and free areas (holes)
  

Memory Access Example

Assembly	Access for Instruction	Access for Execution
0x10: movl 0x8(%rbp), %edi	Fetch instruction at 0x10	Load from 0x208
0x13: addl $0x3, %edi	Fetch instruction at 0x13	No memory access
0x19: movl %edi, 0x8(%rbp)	Fetch instruction at 0x19	Store to 0x208

Basic Mechanisms

Time Sharing

• On process switch, save current process’s memory to disk and load another process’s memory from disk.
• Ridiculously poor performance

Static Relocation

• Idea

  • OS rewrites each program before loading it as a process in memory
  • Each rewrite for different process uses different addresses and pointers
  • Change jumps, loads of static data

• Disadvantage

  • Process can destroy OS or other processes
  • No privacy
  • Cannot move address space after it has been placed
  • May not be able to allocate new process

Dynamic Relocation: Introduction

• Goal: Protect processes from one another

• Memory Management Unit (MMU)

  • MMU dynamically changes process address at every memory reference
  • Process generates logical or virtual addresses (in their address space)
  • Memory hardware uses physical or real addresses

• Two operating modes

  • Kernel mode

    • Can manipulate contents of MMU
    • Allows OS to access all of physical memory

  • User mode

    • Perform translation of logical address to physical address

Dynamic Relocation: Base Register

• Translation on every memory access of user process
• MMU adds base register to logical address to form physical address
• Store offset in base register
• Each process has different value in base register
• Dynamic relocation by changing value of base register.

• Quiz

  • What entity should do translation of addresses with base register? Hardware
  • What entity should modify the base register? OS

• Problem: No protection

Dynamic Relocation: Base + Bounds

• Idea

  • limit the address space with a bounds register
  • Base register: smallest physical addr (or starting location)
  • Bounds register: size of this process’s virtual address space
  • OS kills process if process loads/stores beyond bounds

• Implementation

  • MMU compares logical address to bounds register
  • if logical address is greater, then generate error
  • MMU adds base register to logical address to form physical address

• Context switch

  1. Change to privileged mode
  2. Save base and bounds registers of old process
  3. Load base and bounds registers of new process
  4. Change to user mode and jump to new process

• Advantages

  • Provides protection (both read and write) across address spaces
  • Supports dynamic relocation
  • Simple, inexpensive implementation: Few registers, little logic in MMU
  • Fast: Add and compare in parallel

• Disadvantages

  • Each process must be allocated contiguously in physical memory
  • Must allocate memory that may not be used by process
  • No partial sharing: Cannot share limited parts of address space

Segmentation

• Idea

  • MMU contains Segment Table (per process)
  • Each segment has own base and bounds, protection bits
  • Example: 14 bit logical address, 4 segments;

• Example

  • Segment Table

    Segment	Base	Bounds	R W
    0	0x2000	0x6ff	1 0
    1	0x0000	0x4ff	1 1
    2	0x3000	0xfff	1 1
    3	0x0000	0x000	0 0

  • Translation

    Logical address	Segment	Base	Physical address
    0x0240	0	0x2000	0x2240
    0x1108	1	0x0000	0x1108
    0x256c	2	0x3000	0x356c
    0x3002	3	0x0000	Fail

• Advantages

  • No extra memory access
  • Enables sparse allocation of address space
  • Stack and heap can grow independently
  • Enables sharing of selected segments
  • Read-only status for code
  • Supports dynamic relocation of each segment

• Disadvantages

  • Each segment must be allocated contiguously
  • May not have sufficient physical memory for large segments?
  • External Fragmentation

Summary

Description	Name of approach
One process uses RAM at a time	Time Sharing
Rewrite code and addresses before running	Static Relocation
Add per-process starting location to virt addr to obtain phys addr	Base
dynamic approach that verifies address is in valid range	Base + Bounds
Several base+bound pairs per process	Segmentation

Paging

Fragmentation

• Definition

  • Free memory that can’t be usefully allocated

• Types of fragmentation

  • External: Visible to allocator (e.g., OS)
  • Internal: Visible to requester

Introduction for Paging

• Goal

  • Eliminate requirement that address space is contiguous
  • Eliminate external fragmentation
  • Grow segments as needed

• Idea

  • Divide address spaces and physical memory into fixed-sized pages (usually 4KB)

Translation of Page Addresses

• Logical address
  • High-order bits of address designate page number
  • Low-order bits of address designate offset within page

• Address Format

  Page Size	Low Bits	Virt Addr Bits	High Bits	Virt Pages
  16 bytes	log(16) = 4	10	10 - 4 = 6	2 ^ 6 = 64
  1 KB	log(1K) = 10	20	20 - 10 = 10	2 ^ 10 = 1024
  1 MB	log(1M) = 20	32	32 - 20 = 12	2 ^ 12 = 4K
  512 bytes	log(512) = 9	16	16 - 9 = 7	2 ^ 7 = 128
  4 KB	log(4K) = 12	32	32 -12 = 20	2 ^ 20 = 1M

• Address Translation

  • Number of bits in virtual address need not equal number of bits in physical address

Pagetables

• How should OS translate VPN to PPN?

  • Simple solution: Linear page table aka array

• Example
  

  • Page table for P1: 3, 1, 7, 10
  • Page table for P2: 0, 4, 2, 6
  • Page table for P3: 8, 5, 9, 11

• How big is a pagetable

  • Given 32-bit address space, 4KB pages, 4 byte entries
  • 4KB pages => 12 bit for offset
  • 32-bit address space => 20 bit for VPN => 2 ^ 20 = 1MB entries
  • 1MB entries * 4 byte per entry = 4MB

• Where are pagetables stored

  • Store each page table in memory
  • Hardware finds page table base with register (e.g., CR3 on x86)

• What happens on a context-switch?

  • Change contents of page table base register to newly scheduled process
  • Save old page table base register in PCB of descheduled process

• What other info is in pagetable entries besides translation?

  • valid bit
  • protection bits
  • present bit (needed later)
  • reference bit (needed later)
  • dirty bit (needed later)

Memory Access with Paging

• Given

  • Current instruction: 0x0010: movl 0x1100, %edi
  • Assume PT is at phys addr 0x5000
  • Assume PTE’s are 4 bytes
  • Assume 4KB pages => 12 bits for offset
  • Page table for current process: 2, 0, 80, 99

• Fetch instruction at logical addr 0x0010

  • Access page table to get ppn for vpn 0
  • Mem ref 1: 0x5000
  • Learn vpn 0 is at ppn 2
  • Fetch instruction at 0x2010 (Mem ref 2)

• Exec, load from logical addr 0x1100

  • Access page table to get ppn for vpn 1
  • Mem ref 3: 0x5000
  • Learn vpn 1 is at ppn 0
  • movl from 0x0100 into reg (Mem ref 4)

Advantages of Paging

• No external fragmentation

  • Any page can be placed in any frame in physical memory

• Fast to allocate and free

  • Alloc: No searching for suitable free space
  • Free: Doesn’t have to coalesce with adjacent free space

• Simple to swap-out portions of memory to disk (later lecture)

  • Page size matches disk block size
  • Can run process when some pages are on disk
  • Add “present” bit to PTE

Disadvantages of Paging

• Internal fragmentation: Page size may not match size needed by process

  • Wasted memory grows with larger pages
  • Tension?

• Additional memory reference to page table -> Very inefficient

  • Page table must be stored in memory
  • MMU stores only base address of page table

• Storage for page tables may be substantial

  • Simple page table: Requires PTE for all pages in address space
  • Entry needed even if page not allocated?

Paging Translation Steps

1. extract VPN (virt page num) from VA (virt addr)
2. calculate addr of PTE (page table entry)
3. read PTE from memory
4. extract PFN (page frame num)
5. build PA (phys addr)
6. read contents of PA from memory into register

TLB

Motivative Example: Iterating Array

• Code

  int sum = 0;
  for (int i = 0; i < N; i++){ 
      sum += a[i];
  }

• Memory Access

  What virtual addresses?	What physical addresses?
  load 0x3000	load 0x100C load 0x7000
  load 0x3004	load 0x100C load 0x7004
  load 0x3008	load 0x100C load 0x7008
  load 0x300C	load 0x100C load 0x7008

Introduction

• Strategy: Cache Page Translations
• TLB stands for Translation Lookaside Buffer
  

TLB Organization

• TLB Entry

  Tag (virtual page number)	Physical page number (page table entry)

• Fully associative

  • Any given translation can be anywhere in the TLB
  • Hardware will search the entire TLB in parallel

Example: Iterating Array with TLB

• Code

  int sum = 0;
  for (int i = 0; i < 2048; i++){ 
      sum += a[i];
  }

• Page table for current process (starting at 0x0000)

  PPN	1	5	4	…
  VPN	0	1	2	3

• TLB

  Valid	VPN	PPN
  1	1	5
  1	2	4

• Memory Access

  What virtual addresses?	What physical addresses?
  load 0x1000	load 0x0004 load 0x5000
  load 0x1004	(TLB hit) load 0x5004
  load 0x1008	(TLB hit) load 0x5008
  load 0x100C	(TLB hit) load 0x500C
  …	…
  load 0x2000	load 0x0008 load 0x4000
  load 0x2004	(TLB hit) load 0x4004

• Performance

  • # TLB lookups = number of accesses to a = 2048
  • # TLB misses = 2
  • Miss rate = 2/2048 = 0.1%
  • Hit rate = 1 – miss rate = 99.9%

TLB Replacement Policies

• Access Patterns

  • Sequential array accesses almost always hit in TLB: Very fast!
  • Highly random, with no repeat accesses: Slow

• Code Example

  Workload A	Workload B

• Workload Locality

  • Spatial Locality: future access will be to nearby addresses
  • Temporal Locality: future access will be repeats to the same data

• What TLB characteristics are best for each type?

  • Spatial:

    • Access same page repeatedly; need same vpn à ppn translation
    • Same TLB entry re-used

  • Temporal:

    • Access same address near in future
    • Same TLB entry re-used in near future
    • How near in future? How many TLB entries are there?

• Replacement policies

  • LRU: evict Least-Recently Used TLB slot when needed
  • Random: Evict randomly choosen entry

Context Switches

• What happens if a process uses cached TLB entries from another process?

  1. Flush TLB on each switch

     • Costly
     • lose all recently cached translations

  2. Track which entries are for which process

     • Address Space Identifier
     • Tag each TLB entry with an 8-bit ASID

• TLB Example with ASID

  • Pagetable

    • P1 (ASID 11): 1, 5, 4, …
    • P2 (ASID 12): 6, 2, 3, …

  • TLB

    Valid	Virt	Phys	ASID
    0	1	9	11
    1	1	5	11
    1	1	2	12
    1	0	1	11

  • Memory access

    Virtual	Physical
    load 0x1444 with ASID 12	0x2444
    load 0x1444 with ASID 11	0x5444

• TLB Performance

  • Context switches are expensive

  • Even with ASID, other processes “pollute” TLB

    • Discard process A’s TLB entries for process B’s entries

  • Architectures can have multiple TLBs

    • 1 TLB for data, 1 TLB for instructions
    • 1 TLB for regular pages, 1 TLB for “super pages”

TLB Misses

• Who Handles TLB MISS? Hardware or OS?

• Hardware: CPU must know where pagetables are

  • CR3 register on x86
  • Pagetable structure fixed and agreed upon between HW and OS
  • HW “walks” the pagetable and fills TLB

• OS: “Software-managed TLB”

  • CPU traps into OS upon TLB miss
  • OS interprets pagetables as it chooses
  • Modifying TLB entries is privileged
  • Need same protection bits in TLB as pagetable - rwx

Summary

• Pages are great, but accessing page tables for every memory access is slow

• Cache recent page translations -> TLB

  • Hardware performs TLB lookup on every memory access

• TLB performance depends strongly on workload

  • Sequential workloads perform well
  • Workloads with temporal locality can perform well

• In different systems, hardware or OS handles TLB misses

• TLBs increase cost of context switches

  • Flush TLB on every context switch
  • Add ASID to every TLB entry

Smaller Page Tables

Motivation

• How big are page tables

  1. PTE’s are 2 bytes, and 32 possible virtual page numbers

     • 2 bytes * 32 = 64 bytes

  2. PTE’s are 2 bytes, virtual addrs are 24 bits, pages are 16 bytes

     • 16 bytes page => 4 bit offset => 20 bit VPN
     • => 2^20 Pages => 2^20 * 2 = 2MB for page tables

  3. PTE’s are 4 bytes, virtual addrs are 32 bits, and pages are 4 KB

     • 4KB page => 12 bit offset => 20 bit VPN
     • => 2^20 Pages => 2^20 * 4 = 4MB for page tables

  4. PTE’s are 4 bytes, virtual addrs are 64 bits, and pages are 4 KB

     • 4KB page => 12 bit offset => 52 bit VPN
     • => 2^52 Pages => 2^52 * 4 = 18.0143985 PB for page tables

• Why are Page Tables so Large?

  • Many invalid PT entries

• Summary

  • Storage for page tables may be substantial

  • Simple page table: Requires PTE for all pages in address space

  • Entry needed even if page not allocated.

Smaller Page Tables

• Use more complex page tables, instead of just big array

• Any data structure is possible with software-managed TLB

  • Hardware looks for vpn in TLB on every memory access

  • If TLB does not contain vpn, TLB miss

    • Trap into OS and let OS find vpn->ppn translation
    • OS notifies TLB of vpn->ppn for future accesses

• Other approaches

  1. Segmented Pagetables

  2. Multi-level Pagetables

     • Page the page tables
     • Page the pagetables of page tables…

  3. Inverted Pagetables

Paging with Segmentation

• Idea

  • Divide address space into segments (code, heap, stack)

  • Divide each segment into fixed-sized pages

  • Logical address divided into three portions

    seg # (4 bits)	page number (8 bits)	page offset (12 bits)

• Implementation

  • Each segment has a page table
  • Each segment track base (physical address) and bounds of the page table

• Quiz

  • Logical address layout

    seg # (4 bits)	page number (8 bits)	page offset (12 bits)

  • Segment Table

    Segment	Base	Bounds	R W
    0	0x002000	0xff	1 0
    1	0x000000	0x00	0 0
    2	0x001000	0x0f	1 1

  • Translation

    Virtual	Seg	Base	Offset	PPN	Physical	Note
    0x002070 R	0	0x002000	2	0x004	0x004070
    0x202016 R	2	0x001000	2	0x003	0x003016
    0x104c84 R	1	-	-	-	-	R = 0
    0x010424 W	0	-	-	-	-	W = 0
    0x210014 W	2	-	-	-	-	bounds
    0x203568 W	2	0x001000	3	0x02a	0x02a568

• Advantages

  • Advantages of Segments

    • Supports sparse address spaces.
    • Decreases size of page tables. If segment not used, not need for page table

  • Advantages of Pages

    • No external fragmentation
    • Segments can grow without any reshuffling
    • Can run process when some pages are swapped to disk (next lecture)

  • Advantages of Both

    • Increases flexibility of sharing: Share either single page or entire segment

• Disadvantages

  • Potentially large page tables (for each segment)
  • Must allocate each page table contiguously
  • More problematic with more address bits

Multilevel Page Tables

• Goal: Allow each page tables to be allocated non-contiguously

• Idea: Page the page tables

  • Creates multiple levels of page tables; outer level “page directory”
  • Only allocate page tables for pages in use
  • Used in x86 architectures (hardware can walk known structure)

• Multilevel Pagetable Translation

  • Page directory and page tables

    	0x0	0x1	…	0xE	0xF
    Page directory	0x3	-	…	-	0x92
    PT @PPN 0x3	0x10	0x23	…	-	-
    PT @PPN 0x92	-	-	…	0x55	0x45

  • Address layout

    outer page (4)	inner page (4)	page offset (12)

  1. Translate 0x01ABC

     • Outer page = 0x0 => Use page table at 0x3
     • Inner page = 0x1 => PPN = 0x23
     • Physical address = 0x23ABC

  2. Translate 0xFEED0

     • Outer page = 0xF => Use page table at 0x92
     • Inner page = 0xE => PPN = 0x55
     • Physical address = 0x55ED0

• Address Format for Multilevel Paging

  • Given 30-bit address with 4KB page size
  • #bits for page offset = log(4K) = 12
  • 4 bytes per PTE => 1K entries per page => #bits for inner page = log(1K) = 10
  • #bits for outer page = 30 - 10 - 12 = 8

• Pagetable with 3 levels

  • Problem

    • Page directories (outer level) may not fit in a page

  • Solution

    • Split page directories into pieces
    • Use another page dir to refer to the page dir pieces.

  • Memory Addressability Comparison

    • 1 level = 2¹⁰ * 2¹² = 4MB
    • 2 level = (2¹⁰)² * 2¹² = 4GB
    • 3 level = (2¹⁰)³ * 2¹² = 4TB

• Quiz: Count Memory Access

  • Assumption

    • 3-level page table
    • 256-byte pages
    • 16-bit addresses
    • ASIC of current process is 211

  • TLB

    ASID	VPN	PFN	Valid
    211	0xbb	0x91	1
    211	0xff	0x23	1
    122	0x05	0x91	1
    211	0x05	0x12	0

  1. 0xAA10: movl 0x1111, %edi

     • TLB miss for 0xAA10 => 3 memory accesses for page table + 1 more to get the instruction

     • TLB miss for 0x1111 => 3 memory accesses for page table + 1 more to get the instruction

     • Total: 4 memory accesses

  2. 0xBB13: addl $0x3, %edi

     • TLB hit for 0xBB13 => 1 access more to get the instruction

  3. 0x0519: movl %edi, 0xFF10

     • TLB miss for 0x0519 => 3 memory access for page table + 1 more to get the instruction

     • TLB hit for 0xFF10 => 1 access more to get the instruction

     • Total: 5 memory accesses

Inverted Page Table

• Only need entries for virtual pages w/ valid physical mappings

• Naïve approach:

  • Search through data structure <ppn, vpn+asid> to find match
  • Too much time to search entire table

• Better:

  • Find possible matches entries by hashing vpn+asid
  • Smaller number of entries to search for exact match

• Managing inverted page table requires software-controlled TLB

Swapping

Motivation

• Support processes when not enough physical memory
• Single process with very large address space
• Multiple processes with combined address spaces

Idea

• OS keeps unreferenced pages on disk

  • Slower, cheaper backing store than memory

• Process can run when not all pages are loaded into main memory

• OS and hardware cooperate to make large disk seem like memory

  • Same behavior as if all of address space in main memory

Locality of Reference

• Leverage locality of reference within processes

  • Spatial: reference memory addresses near previously referenced addresses
  • Temporal: reference memory addresses that have referenced in the past
  • Processes spend majority of time in small portion of code

• Implication:

  • Process only uses small amount of address space at any moment
  • Only small amount of address space must be resident in physical memory

• Memory Hierarchy

  

Mechanism

• Each page in virtual address space maps to one of three locations:

  • Physical main memory: Small, fast, expensive
  • Disk (backing store): Large, slow, cheap
  • Nothing (error): Free

• Extend page tables with an extra bit: present

  • permissions (r/w), valid, present
  • Page in memory: present bit set in PTE
  • Page on disk: present bit cleared
    • PTE points to block on disk
    • Causes trap into OS when page is referenced

• Procedure

  Hardware checks TLB
  if TLB hit
      address translation is done
      page in physical memory
  else // TLB miss
      Hardware or OS walk page tables
      if PTE designates page is present
          page in physical memory (i.e., present bit is cleared)
      else // page fault
          Trap into OS (not handled by hardware)
          OS selects victim page in memory to replace
          if victim page is modified
              write victim page out to disk
          OS reads referenced page from disk into memory
          Page table is updated, present bit is set
          Process continues execution

Policy: Page selection

• When should a page on disk be brought into memory?

• Demand paging: Load page only when page fault occurs

  • Intuition: Wait until page must absolutely be in memory
  • When process starts: No pages are loaded in memory
  • Problems: Pay cost of page fault for every newly accessed page

• Prepaging (anticipatory, prefetching): Load page before referenced

  • OS predicts future accesses (oracle) and brings pages into memory early
  • Works well for some access patterns (e.g., sequential)

• Hints: Combine above with user-supplied hints about page references

  • User specifies: may need page in future, don’t need this page anymore, or sequential access pattern, …
  • Example: madvise() in Unix

Policy: Page replacement

• Which resident page in memory should be thrown out to disk?

• OPT: Replace page not used for longest time in future

  • Advantages: Guaranteed to minimize number of page faults
  • Disadvantages: Requires that OS predict the future; Not practical, but good for comparison

• FIFO: Replace page that has been in memory the longest

  • Intuition: First referenced long time ago, done with it now
  • Advantages: Fair: All pages receive equal residency; Easy to implement
  • Disadvantage: Some pages may always be needed

• LRU: Replace page not used for longest time in past

  • Intuition: Use past to predict the future
  • Advantages: With locality, LRU approximates OPT
  • Disadvantages: Harder to implement and does not handle all workloads well

• Comparison

  LRU, OPT	FIFO
  Guaranteed to have fewer page faults Smaller memory sizes ⊆ larger memory sizes Smaller cache ⊆ bigger cache	Usually have fewer page faults May actually have more page faults!

Implementing LRU

• Software Perfect LRU

  • OS maintains ordered list of physical pages by reference time
  • When page is referenced: Move page to front of list
  • When need victim: Pick page at back of list
  • Trade-off: Slow on memory reference, fast on replacement

• Hardware Perfect LRU

  • Associate timestamp register with each page
  • When page is referenced: Store system clock in register
  • When need victim: Scan through registers to find oldest clock
  • Trade-off: Fast on memory reference, slow on replacement (especially as size of memory grows)

• Approximating LRU: Clock Algorithm

  • Hardware

    • Keep use (or reference) bit for each page frame
    • When page is referenced: set use bit (page was used recently)

  • Operating System

    • Page replacement: Look for page with use bit cleared (has not been referenced for a while)
    1. Keep pointer to last examined page frame
    2. Traverse pages in circular buffer
    3. Clear use bits as search
    4. Stop when find page with already cleared use bit, replace this page

Summary

• Abstraction: Virtual address space with code, heap, stack

• Address translation

  • Contiguous memory: base, bounds, segmentation
  • Using fixed sizes pages with page tables

• Challenges with paging

  • Extra memory references: avoid with TLB
  • Page table size: avoid with multi-level paging, inverted page tables etc.

• Larger address spaces: Swapping mechanisms, policies (LRU, Clock)

打赏