System and method for using a task starvation indication to prevent starvations of tasks in a multiple processing entity system
View Patent ↗A system, computer program and a method for preventing starvations of tasks in a multiple-processing entity system, the method includes: examining, during each scheduling iteration, an eligibility of each task data structure out of a group of data structures to be moved from a sorted tasks queue to a ready for execution task; updating a value, during each scheduling iteration, of a queue starvation watermark value of each task data structure that is not eligible to move to a running tasks queue, until a queue starvation watermark value of a certain task data structure out of the group reaches a queue starvation watermark threshold; and generating a task starvation indication if during an additional number of scheduling iterations, the certain task data structure is still prevented from being moved to a running tasks queue, and the additional number is responsive to a task starvation watermark.
1. A method for preventing starvations of tasks in a multiple-processing entity system, the method comprising:
moving a task data structure of a group of data structures in a pending tasks queue to a sorted tasks queue when all pre-requisites for the task data structure are fulfilled;
determining whether the sorted tasks queue is frozen;
sorting task data structures within the sorted tasks queue in response to the sorted tasks queue being unfrozen, during each of a plurality of scheduling iterations, according to values of the task data structure from multiple sorting rules, wherein each sorting rule is either an ascending sorting rule or a descending sorting rule;
examining, during each of the scheduling iterations, an eligibility of the task data structure to be moved from the sorted tasks queue to a running tasks queue;
updating a value, during the each of the scheduling iterations, of a queue starvation watermark value of the task data structure when the task data structure is not eligible to move from the sorted tasks queue to the running tasks queue, until a queue starvation watermark value of the task data structure reaches a queue starvation watermark threshold;
generating a task starvation indication if during an additional number of scheduling iterations, the certain task data structure is still prevented from being moved to the running tasks queue, wherein the additional number of scheduling iterations is responsive to a task starvation watermark; and
performing, in response to the task starvation indication, one or more actions selected from a list of actions:
(a) sending an interrupt request to at least two processing entities in the multiple-processing entity system;
(b) sending the task starvation indication to at least one processing entity in the multiple-processing entity system; and
(c) sending the interrupt request to all processing entities in the multiple-processing entity system.
2. The method according to claim 1 comprising determining that a task data structure is not eligible to move to the running tasks queue that is associated with the sorted tasks queue if the running tasks queue is full or if at least one pre-requisite to a provision of the task data structure to the associated running tasks queue is not fulfilled.
3. The method according to claim 1 wherein the group of data structures comprises a head of queue task data structure per each sorted tasks queue.
4. The method according to claim 1 comprising receiving sorting rules indicators that indicate, for each sorting rule, whether the sorting rule is an ascending sorting rule or a descending sorting rule.
5. The method according to claim 1 comprising freezing sorted tasks queues other than the sorted tasks queue that stores the certain task data structure.
6. The method according to claim 1 comprising sorting task data structures in response to the sorted tasks queue being unfrozen, during each of the scheduling iterations, according to hierarchical sorting rules.
7. The method of claim 1 , wherein the action performed is:
sending the interrupt request to at least two processing entities in the multiple-processing entity system.
8. The method of claim 1 , wherein the action performed is:
sending the task starvation indication to at least one processing entity in the multiple-processing entity system.
9. The method of claim 1 , wherein the action performed is:
sending the interrupt request to all processing entities in the multiple-processing entity system.
10. A system for preventing starvations of tasks, the system comprising:
multiple hardware processor entities adapted to process tasks; and
a scheduler adapted to schedule an execution of tasks, wherein the scheduler is further adapted to:
move a task data structure of a group of data structures in a pending tasks queue to a sorted tasks queue when all pre-requisites for the task data structure are fulfilled;
determine whether the sorted tasks queue is frozen;
sorting task data structures within the sorted tasks queue in response to the sorted tasks queue being unfrozen, during each of a plurality of scheduling iterations, according to values of the task data structure from multiple sorting rules, wherein each sorting rule is either an ascending sorting rule or a descending sorting rule;
examine, during each of the scheduling iterations, an eligibility of the task data structure out of a group of data structures to be moved from the sorted tasks queue to a running tasks queue;
update a value, during each of the scheduling iterations, of a queue starvation watermark value of the task data structure when the task data structure is not eligible to move from the sorted tasks queue to the running tasks queue, until a queue starvation watermark value of the task data structure reaches a queue starvation watermark threshold;
generate a task starvation indication if during an additional number of scheduling iterations, the task data structure is still prevented from being moved to the running tasks queue, wherein the additional number is responsive to a task starvation watermark; and
perform, in response to the task starvation indication, one or chore actions selected from a list of actions:
(a) send an interrupt request to at least two processing entities in the multiple-processing entity system;
(b) send the task starvation indication to at least one processing entity in the multiple-processing entity system; and
send the interrupt request to all processing entities in the multiple-processing entity system.
11. The system according to claim 10 wherein the scheduler is adapted to determine that a task data structure is not eligible to move to the running tasks queue that is associated with the sorted tasks queue if the running tasks queue is full or if at least one pre-requisite to a provision of the task data structure to the associated running tasks queue is not fulfilled.
12. The system according to claim 10 wherein the group of data structures comprises a head of queue task data structure per each sorted tasks queue.
13. The system according to claim 10 wherein the scheduler is adapted to sort rules indicators that indicate, for each sorting rule, whether the sorting rule is an ascending sorting rule or a descending sorting rule.
14. The system according to claim 10 wherein the scheduler is adapted to sort task data structures in response to the sorted tasks queue being unfrozen, during each of the scheduling iterations, according to hierarchical sorting rules.
15. The system according to claim 10 wherein the scheduler is adapted to freeze sorted tasks queues other than a sorted tasks queue that stores the certain task data structure.
16. The system of claim 10 , wherein the action performed is:
sending the interrupt request to at least two processing entities in the multiple-processing entity system.
17. The system of claim 10 , wherein the action performed is:
sending the task starvation indication to at least one processing entity in the multiple-processing entity system.
18. The system of claim 10 , wherein the action performed is:
sending the interrupt request to all processing entities in the multiple-processing entity system.
19. A non-transitory computer program product that comprises a computer readable medium that stores instructions for:
moving a task data structure of a group of data structures in a pending tasks queue to a sorted tasks queue when all pre-requisites for the task data structure are fulfilled;
determining whether the sorted tasks queue is frozen;
sorting task data structures within the sorted tasks queue in response to the sorted tasks queue being unfrozen, during each of a plurality of scheduling iterations, according to values of the task data structure from multiple sorting rules, wherein each sorting rule is either an ascending sorting rule or a descending sorting rule;
examining, during each of the scheduling iterations, an eligibility of the task data structure to be moved from the sorted tasks queue to a running tasks queue;
updating a value, during the each of the scheduling iterations, of a queue starvation watermark value of the task data structure when the task data structure is not eligible to move from the sorted tasks queue to the running tasks queue, until a queue starvation watermark value of the task data structure reaches a queue starvation watermark threshold;
generating a task starvation indication if during an additional number of scheduling iterations, the task data structure is still prevented from being moved to the running tasks queue, wherein the additional number of scheduling iterations is responsive to a task starvation watermark; and
performing, in response to the task starvation indication, one or more actions selected from a list of actions:
(a) sending an interrupt request to at least two processing entities in the multiple-processing entity system;
(b) sending the task starvation indication to at least one processing entity in the multiple-processing entity system; and
(c) sending the interrupt request to all processing entities in the multiple-processing entity system.
20. The computer program product according to claim 19 comprising instructions for receiving sorting rules indicators that indicate, for each sorting rule, whether the sorting rule is an ascending sorting rule or a descending sorting rule.
21. The computer program product according to claim 19 comprising instructions for sorting task data structures within each unfrozen sorted tasks queue, during each of the scheduling iterations, according to hierarchical sorting rules.
22. The computer program product according to claim 19 comprising instructions for freezing sorted tasks queues other than a sorted tasks queue that stores the certain task data structure.
23. The computer program product of claim 19 , wherein the action performed is:
sending the interrupt request to at least two processing entities in the multiple-processing entity system.
24. The computer program product of claim 19 , wherein the action performed is:
sending the task starvation indication to at least one processing entity in the multiple-processing entity system.
25. The computer program product of claim 19 , wherein the action performed is:
sending the interrupt request to all processing entities in the multiple-processing entity system.