Hardware Reference
In-Depth Information
However, small pages also have the advantage that if the working set consists
of a large number of small, separated regions in the virtual address space, there
may be less thrashing with a small page size than with a big one. For example,
consider a 10,000
10,000 matrix,
A
, stored with
A
[1, 1],
A
[2, 1],
A
[3, 1], and so
on, in consecutive 8-byte words. This column-ordered storage means that the ele-
ments of row 1,
A
[1, 1],
A
[1, 2],
A
[1, 3], and so on, will begin 80,000 bytes apart.
A program performing an extensive calculation on all the elements of this row
would use 10,000 regions, each separated from the next one by 79,992 bytes. If
the page size were 8 KB, a total storage of 80 MB would be needed to hold all the
pages being used.
On the other hand, a page size of 1 KB would require only 10 MB of RAM to
hold all the pages. If the available memory were 32 MB, with an 8-KB page size,
the program would thrash, but with a 1-KB page size it would not. All things con-
sidered, the trend is toward larger page sizes. In practice, 4 KB is the minimum
these days.
×
The virtual memory discussed above is one-dimensional because the virtual
addresses go from 0 to some maximum address, one address after another. For
many problems, having two or more separate virtual address spaces may be much
better than having only one. For example, a compiler might have many tables that
are built up as compilation proceeds, including
1. The symbol table, containing the names and attributes of variables.
2. The source text being saved for the printed listing.
3. A table containing all the integer and floating-point constants used.
4. The parse tree, containing the syntactic analysis of the program.
5. The stack used for procedure calls within the compiler.
Each of the first four tables grows continuously as compilation proceeds. The last
one grows and shrinks in unpredictable ways during compilation. In a one-dimen-
sional memory, these five tables would have to be allocated as contiguous chunks
of virtual address space, as in Fig. 6-7.
Consider what happens if a program has an exceptionally large number of vari-
ables. The chunk of address space allocated for the symbol table may fill up, even
if there is lots of room in the other tables. The compiler could, of course, simply
issue a message saying that the compilation cannot continue due to too many vari-
ables, but doing so does not seem very sporting when unused space is left in the
other tables.
Another possibility is to have the compiler play Robin Hood, taking space
from the tables with much room and giving it to the tables with little room. This
