Page:The Paging Game.djvu/3

From Wikisource
Jump to navigation Jump to search
This page needs to be proofread.
Vol. 4/No. 7
19 June 74

amount of disk referencing, so that the disk's slower speed won't impede system performance too much.

Real Memory Stretching

(Part I game terms are in parentheses, following their real counterparts.)

Notice that without paging, the total number of bytes (things) that a computer can store is equal to the capacity of its real memory (workshop) alone. With paging, the total number of stored bytes (things) is equal to the real memory (workshop) capacity plus the paging devices (warehouses) capacity plus the disk (dump) capacity. In our case, the approximate figures are:

Total Real Memory (Workshop) 2,000,000 bytes
Total Drum (Warehouse) 7,200,000 bytes
Total Disk (Dump) 100,000,000 bytes
Total Available Memory  
    for All Jobs at  
     Any One Time 109,200,000 bytes

Paged memory is called virtual memory to distinguish it from ordinary (real) memory.

Virtual memory is MUCH cheaper than equal amounts of real memory. Real memory is at least ten times as expensive as drum and disk memory. Consequently, our virtual memory, which consists mostly of drum and disk storage, costs much less than an ordinary, 100-percent real memory of the same size.

PART III

In Part I we invented a game whose rules paralleled the real rules of memory paging; in Part II we gave the real rules. In this part we'll discuss the implications of those rules for programmers who are using a paging machine.

When writing programs, there is only one rule that need be followed:

LOCALIZE YOUR REFERENCES.

What does this mean? It means that you should write your programs so that they refer to storage in as contiguous and non-scattered a way as possible. Let's take a pair of simple FORTRAN examples. We'll exaggerate the severity of the problem for the sake of explanation, then consider a more realistic example later.

Program A:       DIMENSION X(2000)
      X(1)=50.
      X(1999)=40.
      X(2)=30.
      X(2000)=20.
      STOP
      END
Program B:       DIMENSION X(2000)
      X(1)=50.
      X(2)=30.
      X(1999)=40.
      X(2000)=20.
      STOP
      END

Both of these programs do the same thing; Program B does it more efficiently. Why? Let's look at the array X in the context of paging. X is 2000 words long; each word takes 4 bytes, so X requires 8000 bytes of storage. Since each page is 4096 bytes of virtual memory, X takes a bit less than 2 pages. Since the elements of arrays like X are arranged in subscript order, X(1) and X(2) will fall in one page, while X(1999) and X(2000) will fall in another. We can draw a little map of X in storage:

PAGE     *
A
S
C
E

PAGE
X(1)
X(2)
N
D
I
N
G
PAGE
X(1999)
X(2000)    

A
D
D
R
E
S
PAGE S
*

If X starts near the end of a page, the storage map might look like this:

PAGE    
X(1)
X(2)
*
A
S
C
E
PAGE


X(1999)
X(2000)    
N
D
I
N
G
PAGE
A
D
D
R
PAGE E
S
S
*

In either case, X(1) and X(2) will be in a different page from X(1999) and X(2000).

Now, let's see what happens when Program A runs.
Statement/Action
DIMENSION X(2000)

Action: None. DIMENSION is non-executable.

X(1)=50.

Action: X(1) is set to 50. However, the page con-
4