US5812844A — Method and system for scheduling the execution of…

Claim 1

Independent Claim 182 words

A method in a computer system for scheduling the use of a limited resource of the computer system by a plurality of consumer entities, the method comprising the steps of: (a) receiving for each consumer entity either a time-general scheduling constraint, indicating that the consumer entity should be able to use the resource for a specified share of a total time that the resource is available, or a time-specific scheduling constraint, indicating that the consumer entity should be permitted to use the resource for a specified total period of time by a specified time deadline; (b) for each consumer entity for which is received a time-general scheduling constraint, determining a restart time corresponding to the time-general scheduling constraint based on the share specified by the time-general scheduling constraint; (c) for each consumer entity for which is received a time-specific scheduling constraint, determining a restart time corresponding to the time-specific scheduling constraint based on the total period of time and the deadline specified by the time-specific scheduling constraint; and (d) selecting the consumer entity having the earliest restart time to use the resource.

Claim 2

Independent Claim 182 words

A method in a computer system for scheduling the use of a limited resource of the computer system by a plurality of consumer entities, the method comprising the steps of: (a) receiving for each consumer entity either a time-general scheduling constraint, indicating that the consumer entity should be able to use the resource for a specified share of a total time that the resource is available, or a time-specific scheduling constraint, indicating that the consumer entity should be permitted to use the resource for a specified total period of time by a specified time deadline; (b) for each consumer entity for which is received a time-general scheduling constraint, determining a restart time corresponding to the time-general scheduling constraint based on the share specified by the time-general scheduling constraint; (c) for each consumer entity for which is received a time-specific scheduling constraint, determining a restart time corresponding to the time-specific scheduling constraint based on the total period of time and the deadline specified by the time-specific scheduling constraint; and (d) selecting the consumer entity having the earliest restart time to use the resource.

Claim 3

Dependent Claim 16 words

The method of claim 1 wherein each of the plurality of consumer entities is a thread.

Claim 4

Dependent Claim 36 words

The method of claim 2 wherein the resource is a processor in the computer system, and wherein step (d) includes the step of selecting the thread having the earliest restart time for execution on the processor.

Claim 5

Dependent Claim 59 words

The method of claim 1, wherein each time-general scheduling constraint contains a resource share value, and wherein step (b) includes the step of: for each consumer entity for which is received a time-general scheduling constraint, determining a restart time that succeeds a time at which step (b) is performed by a period inversely related to the resource share value.

Claim 6

Dependent Claim 93 words

The method of claim 1, further including the steps of: (e) receiving a time-specific scheduling constraint for a consumer entity for which was initially received a time-general scheduling constraint; (f) a determining a restart time corresponding to the specific scheduling constraint received in step (e); and (g) for the consumer entity for which the time-specific scheduling constraint was received in step (e), replacing the restart time determined in step (b) with the restart time determined in step (f), such that the selecting step selects based on the restart time determined in step (f).

Claim 7

Dependent Claim 44 words

The method of claim 1, further including the step of updating the restart time of the selected consumer entity to reflect the work done by the resource on behalf of the selected consumer entity while the consumer entity was selected to use the resource.

Claim 8

Dependent Claim 50 words

The method of claim 1, further including the steps of: identifying a future time at which the restart time of the selected consumer entity will be later than the restart time of one of the other consumer entity; and setting a timer interrupt to occur at the identified future time.

Claim 9

Dependent Claim 35 words

The method of claim 7 wherein the identifying step is performed at an identifying time, and wherein the identified future time is later than the identifying time by at least a preselected minimum use period.

Claim 10

Dependent Claim 66 words

The method of claim 7, further including the steps of, upon the occurrence of the set timer interrupt: updating the restart time of the selected consumer entity to reflect the work done by the resource on behalf of the selected consumer entity while the consumer entity was selected to use the resource; and repeating the selecting step to select another consumer entity to use the resource.

Claim 11

Independent Claim 189 words

A method in a computer system for scheduling the execution of a plurality of threads, each thread having an indication of its urgency, the plurality of threads including a first thread running in client code that contains an inter-thread call to server code executed by a second thread, the indication of urgency of the first thread indicating that it is more urgent than the second thread, the computer system having a measure of the execution of the first thread that is updated when the first thread executes to reflect such execution, the method comprising the steps of: under the control of the client code executed by the first thread, initiating an inter-thread call to the server code executed by the second thread; in response to the initiating step, modifying the urgency indicator of the second thread to attribute the higher urgency of the first thread to the second thread; executing the second thread for an amount of time during the inter-thread call and updating the measure of the execution of the first thread to reflect the amount of time for which the second thread executes during the inter-thread call.

Claim 12

Independent Claim 189 words

A method in a computer system for scheduling the execution of a plurality of threads, each thread having an indication of its urgency, the plurality of threads including a first thread running in client code that contains an inter-thread call to server code executed by a second thread, the indication of urgency of the first thread indicating that it is more urgent than the second thread, the computer system having a measure of the execution of the first thread that is updated when the first thread executes to reflect such execution, the method comprising the steps of: under the control of the client code executed by the first thread, initiating an inter-thread call to the server code executed by the second thread; in response to the initiating step, modifying the urgency indicator of the second thread to attribute the higher urgency of the first thread to the second thread; executing the second thread for an amount of time during the inter-thread call and updating the measure of the execution of the first thread to reflect the amount of time for which the second thread executes during the inter-thread call.

Claim 13

Dependent Claim 33 words

The method of claim 10, further including the step of: when the inter-thread call is completed, modifying the urgency indicator of the second thread to attribute to the second thread its original urgency.

Claim 14

Independent Claim 129 words

A method in a computer system for scheduling the processing of a device interrupt when one or more threads unrelated to the processing of the device interrupt are ready to be executed, the method comprising the steps of: associating with each of the threads unrelated to the processing of the device interrupt an indication of the thread's urgency; detecting an occurrence of the device interrupt; in response to the detecting step, assigning a device interrupt processing thread for processing the detected device interrupt occurrence to the detected device interrupt occurrence; associating an indication of urgency with the device interrupt processing thread; and scheduling the device interrupt processing thread relative to the threads unrelated to the processing of the device interrupt based upon the indications of urgency of each thread.

Claim 15

Independent Claim 129 words

A method in a computer system for scheduling the processing of a device interrupt when one or more threads unrelated to the processing of the device interrupt are ready to be executed, the method comprising the steps of: associating with each of the threads unrelated to the processing of the device interrupt an indication of the thread's urgency; detecting an occurrence of the device interrupt; in response to the detecting step, assigning a device interrupt processing thread for processing the detected device interrupt occurrence to the detected device interrupt occurrence; associating an indication of urgency with the device interrupt processing thread; and scheduling the device interrupt processing thread relative to the threads unrelated to the processing of the device interrupt based upon the indications of urgency of each thread.

Claim 16

Dependent Claim 71 words

The method of claim 12, further including the steps of: at a time preceding the performance of the detecting step, creating the device interrupt processing thread; and upon creating the device interrupt processing thread, blocking the device interrupt processing thread to wait for the occurrence of the device interrupt, and wherein the assigning step includes the step of unblocking the device interrupt processing thread to process the detected device interrupt occurrence.

Claim 17

Independent Claim 224 words

A method for scheduling the execution of a server thread on a first computer system in response to a request from a client thread in a second computer system, each computer system having a scheduler, the client thread having an urgency indicator, the method including the steps of: sending a request to execute the server thread from the second computer system to the first computer system, the request containing the urgency indicator of the client thread obtained from the scheduler of the second computer system; receiving the request in the first computer system; in response to the step of receiving the request, scheduling the server thread to execute under the control of the scheduler of the first computer system utilizing the urgency indicator of the client thread contained in the received request; updating the urgency indicator of the client thread to reflect the work done by the server thread; when execution of the server thread concludes, sending a completion notice from the first computer to the second computer system containing the updated urgency indicator of the client thread; receiving the completion notice in the second computer system; and in response to the step of receiving the completion notice, scheduling the client thread under the control of the scheduler of the second computer system using the updated urgency indicator contained in the received completion notice.

Claim 18

Independent Claim 224 words

A method for scheduling the execution of a server thread on a first computer system in response to a request from a client thread in a second computer system, each computer system having a scheduler, the client thread having an urgency indicator, the method including the steps of: sending a request to execute the server thread from the second computer system to the first computer system, the request containing the urgency indicator of the client thread obtained from the scheduler of the second computer system; receiving the request in the first computer system; in response to the step of receiving the request, scheduling the server thread to execute under the control of the scheduler of the first computer system utilizing the urgency indicator of the client thread contained in the received request; updating the urgency indicator of the client thread to reflect the work done by the server thread; when execution of the server thread concludes, sending a completion notice from the first computer to the second computer system containing the updated urgency indicator of the client thread; receiving the completion notice in the second computer system; and in response to the step of receiving the completion notice, scheduling the client thread under the control of the scheduler of the second computer system using the updated urgency indicator contained in the received completion notice.

Claim 19

Independent Claim 143 words

An apparatus for scheduling the use of a computer system resource by consumer entities, comprising: a scheduling constraint receiver that receives for each consumer entity either a time-specific scheduling constraint or a time-general scheduling constraint; an urgency memory containing an urgency data structure for each consumer entity reflecting, at any given time, the relative immediate urgency of scheduling use of the computer system resource by the consumer entity; an urgency generation subsystem that creates an urgency data structure in the urgency memory for each consumer entity that reflects a relative immediate urgency corresponding to the time-specific scheduling constraint or time-general scheduling constraint received for the consumer entity by the scheduling constraint receiver; and a scheduling subsystem for, at any given time, scheduling the use of the computer system resource for the consumer entity whose urgency data structure reflects the highest relative immediate urgency.

Claim 20

Independent Claim 143 words

An apparatus for scheduling the use of a computer system resource by consumer entities, comprising: a scheduling constraint receiver that receives for each consumer entity either a time-specific scheduling constraint or a time-general scheduling constraint; an urgency memory containing an urgency data structure for each consumer entity reflecting, at any given time, the relative immediate urgency of scheduling use of the computer system resource by the consumer entity; an urgency generation subsystem that creates an urgency data structure in the urgency memory for each consumer entity that reflects a relative immediate urgency corresponding to the time-specific scheduling constraint or time-general scheduling constraint received for the consumer entity by the scheduling constraint receiver; and a scheduling subsystem for, at any given time, scheduling the use of the computer system resource for the consumer entity whose urgency data structure reflects the highest relative immediate urgency.

Claim 21

Dependent Claim 65 words

The apparatus of claim 15, further including an urgency updating subsystem for updating the relative immediate urgency reflected by the urgency data structure for the consumer entity scheduled to use the computer system resource by the scheduling subsystem to account for the use made of the computer system resource by the consumer entity while the consumer entity is scheduled to use the computer system resource.

Claim 22

Dependent Claim 12 words

The apparatus of claim 15 wherein each consumer entity is a thread.

Claim 23

Dependent Claim 14 words

The apparatus of claim 15 wherein the scheduled computer system resource is a processor.

Claim 24

Dependent Claim 124 words

The method of claim 1 wherein the restart time determined for each thread for which is received a time-specific scheduling constraint reflects the latest time at which exclusive use of the resource by the consumer entity would enable the consumer entity to use the resource for the total period of time specified by the time-specific scheduling constraint by the deadline specified by the time-specific scheduling constraint, and wherein the restart time determined for each thread for which is received a time-general scheduling constraint reflects the time by which use of the resource by the thread should commence in order for the thread to use the resource for the share of the total time that the resource is available specified by the time-general scheduling constraint.

Claim 25

Dependent Claim 158 words

A computer-readable medium whose contents cause a computer system to schedule the use of a limited resource of the computer system by a plurality of consumer entities by performing the steps of: (a) receiving for each consumer entity either a time-general scheduling constraint, indicating that the consumer entity should be able to use the resource for a specified share of a total time that the resource is available, or a time-specific scheduling constraint, indicating that the consumer entity should be permitted to use the resource for a specified total period of time by a specified time deadline; (b) for each consumer entity for which is received a time-general scheduling constraint, determining a restart time corresponding to the time-general scheduling constraint; (c) for each consumer entity for which is received a time-specific scheduling constraint, determining a restart time corresponding to the time-specific scheduling constraint; and (d) selecting the consumer entity having the earliest restart time to use the resource.

Claim 26

Dependent Claim 158 words

A computer-readable medium whose contents cause a computer system to schedule the use of a limited resource of the computer system by a plurality of consumer entities by performing the steps of: (a) receiving for each consumer entity either a time-general scheduling constraint, indicating that the consumer entity should be able to use the resource for a specified share of a total time that the resource is available, or a time-specific scheduling constraint, indicating that the consumer entity should be permitted to use the resource for a specified total period of time by a specified time deadline; (b) for each consumer entity for which is received a time-general scheduling constraint, determining a restart time corresponding to the time-general scheduling constraint; (c) for each consumer entity for which is received a time-specific scheduling constraint, determining a restart time corresponding to the time-specific scheduling constraint; and (d) selecting the consumer entity having the earliest restart time to use the resource.

Claim 27

Dependent Claim 44 words

The computer-readable medium of claim 20 wherein the resource is a processor, wherein each of the plurality of consumer entities is a thread, and wherein step (d) includes the step of selecting the thread having the earliest restart time for execution on the processor.

Claim 28

Dependent Claim 104 words

A computer memory containing a thread scheduling data structure for scheduling the execution of a plurality of threads, each thread being the subject of a timing constraint specifying timing guidelines for the execution of the thread, at least one of the threads being the subject of a time-specific scheduling constraint, at least one of the threads being the subject of a time-general scheduling constraint, the data structure containing, for each thread, a restart time based upon the timing constraint of which the thread is the subject, such that the threads may be scheduled by selecting for execution the thread having the earliest restart time.

Claim 29

Dependent Claim 104 words

A computer memory containing a thread scheduling data structure for scheduling the execution of a plurality of threads, each thread being the subject of a timing constraint specifying timing guidelines for the execution of the thread, at least one of the threads being the subject of a time-specific scheduling constraint, at least one of the threads being the subject of a time-general scheduling constraint, the data structure containing, for each thread, a restart time based upon the timing constraint of which the thread is the subject, such that the threads may be scheduled by selecting for execution the thread having the earliest restart time.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2001-09-21	2002-03-23	2002-09-22	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2005-09-21	2006-03-23	2006-09-22	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2009-09-21	2010-03-23	2010-09-22	$7700.00	Window Closed / Lapsed

Method and system for scheduling the execution of threads using optional time-specific scheduling constraints

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag