Введение

Справедливое распределение ресурсов — это алгоритм планирования для компьютерных операционных систем, в котором время процессора распределяется равномерно между пользователями системы или группами, в отличие от равномерного распределения ресурсов между процессами. Один из распространенных методов логической реализации стратегии справедливого распределения заключается в рекурсивном применении стратегии планирования методом циклического перебора (round robin) на каждом уровне абстракции (процессы, пользователи, группы и т. д.). Квант времени, необходимый для циклического перебора, произволен, поскольку любое равное разделение времени даст одинаковые результаты. Впервые этот алгоритм был разработан Джуди Кей и Пирсом Лаудером в ходе их исследований в Сиднейском университете в 1980-х годах. Например, если четыре пользователя (A, B, C, D) одновременно выполняют по одному процессу, планировщик логически разделит доступные циклы процессора таким образом, что каждый пользователь получит 25% от общего времени (100% / 4 = 25%). Если пользователь B запустит второй процесс, каждый пользователь по-прежнему будет получать 25% от общего количества циклов, но каждому из процессов пользователя B теперь будет выделено 12,5% от общего времени процессора, что в сумме составляет справедливую долю пользователя B в 25%. С другой стороны, если новый пользователь запустит процесс в системе, планировщик перераспределит доступные циклы процессора таким образом, чтобы каждый пользователь получал 20% от общего времени (100% / 5 = 20%). Другой уровень абстракции позволяет разделить пользователей на группы и применить алгоритм справедливого распределения и к группам. В этом случае доступные циклы процессора сначала делятся между группами, затем между пользователями внутри групп, а затем между процессами каждого пользователя. Например, если есть три группы (1, 2, 3), содержащие три, два и четыре пользователя соответственно, доступные циклы процессора будут распределены следующим образом:

100% / 3 группы = 33,3% на группу
Группа 1: (33,3% / 3 пользователя) = 11,1% на пользователя
Группа 2: (33,3% / 2 пользователя) = 16,7% на пользователя
Группа 3: (33,3% / 4 пользователя) = 8,3% на пользователя