=Paper=
{{Paper
|id=Vol-1464/ewili15_2
|storemode=property
|title=Fuzzy Logic Based Adaptive Hierarchical Scheduling for Periodic Real-Time Tasks
|pdfUrl=https://ceur-ws.org/Vol-1464/ewili15_2.pdf
|volume=Vol-1464
|dblpUrl=https://dblp.org/rec/conf/ewili/SpringerPG15
}}
==Fuzzy Logic Based Adaptive Hierarchical Scheduling for Periodic Real-Time Tasks==
https://ceur-ws.org/Vol-1464/ewili15_2.pdf
Fuzzy Logic Based Adaptive Hierarchical Scheduling for
Periodic Real-Time Tasks
Tom Springer, Steffen Peter, and Tony Givargis Center for Embedded Computer Systems
University of California, Irvine, USA {tspringe, st.peter, givargis}@uci.edu
ABSTRACT requirements are respected. During an overload event the system
In this paper, we present a new scheduling approach for real-time needs to be able to dynamically adapt to the current load so that
tasks in an embedded system. Our method utilizes hierarchical system performance can degrade gracefully.
scheduling to provide a resource based allocation scheme while As a solution to these challenges our work utilizes hierarchical
using a fuzzy logic based feedback scheduler to react to scheduling to provide the temporal isolation for real-time tasks by
environmental changes within the application. The primary goal is enforcing their timing constraints. The hierarchical scheduling
to provide a scheduling mechanism that can adapt to overload framework (HSF) originally proposed by researchers [1] is a
conditions but still present a level of service while enforcing the component based technique for scheduling complex real-time
temporal isolation between independent applications. The systems. The initial idea in applying this approach is that
scheduler then considers this level of service to make scheduling relatively simple components can be used to create larger and
decisions based upon a task’s service requirements, such as more complex systems. In this way, the timing constraints of
criticality or timeliness. Implemented in VxWorks on a individual components can be verified, a type of divide and
uniprocessor-based platform results show that our adaptive conquer approach. Therefore, by extending this framework we can
approach provides significant advantages, during overload then schedule each application (i.e. component) such that their
conditions, over traditional fixed-priority scheduling schemes. timing constraints are satisfied. However, the current limitation
with a traditional HSF-based approach is that the scheduling
Categories and Subject Descriptors parameters for each component are assigned statically.
C.3 [Special-Purpose and Application-Based Systems]: Real- Unfortunately, in a dynamic system the resource demand for each
Time and embedded systems. component can vary significantly especially during periods of
overload. It is for this reason that we present an adaptive
General Terms mechanism where the component parameters can adapt to
Algorithms, Performance, Reliability environmental changes in the system. In this way, the system can
degrade gracefully in the presence of computational overload
Keywords while still maintaining a level of serviceability for critical
Real-time systems, hierarchical scheduling, fuzzy logic, real-time applications.
operating systems.
For this work we apply a novel approach where the component
1. INTRODUCTION parameters adapt based upon a value-based heuristic instead of a
Current embedded systems are becoming considerably more deadline based policy. This value-based approach is applied
complicated and they are expected to handle increasingly diverse because authors in [5] have presented the limitations of a deadline
applications. No longer are they considered special-purpose based model for real-time scheduling and have concluded that a
computing environments but are evolving into more general- value-based approach can more accurately represent the cost or
purpose type platforms in terms of their processing and workload benefit of meeting or missing a deadline. The challenge is in
requirements. These increasingly diverse applications present new assigning this value metric because in the event of an overload we
challenges for traditional real-time scheduling mechanisms in that want to degrade the performance gracefully by ensuring that tasks
applications can have conflicting objectives. For example, one are provided at least some minimum level of service. Therefore,
application may be more concerned with screen update response during an overload when the current schedule is unfeasible we
as opposed to whether a single update is missed. While a mission want the scheduler to schedule tasks according to some intelligent
critical application, such as a navigational task, cannot afford to heuristic. Some possible heuristics would include scheduling the
miss even a single update. most important tasks first while still maintaining some level of
timeliness for the less important tasks. Our approach is to utilize a
The problem is that traditional real-time scheduling mechanisms heuristic function for guiding the scheduling decisions in a
do not map well to these diverse types of applications specifically complicated situation where multiple factors may need to be
during a processing fault or during periods of computational considered such as deadlines, task criticality or task response
overload. Faults can occur from longer than unexpected task times.
execution time or from programming errors which can lead to the
starvation for all lower-priority tasks. An overload can occur as In this paper we present a new adaptive hierarchical scheduler for
the result of too many tasks being admitted into the system real-time systems (AHS-RT) that provides timing guarantees for
resulting into what is known as the “domino effect” where all critical tasks and a minimum level of service for non-critical tasks
tasks except the newly admitted one miss their deadlines. during overload conditions. Our approach is to utilize fuzzy logic
for the guidance mechanisms because they prove to be easier to
The challenge is that many embedded systems are expected to express, comprehend and modify than other heuristic functions.
perform continuous operations in potentially harsh environments
and execute at least a subset of critical operations during a fault or The remainder of this paper is organized as follows. Section 2
overload condition. In order to enforce these strict timing provides an overview of the hierarchical scheduling framework
constraints required by critical functions during a fault condition a used by our scheduling mechanism. Section 3 discusses related
form of temporal isolation is needed so that corresponding timing work and Section 4 provides an overview of the hierarchical
EWiLi’15, October 8th, 2015, Amsterdam, The Netherlands.
Copyright retained by the authors.
scheduler (AHS-RT). Section 5 presents the simulations we used 2.4 Fuzzy Systems
to provide comparisons between our scheduling approach and The scheduler and the controller of AHS-RT are based upon
traditional fixed priority scheduling. In Section 6 we conclude fuzzy-logic heuristics. The fuzzy logic based approach was
with future work and the research summary. chosen because of its strength in dealing with dynamic
2. BACKGROUND
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.
2.1 Hierarchical Scheduling Framework
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). Figure 1: AHS-RT Architecture
environments involving a certain degree of uncertainty. The fuzzy
2.2 Task Model system is defined as having n inputs , where
We consider a task set , such that each task
and , is the collection of numbers for (universe of discourse
is defined as where is defined as the task period,
for ) and one output , where is the universe of discourse
denotes the task worst case execution time (WCET), is the
for (multiple input single output fuzzy system). The inputs
relative deadline and represents the task criticality value. It is
and output are crisp values (i.e. real numbers). The structure of
assumed that each task is a constrained task such that
the fuzzy system consists of three stages; fuzzication stage,
. The criticality value represents the importance or
inference stage and the defuzzication stage. The fuzzication stage
weight of the task as it relates to other tasks in the set. The
converts the crisp input values into fuzzy sets to be used by the
criticality value along with the deadline and period are used by the
inference stage. The inference stage uses the rules defined in the
fuzzy inference engine to make scheduling decisions by the local
rule base to convert these fuzzy sets into other fuzzy sets that
scheduler.
represent the recommendations of the various rules in the rule
2.3 Subsystem Model base. The defuzzication stage combines these fuzzy
Each subsystem consists of a task set such that . The recommendations to provide a crisp output .
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 3. RELATED WORK
subsystem is defined as where represents the Hierarchical scheduling framework (HSF) was initially proposed
subsystem period, represents the subsystem budget and by researchers [1][4][6] as a means to reduce the scheduling
represents the subsystem criticality level. Similar to the task complexity for open source embedded systems. Resource
model the service value is used to make scheduling decisions at partitioning [7] was introduced as a general technique for limiting
the subsystem level. Note that during overload conditions the the effects of overruns in tasks with variable execution times. This
subsystem with the highest criticality level is granted its full resource reservation technique can then be applied by hierarchical
budget at the possible expense of lower criticality subsystems. schedulers to provide the temporal isolation between subsystems
for more predictable behavior, improved reusability and
2.3.1 Periodic Server composability. However, the current limitation with HSF is that in
The virtual server is invoked with the corresponding subsystem order to determine the resource reservations all tasks parameters
period . If there are any ready tasks within the subsystem then must be known a priori and fixed during run-time. The problem is
they execute until they complete or the server’s budget is that accurate task information may not be known or hard to derive
exhausted. If there are no ready tasks to execute or no higher at run-time. Additionally, in order to account for overload
priority subsystem needs to utilize some of the server’s budget conditions the system may need to be over-engineered which
during an overload condition then the capacity is idled away as if could lead to significant under utilization during nominal load
a background task were running. After a server’s budget is periods.
exhausted the server suspends the execution of the subsystem In [8] [9] [10] authors proposed a feedback mechanism to account
until the capacity is replenished at the start of the next period. For for the dynamic behavior when the task parameters may not be
this work we choose a periodic server as the fixed priority server fully known. The approach was for the scheduler to maximize the
algorithm, in part because the simpler design has less overhead CPU utilization, avoid system overload and distribute the
but also because authors in [2] have shown it to dominate other computing resource evenly among tasks. By incorporating
fixed-priority server algorithms. feedback the scheduler reacts to changes in the workload then
tries to keep the overall utilization as close as possible to a desired
set point typically using a type of control mechanism, such as a
proportional integral derivative (PID) controller. Related work
[11] [12] adjusts the resource allocation on-line based upon a criticality subsystem which may or may not be a lower priority
quality-of-service (QoS) scheme where a certain level of service subsystem.
is provided in cases overload. However, the primary objective of The logical approach may be to re-assign budgets based upon
this approach is control performance and not necessarily subsystem priority. However, during an overload event studies
minimizing the number of missed deadlines. have shown [3] that a value-based approach offers considerable
Authors in [14] took a slightly different approach in that they advantages over traditional deadline-based approaches. For this
based their scheduler on a benefit based model. Their approach reason, during an overload event the global scheduler of AHS-RT
was to schedule the tasks using a traditional deadline based temporarily switches from a deadline-based scheduling policy to a
scheduling policy until a potential fault was detected and before value-based scheduling policy. Instead of the highest priority
an overload condition could occur. After a fault is detected the subsystem receiving their full budget the subsystem with the
scheduler switches to a benefit based scheduler that considers task highest criticality level will receive their entire budget.
importance, system state and timeliness to schedule tasks. Authors Therefore, the global scheduler redistributes budgets based upon
in [13] also took a similar approach in adaptive scheduling except the criticality level which means lower criticality subsystems yield
they manipulated the task period of other tasks to achieve the their budgets to higher criticality subsystems. This greedy
desired level of performance. approach can lead to starvation, even for some high priority
Other research [15] [16] [17] treated the uncertainty of varying subsystems, but this is acceptable in that during overload
execution times as a multi-criteria optimization problem then conditions the highest criticality subsystems are considered
applied fuzzy logic to derive a feasible schedule. Their approach superior to lower criticality subsystems.
was to treat various task parameters, such as deadline, start time 4.1.1 Detecting Overloads
or execution time, as inputs to the fuzzy scheduler then perform An overload condition is based upon the overall subsystem
fuzzy analysis to assign a task priority value. Additional work utilization which is defined as:
[18] utilized fuzzy logic as a means for tuning a feedback
controller to provide optimal resource utilization through task
period re-adjustment.
and because we are using RM then an overload condition is
Recent work [19] extended hierarchical scheduling to provide an
determined by , where m is the number of
adaptive hierarchical framework for managing overruns in tasks
subsystems. An overload can occur because a subsystem requests
with varying execution times. Their approach was to utilize a
a budget change in order to adapt to a fault or missed deadline
feedback control mechanism for adapting the resource allocation
within a task of an individual application. A budget change does
by adjusting the amount of budget assigned to a subsystem. By
not necessarily mean that the system is overloaded just that there
adjusting the budgets at run-time the framework can better adapt
is the potential for an overload condition to exist. Consider some
to changes in the workload.
unallocated system utilization denoted as such that
Our approach in AHS-RT is similar to the work in [19] in that we , and then this extra utilization could be temporarily
also utilize hierarchical scheduling for determinism and temporal
isolation. However, AHS-RT differs in how the local scheduling reallocated to the subsystem requesting the additional budget.
and global scheduling is performed. Local scheduling is based However, if there are not sufficient resources to satisfy all the
upon a fuzzy scheduler which is more adept at making scheduling budget requirements then the system is considered overloaded
decisions when the task parameters are vague. Research by which implies that a budget reallocation needs to be performed.
authors in [17] demonstrated that fuzzy logic based approaches 4.1.2 Budget Reallocation
outperform traditional deadline based policies such as earliest After the full budget has been allocated to the highest criticality
deadline first (EDF). In AHS-RT global scheduling also uses a subsystem the lower criticality budgets needs to be re-
feedback controller but the controller is based upon a fuzzy logic dimensioned. The next lower criticality subsystems are then
heuristic instead of a PID controller. Because fuzzy logic can assigned budgets based upon the remaining utilization. The
better tolerate imprecision thereby providing improved run-time algorithm and description for budget dimensioning is provided
flexibility. below.
4. AHS-RT Architecture
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.
4.1 Global Scheduling
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 The budget dimensioning algorithm (Algorithm 1) works by
scheduled next with its full budget unless an overload condition is iterating through all the subsystems in the subset of lower
detected. In the event of an overload a higher criticality subsystem criticality subsystems. In line 2 the new budget is calculated based
may request a budget change at the possible expense of a lower upon the remaining system utilization. A schedulability test (line
3) is then performed on the modified budget. If the modified These fuzzy conclusions are then combined to produce a fuzzy
budget renders the system unschedulable then a new budget value variable that represents the criticality level of the task. The
is attempted based upon the previous failed value. The algorithm variable is then defuzzified to create a value that is compared to
continues to reduce the budgets of lower criticality subsystems other tasks to determine which task should be scheduled next. The
until a schedulable system is found. decision surface illustrates the crisp output value (priority) that is
obtained based upon the input parameters (See Figure 3).
4.2 Local Scheduling
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.
4.2.1 Fuzzy Scheduler
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 The fuzzy scheduler algorithm (Algorithm 2) iterates through all
is the worst-case execution time for that task. These parameters the tasks in the task set for a particular subsystem and for each
are then fuzzified and represented as linguistic variables (i.e. a task passes the deadline ( ), criticality value ( ) and starting
word used to describe a variable). Fuzzy rules are then applied to time ( ) into the fuzzy inference engine. The output from the
the linguistic variables to compute the service value. The inference function is a crisp value used to assign a priority to each
linguistic values for the three parameters are defined as: task task and stored in a priority array ( ). The task with the
deadline (early, on-time, late), task criticality (hard, firm, soft) highest priority is then executed until some scheduling event
and CPU time (very low, low, normal, high, very high). Fuzzy occurs (task completion, new task instance arrives or server
rules are then applied to create a fuzzy conclusion for computing budget exhaustion). The system status is then updated and if a task
the priority level. Figure 2 illustrates the linguistic variables used misses its deadline such as server budget exhaustion then the
by the inference stage of the fuzzy scheduler. deadline miss is reported to the feedback controller which could
trigger a budget reallocation across the system.
4.2.2 Fuzzy Feedback Controller
The feedback controller in AHS-RT is similar to the FC-UM
algorithm [20] in that both the miss-ratio and utilization are
monitored. The reference inputs for miss-ratio and unused
budget are both set to zero. At each sampling instant the miss-
ratio M(k) and the unused subsystem budget U(k) are fed back
into the controller. These values are then compared to their
Figure 2: AHS-RT Inference block system rules respective set points to determine the difference where du(k)
represents the utilization error and dm(k) represents the miss-ratio
Some of the fuzzy rules for the scheduler inference mechanism
error. The output from the fuzzy controller is the budget
are listed as an example here:
dimensioning factor . As part of a typical fuzzy controller
If (CPU Time is high) and (deadline is late) and (Figure 4) we need to specify meaningful linguistic values and
(criticality is hard) then (Priority is very high) membership functions for each input and output variable. The
If (CPU Time is normal) and (deadline is on-time)and input to the controller are miss ratio and task utilization ratio
(critically is firm) then (Priority is normal) defined as a triangular membership functions. The input
If (CPU time is low) and (deadline is early) and linguistic values are utilization (very low, low, normal, high, very
(criticality is soft) then (Priority is low). high) and deadline misses (zero, small, medium, high). The output
linguistic values is bandwidth adjustment (none, very small,
small, medium, big and very big).
Figure 3: AHS-RT Decision Surface Figure 4: Internal structure of the feedback controller
Some of the fuzzy rules for the controller inference mechanism t12 task will complete execution but task will be scheduled
are listed as an example here: over even though both tasks have the same relative deadline
If (misses are zero) and (utilization is normal) then and start time. This is because was assigned a higher priority
(bandwidth adjustment is none) by the fuzzy controller because was defined to be a higher
If (misses are small) and (utilization is high) then criticality task than . Also note, due to subsystem budget
(bandwidth adjustment is small) exhaustion at time unit t15 task will miss its deadline which
would trigger a budget reallocation request to the fuzzy controller
If (misses are high) and (utilization is high) then
for an increase in the subsystem budget. Finally, at time unit t20
(bandwidth adjustment is high)
(see Table 5) the scheduler re-orders the task priorities where once
4.3 Task Scheduling Example again will be assigned the highest priority.
To demonstrate AHS-RT we have provided an example
scheduling scenario. Note for illustration purposes we are only
4.4 Subsystem Reallocation Example
Consider the following subsystems with parameters presented in
considering one subsystem. So, the primary purpose of this
Table 6 which is used to illustrate how a subsystem is scheduled
example is present how the fuzzy scheduler manages tasks within
the context of one subsystem. by AHS-RT.
Table 6: Subsystem Parameters
Table 1: Subsystem Parameters
Subsystem
Subsystem 12 4 10
10 5 10 15 3 8
20 4 5
Table 2: Task Parameters
Table 7: Budget Reallocation Snapshot
Task
Subsystem
10 2 10 5
12 3 10 -0.2 0.1 ~4.0
15 5 15 10
15 3 8 0.0 0.0 ~3.0
20 3 20 10 0.0 0.0 ~5.0
20 5 5
Table 3: Scheduling snapshot at time 0 Suppose that at some scheduling instant subsystem has a
Task current budget but due to a deadline miss the fuzzy
0,10,20,30 10,20,30,40 2 5 ~9 controller recommends a budget increase to 4. Also suppose that
and report no deadline misses or under utilization so the
0,15,30 15,30 5 10 ~5 fuzzy controller recommends no budget changes. However, the
0,20,40 20, 40 3 10 ~3 increased budget of causes the schedulability test to fail
Table 4: Scheduling snapshot at time 10 because so now the criticality level is
Task considered and since has the highest criticality level it is
granted the full budget. After = 4 the budget dimensioning
20,30 20,30,40 2 5 ~5 algorithm is performed to redistribute the remaining utilization.
15,30 15,30 2 10 ~9 Initially, the budgets for and will be and
then a successful schedulability test will be performed. Next the
20 20, 40 3 10 ~7 budget for will be but the schedulability test will fail.
Since the system is no longer schedulable the budget for will
Table 5: Scheduling snapshot at time 20
now be . This time the system is schedulable so the
Task adjusted budgets are reallocated to their respective subsystems.
20,30 30,40 2 5 ~10
5. SIMULATION
30 30 5 10 ~5 AHS-RT was implemented as part of the VxWorks 6.9 real-time
40 40 3 10 ~3 operating system (RTOS). The simulations were executed using
the SIMNT vxsim simulator. For evaluation purposes we ported
Consider the task set and subsystem listed in Tables 1 and 2. the SNU Real-Time Benchmark Suite [22] to compare deadline
Table 3 describes the scheduling of tasks at the first scheduling misses. The SNU real-time benchmark suite contains small C
event where tasks and all have the same initial starting programs used for worst-case execution time analysis. The
time but since has the nearest deadline it is assigned the highest programs are mostly numeric and DSP algorithms. In order to
priority by the fuzzy scheduler. Therefore, is allowed to represent the periodic task model of an embedded system a subset
execute until completion then at time unit t3 task executes until of the programs in the benchmark suite were chosen and assigned
time unit t5 when the subsystem’s budget expires. At time unit t10 arbitrary task rates and criticality levels. Illustrated in Figure 6
(see Table 4) the subsystem’s budget is replenished where the both AHS-RT and the VxWorks native fixed-priority preemptive
tasks can continue execution. At this time the fuzzy scheduler scheduler (FPPS) are comparable as long as the load factor is
performs a re-ordering of task priorities to reflect the system state. below ~0.70 which corresponds with the lower bound for priority
Task is assigned the highest priority because the start time is based algorithms. Notice that AHS-RT experiences significantly
the earliest and the deadline is the closest. Note that at time unit fewer deadline misses than FPPS when the system starts to
become overloaded (> ~0.70). Also note that AHS-RT manages
overload more effectively in that it does not start to report 7. ACKNOWLEDGMENT
deadline misses until closer to a ~0.80 load factor. Another This work was supported in part by the National Science
important observation depicted in Figure 7 is that AHS-RT Foundation under NSF grant number 1136146
manages deadline misses much more effectively than FPPS for
higher criticality tasks. Notice that AHS-RT does not even start to 8. REFERENCES
report deadline misses until close to a ~1.25 load factor while [1] Z. Deng and J. W.-S. Liu, “Scheduling real-time applications in an
FPPS starts to report deadlines as early as ~0.85. Clearly, AHS- open environment,” (RTSS’97), pp. 308–319.
RT is the superior scheduling mechanism as compared to FPPS [2] Davis, R.I.; Burns, A., "Hierarchical fixed priority pre-emptive
specifically during periods of overload. scheduling," (RTSS’05)
[3] Saini, G., "Application of fuzzy logic to real-time scheduling," Real
Time Conference, 2005.
[4] I. Shin and I. Lee, “Periodic resource model for compositional real-
time guarantees,” (RTSS ’03).
[5] C.D. Locke and H. Tokuda, “A Time-Value Driven Scheduling
Model for Real-Time Operating Systems”, Proc. Symp. on Real-
Time Systems, Nov. 1985.
[6] F. Zhang and A. Burns, “Analysis of hierarchical EDF pre-emptive
scheduling,” in Proc. of the 28th IEEE International Real-Time
Systems Symposium (RTSS’07)
[7] A. Mok, X. Feng and D. Chen, “Resource partition for real-time
systems,” in Proc of the 7th Real-Time Technology and Applications
Symposium (RTAS’01), 2001
[8] J. Stankovic, C. Lu, S. Son and G. Tao, “The case for feedback
control in real-time scheduling,” in Proc. of the 11th Euromicro
Figure 5: Number of Deadline Misses (All Tasks) Conference on Real-Time Systems (ECRTS ’99).
[9] C. Lu, J. Stankovic, G. Tao and S. Son, “Design and evaluation of a
feedback control EDF scheduling algorithm,” in Proc. of the 20th
IEEE (RTSS’99).
[10] C. Lu, J. Stankovic, S. Son and G. Tao, “Feedback control real-time
scheduling: Framework, modeling and algorithms,” Real-Time
Systems, vol. 23, pp 85-126, 2002.
[11] T. Abdelzaher, E. Atkins and K. Shin, “QoS negotiation in real-time
systems and its application to flight control,” in Proc. of the IEEE
(RTSS’97).
[12] R. Rajkumar, C. Lee, J. Lehoczky and D. Siewiorek, “A resource
allocation model for QoS management, “ in Proc. of the IEEE Real-
Time Technology and Applications 1997.
[13] S.P. Dwivedi, "Adaptive Scheduling in Real-Time Systems
Through Period Adjustment", CoRR, 2012.
Figure 7: Number of Deadline Misses (Highest Criticality [14] Richardson, P.; Sarkar, S., "Adaptive scheduling: overload
Tasks) scheduling for mission critical systems," (RTSA) 1999
[15] J. Yen, J. Lee, N. Pfluger, and S. Natarajan. "Designing a fuzzy
6. CONCLUSIONS/FUTURE WORK scheduler for hard real-time systems." (1992).
In this paper we considered the problem of how to schedule tasks [16] L. Jonathan, A. Tiao, and J. Yen. "A fuzzy rule-based approach to
with varying levels of criticality on a uniprocessor to more real-time scheduling." In Fuzzy Systems, In Proc. of the 3rd IEEE
effectively adapt to computational changes. Those changes were Conference. IEEE, 1994.
managed by hierarchical scheduling to provide the temporal [17] S. Mojtaba, and M. Naghibzadeh. "A Fuzzy algorithm for real-time
isolation between tasks. The efficient scheduling of tasks was scheduling of soft periodic tasks." IJCSNS International Journal of
accomplished using a fuzzy based heuristic which has been Computer Science and Network Security 6.2A (2006):
proven to be more effective than traditional deadline based [18] X. Feng, X. Shen, L. Liu, Z. Wang, and Y. Sun. "Fuzzy logic based
approaches especially during periods of overload. The results are feedback scheduler for embedded control systems." In Advances in
a demonstrated reduction in deadline misses for all tasks during Intelligent Computing, 2005.
periods of overload as compared to traditional fixed priority based [19] Khalilzad, N.M.; Behnam, M.; Nolte, T., "Adaptive hierarchical
scheduling mechanisms. As further confirmation for the scheduling framework: Configuration and evaluation," (ETFA),
practicality for this approach we implemented AHS-RT as part of 2013.
the VxWorks RTOS. [20] L., Chenyang, J. Stankovic, H. Son, and G. Tao. "Feedback control
real-time scheduling: Framework, modeling, and algorithms*." Real-
Future work includes evaluating the additional overhead AHS-RT Time Systems (2002).
incurs in VxWorks as compared to the traditional scheduler.
Additionally, we would like to extend AHS-RT into a multi-core [21] M. Behnam, T. Nolte, I. Shin, M. Asberg. Towards Hierarchical
Schedling in VxWorks. (OSPERT) 2008
environment and consider semi-independent tasks where
subsystems would have to share a mutual resource such as a [22] SNU Real-Time Benchmark, http://www.cprover.org
semaphore.