METHOD AND SYSTEM FOR SIMULATING A MULTI-QUEUE SCHEDULER USING A SINGLE QUEUE ON A PROCESSOR

• US 20090113432A1
• Filed: 10/24/2007
• Published: 04/30/2009
• Est. Priority Date: 10/24/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Singh, Balbir, Srivatsa, Vaddagiri
• Granted Patent: US 8,117,621 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method and system for scheduling tasks on a processor, the tasks being scheduled by an operating system to run on the processor in a predetermined order, the method comprising identifying and creating task groups of all related tasks; assigning the tasks in the task groups into a single common run-queue; selecting a task at the start of the run-queue; determining if the task at the start of the run-queue is eligible to be run based on a pre-defined timeslice allocated and on the presence of older starving tasks on the runqueue; executing the task in the pre-defined time slice; associating a starving status to all unexecuted tasks and running all until all tasks in the run-queue complete execution and the run-queue become empty.

Claims

1. A method for simulating a multi-queue group scheduler for scheduling tasks on a processor, the tasks being scheduled by an operating system to run on the processor in a predetermined order, the method comprising:

(a) identifying and creating task groups of all related tasks;

(b) assigning the tasks in the task groups into a single common run-queue;

(c) selecting a task at the start of the run-queue;

(d) determining if the task at the start of the run-queue is eligible to be run based on a pre-defined timeslice allocated and if presence of other older starving tasks in the runqueue are eligible to run;

(e) executing the task in the pre-defined time slice;

(f) repeating steps (a)-(e) until all tasks in the run-queue are executed and the run-queue become empty.

2. The method of claim 1, wherein on determining that the task at the start of the run-queue is eligible to run, further comprising:

renewing the task timeslice if the task timeslice is zero.

3. The method of claim 1, further comprising:

monitoring the processor usage while the task is being run.

4. The method of claim 3, wherein upon determining that the task running has consumed the allocated group timeslice:

terminating further execution of the task;

associating a starving identifier (starve_id) to the terminated task; and

moving the terminated task to the end of the run-queue.

5. The method of claim 3, wherein upon determining that the task running has consumed the allocated task timeslice:

terminating further execution of the task;

clearing the starving identifier of the terminated task; and

moving the terminated task to the end of the run-queue, with its task timeslice field remaining at 0.

6. The method of claim 1, wherein upon negative determination in step (d) associating a starving identifier to the task;

moving the task with the starving status to the end of the run-queue; and

selecting the next task at the start of the run-queue for execution.

7. The method of claim 1, wherein the timeslice includes a task timeslice or a group timeslice.

8. The method of claim 1, wherein a user can create task groups by selectively assigning tasks to the task groups.

9. The method of claim 1, wherein determining a task to execute/run comprising:

renewing the timeslice for all task groups if all task groups have expired the allocated timeslice or of there are no tasks in the run-queue associated with the task groups whose task group has not completed the allocated timeslice.

10. A system comprising a processor comprising tasks being scheduled by an operating system to run on the processor in a predetermined order, wherein the system is configured to perform:

(a) identifying and creating task groups of all related tasks;

(b) assigning the tasks in the task groups into a single common run-queue;

(c) selecting a task at the start of the run-queue;

(d) determining if the task at the start of the run-queue is eligible to be run based on a pre-defined timeslice allocated and if presence of other older starving tasks in the runqueue are eligible to run, the timeslice including a task timeslice or a group timeslice;

(e) executing the task in the pre-defined time slice;

(f) repeating steps (a)-(e) until all tasks in the run-queue are executed and the run-queue become empty.

11. The system of claim 10, wherein upon determining that the task at the start of the run-queue is eligible to run, further comprising:

renewing the task timeslice if the task timeslice is zero; and

monitoring the processor usage while the task is being run.

12. The system of claim 11, wherein upon determining that the task running has consumed the allocated group timeslice:

terminating further execution of the task;

associating a starving identifier (starve_id) to the terminated task; and

moving the terminated task to the end of the run-queue.

13. The system of claim 11, wherein upon determining that the task running has consumed the allocated task timeslice:

terminating further execution of the task;

clearing the starving identifier of the terminated task;

moving the terminated task to the end of the run-queue, with its task timeslice field remaining at 0;

clearing all terminated tasks associated with the starving status; and

repeating until all tasks in the run-queue are executed and the run-queue is empty.

14. The system of claim 10, wherein upon negative determination in step (d):

associating a starving status to the task;

moving the task with the starving status to the end of the run-queue; and

selecting the next task at the start of the run-queue for execution.

15. The system of claim 10, wherein determining a task to execute/run comprises:

renewing the timeslice for all task groups if all task groups have expired the allocated timeslice or of there are no tasks in the run-queue associated with the task groups whose task group has not completed the allocated timeslice.