Randomized Work Stealing for Large Scale Soft Real-Time Systems

Jing Li, Son Dinh, Kevin Kieselbach, Kunal Agrawal, Christopher Gill, Chenyang Lu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

18 Scopus citations


Recent years have witnessed the convergence of two important trends in real-time systems: growing computational demand of applications and the adoption of processors with more cores. As real-time applications now need to exploit parallelism to meet their real-time requirements, they face a new challenge of scaling up computations on a large number of cores. Randomized work stealing has been adopted as a highly scalable scheduling approach for general-purpose computing. In work stealing, each core steals work from a randomly chosen core in a decentralized manner. Compared to centralized greedy schedulers, work stealing may seem unsuitable for real-time computing due to the non-predictable nature of random stealing. Surprisingly, our experiments with benchmark programs found that random work stealing (in Cilk Plus) delivers tighter distributions in task execution times than a centralized greedy scheduler (in GNU OpenMP).To support scalable soft real-time computing, we develop Real-Time Work-Stealing platform (RTWS), a real-time extension to the widely used Cilk Plus concurrency platform. RTWS employs federated scheduling to allocate cores to multiple parallel real-time tasks offline, while leveraging the work stealing scheduler to schedule each task on its dedicated cores online. RTWS supports parallel programs written in Cilk Plus and requires only task parameters that can be readily measured using existing Cilk Plus tools. Experimental results show that RTWS outperforms Real-Time OpenMP in term of deadline miss ratio, relative response time and resource efficiency on a 32-core system.

Original languageEnglish (US)
Title of host publicationProceedings - 2016 IEEE Real-Time Systems Symposium, RTSS 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages12
ISBN (Electronic)9781509053025
StatePublished - Jul 2 2016
Event2016 IEEE Real-Time Systems Symposium, RTSS 2016 - Porto, Portugal
Duration: Nov 29 2016Dec 2 2016

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Other2016 IEEE Real-Time Systems Symposium, RTSS 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Randomized Work Stealing for Large Scale Soft Real-Time Systems'. Together they form a unique fingerprint.

Cite this