Lecture 15
Ryan Chalman and Phillip Vong
Linear Page Tables
Entries in the page table (called virtual addresses) are 32 bits long, with the first 20 bits being the virtual page number (or vpn) and the last 12 bits as the offset into the page.
- The size of the page table is 222 Bytes, or 4MB
- For virtual space this is 232 Bytes, or 4GB
- 1/1000th of total space goes to the page table
If you have 100 processes, however, this becomes 10%.
To fix this, we use a 2-level page table. Entries are still 32 bits, with the first 10 bits being the vpn of the top level, and the second 10 bits the vpn of the second level table. The last 12 bits remain the offset.
In this way, if you have a small process, most of the top level entries will be 0.
C code to model how the hardware behaves
int pmap(int vpn)
{
int hi = vpn >>10;
int lo = vpn & (1<<10)-1;
int *page2 = PAGE_TABLE[hi];
if(page2 == FAULT)
return FAULT;
return page2[lo];
}
When a page fault occurs, there is a trap and the kernel gains control.
Kernel can:
- Terminate the process
- Send SIGSEGV to the process
- i.e. set the instruction pointer to the SEGV handler before returning
- Page fault
- If the kernel can't find the virtual page, the OS looks on disk to see if it's there, it can then copy the page into RAM from disk.
Virtual memory "lives" on disk.
- On linux, this is in the swap space
Mechanism for Swapping Pages In
long long swapmap(proc, vpn) {
return the disk address or FAIL
}
void pfault(proc, vpn) {
long long da = swapmap(proc, vpn);
if(da == FAIL)
kill(proc);
else{
(vicproc, vicpn) = page_removal_policy();
pa = vicproc->pmap(vicpn);
write from pa for 4KB to swapmap(vicproc, vicpn);
vicproc->pmap(vicpn) = FAULT;
read into pa for 4KB from da;
proc->pmap(vpn) = pa;
}
}
Thrashing
If you have a high proportion of instructions fault, the system becomes unusably slow.
We want locality of reference, which is found in small processes.
What if the kernel gets big?
Can you use virtual memory inside the kernel?
- Yes, if done with care.
- If you trap in the kernel, never pick as a victim the memory handler itself. Make sure to wire these pages down
Aside: Size of Swap Space
If we have a high locality of reference we can expand the size of the swap space, because our RAM can handle it.
If we have a low locality of reference there is no point (because the system will be slow), so the swap space can be small or non-existent.
Performance Suggestions
- pfault: don't write out unmodified pages
- We need a 'dirty bit' to tell if a page has been modified.
- Hardware can maintain one in the page table entry.
- However we can also do it in software.
- A page is read only initially, then trap due to a write, the kernel sets the dirty bit and makes the page writable
- Demand Paging
- Only read in the first program pages into RAM, and then let it run until another page is needed
- This method wins if you need just a few pages.
- Can increase the overall cost for large programs, though
- Use a good page replacement policy.
- Policy: How to choose a victim?
- If pages are accessed at random, then any policy works.
- FIFO: The victim is the oldest serving page.
FIFO example:
| |
Virtual Page |
| Physical Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
| A |
0 |
0 |
0 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
| B |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
2 |
2 |
2 |
| C |
|
|
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
3 |
3 |
In this example there are 9 page faults.
If we add more RAM, we should get less page faults, right? Here is an example of this:
| |
Virtual Page |
| Physical Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
4 |
4 |
4 |
3 |
3 |
| B |
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
4 |
| C |
|
|
2 |
2 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
| D |
|
|
|
3 |
3 |
3 |
3 |
3 |
3 |
2 |
2 |
2 |
In this example there are 10 page faults, even though we added more RAM. This is called Belady's Anomaly.
Most of the time adding more RAM will cause less page faults, however it is possible, as this example shows, for it to slow down and cause more page faults.
Now an example using the optimal policy, where the victim is the page next used furthest in the future.
| |
Virtual Page |
| Physical Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
| A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
3 |
| B |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| C |
|
|
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
This optimal policy gives 7 page faults.
However, this policy requires that we know exactly when each page will next be accessed, which isn't usually the case in real world scenarios.
Now an example using Least Recently Used (LRU) Policy
- We implement this by keeping a clock value in each page table entry
| |
Virtual Page |
| Physical Page |
0 |
1 |
2 |
3 |
0 |
1 |
4 |
0 |
1 |
2 |
3 |
4 |
| A |
0 |
0 |
0 |
3 |
3 |
3 |
4 |
4 |
4 |
2 |
2 |
2 |
| B |
|
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
| C |
|
|
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
4 |
This method gives 10 page faults again.
VM and Apache
Simple C code representing these would look like:
socket(...)
bind(...)
listen(...)
for(;;) {
fd = accept();
read(fd);
handle_request(fd);
close(fd);
}
However this is very naive. Here is a better for loop:
for(;;){
fd = accept();
if(fork() == 0){
read(fd);
handle_request(fd);
close(fd);
}
The problem with this: fork() is expensive. Have to copy the process' state, including the page table and data.
Let's speed this up by only copying the page tables.
With this method we will have two different page tables, both pointing to the same data.
We will only copy part of the data when the parent or child wants to edit it.
vfork();
- Like fork, but the parent is frozen until the child exits or execs.
- Child might stomp on parents' memory.