- 10 -
This required amount of store, from the upper limit of the Hole downwards,
is assigned before starting to read in the A program (unlike the procedure
described above for B programs, which starts with only 32 words assigned).
Once the B-block has been read, this area may be contracted (from the top
downwards) if the actual store requirement is less than the amount assigned:
the vacant space thus created will be transferred to the "Hole in the middle"
by the normal program-moving procedure.
Note that core storage ceases to be "vacant" as soon as it has been assigned
for program input, and is therefore liable to be "slid" up or down the store
while the program to occupy it is still. being input. However, an assigned
area can only be moved when there are no peripheral lock-outs set on it.
The case described above, when the store area assigned to a B program
"expands", between reading the B and C-blocks, from 32 words to the
requisite number, is the only one which ever involves increasing the amount
of store belonging to a program: it is the only case where there is a
vacant area, i.e. the "Hole in the middle", to expand into. The area
assigned to a program may be decreased on three occasions: firstly, in the
case already described, where an A program's store requirement is less than
the amount pre-assigned for reading it in; secondly, when a program obeys
OUT 1; and thirdly, when a program obeys OUT 2. In the last two cases,
the new program/section and its predecessor have the same E0, and the contents
of any part of the store common to both old and new programs/sections are
unaltered (provided, of course, that in the case of OUT 1, they have not been
overwritten by the latter). But the new program/section must not demand
more store space than the old: if it does, failure occurs. If the new
program/section has a blank store requirement, it is given exactly the same
assignment as its predecessor.
The new program/section has the same priority, and the same A/B character-
istic, as the old one, and, for an A program, is pre-allocated the same
peripheral units.
Only one A and one B program can be in the process of input at any time -
this includes the input of a new program/section after OUT 1, which may
therefore have to wait if program input is already going on at another
priority.
2.3 Housekeeping by the Director
Whenever any program is loaded it is assigned one of the four Sets of stacks
and Q-stores. Although a program may change its priority while it is in the
machine, it always keeps the same Set of stacks, etc., and so it is
convenient to identify each program with the number of its "Set". To avoid
confusion with priority numbers, the "Sets", and programs, are called P, Q,
R, and S. The bottom two bits of the octal representation of these
characters - 60, 61, 62, 63 - give the actual number of the "Set".
Inevitably, a great many of the "housekeeping" parameters used by the
Director are in groups of 4 consecutive words (quartets), one word for each
program. Within each quartet the words are arranged in priority number
order, so that the first word pertains to priority 0, the second to
- 11 -
priority 1, and so on. This arrangement is chosen (in preference to Program
letter order) because in practice the priority number occurs more naturally
and hence is a more convenient parameter for indirect addressing. In almost
every case in which the priority number is used for indirect addressing (or
for any other purpose) it is stored in M5, and so the convention is adopted
in this report of referring to e.g. "V29P104M5" as meaning "the 4 words
stored in V29P104, V30P104, V31P104 and V32P104, which have similar
significance in relation to priorities 0, 1, 2 and 3, respectively."
The housekeeping parameters which are particularly relevant to the storage
of programs in the machine are the single word V0P104, and the
quartet V9P0M5.
The most significant 24 bits of V0P104 are assigned in groups of 6 to the
four priorities so that D0-5, D6-D11, D12-17 and D18-23 correspond
respectively to priorities 0, 1, 2 and 3. The bits for priority 0 have the
following significance:
D5 = 1 if priority 0 cannot be entered for any reason (apart from
a peripheral hold up)
D4 = 1 if priority 0 is a pre-assigned "A" level
D3 = 1 if priority 0 is occupied by an "A" program
D2 = 1 if priority 0 is occupied by a "B" program. Obviously
D2 and D3 cannot both be non-zero; and if D3 = 1, D4
must be non-zero.
The corresponding bits of the other groups of six have the same significance
in relation to priorities 1, 2 and 3.
The "hold-up" bits, D5, 11, 17, 23, allow for every possible "software"
reason for not entering a priority, and could indicate, for instance,
that there is no program occupying a certain priority level, or merely
that the priority is held up pending the allocation of a peripheral
unit. Note that after obeying the instruction K5 (1.3, 1.6.9), bits D5,
D11, D17, D23 of N1 indicate peripheral hold-ups: and therefore the
sequence of instructions
V0P104; K5; OR;
will leave a complete indication in those bits of N1, of which priorities
can be entered and which cannot.
The quartet V9P0M5 contain the Base Address, Number of Locations and Priority
Number for each priority. Just before any program is entered the contents
of the appropriate word is transferred, by executing = K1 (1.6.5) to the
BA/NOL/CPL registers.
The quartet V9P0M5 therefore indicate the areas of store occupied by each
priority. This includes storage which may be in the process of being
"expanded" or "contracted" during program input - it may, for instance,
amount to only 32 words, during the input of the B-block of a B program.
The BA portion of any word of this quartet is zero if, and only if, there
is no vestige of a program at that particular priority level. It is
only when BA = 0 that D2 and D3 of the corresponding 6-bit group in V0P104
- 12 -
are both zero: as soon as a priority is assigned any storage at all, it
acquires the status of either an A or a B program, and keeps the status
just as long as it has a foothold in the store; i.e. D38-47 (BA) of
V9P0M5, and D2-3 of the appropriate group in V0P104 are set and cleared
together.
2.4 Program movement and priority interchange
One of the properties of KDF 9 Time-sharing is that programs may have
their priorities interchanged, and may be moved about in the store.
The priority of a program may be changed either as the result of a
TINT V, or following the priority upgrading which may occur at the end
of an A program. A program may be moved in the store as a result of
the ending of a program leading to the expansion of the "Hole in the
Middle".
As explained in 1.3 above, it is dangerous to change the priority of
a program while any part of its area is locked out, because it may
lead to a peripheral hold-up getting "stuck" in the wrong PHU register.
Similarly, a program may not be moved in the store while any part
of its area is locked out - a lock-out implies that a transfer is
going on in that area and so the contents of the area are liable to
change. Therefore if a reason for moving a program, or changing its
priority, occurs while any part of the programs area is locked out,
the details of the required, change are recorded (in the appropriate
member of the quartet V9P0M5), and at the same time the program is
temporarily prevented from resuming, using the appropriate bit in V0P104.
The impending change is recorded in V9P0M5 as follows:
D0-2 = quantity to be added to priority number
D14-23 = new value of BA.
The program is only allowed to resume when D0-23 are all zero.
Not only is the program held up when a priority change or store move is
impending, but also the Director must be prevented from starting any
peripheral transfer which involves the program's area, as this would
prolong the duration of the lock-out on the area. Therefore before any
peripheral transfer executed by Director, a check is performed that the
transfer area does not lie within a region belonging to a program which
is going to be moved or have its priority altered. Subroutine P103
performs this check, requiring as data the (absolute) addresses of the
transfer. This subroutine also performs another important function -
if the transfer is to be allowed to proceed, P103 alters the value of
CPL to that pertaining to the program whose area is involved. This
meets a requirement mentioned in 1.3; again, it prevents the probability
of a peripheral holdup getting "stuck".
When the priorities of two programs are interchanged the relative
positions of the relevant numbers of all the parameter quartets have to
be changed accordingly, All the quartets which have to be re-ordered
-13-
in this way are stored in the V-stores of P104, from V1 onwards. There
are two other quartets which require a slightly more complicated re-
arrangement: one is the quartet V9P0M5, in which the values of the
The manual reads V0P0M5 but this has to be a typo
priority number (D34-5) and the priority displacement (D0-2) have to be
modified as well; the other is the quartet V24P0M5, which comprises the
four "TAB" words, each containing the characters CR-LF, Case Normal,
then sufficient TABs to ensure that any message typed out for the
relevant program starts in the right column, the priority number and a
space: here the priority number (D40-1) has to be modified. In addition,
the appropriate sets of 6 bits in V0P104 have to be interchanged. Any
priority numbers recorded in special locations (e.g. the priority level at
which A or B program input is taking place, and the priority number of the
last program interrupted) must be altered it necessary. The priority -
dependent subprogram hold-up table (4.1.5) and subprogram numbers in the
various peripheral transfer queues (4.1.3) also have to be modified
appropriately, All these functions are performed by the subroutine P105,
which carries out all priority changes and store moves, and also
continually inspects the store and the state of the A programs to see
what new moves and priority changes need to be instigated.
When a program's area is moved in the store (also by P105), the appropriate
member of the quartet V9P0M5 has to be modified (D14-23 and D38-47). Also
any "absolute" addresses, in the subprogram tables and the various
peripheral transfer queues (see 4.105 and 4.1.3), which are affected, have
to be altered. This is all looked after by P105, which is entered after
every EDT,
The parameters contained in the various quartets of P104 are defined in
the User-code listing. One quartet, V25P104M5, is of particular interest
here. The "software hold-up" bit corresponding to any priority in
V0P104 is set if, and only if, the corresponding member of the quartet is
non-zero. The various bits in each word of this quartet, when non-zero,
each indicate a different reason for a holdup, as follows:-
D43 = 1 implies a store move and/or priority change impends
D44 " " a hold-up due to the "OUT 8" subprogram
D45 " " the program is suspended by TINT S
D46 " " the program is absent, or being input or terminated
D47 " " the main subprogram is active
The significance of D44 and 47 is explained in the sections dealing, with
subprograms (4.1.5, 4.1.6, 5.3), The termination hold-up, D46, is
described in 2.5, below.
The subroutines P113 and P114 are used respectively, to set and clear
bits in V25P104M5, and at the same time set or clear the hold-up bits
in V0P104, as appropriate.
2.5 Program Input and Termination
While a program is being input or terminated at any priority level,
entry to it is inhibited by the setting of D46 in V25P104M5, which
in turn sets the appropriate holdup bit in V0P104. This particular
- 14 -
hold-up covers all sorts of conditions, ranging from the complete absence
of the program (indicated by a zero BA in the relevant member of V9P0M5,
and no B or A "program present" bit in V0P104), through the first stages
of program input (when the program, still anonymous, has a small foothold
in the store), to termination by TINT A, OUT 0, OUT 1, or OUT 2.
These different conditions are indicated by the quartet V29P104M5, the
various bits of each member of which having the following significance:
D0 = 1 during termination of a program, indicates that the
termination of "OUT 8" - type procedures is awaited. The
main termination subprogram is held up at one stage until
the subsidiary (OUT 8) subprogram has completed sequences,
which lead to this bit being cleared.
D1=0,D2=1 this combination of bits occurring during program input
indicates an input holdup - due e.g. to lack of a program
input device, or sufficient core store - such that the
input process can be terminated by TINT A. If TINT A
is performed while V29P104M5 contains this pattern, it is
converted to:
D1=1,D2=1 which causes the input procedure to be appropriately
cancelled (if TINT A is performed while V29P104M5 is
non-zero, but contains some other combination in these
bit positions, it is ignored).
The execution of TINT E (A or B as appropriate) while
an A or B program is awaiting a program tape, i.e. while
the member of V29P104M5 corresponding to that program has
D1 = 0, D2 = 1, will cause D2 to be reset to zero.
D47 = 1 during the input or termination of a program, indicates
that it is a B program,
D46 = 1 OUT 1 in progress
D45 = 1 TINT A or OUT 0 in progress, or normal program input
D44 = 1 OUT 2 in progress
While a priority level is unoccupied, and is not involved in
program input, the relevant member of V29P104M5 contains 5 (D45
and D47 = 1) regardless of whether the priority level is A or B.
Program input is performed by the subroutines P120 and. P52 - the latter
handles B program input (TINT T) in its initial stages and soon joins
P120. Program input is carried out using the main subprogram (see 4.1.5)
of the priority level concerned, so that effectively it is an activity
having the same priority as the program it is loading. Advantage is
taken of the restriction that not more than one A program and one B
program can be in process of input at one time, in that only 2 sets
of the parameters relevant to these activities need be stored: these
- 15 -
are kept in V0-2 of P120 (A programs) and P52 (B programs), as follows:
V0 = priority level at which input is taking place
(negative if inactive)
V1 = program tape number (A or B)
V2 = input paper tape reader (must be cleared as soon as
PTR is finished with)
The instruction sequences in P120 for A or B program input are largely
identical. A useful subroutine is P124, which, given the priority
number in M5, sets the address of either V0P120 or V0P52 in M6 according
to whether an A or a B program is being input at that priority level -
i.e. according to whether D47 of V29P104M5 is 0 or 1.
The subroutine P121 deals with all CRNP failures, including those
following OUT 1.
Program termination is performed by subroutines P15 (OUT 0), P16
(OUT 1) and P17 (OUT 2). P17 and P33 (TINT A) both lead into P15.
Program failures are handled by P2, which also leads to P15 if the
failure results in program termination.
- 16 -
3. Interruption processing
3.1 Paths through the Director
As in the non-Time-sharing Director (N.4) there are two main paths
through the Time-sharing Director from the interrupt entry at word
0 to resumption of a program. Fig. 1 shows them in outline.
- 17 -
The coding for both paths comprises P0 of the Director.
The "standard preliminaries"mentioned in Fig. 1 are the instructions:
Q0; SHL+63; =+Q0;
SET B140000; =K1; ERASE;
which are stored in words 0 and 1 (by the Director Call Program).
Because both paths require the use of at least one Q-store, Q5 is
dumped before the paths diverge. Similarly the state of the overflow
and TR are recorded. In this context "recorded" implies that they are
stored in the member of a quartet - V1P104M5, in this case - which
pertains to the program interrupted (the priority of this program is
to be found in V7P0). "Dumped" implies parking temporarily in a
single location.
The Short path is followed if one of the RFI's LOV or PR occurs and
no other. Any other RFI (CLOCK, FLEX, LIV, NOUV, EDT, OUT, RESET, or
the abnormal absence of any RFI's at all) sends the Director down the
Long path.
The Link is not dumped (as happens in the non-Time-sharing Director, N4.1)
but no subroutine entry is made until NOUV has been dealt with, to avoid
the risk of corrupting the contents of SJNS (N2.2.3).
A Director/Program marker (V28P0) is used to record whether the machine
is in Director mode or not. It is examined, and set to zero, immediately
after the "standard preliminaries". An interruption occurring while this
marker is zero leads to a loop stops, typing
FAILS
FAILS etc.
(This loop stop also occurs if any other hardware malfunction occurs to
make the Director behave in a logically inconsistent way).
3.2 The Short Path
Following the standard initial steps described above, the subsequent
actions of the Director as it proceeds along the Short path fall into
three stages:-
Stage (a): Accounting. This consists of augmenting the run time record
of the program interrupted, and checking that its time limit has not been
exceeded (if it has, the Long Path is entered).
Stage (b): The hold-up bits in the PHU store and in V0P104 are examined
to determine which is the highest priority program not held up for any reason.
If there is no eligible program, the Long Path is entered.
Stage (c): Once the return priority has been determined, the Director
carries out functions in respect of the new program which are more or less
complementary to those carried out in the initial steps and stage (a) in
respect of the interrupted program - it updates the run time record, sets
up overflow and TR appropriately, resets CPDAR, and finally restores the
previously dumped Q5 and brings into action the new Set of stacks and Q-
stores (first having recorded their erstwhile state in the right member
of the quartet V13P104M5) before resetting (non-zero) the Director/Program
marker, and obeying the sequence of instructions
*=K1; ERASE; EXITD;
to reenter the chosen program.
- 18 -
Note that, just as in the non-Time-sharing Director, not more than 3 and
1 cells of the Nest and SJNS, respectively, are used along the Short Path,
and the RFIR is only inspected once.
Stage (a) is common to all paths through the Director. The Long path usually
rejoins the Short path before, but sometimes after, stage (b).
3.3 The Long Path
The outstanding difference between the Long paths of the Time-sharing
and non-Time-sharing Directors is that, whereas in the latter all sequences
of instructions are constrained to use only 3 cells and 2 cells, respectively,
of Nest and SJNS, in the former the contents of both Nest and SJNS are
completely dumped so that their full capacity may be used. The adaptability
which results from this more than compensates for the additional storage
required for dumping. Note that there is no conflict here between the
provision of 4 Sets of Nests, etc, and the idea of dumping the Nest and
SJNS in the core store - the object of the former is to make the frequently-
used Short path as fast as possible, while the latter is aimed at simplifying
the coding of the comparatively rarely used, but much more complicated, Long
path. This dump only holds the Nest and SJNS of one program (the one last
interrupted), not of all four.
Altogether four Q-stores - 4,5,6 and 7 - are dumped, and may be used by
the Long path.
There are three "entries" to the Long Path (see fig. 1), and two "ways out".
The first step on each entry is to dump Q4, Q6 and Q7, and the contents of
the Nest and SJNS (which will be the ones corresponding to the interrupted
program, whose priority number is in V7P0), and the last step before
leaving (to join stage (b) or (ci of the Short path) must be to restore
Q4,6 and 7 and refill the (empty) Nest and SJNS. Thus within the region
bounded by the dotted line in fig. 1, 19 and 17 cells, respectively, of
Nest and SJNS may be used, with Q4, Q5, Q6 and Q7 - and, of course, overflow
and TR.
It may be necessary at various points in the Long path to manipulate the
contents of a program's Nesting store or. SJNS: this may not necessarily
be the program which has just been interrupted, so these contents may be
either in the "Dump" or actually In one of the 3 "Sets" which are not
currently in use. In order to carry out these manipulations a multiple-
entry subroutine, P29, is used. This requires as a parameter the priority
number, in M5, of the program whose Nest or SJNS are to be manipulated.
The entries are :
1P29 Fetch one item from program's Nest
2P29 Store one item into program's Nest
3P29 Erase one item from program's Nest
4P29 Clear program's Nest altogether
5P29 Fetch one item from program's SJNS
6P29 Store one item into program's SJNS
7P29 Clear program's SJNS altogether.
- 19 -
Here "Nest" and "SJNS" refer specifically to the contents of those belonging
to the nominated program. Fetching and storing have the usual erasing and
nesting effects on them. The item transferred will be brought to, or taken
from, N1 of the Director's Nest. The validity of each operation is indicated
by the EXIT from P29 (EXIT 2 - valid, EXIT 1 - invalid).
Certain sequences in the Long path (OUTS and program failures) do not
use P29 initially to manipulate the Nest and SJNS, but operate directly on
the "dump". This is perfectly legitimate because (a) the operations are
performed on the Nest or SJNS of the interrupted program, and (b) they are
performed before there has been any "hold-up" in the instruction sequence
from the time of interruption. However once any of these Long path
activities are suspended for any reason, an resumption they are not entitled
to assume that the contents of the "dump" pertain to the same program as
before, because during the suspension other programs could have been
re-entered, and the contents of the dump will always belong to the last one
entered. P29 always knows whether the Nest or SJNS it wants is in the dump
or not by comparing M5 with V7P0, which contains the priority number of the
program occupying the "dump".
The three entries to the Long Path are, in order of possible occurrence,
(A) immediately after the initial steps (3.1), if any RFI2s other than PR
or LOV are found, (B) after stage (a) of the short path, if the time limit
has been exceeded, and (C) after stage (b) of the Short path, if there are
no eligible priorities to re-enter. Entries (A) and (B) are strictly
"Phasel", but entry (C) may occur repeatedly in "Phase 2".
Entry (A) uses the subroutine P1 to dump the Nest & SJNS and Q4,6,7 unless
NOUV has occurred, in which case the dumping is slightly different. P1
parks N1 onwards in V0P1 onwards, S1 onwards in V16P1 onwards, and the
numbers of items in the Nest and SJNS in V32P1 and V33P1, respectively.
The NOUV dumping procedure is similar, but only N1 and N2 are dumped, in
V0P1 and V1P1 (the remaining Nest items are erased); and if the capacity
of the SJNS has been abused, S1 is dumped in V34P1 and the remaining SJNS
items in V16P1 onwards (with a marker in V6P12). Following a NOUV, the
"dump" cannot be restored to the Nest and SJNS, so must be typed out, and
cleared, before any "hold-up" in the instruction sequence occurs.
Entries (B) and (C) both start with Pl. Entry (A) is followed by accounting
procedures (similar to stage (a) of the Short path) which take account of
the possibility of a clock interrupt. The next step, at which entry (B)
also joins, is to deal with program failures (using P2) and OUT (P3). **After
this, P4 is entered if FLEX has occurred, P5 if EDT has occurred. Next
(entry (C) joins here), P60 is entered to have another look at the RFIR.
P60 corresponds more or less to the subroutine /RWR/ in the non-Time-sharing
Director: it has only one EXIT, but leaves a marker in N1 which is non-
zero if FLEX, EDT or CLOCK RFIes have occurred. If N1 is non-zero on this
occasion, the Long path returns to the doubly asterisked step above
As soon as P60 has left a zero in N1, the Nest and SJNS, being empty, are
refilled from the V-stores of P1, and Q4,6 and 7 are replaced. The Short
path is now rejoined, between stages (a) & (b) if V14P0 is negative, other-
wise between stages (b) and (c). V14P0 is a marker whose contents, if non-
negative, are a "return priority number" generated by P5 (after an EDT
interrupt) for reasons connected with the forcible clearing of PHU
registers (see 1.3)