- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Response-time analysis and overload management in real-time...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Response-time analysis and overload management in real-time systems Murali, Sriram
Abstract
We provide two approaches to handling overload in shared resources offering realtime guarantees. We first provide a technique (based on mathematical optimization) for identifying the possible causes for an overload situation by computing the worst-case demand of the system, depending upon the amount of requests serviced. Worst-case analysis of response time has a pseudo-polynomial time complexity, and when there is no knowledge about the workload, the complexity further increases. We provide polynomial-time heuristics to reduce the computation time of the algorithm. Further, we evaluate it against other techniques using stochastic analysis to stress on the accuracy and ease of estimation of the result. The scheduling policy based on the approach is useful to detect an overload in the resource and to allow us to make responsible decisions on it. Secondly, we present a scheduling policy (obtained through stochastic approximation) to handle overload in real-time systems. Competitive analysis of online algorithms has commonly been applied to understand the behavior of real-time systems during overload conditions. While competitive analysis provides insight into the behavior of certain algorithms, it is hard to make inferences about the performance of those algorithms in practice. Similar on-line scheduling approaches tend to function differently in practice due to factors. Further, most work on handling overload in real-time systems does not consider using information regarding the distribution of arrival rates of jobs and execution times to make scheduling decisions. With some information about the workload, we aim to improve the revenue earned by the service provider, in a scenario when each successful job completion results in revenue accrual. We prove that the policy we outline does lead to increased revenue when compared to a class of scheduling policies that make static resource allocations to different service classes. We also use empirical evidence to underscore the fact that this policy performs better than a variety of other scheduling policies. The ideas presented can be applied to several soft real-time systems, specifically systems with multiple service classes.
Item Metadata
Title |
Response-time analysis and overload management in real-time systems
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2012
|
Description |
We provide two approaches to handling overload in shared resources offering realtime
guarantees. We first provide a technique (based on mathematical optimization)
for identifying the possible causes for an overload situation by computing the
worst-case demand of the system, depending upon the amount of requests serviced.
Worst-case analysis of response time has a pseudo-polynomial time complexity,
and when there is no knowledge about the workload, the complexity further increases.
We provide polynomial-time heuristics to reduce the computation time
of the algorithm. Further, we evaluate it against other techniques using stochastic
analysis to stress on the accuracy and ease of estimation of the result. The scheduling
policy based on the approach is useful to detect an overload in the resource and
to allow us to make responsible decisions on it. Secondly, we present a scheduling
policy (obtained through stochastic approximation) to handle overload in real-time
systems. Competitive analysis of online algorithms has commonly been applied to
understand the behavior of real-time systems during overload conditions. While
competitive analysis provides insight into the behavior of certain algorithms, it is
hard to make inferences about the performance of those algorithms in practice.
Similar on-line scheduling approaches tend to function differently in practice due
to factors. Further, most work on handling overload in real-time systems does
not consider using information regarding the distribution of arrival rates of jobs
and execution times to make scheduling decisions. With some information about
the workload, we aim to improve the revenue earned by the service provider, in
a scenario when each successful job completion results in revenue accrual. We
prove that the policy we outline does lead to increased revenue when compared to
a class of scheduling policies that make static resource allocations to different service classes. We also use empirical evidence to underscore the fact that this policy
performs better than a variety of other scheduling policies. The ideas presented
can be applied to several soft real-time systems, specifically systems with multiple
service classes.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2012-02-22
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0072592
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2012-05
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International