THE IMPROVEMENT OF PROGRAM BEHAVIOUR IN PAGED COMPUTER SYSTEMS

C. J. PAVELIN

Ph.D. University of Edinburgh August 1970

SUMMARY

The thesis initially considers two questions: what is meant by program behaviour in a paged computer system, and what is meant by its improvement. The former, especially, demands a general discussion on paging and its uses and abuses in modern operating systems. Reference is made to a brief study of the behaviour of some KDF9 programs. The problem of restructuring a program in order to improve its paging behaviour, is then investigated; a solution using clustering techniques is suggested. A scheme to perform such a restructuring automatically, on the basis of monitored information from the program at run-time, has been implemented on the ICL 4-70. This scheme is described and some results presented; these show that considerable improvement can be obtained.

This work was supported by International Computers Ltd.

CONTENTS

INTRODUCTION

CHAPTER I: Paging and program behaviour CHAPTER II: Improvement of program behaviour CHAPTER III: Formal restructuring of programs CHAPTER IV: Practical aspects of the restructuring technique CHAPTER V: The restructuring scheme CHAPTER VI: Results and conclusions

REFERENCES

APPENDIX A: A brief study of program behaviour on the KDF9 APPENDIX B: Some implementation details of restructuring scheme APPENDIX C: Properties of the mean working set size

utilisation whatever the degree of multiprogramming.

2. A 'virtual store' (see introduction) can be realised, a great convenience for the user.

3. Use of memory is made flexible; a program can be loaded without the need for a large area of contiguous vacant store. (The mapping mechanism solves all relocation problems in physical store.)

In paging systems we have in addition:

4. extreme simplicity, owing to the fact that a page can be loaded arbitrarily into any available page frame. If allocation is in non-constant size units, as these are loaded and unloaded the vacant store rapidly fragments into blocks of varying lengths. When a storage request is made, the system has to search for a suitable unoccupied section or perhaps reshuffle the code around the store to create one. Such problems, and the considerable software overheads associated with their solution, do not arise in the paging situation. In addition the constancy of size means one less set of variable parameters in the system.

Disadvantages

1. Mechanisms which map from the program name space into actual address space can be expensive (the hardware components), and result in an increase in average addressing time.

2. The tables containing information about units necessary to the address mapping mechanism (e.g. page tables) take up valuable space in main memory.

3. There is greater software (and possibly hardware) overhead in moving several small areas of data between working store and backing store, than one large area. (Thus the total overhead in

transferring a complete program into store is greater for smaller units.)

And finally the additional factor against paging systems.

4. Since page sizes are fixed, their boundaries will normally be imposed more or less arbitrarily on a program. This makes it more difficult to reap the profit from advantage 1 than in the case where variable size units of allocation can be chosen to reflect the structure of the program to some degree.

Paging thus gives the gain of advantage 4 while foregoing part of the potential benefits expressed in advantage 1. The realisation of the latter is in any case far from easy; but this is particularly true in the paging environment. However it was not simply the failure to achieve these benefits that led to unfortunate results in some early paging systems, but a lack of appreciation of the fact that this is where the problem lay.

(We note in passing that the choice of ideal page size is a compromise between the overheads of 2 and 3 above, and the gains of advantage 1. For the latter to exist at all, the size clearly has to be fairly small compared to the average program requirements; this gives an upper bound, but in practice it is not clear what lower bound the disadvantages impose. The commonly chosen page size of about 1000 words may be dictated more by tradition than measured efficiency considerations. Shemer and Shippey (ref.4) detail the effects of page size.)

2. THE ALLOCATION PROBLEM

The problem arises from the fact that there is no sure way of knowing which parts of a program will be referenced in a particular

run or time-slice. Short of loading the whole program, which obviously extracts none of the potential benefits of advantage 1, there must be at least some occasions when reference is made to a page not in main memory, i.e. a page-fault occurs. It is at these times that whatever action the system takes introduces a possible cause of inefficiency.

1. The normal course is to load the referenced page (loading only after a faulting reference is known as demand paging). If there is an available page-frame, i.e. one not occupied by pages of an active program, there is no difficulty (but even then it should be noted that the I/O overhead involved in loading a set of pages is less when requests are made altogether than when each page is loaded singly after a page-fault.)

More significant is the likely case that there is no available space when the page-fault occurs. This makes it necessary to over-write - after writing back if necessary - a page, either of the program concerned, or of another. This in itself is not significant, but it becomes so if the overwritten page is required again in the current run or time-slice of its program. Every reloading represents a possible loss of efficiency over whole program roll-in roll-out methods.

One could reserve for the program before it is allowed in store a sufficient space allocation to ensure that the above situation never occurred, but this extreme would probably lead to reservation of almost the total program size, and again scarcely realise one of the main benefits of the small allocation unit.

2. The other alternative, in a time-sharing system, is to use the faulting reference to terminate the time-slice, the program

being unloaded to make room for others. This is no solution though; there will be an increase in the proportion of time spent loading and unloading programs, and a decrease in CPU utilisation. An upper bound to the length of the time-slice is a constraint arising from the demands of a good response time for a large number of users; a system is unwise to reduce a time-slice more than these inefficient demands of time-sharing already dictate.

Thus the attempt to take some of advantage 1 of the last section may lead to more movement of pages between backing store and main memory (page swapping). A very simple model can demonstrate at least the possibility of this increased I/O swamping the multi-programming advantage which apparently arises from having more programs in store.

Suppose program i is allocated store size $s_i$ over a long period, and that as faults occur, pages of i (chosen according to some strategy) are overwritten. Take as a unit of time, the average page fetch time from immediate backing store. (Page write time is not explicitly included as only those pages which have changed have to be written back - this can be allowed for in the average fetch time if necessary.) For rotating backing store devices, the unit is typically a few thousand instruction cycles.

Let $r_i(s_i)$ be the average number of page faults that occur from program i during a unit of its own processing time (this is the program's page-fault rate). An upper limit to the ratio of its CPU time : real time is $1:1 + r_i(s_i)$

$$\sum_{\text{all progs.}} \frac{1}{1 + r_s(s_i)}$$

If the total core size is M, and a set of similar programs are each allocated store s (giving fault rates r(s)), the number of such programs that can be accommodated is M/s; the CPU utilisation is then at most:

$$\frac{M}{s(1 + r(s))} \tag{1.2}$$

Suppose each program is subject to processing time-slices of length T (between which its pages are removed), and it references S(T) distinct pages in such a time-slice. Assuming wholly demand paging, then r as defined above will achieve its minimum value of S(T)/T for s = S(t). For allocations greater than S(T), the efficiency will clearly fall. But consider a very small s, perhaps just two or three pages; little knowledge of program behaviour is required to see that the interval between faults can easily be no more than a few instructions. The value of r (in the above units) would then be over a thousand and the CPU utilisation practically zero, except with a vast main memory. It is obvious how irrelevant the multiprogramming advantage (effectively the multiplier M/s) can become if page-faults occur with great rapidity. (Note also how a small time-slice - T $\ll 1$ in the defined units - imposes an immediate bound on achievable efficiency).

Somewhere between the extremes of store allocation, there will be an optimum. The difficulty lies in finding it, or equivalently finding the optimum number of the programs currently competing for service, to allow in store. It will depend at any moment on the

behaviour of all the programs, the replacement strategy being used, and other system variables. The best allocation will be continuously varying and modern systems adopt adaptive strategies (refs.5,6); these respond to changing program demands and try and maintain page-faulting at an acceptable level, even if some programs have to be given a large proportion of their total size.

The overwhelming significance of the page fetch time should be quite clear; it is because our time unit is extremely long compared to instruction times (and therefore to likely intervals between page faults) that efficiency problems can so easily arise (see e.g. Denning ref.7). Bulk core store cheap enough to replace the rotating drum normally used for immediate backing store at present, could revolutionize the efficiency of time sharing systems.

Inexplicably, some early system designers allowed the concept of paging to obscure the problems of storage allocation. All active programs fought simultaneously for the available store with the inevitable results that excessive page swapping led to congestion and very low CPU utilisation. However programs were believed to behave under paging, there would seem to be no reason to have adopted such a policy.

Notes on formula 1.2

This formula only purports to give insight into gross aspects of system performance, but since it is referred to later in this chapter, a mention of the principal limitations is given here.

1. Ratio 1.1 is an upper limit only attained when there is a small number of programs and the CPU utilisation is fairly low. In practice the situation is worse than the model suggests - there

will be occasions when a program is held up not for I/O but because another process is using the CPU. (Even a moderately accurate treatment of multiprogramming is complex, and depends on probability models for aspects of program behaviour - see ref.8.)

2. The page fetch time is not constant. Worse still, its average will lengthen when queueing for I/O channels starts to take place. This may be due to heavy page faulting of active programs, or pages filtering through lower levels of store (disc to drum etc.), via the main memory.

3. CPU time lost due to system use or I/O cycle stealing is not allowed for.

On all these counts, formula 1.2 gives an optimistic view of the situation.

3. PROGRAM BEHAVIOUR

A program which references a large proportion of its pages within short time intervals is generally said to be 'badly behaved' (or have a high 'vagrancy'). A good operating system must expect, and be able to cope with, programs displaying any behaviour pattern; a badly behaved program simply yields less of the advantages of small-unit allocation. However a knowledge of general characteristics of average programs, or perhaps of particular system software, is useful for performance prediction, aspects of design, and for evaluation of paging as an allocation method. Since the much cited and pessimistic study by Fine, Jackson and McIsaac (ref.9), there have been numerous other empirical investigations of paging behaviour (e.g. refs. 10,11,12).

Unfortunately it is not easy to decide just what to measure;