Lottery scheduler for the Linux kernel



Document title: Lottery scheduler for the Linux kernel
Journal: Dyna (Medellín)
Database:
System number: 000537769
ISSN: 0012-7353
Authors: 1
2
3
Institutions: 1Universidad de Caldas, Manizales. Colombia
2Universidad de Caldas, Departamento de Sistemas e Informática, Manizales. Colombia
3University of Arizona, Department of Computer Science, Tucson. Estados Unidos
Year:
Season: Ene-Feb
Volumen: 82
Number: 189
Pages: 216-225
Country: Colombia
Language: Inglés
Spanish abstract Este artículo describe el diseño e implementación del planificador Lotería en el núcleo de Linux, este planificador es un algoritmo de administración de proporción igual de recursos, Una nueva clase, el planificador Lotería (Lottery scheduler), fue adicionado al núcleo y ubicado entre la clase de tiempo-real y la clase de planificador completamente equitativo (Complete Fair scheduler-CFS) en la jerarquía de los módulos planificadores. Este trabajo evalúa el planificador propuesto en computación intensiva, entrada-salida intensiva y cargas de trabajo mixtas. Los resultados indican que el planificador de procesos es probabilísticamente equitativo y previene la inanición de procesos. Otra conclusión es que la sobrecarga de la implementación es aproximadamente lineal en el número de procesos que corren.
English abstract This paper describes the design and implementation of Lottery Scheduling, a proportional-share resource management algorithm, on the Linux kernel. A new lottery scheduling class was added to the kernel and was placed between the real-time and the fair scheduling class in the hierarchy of scheduler modules. This work evaluates the scheduler proposed on compute-intensive, I/O-intensive and mixed workloads. The results indicate that the process scheduler is probabilistically fair and prevents starvation. Another conclusion is that the overhead of the implementation is roughly linear in the number of runnable processes.
Keyword: Planificador Lotería,
Planificador de procesos,
Núcleo Linux,
Sistemas operativos
Keyword: Lottery scheduling,
Schedulers,
Linux kernel,
Operating system
Full text: Texto completo (Ver HTML) Texto completo (Ver PDF)