GB2367913A

GB2367913A - Processor resource scheduler

Info

Publication number: GB2367913A
Application number: GB0022868A
Authority: GB
Inventors: Patrick Mcandrew; Philip Alan Tottle
Original assignee: Motorola Inc
Current assignee: Motorola Solutions Inc
Priority date: 2000-09-16
Filing date: 2000-09-16
Publication date: 2002-04-17
Also published as: AU2001287737A1; WO2002023329A3; GB0022868D0; WO2002023329A2

Abstract

A processor resource scheduler is provided for a data processing system 400 having a predetermined amount of processing resources 460, 470, 480, 490. The scheduler includes a resource utilization manager 410 which manages the processing of a plurality of data processes 450. The scheduler also has a resource utilization table 415 which stores processor resource requirement values of the processes and the value of available processing resources. Priority information for the data processes may also be stored. The resource utilization manager 410 uses the table 415 to determine the scheduling of the data processes 450 in dependence upon the requirements of the data and the available processing resources of the system. In this way at run-time, potential resource (MIPs, memory, processors) overloads are determined. The processor resource scheduler may be incorporated into a mobile communications device. Alternatively, it may be coupled to a mobile communications device via a network, wherein the resource utilization manager is at least partially located at a base station remote from the mobile communications device.

Description

2367913 PROCESSOR RESOURCE SCHEDULER AND METHOD

Field of the Invention

5 This invention relates to processor resource schedulers for data processing systems and particularly, but not exclusively, to such schedulers when arranged to decode multiple data streams.

Background of the Invention

Currently, in systems utilising data processors, including Complex Instruction Set (CISC), Reduced 15 Instruction Set (RISC)jA and scalar processors, the ability to process multiple tasks is common. Typically, these tasks relate to the processing of one type of data stream where the limits of required resources are generally well understood. The scheduling of these tasks is normally 20 handled by a Real-Time Operating System (RTOS) that allocates processor bandwidth to each task in a timesliced manner according to some pre-determined priority scheme. Potential over-loading of processor resources is handled within the software design phase, where the tasks 25 that are envisaged to be run are constrained to utilise less than the total amount of processor resources. If a resource overload situation should occur at run-time, then mis-operation of many tasks may occur due to the inadequate allocation of the available resources. For 30 applications such as compressed video or graphics decoding, the temporal processing needs vary hugely and rapidly dependent upon the source material as well as the coding type. For such applications the software design phase assumptions must take into consideration the typical resource requirements as well as predicted worstcase utilisation. This leads to great under-utilisation 5 of resources in some situations and an overload situation (incapacity to process real-time data) in others.

In the future, with the advent of Software Definable Radio (SDR) and the ability to simultaneously process 10 different data streams, the difficulty in prediction of required resources will increase yet further. Using the traditional method to predict a worst-case resource requirement will result in systems running in an even greater under-utilised manner for most of the time. For 15 practical systems, this means that the processor speed and memory used will greatly exceed that generally required for normal operation. This directly leads to cost and operating power increases.

20 It is an object of the present invention to provide processor resource scheduler wherein the abovementioned disadvantages may be alleviated.

25 Statement of Invention

In accordance with a first aspect of the present invention there is provided a processor resource scheduler as claimed in claim 1.

In accordance with a second aspect of the present invention there is provided a method of scheduling resources for a processor of a data processing system as claimed in claim 12.

5 Brief Description of the Drawings

A processor resource scheduler incorporating the present invention will now be described, by way of example only, with reference to the accompanying drawing(s), in which:

FIG. I shows a block diagram of a prior art Real

Time Operating System incorporated in a device; FIG. 2 shows a block diagram of a Real-Time Operating System incorporating a processor resource 15 scheduler in accordance with the present invention; FIG. 3 shows an illustrative block diagram of the operation of a data processing system incorporating the processor resource scheduler in accordance with the present invention; and, 20 FIG. 4 shows a flow chart of the operation of the processor resource scheduler of FIG. 3.

Detailed Description of a Preferred Embodiment

Referring to FIG. 1 there is shown a block diagram of an existing Real-Time Operating System (RTOS) for an electronic device such as a mobile communications radio (not shown). The RTOS manages all aspects of the device:- 30 scheduling, memory, power, timers, files, keyboard, pointer, screen, PC Cards, CF-card removable media, etc. The device typically has at least one Central Processing Unit (CPU- not shown) which processes data under the control of the RTOS.

An RTOS runtime kernel 5 comprises a kernel executive 10 5 and a kernel server 20. A kernel Application Program Interface (API) 25 provides services to device drivers 30.

The kernel 5 supports pre-emptive multi-tasking using 10 threads, which are the basic unit of execution. A kernel service thread 35 is shown. A process scheduler (not shown) runs the eligible thread with the highest priority.

15 Processes are the basic unit of memory management: a process has its own address space, a primary thread, and any number of other threads. A tick interrupt is used to drive timer queues and round-robin scheduling of the highest-priority threads.

The kernel 5 and device drivers 30 use a power model to keep track of power requirements and power sources, and to close down devices and power sources when not required. The kernel S implements power management with a 25 so-called "null thread function" 40, the lowest-priority thread function in the system. When a null thread is scheduled, this simply informs the power model that the CPU is no longer needed: the power model then shuts down the CPU until the next interrupt. Above the priority 30 level of the null thread function 40, there is a kernel server thread function 50, and above that user thread functions 60.

Referring now also to FIG. 2, there is shown a block diagram of a new RTOS runtime kernel 205 in accordance with the invention, used in the RTOS 202 of a mobile communications device such as a cellular radio 200. The 5 kernel 205 comprises a kernel executive 210 and a kernel server 220. A kernel Application Program Interface (API) 225 provides services to device drivers 230, and a kernel service thread 235 is also shown, as before.

10 A Resource Utilisation Manager (RUM) thread function 245 is a new kernel thread function above the power management (null) thread function that assesses whether a new task can be enabled. This allows run-time potential overloads to be determined and avoided by delaying 15 enabling of a task or the suspension of other tasks. The RUM thread function 245 uses data tagged at design time to each task and an active list of the present system resource utilisation to calculate the resource loading of the system. This will be further described below.

The RUM thread function 245 can also use resource data collected during the real-time utilisation of a resource and use this data in a manner to be described below to predict the utilisation of a resource instead of the data 25 tagged at design time. For certain applications, e.g.

video decode, this may give a more accurate estimate of the resource utilisation and allow the processor to be more heavily loaded.

30 The RUM thread function 245 therefore has the ability at run-time to calculate the resource loading of the system.

As the execution of new tasks is requested, the resultant resource loading is be checked and only directly allowed if still within the system limits. This provides the facility to selectively enable, disable or delay tasks or streams to permit higher priority tasks to be run 5 correctly. For the case of the previously mentioned SDR processing simultaneous data streams, this provides a mechanism to permit time insensitive streams (e.g. email) to be delayed whilst focussing processing resources on time critical streams (e.g. video).

As mentioned above, at design time, additional information (Task Resource Data) describing required processor resources such as, mips, memory and priority for each task, is tagged to (or embedded in) that 15 software module.

It is also possible to extract real-time data describing the utilisation of the processor or a key component of it. This could be done as an alternative or in addition 20 to the task resource data embedded in the data stream. An example of this would be in the case of digital signal processing, to monitor the data Arithmetic Logic Unit(s) (ALU) either by instruction decode or from signals inherent within the ALU hardware, thus obtaining an 25 average percentage utilisation factor. For many types of processing this figure may be valid over reasonable time intervals (video decode) and may therefore indicate a closer estimate of the actual resource utilisation than that provided by the design figure.

An alternative is that the streams real time processing requirements that are data dependent can be attached to the data stream to be decoded as additional task resource data (mips, memory) and used to make a decision on whether to schedule a task.

5 It is also possible for the RUM to keep a history of previous utilisation values and to predict future resource requirements from that history by observing the trend of recent resource utilisation (rather than current utilisation) together with the requirements for a new 10 task or process.

In operation, and referring now also to FIG. 3, there is shown a data processing system 400. A stream (Sn) 405 to be received, initiates a call to a Resource Utilisation 15 Manager (RUM) 410 of the system 400. The RUM 410 then calculates the potential system resource loading by reading task resource data from the stream 405 and adding it to the current system resource level contained in a Resource Utilisation Table (RUT) 415. A more detailed 20 description of this process is provided below in FIG. 4. Based upon this calculation, the processing of that stream may be enabled (box 420), disabled (box 430) or delayed for a fixed time period (box 440). Additionally, if enabled, the RUM 410 may decide to disable other lower

25 priority tasks in order to permit the processing of the current stream 405. If this is the case, they may be reenabled at a future time by the RUM 410.

Additionally, after initiation of the stream Sn 405, 30 calls would be remade to the RUM 410 in order to determine if changes to the executing tasks should be made in order to improve system performance. At this time, use may be made of the run-time utilisation factor when recalculating the predicted system utilisation. This may generally result in a more accurate and lower figure, possibility allowing more tasks to be run. 5 The RUM 410 sends control signals to first and second memory stores 460 and 490 respectively, and ALUs 470 and 480 in a conventional manner to perform appropriate functions on the stream Sn (shown as item 450 being 10 loaded into memory store 460).

The output from memory store 490 may be a Digital to Analog Converter (DAC) 485 or a display 495 of the device. In this way the stream Sn 450 is loaded into the 15 first memory store 460, processed by one or more of the ALUs 470, 480, and the resulting data sent to the second memory store 490, where it is output to the DAC 485 or the display 49S.

20 The RUT 415 is maintained in order to allow the RUM 410 to both track the current system resource utilisation and to calculate predicted values for the launching of new tasks. The typical content of a RUT is shown in Table 1.

The current system total is the values relating to the 25 tasks currently being utilised. The maximum values are set at design and reflect the maximum obtainable from the system less some degree of typical safety margin.

Calculation of predicted resource utilisation is 30 performed as follows. When a request for a new task to be added to the system is made, the parameter tags for that task (mips, memory etc) are added to the current system total. A check is made to determine whether this exceeds the maximum allowable for the system (also contained in the RUT). If the potential total is less than the system maximum allowable, then the request may be allowed.

5 However, if this is not true, then the RUM 410 may recalculate potential loadings by considering possible deletion of currently running tasks. The choice of deleted task(s) is made by consideration of the RUT priorities and may be an iterative process.

Priority MIPS Memory Memory #1 #n Task #1 Task #n Current System Total Max Allowable System Table 1: Resource Utilisation Table (RUT) Referring now also to FIG. 4, there is shown a flow diagram of the calculation function of the RUM 410 of 15 FIG. 3. At box 505, a request is received by the RUM 410 to process stream Sn (405). The RUM 410 calculates the potential system resource loading by reading the process resource data of the stream Sn (box 510) and adding this to the current system total as provided by the RUT 415 20 (box 515). This potential figure is then compared (box 520) to the maximum system total available (box 525), again courtesy of the RUT 415.

If the predicted resource level is less than the Total available system level (box 530) then processing of stream Sn is enabled (box 535). If the predicted resource level is less than the available system resources, then 5 the priority level of the stream Sn is compared to the priority levels of other tasks (box 540). This is done by the RUT 415 providing the lowest priority task or process (box 550) to the RUM 410 (box 545) and comparing this to the priority level of the stream Sn (box 560).

If the stream Sn priority is less than all other task priorities then processing of the stream Sn is delayed (box 555). If however the stream Sn priority is greater than the lowest priority tasks currently being processed, 15 then the sum of the resources used by these lower priority tasks are then calculated (box 570), using the RUT 415 again (box 575) to provide the resource values (MIPs, memory, etc... - box 565). The RUM 410 then calculates whether the total available system resources 20 which would be available if the lower priority tasks were disabled, is sufficient to enable the Stream Sn (box 580). If so, the lower priority processes are disabled (box 585) and the stream Sn is enabled (box 590). Otherwise, the stream Sn is delayed (box 595).

In this way the system resources are optimally managed, providing dynamic allocation of resources in order to ensure that high priority processes take precedence over lower priority processes.

Using the traditional method to predict a worst-case resource requirement results in systems running in a greatly under utilised manner for most of the time. For practical systems, this means that the processor speed and memory used will greatly exceed that generally required for normal operation. This directly leads to 5 cost and operating power increases.

In contrast, the present invention results in a system in which run-time resource usage is maximised demonstrating improved operation to the user. This also leads to cost 10 and operating power decreases since the design margin for worst-case performance requirements can be reduced as the processor resource scheduler controls resource usage to ensure that the system does not enable tasks that would result in all tasks not being able to run successfully.

It will be appreciated that alternative embodiments to those described above are possible. For example, the software architecture, the types of data and the processing system arrangements may be different from 20 those described above Furthermore, the device processing system described above may be arranged to provide the RUT information and processor capability to a remote server that is the 25 source of the data stream. The server matches the source data parameters (size, coding, etc...) to the resources that the processor has available and transfers the appropriate data stream via the network. In this way the remote server also provides part or all of the functions 30 of the resource utilisation manager (RUM) and makes a decision on the loading of the processor. This may be an adaptive process with the processor providing updates of the RUT to the remote server and the server changing the source data parameters to match the changes to the RUT.

Cla:Lms 1. A processor resource scheduler for a data processing system, the system having a predetermined amount of 5 processing resources and being arranged to process a plurality of data processes, each having processor resource requirements, the scheduler comprising:

resource utilisation manager, arranged for managing the processing of the plurality of data 10 processes; and resource utilisation table, arranged for storing processor resource requirement values of the plurality of data processes and the value of available processing resources of the system, 15 wherein the resource utilisation manager uses the resource utilisation table to determine the scheduling of the plurality of data processes in dependence upon the resource requirements of the data processes and the available processing 20 resources of the system.

2. The processor resource scheduler of claim 1, wherein the resource utilisation table also contains priority information for each of the plurality of data processes.

3. The processor resource scheduler of claim 2 wherein the resource utilisation manager also utilises the priority information from the resource utiiisation table to determine the scheduling of the plurality of data 30 processes.

4. The processor resource scheduler of any preceding claim wherein at least some of the processor resource requirement values for each of the plurality of data processes are provided within the data process.

5. The processor resource scheduler of any preceding claim wherein at least some of the processor resource requirement values for each of the plurality of data processes are provided by extracting from the processing 10 system real-time data describing the utilisation thereof.

6. The processor resource scheduler of any preceding claim wherein the resource utilisation manager is arranged to store previous values of the resource 15 utilisation table values in order to predict future resource requirements based on the previous values.

7. The processor resource scheduler of any preceding claim wherein the data processing system is incorporated 20 in a mobile communications device.

8. The processor resource scheduler of claim 7 wherein the resource utilisation manager is at least partially located at a base station remote from the mobile 25 communications device and coupled thereto via a network.

9. The processor resource scheduler of claim 8 wherein the resource utilisation manager determines which data processes are to be transmitted from the base station to 30 the mobile communications device.

10. An operating system for a processor of a data processing system, the operating system including the processor resource scheduler of any preceding claim.

5 11. A mobile communication device including the operating system of claim 10.

12. A method of scheduling resources for a processor of a data processing system, the system having a 10 predetermined amount of processing resources and being arranged to process a plurality of data processes, each having processor resource requirements, the method comprising:

providing a resource utilisation manager managing 15 the processing of the plurality of data processes; providing a resource utilisation table storing processor resource requirement values of the plurality of data processes and the value of available processing resources of the system, and 20 using the resource utilisation table to determine the scheduling of the plurality of data processes in dependence upon the resource requirements of the data processes and the available processing resources of the system.

13. A processor resource scheduler substantially as hereinbefore described with reference to FIGs. 2 to 4 of the accompany ing drawings.

30 14. A method of scheduling resources for a processor of a data processing system substantially as hereinbefore described with reference to FIGs. 2 to 4 of the accompanying drawings.