Method and apparatus for scheduling real-time and non-real-time access to a shared resource

1. 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 TR 1 . . . TRM, beginning with the real-time request having the earliest required service completion time being designated as request R 1 with a required service completion time TR 1 and a duration DR 1 , 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 {R 1 , R 2 R 1 , R 3 . . . R 1 , . . . , RM...R 1 }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.

2. The scheduler of claim 1 , wherein the scheduler is operable to schedule access again after completion of the granted request.

3. The scheduler of claim 1 , wherein the scheduler is operable to schedule access each clock cycle of the shared resource.

4. The scheduler of claim 1 , wherein the real-time request control circuit is further operable to control registers in the timer circuit.

5. 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 R 1 –RM according to completion time TR 1 . . . TRM, each request having durations DR 1 . . . DRM, such that R 1 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:

R 1 only: Tb 1 =TR 1 −DR 1

R 2 . . . R 1: TL 2 =TR 2 −DR 2 −DR 1

. . .

RM . . . R 1: TLM=TRM−DRM− . . . −DR 1;

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.

6. The method of claim 5 , wherein the method is implemented by hardware.

7. The method of claim 5 , wherein the method includes the further step of repeating the steps after completion of the granted request.

8. The method of claim 5 , wherein the method includes the further step of repeating the steps each clock cycle of the resource.

9. The method of claim 5 , wherein the step of adding anticipated requests for real-time requesters that currently have no active request further includes using a maximum anticipated duration Di.

10. 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 = 1 N) 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 R 1 –RM according to completion time TR 1 . . . TRM, each request having durations DR 1 . . . DRM, such that R 1 is earliest request for service to be completed as determined by completion time TR 1 , 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:

R 1 only: TL 1 =TR 1 −DR 1

R 2 . . . R 1: TL 2 =TR 2 −DR 2 −DR 1

. . .

RM . . . R 1: TLM=TRM−DRM− . . . −DR 1;

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.