System and method for optimizing dispatch latency of tasks in a data processing system

• US 6,021,425 A
• Filed: 04/03/1992
• Issued: 02/01/2000
• Est. Priority Date: 04/03/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Winters, Scott L., Huynh, Khoa D., Tyler, John G., Giangarra, Paul P., Waldron, Theodore C. III
• Primary Examiner(s): BUTLER, DENNIS
• Application Number:
  US07/862,888
• Time in Patent Office: 2,860 Days
• Field of Search: 395/650, 709/103, 709/107, 709/108
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The invention provides a system and method of enhancing efficiency in a data processing system having a processor, a memory, and a multitasking operating system for managing the processor and the memory. A normal and an expedited scheduling path are provided for scheduling tasks on the processor. The tasks are each assigned a priority for execution on the processor. A queue is provided for the placement of tasks ready for execution. Upon entry into the ready-to-run queue, the execution priority of the new task is compared to the execution priority of the executing task. Responsive to the new task holding a higher execution priority or to absence of an executing task, the expedited scheduling path is invoked. Otherwise the normal scheduling path is invoked.

Claims

1. A method of enhancing task scheduling efficiency in a data processing system having a processor, a memory, and a multitasking operating system for managing the processor and the memory, the method comprising the data processing system implemented steps of:

providing both a first expedited task scheduling path for tasks and a second task scheduling path for tasks in a scheduler within said multitasking operating system, said first expedited task scheduling path implemented in assembly language and having a code sequence for minimizing state chain linking and unlinking and said second task scheduling path including a timer set to terminate a task upon elapse thereof;

assigning an execution priority to each of a plurality of tasks within said data processing system for execution on the processor;

periodically placing selected tasks in a ready-to-run queue within said data processing system;

periodically selecting a task holding a highest execution priority from among said selected tasks in the ready-to-run queue;

determining if a task is executing on the processor;

if a task is executing on the processor, comparing the execution priority of the selected task to the execution priority of the executing task;

responsive to the selected task holding a higher execution priority or to absence of an executing task, processing the selected task for execution on the processor along said first expedited scheduling path; and

processing the selected task for execution on the processor along said second scheduling path responsive to the presence of an executing task holding an execution priority higher than the selected task.

2. A method of enhancing task scheduling efficiency in a data processing system as set forth in claim 1, wherein the step of processing the selected task for execution on the processor along said first expedited scheduling path comprises the steps of:

responsive to presence of an executing task on the processor, placing the executing task within the ready-to-run queue in an optimized manner;

performing a context switch on the processor; and

dispatching the selected task to the processor.

3. A method of task scheduling efficiency in a data processing system as set forth in claim 2, wherein the selected task inherits a timer previously generated for the formerly executing task.

4. A method of enhancing task scheduling efficiency in a data processing system as set forth in claim 1, the method further comprising the steps of:

prior to processing the selected task for execution on the processor along said first expedited scheduling path;

determining if a critical section is in effect for a task from the same process as the selected task;

responsive to an affirmative determination, further determining if the selected task owns the critical section; and

responsive to a negative determination of ownership, placing the selected task into a hold list and returning to the periodic selection step of claim 1.

5. A method of enhancing task scheduling efficiency in a data processing system as set forth in claim 4, the method further comprising the steps of:

prior to selecting a task holding a highest execution priority from among said selected task in the ready-to-run queue;

blocking all external interrupts; and

responsive to presence of a pseudo-system action request, placing a task into the ready-to-run queue.

6. A data processing system comprising:

a processor;

a memory;

a multitasking operating system within said data processing system for managing the processor and the memory;

a scheduler in the multitasking operating system having a first expedited scheduling path for tasks within said data processing system and a second scheduling path for tasks within said data processing system, said first expedited task scheduling path implemented in assembly language and having a code sequence for minimizing state chain linking and unlinking and said second task scheduling path including a timer set to terminate a task upon elapse thereof;

means for assigning an execution priority to each of a plurality of tasks within said data processing system for execution on the processor;

means for periodically placing selected tasks in a ready-to-run queue within said data processing system;

means for periodically selecting a task holding a highest execution priority from among said selected tasks in the ready-to-run queue;

means for determining if a task is executing on the processor;

means responsive to execution of a task on the processor for comparing the execution priority of the selected job to the execution priority of the executing task;

means responsive to the selected task holding a higher execution priority than the executing job or to absence of an executing task on the processor for processing the selected task for execution on the processor along said first expedited scheduling path; and

means processing the selected task for execution on the processor along said second scheduling path responsive to the presence of an executing task holding an execution priority higher than the selected task.

7. A data processing system as set forth in claim 6, wherein said means for processing the selected task for execution on the processor along said first expedited scheduling path comprises:

means responsive to presence of an executing task on the processor for placing the executing task within the ready-to-run queue in an optimized manner;

means for performing a context switch on the processor; and

means for dispatching the selected task to the processor.

8. A data processing system as set forth in claim 7, wherein the selected task inherits a timer previously generated for the formerly executing task.