Постановка задачи оптимизации обслуживания многоочередных структур данных
Множество вершин (вторая доля), соответствующих множеству заявок (потоков). U — множество ребер, связывающих вершины множества E с вершинами множества W. Конкретное решение задачи распределения заявок представляется в виде подграфа. Таким образом, загрузка Rli заявками процессора ei с учетом времени переключения между соседними заявками в очереди Pli, а также времени rij непрерывного… Читать ещё >
Постановка задачи оптимизации обслуживания многоочередных структур данных (реферат, курсовая, диплом, контрольная)
Пусть МВС состоит из n идентичных, параллельно работающих процессоров.
E={ei|i=1,2,…, n}.
На вход МВС поступает множество m независимых программ.
W={wj|j=1,2,…, m},.
которые требуется распределить между процессорами. Если время rj непрерывного использования процессора для выполнения каждой программы wj, одинаково для всех процессоров, то множеству W сопоставляется множество.
R={rj|j=1,2,…, m}.
l-м решением задачи планирования в этом случае является множество.
Vl={Wli|i=1,2,…, n},.
где Wli подмножество программ, выполняемых на процессоре ei:
(i, j)[((ij)&(WliVl)&(WljVl))>((WliWlj =)&(Wli= W))]. (1).
Запланированная вариантом решения Vl загрузка программами каждого процессора ei оценивается ресурсом:
Rli =rk; где rk |wk Wli. (2).
Если производительность процессоров различна, то задается время rij непрерывного использования процессора ei для выполнения программы wj. Таким образом, множествам E и W сопоставляется множество R={rij| i=1,2,…, n; j=1,2,…, m}. В этом случае формула (2) примет вид:
Rli =rik, где k|wk Wli. (3).
Представим некоторую очередь программ, поступающих на процессор ei в виде списка.
Pli=p1,p2,p3,…, ps,…, pm.,.
где ps это индекс программы, у которой порядковый номер в очереди Pli равен s.
Загрузка программами каждого процессора, рассчитываемая по формулам (2) или (3), не учитывает время переключения между различными заявками. Отметим, что время переключения для каждой пары соседних заявок в очереди имеет свое значение.
Продолжительность переключения между соседними в очереди заявками, поступающими на обслуживающий прибор ei, задается матрицей переключений.
Тi=||tk, s||mm.
Таблица № 1 Матрица переключений Тi.
*. | t12. | t13. | t14. | t15. | |
t21. | *. | t23. | t24. | t25. | |
t31. | t32. | *. | t34. | t35. | |
t41. | t42. | t43. | *. | t45. | |
t51. | t52. | t53. | t54. | *. | |
tk, s — время переключения между соседними в очереди заявками (wk, ws).
Очередь заявок, поступающих на обслуживающий прибор, с учетом времени переключения между различными соседними заявками примет вид:
Pli = p1, t12, p2, t23, p3, ,…, ps, ts, s+1, ps+1 ,…, pm-1, tm-1,m, pm.
Здесь ts, s+1 — время переключения между соседними в очереди Pli программами с порядковыми номерами s и s+1.
Общее время Tli переключения между заявками, поступающими на вход обслуживающего прибора ei, определится как сумма переключений:
Tli =tk-1,k, где k| tk-1,k Pli. (4).
Таким образом, загрузка Rli заявками процессора ei с учетом времени переключения между соседними заявками в очереди Pli, а также времени rij непрерывного использования процессора ei для выполнения каждой программы wj Wli определится как:
Rli =Tli +rik, где k|wk Wli (5).
Для обеспечения максимальной эффективности использования существующих ресурсов необходимо упорядочить очередь заявок в каждом списке Pli. Будем считать, что.
Pl={Pli|i=1,2,…, n} ;
множество упорядоченных списков, задающих очередность обработки заявок на обслуживающих приборах.
В этом случае решением Zl задачи распределения заявок между обслуживающими приборами является совокупность двух множеств Vl и Pl, т. е.
Zl=(Vl; Pl).
В качестве оценки решения Zl рассматривается величина:
Fl=max (Rli). i.
Наиболее распространённым критерием оптимизации при планировании в случае многоуровневой очереди является «минимаксный» критерий:
F=min Fl = min max (Rli). l l i.
Это связано с тем, что в большинстве реальных задач при планировании чаще всего требует решения задача уменьшения времени выполнения всех заявок. Поскольку, чем быстрее СМО обслуживает поступающие заявки, тем выше ее производительность, а значит, и выше экономическая эффективность предприятия, использующего данную систему.
Для отображения распределения заявок по обслуживающим приборам используется полный двудольный граф.
Hnm=(EW, U), где E={ei|i=1,2,…, n}.
— множество вершин (первая доля), соответствующих множеству обслуживающих приборов, а.
W={wj|j=1,2,…, m} ;
множество вершин (вторая доля), соответствующих множеству заявок (потоков). U — множество ребер, связывающих вершины множества E с вершинами множества W. Конкретное решение задачи распределения заявок представляется в виде подграфа.
Hl=(EW, Ul). HlHnm, UlU.
Вершина wjW связана с вершиной eiE в том и только в том случае, когда wj назначена в ei. Пусть Uli множество ребер двудольного графа Hl, связывающих вершину ei с вершинами множества Wli.
Uli=Ul.
Для наглядности представления конкретного распределения заявок (рис. 1) множество заданий W сгруппировано в подмножества Wli, где Wliподмножество заявок, поступающих на обслуживающий прибор ei.
Отличительной особенностью представленного двудольного графа.
Hl=(EW, Ul).
является то, что число ребер множества Uli равно числу вершин множества Wli. Каждое ребро uzUli, с одной стороны, инцидентно вершине ei, а с другой стороны, инцидентно одной и только вершине wkWli.
Назовем двудольный граф, представляющий распределение заявок, граф — распределением Hl. Отметим, что в графе — распределении Hl локальная степень любой вершины wjW равна единице, а локальная степень вершины ei равна мощности множества Wli, т. е.
с (wj)=1, с (ei)= |Wli|.
Таким образом, поиск распределение заявок сводится к поиску на полном двудольном графе Hnm подграфа Hl.
Рис. 1 Интерпретация распределения программ в МВС