Attila Zabos

Robert I Davis

Alan Burns

Michael González Harbour

Spare Capacity Distribution Using Exact Response-Time Analysis

Real-time systems designed for use in dynamic open

environments allow applications to enter and leave the system during runtime. This leads to changing runtime scenarios where the load and the spare capacity of hardware resources is influenced by the resource demand of running applications. Flexible real-time application components, with variable temporal parameters, can adapt their timing behaviour to these changing runtime scenarios and improve both, their Quality of Service (QoS) and the utilisation of system resources. In these open systems application components are often designed independently of each other, introducing the need for system management of resources at runtime. This management requires a mechanism to distribute the available system resources among the running application components, in a way that maximises resource usage and increases QoS with respect to their importance and temporal limits. This paper introduces a runtime algorithm for the distribution of spare capacity in flexible real-time systems. The efficiency of the presented algorithm is evaluated by empirical tests and performance measurements on embedded hardware.

Introduction

In embedded real-time systems being developed today it is common to find requirements for flexibility and support for dynamic behaviour that are key driving factors in the design of their architectures and scheduling methods. Manufacturers of these embedded and resource constrained systems are faced with the difficulty of providing guarantees on the real-time behaviour of their applications while at the same time handling flexibility and dynamic changes to the applications being executed. Traditional real-time scheduling focuses on worst-case behaviour and using it for static configurations implies that a large amount of capacity, that is only used occasionally, is statically allocated in order to manage dynamic changes in application demand. This conflicts with the common requirement to be able to use the maximum possible amount of the available resources.

In this context of requirements for flexibility and support for dynamic behaviour it is possible to design applications that adapt themselves to the available resources, trading the quality of the response with the usage of re-sources. In a system developed with this adaptivity in mind it is possible to maximise resource usage while trying to provide the best possible QoS.

The complexity of modern embedded systems is also driving the need to independently develop applications or application components that may join and leave the system during runtime. The available resources should be dynamically adapted to these changing situations. In most platforms these dynamic changes may be frequent, but not as fast as the regular application periods. We may have new applications that stay in the system for seconds or minutes, while their own internal periods may be in the milliseconds range.

Motivation

Flexible applications come in many different forms. For instance, multimedia systems need to process different kinds of video and audio streams that have highly variable computation times but require real-time processing and rendering. It is common that classic industrial control applications, such as a robot control, get mixed together with multimedia activities when the process in which the robot is working requires image capture and analysis, or remote video monitoring. Mobile phones and other embedded devices are turning themselves into devices with multiple capabilities, including audio and video processing, GPS positioning, Internet navigation, and more, in addition to their original radio link capabilities. In these systems it is common that the user starts or downloads new applications that must run together with the previous ones in an environment with limited resources; and many of these applications have real-time constraints.

Not all the applications running in the system are capable of adapting or adapting equally to the available resources. Most applications will require a minimum amount of resources to produce results of the minimum acceptable quality. Then, some applications may be able to use additional resources, while others won't. Of those that may adapt to the available resources the level of adaptation may be different. For instance, a video player may upgrade itself to a higher frame rate if more resources are available, changing the rate in a continuous way, up to a maximum level after which there is no perceived increase in the quality of the output. These type of applications are referred to as continuous. A con-trol algorithm on the other hand may have two versions: a fast one with a low quality output and one requiring more computation time and providing a high quality output. In this case the system should allocate resources to run either one version or the other. Applications with this type of behaviour are referred to as discrete. In general we find applications that can operate and generate valid results at different frequencies (i.e. having a variable period), and/or handle different processing time assignments (i.e. having a variable execution time).

The FRESCOR1 EU project is developing a middleware layer, that is placed on top of a real-time operating system, with the capability of running multiple application components and scheduling the resources that they need to run. Each application component describes the resource requirements through one or more contracts. These contracts specify the minimum resource requirements and the way in which the component is able to use any additional available resources. The contract is negotiated with the system in order to verify that the minimum resources required can be granted to the application component. Once a contract has been accepted by the system a virtual resource (VR) (which has similar properties to servers [START_REF] Harbour | Architecture and contract model for integrated resources[END_REF]) is allocated to the application component. This VR represents a resource reservation, and manages the consumption of the resource by the application component to ensure that it can always get its allocated budget, and that it never exceeds it, so that other application components can also run in the system with full temporal protection. On the other hand, when application components complete processing and terminate, their VRs are destroyed. In this situation the utilisation of the processing hardware resource decreases, causing an increase of the spare capacity. As a consequence this spare capacity can be distributed to all of the currently active VRs by adapting their parameters.

Since the decision making process for the selection of VR parameters is an online task, there will be a trade-off between the selection of optimal VR parameters and the maximal affordable processing time for this task.

These mixed application and system requirements give us the motivation for an online anytime algorithm that is capable of distributing the spare capacity available in a given system resource. This resource is commonly a processor running tasks, but may also be a network transmitting message streams. The algorithm presented in this paper is designed for fixed priorities, although we believe that it could be easily extended to other scheduling policies. We call this algorithm SCD, for spare capacity distribution.

The SCD algorithm is based on the idea of maximising the utilisation of the processing hardware resource, whilst optimising the QoS of the applications as dictated by their importance and weight. The two attributes, importance and weight, specified in each contract allow the system integrator to control the spare capacity distribution among active applications in the system by defining their significance to the system and relative to each other. The SCD algorithm maximises the hardware resource utilisation by modifying the VRs' temporal attributes during runtime (i.e., budget, period, deadline and as a consequence their priorities as well), under the condition that their temporal requirements are not violated. The search for a feasible spare capacity distribution is an incremental process and it is based on bisection that provides the foundation for a simple and efficient implementation of the presented algorithm in a runtime framework. Furthermore, the algorithm uses response time analysis to test for schedulability, and since this method is known to be exact no schedulability losses are incurred by the test itself. The transition to a system state where the new temporal values and priority ordering are used, is performed at a feasible time instant (e.g., at an idle instant [START_REF] Tindell | A very simple protocol for mode changes in priority preemptive systems[END_REF], or according to the idle instant optimised protocol [START_REF] Harbour | Mode change protocol for budget changes in contract-based scheduling[END_REF]). The protocol for the change from one set of applications to another one, is currently a subject of extensive research. The purpose of this paper is to present and evaluate the SCD algorithm.

Related work

In real-time systems, servers are often used as a resource reservation mechanism to accomplish temporal partitioning among running application components. They provide a budgeting mechanism, which prevents malicious applications from affecting the operation of other applications in the system. Although server concepts [START_REF] Sha | Solutions for some practical problems in prioritizing preemptive scheduling[END_REF][START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF][START_REF] Liu | Real-Time Systems[END_REF] have been introduced to improve the response time of aperiodic tasks, their application has been adapted to provide temporal partitioning among tasks [START_REF] Abeni | Integrating multimedia applications in hard real-time systems[END_REF].

The composition of independently developed applications has been considered by Deng et al. [START_REF] Deng | A scheme for scheduling hard real-time applications in open system environment[END_REF]. They defined a scheme for a two-level hierarchically scheduled open system. Their work was based on dynamic scheduling. Kuo and Li [START_REF] Kuo | A fixed-priority-driven open environment for real-time applications[END_REF] later adapted Deng's approach [START_REF] Deng | A scheme for scheduling hard real-time applications in open system environment[END_REF] to a fixed-priority operating system scheduler.

The FIRST2 project addressed the need for a scheduling framework that could handle applications with varying processing demand [START_REF] Rivas | Fsf: A real-time scheduling architecture framework[END_REF]. The algorithm to adapt the server parameters used utilisation-based schedulability tests which are not exact, thus causing a lower resource usage in the system.

Utilised in this paper are the improvements to the exact schedulability test for fixed-priority tasks that were presented in [START_REF] Davis | Efficient exact schedulability tests for fixed priority real-time systems[END_REF] by Davis et al. and in [7] by Davis and Burns. In our case, the exact schedulability test is applied to VRs and determines whether the full amount of each VR's budget can be utilised before its deadline by the associated application tasks.

The server attributes, importance and weight, that are related to the spare capacity distribution, were intro-duced in [START_REF] Rivas | Fsf: A real-time scheduling architecture framework[END_REF]. They were further adopted for VRs in [START_REF] Harbour | Architecture and contract model for integrated resources[END_REF]. These attributes allow the applications to influence the outcome of the spare capacity distribution.

Rosu et al. [START_REF] Rosu | On adaptive resource allocation for complex real-time application[END_REF] described an adaptive resource allocation mechanism for distributed real-time systems. The expected application resource needs are specified by configurations. The choice of the appropriate configuration and the resulting resource allocations depends on environmental states, availability of resources in the system and the achievable system performance. The resource allocation is carried out as a response to events in the environment and changes in the processing demand of a complex distributed application.

Resource adaptive soft real-time systems were considered by Lin et al. [START_REF] Lin | Diverse soft real-time processing in an integrated system[END_REF]. Here, the Rate-Based Earliest Deadline (RBED) scheduler uses a heuristic algorithm to increase the overall benefit by adjusting the QoS level of the adaptive soft real-time tasks. Since the resource demand varies with the QoS levels, the processing of the adaptive tasks is adjusted so that they can be accommodated on the available resources.

An elastic tasking model has been defined by Buttazzo et al. [START_REF] Buttazzo | Elastic task model for adaptive rate control[END_REF][START_REF] Buttazzo | Elastic scheduling for flexible workload management[END_REF], where the task periods can be adjusted in order to adapt to different load conditions.

Rajkumar et al. [START_REF] Rajkumar | A resource allocation model for qos management[END_REF] introduced a QoS based resource allocation model. Resource allocation to applications is made in terms of resource utilisation, but it is the application's responsibility to choose the appropriate budget and period. The algorithm that determines the resource allocation, requires QoS functions representing resource dependent changes of the application's contribution to the system value. However, the definition of such a function is not always straightforward.

Almeida et al. [START_REF] Almeida | A dynamic scheduling approach to designing flexible safetycritical systems[END_REF] presented an approach to adapt during runtime the temporal parameters of flexible periodic tasks. Each task's execution time and period is expressed as an n-tuple vector for n different QoS levels. From the set of all possible combinations of task parameters, a set of schedulable configurations is deduced by an offline method. This set is used by the online QoS manager to adapt the task parameters.

The SCD algorithm presented in this paper addresses the following issues of previous work: The resource allocation model in [START_REF] Rosu | On adaptive resource allocation for complex real-time application[END_REF] is designed for high performance distributed systems, rather than for embedded real-time systems. Compared to the resource allocation model in [START_REF] Lin | Diverse soft real-time processing in an integrated system[END_REF], we focus on fixed-priority scheduled systems. The elastic task model [START_REF] Buttazzo | Elastic task model for adaptive rate control[END_REF][START_REF] Buttazzo | Elastic scheduling for flexible workload management[END_REF] addresses resource adaptation by changing task periods but not their allocated processing times. In contrast to the scheduling framework in [START_REF] Rivas | Fsf: A real-time scheduling architecture framework[END_REF], the SCD algorithm can be used as an anytime algorithm, and terminate after a maximum execution time providing non-optimal but schedulable VR parameters. Furthermore, loss of distributable spare capacity due to the schedulability test of VRs is prevented by using an exact test. The adaptation method presented in [START_REF] Almeida | A dynamic scheduling approach to designing flexible safetycritical systems[END_REF] conflicts with the notion of open systems due it assumption of static set of tasks that are known before runtime, and is therefore not well applicable to open systems.

System model

It is assumed that a set of flexible application components

{A 1 , A 2 , • • • , A m } are mapped to a set of virtual resources Γ = {S 1 , S 2 , • • • , S n }, with m ≤ n.
The tasks of each flexible application component are mapped to and are executed by one or more VRs. In the former case the application's taskset is mapped to one VR, where in the latter case the taskset is divided into subsets and each subset is mapped to a VR. Unless a one-to-one mapping of task to VR is used, a hierarchical scheduler can be utilised to determine the order of execution of tasks on the same VR. The presence of one or more tasks on a single VR does not affect the spare capacity distribution, as it is done solely for VRs according to their requirements specified in their respective contracts.

The tasks of one application component are not mixed with tasks of other components in the same VR, in order to ensure the temporal protection among them.

Each virtual resource S i is characterised by its processing budget C i , replenishment period T i , deadline D i , importance I i and weight W i .

Each virtual resource S i is either defined as a continuous or discrete VR [START_REF] Harbour | Architecture and contract model for integrated resources[END_REF] depending on the domain of its temporal parameters:

• For continuous VRs, the operational ranges of period and budget are defined by a lower and upper bound,

[T min i , T max i ] and [C min i , C max i ]
, respectively. The actual value assigned to a VR's temporal attribute can take any value from within corresponding operational ranges. The budget and period of continuous VRs are independent of each other and therefore can be adjusted independently.

• For discrete VRs a finite set of (C j , T j , D j ) triples are defined. Only values from this set of (C j , T j , D j ) triples can be assigned to discrete VRs' temporal attributes. This definition implies that temporal attribute values are linked to each other. The budget C i denotes the maximal processing time that can be consumed by a VR before it is suspended. The budget is replenished to its full amount after every period T i .

The deadline D i of a VR specifies the relative time from the point when it has been released until it has to complete the supply of its budget to the associated application component. The deadline D i of a virtual resource S i can be defined to be: 1. equal to its period T i for a continuous VR, 2. equal to D j from the selected (C j , T j , D j ) triple for a discrete VR or, 3. a constant value for both types of VRs. Additionally, it is assumed that the deadline of a VR is always less than or equal to its period, D i ≤ T i .

The priority P i of a VR S i is assigned to it using a

In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 fixed-priority assignment policy. The priority of VRs may change during the spare capacity distribution, but it remains fixed during the steady operational state of the system. If a VR's temporal attribute, which is used by the priority assignment policy, is modified during the execution of the SCD algorithm, then the priority assignment has to be updated. Nevertheless, the constraint D i ≤ T i is not violated by the modification of the period.

For a VR S i two of its attributes, importance level I i and weight W i , are used to influence the outcome of the SCD algorithm. The precedence, in which the spare capacity is assigned to VRs is determined by the importance level I i of the VRs. For the spare capacity distribution, VRs with the same importance level are logically combined into groups. A group G l is the set of all VRs with the same importance level l (see Equation1).

G l = {S i ∈ Γ|I i = l} (1)
Each major iteration of the SCD algorithm is limited to a group G l of VRs. Usually several major iterations of the SCD algorithm are required until a solution is found for the given set Γ of VRs.

The weight attribute W i influences the fraction of the spare capacity that a VR will get. The fair share value [START_REF] Kay | A fair share scheduler[END_REF] denoted as H i is used as a factor to determine the fraction of additional capacity that a virtual resource S i will get when a certain amount of spare capacity is distributed at the currently examined importance level I C (see Equation 2). In this equation, I j denotes S j 's importance level.

H i = W i ∀j:Ij =IC W j (2)
The usage of shared resources and the consequent blocking factors have no direct impact on the SCD algorithm itself. Therefore, there are neither assumptions nor restrictions on the usage of shared resources, since the corresponding blocking factors affect only the schedulability test.

The utilisation caused by a virtual resource S i on a processor is the amount of assigned budget C i per replenishment period T i . The processor's capacity that is unused by VRs is denoted as spare capacity.

The processor's utilisation is calculated as the sum of all VRs' utilisation. The largest utilisation of the processor, determined by the SCD algorithm, at which the set of VRs in the system becomes unschedulable is referred to as the breakdown utilisation. The breakdown utilisation mainly depends on the VR types in the system. With only continuous VRs it is likely that close to 100% processor utilisation is achieved since the utilisation assigned to these VRs can be gradually increased. Whereas with discrete VRs the largest processor utilisation is likely to be significantly less than 100% due to the limited number of VR budget and period values.

Spare capacity distribution algorithm

SCD algorithm characteristics

The intention of the SCD algorithm is to allocate as much as possible of the processor's spare capacity U s to VRs in the system. Of course, after the application of the SCD algorithm, the set of VRs with their new utilisation values has to be schedulable.

The utilisation probe U p is the amount of spare capacity that can be distributed at once among the VRs at the processed importance level.

Since the presented algorithm is a search based approach, feasibility of various probe values need to be tested. An efficient approach to find a feasible probe value U p ∈ {0, 0 + δU p , . . . , U s -δU p , U s } is provided by bisecting the interval [0, U s ] and applying the binary search algorithm to it. The binary search algorithm is fast, has minimal memory requirements and the required processing resources are also low.

For a given set of VRs, the maximal distributable spare capacity can be found within 1 + ⌈log 2 N ⌉ iterations, where N is the number of potential values for U p . Given the granularity δU p of the interval [0, U s ], the number of potential values for U p can be calculated as N = Us δUp . For example, a typical value of 1% for δU p and the possible maximum value for U s of 100%, limits the number of potential values N for U p to 100. By applying the binary search on the 100 possible values, a feasible U p can be determined by checking the schedulability of 1 + log 2 100 = 8 different spare capacity distribution scenarios.

A virtual resource S i is defined to be available/active for spare capacity distribution if it is able to increase its utilisation due to the following conditions:

• During the last iteration of the spare capacity distribution, S i did not render the system unschedulable, • S i has not reached its predefined maximal utilisation and can therefore utilise a higher spare capacity allocation.

In order to determine the optimality of the SCD algorithm the following assumption is made, driven by the FRESCOR project: The spare capacity supplied at higher importance levels is considered infinitely more valuable than at lower importance levels. This implies that different importance levels are incomparable. The SCD algorithm starts with the spare capacity distribution at the highest importance level. Spare capacity is supplied by decreasing the periods and increasing budget of VRs at this importance level. Only after all possible spare capacity has been allocated at the highest importance level, does the algorithm considers the next highest level and so on. Hence, under the assumption that importance levels are incomparable, the SCD algorithm provides the optimal spare capacity distribution.

The schedulability test used by the SCD algorithm is an exact test for fixed-priority scheduled uniprocessor real-time systems [START_REF] Davis | Efficient exact schedulability tests for fixed priority real-time systems[END_REF]. Before the SCD algorithm is ap-plied to the VRs in the system, the schedulability using their minimal timing requirements is ensured. Changes to the set of the VRs in the system are only permitted if the changed set remains schedulable using the minimal temporal requirements of the VRs.

Description of the SCD algorithm

As input, the SCD algorithm requires a priority ordered list of VRs along with their temporal attributes. This priority ordered list (Π) contains VRs that want to benefit from the additional assignment of spare capacity. Π is also used as the output list.

The SCD algorithm starts with the VRs' temporal parameters set to their minimum timing requirements. The minimum timing requirement is either the minimum budget C min i and largest period T max i in the case of a continuous VR, or (C j , T j , D j ) triple with the smallest utilisation in the case of a discrete VR. A soon as the SCD algorithm finds an intermediate or final solution, the new temporal values of the VRs are stored in Π.

With the SCD algorithm, at each importance level the search for the largest feasible U p is carried out in order to determine a feasible spare capacity distribution (see Algorithm 1).

InOut: Π: Priority ordered list of VRs foreach importance level l (in decreasing order) do

Determine Hi for all S l i that are active; while not all possible Up values checked do Calculate ∆Ui (see Equation 3) and increase the current utilisation of S l i to U new i by ∆Ui; Determine S l i new parameters using Algorithm 2; Determine new priority ordering for the schedulability test; if all VRs are schedulable then Store new priority ordering and temporal values of all active S l i in Π;

Algorithm 1: Spare capacity distribution Each major iteration of the SCD algorithm is limited to VRs at a particular importance level, starting at the highest level.

The steps of the SCD algorithm that are executed at every importance level are as follows: 1. Calculate the fair share values.

The fair share value H i of every active virtual resource S i at the currently processed importance level is calculated using Equation 2. This value is used to determine the fraction of capacity that will be assigned to the active VRs. One possible approach to determine the budget and period of a continuous VR S i (with an increased utilisation equal to U new i ) is presented in Algorithm 2. If possible, the VR's smallest period T min i is used and its budget is calculated accordingly. If it is not feasible to use its smallest period, then the minimum budget C min i is fixed first and the period is calculated accordingly. Under both circumstances, the calculated values are restricted to the specified interval for the budget and the period, respectively.

if (C min i /T min i ) > U new i then Ci = C min i ; Ti = min `(C min i /U new i ), T max ´; else Ti = T min i ; Ci = min `(T min i • U new i ), C max ´;
Algorithm 2: Budget and period calculation For a discrete VR, the utilisation values of its different discrete (C j , T j , D j ) triples are calculated. Then the (C j , T j , D j ) triple with the biggest utilisation value, which is less than or equal to U new i , is selected.

Priority assignment

In this paper, the deadline-monotonic priority assignment [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic real-time tasks[END_REF], as provided by the FRESCOR framework, was used for the empirical evaluation. The implementation of the SCD algorithm considers two different VR configurations for the deadline: 1. Virtual resource's deadline is equal to its period, 2. Virtual resource's deadline is constant.

In the case that a VR's deadline is configured to be equal to its period, whenever the period is changed during the spare capacity distribution its deadline is adjusted accordingly and priority reordering is carried out.

Furthermore, the schedulability test of the VRs is carried out in decreasing order of their priorities.

Empirical evaluation

Test data generation

To evaluate the performance of the SCD algorithm, VR sets were generated where the variation of particular isolated test-case parameters was examined. For each The approach, presented by Bini and Buttazzo [START_REF] Bini | Measuring the performance of schedulability tests[END_REF], to create tasks parameters for a given maximal utilisation (subsequently referred to as the Initial Target Utilisation (ITU)), was used in this work to generate the random VR parameters.

The ITU was chosen so that the performance of the spare capacity distribution could be observed in different scenarios where more or less spare capacity was available. The chosen ITUs were 30%, 50% and 80%. Before the VR sets were processed by the SCD algorithm, it was ensured that the generated sets were schedulable at the chosen ITU. Test-cases with initially unschedulable VR sets were not considered in the measurement and they were replaced with a new and schedulable VR set.

The period and budget of the VR is derived from its randomly generated utilisation value. First, the VR's period is chosen according to a uniform random distribution from a randomly selected period magnitude range (i.e. [10 3 , 10 4 ], [10 4 , 10 5 ], [10 5 , 10 6 ] or [10 6 , 10 7 ]). Given the VR's utilisation and period, the calculation of its budget is straight forward.

To take advantage of the flexibility of VRs, a definition for the upper and the lower bound of their utilisation ranges is required. For each VR the initially generated random utilisation values are considered in the tests as their lower utilisation bounds. This lower utilisation bound is used to derive the VR's minimum budget and maximum period. The minimum budget is then multiplied and the maximum period is divided by a factor in order to determine the VR parameters (i.e. maximum budget and minimum period) for its upper utilisation bound. A factor of 2.0 for the 30% ITU, and a factor of 1.5 for 50% and 80% ITU was used.

For discrete VRs, additional to their lower and upper utilisation bounds, a random number of intermediate utilisation values were generated. The number of intermediate values was in the range of 1 to 3, where 5 is the maximum number of discrete temporal attributes defined by the FRESCOR framework.

Experiment evaluation

This section evaluates the data, which was collected from various measurements by varying different parameters as indicated in Section 6.1. The diagrams show the progress of the spare capacity distribution as a function of the number of ceiling operations needed by the schedulability analysis, a useful proxy for algorithm execution time [START_REF] Davis | Efficient exact schedulability tests for fixed priority real-time systems[END_REF]. This section uses the number of ceiling operations to give insight into the complexity of the algorithm. Section 7.2 extends this information by mapping it onto absolute time. In the following, the term number of ceiling operations will be referred to as num-ber of iterations.

The presented experiments contain a mixed set of VRs (both continuous and discrete). The only exception is the experiment in which the impact of the different temporal attribute types (i.e. discrete or continuous) on the SCD algorithm is examined.

For the sake of clarity, the diagram types used to support the empirical evaluation are introduced in Figure 1. Of main interest are the following properties of the SCD algorithm: how fast can the spare capacity be distributed and the number of iterations required by the algorithm to terminate. The average increase of processor's utilisation as the SCD algorithm progresses, is depicted in Figure 1a. The percentage of test-cases terminated by a certain number of iterations is depicted in Figure 1b. This figure can also be interpreted as the probability that the SCD algorithm will terminate within a given number of iterations for a given number of VRs.

For all experiments the SCD algorithm was executed until it terminated itself. The processor's utilisation achieved in this way is the highest schedulable utilisation of the active VRs in the system.

In Figure 1 the effect of the number of VRs on the SCD algorithm is examined. Figure 1a shows that the rate of the average utilisation increase from an ITU of 50% slows up when the number of VRs in the system is increased. The number of iterations required to terminate with a particular probability also increases with the number of VRs (see Figure 1b). The diagrams indicate that more iterations are required to find a feasible spare capacity distribution as the number of VRs in the system increases. This comes about due to the increased number of schedulability tests that are required for each VR utilisation level.

In dynamic real-time systems the processor's utilisation at which application components are submitted into the system cannot be predicted in advance. Therefore, the impact of the initial processor's utilisation on the progress of the SCD algorithm was also considered (see Figure 2). In Figure 2a it can be observed that the ITU has an effect on the processor's utilisation increase only at the beginning of the algorithm. In the long term (i.e. above 2000 iterations) the ITU becomes irrelevant and the utilisation increase is dominated by the number of VRs in the system. The probability for the termination of the SCD algorithm is influenced from the beginning by the number of VRs and the ITU has only a negligible effect (see Figure 2b). The effect of the ITU is small since the number of schedulability tests that are carried out during the runtime of the SCD algorithm stay nearly identical for various ITUs.

The VR's temporal attributes can be either of continuous or discrete type. Hence, there can be three different VR sets in the system. Only continuous, only discrete or a mixed set of VRs. Our experiments show that the temporal attribute type has only a minor effect on the increase of the processor's utilisation and the runtime of the SCD algorithm. For space reasons, these results are not included in this paper but are available in a technical report [START_REF] Zabos | Utilization based spare capacity distribution[END_REF].

The VR to importance levels has been analysed in two scenarios (see Figure 3). In one scenario, the VRs have been randomly distributed among the available importance levels. In the other scenario, they have been assigned to a single importance level. Figure 3a shows that the use of a single importance level had a negative effect on the processor's utilisation increases. These are much slower although in long term, the processor's utilisation values for both scenarios converge towards each other. On the other hand, the number of iterations required for the termination of the algorithm decreased if a single importance level was used (see Figure 3b). In this case, performing the schedulability test for the empty importance levels was avoided, which led to the reduction in iterations.

Figure 3. Importance level allocation

The measured data, presented in this section, reveal that the performance of the SCD algorithm is mainly influenced by the number of VRs in the system.

Performance evaluation

This section provides information about the embedded hardware that was used for the performance measurements and the absolute values for the execution times obtained. Additionally, using a pragmatic approach, a linear upper bound equation is derived for the execution time of the SCD algorithm. This allows us to determine the required budget for the SCD algorithm, in order to provide a complete or partial solution for the spare capacity distribution of the system.

Test environment

The empirical evaluation, which was presented in Section 6, is extended by performance measurements on an embedded platform. The intention of this task is to determine which parameters influence the SCD algorithm's execution time.

In order to exclude operating system and other undesirable overhead, an embedded system was configure in a way that only the spare capacity distribution was executed. This provided the facility to obtain absolute values for the execution time of the SCD algorithm.

The embedded platform consisted of an MPC555 microcontroller running at 40 MHz system clock.

To create the target executable file, a development environment comprising the GNU C compiler and RapiTime version 1.2, a tool for worst-case execution time analysis, was used. The executable files were optimised by the compiler using the option -O2. To avoid falsification of the measurements by intermediate performance monitoring of the SCD algorithm, only endto-end execution times were recorded.

Due to the limited performance of the embedded system, the number of test cases used was reduced to 3000 randomly generated VR sets for each fixed number of VRs in the set (i.e. 5, 10, 15,. . . , 45, 50 VRs). The ITU (i.e. 30%, 50% or 80%) and the type of the VR sets (only continuous, only discrete or mixed type) were randomly created for each of the 3000 sets. Nevertheless, sufficient data was captured to analyse the behaviour of the SCD algorithm on real hardware.

Measurement

During the design phase of real-time systems, information is required about the expected complexity of the SCD algorithm. In the following, an upper bound equation will be defined that allows engineers to determine during the design phase the required amount of budget for the SCD algorithm.

As an initial step, the dependency of the SCD algorithm's execution time on the number of iterations and VRs in the system was examined. Figure 4 shows for different numbers of VRs the execution time plotted against the number of iterations and the corresponding regression lines. Since the scatter of the measured values along the x-axis is very narrow for the test-cases with 5, 10 and 15 VRs, their regression lines are omitted.

To determine the necessary values for the linear upper bound equation, the least-squares linear regression method was applied to the collected data. 4 indicate that the slope of each regression line is very similar. This observation suggests a linear dependency of execution time on the number of iterations.

But a single linear equation is not sufficient to express the execution time of the SCD algorithm. Since the regression lines do not overlap but have an offset between them, the dependency of this offset on the number of VRs has been examined as well. In Figure 4 the intersection points of the regression lines with z-y-plane shows that the offset also increases linearly with the number of VRs in the system. The equation, which describes the y-axis intersection of the execution time regression lines against the number of VRs, was also determined via linear regression (see Equation 4).

y 0 (v) = 2.381 • v -21.397 (4)
The former analysis reveals that the execution time depends mainly on two parameters. Figure 4 shows the execution times plotted along the y-axis. The x-axis represents the number of iterations and the z-axis the number of VRs. The observable linear behaviour of the plotted data along the x-axis as well as along the z-axis suggests the definition of the execution time upper bound as a plane equation with the number of iterations and VRs as independent variables. Next, the coefficients, a 1 and a 2 , for the plane equation were specified. They were derived from the data that was obtained by measurements on the embedded platform.

The first coefficient, a 1 , was determined by calculating the average slope of the execution time regression lines. The average value is approximately 1.58224 • 10 -3 , but for ease of use, this value has been rounded up to 1.6 4) until the regression lines in Figure 4 became the upper bound on the measured execution times for the corresponding set of VRs (i.e. every execution time sample was below the upper bound). Using this information, an execution time upper bound equation for the SCD algorithm was derived (see Equation 5). The equation represents a pragmatically derived execution time upper bound for the MPC555 microcontroller that was used to carry out the performance measurements.

C(n, v) = 0.0016

• n + 2.8 • v (5)
To get an idea of how the execution time upper bound increases with system complexity, the upper bound was plotted against the number of VRs in the system and the number of iterations. The data that was generated by the application of Equation 5 spans a plane in three dimensional space. The plane in Figure 5 illustrates the execution time upper bound of the SCD algorithm. For the sake of clarity contour lines are rendered at 50 ms intervals.

Figure 5. Execution time upper bound

In order to determine the required budget for the SCD algorithm, the expected maximal number of VRs in the system and the granted maximal number of iterations for the runtime of the algorithm has to be specified. The parameter, maximal number of iterations, also influences the probability of the SCD algorithm terminating within the determined budget. The probability of termination within a certain number of iterations has already been investigated during the empirical evaluation in Section 6.2. It can be summarised as follows.

Table 2 shows the maximal number of iterations that were required by the SCD algorithm to terminate for 99.99%, 99.90%, 99.00% and 90.00% of the test-cases. There is a slight difference in the number of required iterations for the algorithm among the test-cases that were performed with 30%, 50% and 80% ITU; but the great-est observed values were chosen. Based on the data that was collected during the empirical evaluation and the performance measurements, the required budget for the SCD algorithm can be derived for a real-time system using an MPC555 microcontroller and a specified maximum number of VRs.

As an example, we now determine the budget for two different configurations. First, the budget for the SCD algorithm on a system with a maximum of 5 application components is calculated. The budget is chosen such that the algorithm can terminate in 99.99% of the cases. Applying the information from Table 2 in Equation 5, provides a budget estimate of C(3000, 5) = 0.0016 • 3000 + 2.8 • 5 = 18.8ms. For the second example, we assume a system with at most 25 components. Again, the budget should allow the SCD algorithm to terminate in 99.99% of the cases. Hence, the estimated budget is C(45000, 25) = 0.0016•45000+2.8•25 = 142ms. The calculated values for the examples are also illustrated in Figure 5.

The two coefficients, a 1 and a 2 , of the linear equation depend on various hardware factors, like the availability and size of data caches, data bus bandwidth, external memory speed, etc. They also depend on the location (i.e. internal or external memory) of the relevant processing data. Therefore, the linear equation representing an upper bound for SCD algorithm's execution time, has to be individually derived for each hardware platform. This can however easily be performed using a suitable program for calibration, such as the one used to generate the results presented here.

Conclusion

In this paper we presented an easily and efficiently implementable algorithm for the distribution of a processing resource's spare capacity. The contribution can be summarised as:

• an anytime SCD algorithm that can generate useful results even if the algorithm's execution time is limited, • runtime adaptation of continuous and discrete VR temporal parameters (i.e. budget and period), • preventing schedulability test based inefficiency using an exact test.

In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

The efficiency of the SCD algorithm was examined by empirical evaluation and performance measurements on an embedded platform.

The performance evaluation of the SCD algorithm shows that, for example in a system with up to 25 mixed VRs, the algorithm terminates in 99.99% of the cases within 45000 iterations, and within the same number of iterations the processor reaches an average utilisation of 98%. Based on the upper bound equation (Equation 5), the worst-case execution time for 45000 iterations and 25 VRs is equivalent to 142 ms on an MPC555 microcontroller with a system clock of 40 MHz. The MPC555 is not however a sufficiently powerful processor to support 25 application components.

On faster processors, the cost for one iteration of the SCD algorithm, as well as the overall execution time, decreases. Therefore the complexity of a system, measured in terms of the number of active VRs, for which the SCD algorithm can be considered applicable, increases. For example, a processor with approximately 10 times the performance of a 40MHz MPC555 might be used in Avionics or Telecommunications applications that need to support 10 to 25 application components. In this case, such a processor would require at most 15ms to execute the SCD algorithm.

The SCD algorithm shown in this paper has been integrated into the FRESCOR framework, giving it the capability to distribute spare capacity among different application components with the objective of fully using the available processor capacity and maximising the QoS. While the algorithm is based on the current implementation of FRESCOR on fixed priorities, we believe that it is easily extensible to other scheduling policies and tests. As future work we will investigate the mode change protocols used to make effective the calculation of a new resource allocation as a result of the SCD algorithm. Furthermore, the allocation of multiple resources (e.g. processor, network bandwidth, memory, etc.) to application components and their interdependency will be examined.

Figure 1 .

 1 Figure 1. Number of VRs: 5, 10, ..., 50

Figure 2 .

 2 Figure 2. ITU: 30%, 50% and 80%

Figure 4 .

 4 Figure 4. Execution time samplesThe general form of the plane equation can be defined as C(n, v) = a 1 • n + a 2 • v, with C(n, v) representing the execution time, n the number of iterations and v the number of VRs.Next, the coefficients, a 1 and a 2 , for the plane equation were specified. They were derived from the data that was obtained by measurements on the embedded platform.The first coefficient, a 1 , was determined by calculating the average slope of the execution time regression lines. The average value is approximately 1.58224 • 10 -3 , but for ease of use, this value has been rounded up to 1.6 • 10 -3 .Finally, the value of the second coefficient, a 2 , was defined. Based on Equation 4 and on the data of Figure4, the value of 2.8 was determined for a 2 . This value was obtained by the application of pragmatic steps in or-

  2. Search for a feasible spare capacity distribution. The algorithm considers only VRs that are active (i.e. capable of accepting more than their current utilisation) at the currently examined importance level. Using binary search (represented by the whileloop condition in Algorithm 1), the distributable spare capacity U p is narrowed down to the largest value at which the system is schedulable, but where an additional amount (δU p ) of spare capacity assign-ment (i.e. U p + δU p ) would cause an infeasible schedule. For each utilisation probe U p , the temporal parameters of active VRs at the currently examined im-

	portance level are recalculated using Algorithm 2,
	where U new i by ∆U i .	denotes the increased utilisation of S i
		∆U i = U p • H i	(3)
	3. Increase active VRs' utilisation.
	If a schedulable spare capacity distribution has been
	found, the new VR temporal parameters are stored in
	the output list Π regardless of whether these values
	are intermediate or final.

  In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 of these VR sets 100000 different configurations were created. Each configuration consists of the predefined number of VRs (i.e. 5, 10, 15, . . . , 50) for which randomly generated VR parameters (i.e. budget, period and deadline) were created.

  Table 1 summarises the parameters of the regression lines from Figure 4. The data in Table 1, as well as visual inspection of Figure

Table 1 . Regression line parameters

 1

	VR#	Function	Slope `10 -3 ´Y-axis offset
	50	f50(x)	1.5425	99.287
	45	f45(x)	1.5520	87.238
	40	f40(x)	1.5579	75.519
	35	f35(x)	1.5722	64.308
	30	f30(x)	1.5862	53.022
	25	f25(x)	1.6263	42.277
	20	f20(x)	1.6386	32.486

  • 10 -3 . Finally, the value of the second coefficient, a 2 , was defined. Based on Equation 4 and on the data of Figure 4, the value of 2.8 was determined for a 2 . This value was obtained by the application of pragmatic steps in or-In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 der to simplify Equation 4. The aim was to preserve just a single factor that expresses the dependency between the number of VRs, and the y-axis intersection of the lines that represent the execution time upper bounds for each set of VRs. The value of coefficient a 2 was increased from the value starting at 2.381 (as specified by Equation

Table 2 . Number of iterations

 2

	VR#	99.99%	99.90%	99.00%	90.00%
	5	3000	2000	1000	1000
	10	9000	6000	4000	3000
	15	18000	14000	10000	6000
	20	32000	24000	18000	12000
	25	45000	36000	27000	18000
	30	58000	49000	38000	26000
	35	77000	66000	51000	36000
	40	98000	86000	68000	49000
	45	135000	108000	85000	62000
	50	157000	132000	107000	77000

Framework for Real-time Embedded Systems based on COntRacts[START_REF] Harbour | Architecture and contract model for integrated resources[END_REF]

Flexible Integrated Real-Time Systems Technology In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

Acknowledgements

This work was funded in part by the EU FRESCOR project (contract number FP6/2005/IST/5-034026). We would also like to thank Rapita Systems Ltd. 3 for providing the necessary equipment and tools for the performance measurements. Furthermore, we would like to thank Daniel Sangorrín López for his valuable comments.


Vandy Berten
email: vandy.berten@ulb.ac.be

Joël Goossens
email: joel.goossens@ulb.ac.be

Multiprocessor Global Scheduling on Frame-Based DVFS Systems

In this work, we are interested in multiprocessor energy efficient systems where task durations are not known in advance but are known stochastically. More precisely we consider global scheduling algorithms for frame-based multiprocessor stochastic DVFS (Dynamic Voltage and Frequency Scaling) systems. Moreover we consider processors with a discrete set of available frequencies.

We provide a global scheduling algorithm, and formally show that no deadline will ever be missed. Furthermore, we present simulations showing that we have an energy benefit in doing global scheduling instead of static partitioning.

Introduction

Nowadays, it is straightforward that energy efficiency is a crucial aspect of embedded systems where a huge number of small and very specialized autonomous devices are interacting together through many kinds of media (wired/wireless network, bluetooth, GSM/GPRS, infrared. . . ). Moreover, we know that the uniprocessor paradigm will no longer hold in those devices. Even today, a lot of mobile phones are already equipped with several processors.

In this work, we are interested in multiprocessor energy efficient systems, where task durations are not known in advance, but are known stochastically, which means that we know the probabilistic distribution of their execution time. More precisely, we consider global scheduling algorithms for frame-based multiprocessor stochastic DVFS (Dynamic Voltage and Frequency Scaling) systems. Moreover, we consider processors with a discrete set of available frequencies.

In the past few years, a lot of work has been provided in multiprocessor energy efficient systems. Most work was done considering static partitioning strategies, meaning that a task was assigned to a specific processor, and each instance of this task runs on the same processor. First of those work were devoted to deterministic tasks (with a task duration known beforehand, or the worst-case is considered), such as [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Yang | An approximation algorithm for energy-efficient scheduling on a chip multiprocessor[END_REF][START_REF] Chen | Energy-efficient scheduling of periodic real-time tasks over homogeneous multiprocessors[END_REF][START_REF] Chen | Multiprocessor energyefficient scheduling for real-time tasks with different power characteristics[END_REF], and later probabilistic mod-els were also considered [START_REF] Xian | Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time[END_REF][START_REF] Mishra | Energy aware scheduling for distributed real-time systems[END_REF]. Only a little work has been provided about global scheduling, such as [START_REF] Chen | Multiprocessor energy-efficient scheduling with task migration considerations[END_REF], but for deterministic systems, or [START_REF] Zhu | Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor real-time systems[END_REF], using some slack reclamation mechanism, but not really using stochastic information.

As far as we know, no work has been provided with global scheduling on stochastic tasks. We propose to work towards this direction. Notice that the frame-based model we consider in our work, where all tasks share the same (synchronous) period or deadline, is also used by many researchers, such as [START_REF] Yang | An approximation algorithm for energy-efficient scheduling on a chip multiprocessor[END_REF][START_REF] Chen | Multiprocessor energy-efficient scheduling with task migration considerations[END_REF][START_REF] Mishra | Energy aware scheduling for distributed real-time systems[END_REF][START_REF] Zhu | Scheduling with dynamic voltage/speed adjustment using slack reclamation in multi-processor real-time systems[END_REF]. This model attracts a lot of attention, both from industry and theoretical community. In the current state of the art of stochastic lowpower multiprocessor systems, the knowledge we have about very general models is not accurate enough to allow practical implementations. This is why simple but realistic models are interesting, but can be seen as a step towards more general models which are going to be considered in a near future.

The contribution of this paper is to provide a first algorithm allowing to efficiently schedule a frame-based task set on a multiprocessor DVFS platform. We will proof that our algorithm never misses deadlines, and will show how we can save energy, compared to partitioned systems.

The paper is organized as follows: we first present the task and system model we consider. Secondly we present our algorithm, and prove its correctness. Then we provide some simulation results attesting the benefit of doing global scheduling, and finally we conclude and give some perspectives.

Model

We consider a set of n non parallel and non preemptive tasks τ = {τ 1 , . . . , τ n }. Task τ i requires x cycles with a probability c i (x), and its maximum number of cycles is w i (Worst Case Execution Cycles, or WCEC). The number of cycles a task requires is not known before the end of its execution. We consider a frame-based model, where all tasks share the same (synchronous) period or deadline D. In the following, D denotes the frame length, and as we manage each frame independently, we denote by t = 0 the beginning of each frame.

Those tasks run on m identical CPUs Π 1 , . . . , Π m , and each of those CPUs can run at M frequencies f 1 , . . . , f M .

In this work, the execution time is assumed to be strictly proportional to the CPU frequency: if task τ i takes α units of time at frequency f k , the same task would have taken

α f k f at frequency f .
We consider that tasks cannot be preempted, but different instances of the same task can run on different processors, i.e., task migrations are allowed, but job migrations are not. We are interested in global scheduling techniques which schedule a queue of tasks; each time a CPU is available, it picks up the first task in the queue, choose a frequency, and run the job. We assume the system is work conserving 1 , and the job order has been chosen beforehand, but in some cases, in order to ensure the schedulability, the scheduler can adapt that order. In other words, we assume that the initial task order is not crucial and can be considered to be a soft constraint. We will discuss later in this work the importance of the task order.

Examples

A simple example where this kind of system can be useful is a system where n web-cams are connected to a device with m processors. If the web-cams are synchronous, they could all send an image, let say, 24 times a second, and all those images should be processed before the next arrival. Task τ i consists then in processing the images of the i th web-cam, which can be done on any of the m processors.

A symmetric example can also be considered: a m-CPUs device receives a stream containing, 24 times a second, n compressed images to decompress, and to send to n screens. In both cases, we know the distribution of the processing time, and would like to reduce as much as possible the energy consumed by the processors.

Global Scheduling Algorithm

In [START_REF] Berten | Discrete frequency selection of frame-based stochastic realtime tasks[END_REF], we have provided techniques allowing to schedule such a task set on a single CPU. The main idea is to compute (offline) a function giving, for each task, the frequency to run the task based on the time elapsed in the current frame. This function, S i (t) gave the frequency at which τ i should run if started at time t in the current frame. Here, for the sake of clarity, we are going to consider the symmetric function of S: Ŝi (d) def = S i (D -d) gives the frequency for τ i if this task is started d units of time before the end of the frame.

In the uniprocessor case, we were able to give schedulability guarantees, as well as good energy consumption performance, using the worst case number of cycles, as well as the probability distribution of the number of cycles. We want to be able to provide both in this multiprocessor case, using a global scheduling algorithm. As far as we know, global scheduling algorithm on multiproces-sor system using stochastic tasks, and a limited number of available frequencies, has not been considered so far.

The idea of our scheduling algorithm is to consider that a system with m CPUs, and a frame length D, is "close" to a system with a single CPU, but a frame length m × D, or, with a frame length D, but m times faster. We then first compute a set of n Ŝ-functions considering the same set of tasks, but a deadline m × D. A very naive approach would consist in considering that when a task ends at time t, the total remaining available time before the deadline is the sum of remaining time available on each CPU, which means D -t on the current CPU, and D -t p on the other ones, where at each instant, t p represents the worst time at which the task currently running on Π p will end, or the current time if no task is running. Then, we could use Ŝi (d) to choose the frequency.

Unfortunately, this simple approach does not work, because a single task cannot use time on several CPUs simultaneously, i.e., task parallelism is forbidden. However, if the number of tasks is reasonably greater than the number of CPUs, we think that in most cases, Ŝi (d) will not require to use more than the available time on the current CPU, and somehow, will let the available time on other CPUs for future tasks. And when Ŝi (d) requires more time than actually available, we just use a faster frequency.

Of course, we need to ensure the schedulability of the system, which cannot be guaranteed with the previous approach: for instance, at the end of a frame, we might have some slack time unusable because too short to run any of the remaining tasks. But as this time has been taken into account when we chose the frequency of previous tasks, we might miss the deadline if we do not take any precaution.

The algorithm we propose is composed of two phases, an off-line phase, and an on-line one. The off-line one consists in performing a (virtual) static partitioning, aiming at reserving enough time in the system for each task. This phase is close to what we did in [START_REF] Berten | Discrete frequency selection of frame-based stochastic realtime tasks[END_REF] using the concept of Danger Zones. Briefly, in uniprocessor systems, the danger zone of a task τ i starts at z i , where z i is such that if this task is not started immediately, we cannot ensure that this task and every subsequent tasks can all be finished by the deadline. In other words, if a task starts in its danger zone, and this task and all the subsequent ones use their WCEC, even at the highest frequency, some tasks will miss the (common) deadline.

The on-line phase uses both this pre-reservation to ensure the schedulability (but performing dynamic changes to this static partitioning), and the Ŝ-functions, to improve the energy efficiency.

Virtual Static Partitioning

This first phase, which is performed offline, aims at "virtually" assigning each task to one processor -virtually meaning that a task assigned to a processor does not necessarily run on that processor -in such a way that if each task assigned to one processor takes its worst case execution number of cycles, we can still manage to finish those tasks in a frame of length D. Figure 1, left part, shows an example of such a partitioning. This basic idea is to put those tasks on the right side of the schedule (in light grey on Figure 1), just before the deadline, with the amount of time they would need to run in the worst case at the highest frequency. We call this grey zone the reservation zone. When we start a task, we remove it from this reservation zone, and start it, but in a way that a task that we run will never overlap with a task reservation even in the worst case.

The partitioning problem boils down to have n objects of size wi f M , ∀i ∈ {1, . . . , n} that we need to put in m boxes of length D. This is actually a bin packing problem, and the optimal algorithm (giving a valid partitioning for every partitionable system) is known to be NP-hard [START_REF] Garey | Computers and Intractability : A Guide to the Theory of NP-Completeness[END_REF].

If we denote by Γ p the set of tasks assigned to CPU Π p , we need to find an assignment such as:

τq∈Γp w q f M ≤ D ∀p ∈ {1, . . . , m},
meaning that no CPU has more than what it could run in the worst case, and

∀p = q, Γ p ∩ Γ q = ∅
meaning that a task cannot be assigned to several processors,

p Γ p = τ
which means all the tasks are assigned to some processor. During the on-line phase, the partitioning will be updated by moving some tasks from a processor to another one. As long as those tasks have not started yet, they can be moved without any migration cost. But of course, a task can be moved to a processor Π p only if there is enough space between t p (the worst end of the task currently running on this CPU), and D -A p (the begin of the reservation zone, assuming the frame starts at time 0).

This static partitioning can be performed in many ways, but we propose in Algorithm 1 to do it as balanced as possible, by sorting tasks according to their WCEC.

Algorithm 1: Static partitioning

A p = 0 ∀p ; // Reserved time on Π p Γ p = {} ∀p ; // Tasks assigned to Π p 1 foreach τ i descending sorted by w i do 2 q = argmin p A p ; // C P U with the

3 largest not yet assigned time if D -A q > wi f M then 4 A q = A q + wi f M ; // τ i reservation 5 Γ q = Γ q ∪ τ i ; 6 else 7 Failed! 8
After this first step of virtual static partitioning, we can see the system as in Figure 1, left part. A p is the length of the reservation zone on Π p , then the length of the grey part.

Notice that it is not because we cannot manage to do this virtual partitioning that the system is not schedulable. But at least, if we manage to do so, then we can ensure that the system is schedulable, as we will show formally later in this paper. This virtual static partitioning can be computed offline, and used for the whole life of the system.

This partitioning can be done in O(n × log m), if A p 's are stored in a heap. We also need in the off-line phase to compute the Ŝ-functions, which can be done in O(n 2 × M × W ), where W is the number of samples in the distribution, using for instance the PITDVS closest algorithm described in [START_REF] Berten | Discrete frequency selection of frame-based stochastic realtime tasks[END_REF].

Notice that the static partitioning aims at reserving the minimum amount of time required in the worst case, then this amount of reserved time corresponds to the time needed to run the worst case at the highest frequency f M . Moreover, if the task number (written on tasks in Figure 1) gives the order in which tasks should be run, the partitioning is done sorting tasks on their worst case execution time. So the order shown on the partitioning could seem to be randomly chosen regarding to tasks number. However, tasks (virtually) assigned to a CPU can be seen as an unordered set: the only information we will need later about this task set is its total size. And except in some specific cases, tasks will be picked up by increasing task number.

Figure 1 Left: Static partitioning. Right: State of the system after having started tasks {τ 1 , . . . , τ 7 }. Notice that reservations (light grey tasks, right aligned) correspond to worst cases, while effective tasks (white tasks, left aligned) are actual execution times, and change then from frame to frame. Vertical axis is frequency, horizontal is time. Then areas correspond to amount of computation.

On-line Algorithm

Based on the virtual static partitioning, the main idea of the on-line part is to start a task at a frequency which allows it to end before the beginning of the reserved zone on this processor. For instance, in Figure 1, τ 1 could start on Π 1 using all the space between the beginning of the frame, and the reserved space for τ 5 . But we will see situations where it would be more energy efficient to give more time for τ 1 , in order to run it slower. In such cases, we can also move, for instance, τ 5 or τ 6 on Π 2 , or τ 12 to Π 3 . By doing so, and because we never let a running task using the reserved time of another (not started) task, we can guarantee that, if we were able to build a partitioning in the off-line phase, no task will never miss its deadline. A formal proof of this will be given in Section 3.3. Of course, as soon as a task starts, we release the reserved time for this task.

The on-line part of the algorithm is given in Algorithm 4. We first give some explanation about two procedures we need in the main algorithm.

Remark that as we only move tasks which have not started yet, we do not need to move any context or perform any migration. The only thing we change is the information that, in the future, a job is going to start on a given processor.

MoveTasksOut

This procedure (Algorithm 2) aims at moving enough tasks from CPU Π p , until enough space (the quantity s in the algorithm) is available, or no task can be moved anymore. For instance, in Figure 1, at time t = 0, we may want to run τ 1 on Π 1 at frequency f 2 . But according to the worst case of τ 1 , we do not have enough time to run this task between 0, and the beginning of the reserved area of τ 5 . However, we can move τ 3 to Π 3 , and τ 5 or τ 6 to Π 2 .

While s units of time is not available, we take the largest task on Π p , and put it on the CPU with the largest free space, where the free space is the space between t q , the worst end of current job, and D -A q , the begin of the reservation zone. This is of course an heuristic, since finding the optimal choice is probably an NP-hard or at least an intractable problem. We will show an improvement for this heuristic further on this paper.

This algorithm has a time complexity of O(n × log m): the main loop can be at most run once for each task, and the argmax operation can have a complexity of log m.

MoveTaskIn

This procedure (Algorithm 3) aims at trying to move a task τ i assigned to a CPU Π q to the CPU Π p . The main idea is that we first move out as many tasks as needed from Π p (line 1), until we have enough space to move τ i in (lines 2 to 5). If we have not managed to get enough space, false is returned (line 7). Again, this algorithm is an heuristic, and is not always able to find a solution, even whether such a solution exists.

For instance (see Figure 1, right part), at the end of τ 7 , we would like to start τ 8 on Π 1 . But neither τ 9 nor τ 12 can be moved on another CPU, so our algorithm fails in finding a solution. However, a smarter algorithm could find out that by swapping τ 8 and τ 9 , τ 8 would be able to Algorithm 2: MoveTasksOut Data: processor Π p , current time t, space to free s // Move out tasks from Π p until s units of time are free from t. while D -A p -t < s do 1 τ i = next task in Γ p (sorted by decreasing w i );

2 if No such τ i then 3 return false; 4 q = argmax r =p D -A r -t r ; // C P U with 5 the maximal amount of available space if D -A q -t q ≥ wi f M then 6 // Enough place to move τ i on Π q Γ p = Γ p \ τ i ; A p -= wi f M ; 7 Γ q = Γ q ∪ τ i ; A q += wi f M ; 8 return true; 9 start on Π 1 .
Notice that giving a solution in any solvable case is probably also an NP-hard or at least an intractable problem.

The procedure we give here is quite naive, and not very efficient. We keep it simple for the sake of simplicity, but we present some improvements afterwards. The naivety of this algorithm does not affect the schedulability at all: it just makes the system to be forced more often to accept tasks order changes, which might degrade the energy efficiency (S-functions are computed according to the given order), and the user satisfaction, if its preferences are often not respected.

Algorithm 3: MoveTaskIn

Data: processor Π p , current time t, task τ i , Result: true if τ i can be moved on Π p , false otherwise // Move enough tasks from Π p to let

τ i running if MoveTasksOut(Π p , t, wi f M ) then 1 // We know that D -A p -t ≥ wi f M let q be such as τ i ∈ Γ q ; 2 // Move τ i from Π q to Π p Γ q = Γ q \ τ i ; A q -= wi f M ; 3 Γ p = Γ p ∪ τ i ; A p + = wi f M ;

Main algorithm

Here are the main steps of the procedure given in Algorithm 4, which is called each time a CPU (say Π p ) is available, at time t, with τ i the next task to start. This procedure will always start a task at a speed guaranteeing deadlines, but not necessarily τ i .

• line 1: We first evaluate d, the remaining time we have for τ i , . . . , τ n : if t q is the worst time where Π q is going to be available (the time of the last start, plus the worst case execution time of the current task at the chosen frequency), we have:

d = (D -t) + q =p (D -t q ) = mD -   t + q =p t q   .
• line 2: Let f = Ŝi (d), the frequency chosen for τ i in the single CPU model with d units of time before the deadline. We are going to check if we can use this frequency (we assume this frequency to be a "good" one from the energy consumption point of view).

• line 3-6: If τ i was not assigned to Π p , we first try to move it to Π p (Algorithm 3). If we have enough space on Π p , the situation is easy. Otherwise, we need to move some tasks out from Π p , in order to create enough space.

• line 5: If we cannot manage to make enough space, then we are not able to start τ i right now. We try then the same procedure for τ i+1 , but we need to left-shift Ŝ-functions of wi f M . This is not required from the schedulability point of view (we ensure the schedulability by controlling the available time), but we guess it will improve the energy consumption. For the same reason, we will need to right-shift functions of the same amount when τ i starts, because we have one task less to run after τ i . This improvement is not presented here, but we have implemented it in the simulation we present in this paper. It requires to be done carefully, because we might have several swapped tasks.

• line 9: If we succeeded, we try to move as many tasks as possible from Π p to other CPUs (Algorithm 2), until we have enough space to start τ i at f , or no task can be moved anymore. We then start τ i either at f , or at the smallest frequency allowing to run τ i in the space we manage to free (line 10). As τ i was assigned to Π p (possibly after some changes), we are at least sure that we can start τ i at f M .

Notice that when StartTask is invoked, it is always possible to run a job, and therefore, we will never consider τ n+1 in Algorithm 4, line 5 (see next section for a proof).

The complexity of StartTask is a little bit complex, because this function is recursive. Let first compute the complexity when we do not need to invoke If we do invoke StartTask recursively, then in the worst case, we have a depth of n calls. In this case, lines 1 to 5 are run n times (O(n × (m + n log m)), and lines 7 to 12 only once (O(n log m)). Then, in total (O(n × (m + n log m)).

Correctness

In this section, we will show the correctness of this algorithm, meaning that the on-line algorithm does not jeopardize the schedulability provided by the off-line phase. We will need two proofs for this: first, we will show that if we are able to obtain a virtual static partitioning, then we will always meet the deadline. Then, we will show that the algorithm "StartTask" runs all the tasks.

We remind the reader that t q is the worst end time of tasks running on Π q . If no task is running on this CPU, t q is actual end time of the last task which ran on Π q , 0 if no task has ever started on this CPU.

We first provide a definition: Definition 1. Let A q the "reserved time" on Π q , i.e.

p:τp∈Γq wp f M . A correct state is a state where, on each CPU Π q , the worst end t q is always lower than the begin of the reserved In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009 zone [D -A q , D], or, more formally, a state is said to be correct iff

t q ≤ D -A q ∀q ∈ [1, . . . , m].
We will show that, starting from a correct state, one step of the algorithm StartTask (or one call to Algorithm 4) will reach another correct state. Lemma 1. Algorithm 4 keeps states correct.

Proof. In order to show the lemma, we will prove that, if before we call the algorithm, we have t q ≤ D -A q , ∀q, this condition is still respected at the end. We will denote by A q the value of A q before we call the algorithm, and by A q this value after the call. We then have to show that

t q ≤ D -A q ⇒ t q ≤ D -A q .
We first show that MoveTasksOut (Algorithm 2) and MoveTaskIn (Algorithm 3) respect this property.

MoveTasksOut (Algorithm 2, page 4). We can show that any iteration of the while loop keeps the property. The only lines that change A q are the line 7 and 8. Here, we denote by A q (resp. A q ) the value of A q at the beginning (resp. the end) of the loop.

For A q , we have from line 6 that D -A q -t q ≥ wi f M . From line 8, we have A q = A q + wi f M . Then,

D -A q + w i f M -t q ≥ w i f M ,
and therefore, t q ≤ D -A q .

For A p , as we remove a task from Π p , the condition remains obviously true. Remark that, if the function returns true, we can easily see that D -A p -t ≥ s.

MoveTaskIn (Algorithm 3, page 4). The proof is very similar to the previous one.

We first call MoveTasksOut, which preserves the condition, as we have shown above. And with the same way as before, we can show that lines 3 and 4 also preserve the condition, because we run them if and only if

D -A p -t ≥ wi f M .
StartTask (Algorithm 4, page 5). The first part of the algorithm (lines 1 to 6) preserves the condition t q ≤ D -A q for sure: lines 1 and 2 do not change any value in the condition, MoveTaskIn preserves the condition, and if we invoke StartTask, we return right after the call.

When we are at line 7, we know that τ i , the task we want to start, is on Π p , the CPU which has just been released, or τ i ∈ Γ p . As A p = A p -wi f M . Notice that as t corresponds to the time at which Π p has just been released (or at the begin of the frame if t = 0), we have t = t p .

Line 7 preserves the property, because we reduce Remark that we do not need to make any hypothesis on S i (t), except that this function always return an allowed frequency.

A p (if t p ≤ D -A p -wi f M , then t p ≤ D -A p ),
Lemma 2. All tasks are started by the algorithm.

Proof. The reason why we need to proof this is that we sometime skip a task, if we are not able to start it right now without violating any reservation.

We first have to do the hypothesis that StartTask is always called with the task with the smallest index that has not started yet. But of course, StartTask could possibly call recursively itself with a task with an higher index.

We can consider separately three cases:

• The task τ i is already allocated to CPU Π p . Then τ i can for sure start on Π p right away, possibly at the highest speed;

• The task τ i is not on CPU Π p , but we can move it there. So we are in the same situation as the first case;

• The task τ i is not on CPU Π p , and we cannot move it there. We will now consider this last case.

If it is impossible to move τ i on Π p , it is obviously because there is at least one task already reserved on Π p . And as at the first level of StartTask, i is the smallest index of the not started tasks, the reserved tasks have all an index larger than i. Let j be the smallest index of the tasks reserved on Π p .

As we cannot move τ i on Π p , we call StartTask with τ i+1 . If i + 1 = j or τ i+1 can be moved on Π p , then we can start a task. Otherwise, we try with τ i+2 , τ i+3 , . . . , and we are then sure to reach τ j at some point, or to start a task with an index between i and j.

Theorem 1. If a virtual static partitioning can be found, then algorithm StartTask runs all jobs, and meets all deadlines.

In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

Proof. The proof is a direct consequence of the two previous lemmas. The initial state, just after the virtual partitioning has been performed, is correct: we have t q = 0 ∀q ∈ [1, . . . , m], and if the partitioning is correct, then

D ≤ A q ∀q ∈ [1, . . . , m].
We can also see that if the final state (when all task have finished) is correct, then we have not missed any deadline: in the final state, A q = 0 ∀q ∈ [1, . . . , m]. Then, if the state is correct, we have t q ≤ D ∀q ∈ [1, . . . , m], where t q is the end time of the last task running on Π q . And obviously, if all last tasks have finished before the deadline, no deadline has been missed.

As the initial state is correct, the algorithm preserves the correctness, and all tasks are run by the algorithm, then the final state will be reach, and will be correct. Then all tasks meet their deadline.

Algorithm Improvement

A drawback of the algorithms we present here is that in some cases, we are not able to start the task in the given order, and then accept to swap the order in which tasks are started. But our Ŝ-functions are computed to be efficient in the case we respect the order. Unfortunately, we have some cases where we cannot avoid intrinsically this task swapping. But we can however improve the function MoveTaskIn and MoveTasksOut in order the reduce the cases where we need to change the task order. We show here how to do that for MoveTaskIn can be improved, but a similar modification can be done for MoveTasksOut.

The idea is that if we cannot manage to free enough space on the target CPU, then we can try to swap the task we want to move on this CPU with one of the task already there.

Algorithm 5: Improvement for Algorithm 3 (MoveTaskIn) function CanSwap(τ i , τ j ) p is such that τ i ∈ Γ p ; q is such that τ j ∈ Γ q ; return D -t p -A p -wi f M ≥ wj f M and D -t q -A q - wj f M ≥ w i f M ; function SwapTasks(τ i , τ j ) p is such that τ i ∈ Γ p ; q is such that τ j ∈ Γ q ; Γ p = Γ p \ τ i ∪ τ j ; A p = A p - w i f M + w j f M ; Γ q = Γ q \ τ j ∪ τ i ; A q = A q - w j f M + w i f M ;
Those lines replace line 7 in Alg. 3 (MoveTaskIn): foreach j : τ j ∈ Γ p do if CanSwap(τ i , τ j ) then SwapTasks(τ i , τ j ); return true; return false;

Simulation Results

In this section, we will present several simulations we performed in order to evaluate the interest of doing global scheduling of such frame-based multiprocessor platforms, in terms of energy savings. The simulator has been written in c++, by the authors of this paper. Before we really evaluate our scheduling algorithm, we will first study how the task order can influence the gain in energy. We then compare the energy consumed by a platform with static partitioning with the same platform and job characteristics, when global scheduling is allowed.

In the plots we present here, the load of a system (horizontal axis) is computed in this way: We first define D min as the minimal deadline that any system can reach:

D min = m f M i w i .
We then define the load of a system as the ratio between the actual deadline D and the minimal deadline D min :

D D min = Df M m i w i .
Of course, on multiprocessor systems, a load of 1 is very rare to reach. A load of 10% does not mean that the system is busy at 10%, but that, if we neglect switching times, and the system only uses f M , it would be busy at 10%. We have consider two task sets. For the first one, we consider 32 tasks with normal distribution for the length (except that we truncate the tail in order to have a known WCEC, and reject the negative values).

On another side, we consider real traces which have been collected in the National Taiwan University, CSIE department, on devices decoding video streams. See [START_REF] Berten | Discrete frequency selection of frame-based stochastic realtime tasks[END_REF] for more explanation about those traces. In the simulation we present here, we have 18 such tasks for Figures 3, 6 and7, and 100 tasks for Figure 8.

In the following, we will mainly consider the Intel XScale CPU, but will also present some results on the Intel StrongArm SA-1100. The XScale provides 5 frequencies ranging from 150 to 1000 MHz, with a consumption going from 80 mW at 150 MHz to 1.6 W at 1000 MHz. More details can be found for instance in [START_REF] Xu | A unified practical approach to stochastic DVS scheduling[END_REF]. The Stron-gArm has 11 frequencies, between 60 and 206 MHz.

Impact of the Task Order

In this section, we compare several sorting criteria defining different task orders. We did not conduct a full study on this subject, and let this to further research, but we wanted to see how simple criteria could impact on the performance. We experimented many methods, but we only present here a few of them (others did not show significant differences).

We evaluate several task characteristics in order to sort tasks. Here are the names given in the figures legend:

• rand: tasks are randomly ordered; • wcec: tasks are sorted on decreasing worst case execution cycles;

• avg: tasks are sorted on decreasing average number of cycles;

• var: tasks are sorted on decreasing variance.

Intuitively, we may think that tasks with a smaller variance (or, in other words, with a better knowledge about their execution time) should be put at the end of a frame. This way, the scheduler will have a better chance to finish the last task very close to the deadline, and have then a slower average speed, which is known to be more efficient.

In Figures 2 (32 normally distributed (truncated) tasks on 8 XScale) and 3 (18 tasks with realistic distribution, on 4 XScale), we show two systems, where we compare for various loads the ratio between the energy consumption for var, and with the three other metrics. A value higher than one means then that, at that load, this metric consumes more energy, and then performs worse.

At a first look, we can see that rand performs worse that var on both platforms (using up to 15% more energy in the first plot, and up to 45% in the second case). The two other metrics (var and avg) do not show significant difference with the normal distribution (Fig. 2), but show a 10% loss in the realistic case, at high load.

The erratic aspect of the plots, especially the jumps we can observe in Fig. 2 around 0.2, can be explained quite simply, as we did for uniprocessor systems in [START_REF] Berten | Discrete frequency selection of frame-based stochastic realtime tasks[END_REF]. The speed at which the first m tasks are started in a frame only depends upon the characteristics of the system, contrary to the speed of subsequent tasks, which will strongly depends on the time previous tasks actually took. Then, a slight change in the deadline, for instance, could cause one of the m first tasks to start at a higher speed, and has then a large impact on the system behavior. In the next few plots, we will try to see in which configuration we have any benefit in global scheduling. As a first plot, we present in Figure 4 the same system as in Figure 2, but present another metric. Here, we show the ratio between the energy consumed with static partitioning and the energy with global scheduling. So the higher, the better is to use global scheduling. We show that for the four sorting metrics we presented above.

Benefit of Globalization

In the first plot (Fig. 4 ; 32 normally distributed tasks on 8 XScale CPUs), we can see that with rand, static partitioning performs better than global scheduling. But for other metrics, except at high load where it seems to be quite unpredictable which strategy is better, global scheduling saves always energy. This plot does not show that static partitioning and random ordering is better that other strategies. It shows that if the order is given and random, then we should not use global scheduling for this task set.

In order to better show how global scheduling performs on this task set, we will show in Figure 5 the ratio between all the combinations (a task ordering) and (global or partitioning), and the global strategy on var. From this figure, we can see that any couple task ordering/strategy behaving better than var/global (meaning having most of its point below 1) is also a global strategy. We also present here simulations with other system and task parameters. Figure 6 presents the same system as in Figure 3 (but again with another metric). In Figure 7, we show the same task set, but on a StrongArm CPU. In Figure 8, we can see a much bigger system 100 (realistic) tasks, on a platform with 32 XScale CPUs.

All those simulations point out that when the order of tasks is arbitrary (e.g. rand), it sounds better to do static partitioning. But when the order is better, then most of the time, we gain several percents of energy by doing global scheduling. But not always for high loads: we observe very often that, for some high loads, static partitioning performs better than global.

It could seem counter-intuitive that by being more rigid (i.e. static partitioning), we can be more efficient. But several phenomena happen in our strategy, and can explain this behavior.

First of all, in static partitioning system, when a task ends, we know exactly how much time we can give to the next tasks allocated to the same CPU. This is the remaining time before the deadline. But in the global scheduling, we estimate the remaining time we will have for all tasks which have not started yet. And we cannot be very accurate in this estimation, because when a tasks finishes, m -1 tasks could be still running, and we do not know when they will be over. We have then a less accurate knowledge about the system, which could lead to unlucky decisions.

Another phenomenon can be better understood by an example. Let us imagine a system with 3 identical tasks (τ 1 , τ 2 and τ 3 ), and 2 CPUs (Π 1 and Π 2 ). If the variance is quite small, the scheduler on the equivalent uniprocessor system would choose to give each task approximately a third of the time space. On the dual processor system, the scheduler will then try to run τ 1 up to 2D/3 on Π 1 , and will make the same for τ 2 on Π 2 . Then when the first of them ends, we have to start τ 3 , but we cannot use 2D/3 units of time, because only half of this is available on the released CPU, the other half being soon available on the other one. And then we need to speed up the CPU on which τ 3 runs, while the other CPU will be idle for a third of the frame length.

In the static partitioning case, we would have given all the frame to one job on the first CPU, and would have split the frame into two equal parts on the second CPU. And obviously, this scenario consumes less energy, because we use a more constant frequency on one processor, and a lower frequency on the other one. by any algorithm, then our scheduling algorithm will meet all deadlines. Furthermore, we have shown through many simulations that this global algorithms can gain a lot of energy compared to static methods, especially if the tasks are smartly ordered. We have shown several simulations where we can gain up to 20% by doing global scheduling instead of static partitioning.

Lastly, our algorithm has a very reasonable on-line and off-line complexity, and we strongly believe that it would be easy to implement.

As a future work, here are a few points we want to look deeper, allowing to improve the energy consumption, or the number of systems we are able to schedule.

• If we accept to change the frequency during the execution of tasks, we can use the continuous model to obtain a frequency f , and use two frequencies f F and f F to "emulate" this f , where f F (resp. f F ) stands for the smallest frequency above (resp. largest below) f .

• Several steps require to solve NP-hard problems by using some heuristics: Static partitioning (Algorithm 1), MoveTaskIn (Algorithm 3), and MoveTasksOut (Algorithm 2). The efficiency of the first one improves the number of systems we can accept to schedule, the second one, the number of tasks we will need to swap (not run in the right order), and the third one, how close we can stay from the uniprocessor algorithm. We may try to further improve those three algorithms.

• In order to reduce leakage or static energy consumption, we could turn off CPUs if they are not needed anymore before the end of the frame.

• We believe that if jobs are parallelizable, we can still gain more energy by splitting them on several CPUs. But only a few research has been done on this subject so far, and we think it is worth to be deeper studied.

7

 7 The complexity of MoveTaskIn is dominate by the complexity of MoveTasksOut, and is then alsoO(n × log m)In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

  Figure 3

  Figure 4

  Figure 5

5

  Figure 6

  Figure 8

Algorithm 4 :

 4 StartTask Data: Processor Π p , time t, task τ i d = m × D -t + q =p t q ; // Available

	1
		time on the system
	2	f = Ŝi (d); // Freq. we want to run τ i
	3	if τ i / ∈ Γ p then
		// τ i is not on Π p , we try to
		move it in
	4	if not MoveTaskIn(Π p , t, τ i ) then
	5	StartTask(Π p , t, τ i+1 );
	6	return;
		// We have now τ i ∈ Γ p
		A p -= wi f M ; // Release τ i reservation

7 Γ p = Γ p \ τ i ; 8 // Try to remove enough tasks (if needed) from Π p to allow τ i to run at the desired speed f if not MoveTasksOut(Π p , t, wi f ) then 9 // Not enough time to run τ i at f // We know that D -A p -t < wi f f = w i D -A p -t F ; 10 t p + = wi f ; // Worst end time for τ i 11 Start τ i at f ; 12 StartTask at line5. We have m (sum at line 1) + log(m) (line 2) + n log m (MoveTaskIn at line 4) + n log m (MoveTasksOut at line 9), then O(m + n log m).

  as well as MoveTasksOut at line 9.At line 9, we have two cases that we will consider separately. Notice that, as we stated before, MoveTaskIn(Π p , t, wi f ) returns true if and only if D -A p -t ≥ wi f . Then we can see the line 9 as the test 'if(D -A p -t < wi f )'. Let t p be the value of t p just before the test. By hypothesis, we know that t p ≤ D -A p (A p does not change in this part). We now have finished the proof: if t p ≤ D -A p is true before we call StartTask, this condition is still true at the end of the procedure.

	If D -A p -t p ≥	w i f	, we have t p = t p +	w i f	, and then
	t p ≤ D -A p , which validates the first case. If D -A p -t p < w i , then line 10 makes that f ≥ f w i D -A p -t , and then D -A p -t p ≥ w i f , and we can
	then apply the same proof as above.

  In Proc. of the 17th International Conference on Real-Time and Network Systems RTNS'2009, Paris, ECE, 26-27 October, 2009

	Figure 2
			32 Normally distributed tasks -8 CPUs
		1.2
			rand
			avg
		1.15	wcec
	Energy ratio with var	1 1.05 1.1
		0.95
		0.9
			0.2	0.3	0.4	0.5 0.6 0.7 0.8 0.9
					Load

A work conserving system is a system where tasks never wait intentionally. In other words, if a task is ready, no processor can be idle.