BWS: Balanced work stealing for time-sharing multicores

Xiaoning Ding, Kaibo Wang, Phillip B. Gibbons, Xiaodong Zhang

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

30 Scopus citations


Running multithreaded programs in multicore systems has become a common practice for many application domains. Work stealing is a widely-adopted and effective approach for managing and scheduling the concurrent tasks of such programs. Existing work-stealing schedulers, however, are not effective when multiple applications time-share a single multicore-their management of steal-attempting threads often causes unbalanced system effects that hurt both workload throughput and fairness. In this paper, we present BWS (Balanced Work Stealing), a work-stealing scheduler for time-sharing multicore systems that leverages new, lightweight operating system support. BWS improves system throughput and fairness via two means. First, it monitors and controls the number of awake, steal-attempting threads for each application, so as to balance the costs (resources consumed in steal attempts) and benefits (available tasks get promptly stolen) of such threads. Second, a steal-attempting thread can yield its core directly to a peer thread with an unfinished task, so as to retain the core for that application and put it to better use. We have implemented a prototype of BWS based on Cilk++, a state-of-the-art work-stealing scheduler. Our performance evaluation with various sets of concurrent applications demonstrates the advantages of BWS over Cilk++, with average system throughput increased by 12.5% and average unfairness decreased from 124% to 20%.

Original languageEnglish (US)
Title of host publicationEuroSys'12 - Proceedings of the EuroSys 2012 Conference
Number of pages14
StatePublished - 2012
Externally publishedYes
Event7th ACM European Conference on ComputerSystems, EuroSys'12 - Bern, Switzerland
Duration: Apr 10 2012Apr 13 2012

Publication series

NameEuroSys'12 - Proceedings of the EuroSys 2012 Conference


Other7th ACM European Conference on ComputerSystems, EuroSys'12

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Electrical and Electronic Engineering


  • Fairness
  • Multicore
  • Time sharing
  • Work stealing


Dive into the research topics of 'BWS: Balanced work stealing for time-sharing multicores'. Together they form a unique fingerprint.

Cite this