Towards achieving fairness in the Linux scheduler

Chee Siang Wong, Ian Tan, Rosalind Deena Kumari, Fun Wey

Research output: Contribution to journalArticleResearchpeer-review

45 Citations (Scopus)

Abstract

The Operating System scheduler is designed to allocate the CPU resources appropriately to all processes. The Linux Completely Fair Scheduler (CFS) design ensures fairness among tasks using the thread fair scheduling algorithm. This algorithm ensures allocation of resources based on the number of threads in the system and not within executing programs. This can lead to fairness issue in a multi-threaded environment as the Linux scheduler tends to favor programs with higher number of threads. We illustrate the issue of fairness through experimental evaluation thus exposing the weakness of the current allocation scheme where software developers could take advantage by spawning many additional threads in order to obtain more CPU resources. A novel algorithm is proposed as a solution towards achieving better fairness in the Linux scheduler. The algorithm is based on weight readjustment of the threads created in the same process to significantly reduce the unfair allocation of CPU resources in multi-threaded environments. The algorithm was implemented and evaluated. It demonstrated promising results towards solving the raised fairness issue. We conclude this paper highlighting the limitations of the proposed approach and the future work in the stated direction.

Original languageEnglish
Pages (from-to)34-43
Number of pages10
JournalOperating Systems Review
Volume42
Issue number5
DOIs
Publication statusPublished - 1 Jul 2008
Externally publishedYes

Keywords

  • Completely fair scheduler
  • Fairness
  • Linux
  • Process scheduling

Cite this