Method and apparatus for activity based execution scheduling

Patent metadata

Field	Value
Publication number	US-9665398-B2
Application number	US-201414576963-A
Country	US
Kind code	B2
Filing date	Dec 19, 2014
Priority date	May 30, 2014
Publication date	May 30, 2017
Grant date	May 30, 2017

Abstract

A method and an apparatus for activity based execution scheduling are described. Activities may be tracked among a plurality of threads belonging to a plurality of processes running in one or more processors. Each thread may be associated with one of the activities. Each activity may be associated with one or more of the threads in one or more of the processes for a data processing task. The activities may be ordered by a priority order. A group of the threads may be identified to be associated with a particular one of the activities with highest priority based on the priority order. A thread may be selected from the identified threads for next scheduled execution in the processors.

First claim

What is claimed is:

1. A machine-readable non-transitory storage medium having instructions therein, which when executed by a machine, cause the machine to perform a method, the method comprising:
tracking activities among a plurality of threads,
each thread of the plurality of threads associated with one or more of the activities to perform operations for the associated activities, the activities having a priority order, each activity performed by one or more of the threads of the plurality of threads for a data processing task, wherein the plurality of threads belong to a plurality of processes running in one or more processors; identifying a particular activity of the tracked activities,
the particular activity having highest priority based on the priority order among the activities;

identifying a group of the threads of the plurality of threads belonging to the plurality of processes associated with the particular activity identified;
selecting a thread from the group of threads of the plurality of threads identified for next scheduled execution in the processors, the selected thread associated with a first process of the plurality of processes, the first process having the priority of the particular identified activity;
executing the selected thread for next execution in the processors,
receiving, by a second process in the plurality of processes, a message from the first process to perform operations for the particular identified activity on behalf of the first process, the message including the priority of the first process,
setting a priority of a thread of the second process to the priority of the first process, and executing the thread of the second process in the processors.

2. The medium of claim 1 , wherein the processes are prioritized via a process priority, wherein the group of threads are running in two or more of the processes, and wherein the selection from the group of threads is based on the process priority of the threads.

3. The medium of claim 1 , wherein the activities are identified by activity identifiers and wherein the tracking comprises:
maintaining the activity identifiers in a registry, wherein each activity identifier is associated with a reference count indicating whether a corresponding activity identified by the activity identifier has been completed.

4. The medium of claim 3 , wherein the activities include a first activity identified by a first activity identifier of the activity identifiers, the first activity associated with a first reference count in the registry, the maintenance comprises:
in response to a request including the first activity identifier received from the first process, updating the first reference count to indicate an additional reference to the first activity identifier.

5. The medium of claim 4 , wherein the message includes the first activity identifier, and wherein the message is based on an inter process communication mechanism.

6. The medium of claim 4 , wherein the threads include a first thread associated with the first activity, the first thread belongs to the first process, and wherein the request is sent from the first thread before performing an operation for the first activity.

7. The medium of claim 6 , wherein the registry includes associations of the threads and the activity identifiers, the maintenance further comprising:
updating the associations in response to the request, the updated associations in the registry indicating the first thread is associated with the first activity identifier.

8. The medium of claim 4 , wherein the request includes a voucher maintained via a voucher system, wherein the voucher specifies the first activity identifier, and wherein the updating comprises:
verifying whether the voucher is valid via the voucher system, wherein the first reference count is not updated if the voucher is not valid and wherein if the voucher is valid, the voucher is created via the voucher system.

9. The medium of claim 8 , wherein the group of threads is identified via the associations between the threads and the activity identifiers in the registry.

10. The medium of claim 3 , wherein if at least one of the group of threads is runnable without being blocked from execution, the selected thread is among the at least one runnable threads.

11. The medium of claim 10 , wherein the selected thread is not runnable waiting for a blocking condition to be satisfied, the selected thread having a first executable code, wherein if one of the threads has already been identified for satisfying the blocking condition, the identified thread having a second executable code, the execution of the selected thread comprising:
executing the second executable code via the selected thread, wherein the first executable code is subsequently executed via the selected thread already running subsequent to the execution of the second executable code.

12. The medium of claim 11 , wherein the blocking condition can be satisfied via one of the threads associated with a separate one of the activities, wherein no thread has been identified for satisfying the blocking condition, the execution of the selected thread comprising:
identifying one or more of the threads associated with the separate activity; and
executing the one or more threads associated with the separate activity until the blocking condition is satisfied, wherein the selected thread is executed when the blocking condition is satisfied.

13. The medium of claim 12 , wherein the separate activity is identified via a separate one of the activity identifiers, the method further comprising:
determining heuristically a dependency of the blocking condition and the separate activity identifier, wherein the dependency indicates that the blocking condition is to be satisfied via at least one thread associated with the separate activity identifier.

14. The medium of claim 13 , wherein the blocking condition includes a lock, wherein the blocking condition is satisfied when the lock is released.

15. A computer implemented method comprising:
tracking activities among a plurality of threads, each thread of the plurality of threads associated with one or more of the activities to perform operations for the associated activities, the activities having a priority order, each activity performed by one or more of the threads of the plurality of threads for a data processing task, wherein the plurality of threads belong to a plurality of processes running in one or more processors;
identifying a particular activity of the tracked activities, the particular activity having highest priority based on the priority order among the activities;
identifying a group of the threads of the plurality of threads belonging to the plurality of processes associated with the particular activity identified;
selecting a thread from the group of threads of the plurality of threads identified for next scheduled execution in the processors, the selected thread associated with a first process of the plurality of processes, the first process having the priority of the particular identified activity;
executing the selected thread in the processors,
receiving, by a second process in the plurality of processes, a message from the first process to perform operations for the particular identified activity on behalf of the first process, the message including the priority of the first process,
setting a priority of a thread of the second process to the priority of the first process, and executing the thread of the second process in the processors.

16. A computer system comprising:
a memory storing instructions;

Assignees

• Apple Inc

Inventors

• Magee James Michael
• Blaine Russell A
• Chimene Daniel Allen
• Patel Vishal
• Sen Shantonu

Classifications

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F1/3206

  Monitoring of events, devices or parameters that trigger a change in power modality · CPC title

• G06F9/50

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F1/3287

  by switching off individual functional units in the computer system · CPC title

• G06F2209/484

  Precedence · CPC title