US 4,794,526 AGranted

Microcomputer with priority scheduling

AssigneeInmos Limited

InventorsMichael D. May, Roger M. Shepherd

Life of this patent

Estimating the term…

Abstract

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.

Claims23

Dependent claims

A microcomputer comprising memory and a processor operable 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 instruction including a set of function bits which designate a function to be executed by the processor,

(a) the microcomputer including scheduling means comprising
(i) means for indicating the process which is being executed by the processor, said process being called the "current process",
(ii) means for indicating the priority of each of said concurrent processes,
(iii) means for identifying one or more of said concurrent processes which form a first collection awaiting execution by the processor, each process in said first collection having the same first priority,
(iv) means for identifying one or more processes which form a second collection awaiting execution by the processor, each process in said second collection having the same second priority which is lower than said first priority,
(v) means for adding one or more further processes to said first collection or said second collection,
(vi) next process indicator means to indicate the next process in each of said collections to be executed by the processor, and
(vii) a group of program stage indicators, one for each concurrent process;
(b) said processor including means responsive to a selected one of said instructions to stop execution of the current process by said processor and to respond to said next process indicator means to make the next process in said first collection the current process if a process is found in said first collection, or to make the next process indicated by said second collection the current process if no process is found in said first collection, whereby said processor is operated to share its processing time among said plurality of said concurrent processes;
and
(c) said microcomputer including message transmission means for effecting synchronized message transmission between concurrent processes, said message transmission means comprising a plurality of communication channels, means for indicating the status of data communication through each channel and synchronizing means responsive to said status to stop executing a current process or add a process to said first or second collection so that two communicating processes are brought to corresponding program steps when the communication between them is completed.

8 more elements

A method of operating concurrent processes in a computer system wherein each 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;
indicating na allocated priority for each process;
scheduling a plurality of processes for execution by a processor including indicating a process which is being executed by the processor, said process being referred to as the "current" process;
identifying a first collection of processes awaiting executing by the processor wherein all processes in said first collection have a common first priority;
identifying one or more processes forming a second collection awaiting execution by the processor, each of said processes in said second collection having a common second priority lower than said first priority;
indicating the next process in said first collection;
indicating the next process in said second collection;
in response to a particular instruction stopping execution of the current process, storing a second pointer for said current process, changing the indication of the current process to indicate the next process in said first collection if there is a process in said first collection or to indicate the next process in said second collection if no process is found in said first collection, and then executing said next process at a program stage indicated by the second pointer for the second next process;
and
transmitting a message betwene a pair of concurrent communicating processes through an addressable communication channel, wherein each process in said pair executes a seqeunce of instructions in a program including communication instructions, indicating the status of communication through said channel and depending on the indicated status, stopping execution of the current process or adding a process to said first or second collections so that said pair of concurrent communicating processes is brought to corresponding program steps when message transmission between said pair of processes is completed.

8 more elements

A method of operating concurrent processes in a computer system having at least one processor 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 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;
(d) providing an indication of the priority of each process;
(e) scheduling a plurality of processes for execution by a processor including
(i) indicating a process which is being executed by a process which ss being executed by a processor said process being called the "current process,"
(ii) forming a first linked list of processes awaiting execution, each of said processes having the same first priority, said first linked list being formed by providing in the workspace of each process on said first linked list an indication of the first pointer for the respective net first priority process scheduled for execution by the processor,
(iii) forming a second linked list of processes awaiting execution, each of said processes having the same second priority, said second priority being lower than said firs priority, said second linked list being formed by providing in the workspace of each process on said second linked list an indication of the first pointer for the respective next second priority process scheduled for execution by the processor, and
(iv) in response to an instruction stopping execution of the current process, storing said second pointer coresponding to said current process, changing the indication of the current process to indicate the next process on said first linked list if a process is found thereon or indicating the next process on said second linked list if no process is found on said first linked list, and then executing said next process at a program stage indicate by the secodn pointer of said next process;
and
(f) transmitting a message between two concurrent processes through an addressable communication channel, including indicating the status of communication through the channll and, based on said status, stopping the execution of said current process or adding a process to said first or second linked list, that said two concurrent communicating processes are brought to corresponding program steps when message transmission between the two concurrent processes is completed.

8 more elements

A microcomputer comprising memory and a processor coupled to read from and write into memory, said processor being operable to execute a plurality of concurrent processes in accordance with a plurality of program steps, said prorgram steps comprising a plurality of instructions for sequential execution by the processor wherein

(a) the microcomputer includes scheduling means comprising:
(i) a first linked list indicating processes of the same first priority awaiting execution by said processor,
(ii) a second linked list indicating processes of the same second priority awaiting execution by said processor, said sccond priority being lower than said first priority,
(iii) means for indicating the process which is currently being executed by said processor, said process being called the "current process," and
(iv) means for indicating the last process on each of said linked lists;
(b) said memory providing for each process a respective workspace having a plurality of addressable locations, each said workspace including:
(i) memory locations for recording variables associated with the corresponding process,
(ii) a program stage indicatior for the corresponding process, and
(iii) next process indicator means indicating the next process on each of said first and second linked lists,
(c) said microcomputer including means responsive to selected instructions to stop execution of the current process and to make the next process on said linked list the current process is found on said first linked list and to make the next process on said second linked list the current process if no process is found on said first linked list, and to add one of said concurrent processes to the end of said first or second linked list when required, whereby the processor is operated to share its processing time among said plurality of concurrent processes;
and
(d) said microcomputer further comprises message transmission circuitry for effecting synchronizing message transmission between concurrent processes, said message transmission circuitry comprising a plurality of communication channels, a status indicator indicating the status of data communication through each channel and synchronizing means responsive to said status indicator to stop the execution of the current process or to add a process to one of said collections so that two communicating processes are brought to corresponding progrmm steps when the communication between them is completed.

9 more elements

A network of directly interconnected microcomputers each comprising a single integrated circuit microcomputer comprising memory and a processor for executing 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 wherein:

(a) each said microcomputer includes scheduling means comprising
(i) means for indicating the process which is being executed by said processor on said integrated circuit, said process being called the "current process,"
(ii) means indicating the priority of each of said concurrent process,
(iii) means for identifying one or more processes which form a first collection awaiting execution by said processor, each process in said first collection having the same first proirity,
(iv) means for identifying one or more of said concurrent processes which from a second collection awaiting execution by said processor, each process in said second collection having the same second pirority which is lower than sadi first priority,
(v) means for adding a further one of said concurrent processes to said first or second collection,
(vi) next process indicator means to indicate the next process for execution in each of said first and second collections, and
(vii) a group of program stage indicators, one for each concurrent process;
(b) each said processor includes means responsive to a selected instruction to stop execution of its current process and to respond to said next processor indicator means to make the next process indicated in said first collection the current process if a process is found in said first collection and to make the next process indicated in second collection the current process if no process is found in said first collection, whereby the processor is operated to share its processing time between a plurality of concurrent processes;
and
(c) each microcomputer further comprises message transmission circuitry for effecting synchronized message transmission between concurrent processes, said message transmission circuitry comprising a plurality of communication channels, a status indicator indicating the status of data communication through each channel and syncronizing means responsive to said status indicator to stop the execution of the current process or add a process to one of said collections so that two communicating processes are brought to corresponding program steps when the communication between them is completed.

8 more elements

Dependencies are inferred from the claim text.

patentgrep

Loading patent…

Abstract

(a) the microcomputer including scheduling means comprising
(i) means for indicating the process which is being executed by the processor, said process being called the "current process",
(ii) means for indicating the priority of each of said concurrent processes,
(iii) means for identifying one or more of said concurrent processes which form a first collection awaiting execution by the processor, each process in said first collection having the same first priority,
(iv) means for identifying one or more processes which form a second collection awaiting execution by the processor, each process in said second collection having the same second priority which is lower than said first priority,
(v) means for adding one or more further processes to said first collection or said second collection,
(vi) next process indicator means to indicate the next process in each of said collections to be executed by the processor, and
(vii) a group of program stage indicators, one for each concurrent process;
(b) said processor including means responsive to a selected one of said instructions to stop execution of the current process by said processor and to respond to said next process indicator means to make the next process in said first collection the current process if a process is found in said first collection, or to make the next process indicated by said second collection the current process if no process is found in said first collection, whereby said processor is operated to share its processing time among said plurality of said concurrent processes;
and
(c) said microcomputer including message transmission means for effecting synchronized message transmission between concurrent processes, said message transmission means comprising a plurality of communication channels, means for indicating the status of data communication through each channel and synchronizing means responsive to said status to stop executing a current process or add a process to said first or second collection so that two communicating processes are brought to corresponding program steps when the communication between them is completed.

8 more elements