US 10,310,891 B2 · Hand-off scheduling

Abstract

Disclosed herein are systems, methods, and computer-readable media directed to scheduling threads in a multi-processing environment that can resolve a priority inversion. Each thread has a scheduling state and a context. A scheduling state can include attributes such as a processing priority, classification (background, fixed priority, real-time), a quantum, scheduler decay, and a list of threads that may be waiting on the thread to make progress. A thread context can include registers, stack, other variables, and one or more mutex flags. A first thread can hold a resource with a mutex, the first thread having a low priority. A second thread having a scheduling state with a high priority can be waiting on the resource and may be blocked behind the mutex held by the first process. A scheduler can execute the context of the lower priority thread using the scheduler state of the second, higher priority thread. More than one thread can be waiting on the resource held by the first thread. A “pusher list” of threads that are waiting on the first thread can be associated with the first thread. The scheduler can use the pusher list to identify threads that need the first thread to make progress until the first thread releases the resource and mutex. Then, the scheduler can use the pusher list to identify threads that are now runnable and make immediate use of the resource.

Claims25

Dependent claims

A computer-implemented method, comprising:

detecting that a first thread holds a mutex on a resource, the first thread having a first scheduling state that includes a first processing priority and at least one additional scheduling state attribute, and the first thread having a first processing context that includes a state of one or more registers associated with the first thread;
during processing of a second thread, by a processor core of a processing system, detecting that the second thread is blocked, waiting on the release of the mutex on the resource, the second thread having a second scheduling state that includes a second processing priority and at least one additional scheduling state attribute, and a second processing context that includes a state of one or more registers associated with the second thread, wherein the second processing priority is higher than the first processing priority;
keeping the second scheduling state of the second thread on the processor core;
context switching the first processing context of the first thread onto the processor core;
processing, by the processor core, the first processing context using the second scheduling state of the second thread;
after releasing, by the first thread, the mutex on the resource, context switching the first processing context from the processor core back to the first thread.

3 more elements

A non-transitory computer-readable medium programmed with instructions that, when executed by a processing system, perform a method, comprising:

detecting that a first thread holds a mutex on a resource, the first thread having a first scheduling state that includes a first processing priority and at least one additional scheduling state attribute, and the first thread having a first processing context that includes a state of one or more registers associated with the first thread;
during processing of a second thread by a processor core of the processing system, detecting that the second thread is blocked, waiting on the release of the mutex on the resource, the second thread having a second scheduling state that includes a second processing priority and at least one additional scheduling state attribute, and a second processing context that includes a state of one or more registers associated with the second thread, wherein the second processing priority is higher than the first processing priority;
keeping the second scheduling state of the second thread on the processor core;
context switching the first processing context of the first thread onto the processor core;
processing, by the processor core, the first processing context using the scheduling state of the second thread;
after releasing, by the first thread, the mutex on the resource, context switching the first processing context from the processor core back to the first thread.

3 more elements

A processing system comprising:

one or more processors coupled to a memory, the memory programmed with executable instructions that, when executed by the one or more processors perform a method, comprising:
detecting that a first thread holds a mutex on a resource, the first thread having a first scheduling state that includes a first processing priority and at least one additional scheduling state attribute, and the first thread having a first processing context that includes a state of one or more registers associated with the first thread;
during processing of a second thread by a processor core of a processing system, detecting that the second thread is blocked, waiting on the release of the mutex on the resource, the second thread having a second scheduling state that includes a second processing priority and at least one additional scheduling state attribute, and a second processing context that includes a state of one or more registers associated with the second thread, wherein the second processing priority is higher than the first processing priority;
keeping the second scheduling state of the second thread on the processor core;
context switching the first processing context of the first thread onto the processor core;
processing, by the processing core, the first processing context of the first thread using the second scheduling state of the second thread;
after releasing, by the first thread, the mutex on the resource, context switching the first processing context from the processor core back to the first thread.

4 more elements

Dependencies are inferred from the claim text.

Hand-off scheduling

Life of this patent

Hand-off scheduling

Life of this patent

Abstract

Claims25