- 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)