Systems and methods for multi-tasking, resource sharing, and execution of computer instructions
View Patent ↗In a multi-tasking pipelined processor, consecutive instructions are executed by different tasks, eliminating the need to purge an instruction execution pipeline of subsequent instructions when a previous instruction cannot be completed. The tasks do not share registers which store task-specific values, thus eliminating the need to save or load registers when a new task is scheduled for execution. If an instruction accesses an unavailable resource, the instruction becomes suspended, allowing other tasks' instructions to be executed instead until the resource becomes available. Task scheduling is performed by hardware; no operating system is needed. Simple techniques are provided to synchronize shared resource access between different tasks.
1. In a multi-tasking computer system comprising a plurality of resources to be shared by a plurality of tasks, a circuit for allocating each resource to the tasks in a continuous operation so that in said operation, after any one of the tasks has finished accessing any one of the resources in processing a data unit, said one of the tasks does not get access to the same resource until after every other one of the tasks has finished accessing the resource;
wherein accessing any one of said resources by any one of said tasks comprises:
(1) the task attempting to access the resource, wherein attempting to access the resource comprises generating a signal indicating that the task is attempting to access the resource;
(2) in response to the operation (1), the circuit allowing the task to access the resource if the resource is available to the task, the circuit not allowing the task to access the resource until the resource becomes available to the task;
(3) the task accessing the resource when the circuit allows the task to access the resource;
wherein for any task T 1 of said tasks and any resource R 1 of said resources, if the task T 1 attempts to access the resource R 1 after the task T 1 has already finished accessing the resource R 1 , and at least one other task T 2 has not attempted to access the resource R 1 after the task T 1 has finished accessing the resource R 1 , then the circuit will never allow the task T 1 to access the resource R 1 in said operation until the task T 2 attempts to access the resource R 1 and accesses the resource R 1 in said operation.
2. The circuit of claim 1 wherein for at least one resource, each task starts accessing the resource by locking the resource to make it unavailable to any other task, and the task finishes accessing the resource by unlocking the resource.
3. The circuit of claim 1 wherein each data unit is processed by a single one of the tasks which accesses at least two of said resources to process at least one of the data units.
4. The circuit of claim 3 wherein said at least two resources are storage areas each of which is to store data unit processing information of multiple data units.
5. The circuit of claim 4 wherein one of the storage areas is a request FTFO for storing requests to process data units, and another one of the storage areas is a command FIFO for storing commands for processing of the data units;
wherein for each data unit, one of the tasks reads a request from the request FILFO and, if one or more commands are to be written to the command FIFO for the data unit, said one of the tasks writes the one or more commands to the command FIFO.
6. The circuit of claim 5 wherein each request contains an address of a corresponding data unit.
7. The circuit of claim 4 wherein at least some of the data units are received over a network, wherein one of the storage areas is a request FIFO for storing requests to process the data units, and another of the storage areas is a status FIFO for storing status information on reception of the data units over the network;
wherein for each data unit, one of the tasks reads a request from the request FIFO and reads the status information from the status FIFO.
8. The circuit of claim 4 wherein in each said storage area, the data processing information is associated with an order of data units, the order being the same for each said storage area.
9. The circuit of claim 3 wherein in processing each of said data units, the corresponding one of the tasks accesses the resources one after another in a predefined sequence.
10. The circuit of claim 1 wherein in said operation, at least one of the resources is accessed multiple times by each of said tasks.
11. A method for sharing a plurality of resources by a plurality of computer tasks in a continuous operation, the method comprising each of said tasks accessing each of said resources in said operation;
wherein accessing any one of said resources by any one of said tasks comprises:
(1) the task generating a signal indicating that the task is attempting to access the resource;
(2) in response to the operation (1), allowing the task to access the resource if the resource is available to the task, but not allowing the task to access the resource until the resource becomes available to the task;
(3) the task accessing the resource when allowed to access the resource;
wherein for any task T 1 of said tasks and any resource R 1 of said resources, if the task T 1 attempts to access the resource R 1 after the task T 1 has already finished accessing the resource R 1 , and at least one other task T 2 has not attempted to access the resource R 1 after the task T 1 has finished accessing the resource R 1 , then the circuit will never allow the task T 1 to access the resource R 1 in said operation until the task T 2 attempts to access the resource R 1 and accesses the resource R 1 in said operation.
12. The method of claim 11 wherein for at least one resource, each task starts accessing the resource by locking the resource to make it unavailable to any other task, and the task finishes accessing the resource by unlocking the resource.
13. The method of claim 11 wherein each data unit is processed by a single one of the tasks which accesses at least two of said resources to process at least one of the data units.
14. The method of claim 13 wherein said at least two resources are storage areas each of which is to store data unit processing information of multiple data units.
15. The method of claim 14 wherein one of the storage areas is a request FIFO for storing requests to process data units, and another one of the storage areas is a command FIFO for storing commands for processing of the data units;
wherein for each data unit, one of the tasks reads a request from the request FIFO and, if one or more commands are to be written to the command FIFO for the data unit, said one of the tasks writes the one or more commands to the command FIFO.
16. The method of claim 15 wherein each request contains an address of a corresponding data unit.
17. The method of claim 14 wherein at least some of the data units are received over a network, wherein one of the storage areas is a request FIFO for storing requests to process the data units, and another of the storage areas is a status FIFO for storing status information on reception of the data units over the network;
wherein for each data unit, one of the tasks reads a request from the request FIFO and reads the status information from the status FIFO.
18. The method of claim 14 wherein in each said storage area, the data processing information is stored in association with an order of data units, the order being the same for each said storage area.
19. The method of claim 14 wherein in processing each of said data units, the corresponding one of the tasks accesses the resources one after another in a predefined sequence.
20. The method of claim 11 wherein at least one of the resources is accessed multiple times by each of said tasks.
21. In a multi-tasking computer system comprising a plurality of resources to be shared by a plurality of tasks, a circuit for allocating each resource to the tasks so that after any one of the tasks has finished accessing any one of the resources in processing a data unit, said one of the tasks does not get access to the same resource until after every other one of the tasks has finished accessing the resource;
wherein accessing any one of said resources by any one of said tasks comprises:
(1) the task attempting to access the resource, wherein attempting to access the resource comprises generating a signal indicating that the task is attempting to access the resource;
(2) in response to the operation (1), the circuit allowing the task to access the resource if the resource is available to the task, the circuit not allowing the task to access the resource until the resource becomes available to the task;
(3) the task accessing the resource when the circuit allows the task to access the resource;
wherein for any task T 1 of said tasks and any resource R 1 of said resources, if the task T 1 attempts to access the resource R 1 after the task T 1 has already finished accessing the resource R 1 , and at least one other task T 2 has not attempted to access the resource R 1 after the task T 1 finished accessing the resource R 1 , then the circuit does not allow the task T 1 to access the resource R 1 until the circuit obtains an indication of one or more conditions including a condition that every task other than T 1 has finished accessing the resource R 1 after the task T 1 accessed the resource R 1 , the circuit being responsive to said indication to allow the task T 1 to access the resource R 1 .
22. The circuit of claim 21 wherein in said operation, at least one of the resources is accessed multiple times by each of said tasks.
23. The circuit of claim 21 wherein each data unit is processed by a single one of the tasks which accesses the resources one after another in a predefined sequence in processing the data unit.
24. A method for sharing a plurality of resources by a plurality of computer tasks, the method comprising each of said tasks accessing each of said resources;
wherein accessing any one of said resources by any one of said tasks comprises:
(1) the task generating a signal indicating that the task is attempting to access the resource;
(2) in response to the operation (1), allowing the task to access the resource if the resource is available to the task, but not allowing the task to access the resource until the resource becomes available to the task;
(3) the task accessing the resource when allowed to access the resource;
wherein for any task T 1 of said tasks and any resource R 1 of said resources, if the task T 1 attempts to access the resource R 1 after the task T 1 has already finished accessing the resource R 1 , and at least one other task T 2 has not attempted to access the resource R 1 after the task T 1 finished accessing the resource R 1 , then the circuit does not allow the task T 1 to access the resource R 1 until the circuit obtains an indication of one or more conditions including a condition that every task other than T 1 has finished accessing the resource R 1 after the task T 1 accessed the resource R 1 , the circuit being responsive to said indication to allow the task T 1 to access the resource R 1 .
25. The method of claim 24 wherein at least one of the resources is accessed multiple times by each of said tasks.
26. The method of claim 25 wherein each data unit is processed by a single one of the tasks which accesses the resources one after another in a predefined sequence in processing the data unit.