Locality of Reference
Well structured programs obey the principle of locality of reference. What this means is that the address references generated by a process tend to cluster within narrow ranges which are likely to be contained in a few pages. The implications of this is that the needs of a process over a period of time can be satisfied by having a small number of resident pages (not necessarily adjacent). This situation leads to a relatively small number of page faults. The set of pages that a process is currently using, at this stage is called its working set. If the entire working set is in memory, the process will run without incurring many page faults until it moves into another execution phase. At different stages of the processes execution there will be different working sets in memory.
If the available memory is to small to hold the working set, the process will run slowly as it incurs many page faults. It is possible that a situation can arise where a page swapped out of memory can be needed almost immediately – this can lead to a condition called thrashing , where the processor spends most of its time swapping pages rather than executing instructions.
In a multiprogramming system process are often moved to disk to let other processes have a turn on the CPU. When the process is again scheduled for running a question arises as to what pages to bring into memory. Many systems try to keep track of the working set of each process, in order that all the pages belonging to the set can be brought in their entirety. This eliminates the numerous costly page faults that would occur.
Because the working set varies slowly with time it is possible to make a reasonable assumption as to which pages will be needed when the program is restarted on the basis of its working set when it was suspended.
Multi-Level Page Table Motivation:
The problem with page tables was that they could take up too much memory to store them.
Consider a process on a system with a 32 bit virtual address space…
It will be laid out as follows in its virtual space:
The program always starts at virtual address 0.
The heap always starts on then first page boundary after the end of the program.
The stack always starts at the 4 GB mark and works its way down.