By Saurabh Davala
A page fault is when a page cannot be accessible, most likely when a page is not accesible in RAM and a trap is issued. As a result control is granted to the OS kernel. At this point onwards the kernel is responisble in dealing with the page fault. We assume that the kernel keeps track of the current pages in use.
A rough implementation of page fault handling is detailed below:
/*Variables:
*va is virtual addr
*off_t is offset
*accesstype tells if read/write
*/
off_t swapmap(proc, va) { //Kernel supplied function
return disk_address for page or fail (if bad address)
}
pfault(proc, vpn, accesstype) { //Invoked during a page fault
off_t disk_addr = swapmap(proc, vpn);
if(disk_addr == FAIL) { //If address is bad
kill(proc, SIGSEGV)
}
else {
/* General pseudocode for selecting a victim page with kernel policy
*
* Look at physical memory (divided into pages)
* If system is running for long time, there will be no free memory
* Ideally we hope that all pages are in use as this means we are getting the most out of our memory.
*
* Pages abstract layout: | | | | | | | |
*
* Look through pages, and find victim (ex find page from program that hasn't been running)
* Picking a victim is a policy decision not a mechanism decision.
*
* procv, vpn, ppnv = removal_policy() //returns a physical page number (ppn) physical addresses in actual memory, physical page number of the victim
*
* Save victim's data off into secondary storage
* copy new data into physical memory
*
* write physical memory to disk, swapmap(procv, vpn) //After figure out whos victim, save victim to disk, area is free
* readpageatppnFromDisc: swapmap(ppnv, disk address)
*
* Need to update procs page table so that the virtual page number points, also udpate the victims page table
* vpn = ppnv
* vpnv = 0;
*/
}
}
Use large sized pages (Mb sized pages)
Demand Paging
When a program starts up don't read from RAM and jump to first location in memory, just read program's first page into ram and then jump to it and other necessary pages.
Advantages with this approach: improves latency, time to start program to time it starts to do work, improve the wait time (decreases)
Disadvantages: More page faults during execution
Assume:
N = number of pages in program
U = number of pages used in this run
C = cost of reading a page
F = cost of faulting
0 < U < N
no depand paging
then total cost = N*C
latency cost = N*C
If use demand paging
latency cost = C
then total cost = U(C + F) - F //Very first page dont pay cost for -F
Dirty Bits
ppn |rwxd | Ideally the hardware will maintain the dirtybit exploit write bit to implement dirty bit in software make write bit 0
So far talking about mechanisms, look at policy. From policy perspective, assume that mechanism works
How to pick victim (which page to choose)
FIFO (first in first out)
Analyze trace: (sequences of vpn's) corresponing to applications behavior
Ex of trace
Sample 5 virtual pages
0 1 2 3 0 1 4 0 1 2 3 4
FIFO:
0 1 2 3 0 1 4 0 1 2 3
A .0 0 0 .3 3 3 .4 4 4 4 4
B . .1 1 0 0 0 0 0 .2 2 2
C . . .2 2 2 .1 1 1 1 1 .3
Total cost with this method is 9 page faults
If we take hardware approach and try with 4 virtual pages instead of 3
0 1 2 3 0 1 4 0 1 2 3 4
A 0 0 0 0 0 0...
B 1 1 1 1 1...
C 2 2 2 2...
D 3 3 3...
The overall cost is 10 Page Faults! More than with 3 virtual pages.
Exploring LRU
0 1 2 3 0 1 4 0 1 2 3 4
A 0 0 0 0 0 0 0 0 0 2 2 2
B . .1 1 1 1 1 1 1 1 1 3 3
C . .2 .2 2 3 3 3 4 4 4 4 4
With the above example 7 page faults is the optimal result
Lru mechanism: each page table entry has a timestamp for last time used
Distributed Systems (RPC: Remote Procedure Calls)
RPC are to distributed systems as system calls (API open() /ABI int...) are to kernel and they present the illusion to user that they're calling a function.
How rpc differ than kernel:
caller and callee are on different machine and do not share same address space
advantage: hard mouldatiy for free, cons: performance
No call by reference (cant pass a pointer) only call by value
caller and calee may have different architectures:
x86-64 little endian
sparc 64 big -endian
To resolve endinaness problems
1. polite sender approach: sender transmits data in the form recipient prefers
2. rude sender approach: sender transmits data in own format
3. standardize 1 or 2, ex everyone speaks english