"BWS: Balanced Work Stealing for time-sharing multicores",  

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

Proceedings of ACM EuroSys'12, Bern, Switzerland, April 10-13, 2012.  


Abstract

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
multicoretheir 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 stateof-
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%.


BWS is open source software.