Towards Efficient Work-Stealing in Virtualized Environments

Work-stealing, as a common user-level task scheduler for managing and scheduling tasks among worker threads, has been widely adopted in multithreaded applications. With work-stealing, worker threads attempt to steal tasks from other threads' queue when they run out of their own tasks. Though work-stealing based applications can achieve good performance due to the dynamic load balancing, these steal attempting operations may frequently fail especially when available tasks are scarce, thus wasting CPU resources of busy worker threads and consequently making work-stealing less efficient in competitive environments, such as traditional multi programmed and virtualized environments. Although there are some optimizations for reducing the cost of steal-attempting threads by having such threads yield their computing resources in traditional multi programmed environments, it is more challenging to enhance the efficiency of work-stealing in virtualized environments due to the semantic gap between the virtual machine monitor (VMM) and virtual machines (VMs). In this paper, we first analyze the challenges of enhancing the efficiency of work-stealing in virtualized environments, and then propose Robin hood, a scheduling framework that reduces the cost of virtual CPUs (vCPUs) running steal-attempting threads and the scheduling delay of vCPUs running busy threads. Different from traditional scheduling methods, if the steal attempting failure occurs, Robin hood can supply the CPU time of vCPUs running steal-attempting threads to their sibling vCPUs running busy threads, which can not only improve the CPU resource utilization but also guarantee better fairness among different VMs sharing the same physical node. We implement Robin hood based on BWS, Linux and Xen. Our evaluation with various benchmarks demonstrates that Robin hood paves a way to efficiently run work-stealing based applications in virtualized platform. It can reduce up to 64% and 30% execution time of work-stealing benchmarks compared to Cilk++ and BWS respectively, and outperform credit scheduler and co-scheduling for average system throughput by 1.91× and 1.3× respectively, while guaranteeing the performance fairness among applications in virtualized environments.