# Page size in demand - paging systems

Erol Gelenbe, P Tiberio, J.C.A. Boekhorst

► To cite this version:

Erol Gelenbe, P Tiberio, J.C.A. Boekhorst. Page size in demand - paging systems. [Research Report]
IRIA-RR-014, IRIA. 1973, pp.41. hal-04715975

HAL Id: hal-04715975

https://inria.hal.science/hal-04715975v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Zuv: 01973

RR 14

RIA
laboria

laboratoire de recherche
en informatique
et automatique

Page Size in
Demand- Paging Systems

E. Gelenbe,
P. Tiberio,
J. C. A. Boekhorst

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°14

mars 1973
PAGE SIZE IN DEMAND-PAGING SYSTEMS*

E. Gelenbe, P. Tiberio, J.C.A. Boekhorst

ABSTRACT

The problem of determining page size in a page on demand sys-
tem is discussed in detail in this paper. After having introduced
the problem, the effect page size may have on various system per-
formance measures is reviewed based on measurements of program
behaviour and on simple models of system behaviour.

This discussion is followed by a detailed study of the effect
of the choice of page size on the efficient utilization of primary
memory space. The _wasted space-time integral_ (WSTI) of primary mem-
ory space is selected as a measure of this utilisation and a _new_
model of program and system behaviour is used to compute the WSTI
for different secondary memory devices (drum, ECS and LCS) and
different system behaviour parameters such as the time spent in
supervisor mode by the operating system to initiate a page trans-
fer, the time spent in the CPU queue by a program which has reco-
vered from a page fault before it receives the attention of the
CPU, the global page fault rate (or arrival rate at the secondary
storage devices used for paging) and other factors. The influence
of each of these factors is discussed and analyzed, and the condi-
tions under which one or another of these dominates the problem
is identified.

In the Appendix, one of the problems posed by our model, the
use of approximate formulae for fragmentation which remain valid
for a large class of probability distribution functions of program
size, is analyzed in detail. Some tests are developed for the va-
lidity of these formulae.

* This paper will be presented at the Symposium on Measurement and Evaluation of the Association for Computing Machinery, to be held in Palo Alto (USA) in February 1973, and will be included in the Proceedings published for that symposium.
# 1. INTRODUCTION

1.1. The page size problem

1.2. Summary of previous work

1.3. Outline of the paper

# 2. SYSTEM BEHAVIOUR AND PAGE SIZE

2.1. Fragmentation

2.2. Page fault rate

2.3. Superfluity

2.4. Response time

2.5. CPU utilisation

# 3. THE WASTED SPACE-TIME INTEGRAL AND PAGE SIZE

3.1. System and program behaviour under demand paging

3.2. The wasted space-time integral of primary memory: A model

3.3. Computational examples derived from the model

3.4. Conclusions on factors influencing the choice of page size

# ACKNOWLEDGEMENTS

# APPENDIX

Mathematical analysis of fragmentation
# 1. INTRODUCTION

## 1.1 The page size problem

Demand paged multiprogrammed computer systems have proven successful in time sharing environments with highly unpredictable loads due to their greater flexibility in the allocation of system resources.

One of the basic parameters to be selected in a paged virtual memory system is page size itself. The manner in which this para meter affects global system performance is not fully understood, partly because there has been little opportunity to experiment with variable page sizes in systems. It is known that it affects various secondary performance measures but there has been no sys tematic approach to the selection of page size in a system.

Our curiosity about the choice of page size does not only stem from the fact that this choice simply has to be made in each paged system; the problem is also an interesting and important one in its own right since it introduces us to the different issues involved in the design and management of storage allocation sys tems.

In addition to the intrinsic interest of the page size prob lem for computer system design, it has also gained importance in operating system design due to the availability of systems (the IBM 370 series and MULTICS [1]) in which it is possible to choose one of two page sizes for programs or segments. For such systems, it is of interest to provide guidelines for making this choice.
## 1.2. Summary of previous work

There have been several studies of the effect of page size variation on page fault rate. A summary of some of these effects can be found in the excellent survey paper by Kuck and Lawrie 2.

More recent experimental results can be found in the work of Joseph [3] and Hatfield [4]. Some of these results will be summarized in the next section. Belady [5] has considered the loading into memory of words which will be unutilized as a function of page size, and has reported results of trace driven simulations of this effect. The problems of internal and external fragmentation have been discussed by Randell [6], Wolman [7], Gelenbe, Boekhorst and Kessels [8] and others via simulation experiments and mathematical models. Although several authors [9] have expressed the opinion that smaller page sizes will be more desirable if secondary memory devices faster than the drums or disks commonly used at present are introduced, little hard evidence of this exists either on a theoretical or experimental basis; in fact, we believe that this opinion is not founded and can be misleading in certain cases.

## 1.3. Outline of the paper

The purpose of this paper is to focus on one rather important aspect of the problem page size selection: the influence this choice will have on the efficient utilisation of primary memory resources. The measure which has been selected to reflect this utilisation is the *wasted space-time integral* (WSTI) of primary memory space. As we shall presently see, this measure is influenced by such diverse physical properties as page fault rates, mean time spent by a process in the CPU queue, secondary memory device characteristics, program behaviour and other factors. Therefore in the next section we examine the effect page size has on system performance measures.
In the third section we introduce a model of program and system behaviour which is used to calculate the WST1. The model used is too detailed to allow for simple mathematical results to be obtained for the value of page size minimizing the WST1. Therefore we have chosen to compute the WST1 versus page size, for different sets of relevant parameters and different secondary memory devices.

These examples illustrate the important effect which secondary memory device characteristics, particularly the ratio of access to transfer times, should have on the choice of page size. It will also be shown that under certain conditions, the time spent by a program in the CPU queue after a page fault and "superfluity" [5] can play an important role in the optimal choice of page size.

In the Appendix we analyze mathematically in detail one of the minor, but representative, problems which arise in the model introduced in the paper; namely, the validity of certain simple formulae used to approximate internal and table fragmentation. The limited results given in the Appendix serve to illustrate the difficulty of some of the mathematical problems which arise in system modelling. In particular, we concern ourselves with the class of probability distributions of segment or program size for which these formulae are valid, as well as with tests for verifying that they are valid for given distributions.

## 2. System behaviour and page size

Page size can have an appreciable effect on various aspects of system performance. The main effects are summarized in this section. These effects are to a large extent mutually coupled, producing complex interactions. We shall summarize them under different headings keeping in mind the fact that these effects are not always independent.
## 2.1. Fragmentation and page size

If P is the size of a page, and x is the size of a block to be stored,

$$f(x,P) = \left\lfloor \frac{x}{P} \right\rfloor$$

is the number of cells allocated to the block. This implies that an amount of space:

$$l(x,P) = f(x,P) P - x$$

usually called the internal fragmentation is wasted in one of the cells allocated to the block due to the rounding off effect in allocating an integer number of cells, supposing that $P > 1$. In certain cases, the cells allocated to a block form a linked list so that further space:

$$L(x,P) = b f(x,P)$$

is wasted in pointers, b being the number of storage units (e.g. words) utilised per cell for pointers. In other cases, a table listing all of the pages allocated to a block may be formed for each block stored in memory; in this case:

$$T(x,P) = c f(x,P)$$

is the storage space wasted in a table, per block, if c is the storage space needed per page in the table. In some cases, such as in the time-sharing system MTS [10] implemented on an IBM 360/67 a table is set aside in memory for all of the pages which memory may contain. If memory size is M and if it is a multiple of P, then in this case the table size is:

$$D(P) = c \frac{M}{P}$$

<footnote>(°) [y] is the least integer greater than or equal to y.</footnote>
We see that in all cases, the amount of space wasted in internal fragmentation, in linked list pointers and in cell or page tables depend on $x$ and $P$.

In general it is of interest to be able to estimate the amount of this wasted space, and in certain cases it may be desirable to minimize it.

Very often, dynamic storage allocation system have to accommodate blocks of widely varying length. The values this length may take is often unpredictable and can only be specified on a statistical basis. Thus it is of interest to obtain or predict the average value of this wasted space, in terms of the average value of $x$. Some mathematical problems related to this are discussed in the Appendix.

## 2.2. Page fault rate

In this section we will examine the page fault rate $\lambda$ as a function of primary memory allotment in words $K$, for various values of page size $P$.

We would expect that for small $K$, $\lambda$ will vary considerably with the page size. This is because for small $K$, the average time each page is in primary memory will be relatively short; and so the extra words in larger pages will tend to go unreferenced and will only take up space which might better be occupied by new, smaller pages. On the other hand, as $K$ increases, we would expect to see page size have less effect because the probability will be higher that more words in the page will be referenced due to the longer expected page residence time.

Figure 1 is a graph of $\lambda$ versus $(K,P)$ based on experimental data from a FORTRAN compiler [2]. This graph clearly shows that when a program is run in a smaller memory, large page sizes lead to excessive paging. When the page size is small, then the program tends to be more compressible. As $K$ gets larger, the paging behavior becomes less a function of $P$, and for large enough $K$, small $P$
may even increase the page fault rate. Slight minimum points are observed at the (K,P) points (2K, 64), (4K, 256), (8K, 256). This illustrates that if minima exist, then they are not necessarily independent of K.

Further discussion about this problem can be found in [2].

Madnick [11] has constructed examples of page reference strings for which he shows that if page size is halved, the number of page faults can more than double and in certain cases become far greater than the number for the initial page size. The FIFO anomaly [12] which shows that for certain page reference strings, a larger memory can result in an increase in the number of page faults with the FIFO page replacement algorithm does not prevent installations which use this replacement algorithm from increasing their primary memory capacity each year. Similarly, Madnick's [11] report must be taken with caution.

We reproduce here one of the examples of [11] in Fig. 2. It appears that this effect can be duplicated with different replacement algorithms, including LRU. Hatfield [4] reports that in the simulation of some program traces running in a virtual memory environment, it was observed that halving page size more than doubled the page fault rate.

### 2.3. Superfluity

Another factor which leads to an effective underutilization of primary memory arises from instruction or data words which are loaded into primary memory as part of a page but are never referenced during that period of residency. We will refer to these words as superfluous.

We can obtain a lower bound on the number of superfluous words by examining the total primary memory requirements $M$ of a program as a function of page size. That is, assume primary memory is unlimited, then $M(P)$ is the total amount of primary memory occupied.
pied after a given execution of the program with page size P. Now given unlimited primary memory, if the program is run with page sizes $P = B$ and $P = 1$, then $M(B) - M(1)$ words must be superfluous. If we force the program to run with primary memory $m \le M(B)$, then page faulting will occur and the number of superfluous words may increase over $M(B) - M(1)$ since some words that are eventually referenced are not referenced during some period of their page resi dency and are thus superfluous during that period.

O' Neill [13] and Belady [5] present experimental results on $M(P)$ which indicate that a good approximation is:

$$M(P) = A + B \log_2 P$$

The rule of thumb suggested by Belady [5], and which we shall use, is the following: when page size is halved, the amount of space a program occupies for a given execution is reduced by 10%.

## 2.4. Response time

Since one can expect changes in page fault rates of programs as a function of page size, it is of interest to examine, even if in a very approximate manner, the effect page size might have on the response time of a user.

For this we turn to an expression for turnaround time $W$:

$$W = C + 1 + \frac{C}{e(k)} \cdot T_s$$

where $C$ and $1$ are the computation and input-output time, respectively, of the program and $T_s$ is the time necessary to obtain a page from secondary storage. $e(k)$ is the average time between page faults for a primary memory space of size $k$ allocated to the prog
ram. The page fault rate for a given value of k is then a function of P:

$$ \lambda = \frac{1}{e(k)} = \lambda(P) $$

T_s too is a function of P. We shall suppose that the secondary storage device can be adequately modelled by an M/D/1 queue in which interarrival times are independent exponentially distributed random variables with arrival rate λ and the service discipline is a constant service time of the form Pz where z is a constant. This service time is valid for a secondary memory device such as slow core, and is also a reasonable approximation to a sectored paging drum with a heavy load [14] (°).

With these assumptions we have that:

$$ T_s = Z \left[ 1 + \frac{\lambda' z P}{2 (1 - \lambda' z P)} \right] $$

under the condition that the queue is not saturated:

$$ 1 > \lambda' z P $$

Thus we obtain the following expression for turnaround time:

$$ W = C + 1 + C \text{ Z } P \lambda \left[ 1 + \frac{\lambda' z P}{2 (1 - \lambda' z P)} \right] $$

If reducing the page size from P to P/2 roughly doubles the page fault rate, we can write:

$$ \lambda \approx \frac{u}{P}, \quad \lambda' \approx \frac{u'}{P} $$

which, when substituted in the expression for W, yields:

$$ W = C + 1 + C u Z \left[ 1 + \frac{u'z}{z(1-u'z)} \right] $$

<footnote>(°) In that case Z is the time for one complete drum revolution and λ' is the arrival rate to one of the sector queues.</footnote>
which is independent of P. If the page fault rate more than doubles when the page size is halved, we would expect an adverse effect on response time with smaller page sizes and a better one with larger page sizes, up to a certain limit of course. If, on the other hand, $\lambda$ is approximately independent of page size then reducing the page size can actually improve the response time; the improvement with smaller page sizes will be limited by access or latency time of the secondary memory device where it exists. Other similar latency effects will be observed if supervisor time or CPU queueing time is appreciable.

## 2.5. CPU utilization

let the processor demand of a program in the system be denoted by :

$$ \eta = \frac{1}{1 + \mu T_1 + \lambda T_s} $$

where $\lambda$ and $T_s$ are as defined above. $\mu$ and $T_1$ are the input-output put request rate and the average transfer time per input-output transaction, respectively, excluding page faults. $\eta$ may be considered as being the probability that a given program is at the CPU. We may then write CPU utilisation $\eta_s$ as the probability that none of the d programs in memory (the degree of multiprogramming) demands the processor, or :

$$ \eta_s = 1 - (1 - \eta)^d $$

so that :

$$ \eta_s = 1 - \left(1 - \frac{1}{1 + \mu T_1 + \lambda T_s}\right)^d $$

Using the same discussion of the variation of page faults rates with page size, we see that $\eta_s$ will be relatively independent of page size if the average time between page faults increases linearly with page size; if this increase is faster than
linear, then reducing page size will result in a lower CPU utilization. If the page fault rate is relatively independent of page size, as is observed in Fig. 1 for programs operating with a larger amount of memory space, then reducing page size can be expected to improve CPU utilization in the system with secondary memory devices for which access time is relatively unimportant. The assumption in this discussion is that input-output request rate $\mu$ and the average transfer time per input-output transaction $T_1$ are not appreciably affected by page size.

### 3. THE WASTED SPACE-TIME INTEGRAL AND PAGE SIZE

If we examine the different effects of page size on system performance, and the utilization of installed memory resources, we see that these effects are interrelated. For instance although the measurements of page fault rate reported in the previous section do not take it into consideration explicitly, internal and table fragmentation will also influence page fault rates of programs by reducing the memory space available for their execution. If we examine the various effects mentioned, we can see that they can be classified as effects on wasted space (fragmentation and superfluity) and total time in the system (page fault rate). However, the page fault rate conceals another source of wasted space: each time a page fault occurs, all of the primary memory space occupied by a program is not available for computation and thus is in this sense "wasted" until the page is brought in. Thus, if one considers the effect of page size on the efficient utilization of installed memory resources one should use as a measure a *wasted space-time integral* (WSTI) taking these various effects into consideration.

In the sequel we shall derive the WSTI from models of prog ram behaviour based on measured data.

In Fig. 3, the number of distinct words referenced by a prog
ram in a given amount of execution time has been plotted versus execution time. This behaviour has been indicated by a several measurements, including [15]. The program, generates references at a rapid and nearly constant rate until it reaches the "elbow" of the curve; at that point the rate of referencing progressively slows down until it reaches a constant (nearly zero) rate of referencing new words. Our model of program behaviour is based on this characteristic: we assume that the page fault rate varies linearly with page size up to the elbow of the curve in Fig.3 and is independent of page size to the right of the elbow.

### 3.1. System and program behaviour

In the framework of multiprogrammed computer systems the execution of a program is characterized by a repetitive cycle consisting of computation, input-output, and time spent in the CPU queue, in that order. These cycles are interrupted at the end of a *time slice* (a predetermined maximum total CPU time allocated to each program, at the end of which the program has to be rescheduled), or when the program encounters a symbolic STOP statement. During computation, the program is receiving attention of the CPU. The time spent in input-output may consist of a period during which the program communicates with a time-sharing terminal, with files, or other input-output equipment, or the time spent in page wait from secondary storage devices such as drum, large capacity storage (LCS) or extended core storage (ECS). Our concern here is with this last item only. Thus, the programs we are considering are *compute bound*; their behaviour is dominated by their request for the CPU. They are assumed not to possess an input-output activity during their execution. All of their references to secondary memory devices are for paging activity. Although this assumption restricts the validity of our model, an extension to program behaviour including input-output does not appear difficult (°).

<footnote>(°) This aspect of the model is discussed once again in the last section.</footnote>
Page-wait will generally consist of time spent in a queue waiting for the secondary storage device to become available, followed by the time necessary to transfer a page. The magnitude of its effect on overall system performance will depend on the frequency with which page faults occur as opposed to other input-output operations, as well as on the duration of the page-wait.

Each time a page fault occurs, it will be assumed that the system will load the page just referenced from secondary storage into primary memory PM. If the program already occupies the maximum number of pages allotted to it by the system, the incoming page will occupy a page frame previously occupied by another page of the same program. Otherwise it will occupy a page frame without forcing a page of the same program out of primary memory. The time spent in page wait multiplied by the number of pages occupied by the program during page-wait will constitute one part of the wasted-space time integral. The total WSTI will include the effect of internal and table fragmentation [16] (or wasted space due to the "rounding off" effect in assigning an integer number of pages to a program, and the space wasted in page tables indicating the whereabouts of each program page, respectively), as well as the influence of the time between faults.

### 3.2. The WSTI of primary memory: A model

When paging is used the program, starting initially with no pages in PM, generates page faults at a near constant rate (and these are loaded into PM under a demand paging policy) until a number W of pages are in PM. The page fault remains constant there on. If the page size is P, W corresponds to:

$$K = WP \qquad (1)$$

amount of memory space. To simplify the terminology, we shall use a word as the basic memory unit. We assume that the program operates with K words of its address space in PM. From Figure 3 we de
duce that the time between page faults, up to the time when the program has K words in PM, is given by :

$$m = \frac{\alpha P}{K} \qquad (2)$$

After K words have been loaded into PM, the mean time between successive page faults will be M, a constant. Figure 3 reflects the behaviour of the program which is able to require the pages it requests.

When a page fault occurs, the page request is placed in the queue of the secondary memory (SM) as shown in Figure 4, to wait for service. It is assumed that page requests constitute a Poisson arrival process. Although we are tracing the behaviour of a single program, page requests may be generated by each program in the system so that these may be viewed collectively as a random process. Arguments for the validity of results obtained with the Poisson assumption have been made on the basis of measurements on the University of Michigan Time-Sharing System [17] and elsewhere. This assumption simplifies the mathematical model. The service mechanism of the SM queueing system will depend on the SM device chosen. We will consider three devices in this study: drum, LCS, and ECS. We shall discuss the models for these in detail later. For the present, let us denote the time elapsed between a page request and when computation resumes on the program by t.

Let $W_i$ be the number of pages in memory when the i-th page fault occurs. Thus $W_1 = 0$, and

$$W_{i+1} = \begin{cases} W_{i+1} & \text{if } W_i < W \\ W & \text{if } W_i = W \end{cases}$$

We assume that $i = 1$ when the first page of the program is requested. Since the program acquires an extra page frame as soon as a page fault occurs if $W_i < W$, the total WSTL during page faults up to the time that the W-th page is in PM is given by :
$$S_{F1} = \sum_{i=0}^{W-1} (W_i+1) \quad P_t = P_t W \quad (W+1)/2$$

or from (1):

$$S_{F1} = K t \quad (W+1)/2 \quad (3)$$

By this time, the program has a remaining computing time of $(C-\alpha)$ $\ge 0$, during which page faults will occur each M time units. This will give a space-time integral waste of:

$$S_{F2} = k \cdot t \quad (C-\alpha)/M \quad (4)$$

during page faults after W pages have been acquired.

The pagination of a program necessitates keeping a page table (PT) indicating the whereabouts of each program page, for each program. Let x be the program size. Then the PT size is:

$$\left\lfloor \frac{x}{P} \right\rfloor \cdot b \quad (5)$$

where b is a constant. The implicit assumption is made that the virtual memory is not segmented as well as paged, because then each program segment would be paged, rather than the whole program address space of size x. The PT will be maintained in PM throughout the time a program is active. Disregarding the time before the program obtains its first page frame and after it has obtained a total computing time C, the total active period of the program is:

$$\tau = C + Wt + t \quad (C-\alpha)/M \quad (6)$$

so that table fragmentation contributes:

$$S_T = b \quad \frac{x}{P} \quad \tau \quad (7)$$

to the total WST1. Due to the assignment of an integral number of pages to the program, space is wasted in internal fragmentation. This would normally be concentrated in one program page, and is given by:
$$P\left[\frac{x}{P}\right] - x \qquad (8)$$

However, since the times when this page is contained in PM are unknown, it has been assumed that internal fragmentation is distributed among all program pages, so that the amount per page is:

$$\delta = P - x / \left[ \frac{x}{P} \right] \qquad (9)$$

With this assumption, internal fragmentation in PM is proportional to the number of page frames occupied by the program. Its contribution to total WST1 is given by:

$$S_I = \sum_{i=1}^{W-1} i \delta \frac{\alpha P}{K} + (C - \alpha) W \delta \qquad (10)$$

During page-wait the total space occupied by a program is considered to be wasted. Therefore, $S_I$ is only calculated over the computing time. Using (1), (10) is rewritten as:

$$S_I = \frac{\alpha \delta (W-1)}{2} + (C - \alpha) W \delta \qquad (11)$$

The total WST1 for a program whose address space contains x words is then (not considering superfluity):

$$S = S_1 + S_{F1} + S_{F2} + S_T \qquad (12)$$

Let us now examine the time t elapsed from the occurrence of a page fault to resumption of computation (attention of the CPU) to the program. Evidently, this time is a random variable. We shall henceforth use t to denote the average value of this time. t may be written as:

$$t = t_{CPU} + t_{SM} + t_{SUP} \qquad (13)$$

where $t_{SUP}$ is the time the operating system will spend in supervisor activities as a result of the fault, $t_{SM}$ is the time spent waiting for the page, and $t_{CPU}$ is the time the program spends in
the CPU queue waiting for the attention of the CPU after it has received a page.

We assume that $t_{CPU}$ is independent of P. $t_{SM}$ will depend on P, as well as the SM device. Therefore, we examine it for the drum, ECS, and LCS separately. $t_{SUP}$ is also assumed independent of P. Notice that we have not included the effect of "superfluity" in the model. This will be included in the model at a later stage.

The times elapsed between consecutive page faults are assumed to be independent, identically distributed random variables with exponential distribution and mean M so that the arrivals to the SM queue of Figure 4 constitute a Poisson process with parameter 1/M. Thus the ECS and LCS can be modelled as M/D/1 queues (Poisson arrival with constant service time) since they are "random access" devices. For the drum, the M/G/1 queue model will be used.

**Extended Core Storage (ECS).** This is a magnetic core memory equipped with special data transmission facilities which allow it to deliver d words per PM cycle after an initial access time a. Thus, the time to read or write a page is

$$a + \frac{P}{d} c \qquad (14)$$

where c is the PM cycle time. Typically a = 3 µsec, c = 1 µsec, and d = 10 words. Thus, with the assumption that page requests constitute a Poisson arrival process with parameter 1/M, the ECS can be treated as an M/D/1 queue, for which we immediately write:

$$t_{ECS} = \left(a + \frac{P}{d} c\right) \left[ 1 + \frac{\left(a + \frac{P}{d} c\right)/M}{2\left(1 - \left(a + \frac{P}{d} c\right)/M\right)} \right] \quad (15)$$

With an empty queue, we obviously obtain :

$$t_{ECS} = a + \frac{P}{d} c \qquad (16)$$
**Large Capacity Storage.** This is a core memory whose cycle time is considerably lower than that of PM. The time to read or write a page is

$$Pz \qquad (17)$$

where z is a typically 10 usec. It is modelled as an M/D/1 queue so that

$$t_{\text{LOS}} = (Pz) \left[ 1 + \frac{Pz/M}{2(1-Pz/M)} \right] \qquad (18)$$

For an empty queue

$$t_{\text{LOS}} = Pz \qquad (19)$$

**Drum.** The drum considered here is of the sectored type as used in paged systems. Each page is addressed by a sector and track number, and the drum has to be rotated to the proper sector portion for a page read or write. The page requests are placed in a queue corresponding to their sector so that there is a queue for each drum sector. This mechanism can be implemented in software or by some special purpose hardware. Let w be the number of words per track of the drum and let $\delta$ be the time for a complete drum rotation. Then

$$\tau = \frac{P}{w} \delta \qquad (20)$$

is the time necessary for a page read or write after the drum has been positioned. It is assumed that there are N sectors in the drum and that page requests are equally likely to occur for any sector. The service time is obtained via an expression from [14]

$$t_{\text{DRUM}} = \delta \left(\frac{N+2}{2N}\right) + \frac{1}{MN} \left[ \frac{\delta^2 \left(\frac{N+2}{2N}\right)^2}{2\left(1-\delta\left(\frac{N+2}{2N}\right)\frac{1}{MN}\right)} \right] \qquad (21)$$

## Examples

A FORTRAN IV program has been written which to compute S of (12) for different values of page size P, mean time between
faults M, $t_{SUP}$, $t_{CPU}$, and different secondary memory devices as well as program size distributions. Some of the results obtained have been plotted in Figures 5, 6 and 7.

In all three of these figures we have calculated the expected value of S, taking x to be a random variable with Erlang probability density function of mean value 20 K (words). The purpose was to represent a family of programs of different sizes in a system and to compute the average value of S for this class.

The curves in Figures 5,6,7 were plotted for two values of mean time between page faults M (0.1 sec and 0.01 sec) and two values of time spent in the CPU queue $t_{CPU}$ after a program recovery from a page fault (0msec and $0msec$). These parameter values are representative of the values they may take in various systems. The curves have been plotted without taking into account the effect of superfluity; an additional curve has been plotted in each of the figures taking into account the correction, based on the rule of thumb suggested by Belady [5]. We summarize as follows the conclusions which we draw from these examples:

1. In comparing the different components of the WST1, we see that the component $S_T$ representing table fragmentation, which increases as page size is reduced, can be neglected. This is because the WST1 at small page sizes is dominated by the effect of the increase of page faults, hence of $S_{F1}$, for small page sizes. Therefore it is justified to neglect table fragmentation under demand paging as a limitation on the use of small page sizes.

2. For the drum (Fig.5) we see that we are justified in neglecting the effect of superfluity. The advantage of small page sizes due to reduced superfluity cannot compensate for the important increase of $S_{F1}$ for small page sizes. The optimum choice of page size for the drum seems to be situated around 512 or 1K (words) confirming current practice. $t_{CPU}$ in this case does not affect the optimum value of page size.

However, with a mean time between page faults M of 0.1 sec, larger
page sizes (2K words) are preferred. This is an interesting phenomenon which we explain as follows. M represents the global page fault rate in the system: smaller values of M will increase the penalty of a page fault but can be compensated by smaller page size P since the congestion of the drum is both a function of page size and page fault rate. Thus as M increases, larger page sizes are better tolerated.

3. In the curves for LCS (Fig.6) the effect of $t_{CPU}$ is striking. When the time spent in the CPU queue after recovery from a page fault becomes important (8m sec) we see that the WSTI curves for LCS resemble those for the drum in that optimal page size is again of the order of 512 or 1K (words): furthermore, once again superfluity has no appreciable effect in the optimum choice of page size. The situation changes drastically if $t_{CPU} = 0$; now much smaller page sizes of the order of 128 to 256 words are justified, and the effect of superfluity is to further encourage small page sizes.

4. The effect of $t_{CPU}$ is still more apparent with ECS (Fig.7). Very large page sizes (of the order of 2K words) are optimum for $t_{CPU} = 8$m sec and smaller ones, of the order of 256 words, should be chosen for $t_{CPU} = 0$ sec. It is interesting to see that ECS appears less favorable to small page sizes than LCS, even though it is a faster device. This is due to the fact that ECS has an access time which becomes appreciable, in comparison to the transfer time for small page sizes. Furthermore, $t_{SUP}$ (the time spent in supervisor mode to initiate a page transfer) acts as an access time since its magnitude is comparable to the transfer time for ECS.

5. Average program size L and therefore (according to our model) the space K occupied by a program in execution, will influence the value of page size minimizing the WSTI. This is illustrated in Fig.8 in which we have plotted the WSTI versus page size for L = 20K and L = 5K for both drum and ECS. The effect of superfluity has not been taken into consideration since for these two de
vices it does not influence appreciably the page size minimizing
the WST1. We see that smaller page sizes are more suitable for
smaller programs. The reason for this is apparent from a careful
examination of our model. In the model, the number of page faults
increases with decreasing page size up to the point where the prog
ram acquires K words of storage. Therefore if K becomes smaller,
the influence of this effect on the WST1 will be reduced and
smaller page sizes will be favored. This may be an unreliable re
sult derived from our assumptions, which may not be verified if
measurements are made with real programs. More will be said about
this matter below.

6 - It may be worth mentioning that the computational results ob
tained in this study (all of which have not been reported in this
paper) have cost roughly $ 1000 of computer time on the MTS system
at the University of Michigan. This cost is comparable that for
a simulation study, though a simulation study of the same problem
may cost several times more.

3.4. Conclusions on factors influencing the choice of
page size

In this paper we have reviewed the effects page size may have
on various relevant system performance measures, basing ourselves
on measurements and simple models of system behaviour.

We have then focused our attention on a measure of primary
memory utilization, the wasted space-time integral, in a two-
level memory system operating in a demand paging environment. A
model encompassing program behaviour, system behaviour, and the
influence of different secondary memory devices, has been con
structed in order to compute the wasted space-time integral (WST1)
as a function of page size.

We have reached the following conclusions concerning the
choice of page size to minimize the WST1 of primary memory. We
separate the factors which have to be taken into consideration in
this choice into two classes: the primary factors and the seconda
ry factors.

The primary factors are:

(a) The nature of the secondary memory device used
for paging. It is not so much the speed of the device, but the ra
tio of access to transfer time which is important. Thus though ECS
is faster than LCS in absolute terms, the optimal page size for
ECS will be larger than that for LCS, if all other parameters are
kept the same. For a sectored drum page sizes of the order of 512
or 1024 words appear optimal, while for ECS the size chosen should
be of the order of 256 words. For LCS the optimal size is in the
range of 64 to 128 words.

(b) The time spent by a program in the CPU queue after
having recovered from a page fault. If this time is large (of the
order of 8 msec or more) the optimal page size for LCS and ECS is
1024 or 2048 words. The influence on the drum is less important.

(c) The increase of the number of page faults with
smaller page size, particularly during the initial loading portion
of program behaviour. This factor is the main impediment to small
page sizes.

The secondary factors are:

(d) The global page fault rate in the system. As the
global page fault rate, or the arrival rate to secondary memory de
vices, increases optimum page sizes are shifted slightly towards
higher values.

(e) The effect of superfluity. With larger page sizes
the chance that unwanted information is loaded into memory in
creases. We have used a rule of thumb suggested by measurements to
evaluate its effect. This effect encourages slightly smaller page
sizes with LCS but does not seem to affect the choice for the drum
or ECS in an appreciable manner.

(f) Program size. Our examples suggest that the opti
mum page size for a small program which computes for as long as a
larger program should be smaller than for the larger program.

ACKNOWLEDGMENTS

The authors wish to acknowledge the encouragement of several
friends and colleagues for the work reported in this paper. These
include Bernie Galler, Keki Irani and Steve Kimbleten at the Uni
versity of Michigan, and J.F. Klinkhamer and H. Bosma at the
Philips Research Laboratories.

The critical comments of Claude Kaiser of IRIA (France) and of Tad Pinkerton
(The University of Wisconsin) are also gratefully acknowledged.

APPENDIX

ANALYSIS OF APPROXIMATE FORMULAE FOR THE WASTED
SPACE DUE TO TABLE FRAGMENTATION AND INTERNAL
FRAGMENTATION

The purpose of this Appendix is to analyze and justify certain
formulae which are used to approximate fragmentation.

Let x be program or segment size; x is treated as a random
variable with probability distribution function P(x) and density
function p(x). To avoid combinatorial difficulties we assume that
x is real valued (rather than integer valued). The approximations
we wish to validate are:

$$
E \left\{ \left[ \frac{x}{c} \right] \right\} = \frac{\lambda}{c} + \frac{1}{2}
$$

and
$$E \left\{ \left[ \frac{x}{C} \right] \right\} = \frac{\lambda}{C} - \frac{1}{2}$$

where $\lambda$ is the expected value of x and C is some positive constant.

Let $p(x, 1)$ be a density function which is normalised in the sense that its average equals unity. Then we define a class of functions $p(x, \lambda)$ according to the rule:

$$p(x, \lambda) = \frac{1}{\lambda} p\left(\frac{x}{\lambda}, 1\right) \quad (1)$$

It is easy to show that, for any $\lambda > 0$, $p(x, \lambda)$ represents a density function with average $\lambda$:

$$\int_{0}^{\infty} p(x, \lambda) \, dx = 1 \quad \text{and} \quad \int_{0}^{\infty} x p(x, \lambda) \, dx = \lambda.$$

Writing $y = x/\lambda$ we obtain the useful result:

$$\frac{\partial^{m-1} p(x, \lambda)}{\partial x^{m-1}} = \frac{1}{\lambda^m} \frac{\partial^{m-1} p(y, 1)}{\partial y^{m-1}} \quad \nexists \text{ integer } m > 0 \quad (2)$$

Note that $p(y, 1)$ is independent of $\lambda$ and so are all its derivatives.

Since:

$$\begin{align}
E \left\{ \left[ \frac{x}{C} \right] \right\} &= \sum_{i=0}^{\infty} i \int_{iC}^{(i+1)C} p(x) \, dx = \sum_{j=1}^{\infty} (j-1) \int_{(j-1)C}^{jC} p(x) \, dx = \nonumber \\
&= E \left\{ \left[ \frac{x}{C} \right] \right\} - 1 \tag{3}
\end{align}$$

we only have to analyze:

$$\begin{align}
E \left\{ \left[ \frac{x}{C} \right] \right\} &= \sum_{i=1}^{\infty} i \int_{iC}^{(i+1)C} p(x) \, dx = \sum_{i=0}^{\infty} \int_{iC}^{\infty} p(x) \, dx = \nonumber \\
&= \sum_{i=0}^{\infty} (1 - P(iC)) \tag{4}
\end{align}$$

where $P(x)$ is the distribution belonging to the density $p(x)$.
We will need two Lemmæ to do so. The first is a general rule for approximating infinite sums by infinite integrals. For a class of functions, the second lemma gives a bound for the error in this approximation.

### Lemma 1

Let $f(x)$ be a two times continuously differentiable function for $x \ge 0$. Then, if $\sum_{i=0}^{\infty} f(i)$ and $\int_{0}^{\infty} f(x) dx$ exist, we can define a function $\Theta_i$ of i such that:

$$ \sum_{i=0}^{\infty} f(i) = \int_{0}^{\infty} f(x) dx + \frac{f(0)}{2} + \frac{1}{12} \sum_{i=0}^{\infty} f''\left(i+\frac{1}{2} + \Theta_i\right) \quad (5) $$

$$ \text{with } \left| \Theta_i \right| < \frac{1}{2} \quad \forall i $$

**Proof:** From the trapezoidal rule

$$ \int_{0}^{x+h} f(x) dx = \frac{h}{2} (f(x_o) + f(x_o+h)) - \frac{h^3}{12} f''(x_o) $$

$$ \text{with } x_o < \xi < x_o+h $$

we obtain, putting $x_o = 1$, $h = 1$ and $\xi = \xi_i$:

$$ \int_{i}^{i+1} f(x) dx = \frac{f(i) + f(i+1)}{2} - \frac{1}{12} f''(x_i) \quad i < \xi_i < i + 1 $$

The proof follows by summation over i, taking

$$ \Theta_i = \xi_i - i - \frac{1}{2} $$

### Lemma 2

The error $R$ caused by neglecting of the last term in (5) is bounded by

$$ |R| \le \frac{N M^2}{12} \frac{e^{M/2}}{1 - \frac{M^2 e^{M/2}}{24}} \quad (6) $$
if $f(x)$ satisfies the following conditions:

a) $f(x)$ is an analytical function for every $x$ 0.

b) the function $f(n)$ defined by $f(n) = \left| \sum_{i=0}^{\infty} f^{(n)}(i+\frac{1}{2}) \right|$ exists for every $n$,

c) the function $G(n)$ defined by $G(n) = \left| \int_{0}^{\infty} f^{(n)}(x) dx \right|$ also exists,

d) $\lim_{n \to \infty} \frac{f(n)}{G(n)}$ exists,

e) $\lim_{m \to \infty} \frac{f^{(m+n)}(x)}{2^m m!} = 0 \quad \forall x, n \ge 0$

f) $G(n) \le NM^n \quad \forall n \ge 2,$
with finite N and

g) $h(x) = 2.57410306 \dots$

The proof will be sketched below.

We expand $f''(i + \frac{1}{2} + \theta_i)$ in a Taylor series:

$$f'' (1 + \frac{1}{2} + \theta_i) = \sum_{m=0}^{\infty} \frac{f^{(m+2)}(i+\frac{1}{2})}{m!} \theta_i^m$$

and interchange the order of summation in the resulting expression for $|R|$:

$$|R| = \frac{1}{12} \sum_{m=0}^{\infty} \frac{1}{m!} \left| \sum_{i=0}^{\infty} \theta_i^m f^{(m+2)}(i+\frac{1}{2}) \right| \le \frac{1}{12} \sum_{m=0}^{\infty} \frac{F(m+2)}{2^m m!} \quad (7)$$

In order to bound $F(n)$ for $n \ge 2$ we consider another integration formula:

$$\int_a^b f(x) dx = (b-a) f(\frac{a+b}{2}) + \frac{1}{24} (b-a)^3 f''(\xi) \quad \text{with } a < \xi < b.$$

Substituting $a = i$, $b = i + 1$ and summing over $i$ yields:

$$\sum_{i=0}^{\infty} f\left(i+\frac{1}{2}\right) = \int_{0}^{\infty} f(x) dx - \frac{1}{24} \sum_{i=0}^{\infty} f''\left(i+\frac{1}{2}+\theta_i\right) \quad \left|\theta_i\right| < \frac{1}{2}$$

More generally we have:

$$\sum_{i=0}^{\infty} f^{(n)}(i+\frac{1}{2}) = \int_{0}^{\infty} f^{(n)}(x) dx - \frac{1}{24} \sum_{i=0}^{\infty} f^{(n+2)}(i+\frac{1}{2}+\theta_i).$$

We expand the last term in Taylor series. Again, the remainder
will vanish because of condition e. After changing the order of summation we obtain:

$$ \sum_{i=0}^{\infty} f^{(n)}(i+\frac{1}{2}) = \int_{0}^{\infty} f^{(n)}(x) dx - \frac{1}{24} \sum_{m=0}^{\infty} \frac{1}{m!} \sum_{i=0}^{\infty} \Theta_i^m f^{(m+n+2)}(i+\frac{1}{2}). $$

Now we have established:

$$ F(n) \le G(n) + \frac{1}{24} \sum_{m_1=0}^{\infty} \frac{F(m_1+n+2)}{2^{m_1} m_1!} $$

Repeatedly substituting this inequality itself for any appearance of $F$ in its right hand side, we find, after the $i^{th}$ iteration:

$$ F(n) \le \sum_{j=0}^{i} \left( \prod_j \sum_m \right) G \left( \sum_{h=1}^{j} m_h + n + 2j \right) + \left( \prod_{i+1} \sum_m \right) F \left( \sum_{h=1}^{i+1} m_h + n + 2i + 2 \right) $$

where we used the notation $(\prod_j \sum_m)$ for the operator:

$$ (\prod_j \sum_m) = \left(\frac{1}{24}\right) \sum_{m_1=0}^{j} \frac{1}{2^{m_1} m_1!} \sum_{m_2=0}^{\infty} \frac{1}{2^{m_2} m_2!} \cdots \sum_{m_j=0}^{\infty} \frac{1}{2^{m_j} m_j!} $$

Because of condition d we may neglect the last term as $i \to \infty$:

$$ F(n) \le \sum_{j=0}^{\infty} \left( \prod_j \sum_m \right) G \left( \sum_{h=1}^{j} m_h + n + 2j \right) $$

The right hand side of this inequality can be evaluated using condition f by repeatedly applying:

$$ \sum_{m=0}^{\infty} \frac{m}{m!} = e^x $$

We find
$$F(n) \le NM^n \sum_{j=0}^{\infty} \left( \frac{M^2 e^{M/2}}{24} \right)^j = NM^n \frac{1}{1 - \frac{M^2 e^{M/2}}{24}}$$

provided $M^2 e^{M/2} < 24$ which corresponds with condition g. Finally we obtain (6) by applying this result to (7).

We will now resume our approximation of $E\left\{\left|\frac{x}{C}\right|\right\}$.

Using (6) and Lemma 1 with $f(x) = 1-P(xC)$ we find:

$$E\left\{\left|\frac{x}{C}\right|\right\} \approx \frac{\lambda}{C} + \frac{1}{2} \qquad (8)$$

$$E\left\{\left|\frac{x}{C}\right|\right\} \approx \frac{\lambda}{C} - \frac{1}{2}$$

To obtain a bound for the error in the above expressions we assume:

$$|p^{(m-1)}(0)| \le A \left(\frac{B}{\lambda}\right)^m \quad \forall m \ge 2 \qquad (9)$$

Note that, as for as it concerns the dependence of $p^{(m-1)}(x)$ on the average $\lambda$, this assumption is quite in agreement with (2).

Writing:

$$G(m) = \left| \int_{0}^{\infty} f^{(m)}(x) dx \right| = \left| f^{(m-1)}(0) \right|$$

we see that condition f is satisfied if we take:

$$M = B \frac{C}{\lambda} \quad \text{and} \quad NM = A$$

Except for possible violation of the other conditions of Lemma 2 we can bound the error in (8) to

$$|R| \le \frac{AB}{12} \frac{C}{\lambda} \frac{e^{\frac{BC}{2\lambda}}}{1 - \frac{B^2 C^2}{24\lambda^2} e^{\frac{BC}{2\lambda}}} \qquad (10)$$

### Example

Let $p(x)$ be given by the Erlang density

$$p_k(x) = a^{k+1} \frac{x^k}{k!} e^{-ax}$$
where $k$ is a nonnegative integer and $a > 0$.

The average $\lambda$ is known to be $\lambda = \frac{k+1}{a}$ and

$$P_k^{(m)}(x) = (-a)^m \sum_{i=0}^{k} \binom{m}{i} (-1)^i P_{k-1}(x).$$

Therefore:

$$|P_k^{(m-1)}(0)| = (\binom{m-1}{k}) a^m < 2^{m-1} a^m = A \left(B \frac{a}{k+1}\right)^m$$

and we may use:

$$A = \frac{1}{2}$$

$$B = 2(k + 1)$$

which gives :

$$|R| \le \frac{k+1}{12} \frac{C}{\lambda} \frac{e^{\frac{(k+1)C}{\lambda}}}{1 - \frac{(k+1)^2 C^2}{6 \lambda^2} e^{\frac{(k+1)C}{\lambda}}}$$

as an upperbound for the error in (8).
REFERENCES

1. F.J. Corbato and V.A. Vyssotsky, "Introduction and overview of the Multics system," AFIPS Conference Prec. FJCC 27, Part I 185-196 (1965).

2. D.J. Kuck and D.H. Lawrie, "The use and performance of memory hierarchies: a survey," Computer and Information Sciences II (J.T. Tou, Editor) Academic Press, N.Y. (1969).

3. M. Joseph, "An analysis of paging and program behaviour," Computer Journal 13, 1, 48-54 (Feb. 1970).

4. D.J. Hatfield, "Experiments on page size, program access patterns, and virtual memory performance," IBM J. of Res. and Dev. 16, 1, 58-66 (1972).

5. L.A. Belady, "A study of replacement algorithms for a virtual-storage computer," IBM Syst. J. 5, 2, 78-101 (1966).

6. B. Randell, "A note on storage fragmentation and program segmentation," Comm. ACM 12, 7, 365-372 (June 1969).

7. E. Wolman, "A fixed optimum page size for records of various lengths," J. ACM 12, 1, 53-70 (Jan. 1965).

8. E. Gelenbe, J.C.A. Boekhorst and J.L.W. Kessels, "Minimizing wasted space in partitioned segmentation," to appear in Comm. ACM.

9. P.J. Denning, "Virtual memory," Computing Surveys, 2, 3, 153-183 (Sep. 1970).

10. M.T. Alexander, "Time sharing supervisor program," University of Michigan Engineering Summer Conf," Advanced Topics in Systems Programming" (1971).

11. S.E. Madnick, "Nested multilevel hierarchical storage system: an analysis of the page size anomaly," M.I.T. Project MAC Report (Dec. 1971).
12. L.A. Belady, R.A. Nelson, and G.S. Shedler, "An anomaly in space-time characteristics of certain programs," Comm. ACM 12, 6, 349-353 (June 1969).

13. R.W. O'Neill, "Experience using a time-shared multiprogramming system with address relocation hardware," AFIPS Conference Proc. SJCC 30, 611-621 (1967).

14. E.G. Coffman, "Analysis of a drum input-output queue under scheduled operation in a paged computer system," J. ACM 16, 1, 73-90 (Jan. 1969).

15. G.H. Fine, C.W. Jackson and P.V. McIsaac, "Dynamic program behaviour under paging," Proc. of the 21st National ACM Conf. P-66, 223-228 (1966).

16. B. Randell and C.J. Kuehner, "Dynamic storage allocation systems", Comm. ACM 11, 5, 297-306 (May 1968).

17. C.G. Moore, "Network models for large-scale time-sharing systems," Ph.D. Thesis, The University of Michigan, 1971.
<figure><img src="image_2.png" /><figcaption>Figure 1</figcaption></figure>
<figure><img src="image_3.png" /></figure>

* * * * * * * * *

EACH PAGE IS DIVIDED INTO TWO PAGES, e.g. A BECOMES
A1 AND A2. TOTAL MEMORY SPACE REMAINS CONSTANT IN
BOTH CASES. COLUMNS MARKED BY AN ASTERISK CORRESPOND
TO A PAGE FAULT. THERE ARE 11 PAGE FAULTS WITH
THE HALVED PAGE SIZE AND 4 PAGE FAULTS WITH THE FULL
PAGE SIZE. THE REPLACEMENT ALGORITHM IS FIFO.

<caption>Fig. 2</caption>
<figure><img src="image_4.png" /><figcaption>Figure 3</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 4</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 5</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 6</figcaption></figure>
<figure><img src="image_8.png" /><figcaption>Figure 7</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>Figure 8</figcaption></figure>