Device comprising a communications stack with a scheduler

• US 20050223191A1
• Filed: 05/27/2003
• Published: 10/06/2005
• Est. Priority Date: 05/27/2002
• Status: Abandoned Application

• Current Assignee: Radioscape Limited
• Original Assignee: Radioscape Limited
• Inventors: Ferris, Gavin Robert
• Application Number:
  US10/515,657
• Publication Number:
  US 20050223191A1
• Time in Patent Office: Days
• US Class Current: 712/28
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 9/45537 Provision of facilities of other operating environments, e.g. WINE I/O emulation G06F13/105
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A scheduler is used to schedule execution of tasks by ‘engines’ that perform high resource functions as requested by ‘executive’ control code, the scheduler using its knowledge of the likelihood of engine request state transitions. The likelihood of engine request state transitions describes the likely sequence of engines which executives will impose: the scheduler can at run-time in effect, as the start of a time slice, look-forward in time to discern a number of possible schedules (i.e. sequence of future engines), assess the merits of each possible schedule using pre-defined parameters (e.g. memory and power utilisation), then apply the schedule which is most appropriate given those parameters. The process repeats at the start of the next time slice. The scheduler therefore operates as a predictive scheduler. The present invention is particularly effective in addressing the “multi-mode problem”: dynamically balancing the requirements of multiple communications stacks operating concurrently.

Claims

1. A device comprising a communications stack split into:

(i) engines designed to perform real time DSP or communications high resource functions;

(ii) executives designed to perform low resource functions, including issuing requests for engine execution tasks; and

(iii) a scheduler that receives the requests and schedules execution of those tasks by an underlying RTOS, the scheduler using its knowledge of the likelihood of engine request state transitions, obtained during simulation, to make, at runtime, scheduling decisions based on evaluating several possible future scenarios.

2. The device of claim 1 in which the scheduler is a service of a virtual machine layer separating the engines from the executives.

3. The device of claim 1 in which the scheduler uses engine resource utilisation profiles.

4. The device of claim 3 in which the engine resource utilisation profiles cover both cycles and memory.

5. The device of claim 1 comprising multiple communications stacks operating concurrently and the scheduler is able to dynamically balance the requirements of the stacks.

6. The device of claim 1 in which executives cannot invoke engines directly but only through the scheduler.

7. The device of claim 1 in which the likelihood of engine request state transitions describes the likely sequence of engines which the executives will impose and is represented as a table or matrix for each of several different executives.

8. The device of claim 1 in which the scheduler decides which engine execution tasks are to be submitted to the underlying RTOS for execution, how many RTOS threads to use, at what priority and at each logical timestep.

9. The device of claim 8 in which the likelihood of engine request state transitions is a relative-frequency-based probability estimate of the likelihood of a given engine being called, given that a known prior engine was called.

10. The device of claim 8 in which the scheduler operates a runtime scheduling policy comprising a heuristic forward scenario generator that takes a set of submitted immediate engine requests and generates an incomplete set of possible future scenarios, based upon the state transition information.

11. The device of claim 10 in which the scheduler operates a runtime scheduling policy comprising a set of planning metrics that can be used to evaluate each of the possible future scenarios, weighing up the relative importance of one or more of the following factors:

(a) memory utilisation, (b) timeslice utilisation, (c) proximity to deadline, (d) power utilisation, and generating a single scalar score.

12. The device of claim 11 in which the planning metrics reflect choices made at design time to weight the factors differently.

13. The device of claim 11 in which the planning metrics reflect choices made at design time to determine whether the device responds early or late to resource shortages.

14. The device of claim 11 in which the scheduler operates a dispatcher that takes the highest scoring such scenario and schedules all forward non-contingent threads onto the underlying RTOS.

15. The device of claim 11 in which the scheduler is able to degrade system performance gracefully, rather than invoking a catastrophic failure, by failing some requests in a systematic manner.