CA1103368A - Task handling apparatus for a computer system - Google Patents

Abstract

TASK HANDLING APPARATUS FOR A COMPUTER SYSTEM

Abstract of the Disclosure Task handling apparatus in a computer system is structured to be common to system control tasks, user tasks and I/O tasks.
Although the task handling apparatus contains a task priority structure, all tasks are handled in the same manner, and there are no fixed interrupt levels for I/O tasks. There are N levels of priority, and N is variable. Each task is a server for a functional request. Task dispatching elements (TDE's) are enqueued in priority sequence on a task dispatching queue (TDQ). A task dispatcher functions to dispatch the highest priority TDE on the TDQ, if any, and to perform task switching. Intertask communication is accomplished by send message, send count, receive message and receive count mechansisms, and is coupled with task synchronization. Task synchronization is achieved by dequeueing and enqueueing TDE's on the TDQ. An active task becomes inactive dispatchable when a higher priority TDE is enqueued on the TDQ by send message or send count mechanisms.
The active task becomes inactive waiting when a receive message or receive count is not satisfied. An inactive dispatchable task becomes the active task when it becomes the highest priority enqueued TDE on the TDQ by the receive message or receive count mechanisms.
An inactive waiting task becomes either the active task or an inactive dispatchable task after being enqueued on the TDQ by the send message or send count mechanisms, depending upon whether it is the highest or other than the highest priority TDE on the TDQ.

Description

3~

] Background of tlle Invention _ _ . _ _

2 1. Field of the Invention

3 This invention relates to stored program digital computer

4 systems, and more particularly, to apparatus for controlling execu-tion of tasks and task switching.
6 The invelltion finds particular utility in stored program 7 computer systems configured to operate interactively with terminal 8 operators, or in stored program computer systems having need to 9 execute a large number of jobs operating in a batch mode such as in a large multiprogramming environment.
11 2. Description of the Prior Art 12 ln the past, stored program computer systems used a com-13 bination of hardware and software for performing the task handling 14 and switching function. The combination of hardware and software includes an interrupt structure witil a fi~ed number of interrupt 16 levels or classes incorporated into hardware, with software resolving 17 contention among tasks on the same interrupt level. Additionally, 18 prior art systems had one priority resolution mechanism for CPU
19 tasks and another priority resolution mechanism for input/output tasks. In the present invention, the priority resolution mechanism 21 or task han~iling function is entirely in hardware, and a common 22 mechanism is used for the CPU and the input/output tasks. By this 23 arraogement task handling performance co~parable to prior systems is 24 obtainable with a lower performance central processing unit. In 2S tile past, it was only feasible to use computers l1aving high per-26 formance central processing units for computer job applications 27 requiring a large number of tasks. Furtller, unlike an interrupt 28 driven system of the prior art, there is no forced switching to R0976~014 2 ~7 il~3~
Back~-ound of the lnventioll (continued) 1 I/0 processing level by the need for servicing I/0 interrupts.
2 The need for service ~y an I/0 device is posted in the task handling 3 apparatus and tlle I/0 device is serviced only when the associated 4 I/0 task becomes the highest priority task in the system. The status oE the I/O device requiring service is acquired after the 6 request for service during the oext instruction fetch cycle, or 7 at predetermined times during execution of certain current instruc-8 tions of the active task. An instruction fetch cycle of the active 9 task always includes a test for ascertaining the need for I/0 cycles for savlng l/0 status. Also, during execution of certain 11 instructions such as complex instructions, testa are made for 12 determining the neecl for handling I/0 events. After the I/0 event 13 is handled, a task switch may or may not take place, depending 14 upon whether or not the I/0 task requesting service has a priority higher than the active taak 16 Summary oL the Invention 17 Th2 principal objecta of the invention are to provide 18 improved task handling apparatus which (a) has a fast response 19 time, (b) enables the use of a relatively low performance central proce6aing unit in a computer system operating in an interactive 21 mode, (c~ has N levela of priority rather than a fixed number, (d) 22 enables priorities to ~e set under program control, (e) is common 23 to system control task6, user tasks and IJ0 tasks, (f~ couples 24 intertask communication with task synchronization, (g) can operate with either virtual or real storage arrangements for all ....

111~3~
Sunul~ary of tlle Inven~ion (continued) 1 task handling functions including I/0 tasks and (h) captures 2 status of an I/0 device requiring service whether or not the 3 I/0 task for providing the service is the active task.
4 The foregoing o~jects are achieved by structuring the task handling apparatus to include a task dispatcher and an inter-6 task communication mechanism. Tl~e task dispatcher renders the 7 highest priority task dispatching element (TDE) on a task dispatching 8 queue (TDQ) active. TDE's are on the TDQ in priority sequence.
9 There are N levels of priority, and N is variable. Each task has a priority key which can be changed under program control. The 11 active task causes instruct~ons to be executed whereby work is 12 performed, or it communicates with other tasks requesting the other 13 tasks to do some work. The other tasks are either in an inactive 14 dispatchable or inactive waiting state. The instruction fetch cycle of the active task always first tests ~or the need to execute 16 I/0 event cycles or dispatch cycles. I/0 event cycles have priority 17 over dispatch cycles. The status of an I/0 device is obtained 18 during I/0 event cycles. Dispatch cycles provide for storing 19 the status of the old task dispatching element (TDE) and ~or loading the CPU facilities with the status of the new TDE. Task 21 status includes an instruction address, instruction length count, 22 condition code and base registers.
23 The intertask com~unication mechanism includes send 24 count, send message, receive count and receive message mechanisms.
The active task invokes the send message or send count mechanisms 26 to ask another task to do some work, and invokes the receive count 27 or receive message mechanisms to determine lf the work was performed 28 by the other task. If the receive count or receive message is not Su~mary o~ thc ~ ult iOIl (contin~

l satisfied, i.e., Llle work has not been done, the active task is 2 de~ueued from the 'l'D~ ~nd put into the inactive waiting state by the 3 receive mechanic;ms. 'lhc waiting is done on a send-receive message 4 queue (SRQ) or on a send receive counLer (SRC). The highe~t priority TDE on the TDQ is then dispatched as the active task. The 6 formerly actlve Lask stays in tlle inactive waiting ~state until the 7 other task invokes the send count or send message ~echanism to 8 indicate that it has co~pleted the work requested. The send count 9 and send message mechanisms take inactive waiting TDE's off of the SRQ or SRC and e1lquetle them in priority sequence onto the TDQ. If 11 t~lere are no dis~atchable TDE's on the TDQ, there is no work to be 12 done, and the system is in an idle or wait state.

13 Brief Description of the Drawings 14 FIG's. l~l and 1-2, with FIG. l-l disposed above FIG. 1-2, taken together are a block diagram of a computer syste~ embodying 16 tlle in~ention;
17 FIG. 2 is a dlagram i]lustrating connective relationships l~ beLween user and I/0 tasks;
19 FIG. 3 is a diagram illus~-rating the format of queueing instructions and objects;
21 FIG's. 4-1 and 4-2, wi~h FIG. 4-2 disposed to the right 22 of F~G. 4-1, taken together are a diagram illustrating interrelationships 23 between a TDQ, SRQ, SRC, ;nstruction stream and base registers;
24 FIG. 5 ;s a diagram illustrating task state transitions;
FIG. 6 is a diagram illustrating control unit cycle 26 sequence interrelationships;
27 ~IG's. 7-1 and 7-29 with FIG. 7-l disposed above FIG. 7-2, 28 taken together are a hlock diagram similar to FIG's. 1-1 and 1-2, 11~33368 Sumlllary of ~he lnvencioll (conLinlle~) .

1 but illustrating the signa:l paths for a Tl CPU cycle;
2 FIG~s. 8-1 and 8-2, witll FIG. 8-1 disposed above FIG. 8-2, 3 taken together are a block diagram similar to FIG's. 7-1 and 7-2, 4 but illustrating the signal paths for a T2 CPV cycle;
FIG's. 9-1 and 9-2, with FIG. 9-1 disposed above FIG. 9-2, 6 taken together are a block diagram similar to FIG's. 7-1 and 7-2, 7 but illustrating the signal paths for a T3 CPU cycle;
8 FIG's. 10-1 and lQ-2, with FIG. 10-1 disposed above FIG. 10-2, 9 taken toget~er are a block diagram simllar to FIG's. 7-1 and 7-2, but illustrating the signal paths for an Al CPU cycle;
11 FIG's. 11-1 and 11-2, with FIG. 11-1 disposed above FIG. 11-2, 12 taken together are a block diagram similar to FlG's. 7-1 and 7-2, 13 but illustrating the signal patlls for an A2 CPU cycle;
14 FIG's. 12-1 and 12-2, with FIG. 12-1 disposed above FIG. 12-2, taken together are a block diagram similar to FIG's. 7-1 and 7-2, 16 but illustrating the signal paths for an Sl CPU cycle;
17 FIG's. 13-l and 1~-2, with FIG. 13-1 disposed above FIG. 13-2, 18 taken together are a block diagram similar to FIG's. 7-1 and 7-2, 19 but ïllustrating the signal paths for an S2 CPU cycle;
FIG's. 14-20, inclusive, are tirning diagra~s for 14, 15, 21 16~ 17, 18, 19 and 20 CPIJ cycles, respectively;
22 FIG. 21 is a f1OW diagram illustrating I-fetch cycles;
23 FIG. 22 is a flow diagram illustrating dispatch cycles;
24 PIG. 23 is a flow diagram illustrating I/0 event cycles;
FIG. 24 is a flow diagram illustrating send courlt, send 26 message and enqueue me~sage execution cycles;
27 FIG. 25 is a flow diagram illustrating insert cycles;
28 FIG. 26 is a flow diagram illustrating recei~e count, 1 lV3~8 Brief Description of the Drawings (continued) 1 receive message and dequeue message execution cycles;
2 FIG. 27 is a flow diagram illustrating remove cycles;
3 FIG. 28 is a diagram illustrating the initial state of a task 4 issuing a receive message instruction to a send receive queue;
FIG. 29 is a diagram illustrating the state of the task dispatching 6 queue and the send receive queue after the receive message instruction 7 of FIG. 28 was unsatisfied;
8 FIG. 30 is a diagram illustrating the state of the task 9 dispatching queue and the send receive queue after the active task in FIG. 29 issued a send message instruction to the same send 11 receive queue that was issued the receive message instruction;
12 FIG. 31 is a diagram illustrating the state of a task 13 issuing a receive count instruction to a send receive count queue;
].4 FIG. 32 is a diagram illustrating an I/O task as the active task issuing a send message instruction to a send receive 16 queue;
17 FIG. 33 is a diagram illustrating the state of the task 18 dispatching queue and send receive queue after the send message 19 instruction of FIG. 32 has been executed, and showing that the new 2~ active task issues a receive message instruction to the same send 21 receive queue which had been issued the send message instruction;
22 FIG. 34 is a diagram illustrating a new active task 23 issuing a receive message instruction to another send receive 24 queue;
FIG. 35 is a diagram illustrating the state of the task 26 dispatching queue, a send receive message queue and a send receive 27 count queue with a task dispatching element waiting thereon;
28 FIG. 36 is a diagram illustrating the I/0 event handler.

11~3;~3~
Brief Description of the Drawings (Continued) FIG. 37 is a diagram illustrating the sending of I/O completion status to the SRQ; and FIG. 38, shown on the page bearing FIG. 4-2, is a diagram il-lustrating the IOM task receiving the I/O completion status from the SRQ.
Detailed Description With reference to the drawings, and particularly to FIG. 1, the invention, by way of example, is illustrated as being incorporated into a stored program computer system which includes main storage 10. Main storage 10 is conventional, and is structured to be selectively address-able under control of storage control 15. Main storage 10 contains both instructions and data which are oriented on a byte basis. A
byte consists of eight binary bits, excluding a parity bit. The data and address paths to and from storage are on a word basis which in this example consists of four bytes. The organization of main stor-age 10 is not critical with respect to the present invention.
Main storage 10 is selectively addressable by storage control 15 which presents an address on bus 16. If a read operation is to take place, the data from the addressed location is available on bus ll and entered into data register 17 of storage control 15.
During a write operation, storage control 15 makes data available on bus 12, and this data is written into the addressed location in storage 10. The read and write operations are quite conventional.
Storage control 15 is connected to receive data and addresses from both central processing unit (CPU) 30 and I/O channel 500.

11~);~3~j~
Det;liletl Descriptioll (cc)ntlnllc 1 CPU 30 provides data to register 17 on bus 31, and addresses to 2 register 18 on bus 32. Register 17 is connected to provide data to 3 CPU 30 via bus 19. I/0 channel 500 provides data and addresses 4 to registers 17 and 18 over buses 501 and 502, respectively.
Data is provided ~o the channel from registel- 17 via bus 20. I/0 6 channel 500 connects to I¦0 devices 510 and 511 via I/0 adapter 505 7 and I/0 controller 506, respectively, The number and type of I/0 8 devices connected to the I/0 channel and the manner of connection 9 is noL pertinent to the present invention. The I/0 channel 500, however, must be able to communicate a need for I/0 event cycles.
11 Whenever I/~ event cycles are required, channel 500 provides a 12 signal on line 512, which is connected to set an I¦0 latcll 94 in 13 C~U 30.
14 The com~uter system incorporating the invention is initialized lly loading main storage 10 wiLh a task queue (TDQ), consisting of 16 one or more task dispatching elements (TDE's). The TDQ is a system 17 ohject meaning that it is a unit of data having particular significance;
18 i.e., control data. The TDQ is a chained list of objects containing 19 CPU status information of executable tasks where one task, and in this example, the top task is the active task, and all other tasks 21 in the list are inactive dispatchable tasks. The format of the 22 TDQ is sho~n in Fig. 3 as consisting of a TDE chain address. The 23 format oI the TDE's is also shown in Fig. 3. During the initial 24 operation of t~le system, the TDQ object is located by transferring an addres~ from TDQ SAR register 52 in SAR array registers 50 26 to address register 18. The TDQ SAR register 52 is selected 27 by an address from control unit 100 on bus 101. The SAR array 28 registers 50 include all of the specific registers containing llU;~68 Detailed Description (continued) 1 storage addresses necessary for pointing to objects and instructions 2 involved in the present invention, as well as the normal instruction 3 address register (IAR). IAR 51 contains the address of the next 4 instruction to be fetched and executed at the time the current instruction is being executed; i.e., it is the program location 6 counter. As will be seen later herein, each of the SAR array 7 registers 50 can be incremented or decremented under control of 8 control unit 100 without having the contents of the register pass 9 through ALU 45. In this particular instance, all address increment/
decrement operations, i.e., +1/-1, provide a four byte or one word 11 increment/decrement. The computer system incorporating the present 12 invention can have more than one TDQ, but if so, one of the TDQ's 13 will be a prime TDQ, and the other TDQ's will be secondary TDQ's.
14The TDE address contained in the TDQ object is passed from storage 10 into the data register 17 during a read storage 16cycle, and from register 17 via bus 19 into SA register 36. SA
17 register 36 is a main storage operand buffer. The contents of 18register 36 are passed to ALU 45 via A-bus assembler 39 and A-19bus 40. ALU 45 receives a signal from control unit 100, which 20causes ALU 45 to pass the left side input into 0-register 46.
21 ALU 45 is of the type well known in the art for performing two's 22 complement binary and subtract operations and AND, OR and Exclusive 23 OR (XOR) logical operations. Arithmetic and logical operations set 24 AZ latch 96 ~f all bits of the result are zeroes. During an arithmetic add operation, the setting of the AC latch 95 indicates that there 26 was a carry out of the high order bit position. On a subtract 27 operation, the setting of AC latch 95 indicates that there was no 28 borrow into the high order bit position. Pass left and pass right llU;~68 Detailed Description (continued) 1 operations are used for register-to-register transfers, and occur 2 without any setting of the ALU condition latches AC 95 and AZ 96.
3 The 0 register 46 functions as the ALU 45 output register for 4 latching the ALU result prior to gating the result to C bus 47.
The output of 0 register 46 is connected by C-bus 47 to D-bus 6 assembler 48. The D-bus assembler 48 feeds SAR array 50 via D-7 bus 49. In this instance, control unit 100 provides a signal to D-8 bus assembler 48 to cause it to select bus 47 as a source, and provides 9 an address via bus 101 for addressing CTDE SAR register 53, whereby the current TDE address is entered into register 53.
ll The operation just described is accomplished during a CPU
12 T2 CPU cycle, which is illustrated in Fig's. 8 and 15, and will be 13 described in detail later herein. The function of a T2 CPU cycle 14 is to transfer the contents of any A-bus 40 source register to any C-bus 47 destination register.
16 Register 53, which contains the current TDE address (CTDE@), 17 is used to hold this address during the entire duration of the 18 associated task. Thus, it is necessary to also load a working regis-19 ter with the current TDE address, which can be incremented or decremented so as to load the CPU registers with address and status information of 21 that TDE. It should be understood that when the current TDE address 22 is transferred from register 53 into this work register, which will 23 be described shortly, the current TDE address also remains in 2~ register 53. It should also be understood that register 53 contains the address of the TDE that is active at the start of the current 26 instruction. If dispatch latch (D latch) 93 is set during execution 27 of the current instruction, then, at the start of the execution of 28 the next instruction, the contents of register 53 are compared with 3;~68 Detailed Description ~continued) 1 the address of the top TDE on the TDQ, to determine if a task 2 switch is required. As will be seen later herein, a task switch 3 may or may not occur, depending upon whether or not a different TDE
4 becomes the top TDE on the TDQ. Hence, if the address of the current TDE does not compare with the address of the top TDE, a 6 task switch is required. The top TDE on the TDQ, of course, is 7 pointed to by the TDQ object, as previously mentioned. Therefore, 8 another T2 CPU cycle will be taken to transfer the current TDE
9 address from register 53 into the OP l SAR register 54. The TDE
address in OP 1 SAR register 54 is then incremented by two words, 11 so as to point to the instruction address field (IA) contained in 12 the TDE.
13 The incrementing of the current TDE address by two words 14 is accomplished by an A2 CPU cycle, which will be described in detail later herein. It is sufficient to note at this time, that during 16 an A2 CPU cycle the SAR array 50 is addressed via control unit 100, 17 whereby the contents of OP 1 SAR register 54 are placed on bus 32, 18 which, in addition to feeding address register 18, also~feeds A-bus 19 as$embler 39. Control unit 100 provides a selection signal to A-bus assembler 39 to cause the same to select bus 32 as the source.
21 Thus, the current TDE address is presented to the left side of 22 ALU 45 via A-bus 40~ Control unit 100 also causes emit encoder 60 23 to present a value of two over bus 61 to B-bus assembler 62, whereby 24 the value two is presented to the right side of ALU 45 via B-bus 63. ALU 45 then performs an add operation in response to a 26 control signal from control unit 100, and the result is entered 27 into 0-register 46. The address then passes from 0-register 46 via 28 bus 47, D-bus assembler 48 and D-bus 49 into OP 1 SAR 54.

..
.~

llV3~68 Detailed Description (continued) 1The incremented address now residing in OP 1 SAR register 54 2 is then transferred into address register 18 as part of an Sl 3 cycle, which will be described in detail later herein. The address 4in register 18 is passed by storage control 15 over bus 16 to address main storage 10. The word appearing on bus 11, in response 6 to the read operation of main storage 10, is entered into register 17 7 and placed on bus 19. The word on bus 19 is then entered into SA
8 register 36. During this Sl cycle, the address taken from OP 1 SAR
9 register 54 is also passed to incrementer 59, which increments the address by one and passes the address to D-bus assembler 48, 11 whereby it is returned into register 54 via the D-bus 49, so as to 12 point to the next word of the TDE, which, in this instance, con-13 tains the instruction length code (IL) field and the condition cade 14 (CC) field of the first instruction associated with the task.
15The contents of SA register 36 contains the address of 16 the first instruction associated with the task. This address is 17 entered into IAR SAR 51 by means of a T2 CPU cycle. Before retrieving 18 the first instruction associated with the task, it is necessary to 19 fetch the remaining words of the TDE. Thus, the incremented address 20in OP 1 SAR~register 54 is entered into address register 18, and 21 the next word of the TDE is read from main storage 10. The instruction 22 length count (IL) and condition code (CC) contained in this next 23 word are entered into IL register 38 and CC register 65, respectively.
24 During this Sl CPU cycle, the address in register 54 is again incremented by incrementer 59 and returned into register 54. The 26 address from register 54 is then again transferred into address 27 register 18, whereby storage 10 is again addressed and ~he word at 28 the addressed location is transferred from storage over bus 11 into X

Detailed Description (continued) 1 register 17. The contents of register 17 are then entered into SA
2 register 36. During this Sl cycle, the address in register 54 is 3 again incremented and returned into register 54, as previously 4 described. The contents of the SA register 36 will be transferred into a work register in the LSR array of registers 70. The work 6 register selected depends upon an address provided by P register 90.
7 P register 90 is a counting register used for indirect addressing 8 of LSR array registers 70, and can be incremented or decremented by g one without the contents thereof passing through ALU 45. In this instance, P register 90 is loaded with an address by means of a Tl 11 CPU cycle, which will be described in greater detail later herein.
12 During a Tl CPU c~cle, control unit 100 provides a signal to emit 13 encoder 60, which emits a value to B-bus assembler 62. This value 14 will be zero, so as to address base register 0 of LSR array 70.
Hence, the value of zero passed to B-bus assembler 62 passes via B-16 bus 63 into ALU 45 and therefrom into register 46. The value zero 17 then leaves register 46 via bus 47 into P register 90, where it is 18 available to address LSR array 70 via bus 91. With the address in ~9 P register 90, a T2 CPU cycle is taken to transfer the contents of 2Q SA register 36 into the addressed base register 0 of LSR array 70.
21 The operation just described repeats until all fields of the active 22 TDE have been retrieved from storage 10. The remaining fields in 23 the TDE are fields which are loaded into base registers 1-15, 24 inclusive, of LSR array 70.
The next operation is to fetch the first instruction of 26 the active task, now that all the fields of the TDE have been 27 fetched and loaded into the appropriate registers. Although the 28 invention does not require it, in this particular example, an 11(~3~f~8 Detailed Description (continued) 1 instruction is prefetched into instruction register 35, and then an 2 instruction fetch cycle follows. The present invention is not 3 dependent upon having instructions prefetched. Prefetching of 4 instructions is well known in the art, and is used to enhance performance of the computer system. The prefetch operation involves 6 two Sl cycl~s whereby a first Sl cycle is taken to load the high 7 half of the IS register 35 via S0 bus 19. The second Sl cycle 8 loads the low half of IS register 35 via bus l9. Instruction 9 register 35 is two words wide and buffers the next instruc~ion of the instruction stream being executed. It should be noted at this 11 time that instructions have different lengths. The computer system 12 of FIG. 1 can process instructions having a length of one-half 13 word, a full word or a word-and-one-half; i.e., instructions having 14 a length of two bytes, four bytes or six bytes.
lS The I-fetch cycle for these instructions is shown in 16 FIG. 21; however, it should be noted that the I-fetch for a two-17 byte instruction is not shown, because none of the instructions 18 pertinent to the present invention are two-byte instructions. Each 19 instruction, of course, has an OP code and, in this instance, the OP code also includes bits indicating the length of the instruction.
21 It should be noted that during the I-fetch operation, control 22 unit 100 first samples the status of a dispatch cycle latch 93 and 23 an I0 latch 94. At the start of the initial task, both of these 24 latches will be in the reset state. The OP code is decoded by decoder 41 and the instruction length is decoded by decoder 42.
26 The signals resulting from decoding the OP code are passed to 27 control unit 100, and the signal indicating the instruction length 28 i5 passed from instruction length decoder 42 to set a latch 92 if 11~J;~;368 Detailed Description (continued) 1 the instruction is six bytes, and reset latch 92 if the instruction is 2 less than six bytes. The control unit 100 samples the latch 92 and 3 a Tl cycle is taken, whereby control unit 100 provides a signal to 4 emit encoder 60, which then emits a value indicating the instruction length. This emitted value will then be entered into IL register 38 6 during the Tl cycle.
7 The I-fetch cycle continues where the contents of instruction 8 length (IL) register 38 are added to the current contents of IAR
9 SAR 51 by means of an Al CPV cycle, and the result is returned to IAR SAR 51. It should be noted that a byte add operation is performed 11 for changing the value in IAR SAR 51. Thus, by adding an IL register 12 value of four or six to the contents of IAR SAR 51, the storage 13 word address is increased by one or one-and-one-half words, respec-14 tively. This provides the IAR SAR 51 with an address to point 15 to the next instruction of the task. The IL register 38 holds the 16 length of the instruction that is currently being executed. The 17 length is held as an unsigned binary number. A T2 CPU cycle is 18 taken where the instruction I-field is put into P register 90 for 19 later use. This is followed by another T2 CPU cycle, where the instruction OP 1 field is placed into the OP 1 SAR 54. Then, a Sl 21 cycle is taken for reading data from main storage 10 and transferring 22 it onto bus 19, and from there, into SA register 36, whereby the 23 first operand of the instruction is fetched. Latch 92 is then tested, 24 and if the instruction is a six-byte instruction, a T2 cycle is taken for loading OP 2 SAR 55 with the contents of the OP 2 field 26 in the instruction. This T2 cycle is then followed by a Sl cycle, 27 where data is read from main storage 10 and transferred onto bus 19 28 to be loaded into SB register 37. SB register 37, like SA register 36, Detailed Description (contined) 1 is a main storage operand buffer. Operands 1 and 2 have now been 2 fetched from main storage 10 and placed into registers 36 and 37, 3 respectively. If the instruction had not been a six-byte instruction, 4 there is no operand 2 to be fetched from main storage 10.
Control transfers to execute cycles, the type of execute 6 cycles being indicated by the decoding of the OP code by the OP code 7 decoder 41. The execute cycles for s_nd message, se~d count, enqueue 8 message, receive message, receive count and dequeue message instruc-9 tions will be described in detail later herein. If the instruction were other than one of the instructions for the execute cycles just 11 mentioned, i.e., conventional instructions such as load, store, 12 branch, etc., the execute cycles for these other instructions would 13 then follow. Since these other instructions are very conventional 14 instructions, their execute cycles are not shown.
In order to achieve a more detailed understanding of the 16 I-fetch cycles, the Tl, T2, Al and Sl cycles will be described in 17 detail. The control signals and those elements of the computer 18 system which are involved during a Tl CPU cycle are shown in detail 19 in FIG. 7. The timing diagram for a Tl CPU cycle is shown in FIG. 14. The function of a Tl CPU cycle is to load an immediate 21 operand into a register of the CPU. As seen in FIG. 7, control 22 unit 100 places signals on bus 102, which activates emit encoder 60 23 to emit a binary value. Emit encoder 60, which is a conventional 24 encoder, in turn places the binary value on bus 61, which feeds B-bus assembler 62. In order for B-bus assembler to select emit 26 ercoder 60 as a source, control unit 100 provides signals on 27 bus 103. The output of the B-bus assembler 62 is applied over 28 bus 63 to ALU 45. ALU 45 is controlled by a signal from control R~976-014 17 llV;~v~ `

Detailed Desciption (continued) 1 unit 100 on line 104 to pass the input on bus 63, i.e., the righthand 2 input, to O register 46, which is loaded under control of a signal 3 from control unit 100 on line 105.
4 C-bus 47 presents the output of O register 46 to destination registers, and the destination register selected by control unit 100 6 is loaded when control unit 100 provides a load pulse, such as on 7 line 106, which is representative of the load line to the selected 8 destination register. Actually, there is a load line to each 9 destination register. The destination registers are, of course, any register fed by the C-bus 47, and include IS register 35, SA
11 register 36, SB register 37, IL register 38, SAR array registers 50, 12 condition code register 65, L register 66, LSR array registers 70 13 and P register 90. Only single load lines are connected to SAR
14 array registers 50 and LSR array registers 70.
The units of the computer system involved in the T2 CPU
16 cycle are shown in FIG. 8, and the timing diagram for a T2 CPU
17 cycle is shown in FIG. 15. The function of a T2 CPU cycle is to 18 transfer the contents of any data source register feeding A-bus 19 assembler 39 to any destination register connected to receive data from C-bus 47. A-bus assembler 39 receives inputs from IS register 35, 21 SA register 36, L register 66, P register 90, SAR array registers 50 22 and LSR array registers 70. Control unit 100 can select a SAR
23 array register 50, by placing an address on bus 101. The data from 24 the selected SAR array register is then read when control unit 100 provides a read signal on line 114. The data read from the selected 26 register then passes over bus 32 to the A-bus assembler 39.
27 The LSR array registers 70 are always selected by an 28 address in P register 90. Data, however, is only read from the Detailed Description (continued) 1 selected register when control unit 100 provides a read signal on 2 line 107. Data from the selected register transfers over bus 69 to 3 A-bus assembler 39. All other registers feeding A-bus assembler 39 4 do not require a read pulse, because their outputs are present without one.
6 The source into A-bus assembler 39 is selected when 7 control unit 100 provides a signal on encoded bus 108. It should 8 be noted that control unit 100 can select one of two sources with a 9 single line. If the source to be selected is from more than two sources, then, depending upon the desired implementation, control 11 unit 100 could send signals over an encoded bus or over a separate 12 line to each source to make selections. The selection of data 13 destinations can also be done in the same manner unless specified 14 differently. The data passed by the A-bus assembler 39 enters the ALU 45 via bus 40. ALU 45 is controlled by a signal from control 16 unit 100 over line 109 to pass the data on A-bus 40, i.e., the left-17 hand input, to O register 46. The data passed by ALU 45 is loaded 18 into O register 46 under control of a signal from control unit 100 19 on line 105. The data residing in O register 46 is then passed to the destination registers.
21 One of the destination registers will be selected by a 22 signal from control unit 100. If one of the SAR array registers 50 23 is the destination register, control unit 100 provides a signal on 24 line 110 to D-bus assembler 48 which then selects C-bus 47 as a source. Control unit 100 will also provide an address on bus 101 26 for selecting one of the SAR array registers 50. The data would be 27 entered into the selected SAR register from D-bus assembler 48 via 28 bus 49 under control of a load pulse which control ~mit 100 would . .. _ llV;~68 Detailed Description (continued) 1 provide on line 111.
2 If one of the LSR array registers 70 were selected as the 3 destination register, control unit 100 would provide a load pulse 4 on line 112. The register selected, of course, would be the one addressed by the contents of P register 90. If the destination 6 register is other than a SAR array register 50 or a LSR array 7 register 70, control unit lO0 provides a load pulse on line 106 8 which is a representative load line.
9 The Al CPU cycle and the timing therefor are shown in FIG's. 10 and 17, respectively. The function of the Al CPU cycle 11 is to transfer the contents of two selected registers to the ALU 45, 12 perform an ALU operation and transfer the result either to the left 13 source register or drop the result. Also, during the Al CPU cycle, 14 the condition latches AC 95 and AZ 96 are appropriately put in ]-5 states determined by the result of the ALU operation. In FIG. 10, 16 control unit 100 will provide an address on bus 101 and a read 17 signal on line 114 if one of the SAR array registers 50 is to be 18 the source register for the lefthand input into ALU 45. If the 19 input into the lefthand side of ALU 45 is to come from one of the LSR array registers 70, control unit 100 provides a read signal on 21 line 107. The source for the left side input into ALU 45 is selected 22 by control unit 100 as it provides a selection signal to A-bus 23 assembler 39 on line 108.
24 The right side input is passed to the ALU 45 by B-bus assembler 62. It will be recalled that B-bus assembler 62 can 2~ select the SB register 37, the IL register 38, the emit encoder 60 27 or the condition code register 65. The selection is made by signals 28 which control unit 100 provides on encoded bus 103. The function 111);~68 Detatled Description (continued~

1 performed by ALU 45 is determined by the signal provided by control 2 unit 100 on line 104. For example, the signal on line 104 might 3 add the contents of the SA register 36 with the contents of SB
4 register 37 and return the result to register 36 via the 0 register 46 and C-bus 47. Another example would be for the AL~ to subtract the 6 contents of the SB register 37 from the contents of the SA register 36.
7 The result can be dropped or passed to the 0 register 46. Control 8 unit 100 providcs a load signal on line 105 to load the result into 9 0 register 46. Ihe result ls then available to C-~us 47 for transfer to a destination register. If the destination of tlle result is one 11 oE the SAR array registers 50, control unit 100 provides a signal 12 on line 110 to D-bus asse~bler 48 Eor causing the same to select C-13 bus 47 as a source, and provides a signal on line 111 for loading 14 the SAR array re~ister 50, se]ected by the address on bus 101 with the result passed by ~-bua assembler 48 via D-bus 49. If the 16 resul~ is to be placed in one of the L5R array registers 70, control 17 unit 100 provides a signal on line 112 for loading the selected 18 register where Lhe selection is made by the address in P-register 90.
19 If t~e destination register is other than those mentioned, control unit 100 provides a signa] on line 106 which is a represell~ative 21 load line. Condition latches 95 and 96 are set or reset by signals 22 from ALU 45 over lines 43 and 44, respectively.
23 During a Sl CPU cycle, data is read from main storage 10 24 and loaded into a register connected to S0-bus 19. The source of the storage address is in one of the S~R array registers 50, and 26 this address can be optionally incre~en~ed or decremented and 27 returned into ~he source SAR array register. Those units of the 28 computer system involved in a Sl CPU cycle are shown in FIG. 12, llV;~
Detailed Description (continued) 1 and the timing diagram for the Sl CPU cycle, is shown in FIG. 19.
2 Control unit 100 provides an address on bus 101 for 3 addressing SAR array 50. The contents of the selected SAR array 4 register are read by a signal which control unit 100 provides on

5 line 114. The contents from the selected SAR array register 50 are

6 placed on bus 32 and entered into register 18, and are also applied

7 to incrementer 59. The output of incrementer 59 is passed to D-bus

8 assembler 48, and if the incremented or decremented address is to

9 be returned to the selected SAR array register, control unit lO0 provides a signal on line 110 to D-bus assembler 48. The incremented 11 or decremented address would then be entered into the selected SAR
12 array register 50 when control unit 100 provides a load signal on 13 line 111~ Control unit 100 then provides a storage read pulse on 14 line 115 to storage control 15. Data is read from storage 10 at the location addressed by the address in register 18. This data 16 passes from storage via bus 11 to storage control 15 and into data 17 register 17. Whether or not register 17 is actually a register is 18 a matter of choice, and depends upon the particular type of storage 19 used; i.e., in some storage units, the data is latched at the output of storage. The data then passes from data register 17 onto 21 S0 bus 19. The data on S0 bus 19 then enters an appropriate destination 22 register, as determined by a load signal on representative load 23 line 106 furnished by control unit 100.
24 The operation of the invention described up to this point is diagramatically represented in FI&. 4; i.e., the TDQ object was 26 retrieved fro~ storage 10 to locate the active TDE on the TDQ.
27 Certain fields of the active TDE were then retrieved from sLorage.
28 Then an instruction fetch was made, and the fetched instruction was ''~'"

llV;~
Detailed Description (continued~

1 executed. The task would then continue until some instruction 2 associated with the task caused a task switch, or a higher priority 3 task was enqueued onto the TDQ. This would also cause a task 4 switch.
A receive message instruction (RECM)can cause the active 6 task to be dequeued from the TDQ and enqueued onto a task dispatching 7 element wait list of a send receive queue (SRQ). The function of a 8 receive message instruction, the format of which is shown in FIG. 3, 9 is to obtain a message (SRM) from a SRQ. If there isn't a SRM on the SRQ, then the receive message instruction is not satisfied, and 11 the active task is taken off the TDQ and goes into a wait state as 12 an inactive waiting TDE on a SRQ. The waiting task then waits on 13 the SRQ until a send operation enqueues a SRM on the SRQ and moves 14 the inactive waiting TDE onto the TDQ. In FIG. 4, the receive message instruction is prefetched in the same manner as any 16 other instruction. The I-fetch cycles for the receive message 17 instruction are a six-byte instruction fetch. Upon completion 18 of the I-fetch cycles, receive message (RECM) execution cycles are 19 taken. The receive message execution cycles are shown in FIG. 26.
The receive message instruction (RECM), as seen in FIG. 3~
21 has an OP code indicating that it is a receive message instruction.
22 The OP code field is followed by an I field and, in this instance, the 23 I field contains the address of an LSR array register 70. This 24 addressed LSR array register 70 will be loaded during the execution of the receive message (RECM) instruction with the address of the 26 dequeued message from a send receive queue (SRQ) which, in turn, is 27 addressed by the OP 1 address field in the receive message instruc-28 tion. The OP 2 address field in the receive message instruction 6~
Detailed Description (continued) 1 contains an address for addressing main storage 10 at a location 2 containing a key data object which will be used for comparison with 3 key fields of send receive messages (SRM) on a SRQ to identify the 4 SRM to be dequeued from the SRQ. The SRM's are chained on the SRQ
in key sequence. The key data object retrieved from storage is 6 compared with the key field of the first SRM on the SRQ, and if 7 the keys are equal, that SRM is dequeued from the SRQ. If the 8 comparison is not equal, that SRM is dequeued from the SRQ. If the 9 comparison is not equal, the key da~a object retrieved from storage is compared with the key field of the next SRM, and so forth, until 11 an equal comparison is found.
12 Assuming that there is an equal comparison, the address 13 of the particular SRM containing the key field which compares equal 14 is placed in the LSR array register 70, addressed by the R3 field in the received message instruction, and the SRM is removed from 16 the chain of SRM's on the SRQ. If the key data object retrieved 17 from storage does not compare with the key field of any SRM's on 18 the SRQ, the receive message instruction is considered unsatisfied.
19 Because the IAR SAR 51 is pointing to the next instruction to be fetched from main storage 10 and if the receive message 21 instruction was not satisfied, it is necessary to decrement the 22 IAR so that it points to the address of the unsatisfied receive 23 message instruction. This operation will be described in detail 24 during the description of the remove cycles. It is necessary to save the address for this unsatisfied receive message instruction, 26 because the active task which contained this instruction in its 27 instruction stream will be dequeued from the TDQ and enqueued onto 28 the wait list of the SRQ addressed by the OP 1 field of the unsatisfied 29 receive message instruction. The dequeueing of the active TDE from Detailed Description (continued) l the TDQ and the enqueueing of this TDE onto the SRQ will be described 2 in detail during the description of the remove cycles. The dequeueing 3 of the active TDE causes a task switch to take place and the new 4 highest priority TDE on the TDQ, if any, will then become the active task. This is illustrated by example in FIG. 28.
6 During the execution of a receive message instruction, 7 control unit 100 resets send latch 87, sets receive latch 88 and 8 resets ST phase latch 97 and RT phase latch 98. Control unit 100 9 accomplishes this either just prior to, or simultaneously with, a T2 CPU cycle, which is taken to transfer the contents of the OP l ll SAR 54 into the PCH SAR 56. PCH SAR 56 normally contains the 12 address of the last or previous queue element. The T2 cycle is 13 then followed by remove cycles. Remove cycles are shown in FIG. 27.
14 In FIG. 28, it is seen that the TDQ object has a TDE
address which points to the highest priority TDE on the TDQ. This 16 happens to be a TDE having a priority of zero. The TDE with the 17 zero priority is chained to a TDE having a priority of one and this 18 TDE chains to the next highest priority TDE, and so forth, with TDE
19 having a priority of N being the last TDE on the TDQ. The TDE
having the zero priority is the active task and its IA field points 21 to a receive message instruction in storage. The OP 1 field of the 22 receive message instruction points to SRQ 1 which has SRM 1 chained 23 to it. SRM 3 ischanged to the SRM 1. There are no TDE's chained 24 to the SRQ 1. This indicates that there are no inactive waiting TDE's on the SRQ l. The OP 2 field of the receive message instruction 26 points to a key data object in main storage lO having a value of two.
27 None of the SRM's on the SRQ l contain a key field having a value of 28 two and, therefore, the receive message instruction is unsatisfied. It li~J ~b~
Detailed Description (continued) 1 should also be noted that the IA field of TDE 1 on the TDQ points 2 to a send message instruction. The I field of this send message 3 instruction points to a LSR array register 70 containing a main 4 storage address of a storage word SRM 2. Because the receive message instruction is not satisfied, the active TDE 0 will be 6 dequeued from the TDQ and enqueued onto the wait list of the 7 SRQ 1., as illustrated in FIG. 29. The TDE 1 will then become the 8 active TDE and the execution of the send message instruction will 9 cause SRM 2 to be enqueued in priority sequence onto SRQ 1, as illustrated in FIG. 30.
11 The remove cycles involved during the receive message 12 instruction start with a T2 CPU cycle, as illustrated in FIG. 27.
13 Prior to the T2 CPU cycle, it should be noted that SA register 36 14 had been loaded with the first field of the SRQ. This took place during the I-fetch cycle for the receive message instruction. Also 16 during the I-fetch cycle for this instruction, register 37 was 17 loaded wi~h the key data object from main storage 10, which will be 18 used for locating a particular SRM, if any, on the SRQ. The CCH
19 SAR 56 was loaded during the receive message execution cycle with the address of the first field of the SRQ 1 just prior to the 21 remove cycle. During the T2 CPU cycle, the CCH SAR 57 is loaded 22 with the contents of the SA register 36. The CCH SAR 57 contains 23 the address of the current queue element being processed. This T2 24 CPU cycle is followed by an A2 CPU cycle, where the contents of CCH
SAR 57 are examined to determine if they are zero. This is done to 26 determine if there are any SRM's on the SRQ.
27 In the particular example of FIG. 28, there are two SRM's 28 on the SRQ and, therefore, the CCH address is not zero, and thus ~0976-014 26 llV~
Detailed Description (continued) 1 the AZ latch 96 will not be set by ALU 45. A Sl CPU cycle is then 2 taken to fetch the key field of SRM 1 and to increment the CCH
3 address. The key field retrieved from storage 10 is then placed 4 into SA register 36. An Al cycle is then taken to compare the key data object with the key field to determine if the key field equals 6 the key object. This is accomplished by subtracting the contents 7 of the SB register 37 from the SA register 36. It should also be 8 noted that if the key data object were greater than the key field, 9 that would be an indication that no further comparisons would be necessary because the key field of any lower priority SRM could 11 never be equal to the key object. If the key field equals the key 12 object, the AZ latch 96 is set. A Sl cycle is then taken to fetch the 13 chained address of the SRM 1 from main storage 10 and place the 14 same in the SA register 36. During this Sl cycle, the AZ and ST
latches 96 and 97 are decoded to determine the next cycle of opera-16 tion. Because the AZ latch 96, in the example of FIG. 28, would be 17 in the reset state because the key field of SRM 1 didn't compare 18 with the key data object and the ST latch 97 is reset, a T2 CPU
19 cycle is taken to transfer the contents of CCH SAR 57 to PCH SAR 56.
This is to put the address of SRM 1 into the PCH SAR. The PCH
21 SAR is then incremented by one during an A2 CPU cycle. The value 22 of the address for the SRM chain address field has now been saved 23 for subsequent use if the next SRM on the chain of SRM's is to 24 be removed.
Because the key object did not compare with the kev field 26 of SRM 1, the operation loops back to the beginning of the remove 27 cycles and the key field of the next SRM on the SRQ 1 will be 28 compared with the key data object. This operation continues until ~r .~

Detailed Description (continued) 1 the key field of the last SRM on the SRQ has been compared with the 2 key data object. In this instance, when the compare operation has 3 been completed with respect to the key field of SRM 3, the main 4 search loop is executed again, and because the SRM chain address field of SRM 3 is zero, the AZ latch 96 will be set and the operation 6 switches, whereby the S and R latches 87 and 88 are decoded by 7 control unit 100. It should be noted that when the AZ latch 96 was 8 set, that was an indication that the receive message instruction 9 was not satisfied. Receive latch 88 is still set; hence, the next operation is that the control unit 100 sets D latch 93 to invoke 11 dispatch cycles at the beginning of the next I-fetch cycle. The 12 S latch 87 is then tested, and because it is off, the RT latch 98 is 13 set by control unit 100. A T2 CPU cycle is then taken to load the 14 contents of the TDQ SAR 52 into the PCH SAR 56. A Sl CPU cycle is then taken to load SA register 36 with a PCH address from main stor-16 age 10, where the PCH address is the address of the TDQ. A T2 CPU
17 cycle is then taken to transfer the contents of the current TDE SAR 53 18 into the OP 2 SAR 55. A Sl cycle is then taken to retrieve the 19 priority field of TDE 0 from main storage 10 and enter the same into SB register 37. This is done so that the search loop previously 21 described can be used for dequeueing the TDE from the TDQ.
22 The main remove cycle's search loop is executed again 23 and, because the priority field of the TDE 0 is being compared 24 with itself, the contents of the SA register will equal the contents of the SB register, and hence, the AZ iatch 96 will be set. The ST
26 latch 97, however, will still be in the reset state. Hence, the 27 next operation will be a S2 CPU cycle rather than a T2 CPU cycle.
28 During the S2 CPU cycle, the value in the SA register 36 is loaded llV;~b~
Detailed Description (continued) 1 into main storage 10 at a location containing the TDE address in 2 the TDQ field. This breaks the previous chain whereby the TDE
3 address in the TDQ field now points to TDE 1 rather than TDE O. It 4 should be noted that, although the TDE 0 is removed from the TDQ, the movement is not a physical movement of the TDE, but only a 6 change in the TDE address in the TDQ field.
7 The SR and RT latches 87, 88 and 98 are then decoded by 8 control unit 100. In this instance, the S latch 87 is reset, and 9 the R and RT latches 88 and 98 are set. Thus, the next operation is to load the contents of the CCH SAR 57 into the OP 2 SAR 55 11 during a T2 CPU cycle. The control unit 100 is setting up the 12 proper conditions for switching the operation to insert cycles. A Sl 13 CPU cycle is then taken to load the SB register 37 with the priority 14 field of TDE 0 from main storage 10. Also during this Sl CPU cycle, the address in the OP 2 SAR 55 is incremented and returned to 16 register 55. A test is then made to determine the type of operation, 17 and this is done by testing the S latch 87. Because the S latch 87 18 is not set, the next cycle is an A2 CPU cycle, where the contents 19 of the OP 1 SAR register 54 are incremented and placed back into the OP l SAR 54, so that the contents of OP 1 SAR 54 point to the 21 TDE address field of SRQ 1. The contents of OP 1 SAR 54 are 22 then transferred to PCH SAR 56 during a T2 CPU cycle. A Sl CPU
23 cycle is then taken to load SA register 36 with the PCH address, 24 i.e., in the example of FIG. 28, with the TDE address fie~d of SRQ 1. The operation then proceeds with insert cycles, which are 26 shown in detail in FIG. 25. At the start of an insert cycle, for 27 the example illustrated in FIG. 28, the SA register 36 contains the 28 TDE address field o SRQ 1, the SB register 37 contains the priority llV;~;36~
Detailed Description (continued) 1 field of TDE 0, the PCH SAR 56 contains the address of the TDE
2 address field of SRQ 1 and the OP 2 SAR 55 contains the chain 3 address field of TDE 0.
4The first cycle of the insert cycles is a T2 CPU cycle which is taken to load the CCH SAR 57 with the contents of SA
6 register 36. An A2 CPU cycle is then taken to determine if the 7 value of CCH SAR 57 is zero. In the particular example of FIG 28, 8 the contents of CCH SAR 57 will be zero, because the TDE address 9 field of SRQ 1 is zero. The zero value indicates that there were no TDE's waiting in the inactive state on SRQ 1. Because the value 11of CCH SAR 57 is zero, the ALU 45 sets the AZ latch 96. This latch 12 is tested and, because it is set, the next operation is a T2 CPU
13 cycle to load the SA register 36 with the contents of the CCH
14 SAR 57. This cycle is followed by a S2 CPU cycle, where the contents of the SA register 36 are stored in main storage 10 at the address 16 contained in the OP 2 SAR 55. Hence, the TDE address field of 17 SRQ 1 (all zeroes) now resides in the chain address field of TDE 0.
18 The OP 2 address in SAR 55 is decremented during the S2 CPU cycle.
19 It is sufficient to note, at this time, that the S2 CPU cycle is illustrated in detail in FIG. 13, and will be described later herein.
21A T2 CPU cycle is then taken to load the SA register 36 22with the contents of the OP 2 SAR 55. The contents of OP 2 SAR 55, 23 as noted, were decremented during the previous S2 CPU cycle.
24 Hence, the SA register 36 is loaded with the address of TDE O.
This address in SA register 36 is then stored in main storage 10 26 during a S2 cycle at an address specified by PCH SAR 56, whereby 27 the TDE 0 is enqueued to SRQ 1. At this time, it should be noted 28 tha~ the states of the TDQ and SRQ 1 are as shown in FIG. 29. In Detailed Description (continued) FIG. 29, it should also be noted that the chain of SRM's on SRQ 1 remains unchanged.
The control unit 100 then decodes the S, ST and RT latches 87, 97 and 98, and finds that the S latch 87 is not set, and that the RT latch 98 is set. Because the S latch 87 is not set, the state of the ST latch 97 is not pertinent at this time. Al and Tl CPU
cycles are then taken in succession so as to reset the IAR SAR 51 so that it will point to the unsatisfied receive message instruc-tion and the IL register 38 is set to zero. The operation then switches to an I-fetch cycle of the active task, which is still TDE
0 because a task switch has not as yet taken place.
With reference again to FIG. 21, the I-fetch cycle is entered, and the D and IO latches 93 and 94 are decoded by control unit 100 and it is found that the D latch 93 is set and the IO ]atch 94 is reset; hence, dispatch cycles are entered. The dispatch cycles are shown in detail in FIG. 22. Upon entering the dispatch cycles, the D latch 93 is reset by control unit 100. A SI cycle is then executed to load SA register 36 with the TDE chain address field of the TDQ. An A2 CPU cycle is then taken to determine if the TDE
chain address field in SA register 36 is zero. Because in the particular example of FIGs. 28 and 29, there are additional TDE's on the TDQ, the contents of SA register 36 will not be zero. Hence, the AZ latch 96 will not be set. If there were no more TDE's on the TDQ, the CPU 30 would enter a wait state.
With the AZ latch 96 in the reset state, a Sl CPU cycle is taken to load the SB register 37 with the TDQ chain address field (which points to the top TDE on the TDQ) from main storage 10.
The current TDE address in CTDE@ SAR 53 is then compared with the contents of the SB register 37 during an Al cycle. In the parti-cular example, the current TDE address is for TDE 0, whereas the TDE

~, ~,~

Detailed Description (continued) 1103368 1 address in the TDQ data object is pointing to TDE 1. Hence, as 2 a result of the ALU operation, the AZ latch 96 will not be set.
3 If it had been set, a task switch would not be required, and 4 I-fetch cycles would follow. A T2 CPU cycle, however, follows where the OP 1 SAR 54 is loaded with the contents of the current 6 TDE SAR 53. The contents of the OP 1 SAR 54 are then incremented 7 by two, so as to point to the IA field of TDE 0. This takes 8 place during an A2 CPU cycle. The function to be performed is 9 to store the status fields of the current TDE. After this is accomplished, as will be described shortly, the statùs fields for 11 the new active TDE, i.e., TDE 1, will be loaded into the appropriate 12 registers.
13 A T2 CPU cycle is taken to load the SA register 36 with 14 the contents of IAR SAR 51. The IAR SAR 51 is then saved in main storage 10 during a S2 CPU cycle by loading the contents of SA
16 register 36 into main storage 10 at the OP 1 address in the OP 1 17 SAR 54, and the OP 1 address is incremented. A T3 cycle is then 18 taken to load the SA register 36 with the contents of IL register 38 19 and condition code register 65. This is followed by a S2 storage cycle to load the contents of the SA register 36 into main storage 10 21 at the address specified by the OP 1 SAR 54.
22 The OP 1 address in SAR 54 is again incremented and 23 returned tv OP 1 SAR 54. A Tl cycle is then taken to put a value 24 of fifteen into the L register 66. L register 66 is a counting register used for controling CPU loop iterations. L register 66 26 can be decremented by one and zero detect circuit 67 examines 27 register 66 for an all zero condition. This Tl cycle is followed 28 by another Tl cycle, where the P register 90 is set to zero. A T2 1`1(~3~
Detailed Description (continued) 1 cycle is then taken to load the SA register 36 with the contents of 2 the local storage array register 70, as addressed by the contents 3 of P register 90. The contents of the SA register 36 are then 4 transferred to main storage 10 at the address specified by the OP 1 SAR 54, and the OP 1 SAR 54 is incremented, all of this taking 6 place during a S2 CPU cycle. A LZ latch 89, which is set when the 7 value of L register 66 is zero, as determined by zero detect circuit 67, 8 is then tested. In this instance, the LZ latch 89 will not be set.
g Hence, the P register 90 is incremented, and the L register 66 is decremented. The SA register 36 is again loaded with the contents 11 of the LSR array register 70 addressed by the contents of the P
12 register 90, and the sequence just described repeats until the contents 13 of all of the LSR array registers 70 have been stored. This fact 14 is indicated when L register 66 has been decremented to zero and the LZ latch 89 is set.
16 With LZ latch 89 set, a T3 CPU cycle is taken to load the 17 CTDE SAR 53 with the contents of the SB register 37. The current 18 TDE address in SAR 53 is then transferred into the OP 1 SAR 54 19 during a T2 cycle. An A2 CPU cycle is then taken to add two to the OP 1 SAR 54. A Sl CPU cycle is then taken to retrieve, from main 21 storage 10, a value at the OP 1 address, and load this value into 22 SA register 36 and increment the OP 1 address. Thus, SA register 36 23 is loaded with the IA field of TDE 1. The IAR SAR 51 is then 24 loaded with the contents of the SA register 36 during a T2 cycle.
The IL and condit~on code registers 38 and 65, respectively, are 26 then loaded with the IL and CC fields from TDE 1 by first retrieving 27 these fields from main storage 10 and loading them into the SA
28 register 36 during an Sl cycle, and then transferring the contents llU;~
Detailed Description (continued) l of the SA register to registers 38 and 65 during a T2 cycle.
2 The LSR array registers 70 are then loaded by first 3 setting the L register 66 to a value of fifteen during a Tl cycle, 4 and then loading P register 90 with a zero value during another Tl cycle. A Sl cycle is then taken to load the SA register 36 with a 6 value for base register 0 of LSR array registers 70 from main 7 storage lO at an address taken from OP 1 SAR 54. The OP 1 SAR 54 8 is incremented during this Sl cycle. A T2 cycle is then taken to 9 load base register 0 of LSR array 70 with the value from the SA
register 36. The LZ latch 89 is tested and it will not be zero.
11 Hence, the L register 66 is decremented and the P register 90 is 12 incremented. A Sl CPU cycle is then taken to again load the SA
13 register 36 with a value from main storage 10 for the next LSR
14 array register 70, i.e., base register 1 of LSR array registers 70, and the loop just described repeats until all LSR array registers 70 16 are loaded. This condition is indicated by the setting of LZ latch 89.
17 An Al cycle is then taken to subtract the contents of the IL register 38 18 from the IAR SAR 51. The address in IAR SAR 51 now points to the 19 first instruction of task TDE 1, which is then prefetched into the IS register 35 during a Sl cycle. The task switch is complete and 21 I-fetch cycles are executed for the first instruction of the new task.
22 Before describing the fetching and execution of the first 23 instruction of the new task, which, in the example shown in FIG. 28, 24 is a send message instruction, the details of the T3, A2 and S2 CPU
cycles will be described. Those elements of the computer involved 26 in the T3 CPU cycle are shown in FIG. 9, and a timing diagram for 27 the T3 CPU cycle is shown in FIG. 16. The function of the T3 CPU
28 cycle is to transfer the contents of any source register feeding B-,~

llU;~
Detailed Description (continued) 1 bus assembler 62 to any register connected to receive data via C-2 bus 47. The inputs into B-bus assembler 62 have been previously 3 described, and are selected by signals from control unit 100 over 4 bus 103. The data fed into B-bus assembler 62 from the selected source then passes over B-bus 63 to ALU 45. ALU 45 is controlled 6 by a signal from control unit 100 over line 104, to pass the data 7 on B-bus 63 to 0 register 46. 0 register 46 is loaded with the 8 data from ALU 45 by a load signal from control unit on line 105.
9 C-bus 47 receives the data from 0 register 46 and passes it to destination registers previously described. If one of the SAR
11 array registers 50 is to be the destination register, control 12 unit 100 provides an address on bus 101, a selection signal to D-13 bus assembler 48 on line 110 and a load pulse on line 111. If the 14 destination register is to be one of the LSR array registers 70, P
register 90 contains the address for selecting the LSR array register, 16 and control unit 100 provides a load signal on line 112. If the 17 selected register is other th~n the registers just described, 18 control unit 100 provides a load pulse on representative load 19 line 106. The other destination registers, of course, are IS
register 35, SA register 36, SB register 37, IL register 38, condition 21 code register 65, L register 66 and P register 90. From the foregoing, 22 it is seen that the T3 CPU cycle is like a T2 CPU cycle, but the 23 source data comes from sources feeding the B-bus assembler 62 24 rather than sources feeding A-bus assembler 39.
The A2 CFU cycle is similar to the Al CPU cycle, but 26 functions to control ALU 45 and inputs thereto from sources feeding 27 A-bus assembler 39, and feeding ALU 45 via A-bus 40, and an immediate 28 operand applied to B-bus assembler 62 and feeding ALU 45 via B-Detailed Description (Continued) ] bus 63. ALU 45, controlled by control unit 100, performs the appropriate 2 function, and the result is returned to either the source register 3 or dropped. ALU 45 appropriately places AC and AZ latches 95 and 96 4 in their proper states via lines 43 and 44, respectively, as a consequence of the ALU operation. In FIG. 11, if the source of the data having an 6 input into ALU 45 via A-bus 40, is to be one of the SAR array registers 7 50, control unit 100 provides an address on bus 101 and a read signal on 8 line 114. The data then transfers to A-bus assembler via bus 32. If 9 the source is to be one of the LSR array registers 70, control unit 100 provides a read pulse on line 107 and data is read from the register 11 selected by the address in P register 90. The data passes from the 12 selected LSR array register 70 to the A-bus assembler 39 via bus 69.
13 All other sources feeding A-bus assembler 39 do not require a read signal.
14 The particular source into A-bus assembler 39 is selected by control unit 100, which provides selection signals or. bus 108. The immediate 16 operand comes from emit encoder 60, which is rendered active by control 17 unit 100 via line 102. B-bus assembler selects the emit encoder 60 as 18 an input source in response to control signals from control unit 100 via 19 bus 103. ALU 45 performs the desired operation under control of a signal from control unit 100 via line 104. The result is entered into 21 O register 46 when control unit 100 provides a load signal on line 105.
22 The result in register 46 is then available to C-bus 47, where it is fed 23 to a destination register.
24 If the destination register is to be one of the SAR array registers 50, control unit unit 100 again provides an address on 2~

Detailed Descripeion (continued) 1 bus 101, a load signal on line 111 and a D-bus assembler selection 2 signal on line 110, whereby bus 47 is selected as the source into 3 D-bus assembler 48, and the data enters the selected SAR array 4 register 50 via D-bus 49. If the destination register is one of the LSR array registers 70, control unit 100 provides a load pulse 6 on line 112, and the data on bus 47 enters the register selected by 7 an address provided from P register 90. If the destination of the 8 result is for registers other than SAR array registers 50 or LSR
9 array registers 70, control unit 100 provides a load pulse on line 106 which is representative of load lines leading to the other 11 destination registers.
12 The details of the S2 CPU cycle are illustrated in FIG's.
13 13 and 20, The S2 CPU cycle differs from the Sl CPU cycle in that 14 data is written into main storage from either SA register 36 or SB
register 37 via buses 28 and 29, respectively, which feed SI bus 16 assembler 34, which in turn feeds data register 17 via bus 31. The 17 data then is passed to main storage 10 from storage control 15 over 18 bus 12 and written into a storage location designated by the address 19 in address register 18. The address placed into register 18 comes from one of the SAR array registers 50. Specifically, control 21 Ullit 100 provides an address on bus 101 to address SAR array 50.
22 The address data is read from the selected SAR array register 50 23 in response to a read signal from control unit 100 via line 114.
24 The address data then passes from the selected SAR array register 50 over bus 32 to address register 18. The address in register 18 is 26 then presented by storage control 15 to main storage 10 over address 27 bus 16 when control unit 100 provides a signal on line 115. The 28 timing for the signal on line 115 is set forth in the timing diagram Detailed Description (continued) 1 of FIG. 20.
2 The data which is to be written into storage is selected 3 from either SA register 36 or SB register 37 by a signal from 4 control unit 100 via line 118 which is applied to SI bus assembler 34. The data passed by SI-bus assembler 34 enters data register 17 6 via bus 31, and is then presented by storage control unit 15 to main 7 storage 10 via bus 12. The data, of course, is available to main 8 storage 10 prior to the storage write pulse on line 115 as seen in g FIG. 20. Additionally, the address provided from the selected SAR
array register 50 can be incremented or decremented by incrementer 59 11 and then loaded back into the selected SAR array register 50. During 12 the incrementing or decrementing operation, control unit 100 maintains 13 the address for the selected SAR array register on bus ]01. Control 14 unit 100 provides a source selection signal to D-bus assembler 48 via line 110, and a load pulse on line 111, whereby the incremented 16 or decremented address is then loaded back into the selected SAR
17 array register 50.
1~ With the immediate foregoing description, all CPU cycles 19 involved in the present invention have now been described. Further, task initialization, instruction execution under a task and task 21 switching have been described. Additionally, intertask communication, 22 by way of a receive message instruction, has been described.
23 Intertask communication by way of a send message instruction will 24 now be described.
The format of a send message instruction (SENDM) is shown 26 in FIG. 3, and it includes an OP code, an I field which contains a 27 register address and an OP 1 field. The send message instruction 28 is a four-byte instruction. The function of a send message instruction Detailed Description (continued) 11~3~6~

1 is to enqueue a message onto a SRQ and to determine if there are 2 one or more inactive waiting TDE's on the wait list of the SRQ. If 3 there are TDE's on the wait list of the SRQ, the TDE's are dequeued 4 from the wait list and enqueued in priority sequence onto the TDQ, and the task dispatcher is invoked. If there are no TDE's on the 6 wait list, the operation is complete and the next instruction of the 7 active task is fetched without invoking the task dispatcher.
8 The execution of a send message instruction is generally g shown in FIG. 4, and specifically shown in FIG's. 28, 29 and 30.
In FIG. 4, the send message instruction enqueues the message pointed 11 at by the pointer in the register defined in the I field of the 12 send message instruction; i.e., the R2 register specified by the 13 OP 1 field in the send message instruction. The TDE's on the wait 14 list of the specified SRQ are enqueued to the TDQ in priority sequence. In FIG. 28, the send message instruction is the first ]6 instruction of the task associated with TDE 1. The message is 17 contained in storage at an address specified by base register 6 of 18 LSR array 70. The message is SRM 2, and it will be enqueued onto 19 SRQ 1, which is pointed at by the address in the OP 1 field in the send message instruction.
21 The send message instruction is prefetched as described 22 above, and the I-fetch cycles, as shown in FIG. 21, follow in the 23 manner previously described. Upon completion of the I-fetch cycles, 24 SENDM cycles are taken. The SENDM cycles are set forth in FIG. 24.
Upon entering the SENDM cycles, the send latch 87 is set~ and receive 26 latch 88, send phase latch 97 and receive phase latch 98 27 are reset. A T2 cycle is then taken to transfer the address from 28 base register 6 of LSR array 70 to OP 2 SAR 55. This is followed ~0976-014 39 1103;~
Detailed Description (continued) 1 by a Sl cycle, which causes the transfer of the key field of SRM 2 2 from main storage 10 to SB register 37. During this Sl cycle, the 3 address contained in OP 2 SAR 55 is incremented so as to point to 4 the SRM chain address field of SRM 2. With the Sl cycle complete, a T2 cycle is taken to transfer the contents of OP 1 SAR 54 into 6 the PCH SAR 56, so as to save the address in the event SR~ 2 is being 7 enqueued onto an empty SRQ. The operation then switches to insert 8 cycles, which are shown in FIG. 25.
9It should be noted that at the start of the insert cycles, 10SA register 36 contains the first field of SRQ 1, the SB register 37 11 contains the first field of SRM 2, PCH SAR 56 contains the address 12 of SRQ 1 and OP 2 SAR 55 contains the address of the second field 13 of SRM 2. The first cycle of the insert cycles is a T2 CPU cycle, 14 where the contents of SA register 36 are transferred to CCH SAR 57.
Thus, CCH SAR 57 contains the address of the first SRM or SRM 1 on 16 SRQ 1. An A2 cycle is taken, and during this cycle, ALU 45 performs 17 an Exclusive OR of the contents of CCH SAR 57 with zeros from emit 18 encoder 60, to determine if there are any SRM's on SRQ 1.
19In the particular example of FIG's. 28-30, inclusive, there are SRM's initially on SRQ 1. Hence, AZ latch 96 is reset by 21 ALU 45. A Sl cycle is then taken to load the SA register 36 with the 22 key field of SRM 1. Also, the CCH SAR 57 is incremented to point to 23 the second field of SRM 1, which contains the SRM chain address.
24 An Al cycle is executed to determine if the key field of SRM 1, which is contained in the SA register 36, is greater than the key 26field of SRM 2, which is contained in the SB register 37. ALU 45 27 performs a subtract operation to accomplish this comparison. If 28 the comparison is satisfied, the AC latch 95 will be set and the AZ

llU;~
Detailed Description (continued) 1 latch 96 will be reset. In the particular example, the comparison 2 fails because the AC latch is reset as a result of the ALU operation.
3 A Sl cycle is then executed to transfer the SRM chain address field 4 of SRM 1 to SA register 36, and to increment the CCH SAR address to point to SRM 1. A T2 cycle is then taken to transfer the contents 6 of CCH SAR 57 to PCH SAR 56. This is followed by an A2 cycle to 7 increment PCH SAR 56 so as to point to the SRM chain address field 8 of SRM 1. The operation then loops back to a T2 cycle for transferring 9 the contents of SA register 36, which now contains the address of SRM 3 to CCH SAR 57. The sequence of CPU cycles which test for the 11 end of the SRM chain condition and perform the SRM key comparison, 12 take place for a second time. In the example under consideration, 13 the key field of SRM 3, i.e., three, is greater than the key field 14 of SRM 2, i.e., two. Thus, the comparison is successful, and AC
latch 95 is set and AZ latch 96 is reset. A T2 cycle is then taken 16 to transfer the contents of CCH SAR 57 to SA register 36. With 17 this transfer, the SA register 36 contains the address of SRM 3.
18 A S2 cycle is then executed to transfer the contents of the SA
19 register 36 to the SRM chain address field of SRM 2 in main storage 10.
SRM 3 is now chained to SRM 2, whereas previously, SRM 3 had been 21 chained to SEM 1. During this S2 cycle, the contents of OP 2 22 SAR 55 are decremented to point to-the beginning of SRM 2. A T2 23 cycle is then taken to transfer the address in OP 2 SAR 55 to SA
24 register 36. A S2 cycle is then taken to transfer the contents of SA register 36 to the SRM chain address field of SRM 1 in main 26 storage 10. This completes the enqueueing of SRM 2 onto the SRQ 1 27 message chain.
28 The insert cycle operation continues by decoding latches 87, Detailed Description (continued) liV~

1 97 and 98. In the example under consideration, latch 87 is set and 2 latches 97 and 98 are in the reset state. Because of this, an 3 operation takes place whereby latch 97 is set, and an A2 cycle is 4 executed to increment the contents of OP 1 SAR 54 to point to the TDE chain address field of SRQ 1. A T2 cycle is then taken to 6 transfer the contents of OP 1 SAR 54 into PCH SAR 56. A Sl CPU
7 cycle follows, and during this cycle, the contents of the TDE chain 8 address field of SRQ 1 are transferred into SA register 36. The 9 various registers in the CPU 30 are now set up for removing the first TDE from the TDE chain of SRQ 1. TDE 0 had been enqueued 11 onto SRQ 1, as illustrated in FIG. 29. With the Sl cycle complete, 12 the operation switches to remove cycles of FIG. 27.
13 The remove cycles for dequeueing a TDE from a queue have 14 already been described. In this particular instance, the TDE
chain address field of the SRQ 1 is tested for a value of all 16 zeros. The TDE chain address field of SRQ 1 will not be zero because 17 TDE 0 is chained thereto, and thus, the test for all zeros will 18 fail. The contents of the SA and SB registers 36 and 37 are then 19 compared to each other. When dequeueing a TDE from a SRQ during a send message instruction, the result of the comparison of the 21 contents of the SA register 36 with the SB register 37 is immaterial 22 because the state of the ST latch 97 controls further CPU execution.
23 Thus, when the AZ latch 96 and the ST latch 97 are decoded, the 24 operation switches to a S2 cycle during which the contents of SA
register 36, which represent the TDE chain address field of TDE 0, 26 are transferred to the TDE chain address field of SRQ 1 in main 27 storage 10. This effectively places zeros in the TDE chain address 28 field of SRQ 1, thereby removing TDE 0 from the chain of TDE's on Detailed Description (continued) 11~3~

l SRQ 1. Hence at this time, TDE 0 has been removed or dequeued 2 from SRQ 1.
3 The remaining cycles set up the necessary CPU
4 facilities for enqueueing TDE 0 onto the TDQ. The S, R and RT
latches 87, 88 and 98 are decoded, and a T2 cycle is taken to 6 transfer the contents of CCH SAR 57 representing the address of 7 TDE 0 to OP 2 SAR 55. The address in OP 2 SAR 55 is then used 8 during a Sl cycle to transfer the key field of TDE 0 from main 9 storage 10 to SB register 37, and to increment the contents of OP 2 SAR 55 so as to point to the TDE chain address field of TDE 0.
11 Also, during this Sl cycle, the state of the S latch 87 is tested 12 and, because it is set, a T2 cycle is executed next to transfer the 13 contents of TDQ SAR 52 to PCH SAR 56. A Sl cycle follows to fetch 14 the TDE chain address field of the TDQ in main storage 10 and load it into the SA register 36. CPU insert cycles of FIG. 25 then 16 begin.
17 ~s previously described, the main loop of the insert 18 cycles is executed until the proper location within the chain list 19 is located for inserting the TDE 0 in key sequence. In the particular example under consideration, the loop is executed once, and TDE 0 21 is enqueued as the top element of the chained list of TDE's. In 22 general, this sequence of dequeueing and enqueueing TDE's continues 23 until all TDE's have been removed from the SRQ and inserted in key 24 sequence onto the TDQ. Hence, the S, ST and RT latches 87, 97 and 98 are decoded during the insert cycles, and the proper CPU facili-26 ties are set up for the remove cycles which are to follow. The 27 remove cycles Qf FIG. 27 are then again taken; however, in the 28 example under consideration, there are no more TDE's chained to ~r Detailed Description (continued) 1 SRQ 1, and hence, when the TDE chain address field of SRQ 1 is 2 tested for all zeros, the AZ latch 96 is found to be in the set 3 state. This causes the decode of the S and R latches 87 and 88.
4 With the S latch 87 is in the set state, D latch 93 will be set to indicate that the state of the TDQ has been changed since the 6 beginning of the execution of the send message instruction. Hence, 7 dispatch cycles must be executed before beginning the execution 8 of the next instruction of the new active task.
g Because the send message instruction execu~ion is complete, the next instruction will have been prefetched in the manner previously 11 described; however, during the I-fetch cycles of this next instruction, 12 the D and I/0 latches 93 and 94 will be decoded, and it will be 13 found that the D latch 93 is set and IJ0 latch 94 is reset. Hence, 14 I-fetch cycles are suspended and dispatch cycles will be taken.
Dispatch cycles occur in the manner previously described. In the 16 example under consideration, the function of the dispatch cycles is 17 to save the status of the current active task in TDE 1 and load the 18 status of task TDE 0 into the facilities of CPU 30, and thereby 19 pass control to the previously unsatisfied receive message instruction of TDE 0 by returning to I-fetch cycles. It will be recalled that 21 during the dispatch cycles, D latch 93 is reset and, hence, control 22 is passed to the previously unsatisfied receive message instruction 23 of TDE 0, and the I-fetch cycles for that instruction continue.
24 In the example under consideration, the receive message 25 instruction will now be satisfied because SRM 2 is now enqueued on 26 SRQ 1. Upon completing the receive message execution cycles illustrated 27 in FIG. 26, remove cycles follow. During the remove cycles, illustrated 28 in FIG. 27, the main loop is executed two times. A key compare Detailed Description (continued) 11~3~

1 occurs during the second time through the loop. SRM 2 is dequeued 2 from SRQ 1, where the dequeueing takes place in the manner previously 3 described. The S, R and RT latches 87, 88 and 98 are decoded.
4 R latch 88 is in the set state at this time, and thus, the address of the dequeued SRM 2, which is contained in CCH SAR 57, is transferred 6 to the LSR array register 70 specified by the R3 field of the 7 receive message instruction. The execution of the receive message 8 instruction is complete, and the I-fetch cycles for the next prefetched g instruction are activated. This completes the description of a satisfied receive message instruction.
11 Intertask communication is also accomplished by receive 12 count and send count operations, which include execution of receive 13 count and send count instructions, illustrated in FIG. 3. The 14 function of a receive count operation is to indicate a readiness to provide service or to determine if a previously requested function 16 has been completed. The receive count operation, like the receive 17 message operation, always has a TDE associated with it; i.e., the 18 top TDE on the TDQ. The receive count instruction has a blank I
19 field and an OP 1 field. The OP 1 field contains an address which points to the first word of a send receive count (SRC) queue.
21 During the operation of a receive count instruction, a count is 22 compared to a limit9 and if the count is greater than, or equal to, 23 the limit, the count is decremented by the limit and the instruction 24 is complete. If the count is less than the limit, the active TDE
is moved from the TDQ to the wait list of the SRC. The count field 26 is not incremented or decremented and the task dispatcher is executed.
27 The send count instruction contains a send count OP code 28 and an OP 1 field where the OP 1 field points to the first word of Detailed Description (continued) 1 the SRC queue. During operation of a send count instruction, the 2 count field is incremented by one and compared to a limit field.
3 If the count is greater than, or equal to, the limit, any TDE's on 4 the wait list of the SRC are enqueued to the TDQ in priority sequence, and the task dispatcher is invoked. If no TDE's are on the wait 6 list of the SRC, the instruction is complete. Also~ if the count is 7 less than the limit, the instruction is complete.
8 Operation of send count and receive count instructions g are illustrated inFIG~ 31. In FIG. 31, TDE O is the active TDE, and it's IA field is pointing to a receive count instruction. The 11 OP 1 field of the receive count instruction points to SRC 1. The 12 format of an SRC queue is shown in FIG. 3, and it consists of a 13 count field, a limit field and a TDE chain address field. In 14 FIG. 31, SRC 1 has a count of zero, a limit of one and a TDE chain address of zero. Because the initial values of the count and limit 16 fields of SRC 1 are zero and one, respectively, the receive count 17 instruction is unsatisfied, and TDE O is dequeued from the TDQ and lB enqueued onto the wait list of SRC 1. TDE 1 is then dispatched by 19 means of the task dispatcher as the highest priority task on the TDQ. TDE 1 has an instruction address which points to a send count 21 instruction. The OP 1 field of this send count instruction points 22 to SRC 1. During execution of the send count instruction, the 23 count field of SRC 1 is incremented by one. Thus, the count field 24 equals the limit field, and because of this, TDE O is dequeued from the wait list of SRC 1 and enqueued onto the TDQ as the highest 26 priority TDE. The task dispatcher then dispatches TDE O as the 27 active task. The receive count instruction pointed to by the IA
28 field of TDE O is reexecuted. This time, the count field is greater Detailed Description (continued) 1 than, or equal to, the limit field and the receive count instruction 2 is considered to be satisfied. The count field is decremented by 3 the limit field by means of a subtract operation, and the new value 4 of the count is returned to the count field of SRC 1, and the receive count instruction is complete. Instruction execution then 6 continues with the next sequential instruction of task TDE 0.
7 The receive count instruction goes through I-fetch cycles 8 in the manner previously described in connection with FIG. 21, and 9 then continues with receive count cycles set forth in FIG. 26. The sequence control latches, i.e., the S, R, ST and RT latches 87, 88, 11 97 and 98, are set to the states of zero, one, zero and zero, 12 respectively. These settings are the same as they were for the 13 receive message instruction. This assures that if TDE's are moved 14 during execution of the receive count instruction, they are moved in an identical manner as that for the receive message instruction.
16 After the sequence control latches have been set, an A2 cycle is 17 taken to increment the OP 1 SAR so that it will point to the limit 18 field of SRC 1. This is followed by a Sl cycle during which the 19 limit field is fetched from storage 10 and loaded into the SB
register 37. The contents of OP 1 SAR 54 are decremented to point 21 back to the count field of SRC 1. Thus, the SA register 36 con-22 tains a count field of SRC 1, and SB register 37 contains the limit 23 field of SRC 1. An Al cycle is then taken to determine if the 24 count field is greater than, or equal to, the limit field, and at the same time, to subtract the limit value from the count value.
26 If the count is greater than, or equal to, the limit, the ALU carry 27 latch AC 95 is set as a result of the ALU operation. As previously 28 indicated in the example under consideration, the count field value -Detailed Descripeion (continued) llV~

1 of zero is less than the limit field value of one, and hence, the 2 ALU carry latch AC 95 is reset by ALU 45. The condition of AC
3 latch 95 is then tested, and since it is in the reset state, it is 4 known that the receive count instruction is unsatisfied. Thus, it is necessary to dequeue TDE 0 from the TDQ and enqueue it as a 6 waiter on SRC 1. Therefore, the operation switches to remove 7 cycles.
8 The remove cycles are entered so as to dequeue TDE 0 from 9 the TDQ, and enqueue TDE 0 on SRC 1. The remove cycles for performing the task switch have been previously described. Thus, the task 11 switch takes place in the same manner as for other task switches, 12 and at this time, control is passed by the task switch to TDE 1, 13 which executes the send count instruction, as generally described 14 above. During execution of the send count instruction, I-fetch cycles are taken, as previously described, and then the operation 16 switches to send count cycles, which are shown in detail in FIG. 24.
17 At the beginning of the send count cycles, the sequence 18 control latches S, R, ST and RT 87, 88, 97 and 98, respectively, 19 are set to the states of one, zero, zero and zero, respectively.
Thus, the sequence control latches for the send count inStruCtiOn 21 are set to the same states as for the send message instruction.
22 This insures that if TDE manipulations are necessary, they proceed 23 in identical fashion as for the send message instruction. An A2 24 CPU cycle is then taken to increment OP 1 SAR 54 so as to point to the limit field of SRC 1. This cycle is then followed by an Sl CPU
26 cycle for fetching the SRC limit field from main storage 10, and 27 enter it into the SB register 37. Also, during this Sl CPU cycle, 2~ the OP 1 SAR 54 is decremented to yoint back to the count field of Detailed Description (continued) 1 SRC 1. At this time, the SA register 36 contains the count field, 2 and SB register 37 contains the limit field of SRC 1. An A2 cycle 3 is then taken to increment the count field by one. This A2 cycle 4 is followed by a S2 cycle to store the incremented count field into main storage 10. Next, an Al cycle is taken to determine if the 6 incremented count field is greater than, or equal to, the limit 7 field. If the count is less than the limit, the ALU carry latch 8 AC 95 is set by ALU 45, and if the count is greater than, or equal 9 to, the limit, the ALU carry latch 95 is reset by ALU 45. In the example under consideration, the count is greater than, or equal 11 to, the limit and hence, the ALU carry latch AC 95 is reset by 12 ALU 45. It should be noted that if the count were less than the 13 limit, the send count instruction execution would be complete, and 14 I-fetch cycles would be activated to execute the next sequential instruction of the TDE O instruction stream.
16 Because the ALU carry latch AC 95 is reset, the control 17 unit 100 sets the ST latch 97 and, thereafter, initiates an A2 CPU
18 cycle for incrementing the contents of OP 1 SAR 54 by two. The 19 incremented value is then transferred to PCH SAR 56 during a T2 CPU
cycie. This T2 CPU cycle is then followed by a Sl CPU cycle for 21 loading SA register 36 with a PCH value from main storage 10.
22 Remove cycles are then taken so as to dequeue TDE O from SRC 1 and 23 enqueue TDE O to the TDQ. Once this is accomplished, the dispatch 24 cycles are activated, and the task switch from TDE 1 to TDE O
occurs. Control is then returned to the previously unsatisfied 26 receive count instruction of TDE 0. Instruction exeuction continues 27 for the receive count instruction by executing I-fetch cycles and 28 then activating the receive count cycles. The receive count cycles Detailed Description (continued) 11~3~

1 proceed exactly as described before, except that this time the ALU
2 carry latch AC 95 is in the set state and hence, instead of proceeding 3 to remove cycles, a S2 cycle is taken to store the decremented 4 count field from the SA register 36 back into the count field of SRC 1 in main storage 10. This completes execution of the receive 6 count instruction, and instruction execution continues with the 7 next sequential instruction of the task TDE 0 instruction stream.
8 In addition to the receive message, receive count, send 9 message and send count instructions, there are also enqueue message and dequeue message instructions. These instructions are shown in 11 FIG. 3. The enqueue message instruction (ENQM) has an enqueue 12 message 0P field, an I field and an OP 1 field. The I field contains 13 an address for pointing to base register 2 of LSR array registers 70.
14 The enqueue message instruction functions to enqueue a SRM onto a SRQ in a manner similar to that of the send message instruction.
16 It is seen in FIG. 24 that, upon entering the enqueue message 17 cycles, the sequence control latches S, R, ST and RT 87, 88, 97 and 18 98 are all set to the reset state. Thereafter, T2, Sl and T2 19 cycles are taken, as in the case of a send message instruction.
After the last T2 cycle, insert cycles are taken.
21 The dequeue message inStruCtiOn (DEQM) has a format 22 similar to the receive message instruction and functions in a 23 manner similar to the receive message instruction. It is seen that 24 in FIG. 26, the sequence control latches S, R, ST and RT 87, 88, 97 and 98 are all set to the reset state and, thereafter, a T2 cycle 26 is taken. Upon completion of the T2 cycle, the operation switches 27 to remove cycles, as in the case of a receive message instruction.
28 I/0 tasks are enqueued on the TDQ in the same manner as ,~

Detailed Description (continued) 1 any other task. In FIG. 32, the I/O task is illustrated as the 2 highest priority TDE on the TDQ. The I/O task is identified by the 3 abbreviation IOM, meaning I/O manager. The IOM task initiates an 4 I/O request by executing a send message instruction. The send message instruction will enqueue a SRM onto a SRQ and dequeue 6 any TDE's on that SRQ. In the example of FIG. 32, the SRM is 7 identified as an ORE, which means operation request element. The 8 TDE on the SRQ is an operational unit (OU) task (OUT). The OU task, 9 dequeued from the SRQ and enqueued onto the TDQ, becomes the active task and handles the request by using a receive message operation.
11 This is illustrated in FIG. 33.
12 The OU task interprets the request and issues a proper 13 device command to the I/O channel 500, and then waits on the SRC
14 until the I/O function is complete. The OU task includes a receive count (RECC) instruction in its instruction stream. This instruction 16 is not satisfied, and, thus, TDE (OUT) is dequeued from the TDQ
17 and enqueued onto the SRC queue. This operation is represented by 18 the dashed line in FIG. 33. A task switch takes place as a result 19 of the dequeuing operation, and the IOM task becomes the active task.
The IOM task issues a receive message instruction which is not 21 satisfied, and, consequently, the IOM task is dequeued from the 22 TDQ and enqueued onto the IOM SRQ, pointed to by the OP 1 field of 23 the receive message instruction, as illustrated in FIG. 34. A
24 task switch takes place, and the highest priority task on the TDQ
becomes the active task. The IOM task is waiting on the SRQ, and 26 the OU task is waiting on the SRC, as illustrated in FIG. 35.
27 When the I/O function is complete, the I/O channel sends 28 a SRC address to an event stack 25, FIG. 36, which is in main Detailed Description (continued) 11~3~

1 storage 10, and sets the I/O latch 94 by means of a signal via 2 line 512, FIG. 1. The I/O event field on the I/O event stack 25 3 is the address of the SRC on which the OU task is waiting.
4 Because the I/O latch 94 was set by the signal from the I/O channel, then during I-fetch cycles, the operation will switch to I/O event 6 cycles.
7 The I/O event cycles, set forth in FIG. 23, perform the 8 function of the I/O event handler. The first operation of the I/O
9 event cycles is a Sl CPU cycle for fetching the SRC address from the event stack in main storage 10 and loading it into the SA
11 register 36. It should be noted that the top entry of the event 12 stack 25, in this particular example, contains all zeros. This all 13 zeros entry is used to indicate that the event stack is empty.
14 Therefore, the next operation of the I/O event cycles is to determine if there is any I/O event field in the I/O event stack. This 16 determination is made by taking an A2 CPU cycle for examining the 17 contents of the SA register 36. If the I/O event stack is empty, 18 ALU 45 sets the AZ latch 96. On the other hand, if there is an I/O
19 event field on the I/O event stack, AZ latch 96 will be in the reset state. Therefore, the next operation is to test the AZ
21 latch. If the AZ latch is set, the I/O latch 94 is reset and the 22 operation switches to the I-fetch cycles and this time through the 23 I-fetch cycles, the I/O latch 94 will be decoded as being in the 24 reset state.
If the AZ latch 96 is reset and A2 CPU cycle is taken to 26 decrement the contents of the I/O SAR 58 so that it will point to 27 the next SRC address which, in this example, is the SRC address 28 above the current one. It should be recognized that this is a ~7 ~

Detailed Description (continued) llU~

1 matter of implementation. The I/O event stack, so far as the 2 present invention is concerned, could be a set of registers, and 3 these registers could be addressed by the contents of I/O SAR 58, 4 and whether the address is incremented or decremented would be a matter of choice. In fact, a fixed register could address the I/O
6 event stack of registers, and the contents of the I/O SAR 58 would 7 be transferred to this register for addressing the I/O event stack 8 of registers. In the particular example under consideration, there 9 is no need to have a separate set of I/O event stack registers, because main storage 10 was adequate, both with respect to capacity 11 and speed. Normally, if there were some critical speed req~irements, 12 the I/O event stack would be implemented as a set of registers 13 rather than reserved positions in main storage.
14 A T2 CPU cycle follows the decrementing of the I/O SAR 58 to transfer the contents of SA register 36 into OP 1 SAR 54. The Sl 16 cycle is then taken to load the SA register 36 with the contents of the 17 main storage location pointed to by the address in OP 1 SAR 54.
18 Send count cycles are then entered to send a count to the count 19 field of the SRC and remove TDE~s waiting on that SRC; i.e., in this particular instance, the OU task TDE. The operation just 21 described repeats until all I/O events on the I/O event stack 22 have been handled; i.e., until the I/O event stack is empty and the 23 I/O latch 94 is reset.
24 It is seen in FIG. 36 that the OU task has been taken out of the wait state and enqueued on the TDQ. The receive count 26 instruction is satisfied when the OU task had been dispatched.
27 The OU task then sends a SRM, which contains completion status, to 28 a SRQ; i.e., the OUQ. This operation is represented in FIG. 37, 3 ~

Detailed Description (continued) 1 where the OU task has a send message instruction containing an R2 2 field for addressing a LSR 70. The selected LSR 70 contains an 3 address which points to the SRM, in this instance an operational 4 request element (ORE) object. This SRM (ORE) object is enqueued onto the SRQ (IOM), which is pointed to by the OP 1 field of the SENDM
6 instruction. Additionally, the TDE (IOM) waiting on the SRQ (IOM) is 7 enqueued on the TDQ, and a task switch takes place. The IOM task is 8 then informed of the completion status by receiving the ORE from the 9 response queue. This is illustrated in FIG. 38, where a RECM instr tion of the active task TDE (IOM) is executed.
11 The particular operation described is also schematically 12 illustrated in FIG. 2, where it should be noted that user tasks 13 originate I/O requests to I/O tasks and field responses, which 14 indicate completion by using the send receive operations to SRQ's.
It should also be noted that timer events are signaled to the i6 system as an I/O event and the I/O event handler functions in the 17 manner previously described to perform a send count to a SRC for 18 each timer event. These SRC's associated with timer events are 19 managed by a system timer task to provide timing services to the system.

~0976-014 54

Claims (9)

The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows:

1. Task handling apparatus in a computer system having main stor-age interconnected with a central processing unit (CPU) and I/O units, where said CPU includes means for processing an active task dispatch-ing element comprising:
a source of task dispatching elements, each having a priority indicator, said task dispatching elements including CPU and I/O task dispatching elements, task queue register means selectively loadable to store said task dispatching elements, means for loading said task queue register means with task dis-patching elements in priority sequence from said source, where the highest priority task dispatching element is dispatchable as an active task and all other task dispatching elements are inactive dispatch-able task dispatching elements, task dispatching means for determining the highest priority task dispatching element in said task queue register means, a source of task messages, each having a priority key, intertask communication queue register means selectively loadable with task dispatching elements and with task messages, intertask communication means comprising send means activatable by said active task dispatching element for loading messages from said source of messages in said intertask communication queue regis-ter means and for unloading task dispatching elements from said intertask communication queue register means and loading said un-loaded task dispatching elements in priority sequence in said task queue register means, said send means activating said task dis-patching means whenever said send means loads one or more task dis-patching elements in said task queue register means, and receive means activatable by said active task dispatching element for unload-ing messages for said active task dispatching element from said intertask communication queue register means and in the absence of any message for said active task dispatching element for unloading said active task dispatching element from said task queue register means and loading it in priority sequence in said intertask communica-tion queue register means, said receive means activating said task dispatching means whenever said receive means unloads said active task dispatching element from said task queue register means, and task switching means having first means responsive to said task dispatching means having been activated in response to said send means loading said task queue register means with a task dis-patching element and said task dispatching means having deter-mined that said loaded task dispatching element has a priority higher than the priority of said active task dispatching element for making said active task dispatching element inactive dispatch-able and said higher priority loaded task dispatching element an active task dispatching element and having second means responsive to said task dispatching means having been activated in response to said receive means unloading said active task dispatching ele-ment from said task queue register means for making the highest priority task dispatching element remaining in said task queue register means an active task dispatching element.

2. The task handling apparatus of claim 1 wherein said task dis-patching elements having in addition to said priority indicator, a task dispatching element address field and a task status field, said task status field including information for starting or con-tinuing execution of the associated task.

3. The task handling apparatus of claim 1 further comprising:
I/O event handler means having first means responsive to an I/O event occurring in one of said I/O units for storing status of said I/O event and second means for activating said send means for loading an I/O task dispatching element in priority sequence in said task queue register means.

4. The task handling apparatus of claim l, wherein said task queue register means is in main storage of said computer system.

5. The task handling apparatus of claim 1, wherein said task mes-sages in addition to said priority key include a message address field and a message information field, said messages being loaded in said intertask communication queue register means according to said priority key.

6. The task handling apparatus of claim 1 further comprising:
an intertask communication counter register means selectively loadable and unloadable with task dispatching elements, limit values and count values where said receive means loads task dispatching elements in said intertask communication counter register means and send means unloads task dispatching elements from said inter-task communication counter register means, means for selectively incrementing said count value, comparing means for comparing said incremented count value, with said limit value, indicating means responsive to said comparing means for indicat-ing that said incremented count value is greater or equal to said limit value, or is less than said limit value said send means being responsive to said indicating means indicating that said incremented count value is greater than or equal to said limit value to unload any task dispatching element in said intertask communication counter register means and load the same in priority sequence in said task queue register means.

7. The task handling apparatus of claim 6, wherein said indicat-ing means is a latch.

8. The task handling apparatus of claim 6, wherein said comparing means compares said count value with said limit value, said indicat-ing means being responsive to said comparing means to indicate that said count value is greater than or equal to said limit value or that said count value is less than said limit value, and further comprising:
means responsive to said indicating means indicating that said count value is greater than or equal to said limit value for decre-menting said count value by said limit value, said receive means being responsive to said indicating means indicating the said count value is less than said limit value unloads the active task dis-patching element from said task queue register means and loads the same in priority seuqence in said intertask communication counter register means.

9. Task handling apparatus for a computer system having main stor-age for storing data and instructions, storage access control mechanism for accessing main storage, a central processing unit (CPU) intercon-nected with said main storage and said storage access control mechanism for providing signals to said storage access control mechanism and operable to execute said instructions accessed from said main stor-age, and to transfer data to and from said main storage, and input/
output (I/O) devices connected to said CPU to perform I/O functions, the improvement comprising:
a source of task dispatching elements including CPU and I/O task dispatching elements, each task dispatching element having a priority indicator, task dispatching means including task queue register means, means for loading said task queue register means with task dispatch-ing elements in priority sequence from said source of task dispatch-ing elements, priority determining means for determining the highest priority task dispatching element in said task queue register means, said task dispatching means being operable to render the determined highest priority task dispatching element active, all other task dispatching elements in said task queue register means being in an inactive dispatchable state, a source of task messages, each having a priority key, inter-task communication queue register means for storing inactive wait-ing task dispatching elements in priority sequence and for storing messages in key sequence, and intertask communication means including a send mechanism for providing a message to an inactive waiting task by loading a message from said source of messages in said intertask communication queue register means and operable to unload inactive waiting task dis-patching elements from said intertask communication queue register means and to load in priority sequence said inactive waiting task dispatching elements in said task queue register means, and a receive mechanism for unloading messages from said intertask communi-cation queue means and providing said unloaded messages to said active task and for unloading said active task dispatching element from said task queue register means in the absence of a message for said active task and loading said unloaded task dispatching element in said intertask communication queue register means, said task dispatching means renders the highest priority inactive dispatchable task dispatching element in said task queue register means as deter-mined by said priority determining means as the active task dispatch-ing element.