I am reading Operating systems from the book "Operating System Concepts" by Peter Baer Galvin, 7th edition.

Performance of Demand Paging:

Let p be the probability of a page fault (0 $\leqslant$ p $\leqslant$1). We would expect p to be close to zero—that is, we would expect to have only a few page faults. The effective access time is then effective access time = (1 - p) x ma + p x page fault time.

To compute the effective access time, we must know how much time is needed to service a page fault.

Example If we take an average page-fault service time of 8 milliseconds and a memory-access time of 200 nanoseconds, then the effective access time in nanoseconds is

effective access time = (1 - p) x (200) + p (8 milliseconds)

= (1 - p) x 200 + p x 8.00(1000

= 200 + 7,999,800 x p.

My doubt when there is a page table hit it we should multiply p by (ma + ma) because, we need one memory access to access page table from memory and one more memory access to access the actual page from memory. In my opinion formula should be effective access time = (1 - p)x(ma+ma) + p x page fault time.

Where ma is memory access time

Please let me where am I wrong?


1 Answer 1


CPUs keep in special purpose caches recently addressed page table entries. Entries are usually named "TLB = Translation Lookaside Buffer"

We have 3 cases :

  • The page is in TLBs and the access is allowed (no write in read-only areas, no user access in supervisor pages, etc...). The delay to access the TLBs is usually hidden through pipelining. The access time depends on whether data is in caches or not. Can be less than 1ns on current high performance CPUs.

  • The page is not in TLBs. The CPU must find a way to update the TLBs. Some do it with simple hardware mechanisms, others use exceptions and let software do the work. In both cases, one or more memory accesses to pages tables is needed. 8ms is far too much for such operations which have a huge impact on CPU performance. This is not really "page faults"

  • The page may be in the TLBs, or not, but there is a real "page fault", for example the memory accessed has been swapped to disk, or not yet initialized, or the applications has a bug... The operating system will need to do complex thing to correct that, loading memory and updating page tables, or killing the applications... 8ms seems a reasonable delay for some of these operations.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.