In this paper, we present a new scheduling approach for real-time tasks in an embedded system. Our method utilizes hierarchical scheduling to provide a resource based allocation scheme while using a fuzzy logic based feedback scheduler to react to environmental changes within the application. The primary goal is to provide a scheduling mechanism that can adapt to overload conditions but still present a level of service while enforcing the temporal isolation between independent applications. The scheduler then considers this level of service to make scheduling decisions based upon a task's service requirements, such as criticality or timeliness. Implemented in VxWorks on a uniprocessor-based platform results show that our adaptive approach provides significant advantages, during overload conditions, over traditional fixed-priority scheduling schemes.
Current embedded systems are becoming considerably more complicated and they are expected to handle increasingly diverse applications. No longer are they considered special-purpose computing environments but are evolving into more generalpurpose type platforms in terms of their processing and workload requirements. These increasingly diverse applications present new challenges for traditional real-time scheduling mechanisms in that applications can have conflicting objectives. For example, one application may be more concerned with screen update response as opposed to whether a single update is missed. While a mission critical application, such as a navigational task, cannot afford to miss even a single update.
The problem is that traditional real-time scheduling mechanisms do not map well to these diverse types of applications specifically during a processing fault or during periods of computational overload. Faults can occur from longer than unexpected task execution time or from programming errors which can lead to the starvation for all lower-priority tasks. An overload can occur as the result of too many tasks being admitted into the system resulting into what is known as the “domino effect” where all tasks except the newly admitted one miss their deadlines. The challenge is that many embedded systems are expected to perform continuous operations in potentially harsh environments and execute at least a subset of critical operations during a fault or overload condition. In order to enforce these strict timing constraints required by critical functions during a fault condition a form of temporal isolation is needed so that corresponding timing requirements are respected. During an overload event the system needs to be able to dynamically adapt to the current load so that system performance can degrade gracefully.
As a solution to these challenges our work utilizes hierarchical scheduling to provide the temporal isolation for real-time tasks by enforcing their timing constraints. The hierarchical scheduling framework (HSF) originally proposed by researchers [1] is a component based technique for scheduling complex real-time systems. The initial idea in applying this approach is that relatively simple components can be used to create larger and more complex systems. In this way, the timing constraints of individual components can be verified, a type of divide and conquer approach. Therefore, by extending this framework we can then schedule each application (i.e. component) such that their timing constraints are satisfied. However, the current limitation with a traditional HSF-based approach is that the scheduling parameters for each component are assigned statically. Unfortunately, in a dynamic system the resource demand for each component can vary significantly especially during periods of overload. It is for this reason that we present an adaptive mechanism where the component parameters can adapt to environmental changes in the system. In this way, the system can degrade gracefully in the presence of computational overload while still maintaining a level of serviceability for critical applications.
For this work we apply a novel approach where the component
parameters adapt based upon a value-based heuristic instead of a
deadline based policy. This value-based approach is applied
because authors in [
In this paper we present a new adaptive hierarchical scheduler for real-time systems (AHS-RT) that provides timing guarantees for critical tasks and a minimum level of service for non-critical tasks during overload conditions. Our approach is to utilize fuzzy logic for the guidance mechanisms because they prove to be easier to express, comprehend and modify than other heuristic functions. The remainder of this paper is organized as follows. Section 2 provides an overview of the hierarchical scheduling framework used by our scheduling mechanism. Section 3 discusses related work and Section 4 provides an overview of the hierarchical scheduler (AHS-RT). Section 5 presents the simulations we used to provide comparisons between our scheduling approach and traditional fixed priority scheduling. In Section 6 we conclude with future work and the research summary.
This section provides a background of the terminology used in the paper as well as an overview of hierarchical scheduling provided as a reference for the overall architecture of adaptive hierarchical scheduling.
Hierarchical scheduling provides a framework for scheduling multiple real-time applications on a single processor which is modeled as a system S. Each system may consist of multiple applications (subsystems ) such that . Each subsystem consists of a number of real-time tasks. Each subsystem is associated with a periodic server which provides the temporal isolation between subsystems. The execution of tasks is performed using a two-level hierarchical scheduling policy: global and local. The global scheduling policy determines which subsystem has access to the processor while the local scheduling policy determines which task should actually execute (Figure 1).
We consider a task set , such that each task is defined as where is defined as the task period, denotes the task worst case execution time (WCET), is the relative deadline and represents the task criticality value. It is assumed that each task is a constrained task such that . The criticality value represents the importance or weight of the task as it relates to other tasks in the set. The criticality value along with the deadline and period are used by the fuzzy inference engine to make scheduling decisions by the local scheduler.
Each subsystem consists of a task set such that . The subsystem is modeled as a periodic task so a subsystem can be scheduled in a similar way as a simple real-time periodic task. The subsystem is defined as where represents the subsystem period, represents the subsystem budget and represents the subsystem criticality level. Similar to the task model the service value is used to make scheduling decisions at the subsystem level. Note that during overload conditions the subsystem with the highest criticality level is granted its full budget at the possible expense of lower criticality subsystems.
The virtual server is invoked with the corresponding subsystem period . If there are any ready tasks within the subsystem then they execute until they complete or the server’s budget is exhausted. If there are no ready tasks to execute or no higher priority subsystem needs to utilize some of the server’s budget during an overload condition then the capacity is idled away as if a background task were running. After a server’s budget is exhausted the server suspends the execution of the subsystem until the capacity is replenished at the start of the next period. For this work we choose a periodic server as the fixed priority server algorithm, in part because the simpler design has less overhead but also because authors in [2] have shown it to dominate other fixed-priority server algorithms.
The scheduler and the controller of AHS-RT are based upon fuzzy-logic heuristics. The fuzzy logic based approach was chosen because of its strength in dealing with dynamic environments involving a certain degree of uncertainty. The fuzzy system is defined as having n inputs , where and , is the collection of numbers for (universe of discourse for ) and one output , where is the universe of discourse for (multiple input single output fuzzy system). The inputs and output are crisp values (i.e. real numbers). The structure of the fuzzy system consists of three stages; fuzzication stage, inference stage and the defuzzication stage. The fuzzication stage converts the crisp input values into fuzzy sets to be used by the inference stage. The inference stage uses the rules defined in the rule base to convert these fuzzy sets into other fuzzy sets that represent the recommendations of the various rules in the rule base. The defuzzication stage combines these fuzzy recommendations to provide a crisp output .
Hierarchical scheduling framework (HSF) was initially proposed
by researchers [1][
In [
Authors in [
Other research [
Recent work [
Our approach in AHS-RT is similar to the work in [
This section describes the overall architecture (see Figure 1) of the AHS-RT scheduling framework which consists of a two-level hierarchical scheduling framework. The root-level contains the global scheduler which manages how subsystems (i.e. applications) are allocated on the processor. While the node-level contains the local scheduler which manages how tasks are scheduled on the processor.
At run-time the global scheduler chooses the highest priority subsystem that has tasks ready to run. The priority is based upon the subsystem period so the shorter the period the higher the subsystem priority. Therefore if the priority of then would be scheduled first with its full budget then would be scheduled next with its full budget unless an overload condition is detected. In the event of an overload a higher criticality subsystem may request a budget change at the possible expense of a lower criticality subsystem which may or may not be a lower priority subsystem.
The logical approach may be to re-assign budgets based upon
subsystem priority. However, during an overload event studies
have shown [
An overload condition is based upon the overall subsystem utilization which is defined as: and because we are using RM then an overload condition is determined by , where m is the number of subsystems. An overload can occur because a subsystem requests a budget change in order to adapt to a fault or missed deadline within a task of an individual application. A budget change does not necessarily mean that the system is overloaded just that there is the potential for an overload condition to exist. Consider some unallocated system utilization denoted as such that , and then this extra utilization could be temporarily reallocated to the subsystem requesting the additional budget. However, if there are not sufficient resources to satisfy all the budget requirements then the system is considered overloaded which implies that a budget reallocation needs to be performed.
After the full budget has been allocated to the highest criticality subsystem the lower criticality budgets needs to be redimensioned. The next lower criticality subsystems are then assigned budgets based upon the remaining utilization. The algorithm and description for budget dimensioning is provided below.
The budget dimensioning algorithm (Algorithm 1) works by iterating through all the subsystems in the subset of lower criticality subsystems. In line 2 the new budget is calculated based upon the remaining system utilization. A schedulability test (line 3) is then performed on the modified budget. If the modified budget renders the system unschedulable then a new budget value is attempted based upon the previous failed value. The algorithm continues to reduce the budgets of lower criticality subsystems until a schedulable system is found.
The local scheduling of AHS-RT consists of two primary components; a fuzzy logic based scheduler and a fuzzy logic based feedback controller. The scheduler selects the task to execute on the processor derived from the fuzzy rules based approach to real-time scheduling. The feedback controller gathers system state information for subsystem budget management to maximize utilization and minimize missed deadlines.
At run-time the fuzzy scheduler selects the highest priority task that is ready for execution on the processor. The priority of the task is determined by several parameters: task deadline, task criticality and task execution time. The task deadline is the time before the task should be completed. The task criticality relates to the consequences of missing a deadline. The task execution time is the worst-case execution time for that task. These parameters are then fuzzified and represented as linguistic variables (i.e. a word used to describe a variable). Fuzzy rules are then applied to the linguistic variables to compute the service value. The linguistic values for the three parameters are defined as: task deadline (early, on-time, late), task criticality (hard, firm, soft) and CPU time (very low, low, normal, high, very high). Fuzzy rules are then applied to create a fuzzy conclusion for computing the priority level. Figure 2 illustrates the linguistic variables used by the inference stage of the fuzzy scheduler. Some of the fuzzy rules for the scheduler inference mechanism are listed as an example here:
(criticality is hard) then (Priority is very high)
(critically is firm) then (Priority is normal)
These fuzzy conclusions are then combined to produce a fuzzy variable that represents the criticality level of the task. The variable is then defuzzified to create a value that is compared to other tasks to determine which task should be scheduled next. The decision surface illustrates the crisp output value (priority) that is obtained based upon the input parameters (See Figure 3). The fuzzy scheduler algorithm (Algorithm 2) iterates through all the tasks in the task set for a particular subsystem and for each task passes the deadline ( ), criticality value ( ) and starting time ( ) into the fuzzy inference engine. The output from the inference function is a crisp value used to assign a priority to each task and stored in a priority array ( ). The task with the highest priority is then executed until some scheduling event occurs (task completion, new task instance arrives or server budget exhaustion). The system status is then updated and if a task misses its deadline such as server budget exhaustion then the deadline miss is reported to the feedback controller which could trigger a budget reallocation across the system.
The feedback controller in AHS-RT is similar to the FC-UM
algorithm [
To demonstrate AHS-RT we have provided an example scheduling scenario. Note for illustration purposes we are only considering one subsystem. So, the primary purpose of this example is present how the fuzzy scheduler manages tasks within the context of one subsystem. Consider the task set and subsystem listed in Tables 1 and 2. Table 3 describes the scheduling of tasks at the first scheduling event where tasks and all have the same initial starting time but since has the nearest deadline it is assigned the highest priority by the fuzzy scheduler. Therefore, is allowed to execute until completion then at time unit t3 task executes until time unit t5 when the subsystem’s budget expires. At time unit t10 (see Table 4) the subsystem’s budget is replenished where the tasks can continue execution. At this time the fuzzy scheduler performs a re-ordering of task priorities to reflect the system state. Task is assigned the highest priority because the start time is the earliest and the deadline is the closest. Note that at time unit 10 5 10 10 5 10 10 5 10 10 5 10 10 ~9 ~5 ~3 ~5 ~9 ~7 ~10 ~5 ~3 t12 task will complete execution but task will be scheduled over even though both tasks have the same relative deadline and start time. This is because was assigned a higher priority by the fuzzy controller because was defined to be a higher criticality task than . Also note, due to subsystem budget exhaustion at time unit t15 task will miss its deadline which would trigger a budget reallocation request to the fuzzy controller for an increase in the subsystem budget. Finally, at time unit t20 (see Table 5) the scheduler re-orders the task priorities where once again will be assigned the highest priority.
Consider the following subsystems with parameters presented in Table 6 which is used to illustrate how a subsystem is scheduled by AHS-RT. Suppose that at some scheduling instant subsystem has a current budget but due to a deadline miss the fuzzy controller recommends a budget increase to 4. Also suppose that and report no deadline misses or under utilization so the fuzzy controller recommends no budget changes. However, the increased budget of causes the schedulability test to fail because so now the criticality level is considered and since has the highest criticality level it is granted the full budget. After = 4 the budget dimensioning algorithm is performed to redistribute the remaining utilization. Initially, the budgets for and will be and then a successful schedulability test will be performed. Next the budget for will be but the schedulability test will fail. Since the system is no longer schedulable the budget for will now be . This time the system is schedulable so the adjusted budgets are reallocated to their respective subsystems.
AHS-RT was implemented as part of the VxWorks 6.9 real-time
operating system (RTOS). The simulations were executed using
the SIMNT vxsim simulator. For evaluation purposes we ported
the SNU Real-Time Benchmark Suite [
In this paper we considered the problem of how to schedule tasks with varying levels of criticality on a uniprocessor to more effectively adapt to computational changes. Those changes were managed by hierarchical scheduling to provide the temporal isolation between tasks. The efficient scheduling of tasks was accomplished using a fuzzy based heuristic which has been proven to be more effective than traditional deadline based approaches especially during periods of overload. The results are a demonstrated reduction in deadline misses for all tasks during periods of overload as compared to traditional fixed priority based scheduling mechanisms. As further confirmation for the practicality for this approach we implemented AHS-RT as part of the VxWorks RTOS.
Future work includes evaluating the additional overhead AHS-RT incurs in VxWorks as compared to the traditional scheduler. Additionally, we would like to extend AHS-RT into a multi-core environment and consider semi-independent tasks where subsystems would have to share a mutual resource such as a semaphore.
[1] Z. Deng and J. W.-S. Liu, “Scheduling real-time applications in an open environment,” (RTSS’97), pp. 308–319. [2] Davis, R.I.; Burns, A., "Hierarchical fixed priority pre-emptive scheduling," (RTSS’05)