The Effective Access Time Under Demand Paging
Chapter Eighty-Two
Syllabus topic Module 2, "Virtual Memory Management - Performance of Demand Paging"
Pages 328 to 331 of 452
In one line
A page fault costs about eighty thousand times what a memory access costs, so the fault rate, not the fault, is what decides whether a paged system is usable.
The two numbers the sum rests on
| Event | Time | In nanoseconds |
|---|---|---|
| a memory access | 100 nanoseconds | 100 |
| a page fault serviced from disk | about 8 milliseconds | 8,000,000 |
A fault costs 80,000 memory accesses.
8,000,000 / 100 = 80,000
That single ratio is the reason this chapter exists. Nothing else in a computer has a gap of that size between two things that happen in the same program, and every consequence in the next five chapters follows from it.
Where the 8 milliseconds goes
| Part of servicing a fault | Typical time |
|---|---|
| service the page fault interrupt: save state, decide, start the read | 1 to 100 microseconds |
| read the page in from disk | about 8 milliseconds |
| restart the process: take the interrupt, restore state, resume | 1 to 100 microseconds |
The first and third parts are software and can be tuned. The middle part is a disk, and Chapter ninety two explains why it cannot be made much faster: it is a seek, a rotation, and a transfer, and two of those are mechanical.
The formula
With p as the probability that a reference faults:
EAT = (1 - p) × memory access + p × fault service time
p is a probability, not a percentage, and not a count. It is the fraction of all memory references that fault. A question that says "one fault every thousand references" means p = 0.001, and a question that says "a fault rate of 1 per cent" means p = 0.01, which as the table below shows is a machine nobody could use.
Worked, at four fault rates
With a 100 nanosecond memory and an 8 millisecond fault:
| Fault rate p | Working | EAT | Times slower |
|---|---|---|---|
| 0.001, one in a thousand | 0.999 × 100 + 0.001 × 8,000,000 = 99.9 + 8000 = 8,099.9 | 8,099.9 | about 81 |
| 0.0001, one in ten thousand | 0.9999 × 100 + 0.0001 × 8,000,000 = 99.99 + 800 = 899.99 | 899.99 | about 9 |
| 0.00001, one in a hundred thousand | 0.99999 × 100 + 0.00001 × 8,000,000 = 99.999 + 80 = 179.999 | 179.999 | about 1.8 |
| 0.000001, one in a million | 0.999999 × 100 + 0.000001 × 8,000,000 = 99.9999 + 8 = 107.9999 | 107.9999 | about 1.08 |
Read the first row again. One fault in a thousand references, which sounds rare, makes the program eighty one times slower. A program that should take one second takes a minute and twenty one seconds. That is the sentence to write in an answer.
And read the last row. One fault in a million costs 8 per cent. The whole art of the next five chapters is getting the fault rate down to something with six zeroes in it.
The Effective Access Time Under Demand Paging
Solving it backwards
The other way the question comes: what fault rate can we afford? Allow the program to be 10 per cent slower than an unpaged machine, so an effective access time of 110 nanoseconds.
110 = (1 - p) × 100 + p × 8,000,000
110 = 100 + 7,999,900p
7,999,900p = 10
p = 10 / 7,999,900 = 1 / 799,990
Fewer than one fault in 799,990 memory references. That is the answer, and it is worth saying what it means: the program may fault about once in every eight hundred thousand references, which for a program touching memory every few nanoseconds is a handful of faults a second. Demand paging is only usable because programs have locality, and Chapter eighty nine is the measure of that.
When the page thrown out is dirty
The variant a question uses to see whether the formula was understood or memorised. If the frame chosen for the incoming page holds a page that has been modified, it has to be written out before the new one can be read in, so that fault costs two transfers.
Suppose 70 per cent of the pages chosen for replacement are dirty.
average fault = 8,000,000 + 0.7 × 8,000,000 = 8,000,000 + 5,600,000 = 13,600,000
EAT = 0.999 × 100 + 0.001 × 13,600,000 = 99.9 + 13,600 = 13,699.9
13,699.9 nanoseconds, about 137 times slower, against 81 times when nothing has to be written back.
That is what the modify bit of Chapter seventy seven is worth: it lets the operating system pick a clean page when it can, and the difference between 81 and 137 is the whole reason the bit exists. Chapter eighty four uses it again.
Distinctions that carry marks
| The TLB sum, Chapter seventy six | This sum | |
|---|---|---|
| What is missing | a translation, which is in memory | the page itself, which is on disk |
| The penalty | one extra memory access, 100 nanoseconds | a disk access, 8 milliseconds |
| Ratio of penalty to a normal access | about 2 | about 80,000 |
| A rate of 2 per cent | costs 22 per cent | costs 160,000 per cent |
| What the fix is | a small cache of translations | keeping the right pages in memory, which is the rest of this module |
| p | 1 - p | |
|---|---|---|
| Name | the page fault rate | the hit rate |
| Multiplies | the fault service time | the memory access time |
| A good value | 0.000001 or smaller | 0.999999 |
What it does not mean
The 8 milliseconds is not the fault handler's code. Nearly all of it is the disk. The software part is microseconds.
The Effective Access Time Under Demand Paging
A fault rate of 1 per cent is not nearly as good as 0.1 per cent. It is ten times worse, and both are unusable: 800 times slower against 81.
The effective access time is not what one fault costs. It is the average cost of a reference, which is what decides how long the program takes.
A smaller page size does not reduce the fault cost. It reduces the transfer a little and increases the number of faults, which Chapter seventy five compared.
Locality is not an assumption in this sum. The sum takes the fault rate as given. Locality is the reason the rate can be as small as 0.000001 in practice.
Quick revision
- A memory access is 100 nanoseconds; a fault serviced from disk is about 8 milliseconds,
which is 8,000,000 / 100 = 80,000 memory accesses.
- EAT = (1 - p) × memory access + p × fault service time.
- p = 0.001 gives 8,099.9 nanoseconds, about 81 times slower; p = 0.0001 gives
899.99, about 9 times; p = 0.00001 gives 179.999; p = 0.000001 gives 107.9999, only 8 per cent slower.
- For a 10 per cent degradation, 110 nanoseconds is 100 plus 7,999,900p, so
p = 1 / 799,990, fewer than one fault in eight hundred thousand references.
- If a fraction of the replaced pages are dirty, the fault costs two transfers: at 70 per
cent dirty the average fault is 13,600,000 nanoseconds and the EAT at p = 0.001 is 13,699.9, about 137 times slower.
- The modify bit is what lets the system avoid the write-back, and the gap between 81 and 137
times is its worth.
- The fault service time splits into interrupt service and restart, both microseconds, and
the disk read, which is milliseconds.
Test yourself
- How many memory accesses does one page fault cost? 8,000,000 divided by 100, which is
80,000.
- Write the formula for the effective access time under demand paging. EAT = (1 - p) times
the memory access time, plus p times the fault service time.
- Find the EAT for p = 0.001 with a 100 nanosecond memory and an 8 millisecond fault.
0.999 × 100 + 0.001 × 8,000,000 = 99.9 + 8000 = 8,099.9 nanoseconds, about 81 times slower.
- The same machine at one fault in a million. 99.9999 + 8 = 107.9999 nanoseconds, about 8
per cent slower.
- What fault rate keeps the slowdown below 10 per cent? Set 110 against 100 plus 7,999,900p
to get p = 10 / 7,999,900 = 1 / 799,990: fewer than one fault in 799,990 references. 6. Why does a dirty replaced page make a fault dearer, and by how much if 70 per cent are dirty? It must be written out before the new page is read in, so the average fault is 8,000,000 + 0.7 × 8,000,000 = 13,600,000 nanoseconds, and at p = 0.001 the EAT becomes 13,699.9, about 137 times slower.
The Effective Access Time Under Demand Paging
- Where does the 8 milliseconds actually go? Almost entirely into the disk read; servicing
the interrupt and restarting the process are microseconds each.
- Why is this sum so much harsher than the TLB sum? A TLB miss costs one extra memory
access, about twice a normal reference; a page fault costs a disk access, about eighty thousand times a normal reference.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.