Vault

ECS154A-L22

4 min read

Cramming for final, filling in.

Virtual-Memory

Transclude of ECS154A-L21-2025-03-19-20.58.37.excalidraw

Last lecture

Caches:

  • line sizes
  • cache write policies
    • hit/miss
  • Writes slower than reads
  • mem hierarchy extends even into caches
    • l1, l2, l3 ..
    • main memory
    • remote storage
    • etc.
  • Evaluate performance of cache with AMAT
  • One of the challenges of caches is that ‘technically’ they are not there.
    • Catch 22, take advantage or don’t, performance vs portability

More practice!

14 bit address, 512 byte cache, DM, LS=4

  • Last 2 are offset
  • entry num: log2(512/4=128)=7
  • Rest are tag - 5

14 bit address, 24 byte 3-way SA, LS=2

  • Last 1 is offset
  • set num: log2(24 / (3x2) ) = 2
  • Rest are tag - 11

14 bit 320 byte fully associative cache, LS=16

  • 4 bits offset
  • other 10 tag

New Material

All programs assume that they have the entire machine to themselves

To accomplish this, take memory and break it into frames.
You don’t need to put the entire program in memory, only need to put the part of the program you’re using in memory.

memspace
frame32
frame32
frame32
frame32
  • 128 byte memory

That’s basically what virtual memory is doing:

  • The OS takes memory and breaks it into frames (pages / page frames)
  • Program will generate virtual addresses, these are broken into a bunch of virtual pages, then the OS takes the page you want to reference into one of the frames.
  • OS:
    • Each process has a

Suppose we have the following system: 8 bit address
What we’re saying is that each of the pages needs 5 bits for the page entry, and then what we have left over is the virtual page number

  • What is the easiest way to figure out how to store the relationship between the virtual page we want and the actual place that it’s put in?
    • We could just use a list.
    • A page table
      • For every possible virtual page number from 000-111, the easiest thing to do is to relate the virtual page number to the frame number.
      • For each frame, what’s in each frame?
        • An example:
          1. Process 1
          2. Process 3
          3. Empty:
          4. On Disk
      • What if there is no frame number in the page table?
        • Generate a page fault, call the OS, the OS returns a frame number to allocate. IE frame number 00
XXXX XXXX
XXX|X XXX

101 | 10110
^virt page #

MAPPING:

  • From a VIRTUAL 8-bit address to a PHYSICAL 7-bit address.
    • A MAPPING
    • from one space to another space.
    • Map from 256 byte space to 128 byte space
    • Accomplish that by counting on the fact that we will reuse the address frequently (locality). Can’t allocate them all at once, instead hope that there’s some locality that makes it so that some are accessed more frequently/closely in time than others.

Helpful Pneumonic - Pictures and Picture Frames. Pictures are virtual, and Picture frames are real.

1k Byte mem
128 byte pages
16 bit address

XXXX XXXX XXXX XXXX

How many frames in memory?

  • 8. 1k / 128 = 8 frames
  • First 7 bits are the offset into the page (128 byte pages, needs 7 bits)
  • 9 bits left over, 9 bit virtual page number
    Needs a page table with 512 entries:
  • From 0 0000 0000 - 1 1111 1111
    • Inside, we have a 3 bit quantity
  • If we found that frame 5 was available:
    • We turn address:
      • XXXX XXXX XXXX XXXX into
      •           10 1XXX XXXX (5 bits for frame, 7 bits for offset)

Given:

  • 20 virtual bit address
  • 4k bytes of mem
  • 512 byte pages
    How wide is each PT entry? Need 3 bits to specify which of the 8 it is.
  • 4k/512 = 8 pages/frames.
    How many PT entries are there? 2^11, the remaining 11 out of 20
11 bits9 bits
  • 20 bits total

vocab so far:
Virtual Memory
Page
Page Table
Page Number
Virtual Page Number?
Frame Number
Frames

Graph View

Backlinks