System for executing, scheduling, and selectively linking time dependent processes based upon scheduling time thereof

Abstract

A microcomputer has a processor arranged to share its time between a plurality of concurrent processes. Each process may have means (69) for indicating a time when the process may be executed. The processes may form a linked list of processes (T, U. V) awaiting scheduling for execution. A location (90) is provided for indicating the beginning of a timer list of processes awaiting execution and means (68) is provided for indicating the end of a timer list. The microcomputer may provide more than one timer list of processes of different priority. Each process may include a number of alternative components one or more of which is time dependent.

Claims

We claim:

1. A microcomputer comprising memory and a processor configured to execute a plurality of concurrent processes by said processor in accordance with a plurality of program steps, at least some of said processes being time dependent, the microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating a process which is being executed by said processor, said process being referred to as the current process;

(ii) a timer list coupled to said storage element for identifying one or more processes which form a time-ordered collection awaiting execution by said processor after respective scheduling times for the processes in said collection;

(iii) a set of storage locations associated with said timer list for indicating scheduling times when the processes in said collection become ready for execution;

(iv) a control system coupled to said timer list and to said processor to cause said processor to add a further process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by said processor, including timing logic responsive to said next process indicator to make said next process the current process for execution after its scheduling time occurs.

(vi) a program stage indicator for each concurrent process; said processor including timing logic responsive to said next process indicator to make said next process the current process for execution after its scheduling time occurs; and

message transmission means for effecting synchronized message transmission between concurrent processes, said message transmission means comprising a plurality of communication channels, a storage apparatus for storing a status indicator to indicate the status of data communication through each channel, and synchronizing means responsive to said status indicator to stop executing a current process or add a process to a collection awaiting execution so that communication between two communicating processes is completed when the two processes are at corresponding program steps.

2. A microcomputer comprising memory, a timer and a processor coupled to read from and write into said memory, said processor being configured to execute a plurality of concurrent processes in accordance with a plurality of program steps, at least some of said processes being time dependent said time dependent process including a time-related instruction including a time value relative to said timer:

(a) the microcomputer including a scheduling system comprising (i) a time-ordered linked list of processes awaiting execution by the processor after a scheduling time for each process in said list, (ii) a set of storage locations associated with said linked list for indicating a scheduling time when the processes in said list becomes ready for execution, and (iii) an addressable storage element for indicating the process which is currently being executed by the processor, said process being referred to as the current process, (iv) a control system coupled to said time-ordered linked list for adding a further process thereto at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time, (v) a next process indicator to indicate the next process on said time-ordered list, and (vi) a program stage indicator for each concurrent process; and

(b) said memory providing for each process a respective workspace having a plurality of addressable locations, each of said work spaces for a process on said time-ordered list including (i) first memory locations for recording variables associated with the corresponding process, (ii) a second memory location for said program stage indicator for the corresponding process, (iii) a third memory location for indicating the next process on said time-ordered linked list;

whereby when said processor executes a time-related instruction, said processor compares said time-related instruction to the time indicated by said timer, and, in response to said time-related instruction having arrived in said timer, continuing execution of said current process; in response to said time value in said time related instruction having not yet arrived, stopping execution of said current process and causing said control to add said current process to said collection.

3. A microcomputer comprising memory and a processor coupled to read from and write into said memory, said processor being configured to execute a plurality of concurrent processes in accordance with a plurality of program steps, at least some of said processes being time dependent:

(a) the microcomputer including a scheduling system comprising (i) a time ordered linked list of processor after a scheduling time for each process in said list, (ii) a set of storage locations associated with said linked list for indicating a scheduling time when the processes in said list becomes ready for execution, and (iii) an addressable storage element for indicating the process which is currently being executed by the processor, said process being referred to as the current process, (iv) a control system coupled to said time-ordered linked list for adding a further process thereto at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time, (v) a next process indicator to indicate the next process on said time-ordered list, and (vi) a program stage indicator for each of said concurrent processes;

(b) said memory providing for each process a respective workspace having a plurality of addressable locations, each of said work space for a process on said time-ordered lists including (i) first memory locations for recording variables associated with the corresponding process, (ii) a second memory location for said program stage indicator for the corresponding process, (iii) a third memory location for indicating the next process on said time ordered linked list; and

(c) the microcomputer further including message transmission means for effecting synchronized message transmission between concurrent processes, said message transmission means comprising a plurality of communication channels, a status indicator for indicating the status of data communication through each channel, and synchronizing means responsive to the status indicator to a current process or add a process to a collection awaiting execution so that communication between two communicating processes is completed when the two processes are at corresponding program steps.

4. A network of directly interconnected microcomputers each comprising a timer and a single integrated circuit microcomputer comprising memory and a processor arranged to execute a plurality of concurrent processes in accordance with a plurality of program steps, said program steps comprising a plurality of instructions for sequential execution by the processor, some of said plurality of instructions being time related, said time related instructions including a time value relative to said timer, each said microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating the process which is being executed by the processor, said process being referred to as the current process;

(ii) a timer list for identifying one or more processes which form a time-ordered collection awaiting execution by the processor after respective scheduling times for each process in said collection;

(iii) a set of storage locations associated with said timer list for storing data to indicate respective scheduling times when the processes in said collection becomes ready for execution;

(iv) a control system coupled to said timer list for adding a further process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by the processor; and

(vi) a program stage indicator for each concurrent process;

said processor further including a logic circuit responsive to said next process indicator to make the next process in said collection the current process for execution after its scheduling time occurs; whereby when said processor executes a time-related instruction, said processor compares said time-related instruction to the time indicated by said timer, and, in response to said time-related instruction having arrived in said timer, continuing execution of said current process; in response to said time value in said time related instruction having not yet arrived, stopping execution of the current process and causing said control to add said current process to said collection.

5. A network of directly interconnected microcomputers each comprising a single integrated circuit microcomputer comprising memory and a processor arranged to execute a plurality of concurrent processes in accordance with a plurality of program steps, said program steps comprising a plurality of instructions for sequential execution by the processor, each said microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating the process which is being executed by the processor, said process being referred to as the current process;

(ii) a timer list for identifying one or more processes which form a time-ordered collection awaiting execution by the processor after respective scheduling times for each process in said collection;

(iii) a set of storage locations associated with said timer list for storing data to indicate respective scheduling times when the processes in said collection becomes ready for execution;

(iv) a control system coupled to said timer list for adding a further process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by the processor; and

(vi) a program stage indicator for each concurrent process, said processor further including a logic circuit responsive to said next process indicator to make the next process in said collection the current process for execution after its scheduling time occurs; and

said microcomputer further including message transmission means for effecting synchronized message transmission between concurrent processes, said message transmission means comprising a plurality of communication channels, a storage apparatus for storing a status indicator for indicating the status of data communication through each channel, and synchronizing means responsive to said status indicator to stop a current process or add a process to a collection awaiting execution so that communication between two communicating processes is completed when the two processes are at corresponding program steps.

6. A method of operating concurrent processes, at least some of which are time dependent processes, in a computer system wherein each concurrent process executes a program having a plurality of instructions, comprising the steps of:

forming a first pointer for each process to identify the process;

forming a second pointer for each process to indicate a program stage for the process;

scheduling a plurality of processes for execution by one processor including

providing an indication of a process which is being executed by said one processor, said process being referred to as the current process;

identifying a time-ordered collection of processes each having a respective scheduling time when the process may be executed by said one processor; and

providing an indication of said scheduling time for each process in the time-ordered collection, the process in said collection having the earliest scheduling time being indicated as the next process;

wherein execution of said current process comprises executing a sequence of instructions including a time related instruction indicating a scheduling time before which the current process is not to continue execution and responding to execution of said time related instruction by (a) determining whether said scheduling time has yet arrived, (b) in response to determining that the scheduling time has arrived, then continuing execution of the said process, and (c) in response to determining that the scheduling time has not yet arrived, (i) storing said second pointer for the process, (ii) stopping execution of the said current process, (iii) causing the said one processor which executed said time related instruction to add the stopped process to said time-ordered collection at a position in the time-ordered collection such that its scheduling time forms an ordered sequence of scheduling times in the collection, and (iv) setting the indication of the current process to indicate a further scheduled process;

at a time after the scheduling time of said next process, responding to execution of an instruction stopping the current process by setting the indication of the current process to indicate the said next process and executing said next process at a program stage indicated by the second pointer for the said next process; and

transmitting messages between concurrent processes through a plurality of addressable communication channels to permit data communication between processes, wherein each process executes a sequence of instructions in a program including communication instructions arranged to complete message transmission between two processes when both are at corresponding program stages.

7. A method according to claim 6 comprising operating concurrent processes in a computer system comprising a network of interconnected integrated circuit devices and wherein said step of transmitting messages between concurrent processes is effected by addressing communication channels of a first type to permit data communication between two processes both on the same integrated circuit device and addressing channels of a second type to permit data communication between processes wherein one process is on one said integrated circuit device and the other process is on another integrated circuit device.

8. A method of operating concurrent processes, at least some of which are time dependent processes, in a computer system wherein each concurrent process executes a program having a plurality of instructions, comprising the steps of:

forming a first pointer for each process to identify the process;

forming a second pointer for each process to indicate a program stage for the process;

scheduling a plurality of processes for execution by one processor including

providing an indication of a process which is being executed by said one processor, said process being referred to as the current process;

identifying a time-ordered collection of processes each having a respective scheduling time when the process may be executed by said one processor; and

providing an indication of said scheduling time for each process in the time-ordered collection, the process in said collection having the earliest scheduling time being indicated as the next process;

wherein execution of said current process comprises executing a sequence of instructions including a time related instruction indicating a scheduling time before which the current process is not to continue execution and responding to execution of said time related instruction by (a) determining whether said scheduling time has yet arrived, (b) in response to determining that the scheduling time has arrived, continuing execution of the said current process, and (c) in response to determining that the scheduling time has not yet arrived, then (i) storing said second pointer for the said current process, (ii) stopping execution of the said current process, (iii) causing the said one processor which executed said time related instructing to add the stopped process to said time-ordered collection at a position in the time-ordered collection such that its scheduling time forms an ordered sequence of scheduling times in the collection, and (iv) setting the indication of the current process to indicate a further scheduled process;

at a time after the scheduling time of said next process, responding to execution of an instruction stopping the current process by setting the indication of the current process to indicate the said next process and executing said next process at a program stage indicated by the second pointer for the said next process; and

executing a process having a plurality of alternative time related components, indicating a time associated with each component, and determining whether the time associated with any of the components has yet occurred.

9. A method according to claim 8 further comprising descheduling the process there defined if the earliest time associated with any of said alternative time related components has not yet occurred and adding said process to said time-ordered collection.

10. A method according to claim 8 further comprising loading into a memory location for the current process a special value indicating the state of the process and indicating that the process is one with alternative components.

11. A method according to claim 10 further comprising loading into said memory location a first special value to indicate that at least one of the alternative components is ready and the process is to remain scheduled, and loading a second special value into said memory location to indicate that the process is descheduled while awaiting arrival of the time associated with one of the alternative components.

12. A method according to claim 8 further comprising loading into a memory location associated with the current process a special value to indicate that none of the alternative components has yet been selected and responding to said special value in order to select one of the alternative process components when the process is scheduled.

13. A method according to claim 8 wherein said process includes a plurality of alternative components at least some of which are time related, and wherein at least one of said alternative components comprises inputting a message through a communication channel, said method including determining whether the earliest time of any time related component has yet occurred and determining whether any communication channel is ready to input a message.

14. A method of operating concurrent processes, at least some of which are time dependent processes, in a computer system wherein each concurrent process executes a program having a plurality of instructions, comprising the steps of:

forming a first pointer for each process to identify the process;

forming a second pointer for each process to indicate a program stage for the process;

scheduling a plurality of processes for execution by one processor including providing an indication of a process which is being executed by said one processor, said process being referred to as the current process;

identifying a time-ordered collection of processes each having a respective scheduling time when the process may be executed by said one processor; and

providing an indication of said scheduling time for each process in the time-ordered collection, the process in said collection having the earliest scheduling time being indicated as the next process;

wherein execution of said current process comprises executing a sequence of instructions including a time related instruction indicating a scheduling time before which the current process is not to continue execution and responding to execution of said time related instruction by (a) determining whether said scheduling time has yet arrived, (b) in response to determining that the scheduling time has arrived, continuing execution of the said process and (c) in response to determining that the scheduling time has not yet arrived, (i) storing said second pointer for the said current process, (ii) stopping execution of the said current process, (iii) causing the said one processor which executed said time related instruction to add the stopped process to said time-ordered collection at a position in the time-ordered collection such that its scheduling time forms an ordered sequence of scheduling times in the collection, and (iv) setting the indication of the current process to indicate a further scheduled process, and at a time after the scheduling time of said next process, responding to execution of an instruction stopping the current process by setting the indication of the current process to indicate the said next process and executing said next process at a program stage indicated by the second pointer for the said next process; and

specifying a time duration for the execution of a current process, responding to said time duration to stop executing the current process after expiry of the time duration, and rescheduling the process by adding it to a scheduled collection.

15. A microcomputer comprising memory and a processor configured to execute a plurality of concurrent processes by said processor in accordance with a plurality of program steps, at least some of said processes being time dependent, the microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating a current process which is being executed by said processor, said process being referred to as the current process;

(ii) a timer list coupled to said storage element for identifying one or more processes which form a time-ordered collection awaiting execution by said processor after respective scheduling times for the processes in said collection;

(iii) a set of storage locations associated with said timer list for indicating scheduling times when the processes in said collection become ready for execution;

(iv) a control system coupled to said timer list and to said processor to cause said processor to add a further process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by said processor;

(vi) a program stage indicator for each concurrent process; said processor including timing logic responsive to said next process indicator to make said next process the current process for execution after its scheduling time occurs; and

the microcomputer further including one or more communication channels for message transmission between concurrent processes and synchronizing means for synchronizing message transmission through said channels.

16. The microcomputer according to claim 15 wherein said scheduling system further includes means for identifying processes which form a scheduled collection of processes awaiting execution by the processor and control means for adding a process to said scheduled collection, said scheduling system being responsive to said synchronizing means to terminate execution of the current process or to add a process to said scheduled collection thereby to achieve synchronization between concurrent processes.

17. The microcomputer according to claim 15 wherein said communication channels include a communication link which can be connected by a dedicated connection to a similar link on another device, thereby permitting message transmission with synchronization between concurrent processes on different microcomputers.

18. The microcomputer according to claim 15 wherein a process may execute one of a number of alternative components at least one of which is time related and at least one of which involves an input through one of said communication channels, said microcomputer further including means for determining whether the earliest time of any said time related component has yet occurred and whether any of said communication channels is ready yet to input a message.

19. A microcomputer comprising memory and a processor configured to execute a plurality of concurrent processes by said processor in accordance with a plurality of program steps, at least some of said processes being time dependent, the microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating a process which is being executed by said processor, said process being referred to as the current process;

(ii) a timer list coupled to said storage element for identifying one or more processes which form a time-ordered collection awaiting execution by said processor after respective scheduling times for the processes in said collection;

(iii) a set of storage locations associated with said timer list for indicating scheduling times when the processes in said collection become ready for execution;

(iv) a control system coupled to said timer list and to said processor to cause said processor to add a further process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by said processor;

(vi) a program stage indicator for each concurrent process; said processor including timing logic responsive to said next process indicator to make said next process the current process for execution after its scheduling time occurs,

(vii) means for identifying one or more processes which form a scheduled collection of processes awaiting execution by the processor,

(viii) second means for adding a further process to said scheduled collection, and

(ix) a second next process indicator to indicate the next process in said scheduled collection to be executed by the processor, the processor being responsive to selected instructions to terminate execution of the current process and to respond to said second next process indicator to make the process indicated therein the current process, whereby the processor is operated to share its processing time between a plurality of concurrent processes; wherein a process may execute one of a plurality of alternative time related components, said microcomputer further comprising means to indicate a time associated with each component, means to test the time associated with each component, and means to determine whether the earliest time associated with a component has yet occurred.

20. The microcomputer according to claim 19 wherein said scheduling system further comprises means to cause descheduling of said process if said earliest time has not yet occurred, and to cause said process to be added to said time-ordered collection.

21. The microcomputer according to claim 20 further comprising means for loading into a memory location corresponding to the process at least one special value to indicate the state of the process and to indicate that the process is one with alternative components.

22. The microcomputer according to claim 21 further comprising means for storing in said memory location corresponding to said process a first special value to indicate that at least one of the alternative components is ready and that the process is to remain scheduled, or a second special value to indicate that the process is descheduled while awaiting an alternative component to become ready.

23. The microcomputer according to claim 19 further comprising means for loading into a memory location corresponding to said process a special value to indicate that none of the alternative components has yet been selected, and means responsive to said special value to select one of the alternative process components when the process is rescheduled.

24. A microcomputer comprising memory and a processor configured to execute a plurality of concurrent processes by said processor in accordance with a plurality of program steps, at least some of said processes being time dependent, the microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating a process which is being executed by said processor, said process being referred to as the current process;

(ii) a timer list coupled to said storage element for identifying one of more processes which form a time-ordered collection awaiting execution by said processor after respective scheduling times for the processes in said collection;

(iii) a set of storage locations associated with said timer list for indicating scheduling times when the processes in said collection become ready for execution;

(iv) a control system coupled to said timer list and to said processor to cause said processor to add a further process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by said processor;

(vi) a program stage indicator for each concurrent process; said processor including timing logic responsive to said next process indicator to make said next process the current process for execution after its scheduling time occurs;

(vii) means for identifying one or more processes which form a scheduled collection of processes awaiting execution by the processor;

(viii) second means for adding a further process to said scheduled collection;

(ix) a second next process indicator to indicate the next process in said scheduled collection to be executed by the processor, the processor being responsive to selected instructions to terminate execution of the current process and to respond to said second next process indicator to make the process indicated therein the current process, whereby the processor is operated to share its processing time between a plurality of concurrent processes;

(x) means for specifying a time duration for the execution of a process; and

(xi) means responsive to said time duration to cause the processor to stop executing the current process after expiration of said time duration and to reschedule that current process by adding it to said scheduled collection.

25. A microcomputer comprising a memory and a processor configured to execute a plurality of concurrent processes in accordance with a plurality of program steps, at least some of said processes being time dependent, including:

a storage device for indicating the process which is currently being executed by the processor, said process being referred to as the current process;

a workspace for each process, said workspace including a plurality of first memory locations for recording variables associated with the corresponding process, a second memory location for indicating another process scheduled for execution by the processor, said second memory locations thereby collectively including a linked list of scheduled processes awaiting execution, a third memory location for storing a program stage indicator for the corresponding process, a fourth memory location for indicating the next process on a time-oriented list of processes so that said fourth memory locations collectively include a linked list of time-oriented processes awaiting scheduling, said memory further providing fifth memory locations for storing a respective time for each process on said linked list of time-ordered processes;

a timing device responsive to time data from said fifth memory location;

a control device responsive to said timing device for adding a process to said linked list of scheduled processes.

26. The microcomputer according to claim 25 wherein said fifth memory locations are distributed in said workspaces for said processes.

27. The microcomputer according to claim 25 further comprising means for indicating the process at the beginning of said time-oriented linked list, and further including storage means for indicating the time data for the process indicated by said first storage means.

28. A method of operating concurrent processes, at least some of which are time dependent processes, in a computer system having a processor wherein each concurrent process executes a program having a plurality of instructions, said processor including a timer comprising the steps of:

forming a first pointer for each process to identify the process,

forming a second pointer for each process to indicate a program stage for the process,

providing an indication of a process which is being executed by said processor, said process being referred to as the current process,

identifying a time-ordered collection of time dependent processes each having a respective specified scheduling time when the process may be executed by said processor,

providing an indication of said specified scheduling time for each process in the time-ordered collection, the process in said collection having the earliest said specified scheduling time being indicated as the next process,

and wherein execution of said current process comprises executing a sequence of instructions including a time related instruction indicating a specified scheduling time before which the current process is not to continue execution and responding to execution of said time related instruction by (a) comparing said specified scheduling time to the time indicated by said timer in said processor to determine whether said specified scheduling time has yet arrived, (b) in response to determining that the specified scheduling time has arrived, continuing execution of the said current process, and (c) in response to determining that the specified scheduling time has not yet arrived, (i) storing said second pointer for the process, (ii) stopping execution of the said current process, (iii) causing the said processor which executed said time related instruction to add the stopped process to said time-ordered collection at a position in the time-ordered collection such that its specified scheduling time forms an ordered sequence of specified times in the collection, and (iv) setting the indication of the current process to indicate a further process, and at a time after the specified scheduling time of said next process, responding to the execution of an instruction stopping the current process by setting the indication of the current process to indicate the said next process at a program stage indicated by the second pointer for the said next process.

29. A method of operating concurrent processes, at least some of which are time dependent processes, in a computer system having at least one processor, said processor including a timer and memory wherein each of said concurrent processes executes a plurality of instructions included in respective programs, the method comprising the steps of:

(a) establishing within the memory a respective workspace for each process, each workspace comprising a plurality of addressable memory locations, and recording in said locations of each workspace variables associated with the corresponding process;

(b) defining a respective first pointer for each process to identify the process;

(c) defining a respective second pointer for each process to indicate a program stage for the process; and

(d) scheduling a plurality of processes for execution by said one processor, including (i) providing an indication of a process which is being executed by said one processor, said process being referred to as the current process, (ii) forming a timeordered linked list of processes awaiting execution by the processor after a respective specified scheduling time indicated for each process in said list, said linked list being formed by providing in the workspace of each process in the list an indication of a specified scheduling time for the process, and an indication of said first pointer for the process with the next specified scheduling time,

and wherein execution of said current process comprises executing a sequence of instructions including a time related instruction indicating a specified scheduling time before which the current process is not to continue execution and responding to execution of said time related instruction by (a) comparing said specified scheduling time to the time indicated by said timer in said processor to determine whether said specified scheduling time has yet arrived, (b) in response to determining that the specified scheduling time has arrived continuing execution of the said current process, and (c) in response to determining that the specified scheduling time has not yet arrived (i) storing said second pointer for the process, (ii) stopping execution of said current process, (iii) causing the said one processor which executed said time-related instruction to add the stopped process to said time-ordered collection at a position in the time-ordered collection such that its specified scheduling time forms an ordered sequence of specified scheduling times in the collection, (iv) setting the indication of the current process to indicate a further scheduled process, and (v) at a time after the specified scheduling time of said next process, responding to execution of an instruction stopping the current process by setting the indication of the current process to indicate said next process and executing said next process at a program stage indicated by the second pointer for the said next process.

30. The method according to claim 29 further comprising adding a further process to said linked list by the steps of indicating a scheduling time for said further process, examining the scheduling times of processes already on the list, and adding said further process to the list at a time-ordered position dependent on its scheduling time, said further process being inserted between a preceding process and a following process by providing in the workspace of said preceding process an indication of said first pointer of said further process and providing in the workspace of said further process an indication of said first pointer of the following process.

31. A method of operating concurrent processes, at least some of which are time dependent processes, in a computer system wherein each concurrent process executes a program having a plurality of instructions, said computer system including a timer, comprising the steps of:

forming a first pointer for each process to identify the process;

forming a second pointer for each process to indicate a program stage for the process;

scheduling a plurality of processes for execution by one processor including providing an indication of a process which is being executed by said one processor, said process being referred to as the current process;

identifying a time-ordered collection of processes each having a respective specified scheduling time when the process may be executed by said one processor; and

providing an indication of said specified scheduling time for each process in the time-ordered collection, the process in said collection having the earliest scheduling time being indicated as the next process;

wherein execution of said current process comprises executing a sequence of instructions including a time related instruction indicating a specified scheduling time before which the current process is not to continue execution and responding to execution of said time related instruction by (a) comparing said specified scheduling time to the time indicated by said timer in said computer system to determine whether said specified scheduling time has yet arrived, (b) in response to determining that the specified scheduling time has arrived, then continuing execution of the said current process, and (c) in response to determining that the specified scheduling time has not yet arrived, (i) storing said second pointer for the current process, (ii) stopping execution of the said current process, (iii) causing the said one processor which executed same time-related instruction to add the stopped current process to said time-ordered collection at a position in the time-ordered collection such that its scheduling time forms an ordered sequence of scheduling times in the collection, and (iv) setting the indication of the current process to indicate a further scheduled process, and

at a time after the specified scheduling time of said next process, responding to execution of an instruction stopping the current process by setting the indication of the current process to indicate the said next process and executing said next process at a program stage indicated by the second pointer for the said next process.

32. A method according to claim 31 wherein the current process continues execution without stopping when on execution of a time related instruction the step of determining whether said scheduling time has yet arrived indicates that the scheduling time has already arrived.

33. The method according to claim 31 wherein said scheduling step further comprises identifying a scheduled collection of processes awaiting execution by the processor and wherein said next process is added to said scheduled collection and removed from said time-ordered collection after its scheduling time.

34. The method according to claim 31 further comprising the steps of indicating a priority for each process and establishing first and second time-ordered collections of processes, said first collection comprising processes of a common first priority and said second collection comprising processes of a common second priority different from said first priority.

35. A method according to claim 31 wherein said next process on a time-ordered collection is removed therefrom when its scheduling time arrives and the process on the time-ordered collection with the next scheduling time is then indicated as the next process.

36. A method according to claim 31 further comprising executing a current process having a program sequence including a time dependent instruction, determining a scheduling time associated with said instruction, and continuing to execute the current process if said scheduling time has already been reached.

37. A microcomputer comprising a timer, memory and a processor configured to execute a plurality of concurrent processes by said processor in accordance with a plurality of program steps, at least some of said processes being time dependent, said time dependent processes including time-related instructions, said time-related instruction including a time value relative to said timer, the microcomputer including a scheduling system comprising:

(i) an addressable storage element for indicating a process which is being executed by said processor, said process being referred to as the current process;

(ii) a timer list coupled to said storage element for identifying one or more processes which form a time-ordered collection awaiting execution by said processor after respective specified scheduling times for the processes in said collection;

(iii) a set of storage locations associated with said timer list for indicating said specified scheduling times when the processes in said collection become ready for execution;

(iv) a control system coupled to said timer list and to said processor to cause said processor to add said current process to said collection at a time-ordered position between a preceding process having an earlier scheduling time and a following process having a later scheduling time;

(v) a next process indicator to indicate the next process in said time-ordered collection for execution by said processor; and

(vi) a program stage indicator for each concurrent process;

said processor including timing logic responsive to said next process indicator to make said next process the current process for execution after its scheduling time occurs whereby when said processor executes a time-related instruction, said processor compares said time value in said time-related instruction to the time indicated by said timer, and, in response to said time value in said time-related instruction having arrived in said timer, continuing execution of said current process; in response to said time value in said time related instruction having not arrived, stopping execution of the current process and causing said control system to add said current process to said collection.

38. The microcomputer of claim 37 wherein said next process indicator comprises an addressable memory location.

39. A microcomputer according to claim 37 wherein said memory provides, for each process, a workspace having a plurality of addressable locations including locations for recording variables associated with the respective process, and wherein said addressable storage element for indicating the current process comprises a processor register for temporarily storing a workspace pointer identifying an address of the workspace of the current process.

40. The microcomputer according to claim 39 wherein said workspace includes a prescribed, addressable memory location for storing said program stage indicator.

41. The microcomputer according to claim 39 wherein said timer list for identifying one or more processes comprises a linked list of processes, each process workspace in said time-ordered collection including a link from said linked list, said link pointing to a subsequent process in said time-ordered collection.

42. The microcomputer according to claim 41 wherein each workspace includes a link location for storing link data, further comprising a special value stored in the link location in one of said process workspaces thereby to indicate that the corresponding process is currently the process with the last scheduling time in said time-ordered collection.

43. The microcomputer according to claim 41 further including means for deleting a process from said time-ordered collection and for altering data in said linked list of selected processes thereby to reestablish a link between the processes remaining on said time-ordered collection after said deletion.

44. The microcomputer according to claim 39 wherein each process workspace further includes an addressable location for storing data indicating the scheduling time of the corresponding process.

45. The microcomputer according to claim 39 wherein each process workspace includes means for holding a workspace pointer for another process in a scheduled collection of processes awaiting execution, thereby forming a linked list of scheduled processes awaiting execution.

46. The microcomputer according to claim 45 further comprising means for indicating the first and last processes on said linked list of scheduled processes.

47. The microcomputer according to claim 37 wherein said processes have first and second priorities, and wherein said timer list forms first and second time-ordered collections of processes awaiting execution by the processor, each process in said first time-ordered collection having said first priority, and each process in said second time-ordered collection having said second priority different from said first priority.

48. The microcomputer according to claim 37 wherein said scheduling system further includes means for identifying one or more processes which form a scheduled collection of processes awaiting execution by the processor, control means for adding a further process to said scheduled collection, and second next process indicator to indicate the next process in said scheduled collection to be executed by the processor, the processor being responsive to selected instructions to terminate execution of the current process and to respond to said second next process indicator to make the process indicated therein the current process, whereby the processor is operated to share its processing time between a plurality of concurrent processes.

49. The microcomputer according to claim 48 wherein said means for identifying processes identifies first and second scheduled collections of processes, said collections having processes of common first priority and second priority, respectively, said first priority being different from said second priority.

50. The microcomputer according to claim 37 further comprising means for receiving time signals and removing a process from said time-ordered collection when said scheduling time for the process is reached.

51. The microcomputer according to claim 50 further comprising means for identifying processes which form a scheduled collection of processes awaiting execution, and control means for adding a process to the scheduled collection when it is removed from said time-ordered collection.

Description

The invention relates to computers including microcomputers and is particularly applicable to microcomputers capable of executing time dependent processes.

BACKGROUND OF THE INVENTION

A microcomputer is described in our European Patent Specification No. 0110642 which includes scheduling means to permit the processor to share its processing time between a plurality of concurrent processes. A linked list of scheduled processes awaiting execution may be formed. A currently executing process may be descheduled and processes may be scheduled by adding to a scheduled list when required. This may for example arise in effecting message transmission between two processes where it is required that both processes be at corresponding stages in their program sequence when the message transmission occurs. However that patent specification does not describe the use of time dependent processes wherein scheduling of a process may be effected in accordance with a specfified time for the process.

OBJECTS OF THE INVENTION

It is an object of the present invention to provide an improved microcomputer for use in executing time dependent processes.

It is a further object of the present invention to provide an improved microcomputer with means for scheduling a plurality of concurrent processes so that the processor shares its processing time between a plurality of processes, together with means for responding to time dependent parameters for one or more processes.

It will be understood that the term microcomputer relates to small size computers generally based on integrated circuit devices but it does not impose any limit on how small a computer may be.

SUMMARY OF THE INVENTION

In the present invention, a processor in a computer system shares its time between a plurality of concurrent processes. At least some of the processes are allocated a scheduling time prior to which they are not to be executed. In order to schedule any time dependent process for execution, it is given a scheduling time so that the processor may execute the process any time after its scheduling time. The scheduling times in the preferred embodiment are absolute times rather than units of delay after some other event. Processes which have been allocated scheduling times are put into a time-ordered list (sometimes also called a "timer list") so that the process at the "top" of the list has the earliest time for execution and the process at the "end" or "bottom" of the list has the latest scheduling time. In between, the processes are arranged in a time-ordered manner so that each process can be taken off the top of the list in turn. When any process has to be added to the list by being given a scheduling time, it is slotted into the list at a time-ordered position so that its scheduling time follows that of the immediately preceding process and is ahead of the immediately following process. This system allows efficient operation of a computer system so that a processor can efficiently handle a plurality of concurrent processes while allowing time control so that no process is executed prior to its allocated scheduling time.

Preferably, the computer system, in addition to maintaining a time-ordered list, also maintains a list of scheduled processes. In the preferred embodiment, those processes which are on the time-ordered list await scheduling after their respective scheduling times have occurred. The preferred embodiment of this invention notes the occurrences and takes the process from the time-ordered list once its scheduling time has occurred so that the process is scheduled in the list of scheduled processes (sometimes called a "scheduled list") and will be executed in due course.

The preferred embodiment also includes a storage location which indicates the process in the time-oriented list which has the earliest scheduling time. This storage location may comprise an addressable memory location.

According to the preferred embodiment, each process is assigned a respective workspace which is a set of addressable memory locations. This workspace includes first locations for recording variables associated with the process. Preferably, a processor register is employed to hold a workspace pointer identifying an address of the workspace for the process which is currently being executed, and that process thus is called the "current process."

Preferably, according to this invention, the workspaces are used to form two linked lists. One linked list indicates those processes which have been scheduled for execution. The other linked list consists of the time-ordered list described supra. Preferably the linked list of scheduled processes is formed by an addressable memory location at a prescribed location at each of the several workspaces corresponding to the processes on the scheduled list. Preferably the linked list of time-ordered processes is formed by a different memory location at each of the workspaces of processes on the time-ordered list.

Thus, according to the preferred embodiment, any given scheduled process will have, at a prescribed memory location in its workspace, an indication of the next process scheduled for execution if one exists. Similarly, any process which is on the time-ordered list will have at another prescribed memory location in the workspace an indication of the next process on the time-ordered list if one exists. Preferably, whichever process has the last scheduling time on the time-oriented list stores a special value at the link location. Another feature of the preferred embodiment of this invention is that the workspace for each process includes an addressable location for indicating the scheduling time of that process.

In the preferred embodiment, the microcomputer allocates different priorities to the processes. Thus, one group of processes may have first priority and another group may have second priority. Correspondingly, in the preferred embodiment, when there are such different priorities, there will also be time-ordered linked lists. A first such linked list includes processes having only first priority, whereas a second time-ordered linked list has processes of only second priority, and so on. Similarly, in the case where there are different priority processes, corresponding, separate lists of scheduled processes are maintained, with all the processes in one scheduled list having one priority and all the processes in another scheduled list having a second priority, and so on.

The present invention extends also to a network having a plurality of interconnected microcomputers, each as described supra. Each microcomputer includes communication channels provided by one or more communication links which are connected by dedicated connections to similar links on further devices so that message transmission with synchronization between concurrent processes on different microcomputers is permitted.

The microcomputer of the preferred embodiment is arranged to execute a process with a plurality of alternative time related components. Such a microcomputer also indicates the time associated with each component, tests the time associated with each component, and determines whether the earliest time associated with a component has yet occurred.

Still another feature of the preferred embodiment is that a time duration may be specified for the execution of a process. The microcomputer is responsive to this time duration and causes the processor to stop executing the current process after expiration of this time duration. It reschedules the process which has thus been terminated by adding it to a scheduled collection.

BRIEF DESCRIPTION OF THE DRAWINGS

An embodiment of the invention will now be described by way of example and with reference to the accompanying drawings in which:

FIG. 1 is a block diagram showing the main features of a microcomputer embodying the present invention,

FIG. 2 is a block diagram of part of the microcomputer and for convenience has been split into two parts shown on FIGS. 2A and 2B, the Figure particularly illustrates the registers, data paths and arithmetic logic unit of the central processing unit as well as the interface between the central processing unit and the memory and communication links,

FIG. 3 illustrates a timer logic circuit which forms part of FIG. 2B,

FIG. 4 illustrates the relationship between processor registers and the workspaces of a scheduled list of high priority processes for execution by the microcomputer,

FIG. 5 is similar to FIG. 4 but illustrates a scheduled list of low priority processes while a high priority process is being executed,

FIG. 6 illustrates a timer list of low priority processes awaiting predetermined times before being rescheduled,

FIG. 7 illustrates a timer list of high priority processes awaiting predetermined times before being rescheduled,

FIG. 8 illustrates a network of communicating microcomputers in accordance with the present invention, the microcomputers in the network having different wordlengths,

FIGS. 9A to 9D illustrate a sequence of operations for a process carrying out a "timer input" operation,

FIGS. 10A to 10E illustrate a sequence for inserting a process into a timer list,

FIGS. 11A to 11C illustrate a sequence of operations for a Time Alternative process and in particular illustrates how the process determines the earlier of the alternative times,

FIGS. 12A to 12C illustrate a sequence of operations by a process selecting between one of a number of alternative times, one of which has already arrived,

FIGS. 13A to 13F illustrate a sequence of operations for a process selecting between a number of alternative times, none of which has arrived when the process first attempts selection,

FIGS. 14A to 14D illustrate a sequence of operations for a process selecting between the alternative of an input from a message channel or the occurrence of a particular time, the message channel being ready to communicate at the time the process starts the selection, and

FIGS. 15A to 15F illustrate a sequence of operations for a process selecting between the alternative of an input through a message channel or the occurrence of a specified time in which the channel is not ready to input a message nor has the time occurred when the process attempts to select one of the alternatives.

DESCRIPTION OF THE PREFERRED EMBODIMENT

The microcomputer described in this example comprises an integrated circuit device in the form of a single silicon chip having both a processor and memory in the form of RAM as well as links to permit external communication. The main elements of the microcomputer are illustrated in FIG. 1 on a single silicon chip 11 using p-well complementary MOS technology. A central processing unit (CPU) 12 is provided with a timer 9 to allow time control of the execution of processes. It also includes some read-only memory (ROM) 13 and is coupled to a memory interface 14 controlled by interface control logic 15. The CPU 12 incorporates an arithmetic logic unit (ALU), registers and data paths illustrated more fully in FIG. 2. The CPU 12 and memory interface 14 are connected to a bus 16 which provides interconnection between the elements on the chip 11. A service system 17 is provided with a plurality of input pins 18. The microcomputer is provided with a random access memory (RAM) 19 and ROM 20 and the amount of memory on the chip is not less than 1K byte so that the processor 12 can be operated without external memory. Preferably the memory on the chip is at least 4K bytes. An external memory interface 23 is provided and connected to a plurality of pins 24 for connection to an optional external memory. To allow the microcomputer to be linked to other computers to form a network, a plurality of serial links 25 are provided having input and output pins 26 and 27 respectively. The input and output pins of one serial link may each be connected by its own single wire non-shared unidirectional connection to the corresponding output and input pins of a serial link on another microcomputer as shown in FIG. 8. Each serial link is connected to a synchronisation logic unit 10 comprising process scheduling logic.

This embodiment is a development of the microcomputer described in our copending PCT patent application No. PCTGB84/00379 and European Patent Application No. 84307586.2. To avoid unnecessary repetition of description, the full details of the construction and operation of that microcomputer will not be set out below but the description in the above mentioned patent applications is hereby incorporated herein by reference.

The present embodiment provides an improved form of Transputer (Trade Mark of INMOS International plc) microcomputer. It provides for timer control so that processes may be executed in dependence on timer data and timer lists of processes awaiting specified times before execution may be formed.

The overall arrangement of the microcomputer is generally similar to that described in the above mentioned patent applications. In the following description similar names will be given to those parts corresponding to the embodiment in the above mentioned patent applications. The memory provides a plurality of process workspaces having addressable locations which can be indicated by pointers. Message communication can be effected through channels which may comprise addressable memory locations in the case of process to process communication on the same microcomputer. To effect process to process communication between different microcomputers input and output channels are provided in serial links and these channels may also be addressed in a manner similar to the locations provided in the memory.

In order to implement the improvements discussed above, various modifications in the construction and operation of the microcomputer are necessary and the following description will be directed to those aspects where modifications are involved in order to effect those improvements.

As in the example of the above mentioned patent applications, the particular wordlength of the example described is 16 bits but it will be understood that other wordlengths such as 8, 16, 24, 32 or other wordlengths may be used. Furthermore, in the present case different wordlength microcomputers can be connected in the same network as shown in FIG. 8 so that they may communicate with each other regardless of their independent wordlength.

Each pointer is a single word and is treated as a two's complement signed value. That means that if the most significant bit in the pointer is a 1 the most signficant bit is taken as negative with all the remaining bits representing positive numbers. If the most significant bit is 0 then all bits in the pointer are taken as representing positive values. This enables the standard comparison functions to be used on pointer values in the same way that they are used on numerical values.

Certain values are never used as pointers as they are reserved to indicate that some special action is required.

In the following description, names are used to represent these and other values as follows:

    ______________________________________
    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
    TimeSet.p       MostNeg + 1
    TineNotSet.p    MostNeg + 2
    ______________________________________

    ______________________________________
    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.
    TIME SLICE REG
                 A register 80 for holding the time at
                 which the current process must be
                 temporarily stopped.
    CLOCK REG    A register 81 for indicating the current
                 time
    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.
    INSERTFLAG   A 1 bit register or flag 82 which is set
                 to 1 when the processor is inserting a
                 process into a timer list.
    DELETEFLAG   A 1 bit register or flag 83 which is set to 1
                 when the processor is deleting a process
                 from a timer list.
    VALIDTIMEFLAG
                 A 1 bit register or flag 84 which is set to 1
                 if there are any processes on the timer list of
                 appropriate priority.
    NEXTTIMEFLAG A register 85 for holding the time at
                 which the first process on the timer list of
                 appropriate priority becomes ready for
                 scheduling.
    ______________________________________

    ______________________________________
    Offset     Name of Offset
                             Name of Location
    ______________________________________
    -1         Iptr.s        Iptr location
    -2         Link.s        Link location
    -3         State.s       State location
    -4         TLink.s       TLink location
    -5         Time.s        Time location
    ______________________________________

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

    ______________________________________
    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]) :
    10.   IF
    11.    Pri = 1
    12.     TimeSliceReg := ClockReg + LengthOfTimeSlice
    13.    Pri = 0
    14.     SKIP :
    ______________________________________

    ______________________________________
    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 :
    ______________________________________

    ______________________________________
    1.  PROC StartNextProcess =
    2.    SEQ
    - Clear the SNP flag := 0
    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 :
    ______________________________________

    ______________________________________
    PROC HandleTimerRequest =
    1.  SEQ
    set ProcptrReg to first process on list
    3.    RIndexWord(TptrLocO, ProcPri, TempReg)
    4.    ProcPtrReg := TempReg
    set TempReg to TLink location of first process
    6.    RIndexWord(ProcPtrReg, TLink.s, TempReg)
    7.    WIndexWord(ProcPtrReg, TLink.s, TimeSet.p)
    update timer pointer word
    9.    WIndexWord(TprtrLoc0, ProcPri, TempReg)
    10.
    is the list now empty?
    11.   IF
    12.     TempReg = NotProcess.p
    Yes.
    14.       ValidTimeFlag[ProcPri] := 0
    15.     TempReg <> NotProcess.p
    No; set NextTimeReg
    17.       RIndexWord(TempReg, Time.s, NextTimeReg
              [ProPri])
    check State location of process
    19.   RIndexWord(ProcPtrReg, State.S, TempReg)
    20.   IF
    21.     TempReg = Ready.p
    22.      SKIP
    23.    TempReg = Waiting.p
    24.      SEQ
    25.       WIndexWord(ProcPtrReg, State.s, Ready.p)
    26.       ProcDescReg := ProcPtrReg  / ProcPri
    27.       Run :
    ______________________________________

    ______________________________________
    PROC InsertStep =
    Areg[Pri] contains the time associated with this process
    Breg[Pri] is used as a pointer to the pointer to the next
    process
    Creg[Pri] is used as a pointer to the next process
    1.  SEQ
    2.   IF
    3.    Creg[Pri] <> NotProcess.p
    pick up time associated with next process
    5.     RIndexWord(Creg[Pri], Time.s, Treg[Pri])
    6.    Creg[Pri] = NotProcess.p
    7.     SKIP
    8.   IF
    9.    (Creg[Pri] <> NotProcess.p) AND (Areg[Pri] AFTER
          Treg[Pri])
    10.    SEQ
    move on one process
    12.     AtWord(Creg[Pri], TLink.s, Breg[Pri])
    13.     RIndexWord(Breg[Pri], 0, Creg[Pr])
    14.   TRUE
    15.    SEQ
    found place to insert
    17.     InsertFlag[Pri] := 0
    link in this process
    19.     WIndexWord(Breg[Pri], 0, WptrReg[Pri])
    20.     WIndexWord(WptrReg[Pri], TLink.s, Creg[Pri])
    Set the NextTimeReg
    22.     RIndexWord(TptrLocO, Pri, Treg[Pri])
    23.     RIndexWord(Treg[Pri], Time.s, NextTimeReg[Pri])
    24.     ValidTimeFlag[Pri] := 1
    25.     WIndexWord(WptrReg[Pri], Iptr.s, IptrReg[Pri])
    26.     SNPFlag[Pri] := 1 :
    ______________________________________

    ______________________________________
    PROC DeleteStep =
    1.   IF
    2.    Creg[Pri] <> WptrReg[Pri]
    3.     SEQ
    not yet found current process; step on
    5.      AtWord(Creg[Pri], TLink.s, Breg[Pri])
    6.      RIndexWord(Breg[Pri], 0, Creg[Pri])
    7.    Creg[Pri] = WptrReg[Pri]
    8.     SEQ -- found process; delete from list
    9.      DeleteFlag[Pri] := 0
    10.     RIndexWord(WptrReg[Pri], TLink.s, Creg[Pri])
    11.     WIndexWord(Breg[Pri], 0, Creg[Pri])
    Check if there are any processes left on queue
    13.     RIndexWord(TptrLoc0, Pri, Breg[Pri])
    14.     IF
    15.      Breg[Pri] = NotProcess.p
    No processes left
    17.       ValidTimeFlag[Pri] := 0
    18.      Breg[Pri] <> NotProcess.p
    Get time from first process
    20.       RIndexWord(Breg[Pri], Time.s, NextTimeReg
              [Pri])
    21.     WIndexWord(WptrReg[Pri], TLink.s,
            TimeNotSet.p) :
    ______________________________________

    ______________________________________
    1.  PROC TimeSlice =
    2.   IF
    3.    (Pri = 1) AND ((ClockReg AFTER TimeSliceReg)
          OR (ClockReg = TimeSlice))
    4.     SEQ
    5.      ProcDescReg := Wptr  / Pri
    6.      Run
    7.      SNP[Pri] := 1
    8.   TRUE
    9.    SKIP
    1.  PROC InsertInTimerList =
    This sets up the registers and the Insert Flag so that
        repeated execution of InsertSep will result in this process
        being inserted into the time list at the time specified in
        Areg[Pri] and then descheduled
    Breg[Pri] is used as a pointer to the pointer to the next
        process
    Creg[Pri] is used as a pointer to the next process
    2.  SEQ
    3.     WIndexWord(WptrReg[Pri], Time.s, Areg[Pri])
    4.     InsertFlag[Pri] := 1
    5.     AtWord(TptrLocO, Pri, Breg[Pri])
    6.     RIndexWord(Breg[Pri], 0, Creg[Pri]):
    1.  PROC DeleteFromTimerList =
    This causes the current process to be deleted from the
         appropriate timer list, TimeNotSet to be written to the
         TLink location. This is achieved by setting up the
         registers and then repeatedly executing DeleteStep.
    Areg is NOT to be used
    Breg is used as a pointer to the pointer to the next
         process
    Creg is used as a pointer to the next process
    2.   SEQ
    3.    DeleteFlag[Pri] := 1
    4.    AtWord(TptrLocO, Pri, Breg[Pri])
    5.    RIndexWord(Breg[Pri], 0, Creg[Pri]):
    1.  PROC IsThisSelectedProcess =
    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 :
    ______________________________________

    ______________________________________
    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
    31        ldtimer     load timer
    32        tin         timer input
    33        talt        timer alt start
    34        taltwt      timer alt wait
    35        enbt        enable timer
    36        dist        disable timer
    ______________________________________

    ______________________________________
    jump
    def:   SEQ
    AtByte(IptrReg[Pri], Oreg[Pri], IptrReg[Pri])
    TimeSlice
    pur-   to transfer control backwards or forwards to provide
    pose:  loops and exits from loops, to cause a process to be
           rescheduled if its allotted time slice has elapsed
    loop end
    def:   SEQ
    RIndexWord(Breg[Pri], 1, Creg[Pri])
    Creg[Pri] := Creg[Pri] -1
    WIndexWord(Breg[Pri], 1, Creg[Pri])
    IF
           Creg[Pri] > 0
            SEQ
             RIndexWord(Breg[Pri], 0, Creg[Pri])
             Creg[Pri] := Creg[Pri] + 1
             WIndexWord(Breg[Pri], 0, Creg[Pri])
             AtByte(IptrReg[Pri], -Areg[Pri], IptrReg
             [Pri])
           TRUE
            SKIP
    TimeSlice
    pur-   to implement replicators and to cause a process to be
    pose:  rescheduled if its allotted timeslice has elapsed
    ______________________________________

    ______________________________________
    OPERATIONS FOR TIMER INPUT
    ______________________________________
    load timer
    def:    SEQ
           Creg[Pri] := Breg[Pri]
           Breg[Pri] := Areg[Pri]
           Areg[Pri] := ClockReg
    pur-    to load the current value of the timer into Areg
    pose:
    timer input
    def:   1.    IF
    2.        ClockReg AFTER Areg[Pri]
    3.         SKIP
    4.        TRUE
    5.         SEQ
    6.          WIndexWord(WptrReg[Pri], State.s,
                Waiting.p)
    7.          Areg[Pri] := Areg[Pri] + 1
    8.          InsertInTimerList
    pur-     to schedule the process after a certain time
    pose:
    ______________________________________


______________________________________
    OPERATIONS FOR ALTERNATIVE TIMER INPUT
    ______________________________________
    timer alternative start
    def:   1.    SEQ
    2.        WIndexWord(WptrReg[Pri], State.s,
              Enabling.p)
    3.        WIndexWord(WptrReg[Pri], TLink.s,
              TimeNotSet.p)
    pur-     to initialise the process state and the timer
    pose:    state prior to enabling alternative inputs
             and the timer
    timer alternative wait
    def:   1.    SEQ
    2.        WIndexWord(WptrReg[Pri], 0 -1)
    3.        RIndexWord(WptrReg[Pri], TLink.s, Breg[Pri])
    4.        RIndexWord(WptrReg[Pri], Time.s, Areg[Pri])
    5.        IF
    6.         (Breg[Pri] = TimeSet.p) AND (ClockReg
               AFTER Areg[Pri])
    7.          SEQ -- clock makes process ready
    8.           WIndexWord(WptrReg[Pri], State.s,
                 Ready.p)
    9.           WIndexWord(WptrReg[Pri], Time.s,
                 ClockReg)
    10.        TRUE
    11.         SEQ -- clock does not make process
                ready
    12.          RIndexWord(WptrReg[Pri], State.s,
                 Creg[Pri])
    13.          IF
    14.           Creg[Pri] = Ready.p
    15.            WIndexWord(WptrReg[Pri],
                   Time.s, ClockReg)
    16.           Creg[Pri] = Enabling.p
    17.            SEQ
    18.             WIndexWord(WptrReg[Pri],
                    State.s, Waiting.p)
    19.             IF
    20.              Breg[Pri] = TimeSet.p
    21.               SEQ
    22.                Areg[Pri] := Areg[Pri] +
                       1
    23.                InsertInTimerList
    24.              Breg[Pri] = TimeNotSet.p
    25.               SEQ
    26.                WIndexWord(WptrReg
                       [Pri], Iptr.s, IptrReg[Pri])
    27.                SNPFlag[Pri] := 1
    pur-     to wait for one of a number of enabled
    pose:    inputs, some of which may be timer inputs
    enable timer
    def:   1.    SEQ
    2.        IF
    3.         Areg[Pri] = MachineFALSE
    4.          SKIP
    5.         Areg[Pri] <> MachineFALSE
    6.          SEQ
    7.           RIndexWord(WptrReg[Pri], TLink.s,
                 Oreg[Pri])
    8.           IF
    9.            Oreg[Pri] = TimeNotSet.p
    10.            SEQ
    11.             WIndexWord(WptrReg[Pri],
                    TLink.s, TimeSet.p)
    12.             WIndexWord(WptrReg[Pri],
                    Time.s, Breg[Pri])
    13.           Oreg[Pri] = TimeSet.p
    14.            SEQ
    15.             RIndexWord(WptrReg[Pri],
                    Time.s, Oreg[Pri])
    16.             IF
    17.              Oreg[Pri] AFTER Breg[Pri]
    18.               WIndexWord(WptrReg[Pri],
                      Time.s, Breg[Pri])
    19.              TRUE
    20.               SKIP
    21.       Breg[Pri] := Creg[Pri]
    pur-     to enable a timer input
    pose:
    disable timer
    usage:   On entry:
                      Areg = Code offset, Breg =
                      Boolean guard
                      Creg = Time
             On exit: Areg = MachineTRUE if this was
                      selected component
                      Areg = MachineFALSE otherwise
    def:   1.    IF
           2.    Breg[Pri] = MachineFALSE
    3.        Areg[Pri] := MachineFALSE
    4.       Breg[Pri] <> MachineFALSE
    5.        SEQ
    6.         RIndexWord(WptrReg[Pri], TLink.s, Oreg[Pri])
    7.         IF
    8.          Oreg[Pri] = TimeNotSet.p
    9.           Areg[Pri] := MachineFALSE
    10.         Oreg[Pri] = TimeSet.p
    11.          SEQ
    12.           RIndexWord(WptrReg[Pri], Time.s, Oreg[Pri])
    13.           IF
    14.            Oreg[Pri]  AFTER Creg[Pri]
    15.             IsThisSelectedProcess
    16.            TRUE
    17.             Areg[Pri] := MachineFALSE
    18.        TRUE
    19.          SEQ
    20.           Areg[Pri] := MachineFALSE
    21.           DeleteFromTimerList
    pur-     to disable an enabled timer input
    pose:    to select one of a number of alternative
             timer inputs
    alternative end
    def:         SEQ
    1.            RIndexWord(WptrReg[Pri], 0, Oreg[Pri])
    2.            AtByte(IptrReg[Pri], Oreg[Pri], IptrReg[Pri])
    pur-     to start execution of the selected component of an
    pose:    alternative process
    ______________________________________