Я думаю, что ответ n=7. Я попытаюсь продемонстрировать, что что-то пойдет не так с n=7; но это дает только верхнюю границу. Что может пойти не так с n=6? Я так не думаю, но я не уверен.
Верхняя граница
Предположим, что у нас есть следующие процессы для планирования:
[1] (т. е. процесс выполняется в течение единицы времени 1)[2][4][5][1,2,3] (т. е. процесс выполняется в течение единиц времени с 1 по 3)[2,3,4][3,4,5]
Для оптимального распределения требуется три процессора:
[1], [2,3,4][2], [3,4,5][1,2,3], [4], [5]
Но жадный алгоритм выдаст следующее:
[1], [2], [4], [5][1,2,3][2,3,4][3,4,5]
Ключевым моментом здесь является то, что он запланирует четыре на первом шаге (потому что он жадный), а затем после этого у нас останется три попарно перекрывающихся процесса.
Нижняя граница
Что может пойти не так с n=6? Я так не думаю, но я не уверен. Мне кажется, что уместным будет случай, когда оптимальное решение требует трех процессоров, каждый из которых запускает два процесса. Можем ли мы найти случай, когда жадный алгоритм планирует три на первом процессоре, а затем остается с тремя перекрывающимися процессами, что требует всего четырех процессоров?
Нам понадобится три пары для оптимального решения; но нам нужно, чтобы эти процессы были построены таким образом, что если вы запланируете три из них на первом шаге, вы не сможете выполнить их за два шага. Ясно, что эти три процесса не могут включать одну из пар, иначе решение может продолжаться так же, как и с парами, но оставить одну из них как одиночку. Поэтому он должен взять по одному из каждой пары.
Если бы процесс мог потребовать несмежных блоков времени, мы могли бы сделать это следующим образом:
[1][2][3][1,2][2,3][1,3] (это не разрешено, т.к. останавливается и запускается заново!)
Оптимальное решение будет сочетать каждый синглтон с его дополнением; жадный алгоритм на первом шаге объединит все одиночки, а затем попарно перекрывающиеся процессы, которые у нас остались, потребуют еще трех процессоров. Но мы обманули, потому что последний из перечисленных выше процессов не выполняется в течение непрерывного временного блока.
Мы не можем изменить последний на [3,4], потому что тогда его можно будет запустить на том же процессоре, что и [1,2]. Фактически, у нас не может быть трех попарно перекрывающихся смежных блоков, если только их пересечение не пусто. Таким образом, мы получим что-то вроде [1,2,3], [2,3,4], [3,4,5], как в случае с семью процессами. Проблема в том, что в таком случае кажется невозможным добавить еще три процесса, которые можно планировать вместе, и при этом обеспечить оптимальное решение для трех процессоров, не допуская возможности планирования двух одиночек с одной из троек. Если мы попробуем
[1][2][4][1,2,3][2,3,4][3,4,5]
тогда жадный алгоритм может запланировать [1], [2], [3,4,5] на первый шаг, что приведет к оптимальному решению (и мы ищем случай, когда недетерминизм гарантирован< /em> привести к неоптимальному решению).
Если мы попробуем
[2][3][4][1,2,3][2,3,4][3,4,5]
то у нас нет оптимального решения на трех процессорах, потому что четырем процессам требуется единица времени 3.
Все эти размышления наводят меня на мысль, что жадный алгоритм будет оптимален в случае n=6, и поэтому верхняя граница n=7 является строгой; но это довольно далеко от доказательства. Как мы можем доказать, что он всегда оптимален для n=6?
person
chiastic-security
schedule
18.10.2014
