Во-первых, обратите внимание, что «потоки», упомянутые на слайдах, не похожи на потоки ОС, как можно подумать.Их определение нити приведено на слайде 10: "a maximal sequence of instructions not containing parallel control (spawn, sync, return)".Чтобы избежать дальнейшей путаницы, позвольте мне вместо этого назвать ее задачей.
На слайдах 32-35 кружок представляет задачу («нить»), а ребра представляют зависимости между задачами.И предложения, о которых вы спрашиваете, на самом деле являются определениями: когда P или более задач готовы к выполнению (и поэтому все P-процессоры могут быть заняты выполнением некоторой работы), ситуация называется полным шагом, в то время как если готово меньше P-задачСитуация называется неполным шагом.Чтобы упростить анализ, предполагается (неявно), что все задачи содержат одинаковую работу (размером 1).
Тогда теорема на слайде 35 предоставляет верхнюю границу времени, необходимого для запуска жадного планировщика.программа.Поскольку все выполнение представляет собой последовательность завершенных и неполных шагов, время выполнения является суммой всех шагов.Поскольку каждый завершенный шаг выполняет ровно P работу, количество завершенных шагов не может быть больше, чем T1 (общая работа), деленное на P. Затем каждый незавершенный шаг должен выполнить задачу, принадлежащую критическому пути (поскольку на каждом шаге по крайней мере один критическийзадача пути должна быть готова, а незавершенные шаги выполнить все готовые задачи);поэтому общее количество незавершенных шагов не превышает промежуток T_inf (критическая длина пути).Таким образом, сумма T1 / P и T_inf дает верхнюю границу времени выполнения.
Остальные слайды в разделе «Теория планирования» довольно просты.