Schedulability analysis and utilization bounds for highly scalable real-time services

Research output: Contribution to journalConference articlepeer-review


The proliferation of high-volume time-critical web services such as online trading calls for a scalable server design that allows meeting individual response-time guarantees of real-time transactions. A main challenge is to honor these guarantees despite unpredictability in incoming server load. The extremely high volume of real-time service requests mandates constant-time scheduling and schedulability analysis algorithms (as opposed to polynomial or logarithmic ones in the number of current requests). This paper makes two major contributions towards developing an architecture and theoretical foundations for scalable real-time servers operating in dynamic environments. First, we derive a tight utilization bound for schedulability of aperiodic tasks (requests) that allows implementing a constant time schedulability test on the server. We demonstrate that Liu and Layland's schedulable utilization bound of ln 2 does not apply to aperiodic tasks, and prove that an optimal arrival-time independent scheduling policy will meet all aperiodic task deadlines if utilization is maintained below 1/1+√1/2. Second, we show that aperiodic deadline-monotonic scheduling is the optimal arrival-time-independent scheduling policy for aperiodic tasks. This result is used to optimally prioritize server requests. Evaluation of a utilization control loop that maintains server utilization below the bound shows that the approach is effective in meeting all individual deadlines in a high performance real-time server.

Original languageEnglish (US)
Pages (from-to)15-25
Number of pages11
JournalReal-Time Technology and Applications - Proceedings
StatePublished - Jan 1 2001
Externally publishedYes
Event7th Real-Time Technology and Applications Symposium (RTAS 2001) - Taipei, Taiwan, Province of China
Duration: May 30 2001Jun 1 2001

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software


Dive into the research topics of 'Schedulability analysis and utilization bounds for highly scalable real-time services'. Together they form a unique fingerprint.

Cite this