CS 111: Operating Systems (Spring 2013)

 Lecture 15: Virtual Memory (continued) and Caching Policies

Week 8: Thursday (May 23^rd)

Table of Contents:

1.     Page Based Memory Management (cont.)

a.     Linear Page Tables

b.     Two-Level Page Tables

c.      Page Faulting

2.     Tuning Virtual Memory Performance

3.     Caching Policies

a.     FIFO

b.     Optimal/Oracle

c.      LRU

4.     Virtual Memory and Apache

1) Page Based Memory Management:

·       Linear Page Table

o   With linear tables, the MMU (Memory Management Unit) splits a virtual address into page number and page offset components, and this page number is used to index into an array of page table entries. The actual physical address is the concatenation of the page frame number in the page table entry and the page offset of the virtual address.

o   To put it in simple words, a linear page table is used to map virtual memory to the physical memory. This works by acquiring the virtual block number, which act like pointers, to look up the appropriate physical block in the page table. Each entry in the page table is called a “page table entry” and holds an integer that .denotes a physical block. The leading bit in the entry denotes whether the page is actually in physical memory.

o   As the picture denotes, Pages in x86 are 4MiB big and virtual addresses are split up with the first 20 bits being the page table lookup and the last 12 bits being extra data bits. So each process has its own page table with 2^22 entries and each entry is 4 bytes long.

phys_page p = pmap(virt_page);

int pmap(int v){

return PAGE_TABLE[v];

}

·       2 – Level Page Table

o   x86 supports an approach to improve the memory usage of the linear page table called the two level page tables. It is similar to the way inodes hold indirect blocks to point to more data. As the name suggests it’s is “two” level page table, which means there are two levels. Just like how the inodes hold indirect blocks, the top level entries map point to the lower page entries which map to the physical block. The virtual address is split up to have equal bits to denoting Hi and Lo, and the rest of bits perform the same tasks as the linear page table.

o   Basically, we added an extra level of indirection. These Hi and Lo secondary tables allow for more efficient use of memory.

o   The code to obtain the mapping is much more difficult, comparatively, to linear page table.

C code to model how hardware acts:

c)   Page Swapping and Faulting

o   Page Swapping

•   Due to memory requirements, processes will eventually fill up their RAM and their page tables with pages. This raises the question of “what happens when I run out of RAM?” In order to work around this we make the program think it has more memory than it actually does by reserving an area called “Swap Space.” This area holds a copy of the virtual memory used by the current processes. Main memory is used as a cache for the processes, so when a running process needs a page that is not in the cache, the OS grabs it from the swap space. In turn, the page replaced by just grabbed one gets placed into swap space. This is called a page fault.
• ·         Virtual memory “lives” on disk in swap space on Linux

o   Page Faults

• A page fault happens when the program needs a page that it doesn’t have in RAM we do a page fault in order to grab the page from swap space and bring it into main memory (cache for swap space).
• Page faults are very slow because one has to read from disk and sometimes even write to disk.
• When a page fault occurs the application traps and the kernel gets control. From here the kernel can either:
• ·         Terminate process
• ·         Send SIGSEGV to process

            (i.e., set ip to SEGV handler before returning)

• ·         Page fault (page in from disk)

Mechanism for swapping pages in:

RETI then re-executes the instruction

§  Thrashing – If a high proportion of instructions fault, the system is unusably slow. (You thrash, you die!)

•   Want locality of reference.

§  What if the Kernel gets big? Can you use Virtual Memory inside the Kernel?

• ·         Yes, if done with care
• ·         But: Wire down pages that contain memory manage

2) Virtual Memory Tuning

Page faulting is a slow process; here are some suggestions to increase the performance:

• Demand Paging -

Is a method of virtual memory management that follows the idea that pages should only be brought into memory if the executing process demands them. In this system the operating system copies a page into physical memory only if an attempt is made to access it (i.e., if a page fault occurs). No pages exist in the physical memory before the process starts, and many page faults will occur until most of a process's working set of pages is located in physical memory.

• The Dirty Bit -

Situation occurs when a bit in a memory cache or virtual memory page has been changed by a processor, but has yet to be updated in the storage. This dirty bit method acts as a flag that indicates whether an attribute needs to be updated,  it is achieved by designating all the page table entries to 0 at frequent intervals and whenever there is a change we set it to 1. If the bit is 0 when the page is victimized, it is a win for us because we only need to replace it; we can eliminate the time for doing a store for that page, hence it leads to an increase the efficiency and performance of the system.

• ·         Use a good replacement policy.

3. Caching Policy: How to choose the victim?

Depends, if pages are accessed at random, any policy works just as well.

We can choose any page to be the victim, but the memory is normally accessed based on locality of reference. (Note: this "doesn't matter" answer also assumes that every file on disk has an equal cost of access.)

We need to decide which ones to bring to cache (i.e. Physical memory).

a)  FIFO

• In FIFO we victimize the page that has been in the memory for the longest under the assumption that pages get accessed for a short while and then the program loses interest in them. We check it by running lots of applications and getting their reference string (virtual page numbers in the order that the program needed those virtual pages).

Assume 5 virtual pages, 3 physical pages

• In the above case when using FIFO some reference strings actually generate more page faults when more page frames, memory, are allotted. This truly unexpected result was first demonstrated by Belady in 1970 and is known as Belady's Anomaly. This presents a problem with the FIFO caching policy.

    b) Optimal Policy (Oracle Policy)

• Victim = one next used furthest into future (i.e. the page that is not needed for the longest time.

• ·The oracle policy replaces the page that won't be needed for the longest time. This is accomplished by looking into the future to decide which pages we will need and which pages should be replaced. This is the most optimal page replacement policy; however it is not really practical as we cannot see into the future. To demonstrate its efficiency here is the same example as before:

• Assume sequential access:

                            Predict via runs

    d) LRU Policy

• The victim, as the policy’s name suggests, is chosen by finding the page that hasn’t been touched in the longest period of time. This policy is a simple method to achieve results close to the “optimal policy”. An example of the policy in action follows:

• From this example, which results in 10 page faults, one may think that this policy is bad, but this is an extreme example. This reference string was used specifically to show an example of the Belady’s Anamoly, which explains the poor result for the LRU policy.  Typically the LRU policy is better than FIFO policy.
• A Major downside to this policy, however, is that it requires keeping track of when pages were last used, which can prove to be expensive. This is generally kept track of by using “age bits”.

4. Virtual memory and Apache

Originally Apache was made very simply and made use of a very naïve implementation.

To give one an idea, it looked roughly like this:

• ·         Problem: fork() is expensive because it has to copy the entire process state
• ·         Solution: Clone page table instead

            In order to make this faster we don’t copy the entire process, instead we copy the page table. We then make have the permissions set to not be writable, thus preventing us from accidentally altering both process files. When we want to alter some data we copy only the page we want to alter, and then make the parent point to one version with the ability to write to it and have the child point to the other copy with the ability to write to it. All other data does not have permission to write. This is depicted in the diagram below:

• ·         One could also use Vfork() instead of a regular fork() for the implementation.
• ·         Vfork() is like fork(), but parent is frozen until child exits or executes + child might stamp on parent’s memory