Towards achieving fairness in the Linux scheduler

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

Research output: Contribution to journalArticlepeer-review

51 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
JournalACM SIGOPS Operating Systems Review
Volume42
Issue number5
DOIs
Publication statusPublished - 1 Jul 2008

Keywords

  • Completely fair scheduler
  • Fairness
  • Linux
  • Process scheduling

ASJC Scopus subject areas

  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Towards achieving fairness in the Linux scheduler'. Together they form a unique fingerprint.

Cite this