GVTS: Global Virtual Time Fair Scheduling to Support Strict Fairness on Many Cores

Cited 1 time in webofscience Cited 1 time in scopus
  • Hit : 410
  • Download : 86
Proportional fairness in CPU scheduling has been widely adopted to fairly distribute CPU shares corresponding to their weights. With the emergence of cloud environments, the proportionally fair scheduling has been extended to groups of threads or nested groups to support virtual machines or containers. Such proportional fairness has been supported by popular schedulers, such as Linux Completely Fair Scheduler (CFS) through virtual time scheduling. However, CFS, with a distributed runqueue per CPU, implements the virtual time scheduling locally. Across different queues, the virtual times of threads are not strictly maintained to avoid potential scalability bottlenecks. The uneven fluctuation of CPU shares caused by the limitations of CFS not only violates the fairness support for CPU assignments, but also significantly increases the tail latencies of latency-sensitive applications. To mitigate the limitations of CFS, this paper proposes a global virtual-time fair scheduler (GVTS), which enforces global virtual time fairness for threads and thread groups, even if they run across many physical cores. The new scheduler employs the hierarchical enforcement of target virtual time to enhance the scalability of schedulers, which is aware of the topology of CPU organization. We implemented GVTS in Linux kernel 4.6.4 with several optimizations to provide global virtual time efficiently. Our experimental results show that GVTS can almost eliminate the fairness violation of CFS for both non-grouped and grouped executions. Furthermore, GVTS can curtail the tail latency when latency-sensitive applications are co-running with batch tasks.
Publisher
IEEE COMPUTER SOC
Issue Date
2019-01
Language
English
Article Type
Article
Citation

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, v.30, no.1, pp.79 - 92

ISSN
1045-9219
DOI
10.1109/TPDS.2018.2851515
URI
http://hdl.handle.net/10203/249792
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
000453533400007.pdf(1.69 MB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0