Lecture 14- Virtual memory

Scribes: David Woo and Jonathan Tengco

Problem: Buggy programs with bad memory references.

Solutions:

  1. Hire better programmers
  2. Runtime checking in user programs

    Unfortunately, both of these solutions incur costs for people developing applications, either in terms of money to hire better programmers or in terms of performance lost from checking programs for bad memory references at runtime.

  3. Partition memory so that each running process gets a region to itself.
    Diagram of memory using base-bounds pairs

    Problems:

    1. Inflexibility; what if the program cheats by changing the base/bounds registers?

      Solution: The registers are privileged, any attempt to change them will result in a trap.

    2. The amount of memory allocated for each program is very hard to change.
    3. No easy way to share memory.

      Solution: Use multiple base/bounds pairs for each process. This is usually a small number that is limited by the hardware.

    4. Programs don't know where they'll be running ahead of time, so they must use relative addresses or rewrite their addresses when loaded.

    Example: The traditional (circa 1978) Unix model of memory.

    Each process gets a segment table, and each entry describes a region of memory that the process can access, along with what permissions that process has for that segment (r/w/x). Some combinations of permissions (r, rx, rw, rwx) are useful, some (w, wx, x, none) are not. Base/bounds pairs can be remapped using the system call map_domain(base, size, permissions...). Note that not all hardware supports all combinations of permissions- before 2003, there was no x permission for intel chips and having read permissions implied having execute permissions.

    A diagram of a segment tableA diagram of a hypothetical memory layout for a segmented address space

    Downsides:

    1. Programs need to know about segments.
    2. Segment sizes need to be set ahead of time.

  4. Paging + Virtual Memory

    Advantages:

    The last advantage was the original selling point of virtual memory. Physical memory was used as a cache for disk- pages that couldn't fit in RAM were stored on disk until they were needed. When the program tried to access a page that wasn't in RAM, a trap occurred and the needed page was loaded from disk. However, this led to a phenomenon called "thrashing" when a high proportion of memory accesses needed to load a page off of disk. When this occurred, the program would slow to a halt because of the long wait times involved in accessing disk. This led to the phrase "If you thrash, you're dead."

Virtual memory implementation

We need hardware help in order to implement virtual memory.

The simplest implementation: linear page table hardware support.

Page table lookup (as modeled in C; vpn = virtual page number)

A diagram of a linear page table 
int pmap(int vpn){
	return PAGE_TABLE[vpn] >> 8;
}

Note: the number of bits that PAGE_TABLE[vpn] is shifted depends on how large the offset is. This function should also return a special value when it tries to look up an unmapped page number (when it page faults).

Problems:

  1. The page table is stored in RAM itself, so there's a bootstrapping issue to take care of.
  2. For a 4 GiB address space, you need a 4 MiB page table- that's a lot of wasted space if you aren't using all, or even most of the 4 GiB.

Solutions:

  1. Special kernel-only instruction that allow direct address to physical memory lets the kernel set up the page table.
  2. Implement a 2-level page table (shown below).
Diagram of a 2-level page table 
int pmap(int vpn){ // 2-level version
	int hi = vpn >> 10;
	int lo = vpn&((1 << 10) -1);
	int *lopage = PAGE_TABLE[hi];
	if(lopage == FAULT)
		return FAULT;
	return lopage[lo];
}

Page faulting

When the virtual memory manager gets a request involving a virtual address that does not resolve to a physical address in RAM (e.g. the data it refers to is still on disk), a trap will occur. The kernel will get the virtual page number from the request, as well as the type of request and the context in which the request was made. It will then do one of two things:

  1. Send a SEGV signal to the process that made the request.
  2. Install a mapping (make a change to the page table), and then restart the instruction that made the request.

Installing a mapping:

int swapmap(proc, va){
	return disk address or FAIL;
}

void pfault(va, atype, context){
	if(swapmap(current, va) == FAIL)
		kill(current, SEGV);
	else{	// Select a page to swap out
		p, va' = removalpolicy();
		pa = p-> pmap(va);
		write pa to disk at swapmap(p, va');
		p->pmap(va') = FAULT;
		read pa from disk at swapmap(current, va);
		current->pmap(va) = pa;	
	}
}

Problems:

Other optimizations