US5247675A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Preemptive and non-preemptive scheduling and execution of program threads in a multitasking operating system
Assignee: International Business Machines Corp
•
Filing: 1991-08-09
•
Granted: 1993-09-21
•
Expires: 2011-08-09
Abstract
Abstract A multitasking operating system permits application programs (and their developers) to influence a schedule of execution of program threads which constitute the application programs by specifying parameters for the program threads. The parameters indicate each thread's priority level and dispatch class in which the thread resides. The application programs specify the thread's parameters based on the following principles of the operating system. The operating system queues the highest priority thread 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. While this thread is dispatchable and being executed, no other thread from the same dispatch class can preempt it unless this executing thread voluntarily relinquishes control of the processor, even if the other thread has a higher priority. (This other thread would have been created or made available after the currently executing thread was selected for the run list.) However, the currently executing thread can be involuntarily preempted at any time by another higher priority, available thread from a different dispatch class. A thread can also voluntarily relinquish control of its processor at other appropriate points in the execution, for example, when data structures are valid, to share the processor with other lower priority threads from the same or different dispatch classes.
Inventors
- 👤 Joel A. Farrell
- 👤 Stephen E. Record
- 👤 Brian K. Wade
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 14:11
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
419 words
A computer system for scheduling execution of program threads of one or more application programs based on parameters specified by the application program(s) and executing the scheduled program threads, said system comprising: at least one processor; first means, responsive to specifications by said application program(s) that one plurality of said program threads is assigned to one class and another plurality of said program threads is assigned to another class, for storing indications that said one plurality of program threads is assigned to said one class and said other plurality of program threads is assigned to said other class; second means, responsive to specifications by said application program(s) of a priority level for each of said program threads, for storing an indication of the priority level of each of said program threads; third means, responsive to specification by an application program or program thread that a program thread is unavailable for execution, for storing an indication that said program thread is unavailable for execution and responsive to a specification by an application program or another program thread that said program thread is available for execution, for storing an indication that said program thread is available for execution; and means, coupled to the first, second and third storing means and said processor processors, for selecting the highest priority available program thread from each of said classes for execution by said processor or processors and scheduling said selected program threads for execution by said processor or processors in order of priority level such that the highest priority, selected program thread is executed first; and wherein the selecting and scheduling means includes means for preempting execution of a program thread from either of said classes with a higher priority level program thread from the other class, said higher priority level program thread from said other class being made available or assigned to said other class after selection by the selecting means of another program thread from said other class with a lower priority than the executing program thread, said selecting means subsequently selecting said higher priority program thread from said other class in place of said lower priority program thread from said other class for execution by the processor; and means for preventing a program thread in said one class, which was made available or assigned to said one class 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 selected program thread from said one class.
Claim 2
Dependent Claim
419 words
A computer system for scheduling execution of program threads of one or more application programs based on parameters specified by the application program(s) and executing the scheduled program threads, said system comprising: at least one processor; first means, responsive to specifications by said application program(s) that one plurality of said program threads is assigned to one class and another plurality of said program threads is assigned to another class, for storing indications that said one plurality of program threads is assigned to said one class and said other plurality of program threads is assigned to said other class; second means, responsive to specifications by said application program(s) of a priority level for each of said program threads, for storing an indication of the priority level of each of said program threads; third means, responsive to specification by an application program or program thread that a program thread is unavailable for execution, for storing an indication that said program thread is unavailable for execution and responsive to a specification by an application program or another program thread that said program thread is available for execution, for storing an indication that said program thread is available for execution; and means, coupled to the first, second and third storing means and said processor processors, for selecting the highest priority available program thread from each of said classes for execution by said processor or processors and scheduling said selected program threads for execution by said processor or processors in order of priority level such that the highest priority, selected program thread is executed first; and wherein the selecting and scheduling means includes means for preempting execution of a program thread from either of said classes with a higher priority level program thread from the other class, said higher priority level program thread from said other class being made available or assigned to said other class after selection by the selecting means of another program thread from said other class with a lower priority than the executing program thread, said selecting means subsequently selecting said higher priority program thread from said other class in place of said lower priority program thread from said other class for execution by the processor; and means for preventing a program thread in said one class, which was made available or assigned to said one class 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 selected program thread from said one class.
Claim 3
Dependent Claim
94 words
A computer system as set forth in claim 1 wherein the scheduling means creates a run list of the selected program threads and orders said selected program threads on said run list for execution based on priority level; and further comprising means, responsive to a specification by an application program of a number greater than one of the program threads from said one class for representation on said run list, for selecting said number greater than one of the highest priority, available program threads from said one class for representation on said run list.
Claim 4
Dependent Claim
92 words
A computer system as set forth in claim 1 wherein the scheduling means creates a run list of the selected program threads and orders said selected program threads on said run list for execution based on priority level; and the preventing means prevents selection for said run list of the program thread in said one class which was made available or assigned to said one class after selection by the selecting means of the other, lower priority program thread from said one class, before execution of said other, lower priority program thread.
Claim 5
Dependent Claim
31 words
A computer system as set forth in claim 1 wherein the preventing means prevents more than one program thread from any class from being scheduled for execution at any one time.
Claim 6
Dependent Claim
53 words
A computer system as set forth in claim 2 wherein said system comprises said number of said processors, and further comprising means, coupled to one or more of said processors, for selecting said number of the highest priority, available program threads from said one class for execution on said number of said processors.
Claim 7
Dependent Claim
93 words
A computer system as set forth in claim 1 further comprising means, responsive to a request by an executing program thread to cease execution, for ceasing execution of said program thread; and wherein the third means responds to said request by storing an indication that said program thread is unavailable for execution; and the selecting and scheduling means responds to said request to cease execution of said currently executing program thread, by selecting for subsequent execution the highest priority, available program thread from the same class as the program thread which ceases execution.
Claim 8
Independent Claim
390 words
A method for scheduling execution of program threads of one or more application programs based on parameters specified by the application program(s) and executing the scheduled program threads on one or more computer processors, said method comprising the steps of: receiving specifications by said application program(s) that one plurality of said program threads is assigned to one class and another plurality of said program threads is assigned to another class, and in response, storing indications that said one plurality of program threads is assigned to said one class and said other plurality of program threads is assigned to said other class; receiving specifications by said application program(s) of a priority level for each of said program threads, and in response, storing an indication of the priority level of each of said program threads; receiving specification by an application program or program thread that a program thread is unavailable for execution, and in response, storing an indication that said program thread is unavailable for execution and receiving a specification by an application program or another program thread that said program thread is available for execution, and in response, storing an indication that said program thread is available for execution; selecting the highest priority available program thread from each of said classes for execution by said processor or processors and scheduling said selected program threads for execution by said processor or processors in order of priority level such that the highest priority, selected program thread is executed first; preempting execution of a program thread from either of said classes with a higher priority level program thread from the other class, said higher priority level program thread from said other class being made available or assigned to said other class after selection by the selecting means of another program thread from said other class with a lower priority than the executing program thread; subsequent to said preempting step, selecting said higher priority program thread from said other class in place of said lower priority program thread from said other class for execution by the processor; and preventing a program thread in said one class, which was made available or assigned to said one class after selection of another, lower priority program thread from said one class of execution, form preempting execution of said other, lower priority selected program thread from said one class.
Claim 9
Independent Claim
390 words
A method for scheduling execution of program threads of one or more application programs based on parameters specified by the application program(s) and executing the scheduled program threads on one or more computer processors, said method comprising the steps of: receiving specifications by said application program(s) that one plurality of said program threads is assigned to one class and another plurality of said program threads is assigned to another class, and in response, storing indications that said one plurality of program threads is assigned to said one class and said other plurality of program threads is assigned to said other class; receiving specifications by said application program(s) of a priority level for each of said program threads, and in response, storing an indication of the priority level of each of said program threads; receiving specification by an application program or program thread that a program thread is unavailable for execution, and in response, storing an indication that said program thread is unavailable for execution and receiving a specification by an application program or another program thread that said program thread is available for execution, and in response, storing an indication that said program thread is available for execution; selecting the highest priority available program thread from each of said classes for execution by said processor or processors and scheduling said selected program threads for execution by said processor or processors in order of priority level such that the highest priority, selected program thread is executed first; preempting execution of a program thread from either of said classes with a higher priority level program thread from the other class, said higher priority level program thread from said other class being made available or assigned to said other class after selection by the selecting means of another program thread from said other class with a lower priority than the executing program thread; subsequent to said preempting step, selecting said higher priority program thread from said other class in place of said lower priority program thread from said other class for execution by the processor; and preventing a program thread in said one class, which was made available or assigned to said one class after selection of another, lower priority program thread from said one class of execution, form preempting execution of said other, lower priority selected program thread from said one class.
Claim 10
Dependent Claim
96 words
A method as set forth in claim 7 wherein the scheduling step creates a run list of the selecting program threads and orders said selected program threads on said run list for execution based on priority level; and further comprising the steps of receiving a specification by an application program of a number greater than one of the program threads from said one class for representation on said run list, and in response, selecting said number greater than one of the highest priority, available program threads from said one class for representation on said run list.
Claim 11
Dependent Claim
87 words
A method as set forth in claim 7 wherein the scheduling step creates a run list of the selected program threads and orders said selected program threads on said run list for execution based on priority level; and the preventing step prevents selection for said run list of the program thread in said one class which was made available or assigned to said one class after selection of the other, lower priority program thread from said one class, before execution of said other, lower priority program thread.
Claim 12
Dependent Claim
30 words
A method as set forth in claim 7 wherein the preventing step prevents more than one program thread from any class from being scheduled for execution at any one time.
Claim 13
Dependent Claim
34 words
A method as set forth in claim 8 further comprising the step of selecting said number of the highest priority, available program threads from said one class for execution on said number of processors.
Claim 14
Dependent Claim
66 words
A method as set forth in claim 7 further comprising the step of: receiving a request by an executing program thread to cease execution, and in response, ceasing execution of said program thread, storing an indication that said program thread is unavailable for execution, and selecting for subsequent execution the highest priority, available program thread from the same class as the program thread which ceases execution.
References Cited (Backward Citations)
US3614745A
Cited
US3662401A
Cited
US4395757A
Cited
US4394725A
Cited
US4103330A
Cited
US4369494A
Cited
US4152761A
Cited
US4145735A
Cited
US4286322A
Cited
US4590555A
Cited
US4333144A
Cited
US4318173A
Cited
US4493022A
Cited
US4468736A
Cited
US4800521A
Cited
US4901230A
Cited
US4661900A
Cited
US4512628A
Cited
US4794526A
Cited
US4658351A
Cited
US4642756A
Cited
CA1277426C
Cited
US4954948A
Cited
US5001666A
Cited
EP0332148A2
Cited
WO1989009964A1
Cited
US4974159A
Cited
US4985831A
Cited
EP0381655A2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-20 | 1997-03-22 | 1997-09-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-20 | 2001-03-22 | 2001-09-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-20 | 2005-03-22 | 2005-09-21 | $7700.00 | Window Closed / Lapsed |