Realtime hardware scheduler utilizing processor message passing and queue management cells

Claim 1

A device for managing one or more scheduling queues which schedule the execution of multiple tasks and events in a computer system having at least one scheduling processor for scheduling individual tasks and events, at least one slave processor for executing such tasks and events and a shared memory including at least one area for storing at least one circular first-in-first-out random access memory queue comprised of multiple, sequential memory locations and at least one area for storing at least one task control block comprising: first scheduler means for managing tasks awaiting execution; and second scheduler means for managing tasks the execution of which has been completed, said first scheduler means and said second scheduler means each further comprising: at least one cell means for storing and retrieving pointers to the location of task control blocks in the shared memory wherein each of said cell means communicates directly with one designated circular random access memory queue in which one memory location is used to store one such pointer; and routing means communicating both with said cell means and with either one scheduling processor or one slave processor for receiving task control block pointer read and write request from such processor and for routing such request to one of said cell means.

Claim 2

A device for managing one or more scheduling queues which schedule the execution of multiple tasks and events in a computer system having at least one scheduling processor for scheduling individual tasks and events, at least one slave processor for executing such tasks and events and a shared memory including at least one area for storing at least one circular first-in-first-out random access memory queue comprised of multiple, sequential memory locations and at least one area for storing at least one task control block comprising: first scheduler means for managing tasks awaiting execution; and second scheduler means for managing tasks the execution of which has been completed, said first scheduler means and said second scheduler means each further comprising: at least one cell means for storing and retrieving pointers to the location of task control blocks in the shared memory wherein each of said cell means communicates directly with one designated circular random access memory queue in which one memory location is used to store one such pointer; and routing means communicating both with said cell means and with either one scheduling processor or one slave processor for receiving task control block pointer read and write request from such processor and for routing such request to one of said cell means.

Claim 7

A method, performed by a computer system including at least two scheduling units each having at least one cell therein for managing a memory queue associated with that cell and a write register containing a value representing a memory location in that queue, at least one processor for scheduling individual tasks and events, at least one processor for executing such tasks and events and a shared memory having at least one area for storing at least one circular first-in-first-out random access memory queue having multiple memory locations and at least one area for storing at least one task control block, for managing and storing a pointer to a task control block for a task which has been identified and for which a task control block containing details about the task has been built and stored in the shared memory, comprising the computer-performed steps of: writing a pointer to the task control block to one of the scheduling units; routing that pointer to a selected cell within said one of the scheduling units; determining if the writing step is valid and, if so, storing the pointer in the memory location designated by the value contained in the write register and, if not, aborting the write operation; resetting the contents of the write register in the cell based on the availability of free memory locations in the queue; signaling the presence and priority of other valid tasks; making manual adjustments to the computer system in the event an invalid writing step has been attempted.

Claim 8

A method, performed by a computer system including at least two scheduling units each having at least one cell therein for managing a memory queue associated with that cell and a write register containing a value representing a memory location in that queue, at least one processor for scheduling individual tasks and events, at least one processor for executing such tasks and events and a shared memory having at least one area for storing at least one circular first-in-first-out random access memory queue having multiple memory locations and at least one area for storing at least one task control block, for managing and storing a pointer to a task control block for a task which has been identified and for which a task control block containing details about the task has been built and stored in the shared memory, comprising the computer-performed steps of: writing a pointer to the task control block to one of the scheduling units; routing that pointer to a selected cell within said one of the scheduling units; determining if the writing step is valid and, if so, storing the pointer in the memory location designated by the value contained in the write register and, if not, aborting the write operation; resetting the contents of the write register in the cell based on the availability of free memory locations in the queue; signaling the presence and priority of other valid tasks; making manual adjustments to the computer system in the event an invalid writing step has been attempted.

Claim 9

A method, performed by a computer system including at least two scheduling units each having at least one cell therein for managing a memory queue associated with that cell and a read register containing a value representing a memory location in that queue, at least one processor for scheduling individual tasks and events, at least one processor for executing such tasks and events and a shared memory having at least one area for storing at least one circular first-in-first-out random access memory queue having multiple memory locations and at least one area for storing at least one task control block, for managing and enabling a requesting processor to retrieve a task control block, comprising the computer-performed steps of: requesting one of the scheduling units to retrieve a pointer to a task control block based on a read request; determining whether there are any valid tasks, pointers to which can be retrieved, and, if not, signaling the absence of such valid tasks and exiting the process; routing the read request to a cell selected on the basis of the mode, parallel or serial, in which such cell is operating if there are valid tasks; accessing a memory location in the queue with which that cell is associated specified by the value contained in the read register of that cell; retrieving a pointer from the accessed memory location in the queue which pointer indicates the location in the shared memory of a task control block; setting the contents of the accessed memory location in the queue specified by the value in the read register of the cell to zero; resetting the value of the read register in the cell; testing whether the particular memory location in the queue which was accessed was empty and, if so, notifying said one of the scheduling units of that status; preparing said one of the scheduling units for routing the next read request to the proper cell; returning the value of the retrieved pointer to the requesting processor; and retrieving the task control block from the location in the shared memory specified by the pointer.

Claim 10

A method, performed by a computer system including at least two scheduling units each having at least one cell therein for managing a memory queue associated with that cell and a read register containing a value representing a memory location in that queue, at least one processor for scheduling individual tasks and events, at least one processor for executing such tasks and events and a shared memory having at least one area for storing at least one circular first-in-first-out random access memory queue having multiple memory locations and at least one area for storing at least one task control block, for managing and enabling a requesting processor to retrieve a task control block, comprising the computer-performed steps of: requesting one of the scheduling units to retrieve a pointer to a task control block based on a read request; determining whether there are any valid tasks, pointers to which can be retrieved, and, if not, signaling the absence of such valid tasks and exiting the process; routing the read request to a cell selected on the basis of the mode, parallel or serial, in which such cell is operating if there are valid tasks; accessing a memory location in the queue with which that cell is associated specified by the value contained in the read register of that cell; retrieving a pointer from the accessed memory location in the queue which pointer indicates the location in the shared memory of a task control block; setting the contents of the accessed memory location in the queue specified by the value in the read register of the cell to zero; resetting the value of the read register in the cell; testing whether the particular memory location in the queue which was accessed was empty and, if so, notifying said one of the scheduling units of that status; preparing said one of the scheduling units for routing the next read request to the proper cell; returning the value of the retrieved pointer to the requesting processor; and retrieving the task control block from the location in the shared memory specified by the pointer.

Claim 11

A system for managing one or more scheduling queues which schedule the execution of multiple tasks and events in a distributed multiprocessing computer system comprising: at least one scheduling processing module; at least one other processing module acting in a slave capacity to said scheduling processor module; a shared global memory array including: first realtime hardware scheduler means for managing queues related to tasks and events awaiting processing wherein said scheduler means may operate in either a parallel or a serial mode; and second realtime hardware scheduler means for managing queues related to completed tasks and events wherein said scheduler means may operate in either a parallel or a serial mode; and a first shared memory area for storing task control blocks; a second shared memory area for storing at least one circular random access memory queue managed by one of said scheduler means wherein each said queue is associated either with a particular execution priority level or with a particular external device or application depending on whether the scheduler means managing that queue is operating, respectively, in a parallel or serial mode; a third shared memory area for storing other data; a bus structure interconnecting all of said processing modules and said shared global memory array.

Claim 12

A system for managing one or more scheduling queues which schedule the execution of multiple tasks and events in a distributed multiprocessing computer system comprising: at least one scheduling processing module; at least one other processing module acting in a slave capacity to said scheduling processor module; a shared global memory array including: first realtime hardware scheduler means for managing queues related to tasks and events awaiting processing wherein said scheduler means may operate in either a parallel or a serial mode; and second realtime hardware scheduler means for managing queues related to completed tasks and events wherein said scheduler means may operate in either a parallel or a serial mode; and a first shared memory area for storing task control blocks; a second shared memory area for storing at least one circular random access memory queue managed by one of said scheduler means wherein each said queue is associated either with a particular execution priority level or with a particular external device or application depending on whether the scheduler means managing that queue is operating, respectively, in a parallel or serial mode; a third shared memory area for storing other data; a bus structure interconnecting all of said processing modules and said shared global memory array.