Memory System Design II - Fundamentals of Computer Organization and Architecture - page 148

It should be noted that Intel's Pentium 4 processor has a 36-bit address bus, which
allows for a maximum main memory size of 64 GB. According to Intel's specifica-
tions, the virtual memory is 64 TB (65,528 GB). This increases the processor's
memory access space from 2 36 to 2 46 bytes. This is to be compared to the PowerPC
604 which has two 12-entry, two-way set-associative translation look-aside buffers
(TLBs): one for instructions and the other for data. The virtual memory space is
therefore 2 52 4 Peta-bytes.

¼ ¼

7.2.5. Replacement Algorithms (Policies)

Basic to the implementation of virtual memory is the concept of demand paging.
This means that the operating system, and not the programmer, controls the swap-
ping of pages in and out of main memory as they are required by the active pro-
cesses. When a process needs a nonresident page, the operating system must
decide which resident page is to be replaced by the requested page. The technique
used in the virtual memory that makes this decision is called the replacement policy.
There exists a number of possible replacement mechanisms. The main objective
in all these mechanisms is to select for removal the page that expectedly will not be
referenced in the near future.

Random Replacement According to this replacement policy, a page is selected
randomly for replacement. This is the simplest replacement mechanism. It can be
implemented using a pseudo-random number generator that generates numbers
that correspond to all possible page frames. At the time of replacement, the
random number generated will indicate the page frame that must be replaced.
Although simple, this technique may not result in efficient use of the main
memory, that is, a low hit ratio h. Random replacement has been used in the Intel
i860 family of RISC processor.

First-In-First-Out (FIFO) Replacement According to this replacement policy,

the page that was loaded before all the others in the main memory is selected for
replacement. The basis for page replacement in this technique is the time spent
by a given page residing in the main memory regardless of the pattern of usage of
that page. This technique is also simple. However, it is expected to result in accep-
table performance, measured in terms of the main memory hit ratio, if the page refer-
ences made by the processor are in strict sequential order. To illustrate the use of the
FIFO mechanism, we offer the following example.

Example Consider the following reference string of pages made by a processor:

6, 7, 8, 9, 7, 8, 9, 10, 8, 9, 10. In particular, consider two cases: (a) the number of
page frames allocated in the main memory is TWO and (b) the number of page
frames allocated are THREE. Figure 7.13 illustrates a trace of the reference string
for the two cases. As can be seen from the figure, when the number of page
frames is TWO, there were 11 page faults (these are shown in bold in the figure).
When the number of page frames is increased to THREE, the number of page