|
где п число используемых ресурсов. Имеют место два особых случая для этого результата. 1)Когда/: = О, И0)/%<2-1/л ограничение, разработанное для общей начальной границы при п п 2) Если к = 2п, W(2n)/W0<4/3-l/3-n. Таким образом, предыдущие два результата были частными случаями. Обратимся еще раз к алгоритмам наидлиннейшего пути, которые достаточно полно были исследованы Кауфманом для графов с древовидной структурой. В этом случае при формировании распределенных процессов считается, что допускаются неравные длительности задач, но не разрешены приоритетные прерывания. Традиционно задачи с весами больше единицы представляются в виде строки задач с единичным весом, чья сумма равна весу изначальной задачи. Такое представление графа позволяет определять оптимальное неприоритетное решение, используя опять-таки алгоритм Хью, так как граф является деревом, хотя алгоритм наидлиннейшего пути Кауфмана [13] или G-алгоритм и не позволяет прерывать ресурс до завершения задачи, если эта задача является членом строки задач, представляющей задачу неединичного веса. Если Wp оптимальный приоритетный план, Wn оптимальный неприоритетный план, a план, полученный с помощью G-алгоритма, то ограничения Кауфмана могут быть определены как Wp На основании результатов моделирования в реальных средах реализации распределенных процессов проведено сравнение 60 |
w{G}/WQ<2-\/n ограничение, разработанное для общей начальной границы при п = п \ 2) Если к = 2п, W(2n)IWQ<4l3-\/3-n. Таким образом, предыдущие два результата были частными случаями. Обратимся еще раз к алгоритмам наидлиннейшего пути, которые достаточно полно были исследованы Кауфманом для графов с древовидной структурой. В этом случае при формировании распределенных алгоритмов считается, что в вычислительной среде ИУС допускаются неравные длительности задач, но не разрешены приоритетные прерывания. Традиционно задачи с весами больше единицы представляются в виде строки задач с единичным весом, чья сумма равна весу изначальной задачи. Такое представление графа позволяет определять оптимальное неприоритетное решение, используя опять-таки алгоритм Хью, так как граф является деревом, хотя алгоритм наидлиннейшего пути Кауфмана [...] или Gалгоритм и не позволяет прерывать процессор до завершения задачи, если эта задача является членом строки задач, представляющей задачу неединичного веса. Если Wp оптимальный приоритетный план, W„ — оптимальный неприоритетный план, a Wg план, полученный с помощью G-алгоритма, то ограничения Кауфмана могут быть определены как Wp На основании результатов моделирования в реальных средах реализации распределенных алгоритмов (рассмотрены в разделе 4) проведено сравнение производительности нескольких списков планов, сформированных в среде без ограничений. Использовались ниже приведенные пять исследуемых эвристик: 66 |