4.2 PAGING BEHAVIOR

The principle of locality means that execution tends to dwell in one region of the process for some time and then passes into another region; only small subsections of a process are active at a time. Another way to state this principle is to say that memory locations that have been recently referenced are likely to be referenced again in the near future. For example, any program is likely to contain several subprograms (C Functions or Pascal PROCEDUREs and FUNCTIONs or FORTRAN SUBROUTINEs and FUNCTIONs, etc.), and within each are looping structures that clear arrays, read data, make computations, and so forth. The process will spend a certain amount of time first looping in one region, then in another. Such behavior is characterized graphically in Figure 4.5a. It shows the value of the program counter (PC) over a given range of time, say 10 milliseconds. The solid ramps represent sequentially executing statements; the dashed discontinuities are caused by subroutine calls, gotos, if-then-else, and case statements. The branch at the bottom of the loop is shown as a dashed line too. Repetitive patterns are caused by loops of one kind or another.

Figure 4.4: Partial layout of an image with an ADDL3 instruction

Horizontal lines represent page boundaries in this model, and the first time a solid path crosses a horizontal line, a page fault occurs. The horizontal scales of the two graphs in Figure 4.5 are identical, so the intersection point is dropped down to the...