CS 111 Lecture 14: Virtual Memory

by Alan Liao, Matthew Arakaki, and Yuncun Shen

Table of Contents:

1. Introduction
2. Simple Hardware Approach
3. Segmentation
4. Page-Based Memory Management
5. 2-Level Page Tables
6. Page Faulting
7. Virtual Memory Tuning

Introduction

Processes are often unreliable because of bad memory references

Causes: subscript errors, dereferencing null, uninitialized, fixed pointers, etc.

Possible Solutions:

1. fire all the programmers! (and then hire better ones)

1. disadvantage: Unfortunately doesn't scale very well

2. add runtime subscript checking - ex. Java does some subscript checking

1. disadvantages: performance issues/slow

3. trust issues - can be worked around if compiler is part of the OS
4. get help from the hardware

Simple Hardware Approach: Base/Bound Pairs

Add 2 extra registers: base, bounds

This design does a hardware check for each memory access. whenever a process tries to access a forbidden area, a trap is initiated.

Issues with this approach:

1. must have only one chunk of memory (no fragmentation)

1. possible solution: multiple base/bound pairs

2. programs must be able to fit in RAM
3. programs cannot contain absolute addresses (biggest problem)
4. suppose program changes base or bounds?

1. possible solution: make the registers privileged

 EX.

To fix absolute address problem:

1. change the hardware to always add a base pointer to every address
2. mutate absolute addresses to relative addresses in the program as you load it from the disk into RAM
3. prohibit absolute addresses (aka. position independent code, PIC). This is used often enough that gcc has an option for it (gcc -fpic ...).

How does one protect the base/bound registers?

1. make registers privileged (or make instructions to access them privileged)

From now on, let's call the blocks of memory allocated with the base/bound pairs domains (name arbitrary)

Segmentation: Multiple Base/Bound Pairs

What if you want shared memory between processes?

1. multiple base bounds pairs (perhaps one private and one shared)

To implement this idea, we would need to add a system call to create a domain

It might look something like this:

map_domain(size,permissions);

Permissions need to be supported by the hardware (execute,read_execute,read_write, etc.).

1. Perhaps one could add a new register for permissions.

traditional x86 had only read and write permissions (no execute)

1. this made every file with rw permissions executable
2. unfortunately this made buffer overflows very easy

Problem with map_domain - not enough base/bounds pairs

To show this, let’s look at all of the uses for a domain:

1. text of a program (r)
2. data (rw)
3. heap (rw)
4. stack (1/thread)
5. I/O buffers
6. shared memory
7. etc.

To solve this problem, replace base/bounds pairs with registers

ex.

-segment # chooses a base/bound pair from segment table

-privilege needed to change the segment table

This process is called segmentation (or segmented memory)

Page-Based Memory Management

New Problem: new x() or higher level malloc() ie. allocation of dynamic memory

What if one wants to grow a segment? It's very expensive since you would have to move a lot of data

Solution: Page-Based Memory Management

1. each process has its own page table - extra level of indirection
2. all pages are the same size
3. Advantage - don't need pages to be contiguous in physical memory

There are a few problems with this implementation though

Security Issue:

1. Don't allow pages to edit the page table

Performance Issue:

1. Linear page table (x86 page size 4kiB)

1. size=2^20 or 4MiB/process (which is much too large)

2. many pages are unused (very inefficient)

int pmap(int v) {

        return PAGE_TABLE[v] >> 8;

}

2-Level Page Tables

To fix the performance issues, we can add an extra level of indirection

1. Similar to inodes
2. added hi and lo secondary tables allows for more efficient use of memory

int pmap(int v){

int hi = v>>10;

int lo = v&(1 << 10) -1

pt* p = PAGE_TABLE[hi]

if(!p)

        return 0;

return p[10]>>8;

}

Page Faulting

As the OS kernel, we might want to "lie" to the hardware and tell it that the current process is smaller than it actually is in the hardware page table.

This is actually fairly common. Often, a program thinks it has more memory than it actually has (ex. program thinks it has 3.5GiB but it actually has 100 MiB)

To allow dynamic memory:

swap space on disk

AKA Page faulting (causes a trap)

1. very slow! too slow to work if virtual memory >> physical memory because you need to pull data into memory
2. write and read removes useful data from main memory

Mechanism for page faulting:

trap -> enter kernal -> it inspects the faulting address

ex.

p = process(addr,victim page)

va= virtual addr of victim

pa = physical addr of victim

void pfault (int v, int access) {

if(swap_map(v,current_process) == fail)

        kill (current_process);

else{

(p,va) = removal_policy(); //picks a physical page

 //as victim

pa = p-> pmap(va);

p->pmap(va) = FAULT; //mark as bad, placed before write

//to avoid race condition

write(pa, swap_map(p,va));

read(pa,swap_map(current_process,v));

current_process->pmap(v) = pa;

}

}

Memory Manager Pages are never selected as victims

1. You also shouldn't make top-level page table a victim either

Virtual memory Tuning

1) Demand Paging - when you start the program, load just its 1st page (popular)

1. advantage: start up quickly (even though only 1 page of program in RAM)
2. disadvantage: disk arm may move more

2) Dirty Bit - 1 bit/page that keeps track of whether the page has been stored into (only needed for pages with w permissions)

1. can be put into page table entry (PTE)
2. if hardware won't change, then clear the w bit in PTE
3. when stored into, OS sets the dirty bit and sets w bit