Hardprob/Minimum Preemptive Scheduling With Set-Up Times — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена PCRE <m>(\w)_(\w),\s*…\s*,\s*(\w)_(\w)<\/m> на <em>\1<sub>\2</sub>, …, \3<sub>\4</sub></em>)
(Массовая правка: замена PCRE <m>(\w)_(\w)('*)</m> на <em>\1<sub>\2</sub>\3</em>)
Строка 7: Строка 7:
 
*** <m>σ_2(t_{i+1}) ≥  σ_2(t_i) + l(t_i), \ \ 1 ≤i < k</m>
 
*** <m>σ_2(t_{i+1}) ≥  σ_2(t_i) + l(t_i), \ \ 1 ≤i < k</m>
 
** Это расписание должно удовлетворять дополнительному ограничению:
 
** Это расписание должно удовлетворять дополнительному ограничению:
*** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и <m>t_j'</m> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то  
+
*** Если два подзадачи <em>t<sub>i</sub></em> от <em>t</em> и <em>t<sub>j</sub>'</em> от <em>t'</em>, у которых <m>σ_2(t_i) < σ_2(t_j')</m> запланированы последовательно на одном процессоре (т.е. <m>σ_1(t_i) = σ_1(t_j')</m>, и нет другой подзадачи <m>t_k"</m>, у которой <m>σ_1(t_k") = σ_1(t_i)</m> и <m>σ_2(t_i) < σ_2(t_k") < σ_2(t_j')</m>, то  
 
**** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>)
 
**** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если у них один и тот же компилятор (<em>c(t) = c(t')</em>)
 
**** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные.
 
**** <m>σ_2(t_j') ≥  σ_2(t_i) + l(t_i) + s(c(t'))</m> — если эти компиляторы разные.

Версия 23:13, 17 апреля 2023

  • Набор компиляторов C, набор задач T, m процессоров, длительности задач , нужный для задачи компилятор , время запуска-настройки для каждого компилятора .
  • Найти m-процессорное вытесняющее расписание T, т.е. для каждой для каждой задачи t ∈ T, разбиение t на какое-то количество подзадач t1, …, tk, такое что
    • и есть некоторое назначение , которое назначает каждой подзадаче ti пару неотрицательных целых , таких, что
    • Это расписание должно удовлетворять дополнительному ограничению:
      • Если два подзадачи ti от t и tj' от t', у которых запланированы последовательно на одном процессоре (т.е. , и нет другой подзадачи , у которой и , то
        • — если у них один и тот же компилятор (c(t) = c(t'))
        • — если эти компиляторы разные.
  • Минимизировать общее время выполнения, т.е. максимум по всем подзадачам

Задача в лаб22 (рид-онли просмотр)