Back to results
US 7,093,256 B2Granted
Method and apparatus for scheduling real-time and non-real-time access to a shared resource
AssigneeEquator Technologies, Inc.
InventorRudolf Henricus Johannes Bloks
Life of this patent
Estimating the term…
Abstract
A method and apparatus are provided in a computing environment for scheduling access to a resource. The method grants access to the resource by a non-real-time request when the non-real-time request can be completed before the latest possible start time at which a first real-time request must start service to timely complete all actual and anticipated real-time requests, otherwise granting the first real real-time request access to the resource.
Claims10
A scheduler for scheduling access in a computing environment to a resource, the scheduler comprising:
- a real-time request control circuit operable to receive requests from real-time requesters at system time T, and to anticipate requests for real-time requesters that currently have no active request using their known latency Li and duration Di values, so that there are M real and anticipated real-time requests to be scheduled;
- a timer circuit having registers operable to hold a plurality of M real-time requests, each request Ri having a status of anticipated or real, a required service completion time Ti, and a duration Di;
- a reorder logic operable to prepare an ordered list of the M real-time requests in ascending order of required service completion dines TR1 . . . TRM, beginning with the real-time request having the earliest required service completion time being designated as request R1 with a required service completion time TR1 and a duration DR1, and the ascending order concluding with the real-time request having the latest required service completion time being designated as request RM with a required service completion time TRM, and a duration DRM;
- a network of adders and subtractors operable to calculate the latest service start time TLi for every request subsequence {R1, R2R1, R3 . . . R1, . . . , RM...R1}that will provide on-time completion of the plurality M of real-time request;
- a minimum value select circuit operable to find the earliest calculated latest service start time TS;
- and
- a non-real-time request scheduling circuit that includes a plurality of non-real-time control circuits, each control circuit being operable to receive a different non-real-time request R and its duration value D, and to check whether T+D<TS for the non-real-time request R handled by it,
- the real-time request control circuit and non-real-time request scheduling circuit being cooperatively arranged such that when T+D<TS for a non-real-time request R, the non-real-time request scheduling circuit grants the non-real-time request R access to the resource, otherwise the real-time request control circuit grants the real (not anticipated) real-time request having the earliest required service completion time access to the resource.
5 more elements
A method for scheduling access in a computing environment to a resource having a real-time request capacity M, comprising the steps of:
- receiving requests for access to the resource from N real-time requesters, each real-time request Ri (i=requester index for i=1 . . . N) having a latency Li and a duration Di;
- anticipating requests for M-N real-time requesters that currently have no active request using their known latency Li and duration Di values, so that there are now M anticipated, and real (not anticipated) real-time requests for access to be scheduled;
- preparing an ordered list of the M real-time requests as requests R1–RM according to completion time TR1 . . . TRM, each request having durations DR1 . . . DRM, such that R1 is earliest request for service to be completed as determined by completion time TRI, and RM is the latest;
- (i) calculating a latest service start time TLi for every request subsequence shown below for pending and anticipated real-time requests, as follows:
- R1 only:
- Tb1=TR1−DR1
- R2 . . . R1:TL2=TR2−DR2−DR1
- . . .
- RM . . . R1:TLM=TRM−DRM− . . . −DR1;
- selecting a service start time TS that is the earliest of all the calculated latest service start time TLi for every sub-sequence (TS =MINi(TLi));
- and
- granting a non-real-time request R when T+D<TS for the non-real-time request R, otherwise granting the real (not anticipated) real-time request having the earliest required service completion time access to the resource.
9 more elements
A scheduler for scheduling access to a resource in a computing environment, the scheduler comprising:
- a means for receiving requests for access to the resource from N real-time requesters, each real-time request Ri (i=requester index for i =1N) having a latency Li and a duration Di;
- a means for anticipating requests for M-N real-time requesters that currently have no active request using their known latency Li and duration Di values, so that there are now M anticipated and real (not anticipated) real-time requests for access to be scheduled;
- a means for preparing an ordered list of the M real-time requests as requests R1–RM according to completion time TR1 . . . TRM, each request having durations DR1 . . . DRM, such that R1 is earliest request for service to be completed as determined by completion time TR1, and RM is the latest;
- (i) a means for calculating a latest service start time TLi for every request sub-sequence shown below for pending and anticipated real-time requests, as follows:
- R1 only:
- TL1=TR1−DR1
- R2 . . . R1:TL2=TR2−DR2−DR1
- . . .
- RM . . . R1:TLM=TRM−DRM− . . . −DR1;
- a means for selecting a service start time TS that is the earliest of all the calculated latest service start time TLi for every sub-sequence (TS=MINi(TLi));
- and a means for granting a non-real-time request R when T+D<TS for the non-real-time request R, otherwise granting the real (not anticipated) real-time request having the earliest service completion time access to the resource.
8 more elements
Dependencies are inferred from the claim text.