[UCSD CSE120]虚拟内存-virtual memory

本文是我在上UCSD的 CSE 120: Principles of Operating Systems (Winter 2020) 整理的笔记,这一课主要介绍了操作系统里面虚拟内存的概念,主要是对上一节课的逻辑内存的一部分补充,关于segment和page的概念可以参考上一篇笔记。


  1. Segments and Pages

    • Structuring memory as segements/pages allows:

      • partitioning memory for convenient allocation
      • reorganizing memory for convenient usage
    • Approaches

      • Relocation via address translation
      • Protection via matching operations with objects
    • Result: a logically organized memory

  2. Optimization

    • Not all pieces need to be in memory

      • Need only piece being referenced
      • Other pieces can be on disk
      • Bring pieces in only when needed
    • Illusion: there is much more memory

    • Needed:

      • A way to identify whether a piece is in memory
      • A way to bring in a piece (from where to where?)
      • Relocation (address translation)
  3. From logical to virtual memory

    • Logical memory becomes virtual memory

      • Still logical (seperate organization from physical)
      • Virtual: memory seems to exist, regardless of how (memory or disk)
    • Virtual memory: illusion of large memory

      • Keep only portion of logical memory in physical
      • Rest is kept on disk (larger, slower, cheaper)
      • Unit of memory is segment or page (or both)
    • Logical address space $\rightarrow$ virtual address space

Virtual memory based on paging

  1. Paged virtual memory

    • All of pages reside on disk
    • Some also reside in physical memory (which ones?)
  2. Contents of page table entry

    • Valid: is entry valid (page in physical memory or not)
    • Ref: has this page been referenced yet?
    • Mod: has this page been modified?
    • Frame: what frame is this page in?
    • Prot: what are the allowable operations?
  3. Address Translation

    • Process:

      • Get entry: index page table with page number
      • If valid bit is off, which cause a page fualt, then trap into kernel

        • Find page on disk
        • Read it into a free frame

          • may need to make room if there is no available frame: page replacement
        • Record frame number in page table entry

        • Set valid bit and other fields
      • Retry instruction (return from page-fault trap)

    • Possible faults under segmentation/paging

      • two kinds of address:

        • Virtual address: (segment s, page p, offset i)
        • Physical address: (frame f, offset i)
      • [ ] Use s to index segment table (to get page table)

        • may get a segment fualt
      • [ ] Check bound (Is p < bound?)

        • may get a segmentation violation
      • [ ] Use p to index page table (to get frame f)

        • may get a page fault
      • [ ] Physical address: concatenate f and i

    • Cost of page faults is high

      • Disk: 5 ~ 6 orders magnitude slower than RAM
      • Example:

        • RAM access time: 100 nsec
        • Disk access time: 10 msec
        • p = page fault probability
        • Effective access time: 100 + p * 10,000,000 nsec
        • if p = 0.1%, effective access time = 10,100 nsec (100 times slower!)

Possible implementation

  1. Principle of Locality

    • Not all pieces referenced uniformly over time

      • Make sure most referenced pieces in memory
      • If not, thrashing: constant fetching of pieces
    • References cluster in time/space

      • Will be same or neighboring areas
      • Allows prediction based on past
  2. Page replacement policy

    • Goal: remove page not in locality of reference
    • Page replacement is about:

      • which page(s) to remove
      • when to remove them
    • How to do it in cheapest way possible, with:

      • least amount of additional hardware
      • least amount of software overhead
  3. Basic Page Replacement Algorithms

    • FIFO: select page that is oldest

      • Simple: keep pointer to next frame after last loaded
      • Doesn’t perform well (oldest may be popular)
    • OPT: Optimal Page Replacement

      • Optimal: replace page that will be accessed furthest in future
      • Not realistic:

        • Requires predicting the future
        • Useful as a benchmark
    • LRU: Least Recently Used

      • Replace page that was least recently used

        • LRU means used furthest in the past
      • Takes advantage of locality of reference

      • Must have some way of tracking frame with LRU page : requires hardware support


  1. Approximating LRU: Clock Algorithm

    • Select page that is old and not recently used

      • Clock (second chance) is approximation of LRU
    • Hardware support: reference bit

      • Associated with each frame is a reference bit
      • Reference bit is in page table entry
    • How reference bit is used

      • When frame filled with page, set bit to 0 (by OS)
      • If frame is accessed, set bit to 1 (by hardware)
    • Working process

      • Arrange all frames in circle (clock)
      • Clock hand: next frame to consider
      • Page fault: find frame

        • If ref bit 0, select frame
        • Else, set ref bit to 0
        • Advance clock hand
        • If frame found, break out of loop, else repeat
      • If frame had modified page, must write it to disk

  2. Resident Set Management

    • Resident set: process’s pages in physical memory

      • One set per process
      • How big should resident set be? Which pages?
      • Who provides frame (same process or another)?
    • Local: limit frame selection to request process

      • Isolates effects of page behavior on processes
      • Inefficient: some processes have unused frames
    • Global: select any frame (from any process)

      • Efficient: resident sets grow/shrink accordingly
      • No isolation: process can negatively affect another (by replacing other process’s important pages)
  3. Multiprogramming Level

    • Multiprogramming level: number of processes in physical memory (non-empty resident sets)
    • Goal: increase multiprogramming level - how?
    • However, beyond certain point: thrashing (make processor utilization pretty low since many processes may not be working)
    • Resident set should contain the working set
  4. Denning’s Working Set Model

    • Introduction

      • Working set: $W(t, \Delta)$

        • Pages referenced during last delta (process time)
      • Process given frames to hold working set

      • Add/remove pages according to $W(t, \Delta)$
      • If working set doesn’t fit, swap process out
    • Working set is a local replacement policy

      • Process’s page fault behavior doesn’t affect others
    • Problem: difficult to implement

      • Must timestamp pages in working set
      • Must determine if timestamp older than $t - \Delta$
      • How should $\Delta$ be determined?
    • Contrast to Clock

      • Clock: simple, easy to implement, global policy