Providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-009/00
G06F-015/173
G06F-015/16
출원번호
US-0842213
(2004-05-10)
발명자
/ 주소
Jones,Michael B.
Regehr,John
출원인 / 주소
Microsoft Corporation
대리인 / 주소
Lee & Hayes, PLLC
인용정보
피인용 횟수 :
1인용 특허 :
25
초록▼
The present invention provides providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems. In one embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes
The present invention provides providing predictable scheduling of programs using repeating precomputed schedules on discretely scheduled and/or multiprocessor operating systems. In one embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. There may be one scheduling graph for each processor, or a scheduling graph may traverse multiple processors. Start and end times for reservations and constraints are adjusted to compensate for the granularity of the clock of the system. Furthermore, the scheduler may use an existing priority-based scheduler in order to cause scheduling decisions it has made to be acted upon.
대표청구항▼
The invention claimed is: 1. A method for a computer system having a plurality of processors comprising: receiving a constraint for a thread in an activity specifying a desired earliest start time, amount of requested execution time, and a deadline; determining the thread has previously been run on
The invention claimed is: 1. A method for a computer system having a plurality of processors comprising: receiving a constraint for a thread in an activity specifying a desired earliest start time, amount of requested execution time, and a deadline; determining the thread has previously been run on a particular processor; upon determining that the thread has previously been run on a particular processor, determining whether the constraint can be scheduled on the particular processor; upon determining that the constraint can be scheduled on the particular processor, scheduling the constraint on the particular processor using a respective one of a plurality of execution schedules, where each said processor has a corresponding said execution schedule; otherwise, scheduling the constraint on a different processor; and, otherwise, scheduling the constraint on a different processor. 2. A method for a computer system having a plurality of processors comprising: receiving a reservation for an activity that previously had no reservations, the reservation specifying a recurring desired number of time units within a desired period; determining whether a thread within the activity has previously been run on a particular processor; upon determining that the thread has previously been on a particular processor, determining whether the reservation can be scheduled on the particular processor; upon determining that the reservation can be scheduled on the particular processor, scheduling the reservation on the particular processor using a respective one of a plurality of execution schedules, where each said processor has a corresponding said execution schedule; otherwise, scheduling the reservation on a different processor; and, otherwise, scheduling the reservation on a different processor. 3. One or more computer readable media comprising computer executable instructions that, when executed by a computer having a plurality of processors, direct the computer to: receive a constraint for a thread in an activity specifying a desired earliest start time, amount of requested execution time, and a deadline; determine the thread has previously been run on a particular processor; when it is determined that the thread was previously run on a particular processor, determining whether the constraint can be scheduled on the particular processor; upon determining that the constraint can be scheduled on the particular processor, scheduling the constraint on the particular processor using a respective one of a plurality of execution schedules, where each said processor has a corresponding said execution schedule; otherwise, scheduling the constraint on a different processor; and, when it is determined that the thread was not previously run on a particular processor, scheduling the constraint on a different processor.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (25)
Boland Vernon K., Affinity scheduling of data within multi-processor computer systems.
Chen Ming-Syan (Yorktown Heights NY) Turek John J. E. (Chappaqua NY) Wolf Joel L. (Katonah NY) Yu Philip S. (Chappaqua NY), Hierarchical scheduling method for processing tasks having precedence constraints on a parallel processing system.
Jones Michael B. ; Leach Paul J. ; Draves ; Jr. Richard P. ; Barrera ; III Joseph S. ; Levi Steven P. ; Rashid Richard F. ; Fitzgerald Robert P., Method and system for scheduling the execution of threads using optional time-specific scheduling constraints.
Jones Michael B. ; Leach Paul J. ; Draves ; Jr. Richard P. ; Barrera ; III Joseph S. ; Levi Steven P. ; Rashid Richard F. ; Fitzgerald Robert P., Method and system for scheduling the use of a computer system resource using a resource planner and a resource provider.
Browning, Luke Matthew; Peek, Jeffrey Scott, Method and system for scheduling threads within a multiprocessor data processing system using an affinity scheduler.
Rusterholz John T. (Roseville MN), Method for generating a preferred processing order and for detecting cycles in a directed graph used to represent system.
Boland Vernon K. ; Brasche Kevin R. ; Smith Kenneth A., Method for load balancing a per processor affinity scheduler wherein processes are strictly affinitized to processors an.
Rasbold James C. (Livermore CA) Van Dyke Don A. (Pleasanton CA), Method for optimizing instruction scheduling for a processor having multiple functional resources.
Farrell Joel A. (Endicott NY) Record Stephen E. (Ridgefield CT) Wade Brian K. (Apalachin NY), Preemptive and non-preemptive scheduling and execution of program threads in a multitasking operating system.
Bahr James E. (Rochester MN) Corrigan Michael J. (Rochester MN) Knipfer Diane L. (Rochester MN) McMahon Lynn A. (Rochester MN) Metzger Charlotte B. (Elgin MN), Process for dispatching tasks among multiple information processors.
Vaitzblit Lev (Concord MA) Ramakrishnan Kadangode K. (Maynard MA) Tzelnic Percy (Concord MA), Scheduling and admission control policy for a continuous media server.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.