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.