Многие модели стоимости алгоритма (см. Третье издание Кормена, гл. 27) утверждают,
что планировщики все одинаковы, и, следовательно, в основном постоянная
порядок некоторых алгоритмов.
Простой ответ - да.
Контекст, в котором это было сказано в CLRS, заключался в измерении производительности многопоточных алгоритмов. Наиболее очевидным примером такой меры является ускорение , достигаемое с помощью параллельного / многопоточного алгоритма. Работа планировщика ОС, особенно в многопроцессорной среде, заключается в том, чтобы все процессоры выполняли значительную долю всей работы, если это вообще возможно, для максимизации общей производительности. Неважно, какой алгоритм планирования используется ОС. Потому что, если есть свободный процессор и есть работа, которую нужно выполнить, планировщик ОС всегда назначит некоторую работу.
Давайте рассмотрим пример. X - это общая работа, которую нужно выполнить (предположим, что она очень большая, как генные вычисления, так что места для параллелизма достаточно), у вас есть 5 процессоров. Вы написали алгоритм, который разбивает всю работу на 5 почти равных патронов. Предположим, что блоки независимы, и измеренное ускорение равно 3,5 (это не 5 из-за дополнительных затрат на создание потоков, переключение контекста и некоторые коммуникации и т. Д.)
Обратите внимание, что когда вы измеряете ускорение параллельного алгоритма, вы всегда будете измерять его, следя за тем, чтобы никакие другие задачи не выполнялись отдельно от ваших параллельных задач. Нетрудно видеть, что ускорение, достигаемое параллельным алгоритмом, будет почти таким же, так как алгоритмы планирования ОС практически не имеют здесь никакого значения. Поэтому, независимо от планировщика ОС, вы всегда будете получать ускорение, почти аналогичное 3,5 в этом примере.
Не будет ли никакого значения в использовании планировщика O (1) по сравнению с планировщиком CFS?
Да, для измерения производительности параллельного / многопоточного алгоритма .
Цель простого параллельного алгоритма (каким бы трудным на самом деле ни было его достижение) - оптимально разделить работу, чтобы все процессоры работали над выполнением задачи. Разумно предположить, что все ваши (параллельные задачи) потоки одинаковы, если вы не сделаете что-то, чтобы сделать это иначе.
Но задача планировщика ОС в общем случае более сложная. Потому что всегда будет много процессов, работающих с разными приоритетами в одно и то же время, и разное время выполнения и т. Д. Именно в этом контексте в игру вступают алгоритмы планировщика ОС. как они решают, какую задачу выполнять дальше. И исходя из разных потребностей и симпатий разных людей, у нас есть много алгоритмов планирования ОС.
Следует отметить, что производительность параллельного алгоритма может варьироваться в зависимости от планировщика ОС при запуске со многими другими задачами с разными приоритетами. Пусть ваша задача - это T, которая разбита на t1, t2, t3, t4 и t5. Предположим, что другие задачи, которые планировщик выполняет в своей очереди: t12, t25, t99, t75, t60 (здесь я использовал несколько случайных идентификаторов). Тогда общее время выполнения вашей задачи T зависит от того, как планировщик ОС планирует все эти задачи. Так что если одна из ваших задач, скажем, t4, запланирована наконец после выполнения всех остальных (t1, t2, t3, t5, t12, t25, t99, t75 и t60), то вы получите другое время выполнения. И вы получите различное время выполнения в зависимости от того, когда все ваши задачи запланированы и выполнены. В этом контексте алгоритм планирования ОС не влияет на фактическое время выполнения.