The basic idea of Virtual Memory is to allow a program to live fragmented on disk and use RAM as a cache for disk, while giving the program the impression that it has contiguous working memory. The OS keeps track of where the actual data is stored through Page Tables; it hides the inactive parts on disk and puts the most active ones in RAM.
(+) Lets you run programs that are “too big” for Physical RAM.
(-) fetching stuff from disk is slow.
(-) Can’t use VM with real time applications!
This works only if you have excellent locality of reference. Why? Access to disk is REALLY slow, performance would be unacceptable.
Virtual memory was developed in approximately 1959-1962 at the University of Manchester. It wasn’t until 1962 when an IBM research team showed that the virtual memory overlay system consistently worked better than the best manually controlled systems, that VM was used in commercial computers.
Heap will continue to grow until it hits a ‘break’. To add more data space to the heap, use sbrk() (i.e. sbrk(1000) will add 1000 to break).
- Traditional Unix model: 2 pairs of base + boundary registers where used. These stored the top of the stack and a break, respectively. When this approach was used, no virtual memory was needed.
- Page-based model: Divide the virtual address space of an application program into pages. A page is a block of contiguous virtual memory addresses. These pages are usually 4K bytes in size.
o To fiddle with your page tables, use mmap(). The required arguments are a block of memory’s start address, it’s size, an access flag, a file descriptor, and an offset into the file.
o With mmap you can make a change at any location in your space. The traditional model only lets you change the heap boundary.
- Limits on how big your program can get:
1. Disk space: it doesn’t matter if you have virtual memory, if you run out of space you are done.
2. Virtual address space.
3. Page table entries. For example, you may decide that your program will only support small space entry tables.
4. Hardware may ignore top (or "useless bits") in addresses.
5. Operating system limits. Use $ ulimit -a on a linux machine to see your operating system limits.
Basic Idea: Inside the kernel you keep track of processes and a mapping of their virtual addresses. It is done by page tables that translate the virtual addresses seen by the application program into physical addresses used by the hardware to process instructions. Each entry in a page table contains: the starting address of the page; either the real memory address at which the page is actually stored or an indicator that the page is currently held in a disk file.
Traditionally, kernel was kept in RAM. Today, we don’t take this approach anymore because kernels are too big. Instead, what we do is keep a subset of the kernel in RAM.
Kernel Functions:
swapmap(proc, va) {
returns disk address or FAIL;
}pfault(va,...) {
if(swapmap(current, va) == FAIL)) kill(current);
else {
(p, va') = removal_policy();
pa = p->pmap(va');
Write pa to disk at swapmap(p,va');
Read pa from disk at swapmap(current,va);
p->pmap(va') = NULL;
current->pmap(va)=pa;
}
}We must guarantee that this code does not get swapped out by wiring it down.
When a page fault occurs and there are no free pages in primary memory, a multilevel memory manager must choose a "victim" page to replace. The algorithm used to decide which page to remove from primary memory is called the page replacement policy.
Choosing Which Page to Remove
Choosing which page to remove from primary memory depends on how memory is accessed. There are two possibilities:
- Memory access is random
In this case any page replacement policy will do. However most applications do not make memory accesses at random.
- Memory access has locality of reference
Most applications have locality of reference meaning the memory references they make are to a small set of addresses for a significant period of time. There are two ways for an application to exhibit locality of reference:
- Temporal locality:
The application makes several closely-spaced references to the same address (i.e. applications often execute a loop resulting in repeated references to the same set of instructions).
- Spatial locality:
The application makes several closely-spaced references to adjacent addresses (i.e. a programs code is a sequence of instructions that are often stored in adjacent memory cells).
If an application exhibits locality of reference then a designer can implement a page replacement policiy that exploits this property.
Analyzing Page Replacement Policies
Operating System designers can instrument their software and hardware to maintain a trace of the pages referenced by a typical program to be run on the system. After removing adjacent duplicates, page traces can be used to measure the performance of a page replacement policy on a typical workload.
Goal of a Multilevel Memory Manager
The goal of a multilevel memory manager is to minimize the number of page faults. This can be achieved by choosing a page replacement policy with the following characteristics:
- Avoids Belady's anomaly
- Has a hit ratio close to the optimal policy
- Easy to implement
Belady's Anomaly
Belady's Anomaly states that it is possible to have more page faults when increasing the size of primary memory.
Example:
Assume we have:
Page Trace = 0 1 2 3 0 1 4 0 1 2 3 4
Number of pages of RAM = 3
Page replacement policy = First-in first-out (FIFO)
Table:
Page Trace 0 1 2 3 0 1 4 0 1 2 3 4 Page A Content 0 0 0 3 3 3 4 4 4 4 4 4 Page B Content - 1 1 1 0 0 0 0 0 2 2 2 Page C Content - - 2 2 2 1 1 1 1 1 3 3 Page Faults ! ! ! ! ! ! ! - - ! ! - Number of Page Faults = 9
Now assume we have the same trace and page replacement policy but we increase the number of pages of RAM to 4:
Table:
Page Trace 0 1 2 3 0 1 4 0 1 2 3 4 Page A Content 0 0 0 0 0 0 4 4 4 4 3 3 Page B Content - 1 1 1 1 1 1 0 0 0 0 4 Page C Content - - 2 2 2 2 2 2 1 1 1 1 Page D Content - - - 3 3 3 3 3 3 2 2 2 Page Faults ! ! ! ! - - ! ! ! ! ! ! Number of Page Faults = 10!
Although Belady's Anomaly is rare in practice, it demonstrates that the performance of a removal policy can worsen due to an increase in RAM size. Thus it is best to chose a removal policy that avoids Belady's Anomaly (such as LRU).
Optimal Page Removal Policy
The optimal algorithm will always chose the page that will not be needed for the longest time.
Example)
Assume we have:
Page Trace = 0 1 2 3 0 1 4 0 1 2 3 4
Number of pages of RAM = 3
Table:
Page Trace 0 1 2 3 0 1 4 0 1 2 3 4 Page A Content 0 0 0 0 0 0 0 0 0 2 3 3 Page B Content - 1 1 1 1 1 1 1 1 1 1 1 Page C Content - - 2 3 3 3 4 4 4 4 4 4 Page Faults ! ! ! ! - - ! - - ! ! - Best Possible Number of Page Faults = 7
Although it is impossible to implement the optimal page removal policy without an oracle, it is still useful to compare its performance to other page removal policies.
Least Recently Used (LRU)
LRU assumes that the longer the time since a page has been used, the less likely it will be used again soon.
Example)
Assume the same page trace and number of pages as before.
Table:
Page Trace 0 1 2 3 0 1 4 0 1 2 3 4 Page A Content 0 0 0 3 3 3 4 4 4 2 2 2 Page B Content - 1 1 1 0 0 0 0 0 0 3 3 Page C Content - - 2 2 2 1 1 1 1 1 1 4 Page Faults ! ! ! ! ! ! ! - - ! ! ! Number of Page Faults = 10
Although the number of page faults on this trace was higher for LRU then it was for FIFO, LRU has an average performance on a wide class of applications that is close to the optimal policy. Also LRU avoids Belady's Anomaly which FIFO does not.
- Don't write "victim" pages back to disk that have not been changed.
Implementation Options:
Keep a spare copy of each page in RAM that is never written to and compare the copies before removing a page.
Disadvantage:
Costly in terms of RAM space and time.Keep a checksum of pages in RAM.
Disadvantages:
Can result in false hits
Costly in terms of time to calculate and RAM spaceMake pages read-only until the first write.
On the first write a page fault will occur and the kernels page fault handler can set the page to writable.Hardware support
Use a dirty bit to keep track of which pages have been changed.- Demand Paging
Demand paging is an implementation of virtual memory systems in which a page is brought into primary memory only if there is an attempt to access it (as oppose to an implementation that loads all of an applications code at the start).
Advantages:
Initial program start up is faster.
Does not load pages that will never be accessed.
Disadvantage:
Slower if page accesses are sequential and are mapped to sequential disk reads- Fast Forking and Virtual Memory
The simplest implementation of fork() would copy the parents entire address space to create the child's address space. Thus it would execute the following steps:
- Clone all pages in the parents address space.
- Clone the parents page table.
- Add table entries for all the newly cloned pages in the new page table.
This is costly due to the time required to copy the pages and the extra RAM space needed. Also since a fork() is often followed by an exec() command the child's address space is often cleared out soon after being created.
Options for faster forking:
Copy-on-write:
Virtual memory can be used to implement a faster forking by using a technique called copy-on-write. Copy-on-write works by cloning pages only when they are written to. Thus it never clones pages that contain code. Copy-on-write would execute the following steps:
- Clone the parents page table.
- Give read-only access to all pages in both the parent and childs page table.
- On a page fault clone the page, add a page entry for it in the processes page table, and give the process write access to the page.
- When only one process refers to a page, give the process write access to the page.
vfork()
Like fork() except the child process shares its address space with the parent process and the parent is frozen until the child calls exec() or exits.