Controlled scheduling of program threads in a multitasking operating system

• US 5,630,128 A
• Filed: 08/09/1991
• Issued: 05/13/1997
• Est. Priority Date: 08/09/1991
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Farrell, Joel A., Wade, Brian K., Record, Stephen E.
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US07/743,541
• Time in Patent Office: 2,104 Days
• Field of Search: 395/650, 395/275, 395/725
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A multitasking operating system permits application programs (and their developers) to influence a schedule of execution of program threads derived from the application programs. Each of the program threads is assigned a priority level and a dispatch class in which the thread resides. Based on these parameters, the operating system schedules the threads for execution in the following manner. The operating system queues the highest priority thread which is available for execution from each dispatch class onto a run list for execution by a processor. The highest priority thread on the run list is executed first. An application program thread can change the dispatch class in which another program thread resides. An executing program thread can also voluntarily yield to a specified program thread in the same dispatch class or permit the highest priority available thread in the same dispatch class to be queued on the run list with itself being available and in contention for the run list.

Claims

1. A multitasking operating system comprising:

means for receiving from one or more application program threads specification of classes in which a multiplicity of application program threads reside and assigning said multiplicity of application program threads to classes based on said specification, wherein at least one of said classes can be assigned a plurality of program threads;

means for assigning priority levels to said program threads;

means for scheduling execution of said program threads such that the highest priority program thread in each of said classes which is available for execution is selected for execution before a lower priority program thread which is available for execution in the same class; and

means, responsive to a request from one of said application program threads which is executing to halt execution of said one program thread and select for execution a particular application program thread which is specified in said request and available for execution from the same class, for complying with said request, and wherein there is another application program thread, in addition to said particular program thread and said one program thread, which is available for execution from said same class and has a higher priority than said particular program thread.

2. A multitasking operating system as set forth in claim 1 wherein the means for assigning priority levels to the program threads base the assignments on priority levels specified by one or more application programs.

3. A multitasking operating system as set forth in claim 1 wherein the scheduling means queues the selected program threads for execution in an order based on the relative priorities of said selected program threads.

4. A multitasking operating system as set forth in claim 1 wherein the scheduling means permits a program thread which is assigned to a class to preempt execution of a lower priority program thread which is assigned to a different class.

5. A multitasking operating system as set forth in claim 1 wherein the scheduling means prevents a program thread in said one class which is available for execution from preempting execution of another, lower priority program thread in said one class.

6. A method for operating a computer, said method comprising the steps of:

receiving from one or more application programs specification of classes in which a multiplicity of application program threads reside

assigning said application program threads to classes based on said specification, each class being assigned at least one program thread, and at least one class being assigned a plurality of program threads;

assigning a priority to each of said program threads;

queuing the highest priority program thread which is available for execution from each class onto a queue for execution without queuing a lower priority program thread which is available for execution in the same class; and

complying with a request from one of said application program threads which is executing to halt execution of said one program thread, select a particular application program thread which is specified in said request and available for execution from the same class and queue said particular application program thread on said queue; and

wherein

there is another program thread in said same class which is available for execution and has a higher priority than said particular program thread.

7. A method as set forth in claim 6 wherein said multiplicity of program threads are assigned priority levels as specified by application programs.

8. A method as set forth in claim 6 further comprising the steps of:

executing one of the program threads from said queue; and

after executing at least part of said one thread from said queue, preempting execution of said one program thread with a program thread in said queue from another class.

9. A method as set forth in claim 6 further comprising the steps of:

executing one of the program threads from said queue; and

preventing another one of the program threads which is available for execution, has a higher priority than the executing program thread, and is in the same class as the executing program thread from preempting execution of the executing program thread.

10. A computer system comprising:

means for assigning a multiplicity of application program threads to a plurality of classes based on corresponding specifications from one or more application programs, wherein each of said classes is assigned at least one program thread and at least one of said classes can be assigned a plurality of program threads;

at least one processor;

means for assigning a priority level to each of said program threads to affect execution order;

means for selecting at least one available program thread from each of said classes for execution by said processor or processors before a lower priority program thread which is available for execution from the same class, said selection being based at least in part on relative priority levels of the program threads within each of said classes; and

means, responsive to a request from one of said application program threads which is executing to halt execution of said one application program thread, select a particular application program thread which is specified in said request and available for execution from the same class, and queue said particular application program thread on said queue, for complying with said request, and wherein the halted program thread is available for execution; and

there is another program thread in said same class which is available for execution and has a higher priority than said particular program thread.

11. A computer system as set forth in claim 10 wherein said multiplicity of program threads are assigned priority levels as specified by application programs.

12. A computer system as set forth in claim 10 further comprising:

means for preempting execution of a program thread from any of said classes with a higher priority level program thread from another class which is available for execution.

13. A computer system as set forth in claim 10 further comprising:

means for preventing a program thread in said one class, which was made available after selection by the selecting means of another, lower priority program thread from said one class for execution, from preempting execution of said other, lower priority program thread in said one class.

14. A computer system as set forth in claim 10 wherein said particular program thread is from a same application program as said one program thread.

15. A computer system as set forth in claim 10 further comprising means, responsive to a subsequent request by an application program thread to delete said particular program thread, for deleting said particular program thread.

16. A computer system as set forth in claim 10 wherein said particular program thread executes multiple transactions without becoming unavailable to execute during or between said transactions.