Locality

The principle of locality states that during phases of execution, a program requires a small subset of virtual pages. The set of pages used during a phase is the locality set of that phase [D3].

A programmer can observe the locality sets of a program in a phase diagram as seen here. Diagrams such as this were used by early programers to create overlay systems.

This diagram shows which segments are located in main memory during a particular phase of execution. Notice that phases are not uniform in length.

Phases of a program can be arbitrarily defined based on observation of a reference string. Consider the reference string

Programmer could observe phases that would yield either of these phase diagrams.

In the first phase diagram, each locality set contains only one page. This example does not take advantage of the "clustering" of pages implied in the locality principle. In actual operation, the system would spend a great deal of time swapping pages in and out of main memory. At the opposite extreme, the second example shows one locality set containing all pages requested by the program. While no time would be spent swapping pages, is it realistic to assume that an entire program could fit in main memory? After all, what is the motivation for virtual memory?

Now look at the paging behavior of a real program.

The next demonstration lets you look at phase diagrams for examples of algorithms.

Click on the workbench button for the locality demonstration.