Microcomputer with priority scheduling4794526Abstract A microcomputer comprising memory 60 and a process is arranged to execute a plurality of concurrent processes and share its time between them. The microcomputer includes as register (51) for indicating a current process as well as a collection of processes awaiting execution. Each process has a memory location 66 to provide an indication of a next process in a linked list of processes. Each process has an allocated priority and a separate linked list is formed for each priority. A register (53) indicates the front of one list and a further register (52) indicates the end of that list. Claims We claim: Description The invention relates to microcomputers and particularly to scheduling a plurality of concurrent processes to be executed by a microcomputer.
______________________________________
MostNeg the most negative value
(the most significant bit is one,
and all other bits are zero)
MostPos the most positive value
(the most significant bit is zero,
and all other bits are one)
MachineTRUE 1
MachineFALSE 0
NotProcess.p MostNeg
Enabling.p MostNeg + 1
Waiting.p MostNeg + 2
Ready.p MostNeg + 3
______________________________________
As in the example of the above mentioned patent applications, each process may have a workspace consisting of a vector of words in memory used to hold the local variables and temporary values manipulated by the process. A workspace pointer WPTR is used to point to a set location for the process workspace. As the workspace of each process consists of a number of words, it is not necessary to incorporate the byte selector. It is therefore possible to use the byte selector bits to represent the priority of the process. In this way each process can be identified by a "process descriptor" of the type shown in FIG. 6. The least significant bit indicates the priority of the process and the most significant 15 bits indicate the word in memory identifying the process workspace. In the present example the microcomputer allocates one of two possible priorities to each process. A high priority process is given the designation Pri=0 and a low priority process has a designation Pri=1. It can therefore be seen that each process descriptor comprises a single word which is formed by taking the "bitwise OR" of the workspace pointer WPTR and the process priority Pri. Similarly the workspace pointer WPTR can be obtained from a process descriptor by forming the "bitwise AND" of the process descriptor and NOT 1. The priority of the poocess can be obtained by forming the "bitwise AND" of the process descriptor and 1. CPU Data Paths and Registers The central processing unit 12 and its operation will be more fully understood with reference to FIG. 2. The CPU 12 includes an arithmetic logic unit (ALU) 30 and a plurality of data registers connected to an X bus, Y bus, Z bus and bidirectional data bus 31. The operation of the registers and their interconnections with the buses is controlled by a plurality of switches diagrammatically represented at 32 and controlled by signals derived from a microinstruction program contained in the ROM 13. Communication between the CPU and the memory is effected via a unidirectional address path 33 leading to the memory interface 14 as well as the data bus 31. As in the above mentioned patent applications, each instruction consists of 8 bits having the format shown in FIG. 7. 4 bits represent the required function of the instruction and 4 bits are allocated for data. Each instruction derived from the program sequence for the process is fed to an instruction buffer 34 and the instruction is decoded by a decoder 35. The output of the decoder is fed through a condition multiplexor 36 to a microinstruction register 37 used for addressing the microinstruction ROM 13. The operation of the instruction buffer 34, decoder 35, condition multiplexor 36, MIR 37, microinstruction ROM 13 and switches 32 are generally as described in the above mentioned patent applications. As the present embodiment is arranged to deal with two sets of processes, those with priority 0 and those with priority 1, two register banks are provided. Register bank 38 is provided for the priority 1 processes and a similar register bank 39 is provided for the high priority 0 processes. Both register banks have a similar set of registers similarly connected to the X, Y, Z and data buses. For simplicity, the registers and their connections have only been shown in detail for register bank 38. In addition to the two register banks allocated to specific priorities, the CPU includes a constants box 40, a register bank selector 41 and a number of other registers indicated in FIG. 2 which are common to both priority 0 and priority 1 processes. The registers are as follows:
__________________________________________________________________________
Abbreviation
Register
__________________________________________________________________________
Common to both priority processes
MADDR Memory address register 42 containing the address
of the memory location required.
DATAOUT A register 43 for supplying data to the memory on the
data bus 31.
IB Instruction buffer 34 for receiving sequentially
instructions from the memory.
TEMP REG A temporary register 44.
PROCPTR REG
A register 45 for holding a process pointer (no
priority indication).
PROCDESC REG
A register 46 for containing a process descriptor
PRIFLAG A 1 bit register or flag 47 for indicating the
priority 0 or 1 of the currently executing process.
If the processor is not executing a process this is
set to 1.
PROCPRIFLAG
A 1 bit register or flag 48 for indicating a process
priority.
Registers in Bank 38 for Priority 1
TREG A temporary register 49.
IPTR REG A register 50 which holds the instruction pointer
(IPTR) of any process indicated by register 51
WPTR REG A register 51 for holding the workspace pointer
(WPTR) of the current process or an interrupted
process.
BPTR REG A register 52 holding the workspace pointer of a
process at the end of a list of priority 1 processes
awaiting execution.
FPTR REG A register 53 holding the workspace pointer of a
process at the front of a list of priority 1
processes awaiting execution.
AREG A first register 54 for holding an operand for the
ALU 30 and arranged as a stack with registers 55 and
56.
BREG A second register 55 forming part of the stack.
CREG A register 56 forming a third register in the stack.
OREG An operand register 57 for receiving the data derived
from an instruction in the instruction buffer 34, and
used as a temporary register.
SNPFLAG A 1 bit register or flag 58 which when set to 1
indicates that the current process should be
descheduled on completion of the current instruction.
COPYFLAG A 1 bit register or flag 59 which when set to 1
indicates that the process is copying a block of
data to or from memory.
__________________________________________________________________________
The bank of registers 39 for priority 0 processes is the same as that already described for priority 1 processes. In the description that follows the suffix [1] indicates a register relevant to the priority 1 bank and the suffix [0] indicates that the register relates to the priority 0 bank. Where the priority is not known the suffix [Pri] indicates that a register of appropriate priority to the process is used. The registers are generally of word length which in this case is 16 bits apart from the 1 bit flags 47, 48, 58 and 59. The instruction buffer may be of 8 bit length if arranged to hold only 1 instruction at a time. The A, B and C register stack 54, 55 and 56 are the sources and destinations for most arithmetic and logical operations. They are organised as a stack so that the loading of a value into the A register is preceded by relocating the existing contents of the B register into the C register and from the A register into the B register. Similarly storing a value derived from the A register causes the contents of the B register to be moved into the A register and the contents of the C register into the B register. The TREG 49 is available to hold temporary values during the execution of all instructions apart from certain communication instructions which require copying of blocks of data and in that case the TREG 49 is used to indicate the action to be performed when the copying of the block of data is completed. The OREG 57 of both register banks 38 and 39 are connected to the decoder 35 so that for both priority processes that part of the instruction which is fed into the 0 register reaches the decoder for use in generating appropriate microinstructions. The SNP FLAG 58 and COPY FLAG 59 of both priority banks are also connected to the condition multiplexor 36 so that the microinstructions can take into account the setting of these flags for either priority process in determining the next action to be effected by the processor at any time. As the workspace pointer (WPTR) of a process is used as a base from which local variables of the process can be addressed, it is sometimes necessary to calculate offset values from the location indicated by the workspace pointer. The constants box 40 is connected to the Y bus aand enables constant values to be placed on that bus under the control of the microinstruction ROM 13. These can be used in pointing to offset locations in a process workspace. In order to effect selection of one or other of the register banks 38 or 39, the register bank selector 41 has inputs from the PRI FLAG 47, the PROCPRI FLAG 48 and the microinstruction ROM 13. The output from the register bank selector is connected to the condition multiplexor 36, to the decoder 35 and to the switches 32. Depending on the output of the microinstruction ROM 13, the selector will chose the register bank indicated by the PRI FLAG 47 or the PROCPRI FLAG 48. Memory Allocation for Process Workspaces As in the example described in the above mentioned patent applications, the microcomputer carries out a number of processes together sharing its time between them. Processes which are carried out together are called concurrent processes and at any one time the process which is being executed is called the current process. Each concurrent process has a region of memory called a workspace for holding the local variables and temporary values manipulated by the process. The address of the first local variable of the workspace is indicated by the workspace pointer (WPTR). This is indicated in FIG. 3 where four concurrent processes, Prcess L, M, N and O have workspaces 60, 61, 62 and 63. The workspace 60 has been shown in more detail and the workspace pointer held in the WPTR REG 51 points to the zero location which is a single word location having the address indicated in this example as 10000. The other local variables for this process are addressed as positive offset addresses from the word indicated by the workspace pointer. Some of the workspace locations with small negative offsets from the zero location are used for scheduling and communication purposes. In this example three additional word locations 65, 66 and 67 are shown having negative offsets of 1, 2 and 3 respectively below the zero location indicated by the WPTR. These three locations are as follows:
______________________________________
Offset Name of Offset
Name of Location
______________________________________
1 Iptr.s Iptr location
2 Link.s Link location
3 State.s State location
______________________________________
Location 65 is used when a process is not the current process to hold a pointer (IPTR) to the next instruction to be executed by the process when it becomes the current process. Location 66 is used to store a workspace pointer of a next process on a link list or queue of processes awaiting execution. Location 67 is normally used to contain an indication of the state of a process performing an alternative input operation or as a pointer for copying of a block of data. This will be described more fully below. The memory also provides word locations for process to process communication and FIG. 3 indicates such a soft channel 70. In addition to communication through soft channels provided by a single word in memory, external communication may occur through the serial links. Serial Links As described in the above mentioned patent application, data is transmitted from one microcomputer to another in the form of data packets having a predetermined protocol. The receipt of data is indicated by the transmission of an acknowledge packet. In this particular example, data is transmiteed in the form of packet illustrated in FIG. 8. Each packet consists of a standard unit of data which in this case consists of 1 byte (8 bits). The data packet commences with 2 start bits each of 1 followed by the byte of data and terminating with a stop bit of 0. After transmission of each packet as shown in FIG. 8, the input channel of a serial link which receives the packet is arranged to signal to its associated output channel to transmit an acknowledge packet of the type shown in FIG. 9. This is merely a 2 bit packet starting with a 1 and terminating with a 0. The instructions executed by a process to send or receive data may require that more than one such packet of data is involved in the message transmission and consequently the instruction may indicate how many standard units or bytes of data are to be transmitted in order to complete the message required by the instruction. The structure of the links is shown more fully in FIGS. 10 to 14. In the examples shown in FIG. 10 for serial links 70, 71, 72 and 73 are shown each having an input pin 26 and an output pin 27. Each link is connected by parallel buses 75 and 76 to the memory interface 14. The links are also connected to the interface control logic 15 by lines 77 and 78 which provide read request and write request signals respectively to the interface control logic. The control logic 15 is arranged to provide a "DATA VALID" signal to the links on a line 79. Each of the links is arranged to provide a status output signal on line 80 to the condition multiplexor 36 of FIG. 2. The Z bus is also connected to each of the links 70 to 73 and the Z bus is connected via line 81 to the sync logic 10. A line 82 provides an output from the microinstruction ROM 13 to the sync logic 10 and lines 83 provide an output from the sync logic 10 to the condition multiplexor 36. Lines 84 connect each of the links to the sync logic 10 for carrying request signals from the links when the links indicate a request for action by the processor. A line 85 connects the microinstruction ROM 13 to each of the links in order to provide request signals to the links from the processor. FIG. 11 shows more detail of one link. The link has an output channel 90 and an input channel 91. Both are connected to a link interface 92 which is shown more fully in FIG. 14. The link interface 92 is connected to the input pin 26 and output pin 27 and arranged to receive or transmit data and acknowledge packets as previously described with reference to FIGS. 8 and 9. The output channel 90, input channel 91 and link interface 92 are all supplied with clock pulses 93 from a common clock. The output channel 90 is arranged to receive from the link interface an OUTPUT ACK signal 94 and to supply to the link interface an OUTPUT DATA signal on bus 95 and an OUTPUT DATA VALID signal on line 96. Similarly the input channel is arranged to receive from the link interface 92 INPUT DATA on line 97, and INPUT DATA VALID signal on line 98 and to send to the link interface an INPUT ACK signal on line 99. A reset line 101 is connected to the output channel 90, the input channel 91 and the link interface 92. The output channel 90 is arranged to output a predetermined number of bytes of data from a specified memory location by making read requests on line 77 for data to be copied from addresses given on bus 76. The data is supplied to the channel on parallel bus 75 together with an OUTPUT DATA VALID signal on line 79. Similarly the input channel 91 is able to cause a specified number of bytes of data to be written into memory at a specified destination address by generating write requests on line 78 at memory addresses given on bus 76. The data is output to the memory on the parallel bus 75. In order to communicate with the processor, both channels 90 and 91 are connected to the Z bus. The microinstruction ROM 13 may make an OUTPUT REQUEST on line 85a to the output channel 90. In the case of the input channel 91 the microinstruction ROM 13 may provide three different signals on the bus 85. It may make an INPUT REQUEST 85b or an ENABLE signal 85c or a STATUS ENQUIRY 85d. The bus 84 leading to the sync logic 10 may carry an OUTPUT RUN REQUEST 84b and an OUTPUT PRIORITY signal 84a from the output channel 90. The bus 84 may carry an INPUT READY REQUEST 84c with an INPUT PRIORITY signal 84d or an INPUT RUN REQUEST 84e with an INPUT PRIORITY signal from the input channel 91 to the sync logic 10. The input channel 91 also provides a STATUS OUT signal on line 80. The function of these signals will be explained more fully later. FIG. 12 shows further detail of the output channel 90. The Z bus is connected to a priority register 110 used to indicate the priority of the process using the channel. The Z bus is also connected to a byte counter 111 and a pointer register 112 used to contain the address of the source of data to be indicated on bus 76. The channel also includes a transfer state machine 113. The state machines in the serial links each consist of a state register to hold the current state of the machine and a programmable logic array which responds to the value of the state register and various input signals to the state machine in order to produce a predetermined pattern of output signals and a new value for the state register. The state machine 113 has four inputs. These are output request on line 85a, reset on line 101, output ack on line 94 and count zero on line 114. At the beginning of a message output the byte counter register 111 indicates the total number of bytes to be transmitted in the message but as each byte is transmitted the register will decrement under control of a deccount output signal 115 from the state machine 113 and will generate the count zero signal 114 when no bytes remain to be sent. In addition to the deccount output 115, the state machine 113 provides a read request output on line 77, a run request on line 116 and incpointer on line 117. The pointer register 112 initially contains the pointer to the first byte to be transmitted but due to the signal on line 117 the pointer is incremented as each byte is transmitted. The output 116 is connected to the run request signal line which has been marked 84b and also to an AND gate 118 receiving a further input on line 119 from the priority register 110. In this way, the priority of the outputting process can be indicated on line 84a when a run request is made on line 84b. The signals on bus 75 and line 79 from the memory interface pass directly through the channel to the link interface 92 on lines 95 and 96. Bus 75 and line 95 transmit the value of the byte to be transmitted whereas lines 79 and 96 carry the output data valid signal which is generated by the memory interface to indicate that the data now sent properly represents a full byte of data. The succession of transition states for the transfer state machine 113 is as follows:
______________________________________
State Inputs Outputs Next State
______________________________________
any Reset Idle
Idle .DELTA. Outputreq Idle
Idle Outputreq SendByte0
SendByte0 ReadReq SendByte1
Sendbyte1 IncPointer WaitOutputAck
WaitOutputAck
.DELTA. OutputAck WaitOutputAck
WaitOutputAck
OutputAck DecCount CheckFinished
CheckFinished
.DELTA. CountZero SendByte0
CheckFinished
CountZero RunRequest Idle
______________________________________
FIG. 13 shows more fully the input channel 91. This includes a priority flag or register 120, a byte counter register 121 and a pointer register 122 all connected to the Z bus. The input and output signals for the channel are controlled by three state machines. These consist of a TRANSFER state machine 125, an ALTERNATIVE state machine 126 and a READY state machine 127. Each of the state machines receives an input of clock pulses from the same source 93. The TRANSFER state machine 125 controls the input of a message through the channel to a memory location. When the processor executes the instructions necessary to input a message, it loads the byte counter register 121 with an indication of the number of bytes to be input, the pointer register 122 is loaded with a pointer to the first memory location into which the message is to be copied and the priority flag 120 is set with an indication of the priority of the process executing the input instructions. The processor then effects an input request on line 85b which forms one of the inputs to the transfer state machine 125. The byte counter register 121 includes a decrementor arranged so that as each byte of input message is received the count is reduced until finally reaching zero. Similarly the pointer register 122 incorporates an incrementor so that as each byte is received the pointer increments to the memory destination address for the next byte of the input message. The transfer state machine 125 has a reset input from line 101, a count zero signal on line 128 from the byte counter 121, an input request from line 85b and a READY signal on line 129 from the READY state machine 127. The transfer state machine 125 has an output DECCOUNT on line 130 in order to decrement hhe byte counter 121. Similarly it has an output INCPOINTER on line 131 in order to increment the pointer register 122. It also provides an output write request on line 78, input ACK on line 99 and RUNREQ on line 84e. The succession of states of the transfer state machine 125 is as follows:
______________________________________
State Inputs Outputs Next State
______________________________________
any Reset Idle
Idle .DELTA. Inputreq Idle
Idle Inputreq AwaitByte
AwaitByte .DELTA. Ready AwaitByte
AwaitByte Ready WriteRequest
CheckFinished
IncPointer
DecCount
CheckFinished
.DELTA. CountZero AwaitByte
CheckFinished
CountZero RunReq Idle
______________________________________
The READY state machine 127 can be in the form of a simple flip-flop and is used to indicate whether a byte of data has been received in an input register in the link interface and not yet acknowledged. The READY state machine 127 has a reset input 101 and in addition it has an input signal input data valid on line 98 derived from the link interface when a valid byte of data has been received in an input register of the interface. In addition, the state machine 127 has an input 132 derived from the input ACK ignal line 99 so that the state machine is set in one condition when a byte of data has been received by the link interface and is then reset once the input ACK signal has been sent on line 99. The state machine 127 provides a single output READY on line 129 which forms an input to the transfer state machine 125 as well as one input to an AND gate 133 as well as a READY input 134 to the alternative state machine 126. The succession of states of the READY state machine 127 is as follows:
______________________________________
Transitions
State Inputs Outputs Next State
______________________________________
any Reset DataAbsent
DataAbsent
.DELTA. InputDataValid DataAbsent
DataAbsent
InputDataValid
Ready DataPresent
DataPresent
.DELTA. InputAck
Ready DataPresent
DataPresent
InputAck DataAbsent
______________________________________
The alternative state machine 126 deals with processes executing instructions for a number of alternative input channels. In addition to the READY input 134 it has a reset input 101 an enable input 85c and a status enquiry input 85d. It provides a READYREQ output 135 which leads to the signal line 84c. It provides a further output REPLY on line 136 which forms a second input to the AND gate 133. The output line 135 and 84e both form inputs to an OR gate 137. The OR gate provides an output to an AND gate 138 which also receives an input from line 139 indicating the priority of the process using the input channel. By use of input signals on lines 85, the processor can make an input request or enable the channel or make a status enquiry and these will be described more fully below. The link provides RUN requests or READY requests on lines 84 and by use of the gates 137 and 138 the priority is indicated on line 84d when either a READY request or RUN request is made. The provision of the AND gate 133 enables the READY status to be indicated on line 80. The succession of states of the alternative state machine 126 is as follows:
______________________________________
Transitions
State Inputs Outputs Next State
______________________________________
any Reset Disabled
Disabled
StatusEnquiry Disabled
Disabled
.DELTA. StatusEnquiry / Enable
ReadyReq Disabled
/ Ready
Disabled
.DELTA. StatusEnquiry / Enable
Enabled
/ Ready
Disabled
.DELTA. StatusEnquiry / Enable
Disabled
Enable StatusEnquiry Reply Disabled
Enabled
.DELTA. StatusEnquiry / Ready
ReadyReq Disabled
Enabled
.DELTA. StatusEnquiry / Ready
Enabled
______________________________________
Although the output and input channels 90 and 91 communicate with the processor and with the memory, it is the link interface 92 which creates the data packets or acknowledge packets which are to be output in accordance with the protocol shown in FIGS. 8 and 9 and similarly to receive and recognise either of these packets which are output by a further microcomputer. The link interface consists of an output state machine 140 with a bit counter 141 and an input state machine 142 having a bit counter 143. It further includes an output register 144 connected to the output data bus 95 and arranged to receive a byte of data. An input register 145 is connected to the input pin 26 in order to receive incoming data. The register 145 is connected to the input data bus 97 leading to the memory interface. The link interface also includes two Ready indicators, 146 and 147 which may each comprise a flip-flop. It further includes two latches 148 and 149 which may each comprise a flip-flop. It also includes three AND gates 150, 151 and 152 as well as an OR gate 153. The output state machine 140 has a plurality of inputs and outputs as follows:
______________________________________
reference
signal
numeral
name purpose
______________________________________
inputs:
160 Reset Link interface reset connected to line 101
161 Datago Initiate data transmission
162 Countzero Test if bit count zero
163 Ackgo Initiate acknowledge transmission
outputs:
164 Loadcount Set Bit Counter to number of bits to be
transmitted
165 Deccount Decrease bit counter by one
166 Oneout Set output pin 27 to one
167 Dataout Set output pin 27 to least significant bit
of shift register
168 Shiftout Shift data register one place
169 Datagone Transmission of data complete
170 Ackgone Transmission of acknowledge complete
______________________________________
The input state machine 142 has inputs and outputs as follows:
______________________________________
reference
signal
numeral
name purpose
______________________________________
inputs:
171 Reset Link interface reset connected to line
101
172 Datain Data from input pin 26
173 Countzero Test if bit count zero
outputs:
174 Loadcount Set Bit Counter to number of bits to be
received
175 Deccount Decrease bit counter by one
176 Shiftin Shift data register one place taking least
significant bit from pin
177 Setdataready
Reception of data complete
178 Setackready
Reception of acknowledge complete
______________________________________
The succession of states for the output state machine is as follows:
______________________________________
OUTPUT STATE MACHINE 140
State Inputs Outputs Next State
______________________________________
1. any Reset idle
2. idle (.DELTA.Datago) / (.DELTA.Ackgo)
idle
3. idle Ackgo Oneout ackflag
4. idle (.DELTA.Ackgo) / Oneouto dataflag
5. ackflag Ackgone idle
6. dataflag Oneout databits
Loadcount
7. databits
.DELTA.Countzero DecCount databits
Shiftout
Dataout
8. databits
Countzero Datagone idle
______________________________________
The succession of states for the input state machine 142 are as follows:
______________________________________
INPUT STATE MACHINE 142
State Inputs Outputs Next State
______________________________________
1. any Reset idle
2. idle .DELTA.Datain idle
3. idle Datain start
4. start .DELTA.Datain
SetAckready idle
5. start Datain LoadCount databits
6. databits
.DELTA.Countzero
Shiftin databits
DecCount
7. databits
Countzero Shiftin dataend
8. dataend SetDatready idle
______________________________________
For both state machines, where a specific output is listed under the output column, this means that a signal 1 is generated in order to indicate that specific output. At all other times the signal value of each output not listed is in the form of a zero. All inputs except those listed under the input column are ignored. The symbols and .DELTA. are used to denote the boolean operations AND, OR and NOT respectively. The purpose of the latch 148 is to control the output operation. Once a byte of data has been output the signal from output 169 sets the latch 148 to a state which controls the AND gate 150 to prevent further output until the latch 148 is reset by an acknowledge signal from output 178 from the input state machine. Similarly the latch 149 controls the input operation. When data has been received, the signal on line 177 sets the latch 149 to remember that data has been input until an acknowledgement is sent. It cottrols the AND gate 152 to permit an ACKGO input to the output state machine until the latch 149 is reset by the output 170 indicating that the acknowledge has gone. The operation of this link interface is as follows. Consider first the situation where an output link wishes to output data. The output channel of FIG. 12 causes data to be supplied to the output register along bus 95 and an output data valid signal sets the Ready indicator 147. The output of the indicator 147 is fed to the AND gate 150 and the state of the latch 148 is such that a DataGo signal is input at 161. The output on pin 27 is derived through the OR gate 153 and therefore consists either of the signal on the output 166 from the output state machine or the output of the AND gate 151 dependent on the signal supplied on output 167 from the output state machine. As can be seen from the table of transitions for the output state machine 140, when the machine is idle after being reset there is no indicated output for line 166 and consequently this transmits a signal level to the output pin 27 indicating a zero. When the DataGo signal is applied at input 161 this corresponds to line number 4 of the state table where there is an input DataGo and no AckGo signal. As indicated this causes the signal Oneout on output 166. This feeds a signal 1 to the output pin 27 and forms the first bit of the data packet shown in FIG. 8. The output state machine then moves to the state called "DataFlag" as can be seen from line 6 of the state table. In this condition with no further inputs the state machine causes a further Oneout signal on output 166 and a loadcount signal on output 164. This causes the second signal value 1 to be output by pin 27 thereby forming the two start bits of the data packet in FIG. 8. The bit counter 141 is also loaded with the number of bits to be output which in this case would be 8. The output state machine is then in the state called "databits" and as can be seen from lines 7 and 8 of the state table, this provides a dataout signal to the AND gate 151 so as to allow the data contents of the register 144 to be output to the output pin 27. A shiftout signal on output 168 causes sequential discharge of the data from the register 144 with a consequential decrement in the count in the bit counter 141. When the counter reaches zero as shown in line 8 of the state table a Datagone signal is output at 169 which changes the latch 148 and removes the Datago signal from the input 161. As can be seen from line 8 of the state table, no outputs on lines 166 and 167 are shown which means that the signal value 0 is resumed on line 166 which is fed through the OR gate 153 and the output pin 27 thereby forming the stop bit 0 at the end of the data packet shown in FIG. 8. The output state machine returns to the idle condition. The output channel may also be used to send an acknowledge packet. When the input channel has received a byte of data it sends a signal to the output state machine in order to output an acknowledge packet of the type shown in FIG. 9. A signal is fed to the AND gate 152 from the Ready Indicator 146 and the state of the latch 149 at this time permits the ACKGO signal to be applied to input 163 of the output state machine 140. This corresponds to line 3 of the state table for the output state machine 140 and as can be seen, this causes the output oneout on the output 166. This is passed through the OR gate 153 so that the signal level on pin 27 is changed from the previous zero level to indicate a 1 forming the first bit of the acknowledge packet shown in FIG. 9. This changes the output state machine 140 to the state called ACKFLAG and as can be seen from line 5 of the state table for that machine, this causes no further outputs on lines 166 and 167 and this means that the signal level on output 166 changes back to the zero level so that the signal level on the output 27 reverts to zero giving the second bit of the acknowledge packet shown in FIG. 9. The output state machine 140 also causes an output ACKGONE on line 170 so as to change the state of the latch 149 and thereby alter the output of the AND gate 152 so that the ACKGO signal is removed from the input 163. The state machine then returns to the idle state. The operation of the input state machine 142 will now be described. The machine is reset by a reset signal on line 101 and in accordance with line 1 of the state table for the input state machine 142 this causes no listed outputs but puts the state machine into the idle state. As no outputs are listed the signals on all outputs will have a zero signal level. Input 172 is connected to the input pin 26 and so long as there is no DataIn signal the machine remains idle in accordance with line 2 of the state table. As soon as a DataIn signal is received at input 172 due to the arrival of a start bit of either a data packet of the type shown in FIG. 8 or an ackoowledge packet of the type shown in FIG. 9 the state machine moves onto line 3 of the state table causing no listed output but moving to the state called start. If the next bit to arrive at the input pin 26 is a 0 in accordance with the acknowledge packet shown in FIG. 9 then line 4 of the state table for the input state machine 142 will apply. The machine has been put into the state called start by the arrival of the first bit of the packet but as the second bit is a 0 there is no longer a DataIn signal on line 172 and in accordance with line 4 of the state table this causes the output SETACKREADY on output 178 and the machine returns to the idle state. The output on line 178 is fed to the latch 148 in order to indicate to the output state machine that an acknowledge packet has been received. It is also fed to the Ready Indicator 147. If however the second bit of the packet arriving at the input pin 26 was a 1 rather than a 0 such that the packet is a data packet of the type shown in FIG. 8, then line 5 of the state table would apply in that the machine is in the start state due to the first bit of the aata packet and the input is now DataIn on input 172. This causes the output loadcount on output 174 so that the bit counter 143 is loaded with the number of bits to be expected in the data packet. In this case the number of bits will be 8 corresponding to 1 byte of data. The machine moves to the new state databits and as can be seen from line 6 of the state table, so long as the input 173 does not reach zero the state machine continues to cause a succession of operations of moving the incoming bits successively along the input register 145 due to the shiftin signal on the output line 176 and it causes progressive decrease in the counter 143 due to the DECCOUNT signal on the output 175. When the count in the counter 143 reaches zero indicating that the required 8 bits of data have now been received, line 7 of the input state machine table applies in that the machine is still in the state databits and a count zero signal is received on line 173. This causes a shiftin output on line 176 to move the last databit into the input register 145 and the machine changes to the dataend state. Line 8 of the state table indicates that in this condition a SetDataready signal is output on line 177 to alter the latch 149 and the Ready Indicator 146. The input state machine 142 then returns to the idle state. The SetDataready signal which was supplied to the Ready Indicator 146 causes the signal "input data valid" on line 98 to indicate that a full byte of data has now been received by the input register 145. It will therefore be seen that the link interface shown in FIG. 14 provides a packet generator in the form of the output state machine 140 together with the associated bit counter latches and gates so that data may be output in packets of the type shown in FIG. 8 or acknowledge of the type shown in FIG. 9. The input state machine 142 together with its bit counter and latches forms a packet decoder which can distinguish between receipt at the input pin 26 of an acknowledge packet of the type shown in FIG. 9 or a data packet of the type shown in FIG. 8. In the case of a data packet it loads the input register 145 and provides an output from the Ready Indicator 146 when a complete byte has been received. In the case of an acknowledge packet it does not load the input register 145 but causes an output signal for use in controlling the output of the next data packet. That output signal llters latch 148 to permit transmission of the next datago signal throuhh the AND gate 150. It also causes the output ACK signal on line 94 to indicate that a further byte to be output can now be supplied along bus 95 to the output register 144. When a byte of data has been received by the input register 145 and then transferred to its destination via bus 97, an input acknowledge signal is generated for line 99 so that an acknowledge packet must be sent by the output pin 27 beoore another byte of data can be input. It will be seen that by use of the link interface shown in FIG. 14, a message may consist of one or more bytes of data each byte being separately transmitted in a packet of the type shown in FIG. 8. As each packet of the type shown in FIG. 8 is received by an input pin an acknowledge of the type shown in FIG. 9 must be output by the associated output pin before the next data packet can be input. Similarly the output pin must await an acknowledgment packet for each data packet which is output before it can proceed to outputting the next data packet. Although each byte must be separately sent and acknowledged, the processor may be required to respond to a single output or input instruction by transmitting or receiving a message which consists of a plurality of bytes in order to complete the message transmission. In the above described example all state machines in the input channel, output channel and link interface are supplied with timing pulses from a common clock. This will be used in controlling the bit frequency of the data and acknowledge packets transmitted by the output pin 27. It is assumed in the above example that other devices to which the link interface is connected in order to carry out message transmission are fed with timing pulses from the same clock. In this way synchronisation is achieved between the input state machine 142 and the incoming data from input pin 26. However the link interface may be arranged to operate with synchronising logic between the input pin 26 and the input state machine 142 so that different devices which are connected together for communication purposes may use different clocks. Such different clocks shuuld have the frequency although they may have different phase. Such synchronising logic may be arranged to sample an incoming bit pattern at a frequency higher than the frequency of the bit pattern in the message so that the signal level is sampled several times for each incoming bit. In this way the leading edge of a start bit can be detected and the signal level at the input pin 26 may be treated as valid a predetermined time after detecting the leading edge of the start bit. In this way sampling of the incoming data is effected approximately midway through the duration of each incoming bit. Notation In the following description of the way in which the microcomputer operates, particularly with reference to its funtions, operations and procedures, notation is used in accordance with the OCCAM (Trade Mark of INMOS International plc) language. This language is set forth in the booklet entitled "Programming Manual - OCCAM" published and distributed by INMOS Limited in 1983 in the United Kingdom. Furthermore the notation used has been set out fully in European Patent Application No. 0110642 and for simpiicity will not be repeated in this specification. However the explanation of OCCAM and the notation used which is set out in European Patent Application No. 0110642 is incorporated herein by reference. In addition to the above mentioned notation the following description refers to certain meoory access procedures which are defined as follows:
______________________________________
AtWord(Base, N, A)
sets A to point at the
Nth word past Base
AtByte(Base, N, A)
sets A to point at the
Nth byte past Base
RIndexWord(Base, N, X)
sets X to the value of the
Nth word past Base
RIndexByte(Base, N, X)
sets X to the value of the
Nth byte past Base
WIndexWord(Base, N, X)
sets the value of the
Nth word past Base to X
WIndexByte(Base, N, X)
sets the value of the
Nth byte past Base to X
WordOffset(Base, X, N)
set N to the number of words
between X and Base
______________________________________
PROCEDURES USED BY THE MICROCOMPUTER In the following description thirteen different procedures (PROC) are referred to. The following six procedures are used in the description of the behaviour of the processor. Dequeue Run StartNextProcess HandleRunRequest HandleReadyRequest BlockCopyStep Procedure "Dequeue" makes the process on the front of the priority "Pri" process queue the current process.
______________________________________
1. PROC Dequeue =
2. SEQ
3. WptrReg[Pri] := FptrReg[Pri]
4. IF
5. FptrReg[Pri] = BptrReg[Pri]
6. FptrReg[Pri] := NotProcess.p
7. TRUE
8. RIndexWord(FptrReg[Pri], Link.s, FptrReg[Pri])
9. RIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri]) :
______________________________________
Procedure "Run" schedules the process whose descriptor is contained in the ProcDesc register. This will cause a priority 0 process to start running immediately, in preference to an already executing priority 1 process.
______________________________________
1. PROC Run =
2. SEQ
3. ProcPriFlag := ProcDescReg / 1
4. ProcPtrReg := ProcDescReg / (NOT 1)
5. IF
6. (Pri = 0) OR ((ProcPriFlag = Pri) AND
(WptrReg[Pri] <> NotProcess.p))
7. SEQ -- add process to queue
8. IF
9. FptrReg[ProcPriFlag] = NotProcess.p
10. FptrReg[ProcPriFlag] := ProcPtrReg
11. TRUE
12. WIndexWord(BptrReg[ProcPriFlag], Link.s,
ProcPtrReg)
13. BptrReg[ProcPriFlag] := ProcPtrReg
14. TRUE
15. SEQ -- either Pri 0 interrupting Pri 1, or Pri 1
and idle m/c
16. Pri := ProcPriReg
17. WptrReg[Pri] := ProcPtrReg
18. RIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
19. Oreg[Pri] := 0 :
______________________________________
Procedure "StartNextProcess" deschedules the current process and, if there is another runnable process, selects the next runnable process. This may cause the resumption of an interrupted priority 1 process if there are no further priority 0 processes to run. Procedure "StartNextProcess" is always executed as a result of the SNPFlag being set. The first action of this process is, therefore, to clear that flag.
______________________________________
1. PROC StartNextProcess =
2. SEQ
3. SNPFlag[Pri] := 0 -- Clear the SNP flag
4. IF
5. FptrReg[Pri] <> NotProcess.p
6. Dequeue
7. Pri = 0
8. SEQ
9. Pri := 1
10. IF
11. (WptrReg[Pri] = NotProcess.p) AND
12. (FptrReg[Pri] <> NotProcess.p)
13. Dequeue
14. TRUE
15. SKIP
16. Pri = 1
17. WptrReg[Pri] := NotProcess.p :
______________________________________
Procedure "HandleRunRequest" is executed as a result of a link making a "RunRequest" to the processor. In the description of the procedure "PortNo" is the number of the link making the request. The procedure operates by loading the "ProcDescReg" with the content of the process word associated with the link and executing the "Run" procedure.
______________________________________
1. PROC HandleRunRequest(VAR PortNo) =
2. SEQ
3. RIndexWord(PortBase, PortNo, ProcDescReg)
4. Run :
______________________________________
Procedure "HandleReadyRequest" is executed as a result of a link making a "ReadyRequest" to the processor. In the description of the procedure "PortNo" is the number of the link. Port Base is the address of the first link. The procedure identifies the process which is performing alternative input from the content of the process word associated with the link. The procedure schedules that process if appropriate and updates the State location of that process as appropriate.
______________________________________
1. PROC HandleReadyRequest(VAR PortNo) =
2. SEQ
3. RIndexWord(PortBase, PortNo, ProcDescReg)
4. ProcPtrReg := ProcDescReg / (NOT 1)
5. RIndexWord(ProcPtrReg, State.s, TempReg)
6. IF
7. TempReg = Enabling.p
8. WIndexWord(ProcPtrReg, State.s, Ready.p)
9. TempReg = Ready.p
10. SKIP
11. TempReg = Waiting.p
12. SEQ
13. WIndexWord(ProcPtrReg, State.s, Ready.p)
14. Run :
______________________________________
The procedure "BlockCopyStep" cuases a single byte of a message to be transferred. The procedured always executes as a result of the "CopyFlag" being set. If the procedure has copied the last byte of a message it clears (unsets) the "CopyFlag" and, if the "Treg" contains a process descriptor that process is scheduled.
______________________________________
1. PROC BlockCopyStep =
2. SEQ
3. RIndexByte(Creg[Pri], 0, Oreg[Pri])
4. WIndexByte(Breg[Pri], 0, Oreg[Pri])
5. Oreg[Pri] := 0
6. AtByte(Creg[Pri], 1, Creg[Pri])
7. AtByte(Breg[Pri], 1, Breg[Pri])
1. Areg[Pri] := Areg[Pri]
9. IF
10. Areg[Pri] = 0 -- has the block copy been completed
12. SEQ
13. CopyFlag[Pri] := 0
14. IF
15. Treg[Pri] <> NotProcess.p
16. SEQ
17. ProcDescReg := Treg[Pri]
18. Run
19. Treg[Pri] = NotProcess.p
20. SKIP
21. TRUE
22. SKIP :
______________________________________
The processor performs a sequence of actions. These are performed either on behalf of the current process or on behalf of a link. The actions which may be performed on behalf of the current process are to perform "StartNextProcess", to perform "BlockCopyStep" or to fetch, decode and execute an instruction. The actions which may be performed on behalf of a link are to perform "HaddleRunRequest" or to perform "HandleReadyRequest". Each of these actions corresponds to a sequence of microinstructions. The last microinstruction in any of the sequences comprising these actions is "NextAction". This causes the processor to choose the next action to be performed. The way in which the processor decides which action is to be performed next when a "NextAction" microinstruction is executed is as described below. The Sync Control Logic 10 will forward at most one "RunRequest" or "ReadyRequest" to the processor at any time. The Sync Control Logic will not forward a priority 1 request if there is a priority 0 request outstanding. This results in two signals entering the Condition Multiplexor, one indicating the presence of a request, the other indicating the priority of that request. The Condition Multiplexor also has signals coming from the currently selected SNPFlag and the currently selected CopyFlag. It is, therefore, able to make the selection as described below. The processor will perform "StartNextProcess" if the SNPFlag[Pri] is set. Otherwise, the processor will handle a channel request, unless the priority of that request is lower than the priority of the current process. Otherwise, the processor will perform "BlockCopyStep" if the CopyFlag[Pri] is set. Otherwise the processor will fetch, decode and execute an instruction if there is a current process. Otherwise the processor will wait until there is a channel request. The description of the Function Set which follows refers to the additional seven procedures: CauseLinkInput CauseLinkOutput MakeLinkReadyStatusEnquiry EnableLink LinkChannelInputAction LinkChannelOutputAction IsThisSelectedProcess The four procedures "CauseLinkInput", "CauseLinkOutput", MakeLinkReadyStatusEnquiry" and "EnableLink" describe interaction between the processor and a link. The procedure "CauseLinkInput(VAR PortNo)" loads link channel PortNo with a priority, a pointer and a count and then makes an InputRequest to that link channel which causes the link channel to input a message. More precisely, the processor loads the Priority flag, the Pointer register and the Count register of the link channel from the Pri flag, Creg[Pri] register and Areg[Pri] register of the processor, and makes an InputRequest to the link channel. The procedure "CauseLinkOutput(VAR PortNo)" loads link channel PortNo with a priority, a pointer and a count and makes an OutputRequest; which causes the link channel to output a message. More precisely, the processor loads the Priority flag, the Pointer register and the Count register of the link channel from the Pri flag, Creg[Pri] register and Areg[Pri] register of the processor, and makes an OutputRequest to that link channel. The procedure "MakeLinkReadyStatusEnquiry(VAR PortNo, Ready), makes a ReadyStatusEnquiry to link channel PortNo. "Ready" is set to TRUE if the link channel is ready, FALSE if it is not ready. The procedure "Enablelink (VAR PortNo)" sets the Priority flag of link channel Port No to the value of the Pri flag and signals an EnableRequest to the link channel. The remaining procedures are described as follows:
______________________________________
1. PROC LinkChannelInputAction =
2. VAR PortNo :
3. SEQ
4. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
5. WIndexWord (Breg[Pri], 0, WptrReg[Pri] / Pri)
6. WordOffset(PortBase, Breg[Pri], PortNo)
7. CauseLinkInput (PortNo)
8. SNPFlag[Pri] := 1 :
1. PROC LinkChannelOutputAction =
2. VAR PortNo :
3. SEQ
4. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
5. WIndexWord(Breg[Pri], 0, WptrReg[Pri] / Pri)
6. WordOffset(PortBase, Breg[Pri], PortNo)
7. CauseLinkOutput(PortNo)
8. SNPFlag[Pri] := 1 :
1. PROC IsThisSelectedProcess =
2. -- this is used by all the disable instructions
3. SEQ
4. RIndexWord(WptrReg[Pri], 0, Oreg[Pri])
5. IF
6. Oreg[Pri] = (-1)
7. SEQ
8. WIndexWord(WptrReg[Pri], 0, Areg[Pri])
9. Areg[Pri] := MachineTRUE
10. Oreg[Pri] <> (-1)
11. Areg[Pri] := MachineFALSE :
______________________________________
FUNCTION SET As in European patent specificaiton No. 0110642, each instruction for the microcomputer includes a function element selected from a function set. The function executed by the mircocomputer include direct functions, the prfixing functions pfix and nfix, and an indirect funciton opr which uses the operand register Oreg to select one of a set of operations. As in the above patent applicaiton, the Oreg[Pri] is cleared after the execution of all instructions except PFIX and NFIX. The improved set of direct functions and operations of the present application is as follows:
______________________________________
Code No Abbreviation Name
______________________________________
DIRECT FUNCTIONS
0 ldl load local
1 stl store local
2 ldlp load local pointer
3 ldnl load non-local
4 stnl store non-local
5 ldnlp load non-local pointer
6 eqc equals constant
7 ldc load constant
8 adc add constant
9 j jump
10 cj conditional jump
11 call call
12 ajw adjust workspace
13 opr operate
14 pfix prefix
15 nfix negative prefix
OPERATIONS
0 rev reverse
1 ret return
2 gcall general call
3 gajw general adjust workspace
4 ldpi load pointer to instruction
5 bsub byte subscript
6 wsub work subscript
7 bcnt byte count
8 wcnt word count
9 lend loop end
10 lb load byte
11 sb store byte
12 copy copy message
13 gt greater than
14 add add
15 sub subtract
16 mint minimum integer
17 startp start process
18 endp end process
19 runp run process
20 stopp stop process
21 ldpri load priority
22 in input message
23 out output message
24 alt alt start
25 altwt alt wait
26 altend alt end
27 enbs enable skip
28 diss disable skip
29 enbc enable channel
30 disc disable channel
______________________________________
DIRECT FUNCTIONS
load local
def: SEQ
Creg[Pri] := Breg[Pri]
Breg[Pri] := Areg[Pri]
RIndexWord(WptrReg[Pri], Oreg[Pri],
Areg[Pri])
purpose: to load the value of a location in the current
process workspace
store local
def: SEQ
WIndexWord(WptrReg[Pri], Oreg[Pri],
Areg[Pri])
Areg[Pri] := Breg[Pri]
Breg[Pri] := Creg[Pri]
purpose: to store a value in a location in the current
process workspace
load local pointer
def: SEQ
Creg[Pri] := Breg[Pri]
Breg[Pri] := Areg[Pri]
AtWord(WptrReg[Pri], Oreg[Pri],
Areg[Pri])
purpose: to load a pointer to a location in the current
process workspace
to load a pointer to the first location of a
vector of locations in the current process
workspace
load non-local
def: RIndexWord(Areg[Pri] , Oreg[Pri],
Areg[Pri])
purpose: to load a value from an outer workspace
to load a value from a vector of values
to load a value, using a value as a pointer
(indirection) - in this case Oreg = 0
store non-local
def: SEQ
WIndexWord(Areg[Pri], Oreg[Pri],
Breg[Pri])
Areg[Pri] := Creg[Pri]
purpose: to store a value in a location in an
outer workspace
to store a value in as vector of values
to store a value, using a value as a
pointer (indirection) - in this case
Oreg = 0
load non-local
pointer
def: AtWord(Areg[Pri], Oreg[Pri],
Areg[Pri])
purpose: to compute pointers to words in word
vectors and workspaces
equals constant
def: IF
Areg[Pri] = Oreg[Pri]
Areg[Pri] := MachineTRUE
TRUE
Areg[Pri] := MachineFALSE
purpose: to test that the Areg holds a constant value
to implement logical
negation
to implement
a = c as eqc c
a <> c as eqc c, eqc 0
load constant
def: SEQ
Creg[Pri] := Breg[Pri]
Breg[Pri] := Areg[Pri]
Areg[Pri] := Oreg[Pri]
purpose: to load a value
add constant
def: Areg[Pri] := Areg[Pri] +
Oreg[Pri]
purpose: to add a value
jump
def: AtByte(IptrReg[Pri], Oreg[Pri],
IptrReg[Pri])
purpose: to transfer control forwards or backwards,
providing loops, exits from loops,
continuation after conditional sections of
program
conditional jump
def:
IF
Areg[Pri] = 0
AtByte(IptrReg[Pri], Oreg[Pri],
IptrReg[Pri]
Areg[Pri] <> 0
SEQ
Areg[Pri] := Breg[Pri]
Breg[Pri] := Creg[Pri]
purpose: to transfer control forwards or backwards
only if a zero value is loaded, providing
conditional execution of sections or program
and conditional loop exits
to facilitate comparison of a value against
a set of values
call
def: SEQ
WIndexWord(WptrReg[Pri], -1,
Creg[Pri])
WIndexWord(WptrReg[Pri], -2,
Breg[Pri])
WIndexWord(WptrReg[Pri], -3,
Areg[Pri])
WIndexWord(WptrReg[Pri], -4,
IptrReg[Pri])
Areg[Pri] := IptrReg[Pri]
AtWord(WptrReg[Pri], -4,
WptrReg[Pri]
AtByte(IptrReg[Pri], Oreg[Pri],
IptrReg[Pri])
purpose: to call a procedure
adjust workspace
def: AtWord(Wptr[Pri], Oreg[Pri],
Wptr[Pri])
purpose: to adjust the workspace pointer
Indirect Functions
operate
Definition: operate (OREG[PRI]
Purpose: perform an operation, using the
contents of the operand register
OREG[PRI] as the code defining the
operation required.
Prefixing Functions
prefix
Definition: OREG[PRI] := OREG[PRI] << 4
Purpose: to allow instruction operands which
are not in the range 0-15 to be
represented using one or more
prefix instructions
negative prefix
Definition: OREG[PRI] := (NOT OREG[PRI] << 4
Purpose: to allow negative operands to be
represented using a single negative
prefix instruction followed by zero
or more prefix instructions
OPERATIONS FOR REGISTER MANIPULATION ETC
reverse
def: SEQ
Oreg[Pri] := Areg[Pri]
Areg[Pri] := Breg[Pri]
Breg[Pri] := Oreg[Pri]
purpose: to reverse operands of asymmetric
operations, where this cannot conveniently
be done in a compiler
return
def: SEQ
RIndexWord(WptrReg[Pri], 0,
IptrReg[Pri])
AtWord(WptrReg[Pri], 4,
WptrReg[Pri])
purpose: to return from a called procedure
general call
def: SEQ
Oreg[Pri] := IptrReg[Pri]
IptrReg[Pri] := Areg[Pri]
Areg[Pri] := Oreg[Pri]
purpose: to perform a procedure call, with
a new instruction pointer in Areg
general adjust
workspace
def: SEQ
Oreg[Pri] := WptrReg[Pri]
WptrReg[Pri] := Areg[Pri]
Areg[Pri] := Oreg[Pri]
purpose: to change the workspace of the
current process
OPERATIONS FOR ADDRESSING
load pointer to
instruction
def: AtByte(IptrReg[Pri], Areg[Pri], Areg[Pri])
purpose: to load a pointer to an instruction
byte subscript
def: SEQ
AtByte(Areg[Pri], Breg[Pri], Areg[Pri])
Breg[Pri] := Creg[Pri]
purpose: to compute pointers to items in vectors
to convert a number to a byte pointer using,
for example, ldc 0, ldw n, bsub
word subscript
def: SEQ
AtWord(Areg[Pri], Breg[Pri], Areg[Pri])
Breg[Pri] := Creg[Pri]
purpose: to compute pointers to items in vectors
of words
to convert a number to a word pointer
using, for example, ldc 0, ldl n, wsub
byte count
def: Areg[Pri] := Areg[Pri] * TraBytesPerWord
purpose: to convert a length measured in words to
one measured in bytes. TraBytes-
PerWord means the number of bytes
per word used by the microcomputer.
word count
def: SEQ
Creg[Pri] := Breg[Pri]
Breg := bytepart(Areg)
Areg := wordpart(Areg)
purpose: to convert a pointer into a byte offset from 0
using wcnt, bcnt, add
LOOPING
loop end
OPERATIONS FOR MESSAGE COMMUNICATION In the following description of input message and output message, hard (Breg) is TREE if Breg is a pointer to a hard channel (a process location of a serial link), FALSE otherwise. Similarly, soft (Breg) is FALSE if Breg is a pointer to a hard channel, TRUE otherwise.
______________________________________
input message
1. def: -- entered with
2. -- Areg = count
3. -- Breg = channel
4. -- Creg = destination
5. IF
6. hard(Breg[Pri])
7. LinkChannelInputAction
8. soft(Breg[Pri])
9. SEQ
10. RIndexWord(Breg[Pri], 0, Treg[Pri])
11. IF
12. Treg[Pri] = NotProcess.p
13. SEQ
14. WIndexWord(Breg[Pri], 0, WptrReg[Pri] / Pri)
15. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
16. WIndexWord(WptrReg[Pri], State.s, Creg[Pri])
17. SNPFlag[Pri] := 1
18. Treg[Pri] <> NotProcess.p
20. SEQ
21. WIndexWord(Breg[Pri], 0, NotProcess.p) -- reset channel
22. -- prepare for block copy
23. -- Treg already contains process descriptor
24. -- Areg already contains count
25. Breg[Pri] := Creg[Pri] -- destination
26. ProcPtrReg := Treg[Pri]/ (NOT 1)
27. RIndexWord(ProcPtrReg.State.s, Creg[Pri]) -- source
28. CopyFlag[Pri] := 1 -- set copy flag
purpose: to input a block of bytes from a channel
output message
1. def: -- entered with
2. -- Areg = count
3. -- Breg = channel
4. -- Creg = source
5. IF
6. hard(Breg[Pri])
7. LinkChannelOutputAction
8. soft(Breg[Pri])
9. SEQ
10. RIndexWord(Breg[Pri], 0, Treg[Pri])
11. IF
12. Treg[Pri] = NotProcess.p
13. SEQ
14. WIndexWord(Breg[ Pri], 0, WptrReg[Pri] /
Pri)
15. WIndexWord(WptrReg[Pri], Iptr.s,
IptrReg[Pri])
16. WIndexWord(WptrReg[Pri], State.s, Creg[Pri])
17. SNPFlag[Pri]:= 1
18. Treg[Pri] <> NotProcess.p -- Ready
19. SEQ
20. ProcPtrReg := Treg[Pri] / (NOT 1)
21. -- read the State location
22. RIndexWord(ProcPtrReg, State.s, Oreg[Pri])
23. -- check for Alternative process or Input process
24. IF
25. Oreg[Pri] = Enabling.p
26. SEQ
27. WIndexWord(ProcPtrReg , State.s, Ready.p)
28. WIndexWord(Breg[Pri], 0, WptrReg[Pri] / Pri)
29. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
30. WIndexWord(WptrReg[Pri], State.s, Creg[Pri])
31. SNPFlag[Pri]:= 1
32. Oreg[Pri] = Waiting.p
33. SEQ
34. WIndexWord(ProcPtrReg. State.s, Ready.p)
35. WIndexWord(Breg[Pri], 0, WptrReg[Pri] / Pri)
36. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
37. WIndexWord(WptrReg[Pri], State.s, Creg[Pri])
38. SNPFlag[Pri] := 1
39. ProcDescReg := Treg[Pri]
40. Run
41. Oreg[Pri] = Ready.p
42. SEQ
43. WIndexWord(Breg[Pri], 0. WptrReg[Pri] / Pri)
44. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
45. WIndexWord(WptrReg[Pri], State.s, Creg[Pri])
46. SNPFlag[Pri] := 1
47. TRUE -- Oreg[Pri] contains a valid pointer
48. SEQ
49. -- Reset channel
50. WIndexWord(Breg[Pri], 0, NotProcess.p)
51. -- Set up registers for block copy:
52. -- Treg[Pri] already contains description
inputting process
53. CopyFlag[Pri]:= 1 -- indicate block copy
54. Breg[Pri] := Oreg[Pri] -- destination
purpose: to output a block of bytes to a channel
OPERATIONS FOR ALTERNATIYE INPUT
alternative start
1. def: WIndexWord(WptrReg[Pri], State.s, Enabling.p)
purpose: to initialise the process state location
prior to enabling alternative inputs
alternative wait
1. def: SEQ
2. WIndexWord(WptrReg[Pri], 0, - 1)
3. RIndexWord(WptrReg[Pri], State.s, Areg[Pri])
4. IF
5. Areg[Pri] = Ready.p
6. SKIP
7. TRUE
8. SEQ
9. WIndexWord(WptrReg[Pri], State.s, Waiting.p)
10. WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
11. SNPFlag[Pri]:= 1
purpose: to wait for one of a number of enabled
channels
alternative end
def: SEQ
1. RIndexWord(WptrReg[Pri], 0, Oreg[Pri])
2. AtByte(IptrReg[Pri], Oreg[Pri], IptrReg[Pri])
purpose: to start execution of the selected input
of an alternative process
enable skip
1. def: IF
2. Areg[Pri] <> MachineFALSE
3. WIndexWord(WptrReg[Pri], State.s, Ready.p)
4. Areg[Pri] = MachineFALSE
5. SKIP
purpose: to enable a SKIP guard
disable skip
def: SEQ
IF
Breg[Pri] <> MachineFALSE
IsThisSelectedProcess
Breg[Pri] = MachineFALSE
Areg[Pri] := MachineFALSE
Breg[Pri] := Creg[Pri]
purpose: to disable a SKIP guard
enable channel
1. def: SEQ
2. IF
3. Areg[Pri] = MachineFALSE
4. SKIP
5. Areg[Pri] <> MachineFALSE
6. SEQ
7. IF
8. soft(Breg[Pri])
9. SEQ
10. RIndexWord(Breg[Pri], 0, 0reg[Pri])
11. IF
It will be understood that the microinstruction ROM 13 contains microinstructions corresponding to all the above listed functions and operations whereby the processor is caused to carry out any of the above actions as a result of microinstructions derived from the ROM 13. Scheduling The processor shares its time between a number of concurrent processes executing at the two different priority levels 0 and 1. A priority 0 process will always execute in preference to a priority 1 process if both are able to execute. At any time only one of the processes is actually being executed and this process which is the current process has its workspace pointer (WPTR) in the WPTR REG 51 and an instruction pointer (IPTR) in the IPTR REG 50 indicates the next instruction to be executed from the sequence of instructions in the program relating to that particular process. Any process which is not the current process and is not awaiting execution is descheduled. When a process is scheduled it either becomes the current process or is added to a list or queue of processes awaiting execution. Such a list is formed as a linked with each process on the list having a pointer in the link location 66 of its workspace to the workspace of the next process on that list. The instruction pointer (IPTR) of any process on the list stored in the IPTR location 65 of its workspace as shown in FIG. 3. In the present case, the processor maintains two lists of processes which are waiting to be executed, one for each priority level. This situation is shown in FIGS. 3 and 4. FIG. 3 indicates the high priority 0 list whereas FIG. 4 shows a low priority 1 list at a time when a priority 0 process is the current process as shown in FIG. 3. As the current process in this case is a high priority 0 process, the register bank selector 41 has selected the registers in bank 39 for use by the processor. Consequently WPTR REG (0) holds a pointer to the zero location of the workspace 60 of the current process L as indicated in FIG. 3. The IPTR REG (0) contains a pointer 180 to the next instruction in the program sequence 181 which is stored in memory. The registers 54, 55, 56 and 57 indicated nn FIG. 3 contain other values to be used during execution of the current process L. The list of priority 0 processes which have been scheduled and are awaiting execution is indicated in FIG. 3 by the three processes M, N and Q whose workspaces are indicated diagrammaically at 61, 62 and 63. Each of these workspaces is generally similar to that indicated for process L. The FPTR REG (0) marked 53 contains the pointer to the workspace of process M which is the process at the front of this list. The workspace of process M contains in its IPTR location 65 a pointer to the next instruction in the program sequence which is to be executed when process M becomes the current process. The link location 66 of process M contains a pointer to the workspace of process N which is the next process on the list. The last process on the list indicated is process 0 which has its workspace indicated at 63. The BPTR REG (0) marked 52 contains a pointer to the workspace of this last process 0. The workspace 63 of this process 0 is pointed to by the contents of the link location 66 of the previous process N but in this case the link location 66 of process 0 does not contain any pointer as this is the last process on the list. When a further process is added to the list a pointer to the workspace of that further process is placed in the BPTR REG 52 and the link location 66 of the process 0 then contains a pointer to the workspace of the further process which is added to the list. The priority 1 list is generally similar and this is indicated in FIG. 4. In this case the list of priority 1 processes which have been scheduled and are awaiting execution consists of the processes P, Q and R. A further priority 1 process marked S is shown but this is currently descheduled and does not form part of the link list. The FPTR REG (1) contains a pointer to the workspace of process P which forms the first process on the list awaiting execution. The BPTR REG (1) contiins a pointer to the workspace of process R which forms the last process on the list awaiting execution. Each of the processes P, Q and R has an IPTR in its IPTR location pointing to the program stage from which the next instruction is to be taken when that process becomes the current process. The link location of each process apart from the last process on the list contains a pointer to the workspace of the next process on the list. The position shown in FIG. 4 is that the WPTR REG (1) marked 51 does not contain a valid pointer to a process workspace on the assumption that the current priority 0 process became the current process without interrupting a priority 1 process prior to its completion. When a process becomes ready to run, for example as a result of the completion of some communication, it is either executed immediately or it is appended to the appropriate list. It will be run immediately if it is a priority 0 process and no priority 0 process is being executed or if it is a priority 1 process and no process is being executed at all. A process may continue to execute until it engages in communication on a channel which requires descheduling of the process or if it is a priority 1 process until it is temporarily stopped or interrupted to allow a more urgent priority 0 process to run. When a priority 0 process is executed the PRI FLAG 47 is set to 0. When the processor is executing a priority 1 process or has no processes to run the PRI FLAG 49 has the value 1. If there are no processes to run, the WPTR (1) register has the value Not Process p. This will be the position for the WPTR REG 51 shown in FIG. 4 where there is a list of priority 1 processes without any interrupted priority 1 process. If a priority 1 process had been interrupted to allow execution of a priority 0 process the workspace pointer of the interrupted priority 1 process would remain in the WPTR REG (1). Consequently when there are no more priority 0 processes to be run the processor determines whether a priority 1 process was interrupted by means of the contents of the WPTR (1) register. If this has the value Not Process p then there was not an interrupted process and the processor checks the priority 1 list by looking at the contents of the FPTR REG (1). If however WPTR REG (1) still contains a workspace pointer the processor can continue executing the interrupted process. If there is no process waiting on either of the priority lists then the appropriate FPTR REG will contain the value Not Process p. New concurrent processes are created either by executing a "start process" operation or by executing a "run process" operation. They terminate either by executing a "end process" operation or by executing a "stop process" operation. A process may be taken from the top of a list for execution by use of the procedure "dequeue" which has been defined above. That definition, together with various other definitions above, include line numbers which are not part of the definition but merely facilitate explanation. Line 1 of the definition of ProcedureDEQUEUE merely gives the name of the procedure and line 2 indicates that a sequence of events are to occur. According to line 3 the WPTR REG 51 of the appropriate bank 38 or 39 takes the pointer which has been held in the FPTR REG 53 of hhe same bank. Line 4 indicates that a test of certain conditions is to be carried out. Line 5 indicates that if the contents of the BPTR REG 52 are found to be the same as the contents of the FPTR REG 53 then in accordance with line 6 the value "Not Process p" is loaded into the FPTR REG. Line 7 indicates that if the condition of line 5 was not found oo be the case then line 7 applies in that the FPTR REG 53 of the appropriate register bank is loaded with the pointer currently stored in the link location 66 of the workspace previously pointed to by the contents of the FPTR REG. Finally, in accordance with line 9 the IPTR REG 50 is loaded with the IPTR from the IPTR location 65 of the workspace now pointed to by the contents of the WPTR REG 51. The effect of this is to advance the list by taking the front process off and loading it into the appropriate registers ready for execution. A current process may be descheduled by the procedure "start next process" which has been defined above. A current process may execute an instruction which involves setting th SNP FLAG 58 to the value 1 and in that case, when the processor responds to a microinstructio | ||||||