University of Edinburgh

Department of Computer Science

Performance Measurement on the Edinburgh Multi-Access System

J.C. Adams & G.E. Millard

EMAS Report 7
Performance Measurement On The Edinburgh Multi Access System

J.C. ADAMS        Department of Computer Science, Edinburgh University
G.E. MILLARD      Edinburgh Regional Computing Centre

Summary

The performance monitoring facilities incorporated in EMAS (Edinburgh Multi Access System) are described and a brief description of the results obtained is presented.

- presented at the International Computing Symposium 1975
    June 2 - 5 1975
    Antibes, France.
PERFORMANCE MEASUREMENT ON THE EDINBURGH MULTI ACCESS SYSTEM

Introduction

The Edinburgh Multi Access System (W1) is a virtual memory, time sharing operating system developed at Edinburgh over the last eight years. It has been implemented on the International Computers Ltd. System 4/75 which is a paged 3rd generation machine. The entire system is written in the high level, Algol-like language IMP (S1). Up to fifty five or thirty five simultaneous users are supported depending upon hardware configuration and the system supports sharing at all levels. Originally intended as a research and teaching project as well as a production exercise, the system has had incorporated at various levels in its hierarchy a variety of monitoring facilities enabling close measurement of its performance. The structure of the system is shown in figure 1. The monitoring which will be discussed in this paper splits naturally into two main parts:

A) Measurements taken at the level of the resident supervisor. (All monitoring is done by software, we have no hardware monitoring facilities.)

B) Measurements taken at the subsystem level.

The system is implemented at present on two separate System 4/75's at Edinburgh. Normal hardware configurations used are given in table 1. Because of the architecture of the System 4/75 there is no multiprocessing and these systems are distinct, but the capability exists to switch filestores, drums, some tape drives and MCCCUs between machines for experiments or in the event of processor failure.

PERFORMANCE MONITORING WITHIN THE RESIDENT SUPERVISOR

The resident supervisor, in common with the rest of the system, is written entirely in IMP and is thus relatively easy to modify. Special, 'one off' pieces
<table>
  <tr>
    <th>LEVEL</th>
    <th>INVOKED BY</th>
    <th>FUNCTIONS PERFORMED</th>
    <th>CODE</th>
  </tr>
  <tr>
    <td rowspan="2">KERNEL</td>
    <td>Interrupts', routine calls', Returns from MAIN processes.</td>
    <td>Inter-process message switching. Privileged hardware instructions. Interrupt message version. Process dispatching.</td>
    <td>10 k. bytes</td>
  </tr>
  <tr>
    <td>Inter-process messages.</td>
    <td>I/O device control. Paged I/O scheduling and error recovery. Interactive communications device control.</td>
    <td>52 k. bytes</td>
  </tr>
  <tr>
    <td rowspan="2">DEVICE HANDLERS</td>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td rowspan="2">VIRTUAL PROCESSOR SUPPORT</td>
    <td>Inter-process message.</td>
    <td>Active and Main storage allocation. Virtual processor scheduling and contingency handling.</td>
    <td>32 k. bytes</td>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td>VIRTUAL MEMORY MAPPING</td>
    <td>Inter-process message, and Master Page entries.</td>
    <td>Association of virtual memory addresses and immediate memory sites. User process Signal mechanism.</td>
    <td>4 k. bytes</td>
  </tr>
  <tr>
    <td>SUB-PROCESSES</td>
    <td>Inter-process message.</td>
    <td>Interactive communication. File system maintenance. File transfer for I/O.</td>
    <td>46 k. bytes</td>
  </tr>
  <tr>
    <td>EXECUTIVE USER PROCESSES</td>
    <td>Inter-process message.</td>
    <td>Unit record device spooling. Batch scheduler. Archive directory control. English-string test programmes.</td>
    <td>69 k.+ 16 k. + 75 k. bytes</td>
  </tr>
  <tr>
    <td>STANDARD SUBSYSTEM PROGRAMMES</td>
    <td>Inter-process message and routine calls.</td>
    <td>File definition. Object file layout, linking and loading. Logical I/O mapping.</td>
    <td>110 k. bytes</td>
  </tr>
  <tr>
    <td>Editors, Compilers, Utilities and User provided routines and programmes.</td>
    <td></td>
    <td>450 k.+ user code bytes</td>
    <td></td>
  </tr>
</table>

SOFTWARE PRIVILEGED / NON-PRIVILEGED BOUNDARY
Table 1

E.M.A.S. HARDWARE CONFIGURATIONS

<html>
  <table>
    <tr>
      <th></th>
      <th>MACHINE 'A'</th>
      <th>MACHINE 'B'</th>
    </tr>
    <tr>
      <td>4/75 CPU, operator typewriter and console</td>
      <td>1</td>
      <td>1</td>
    </tr>
    <tr>
      <td>1\( \mu \) sec CORE (4 bytes access, 2 way interleaved)</td>
      <td>1024 K bytes</td>
      <td>768 K bytes</td>
    </tr>
    <tr>
      <td>2 M byte DRUMS (128 tracks, 4 pages per track)<br>(transfer rate 860 K bytes/sec<br>revolution 20 m sec)</td>
      <td>3<sup>†</sup></td>
      <td>2<sup>†</sup></td>
    </tr>
    <tr>
      <td>2 x 350 M byte, non replaceable DISC drives on 1 channel<br>(transfer rate 256 K bytes/sec<br>revolution 40 m sec<br>Average arm movement 60 m sec)</td>
      <td>1<sup>†</sup></td>
      <td>1<sup>†</sup></td>
    </tr>
    <tr>
      <td>7.5 M byte replaceable DISC drives</td>
      <td>2</td>
      <td>3</td>
    </tr>
    <tr>
      <td>1600 b.p.i. TAPE drives</td>
      <td>2<sup>†</sup></td>
      <td>2<sup>†</sup></td>
    </tr>
    <tr>
      <td>Hardwired communications multiplexer (MCCU)<br>DATEL 100 lines<br>DATEL 200 lines<br>DATEL 600 lines<br>DATEL 2400 lines<br>DATEL 4800 lines</td>
      <td>1<sup>†</sup><br>64<br>16<br>4<br>5<br>0</td>
      <td>1<sup>†</sup><br>16<br>8<br>0<br>0<br>4</td>
    </tr>
    <tr>
      <td>British Standard Interface</td>
      <td>1</td>
      <td>1</td>
    </tr>
    <tr>
      <td>line printer</td>
      <td>2</td>
      <td>1</td>
    </tr>
    <tr>
      <td>card reader</td>
      <td>1<sup>†</sup></td>
      <td>0</td>
    </tr>
    <tr>
      <td>card punch</td>
      <td>1</td>
      <td>0</td>
    </tr>
    <tr>
      <td>paper tape reader</td>
      <td>1</td>
      <td>0</td>
    </tr>
    <tr>
      <td>paper tape punch</td>
      <td>1</td>
      <td>0</td>
    </tr>
  </table>
</html>

† - switchable between machines by means of a DXE switching unit.

The MCCU's will be replaced shortly by a Front End Processor (PDP 11/45) which is connected to the BSI's and currently handles 16 DATEL 100 lines, a synchronous line to another concentrator and a 1200 baud line to a video, usually going into the 'B' machine.

Page size is 4096 bytes (8 bits). On each machine the drums are on one channel.
of monitoring may easily be added for short periods of time, the compilation and linking of a new supervisor taking only about 10 minutes (real time) on average. We shall describe the permanent monitoring features in this section.

The scheduling algorithms employed within the resident supervisor are discussed in detail in the paper by Shelness et al. (S2) and we give a very brief resume here, to ease understanding of the results presented. Figure 2 is a diagrammatic representation of the management of a process by the supervisor showing all the system queues and major states involved. Each process known to the system exists in one of three states.

a) ASLEEP - awaiting user input
b) AWAKE - awaiting allocation of some system resource
c) PROCESSING - on CPU

Each process is also resident at up to a certain level in the storage hierarchy DRUM, DISC or CORE. E.M.A.S. uses a local scheduling algorithm in which each process is assigned to a CATEGORY dependent upon the recent past history of that process. Associated with each category are

i) a CPU, CORE and DRUM allowance
ii) a CORE queue
iii) a time period after which an attempt to compact the working set will be made
iv) a set of transitions to other categories dependent upon the future behaviour of the process

There are currently 20 categories. Table 4 shows the current category allowances.

Thus for a process which wakes up resident only on DISC. It is first placed in the Active Storage Queue to await a drum allocation. Then it is placed on a Core Queue dependent upon its current category. These core queues are serviced
starts

asleep on disc

active store Q

active take Q

asleep on drum

Q 1   Q 2   Q 3   Q 4   Q 5
core queues

preloading

suspended

run queues

CPU

page wait

stops

awaits user input

awaits system resource

processing

Management of process by the supervisor

Figure 2
according to a priority scheme and when a process is selected from a core queue it is held until its current working set (D1) is preloaded. When the process is core resident it is placed on Run Q0. The run queues are serviced according to an absolute priority basis. All processes which have just completed a page transfer being placed on Run Q0, all preempted or time-slicing processes on RUN Q1 and all penalised processes (which have not interacted with a console for a set period of time) are placed on RUN Q2. The time slice is currently 100 milliseconds. The process will remain core resident until it either goes to sleep or overruns one of its category allocations, whereupon it is rescheduled (perhaps into a new category) and then removed from core.

As it is highly unlikely that all of the core resident processes will be using their full core allocation at any given instant, core is over allocated by a certain amount to obtain more efficient utilisation. Another modification to the basic algorithm concerns preloading: when attempting to preload a process, if it is found that there is not adequate core free to give the process its full allowance but, enough free core exists to allow the preloading of the working set then this 'partial preload' proceeds. When the partial preload is completed, if enough core is still not available then the process is suspended until core is released. A drum working set is also maintained.

CPU TIME MONITORING

The resident supervisor itself consists of a set of routines (or services) each of which has its own unique service number. Requests for these services are stacked in a system table known as the MAIN Q. One of the functions of the KERNEL is to unstack these requests and call the appropriate service. We keep a simple count of the number of calls on each service and the time spent in each. This gives us a very accurate record of all time spent in the supervisor state and a complete record of the areas within the supervisor in which this time is being spent. This raw data is printed at the end of each session.
When the system is IDLE (i.e. none of its current multiprogramming set is able to run), a dummy process, (process \( \neq 0 \)) is loaded and the system executes an idle loop until work arrives. This idle time is further broken down into time during which there was no work available (no process awake) and blocked time (all of the multiprogramming set awaiting some form of a page transfer).

A full analysis of CPU utilisation is printed at the end of each session (table 2). In a typically heavy user session the breakdown between User state, Supervisor state and Idle seems to be 50%, 30%, 20%. Figure 3 is a pie chart representation of supervisor time and it can easily be seen that the dominant areas are the organisation of drum transfers (41%) followed by core loading, (22%) the core loading figure includes time spent compacting working sets - a costly business on the System 4 as we have to read 4 read/write markers per page.

A facility which has proved useful in system tuning and the gaining of a rough insight into how system variables are behaving is one we call Q SAMPLING. In this, a routine is called every 10 seconds to sample interesting system variables. It accumulates a total and records the maximum and minimum values found. An example of the output from this is given in table 3. The negative figure for the minimum CORE UNALLOCATED value is a result of the deliberate over allocation of core. A 20 x 20 array is also stored in which we accumulate all transitions from any one category to any other. This transition matrix, which is printed at the end of each session gives us some insight into how well the system is tuned and what type of load is currently being placed on it. The matrix usually turns out to be highly diagonal and shows a great tendency to cluster around a small subset of the 20 categories. The current category allowances are shown in table 4. The % transition figure is the % of total category transitions involving this category.

EVENT TRACING

E.M.A.S. also maintains an event tracing facility. A list of events which
TABLE 2

E.M.A.S.    CPU TIME ANALYSIS

Configuration 'A' from 17.27.01 on 21.02.74
to 01.40.30 on 22.02.74

<table>
  <tr>
    <th></th>
    <th>SECONDS</th>
    <th>% OF TOTAL TIME</th>
  </tr>
  <tr>
    <td>TIME IN USER PROCESSES</td>
    <td>15272</td>
    <td>50.90</td>
  </tr>
  <tr>
    <td>SUPERVISOR TIME</td>
    <td>9024</td>
    <td>30.07</td>
  </tr>
  <tr>
    <td>IDLE TIME</td>
    <td>5705</td>
    <td>19.01</td>
  </tr>
  <tr>
    <td>TOTAL TIME</td>
    <td>30001</td>
    <td>100.00</td>
  </tr>
  <tr>
    <th colspan="3">ANALYSIS OF SUPERVISOR</th>
  </tr>
  <tr>
    <th colspan="3">VIRTUAL MEMORY SUPPORT</th>
  </tr>
  <tr>
    <td>DRUM TRANSFERS</td>
    <td>3675</td>
    <td>12.24</td>
  </tr>
  <tr>
    <td>DISC TRANSFERS</td>
    <td>568</td>
    <td>1.89</td>
  </tr>
  <tr>
    <td>CORE LOADING</td>
    <td>2942</td>
    <td>9.80</td>
  </tr>
  <tr>
    <td>DRUM LOADING</td>
    <td>247</td>
    <td>0.82</td>
  </tr>
  <tr>
    <td>PROCESS CONTROL</td>
    <td>132</td>
    <td>0.43</td>
  </tr>
  <tr>
    <td>TIME SLICING</td>
    <td>661</td>
    <td>2.20</td>
  </tr>
  <tr>
    <td>FILE SYSTEM</td>
    <td>41</td>
    <td>0.13</td>
  </tr>
  <tr>
    <td>SVC PARAMETER PASSING</td>
    <td>354</td>
    <td>1.17</td>
  </tr>
  <tr>
    <td>COMMUNICATIONS</td>
    <td>177</td>
    <td>0.58</td>
  </tr>
  <tr>
    <td>DEVICE POLLING</td>
    <td>35</td>
    <td>0.11</td>
  </tr>
  <tr>
    <td>MAGTAPES</td>
    <td>8</td>
    <td>0.02</td>
  </tr>
  <tr>
    <td>MISC.</td>
    <td>184</td>
    <td>0.61</td>
  </tr>
</table>

Supervisor CPU Time Analysis

![Pie chart showing CPU time analysis breakdown](page_1012_1042_420_420.png)

Figure 3
DATA COLLECTION

It was obviously necessary to attempt to minimise the overhead in accumulating the recorded data from up to fifty concurrent processes. As mentioned above files are mapped directly into processes' virtual memories and records are accessed by direct reference to virtual memory addresses. It was decided to collect all the data in one file belonging to the system manager's process. When a process is started it determines whether it is permitted write-shared access to the file. If so, it connects the file in write-shared mode, and monitoring is activated. The monitoring file is created with adequate length to contain the records for the period required and has a standard EMAS header containing pointers to the current end of data and physical end of file. Monitoring records are of fixed length and are mapped consecutively onto the file following the header. When a monitoring record is to be written from a particular process the area in the data file is first reserved by updating the current data pointer at the head of the file. If this does not exceed the physical end of the file then the record is then copied to the file. If an end of file condition applies the monitoring activity automatically switches off.

Monitoring is activated by initialising the collection file and permitting it to all users in write-shared mode and terminated by withdrawing the access permission (this does not affect currently active users but no new user will be monitored).

OBSERVATIONS

Subsystem monitoring has been carried out at intervals over two years and samples representing in some instances several days continuous monitoring have been analysed. Comparisons between the distribution of commands measured over a 24 hour period with that determined from an included, continuously busy, period (3 - 5 p.m.) have shown discrepancies of the order of only one per cent. It was
therefore thought adequate to look at analyses of mid-afternoon sessions to determine any trends in the user behaviour pattern or changes in system performance.

As anticipated the monitoring has enabled us to observe the benefits (or otherwise) of different scheduling strategies within the supervisor. We have also been assisted in our attempts to improve the internal organisation of the subsystems such that overall paging activity is reduced.

Over the last two years the only significant change to be observed, apart from improvements in performance, has been a reduction in the average size of source files being compiled. This must in part be due to the increasing number of students using the system, but may also reflect a greater awareness of users to the benefits of editing and recompiling only those parts of their programs which are currently under development.

Since the observations have been so consistent it is relevant to reproduce here some figures relating to a typical two hour period (3-5 p.m. on 22nd April 1974).

<table>
  <tr>
    <th> </th>
    <th> </th>
  </tr>
  <tr>
    <td>Number of concurrent users</td>
    <td>25-30</td>
  </tr>
  <tr>
    <td>Number of user sessions</td>
    <td>136</td>
  </tr>
  <tr>
    <td>Total number of user commands</td>
    <td>1652</td>
  </tr>
  <tr>
    <td>Cpu time spent in user processes</td>
    <td>51 mins (42.5% of elapsed time)</td>
  </tr>
  <tr>
    <td>Average cpu/command</td>
    <td>1.85 secs</td>
  </tr>
  <tr>
    <td>User terminal activity</td>
    <td></td>
  </tr>
  <tr>
    <td>input average 3.5 lines (43 chars)/command</td>
    <td></td>
  </tr>
  <tr>
    <td>output average 8.5 lines (327 chars)/command</td>
    <td></td>
  </tr>
</table>

Table 6 gives the command distributions and the proportion of cpu and elapsed time occupied by the principal commands for editing, compiling and executing programs. The other commands are mainly used for interrogation (e.g. number of users on the system, resources used) and basic file operations (e.g.
listing files, destroying files, defining associations between logical and physical files).

<table>
  <tr>
    <th>Command type</th>
    <th>Count</th>
    <th>% total</th>
    <th>% cpu time</th>
    <th>% elapsed time</th>
  </tr>
  <tr>
    <td>Editing source and data files</td>
    <td>329</td>
    <td>20</td>
    <td>8</td>
    <td>51</td>
  </tr>
  <tr>
    <td>Compiling (IMP and FORTRAN)</td>
    <td>153</td>
    <td>9</td>
    <td>24</td>
    <td>8</td>
  </tr>
  <tr>
    <td>Executing compiled programs</td>
    <td>280</td>
    <td>17</td>
    <td>61</td>
    <td>34</td>
  </tr>
  <tr>
    <td>Others</td>
    <td>890</td>
    <td>54</td>
    <td>7</td>
    <td>7</td>
  </tr>
</table>

Table 6  Command distribution for a typical two hour session

Figure 7 shows, in percentage terms, the elapsed time distribution for the editing, compiling and program execution commands observed during the above session, together with an indication of the sizes of programs compiled and cpu demands made by programs in execution. The average elapsed time for editing was about 3.5 mins and on average each editing session involved 11 lines (140 chars) input and 12 lines (288 chars) output. The average cpu time requirement for a compilation was 5 secs (250-300 statements), and the average elapsed time 67 secs. As can be seen in figure 7(b) these figures are biased by a small number of large compilations. The elapsed times for programs being executed (figure 7(c)) would have been significantly affected by the amount of terminal I/O activity - on average 3 lines (31 chars) in and 27 lines (1233 chars) out at a maximum rate of 10 chars/sec. The average elapsed time of 158 secs and average cpu time of 6.6 secs are also biased by a number of longer running programs.

CONSTRUCTION OF A BENCHMARK

Having demonstrated that at a given point in time the profile of user activity is very stable a benchmark has been defined based on the observations over a specific two hour period. Additional information was required about the
Characteristics observed during a typical 2 hour session

(a) Editing

(b) Compiling

(c) Executing compiled programs

Figure 7
behaviour of a typical user at his terminal, in particular his typing rate and the 'think time' between receipt of an output message or prompt and the input of the next command or data. This has been obtained by external monitoring of the activity over the lines connecting individual terminals to the ICL 4/75s.

A number of 'jobscripts', each containing the command and data input for a complete terminal session, have been constructed. The individual command totals were identical with those in the observed period and the program files, contributed by users, were selected to exhibit the spread of compilation and execution characteristics which had been observed. A PDP 11/45 has been used to simulate the user activity defined by the jobscripts. Each job script includes control data specifying think times and typing rates and appropriate delays are imposed by the PDP 11/45 control program. Delays appropriate to the maximum output rates of the terminals being simulated are also imposed. The PDP 11/45 has the appearance, as far as the system is concerned, of a standard EMAS concentrator.

This benchmark will be used by this and other Universities for assessing the capabilities of new systems. It also provides a standard workload for a series of experiments to be conducted on EMAS using different hardware and software configurations.

ACKNOWLEDGEMENTS

We would like to acknowledge the contribution made by everyone connected with the EMAS project, especially Peter Stephens for invaluable help in the resident supervisor area, and by Ken Dietz and Brian Gilmore in measuring external characteristics and providing the PDP 11/45 software respectively.
REFERENCES

D1    Denning, P.J.   'The working set model for program behaviour'
        Communications of the ACM Vol 11 No. 5

M1    Millard, G.E., Rees, D.J. and Whitfield, H.   'The Standard EMAS Subsystem' Computer Journal - to be published.

S1    Stephens, P.D.   'The IMP language and compiler'
        Computer Journal Vol 17 No. 3

S2    Shelness, N.A., Stephens, P.D. and Whitfield, H.
        'The Edinburgh Multi-Access System Scheduling and Allocation Procedures in the Resident Supervisor'
        Proc. International Symposium on Operating Systems, Theory and Practice. April 23rd-25th 1974 I.R.I.A. Paris

W1    Whitfield, H. and Wight, A.S.   EMAS - 'The Edinburgh Multi Access System' Computer Journal Vol 16 No. 4