KDF9 TIME-SHARING DIRECTOR
SUPPORT DOCUMENTATION
This report contains a detailed description of the inner workings
of the Time-Sharing Director. The report is provided as 'support documentation'
in the sense described in section 2 of the KDF9 Service Routine Library
Manual.
The report should be read in conjunction with the coding (which can
be obtained from the current NINEMASTER - see Service Routine Library Manual)
and the corresponding report on the Non-Time-Sharing Director. References
are made to section A of the latter - by the letter 'N' followed by the
appropriate section number.
The Director described is the Standard Time-Sharing Director and the
report takes no account of optional extra facilities.
The Company reserves the right to change the information contained in
this report without notice.
LIBRARY SERVICES,
SYSTEMS PROGRAMMING DEPARTMENT.
1ST MAY, 1965.
CONTENTS
Page
1 Hardware Features 1
1.1 General 1
1.2 Priorities 2
1.3 The Program Holdup (PHU) store 2
1.4 Program Ready RFI 4
1.5 Switching of Nests, etc. 5
1.6 Summary of Director-only instructions 7
2 Storage and input of programs 8
2.1 A and B levels 8
2.2 Storage assignment 9
2.3 Housekeeping in the Director 10
2.4 Program movement and Priority interchange 12
2.5 Program Input and Termination 13
3 Interruption Processing 16
3.1 Paths through the Director 16
3.2 The Short Path 17
3.3 The Long Path 18
3.4 Timing 20
3.5 V-stores of P0 20
4 Hold-ups and Subprograms 21
4.1 Types of hold-up. Action following EDT 21
4.2 FLEX. The action of P4. 32
5 OUTs (P3, etc.). Program Failure (P2) 36
5.1 P2 (Program Failure) 37
5.2 OUT Routines 38
5.3 P23 and OUT 8 42
6 Subroutine Index 45
- 1 -
1. Hardware Features
1.1 General
Before describing the special hardware features of the Time-Sharing
KDF9 in details a brief account of their objectives is necessary.
The standard (non-Time-Sharing) KDF9 is already provided with
Interruption facilities which enable the operating program to be
interrupted automatically, and thus to pass control to the Director,
when the program is held up by the action of a peripheral transfer -
either because it wants to use the peripheral unit involved or
because it requires access to the area of core store which is locked-
out for the duration of the transfer. However, there is no hard�
ware which will record automatically which peripheral unit or which
part of the core store, is causing the hold-up. Nor is there any
indication given at the end of a particular transfer that was the
cause of a hold-up.
The object of "Time-sharing" in KDF9 is to be able to have more
than one program (besides the Director) stored in the machine at a
time, and to run them on a "priority" basis, so that the highest
priority program runs until it is held up (or ends), when control
will be passed, via Director, to the next priority, which in turn
runs until it is itself held up or ends, or until the conditions
which caused any higher priority program to be held up are removed:
and so on. Thus, whenever a program is interrupted, one expects the
Director to return control to one of the other programs, rather than
waiting until the interrupted program can resume.
The existence of the KDF9 "Base Address" (N1.1) and the store and
peripheral protection facilities provided by NOL (N2.1.3) and CPDAR
(N2.1.4) make the storage (and movement) of several programs a safe
and comparatively simple process. However, to implement efficiently
the priority system describes above, four extra hardware facilities
are required, which make the difference between. a "Time-sharing" and
a. "non-Time-sharing" KDF9:-
(a) a method of associating a priority with each program;
(b) a "Program Hold-up" store to record in a dynamic manner
which programs are held up at any time, and why;
(c) an RFI which will cause a program, to be interrupted on
the removal of a holdup condition which was causing any
program of higher priority to be held up;
(d) a method of speedily interchanging the contents of the
Nest, SJNS and Q-stores, for any two programs, so that
the transfer of control from one program to another is
as fast as possible.
The hardware implementation of these facilities, and the instructions
which use them, are described below.
- 2 -
1.2 Priorities
Whenever any program is running it has associated with it a "current
priority level" (CPL) in the range 0-3. This number is kept in a
2-bit register which is set by the instruction = K1 (N 1.2, N 2.1.3)
which� besides transferring D38-47 of N1 to BA and D24-33 to NOL,
sets CPL equal to the value given in D34, 35 of N1.
Priority 0 is the highest priority, priority 3 the lowest.
It would be possible for several co-existent programs to have the
same priority� but this contradicts the principles underlying the
design of the PHU store (see 103 below) and the multiple Nesting
stores, so in practice there are up to 4 programs, each with its
own priority number.
It is customary to refer to "Priority n" as meaning (in the right
context): "the program which runs at priority level n". It is
possible, subject to certain practical restrictions� to alter the
priority of a program.
The Director itself customarily runs with priority 0 but this has
no great significance. For reasons explained below (1.3), when the
Director is about to execute a peripheral transfer on behalf of a
program (i.e. involving that programs core area) CPL must be set to
the value of that programs priority.
The actual significance of CPL is two-fold: firstly, any peripheral
transfer has associated with it for its entire duration the value of
CPL when it was called (this affects what happens when the transfer
ends); and secondly, it determines whether or not the PR RFI (1.4)
occurs when a peripheral hold-up is removed.
1.3 The Program Hold-Up (PHU) store
This is a set of four 12-bit (D0-11) registers called PHU0, PHU1,
PHU2 and PHU3, Which are used to record, dynamically, peripheral
holdups incurred by priorities 0,1,2 and 3 respectively.
When priority n is interrupted because of a peripheral hold up
(LOV), PHU n automatically records the hold-up as follows: Dll is
set to 1, and D10 is set to 1 or 0 according to whether the hold-up
is due to a reference to a busy peripheral buffer, or to a locked-
out core area. In the former case the busy buffer number is stored
in D6-9 (D0-5 are cleared), in the latter case the most significant
10 bits of the 15-bit absolute address of the locked-out location are
stored in D0-9. This is known as the "group address".
The PHU store is not altered if LOV occurs in Director mode, i.e. if
the Director refers to a busy buffer or locked-out area.
- 3 -
PHU n is also altered if priority n executes the instruction
"INTQq", referring to a busy buffer. Again Dll and D10 are set
to 1, the buffer number is stored in D6-9, and D1-5 are cleared:
but D0 is set to 1.
Note that D11=1 in PHUn implies that priority n is held up by a
peripheral transfer.
The end of a peripheral transfer which was called by priority n
(i.e. called at any time, in Director or program Mode, when CPL
had the value n) will cause PHU n to be cleared if and only if,
(a) D0, 10 and 11 of PHU n are all non-zero
or (b) D10 and 11 are non-zero and the buffer whose number is
given by D6-9 is not busy
or (c) D11 is non-zero, D10 is zero., and D0-9 give the absolute
group address of a block of 32 words which is not locked-
out.
This represents the removal of hold-ups due to (a) "Interrupt if
Busy" - the holdup being removed at the end of any transfer called
by priority n; (b) reference to a busy buffer; c) reference to a
locked-out part of the store.
In simple terms, PHU n is set automatically when priority n is held
up, and will be cleared automatically at the end of the appropriate
peripheral transfer, provided that that transfer was called by, or
on behalf of the same priority, i.e. when CPL was equal to n.
It is possible to ensure that PHU n will always be cleared automatically
in the "lock-out" holdup case (c) by arranging, firstly, that no
program ever transfers into another programs store area (with the
proviso mentioned above, that when the Director starts a transfer
involving a priority's area, that priority number must be in CPL);
and secondly, that no program ever has its priority number changed
while any part of its area is locked-out. Thus no priority can be
held up by a lock-out set by another.
However it is impossible to ensure that no program ever refers to
a buffer which has been made busy by another program, An obvious
example is the "shared" magnetic tape buffer, which is made busy
when any one of the units connected to it - which might be allocated
to different priorities - is carrying out a transfer. Therefore, in
order to avoid a situation which could involve a program being
apparently held up for ever, the hardware is so arranged that at the
end of any peripheral transfer called by priority n, not only is
PHUn examined and, if need be, cleared, but also the remaining
3 PHU registers are examined, and if any of them are showing "busy"
hold-ups due to a buffer which is no longer busy, the EDT RFI is
set (EDT will of course be set anyway if the transfer was called
in Director mode).
- 4 -
Note that these other PHU registers are not cleared, in this case.
To do so would be dangerous: it is preferable that the Director
should be made more positively aware of the situation, in order
that it may decide whether or not to over-rule the normal
priority rules in this case; to allow one of the lower priority
programs to use the shared buffer, for instance. In a case where
two programs are sharing a buffer, and the higher priority of the
two makes frequent use of it while the lower priority only uses it
occasionally, a judicial reversal of priorities, to allow the lower
priority access to the buffer in preference to the higher, can lead
to more efficient operation.
In order to have the necessary control over the PHU store, the
Director must be able to examine its contents, and to clear the
individua1 parts of it.
The instruction K5 causes the least significant 6 bits of each
part of the PHU store to be brought into N1, nesting down one place.
Thus,
D6-11 of PHU0 occupy D0-5 of N1
" " " PHU1 " D6-11 " "
" " " PHU2 " D12-17 " "
" " " PHU3 " D18-23 " "
Thus the Director can tell which priorities are held up at any time,
which are held up by busy buffers, and in such cases, by which buffers.
The instruction CLOQq, as well as clearing lock-outs from the specified
area, also causes PHUn to be cleared, where n is the value of CPL
when the instruction is obeyed.
Note that the Director can determine when a program is held up by a
lock out, but not the address involved (because it only sees 4 bits
of this address).
The effect of all this is that Director must always look at the PHU
store to determine which priorities can be resumed, i.e. are not held
up: and also, whenever EDT occurs, Director must see whether any
parts of the PHU have to be cleared, and, if so, whether the normal
priority system should be over-ruled.
1.4 Program Ready RFI
If at the end of a peripheral transfer called by priority n, the
procedures described above lead to the automatic clearing of PHU n:
and if n is less than the value of CPL, an RFI called "Program Ready"
(PR) is set.
- 5 -
In practice this means that if the hardware detects the end of a
peripheral hold-up on a program which is of higher priority than
the one currently operating, an interruption occurs.
This RFI corresponds to D22 in the copy of RFIR which the instruction
K4 (N2.1.5) transfers to N1. When this RFI is detected the Director
is expected to look at Dll of each part of the PHU store to see which
priority can now resume.
The same process will follow the occurrence of the LOV interrupt.
LOV corresponds to D28 in N1, after K4. In this case a change to
a lower priority level can be expected.
The normal setting of PR is inhibited when the transfer whose
ending led to the clearing of the PHU register is also found to
have been the reason for "buffer busy" hold-ups at other priorities:
in such cases EDT is set anyway, as described in 1.3 above.
PR is also set by the instruction "Interrupt if Busy" (INTQq) when
the relevant buffer is found to be busy, in order to cause the
required interruption. This avoids the need to have a separate RFI
for this case. The same action is required of Director as in the
normal PR or LOV interruptions.
1.5 Switching of Nests, etc.
To provide the necessary rapid changeover of the contents of Q-stores,
Nests and SJNS's, four Sets of each are provided on the Time-sharing
KDF9, together with instructions for switching from one to another.
The Sets are numbered 0-3 but this numbering is completely independent
of the priority numbering system. Each Set comprises 15 Q-stores
(1-15), a Nesting-store stack of sixteen 48-bit cells, and an SJNS
stack of sixteen 16-bit cells. The two stack counters are not
quadruplicated, nor are the overflow and Test registers.
In order to switch from one Set to another, it is necessary to obey
the instruction =K3 with the following parameter in N1:
D0,1 = New Set number
D2-6 = Value to be put in the Nest Stack Counter
D7-11 = Value to be put in the SJNS Stack Counter
The effect of the instruction is to bring into action the new Set
specified by D0,1, and to replace the current values of the Nest
and SJNS stack counters by the specified values. No nesting is involved
in this operation.
The instruction =K3 should be followed by six DUMMY instructions to
allow the new Set time to settle down.
- 6 -
Since it is only the stacks that are involved, the top 3 and 1
cells, respectively, of the Nest and SJNS are not affected. There�
fore whenever control is passed from one program to another, it is
necessary, before obeying =K3, to insert 3 and 1 "dummy" items,
respectively, into these positions, thus causing the (up to) 16
items in each which must be preserved to be nested down completely
into the stacks. The dummy item in N1 must be the parameter for
=K3. Between performing the interchange and returning to the new
program, these dummy items have to be removed. Heading the (up to)
16 items which are preserved in the SJNS stack is the return address
to the program.
Although the instruction =K3 does not alter the contents of either
the "old" or "new" Set of Q-stores and stacks. it does cause the
two stack counters to be overwritten. In order to preserve their
values for future use, the instruction K7 is provided, which fetches
into N1 the current "Set" number, and the current values of the stack
counters, in the same format as for =K3. Here a slight complication
is involved, because K7 nests down one place, but fetches the values
of the stack counters before this nesting operation has been recorded.
So to get a true record of the state of the counters after obeying K7,
it is necessary to add D6 to N1 -- the equivalent of adding 1 to the
Nest stack counter.
Illustrated below is a typical sequence for interchanging two Sets.
Here, the initial and final states of the nests are exactly as they
would be on entry to, and exit from, the Director.
(a) Insert one dummy link in SJNS.
(b) Insert two dummy items in Nest.
(c) K7; (nests down one place).
(d) Add D6 to N1, without nesting down further (by e.g.
SHC+7; NOT; NEG; SHC-7;)
(e) Store N1 (old Set parameter) in a suitable location
(f) Fetch new Set parameter to N1.
(g) =K3; DUMMY; DUMMY; DUMMY; DUMMY; DUMMY;
(h) Erase three items from Nest.
(i) Erase dummy link from SJNS.
When adding corrections to the "stack counters" in N1 (as fetched
by K7) it is important to ensure that no spill occurs from one
"counter" to the other, or into the Set number position. This could
only happen if NOUV had occurred.
The "Set parameter" used in the example is the record of the Set
number and the stack counters actually used by =K3. It therefore
shows excesses of 3 and 1, respectively, in the Nest and SJNS stack
counters over the values these took just after the program they
pertain to was interrupted.
- 7 -
Operations (e) and (f), above, would in practice probably refer to
locations which depend on priority numbers, so the addresses used
are likely to be modified by the contents of Q-stores. Care must
be taken to ensure that those Q-stores have the correct values
(their contents before interruption) restored to them before =K3
is obeyed.
1.6 Summary of Director-only instructions
This includes all the instructions of this type used by the Time-
sharing Director, Some of these have greater power than they do
in a non-Timesharing KDF9.
1.6.1 EXITD (N 1.2)
1.6.2 CLOQq (N2.1.1) As well as clearing the lockout specified
by Qq, this instruction also clears PHUn, where n is the
current value of CPL
1.6.3 CTQq (N2.1.2) Clear transfer
1.6.4 =K0. Switch buzzer on or off. There is a "buzzer"
attached to KDF9 which can be switched on or off by
obeying =K0 with the contents of N1 non-zero or zero
respectively. No nesting. Thus, to switch off the
buzzer, one obeys: ZERO; =K0; ERASE;
1.6.5 =K1. (N2.1.3) This instruction transfers D24-33 of N1
to NOL, D34-35 to CPL, and D38-47 to BA. No. nesting.
1.6.6 =K2. (N2.1.4) Set CPDAR. No nesting
1.6.7 =K3. Brings in a new Set of Q-stores, nests, etc., using
a parameter in N1. No nesting
(D0, 1 = New Set number
D2-6 = Nest stack counter
D7-11 = SJNS stack counter)
1.6.8 K4. (N2.1.5) Fetch RFIR and Clock. Two significant
RFIs are PR (D22) and LOV (D28). Nests down 1 place.
1.6.9 K5. Fetches l.s. 6 bits of PHU0, PHU1, PHU2, PHU3, to
D0-5, D6-11, D12-17, D18-23, resectively, of Nl. Nests
down 1 place.
1.6.10 K7. Fetches current Set number, and Nest and SJNS stack
counter values, to N1, in format as for =K3. Note that
the value of the Nest stack counter shown in D2-6 is 1
less than the value it actually has after obeying this
instruction, because of nesting down 1 place.
- 8 -
2. Storage and input of programs
2.1 A and B levels
The Time-sharing Director can store up to four programs in the machine at
once, each at a different priority level.
The four priority levels are divided, while the machine is running, into
two types, A levels and B levels, and the programs in these levels are
referred to a A programs and B programs. The levels to be used as A
levels are specified when Director is input. Any number of A levels,
from none to four, can be specified.
The A programs work in a �sausage machine� - when one finishes, any A
programs lower in priority are upgraded automatically, and a new A
program is called for into the lowest A level. B programs are only read
in by a typewriter interrupt.
In order that, when any A program finishes, it should be possible to
replace it immediately by any other -usually the next in a "queue"
prepared by off-line or on-line scheduling - it is necessary that all
A programs should operate within the same machine configuration, in
respect of core storage and "unlabelled" peripheral units (including
paper tape readers, punches, printers, etc., but excluding magnetic
tape units, drum and OUT 8 output streams). The A program "Configuration"
is supplied by the operators when the Director is loaded, as well as the
priorities to be used by A programs.
The decision as to whether a given program is A or B is usually made off-
line on the following basis. Suppose n A levels are specified when
director is read in (n . 1,2,3 or 4. If n 0, the problem does not
arise). Then a program is an A program, and so can be read into an A
level, if there are enough core-store and peripheral devices (other, than
magnetic tape units) for n such programs to run simultaneously on the
machine. Thus if a machine has 16K of core-store, 2 p.t. readers, 2p.t.
punches, 1 line printer and 1 card. reader, and if 2 A levels are specified,
then any program needing not more than 1 pot. reader, 1 p.t. punch and 8K
of core-store, and not needing a line printer or card reader can be an A
program. Any other program will be a B program. It is entirely up to the
Operator which category a program belongs to.
The devices that an A program needs are given ("pre allocated") to it when
it is read in (the program still has to do OUT 5 to get them allocated to
it), and remain with it the whole time it is in the machine. As soon as
it is off the machine, these devices will be among those available for
the next A program (provided they are not required by a higher priority),
which is read in on the �sausage machine� principle described above Thus
the whole time an A program is in the machine, the operators know precisely
which devices it will be using.
- 9 -
2.2 Storage Assignment
The part of the core store which a program occupies - always a continuous
area, and a multiple of 32 words beginning at an absolute address which
is also a multiple of 32 - is said to be "assigned" to the program. The
total area available for assignment to programs extends from the very top
(highest address) of the store, down to the lowest word in the store which
is not part of the Director, and whose address is a multiple of 32.
"A" programs are stored at the top of this area, and B programs at the
bottom, next to Director. The Director constantly inspects the store
assignments to ensure that programs are packed tightly next to one
another, and to the limits of the available area. As a result of this
it is necessary, from time to time, for the Director to physically move
programs in the store. This always involves moving a program - that is,
the whole of the area assigned to a program - into a vacant, unassigned,
area next to it; there is no question of ever interchanging the locations
of two programs, nor do programs "leapfrog" over one another. The effect
is of "sliding" programs up or down the store, according to whether they
are A or B, respectively.
This ensures that whatever space becomes vacant. as programs expire,
accumulates in the middle, between the B and A programs. New programs
are input to this area, known as the "Hole in the middle".
A "B" program, whose input at a nominated priority is initiated by a
typewriter interrupt, will be read into the bottom end of the Hole. As
soon as there are available a paper tape reader not required. by a higher
priority, and 32 words of store in the Hole, this area is assigned to
the program, and the A and B-blocks are read in subsequently the amount
of store indicated by the store requirement in the B-block will be
obtained by assigning any vacant storage as soon as it becomes available
in the Hole (provided it is not required by A program input at a higher
priority) until the requisite amount: has been assigned: then the C-blocks
can be read in and the program will start.
During the delay that there may be whilst the program is waiting to obtain
enough store, or between the input of C-blocks, the assigned area may be
moved down the store to take over space vacated by other B programs which
have terminated, in the way already described.
The priority nominated for the input of a B program may be one of those
nominated for A programs. In this cases that priority ceases to be "A"
for the duration of the program.
Director will call for the input of an A program when the following
circumstances obtain:-
(a) a vacant A priority is available which is lower than all those
currently occupied by A programs
and (b) the A program peripheral requirement can be satisfied.
and (c) there is enough space in the "Hole in the middle" to meet the
pre-ordained A program storage requirement.