=Paper=
{{Paper
|id=Vol-1291/ewili14_9
|storemode=property
|title=Adaptive Resource Synchronization In Hierarchical Real-Time Systems
|pdfUrl=https://ceur-ws.org/Vol-1291/ewili14_9.pdf
|volume=Vol-1291
|dblpUrl=https://dblp.org/rec/conf/ewili/SpringerPG14
}}
==Adaptive Resource Synchronization In Hierarchical Real-Time Systems==
https://ceur-ws.org/Vol-1291/ewili14_9.pdf
Adaptive Resource Synchronization
In Hierarchical Real-Time Systems
Tom Springer, Steffen Peter, and Tony Givargis
Center for Embedded Computer Systems
University of California, Irvine, USA
{tspringe, st.peter, givargis}@uci.edu
ABSTRACT Policy (SRP) [5] are not a viable solution either because there is
In this paper we outline the Adaptive Resource Allocation no system wide visibility across subsystems. To cope with these
Protocol (ARAP) as an improved resource synchronization issues, the Hierarchical Scheduling Framework (HSF) has been
algorithm for hierarchically scheduled real-time systems. ARAP introduced to simplify the development and integration of
exploits knowledge about task utilization, using a proportional- embedded systems and shown to be particularly useful in the area
integral-derivative (PID) controller, to estimate required resource of open systems [1].
bandwidth and improve scheduling decisions. Our analysis and The primary goal of hierarchical scheduling is to bind the
experiments with RTSIM show that ARAP provides better temporal behavior of those applications whose execution times
temporal isolation and resource utilization during periods of deviate considerably, allowing for the predictable integration of
transient overload compared to state-of-the-art resource the various subsystems. However, in order to provide this
synchronization algorithms. Implemented as part of VxWorks, the temporal isolation the basic HSF model assumes the absence of
results are confirmed using an avionic system, for which ARAP shared resources. The problem with this assumption is that most
substantially reduced the number of hard real-time deadline embedded systems share global resources and need to be
misses.1 synchronized. While traditional resource access protocols can be
Categories and Subject Descriptors used to synchronize resources locally, within a subsystem, global
C.3 [Special-Purpose and Application-Based Systems]: Real- resource access presents added challenges such as the
Time and embedded systems. unpredictable holding times between globally shared resources.
In this paper we present the Adaptive Resource Allocation
General Terms Protocol (ARAP) which is a new resource synchronization policy
Algorithms, Performance, Reliability.
for globally shared resources in an HSF, focused in a single
Keywords processor environment. ARAP utilizes knowledge about previous
Real-time systems, hierarchical scheduling, resource sharing, task utilization, by applying the concept of control theory using a
operating systems. proportional-integral-derivative (PID) controller, to adapt to
changes in the system. The primary benefit of this new strategy is
1. INTRODUCTION that the system can now adapt to computational changes
Modern embedded and Cyber Physical Systems such as smart dynamically. The result being that temporal isolation is
cities, autonomous automotive systems or the smart electrical grid maintained between subsystems even during periods of overload.
are composed of various subsystems which are often developed
We applied ARAP in an actual embedded system that was
independently. A common requirement for such systems is
experiencing overload conditions resulting in missed deadlines
temporal isolation, meaning that the temporal behavior of one
due to soft and hard real-time tasks sharing the same resource.
subsystem should never adversely affect the temporal behavior of
Our experiments demonstrated the benefit of ARAP specifically
another subsystem.
during overload conditions and as a result deadline misses for
This requirement for temporal isolation is challenged by two hard real-time tasks were eliminated. Other contributions of this
major properties we address in this paper. First, the amount of paper include: the performance analysis of ARAP as compared to
data and resulting computation times may vary significantly. Such other synchronization protocols, the ARAP protocol implemented
variations are not easy to predict neither in their magnitude nor as part of the resource manager class in an open source real-time
their duration. The second challenge is that the temporal behavior scheduling simulator, a simulation model of transient overload
of the subsystems is often influenced by resources which are conditions for performance analysis and the first time
shared among tasks. For instance, if an interface to a sensor implementation (to the best of our knowledge) of an HSF as part
device is locked by a task in one subsystem the temporal isolation of the VxWorks real-time operating system.
of other subsystems requiring access to the sensor could be
The remainder of the paper is structured as follows: In Section 2
violated.
we provide an overview of hierarchical scheduling. Related work
To address these challenges a variety of solutions have been is reviewed in Section 3 while Section 4 presents the adaptive
proposed. The most common approach is “over-engineering.” resource access mechanism used in our protocol. Performance
Historically, systems were designed and considered “safe” with a analysis and results are provided in Section 5. Section 6 describes
utilization factor U of less than 70% [18], while systems with a the simulation environment and Section 7 presents the
higher utilization were deemed “unsafe”. Traditional resource implementation in an actual embedded system application.
access protocols, such as Priority Inheritance Protocol (PIP) [4],
the Priority Ceiling Protocol (PCP) [4] or the Stack Resource 2. PRELIMINARIES
This section presents the overall architecture of a hierarchical
scheduled system as well as the definition of a system overload
1
EWiLi’14, November 2014, Lisbon, Portugal. Copyright condition.
retained by the authors.
2.1 Hierarchical Scheduling Overall system load is defined in [18] as the equivalent to the
The basic framework of a hierarchically scheduled system [2] [3] processor utilization factor U:
is composed of multiple applications (subsystems) where each (1)
application could be composed of multiple tasks (see Figure 1). A
global scheduler controls which application can use the processor where is the computational time and is the task period. A
while the local scheduler determines which application’s task load value of means the system is overloaded (requested
should actually execute. Every application is allocated a separate computation time exceeds the available processor time).
service manager, known as the server. Each server is allocated a Consequently, there are two broad classifications of overload
CPU capacity reserve, which is assigned as a pair where conditions also defined by the authors in [18]:
is defined as the time quantum and is defined as the period.
1. Transient overload is defined for a limited time where the
average load is but the maximum load is .
2. Permanent overload is defined for an unpredictable duration
where the average load is .
It is important to note that in this paper our approach was to only
consider transient overload conditions. As a result, the primary
benchmark of our work is to practically eliminate hard real-time
task deadline misses and manage soft real-time task misses so
that the system can recover gracefully from an occasional
transient overload condition.
3. RELATED WORK
Initially an HSF was proposed by authors in [3][9] as a means to
perform composability analysis for open systems development.
The motivation being that it can quickly become intractable to
accurately verify the timing behavior of the embedded system as
Figure 1: Hierarchical Scheduling Framework the complexity increases. The approach was to verify the timing
behavior of each individual subsystem independently then
Each task gets to execute for its assigned time quantum , when compose each subsystem into the overall system. However,
the task’s time quantum is exhausted the task is blocked until typical embedded systems are not entirely independent because
its next period. In effect, the server functions as an independent subsystems may need to share resources which are why previous
processor virtually limiting the bandwidth of each application. research on HSFs was extended to include schedulability analysis
2.2 Resource Sharing of semi-independent real-time components [8] [5].
Resource sharing in an HSF can be classified as either local or The SIRAP [8] protocol was developed for fixed-priority
global. Tasks that share resources within the same subsystem are preemptive scheduling while the BROE [10] protocol was
considered local resource sharing. Tasks that share resource developed for dynamic-priority scheduling. Both protocols use a
across applications are classified as global resource sharing which form of budget check to determine if there was enough budget left
requires the resource be protected at the local as well as global to enter the critical section. If the remaining budget was deficient
level. Therefore a task that locks a global resource will also cause to complete the critical section the task was blocked from locking
its server to lock the resource. This creates an added complication the resource until the next budget replenishment. The limitation
of increased resource holding times due to the server budget with the budget check approach is that the critical section
exhaustion. execution time is based upon worst-case analysis. This could lead
Researchers have proposed several solutions [8][6] to the problem to resource under utilization due to conservative WCET
of this added delay in critical sections due to server budget estimations. Additionally, a priori knowledge of the WCET for a
exhaustion. One such approach called budget check checks to see critical section is required which is often difficult to evaluate in
if there is sufficient server budget before allowing a task to enter a applications with variable execution times.
critical section. If the budget is insufficient the task is not granted Hierarchical scheduling with resource sharing HSRP [2] and later
access to the resource until the next budget replenishment. In extended to OPEN-HSRP [10] utilized a budget overrun approach
another approach the task is allowed to enter a critical section to reduce the resource holding times during budget expiration.
without checking for a sufficient budget. As a result, if the budget While this approach does provide better flexibility for applications
is exhausted while still inside the critical section the task is just with variable execution times there are some disadvantages. One
allowed to continue and consume extra budget until the end of the such drawback is that even though a task is allowed to overrun its
critical section. budget there still has to be a limit placed upon the maximum
overrun time. In order to prevent unbounded blocking a task is
2.3 Overload Conditions forcefully preempted if it is still holding the resource during the
The problem of server budget exhaustion while a task is inside a next budget replenishment. This leads to limitations being placed
critical section can be amplified during periods of overload upon the types of shared resources used to those that can safely be
because it could unnecessarily increase the time a critical task aborted to relatively short critical section execution times.
would have to wait for the resource. As a consequence, task Another consideration is because a task can overrun its budget the
overruns can result because tasks execute longer than expected strict temporal isolation between subsystems could be violated. It
which can have an increasingly negative impact on resource is for these reasons that HSRP based systems are typically only
holding times. Thus, before we proceed any further, we will take used for soft real-time systems.
the time to provide a brief definition of an overload condition.
Other recently published work, known as RRP [11], took a 4.1.1 Budget Exhaustion
different approach to resource locking before budget exhaustion. The primary difference between the various resource access
Instead of performing a budget check the task is allowed to enter protocols in an HSF is how the budget exhaustion of a
the critical section and unlike HSRP if the budget has expired the subsystem’s server is handled. As mentioned in Section 3 the
task is simply preempted and rolled back. The RRP protocol SIRAP protocol performs a budget check while OPEN-HSRP
improved the average case response times and task schedulability permits budget overflow. Similar to the SIRAP protocol our
compared to SIRAP and the OPEN-HSRP protocols. However, method also performs a form of budget check. However, instead
the limitation with RRP is that it can only be used with shared of using a static a-priori calculation of the Critical Section
resources that can be safely rolled back (e.g. databases). Execution Time (CSET) ARAP incorporates feedback to estimate
Our approach does not rely on WCET analysis of critical section the next resource holding time for that critical section
executions times but instead uses feedback which is more flexible execution instance.
since it represents the actual operating environment. Previous The primary benefit of incorporating feedback is that the system
research has proposed using feedback to manage CPU scheduling can dynamically adapt to changes in CSET specifically during
reservations [12] [13] then extended it to include application periods of transient overload. In this situation the SIRAP protocol
defined Quality of Service (QoS) parameters. However, ARAP is tends to be too conservative because with SIRAP the overload
the first to apply a feedback mechanism to resources that are condition would have to be factored into the CSET calculation
shared across subsystems in a hierarchically scheduled system. resulting in task under utilization. While the OPEN-HSRP
Past research has demonstrated [14][15] that previous task protocol can better adapt to overload conditions the overrun
behavior is a valid indicator for future task behavior and because mechanism could adversely affect the response times of higher
our method incorporates feedback ARAP is better positioned to priority tasks. Therefore, our approach leads to a more robust and
respond to transient overload conditions. Consequently, SIRAP is better utilized system with a higher degree of determinism.
too conservative by using static WCET analysis while OPEN-
HSRP overrun mechanisms could affect the deadlines of higher 4.1.2 Feedback Mechanism
priority tasks specifically during periods of transient overload. Our feedback architecture is implemented as part of the kernel
(see Figure 3) and consists of a PID which is used to estimate the
4. ADAPTIVE RESOURCE ACCESS execution time for a task executing inside a critical section. The
PROTOCOL (ARAP) output or observed value of the PID is the estimated error ratio
This section provides an overview of ARAP which is a resource (ER) which is defined as the ratio between the actual measured
access protocol that synchronizes access to shared resources in a critical section execution time and the previous window of past
hierarchically scheduled system. In this paper we only consider error ratios. The semaphore request mechanism is used as the
shared memory as the mutually exclusive resource. However, actuator of the system determining whether a task is granted
ARAP could also be extended to include other shared resources access to the critical section. The control action is performed by
(e.g. memory-mapped areas, device registers, and peripheral either allowing the task to acquire the semaphore or to block the
devices) as well. The access to these resources are performed as task waiting on the semaphore. If a task requests a semaphore
part of a critical section and protected by a semaphore. (e.g. srp_wait ()) it has to pass the budget check test to acquire the
semaphore. The budget check test uses information from the PID
4.1 Protocol Description controller as well as information from the scheduler to determine
Similar to the SIRAP and OPEN-HSRP protocols ARAP utilizes a if there is enough remaining budget to complete the critical
two-level hierarchy for resource management. Resources that are section. To apply the feedback control ARAP uses the PID
shared within a subsystem are managed with SRP and resources controller to compute which is used to project the next
that are shared across subsystems are managed with an extended critical section execution time based upon the ER. Using the basic
version of HSRP. The overall sequence of actions for ARAP is form a general PID controller [19] defined as:
provided by the flowchart depicted in Figure 2.
(2)
where , and are the PID control parameters, IW is the
integration window and DW is the size of the differentiation
interval.
Figure 3: Structure of feedback architecture
4.1.3 Implementation Considerations
The implementation of ARAP is similar to SIRAP but the locking
operations (srp_wait, and srp_signal) are modified to utilize the
Figure 2: ARAP architecture flowchart feedback mechanism. The locking operation is performed by the
srp_wait function so when a task tries to acquire a resource the
local scheduler performs a check to determine if there is enough tasks with lower priority than which share a global resource,
budget to complete the critical section. At the semaphore request such that:
time t let the function calcRHT(), which utilizes the PID (6)
controller, calculate the projected resource holding time so that
. At the same time let the function (7)
getCurBudget() get the subsystem server’s remaining budget such
that . If the task’s projected resource (8)
holding time then the task is allowed to lock the The resource holding time for is defined as the maximum
resource and execution continues according to the rules of HSRP. critical section execution plus the interference from the tasks
On the other hand, if then the task is not permitted to with a higher preemption level than the ceiling of the resource
lock the resource until the next subsystem budget replenishment, during the CSET of . Such that is computed using
this is known as self-blocking. The release operation is performed as follows:
by the srp_signal function which signifies the completion of the
critical section. The time that is spent in the critical section is used (9)
as the feedback to the PID controller. At the semaphore release where is the ceiling of the resource accessed within the
time t’ the function recordRHT( records the actual time critical section and are the worst-case execution time
spent in the critical section. and period of the task that has a higher preemption level than
. The value u represents the maximum resource
5. PERFORMANCE ANALYSIS within a subsystem.
This section provides the background for the performance analysis
of ARAP as part of a hierarchically scheduled system (equations 5.2 Global Performance Analysis
are applied in subsection 5.3). Given that both ARAP and SIRAP For global scheduling analysis the virtual processor model can be
perform a budget check the analysis performed for SIRAP [8] can extended to a global model where multiple subsystems
be applied to ARAP as well. The difference is that ARAP uses a can be verified according to equation (3). Therefore, the
projected CSET based upon feedback whereas SIRAP uses static schedulability test for a fixed priority global scheduler is defined
a-priori CSET. as:
5.1 Local Performance Analysis (10)
According to the authors in [7] each subsystem is where of subsystem is the maximum resource holding time
schedulable if with a preemption level less than .
(3)
5.3 Performance Results
where is the supply bound function used by authors [8] to Schedulability analysis for HSRP was performed by authors in [2]
calculate the minimum CPU allocations required during an which is very similar to the SIRAP analysis which excludes self-
interval of time. Authors in [7] presented a periodic processor blocking but has to consider the overrun mechanisms. Similar to
model to characterize the allocations defined by what they called SIRAP as well the analysis for OPEN-HSRP is extended from
the virtual processor model represented as . The supply equation (3) as follows:
bound function (see Figure 4) of the virtual processor model is (11)
defined as:
where is the maximum blocking time when is blocked by a
(4) lower priority task. The supply bound function is defined
by equation (4) and the request bound function is
where and is defined as the defined as follows:
interval .
(12)
where is the set of tasks with priorities higher than . The
global schedulability is defined as:
(13)
where the load bound function is defined as follows:
(14)
where
(15)
where is the set of subsystems with a higher priority than
Figure 4: Supply bound function virtual processor model subsystem and is the maximum time that is blocked by
T(3,2), k=3 lower priority subsystems. The performance of ARAP is
evaluated as the minimum value of the request bound function
The request bound function of a task is defined as: that would guarantee schedulability. For the synthetic
(5)
workload we generated random variances of a hierarchical system
where is the WCET of task , is the maximum self- consisting of 3 separate subsystems such that . Each
blocking for task , is the interference from tasks with a subsystem consisted of 3 tasks with a global resource being
higher priority than and is the maximum interference by
shared between each subsystem. Each subsystem has a total using resource sharing with budget overrun (OPEN-HSRP). We
utilization of 15%. Task periods ranged between 100 and 1000. executed sample runs modeling transient overload conditions at
Figure 5 represents the overall task acceptance rate for the 0%, 5%, 10%, 15%, 20% and 25% respectively. The Figures 6
simulated task sets required for task schedulability as defined by and 7 separate out the miss rates between the hard and soft real
equation (3). Notice that ARAP has an improved acceptance rate time tasks.
over SIRAP. The reason for this improvement is that the WCET
calculation for ARAP adapts to the current workload which
provides greater flexibility than SIRAP’s static approach.
Additionally, because ARAP is adaptable it is comparable to
OPEN-HSRP but without the added complexity of managing the
overruns of the OPEN-HSRP protocol.
Figure 6: Hard Real-Time task miss rate (RTSIM)
Figure 5: Task acceptance rate for simulated task sets
6. SIMULATION ENVIRONMENT
This section describes the simulation environment we used to
further analyze ARAP which was implemented as a simulation
component within RTSIM [16]. RTSIM (Real-Time System
Simulator) is a task scheduler simulation and is used primarily for
simulating real-time control systems. In order to implement Figure 7: Soft Real-Time task miss rate (RTSIM)
ARAP in RTSIM we extended the existing resource manager In the figures above EDF-FCFS represents EDF scheduling with
class to include the feedback mechanisms. standard first-come-first-serve resource management (no PIP),
EDF-HSRP represents EDF scheduling with OPEN-HSRP
6.1 Modeling and PID Tuning resource management and EDF-ARAP represents EDF scheduling
A Heaviside step function was used to model the transient with PID feedback control. Depicted in Figure 6 the ARAP
overload condition. Heaviside functions are used extensively in protocol outperforms the other methods while it sacrifices some
control theory to represent different loads. The discontinuous deadline misses in soft real-time tasks. Notice that in Figure 6
nature of this function maps nicely to an overload situation where both scheduling mechanisms EDF-FCFS and EDF-HSRP exhibit
we can model periods of nominal, ramp-up and ramp-down hard real-time task misses. Even though EDF-HSRP manages the
behaviors. The Ziegler-Nichols [17] tuning method was used to soft real-time tasks with a periodic server hard real-time task
tune the feedback mechanism. misses are realized because the overrun mechanism allows the
task to continue, even though its server budget has been
6.2 Example Task Set exhausted. In Figure 7 EDF-HSRP outperforms EDF-ARAP
The example task set consisted of a total of five periodic tasks, because the overrun mechanism allows the task to continue at the
two hard real-time and three soft real-time tasks but only two expense of hard real-time deadline misses.
tasks T3 and T5 shared a critical region and therefore were
synchronized by a semaphore. For the two tasks (T3 and T5), that 7. PRACTICAL EVALUATION
shared a semaphore, execution times were modeled to exceed To demonstrate the practicality of our approach we also
their nominal rates. The Tasks T4 and T5 which represent hard implemented ARAP as part of a ground-based command and
real-time tasks were allowed to execute up to their predefined control test set used for satellite telemetry processing. A
WCET while Task T3 was modeled to exceed its bandwidth, hardware-in-the-loop (HWIL) simulator was used to provide the
thereby generating a transient overload condition. workload for our system. This particular use case was chosen
In order to provide a comparison of ARAP we simulated both the because telemetry processing times can vary considerably
traditional first-come-first-serve (FCFS) and OPEN-HSRP depending upon the data rate and how densely the telemetry frame
resource allocation protocols in RTSIM. One note; is that due to is populated. In this way, we can use the HWIL simulator to
the simulated transient overload conditions of our scenario SIRAP generate transient overload conditions.
was not included in the results because it was repeatedly denied The main software components of the system includes a hard real-
access to the shared resource due to conservative nature of the time periodic task that performs the frame processing of a
protocol. telemetry stream. The other primary software component is a soft
We ran simulations using the task set defined above with the real-time task that provides the health and status monitoring for
Heaviside function to simulate task execution times for analysis as the vehicle. The telemetry processing task and the monitoring task
to how well the ARAP protocol performed against EDF both share a global resource which is the decommutated telemetry
scheduling with FCFS resource allocation (no PIP) as well as EDF buffer. Similar to the simulation environment we used the HWIL
simulator to model transient overloads between 0%-25%. Two of-the-art synchronization protocols. By implementing ARAP as
traditional resource synchronization protocols (PIP and FCFS) part of an actual embedded system application we were able to
were used in the evaluation for comparison. effectively eliminate deadline misses for a critical high priority
The results for the overall deadline miss rates were separated out task. Our motivation for this work stems for the aerospace
based upon soft and real-time tasks. Soft real-time tasks were industry where systems are routinely over engineered in the
scheduled by the local subsystem scheduler which is scheduled by interest of real-time determinism. It is a common perception that
the global fixed priority scheduler of VxWorks. Hard real-time an embedded system is considered “unsafe” above 70% total
tasks were scheduled directly by the global VxWorks scheduler. utilization. As a result of this work we demonstrated that we can
Soft real-time tasks were modeled to allow their execution time to build more efficient embedded systems by more effectively
exceed their budget while the hard real-time tasks were designed managing the tasks within that system and in doing so reducing
to not exceed their pre-defined utilization budget. the total number of processing elements required.
Figures 8 and 9 show the miss rates of the hard real-time tasks and 9. ACKNOWLEDGMENT
soft real-time tasks respectively. The feedback mechanism This work was supported in part by the National Science
represented as FPPS-ARAP in the graph was compared against Foundation under NSF grant number 1136146.
the priority inheritance protocol (FPPS-PIP) and the first-come-
first-server (FPPS-FCFS) protocol. Notice how even when using 10. REFERENCES
priority inheritance a lower priority task can still cause a higher [1] Z. Deng and J.W. Liu, “Scheduling real-time applications in an
priority task to miss their deadline. The reason is that while PIP open environment.” In Proc. of IEEE Real-Time Systems Symp.
does solve the priority inversion problem it does not solve the 1997.
problem of unbounded blocking. [2] R.I. Davis and A. Burns, “Resource Sharing in Hierarchical Fixed
Priority Pre-emptive Systems.” In RTSS’06.
As illustrated in Figure 8 ARAP does provide the mechanism for
[3] P. Goyal, X. Guo and H.M. Vin, “A hierarchical CPU scheduler
eliminating the extended blocking by a lower priority task for multimedia operating systems.” In OSDI, pp. 107-121, 1996.
however, the soft real-time task could be affected causing
increased missed deadlines for the soft real-time task. Notice that [4] L. Sha, R. Rajkumar and J.P. Lehoczky, “Priority Inheritance
in Figure 9 ARAP reports the highest number of deadline misses Protocols: An Approach to Real-Time Synchronization”. IEEE
trans. Comput. Vol 39, pp. 1175-1185, 1990.
for soft real-time tasks. The reason for this behavior is that during
a transient overload the task may be denied access to the resource [5] T.P. Baker , “Slack-Based Scheduling of Real-Time Processes”.
and have to wait until the next budget replenishment period. As Real-Time Systems, vol. 3 pp. 67-99, 1991.
shown in the results using a feedback mechanism can directly [6] L.Abeni and G.C. Buttazzo, “Resource reservations in dynamic
benefit the determinism of a hard real-time at the possible expense real-time systems”, Real-Time Systems, pp. 123-165, 2004.
of other soft real-time tasks that share the global resource. [7] A. Mok, X.Feng and D. Chen. “Resource Partition for Real-Time
Systems”. In Proc. of IEEE Real-Time Technology and Appl.
Symp., pp99-110, 2005.
[8] M. Behnam, T. Nolte, M Sjodin and I Shin. “SIRAP: A
synchronization protocol for hierarchical resource sharing real-time
open systems,” In EM-SOFT 07.
[9] N. Fisher, M. Bertogna and S. Baraugh. “The Design of an EDF-
Scheduled Resource-Sharing Open Environment”. In RTSS ’07.
[10] M. Behnam, T. Nolte, M Sjodin and I Shin. “Overrun Methods and
Resource Holding Times for Semi-Independent Real-Time
Systems,” IEEE trans. on Indus. Informatics, 2010.
Figure 8: Hard Real-Time task miss rate (vxWorks) [11] M. Asberg, T. Nolte and M. Behnam, “Resource Sharing Using the
Rollback Mechanism in Hierarchically Scheduled Real-Time Open
Systems,” In RTSA ’13
[12] L. Abeni, G.C. Buttazzo , “Hierarchical qos management for time
sensitive applications,” In RTAS’01.
[13] L. Abeni, L. Palopoli, G. Lipari, J. Walpole, “Analysis of a
Reservation-Based Feedback Scheduler,” In RTSS ’02.
[14] P. Phinjaroenphan, S. Beivinakoppa, P. Zeephongsekul. “A Method
For Estimating the Execution Time of a Parallel Task on a Grid
mode,” Advances in Grid Computing – EGC 2005.
[15] Burchard, L.-O.; Altenbernd, P., "Estimating decoding times of
Figure 9: Soft Real-Time task miss rate (vxWorks) MPEG-2 video streams," Image Processing, vol.3, 2000
[16] RTSIM, http://www.rtsim.sssupit.com
8. CONCLUSION [17] Ziegler, J.G Nichols, N.B. Optimal settings for automatic
In this paper we considered the problem of sharing global
controllers. Transactions of the ASME pp759-768, 1962.
resources in a hierarchical scheduled system. Traditionally, HSF
was designed for soft real-time applications, in part due to [18] G. C. Buttazzo, Hard Real-Time Computing Systems, Springer,
Real-Time System Series, 2011
problem of unbounded resource holding times between global
resources. Our approach which utilized feedback from the actual [19] Stankovic, Jack A., et al. "The case for feedback control real-time
system to estimate future usage provided greater flexibility and scheduling." Real-Time Systems, 1999. Proc of the 11th Euromicro
Conference on. IEEE, 1999.
allowed for the system to adapt to changes better than other state-