КП (954317), страница 8
Текст из файла (страница 8)
Выполним оценку на примере варианта:
{БД1/ у1, БД4/у1, БД5/у1, БД7/у5, БД8/у5, БД9/у1}
Количественное значение оценки i-го варианта обозначим через Si.
В нашем примере - “S1”:
S1= S1.у2 + S1.у3 + S1.у4 + S1.у5 + S1.у6 + S1.у7 = 12067
где:
--------------------------------------------------------------------------------------------------------------------------------
S1.у2 = S1.у2.п2+ S1.у2.п4+ S1.у2.п10 = 475 + 660 + 522.5 = 1486,5;
S1.у2.п2 = S1.у2.п2.БД2 + S1.у2.п2.БД3 + S1.у2.п2.БД8 = 400 * 0,5 + 300 * 0,5 + 250 * 0,5 = 475;
S1.у2.п4 = S1.у2.п4.БД2 + S1.у2.п4.БД3 + S1.у2.п4.БД6 = 300 * 1,2 + 150 * 1,2 + 100 * 1,2 = 660;
S1.у2.п10 = S1.у2.п10.БД3 + S1.у2.п10.БД5 + S1.у2.п10.БД9 = 240 * 0,95 + 90 * 0,95 + 40 * 0,95 = 522.5;
---------------------------------------------------------------------------------------------------------------------------------
S1.у3 = S1.у3.п1 + S1.у3.п3 + S1.у3.п4 + S1.у3.п10 = 585+ 1060.5 + 440 + 259 = 2344.5;
S1.у3.п1 = S1.у3.п1.БД1 + S1.у3.п1.БД4 + S1.у3.п1.БД6 + S1.у3.п1.БД10 =
= 100 * 1,3 + 60 * 1,3 + 150* 1,3 + 140 * 1,3 = 585;
S1.у3.п3 = S1.у3.п3.БД1+S1.у3.п3.БД3+S1.у3.п4.БД5+S1.у3.п4.БД7 + S1.у3.п4.БД9 + S1.у3.п4.БД10 =
= 30 * 1,05 + 300 * 1,05 + 80 * 1,05 + 400 * 1,05 + 20 * 1,05 + 180 * 1,05 = 1060.5;
S1.у3.п4 = S1.у3.п4.БД2 + S1.у3.п4.БД3 + S1.у3.п4.БД6 =
= 300 * 0,8 + 150 * 0,8 + 100 * 0,8 = 440;
S1.у3.п10 = S1.у3.п10.БД3 + S1.у3.п10.БД5 + S1.у3.п10.БД9 =
=240 * 0,7 + 90 * 0,7 + 40 * 0,7 = 259;
--------------------------------------------------------------------------------------------------------------------------------
S1.у4 = S1.у4.п1 + S1.у4.п2 + S1.у4.п3 + S1.у4.п4 + S1.у4.п10 = 391.5 + 600 + 909 + 605 + 296 = 2961.5;
S1.у4.п1 = S1.у4.п1.БД1 + S1.у4.п1.БД4 + S1.у4.п1.БД6 + S1.у4.п1.БД10 =
= 100 * 0,87 + 60 * 0,87 + 150 * 0,87 + 140 * 0,87 = 391.5
S1.у4.п2 = S1.у4.п2.БД2 + S1.у4.п2.БД3 + S1.у4.п2.БД8 =
= 400 * 0,8 + 300 * 0,8 + 250 * 0,8 = 600
S1.у4.п3= S1.у4.п3.БД1+S1.у4.п3.БД3 + S1.у4.п3.БД5 + S1.у4.п3.БД7 + S1.у4.п3.БД9 + S1.у4.п3.БД10=
= 30 * 0,9 + 300 * 0,9 + 80 * 0,9 + 400 * 0,9 + 20 * 0,9 + 180 * 0,9 = 909
S1.у4.п4 = S1.у4.п4.БД2 + S1.у4.п4.БД3 + S1.у4.п4.БД6 =
= 300 * 1,1 + 150 * 1,1 + 100 * 1,1 = 605
S1.у4.п10 = S1.у4.п10.БД3 + S1.у4.п10.БД5 + S1.у4.п10.БД9 =
= 240 * 0,8 + 90 * 0,8 + 40 * 0,8 = 296
------------------------------------------------------------------------------------------------------------------------------------
S1.у5 = S1.у5.п3 = 1313;
S1.у5.п3 = S1.у5.п3.БД1 + S1.у5.п3.БД3 + S1.у5.п3.БД5 + S1.у5.п3.БД7+S1.у5.п3.БД9+S1.у5.п3.БД10 =
= 30 *1,3 + 300 *1,3 + 80 *1,3 + 400 *1,3 + 20 *1,3 + 180 *1,3 = 1313
S1.у6 = S1.у6.п1 + S1.у6.п2 + S1.у6.п10=1604
S1.у6.п1 = S1.у6.п1.БД1 + S1.у6.п1.БД4 + S1.у6.п1.БД6 + S1.у6.п1.БД10 =
= 100 *1,3 + 60 *1,3 + 150 *1,3 + 140 *1,3 = 585
S1.у6.п2 = S1.у6.п2.БД2 + S1.у6.п2.БД3 + S1.у6.п2.БД8 =
= 400 *0,8 + 300 *0,8 + 250 *0,8 = 760
S1.у6.п10 = S1.у6.п2.БД3 + S1.у6.п2.БД5 + S1.у6.п2.БД9 =
240 *0,7 + 90 *0,7 + 40 *0,7 =259
-------------------------------------------------------------------------------------------------------------------------------
S1.у7 = S1.у7.п2 + S1.у7.п3 + S1.у7.п4 + S1.у7.п10 = 2357,5
S1.у7.п2 = S1.у7.п2.БД2 + S1.у7.п2.БД3 + S1.у7.п2.БД8 =
= 400 *0,6 + 300 *0,6 + 250 *0,6 =570
S1.у7.п3 = S1.у7.п3.БД1 + S1.у7.п3.БД3 + S1.у7.п3.БД5+S1.у7.п3.БД7+S1.у7.п3.БД9 + S1.у7.п3.БД10 =
= 30 *0,95 + 300 *0,95 + 80 *0,95 + 400 *0,95 + 20 *0,95 + 180 *0,95 = 959,5
S1.у7.п4 = S1.у7.п4.БД2 + S1.у7.п4.БД3 + S1.у7.п4.БД6 =
= 300 *0,9 + 150 *0,9 + 100 *0,9 = 495
S1.у7.п10 = S1.у7.п10.БД3 + S1.у7.п10.БД5 + S1.у7.п10.БД9 =
= 240*0,9 + 90 *0,9 + 40 *0,9 = 333
Таким образом оценочная функция варианта распределения баз данных по узлам носит аддитивный характер.
Выбор метода решения:
Данная задача нахождения оптимального варианта является комбинаторной задачей распределения, однако учитывая аддитивный характер оценочной функции ее можно рашить не только методом полного перебора (что практически крайне затруднительно), но также методом динамического программирования, например методом ветвей и границ:
минимизировать S=f(x) при условиях x (- G, где G - полное (конечное) множество вариантов.
Решение задачи
Составляем таблицу 26 , в которой указываем все возможные варианты: размещения баз данных по узлам сети. В каждую клетку этой таблицы записываем число, которое определяет суммарное количество всех запросов от всех процессов всех узлов к данной БД, при условии, что эта БД находится в данном узле..
Таблица 26. Суммарное количество обращений к БД при возможных вариантах их размещения по узлам сети
| Узел | БД1 | БД2 | БД3 | БД4 | БД5 | БД6 | БД7 | БД8 | БД9 | БД10 |
| У2 | 347 | 1418 | 1659 | 208 | 449 | 965 | 600 | 660 | 184 | 485 |
| У3 | 217 | 1345 | 1616 | 130 | 404 | 755 | 360 | 440 | 170 | 303 |
| У4 | 130 | 1273 | 1562 | 78 | 463 | 600 | 600 | 460 | 190 | 182 |
| У6 | 217 | 1568 | 1721 | 130 | 472 | 830 | 600 | 420 | 194 | 303 |
| У7 | 347 | 1508 | 1718 | 208 | 352 | 995 | 240 | 660 | 150 | 485 |
| Min обр к БД | 130 | 1273 | 1562 | 78 | 352 | 600 | 240 | 420 | 150 | 182 |
| Max обр к БД | 347 | 1568 | 1721 | 208 | 472 | 995 | 600 | 660 | 194 | 485 |
Используем правило: «Базу данных помещаем в тот узел, где она максимально используется, т.е. суммарное количество обращений к ней со стороны других узлов минимально» Поэтому в каждом столбце, соответствующем одной конкретной БД, отыскиваем наименьшее значение. Это и будет соответствовать оптимальному варианту размещения этой БД, поскольку .чем меньше это значение, тем меньше суммарное количество обращений от всех процессов всех других узлов к данной БД.
Полученные результаты, показывающие оптимальные варианты размещения БД по узлам сети, записываем в таблицу 27
Таблица 27. Оптимальные варианты размещении БД по узлам сети
| БД1 | БД2 | БД3 | БД4 | БД5 | БД6 | БД7 | БД8 | БД9 | БД10 | Оценка варианта | |
| Вар.1 | У4 | У4 | У4 | У4 | У7 | У4 | У7 | У6 | У7 | У2 | 4987 |
| Вар.2 | У4 | У4 | У4 | У4 | У7 | У4 | У7 | У6 | У7 | У7 | 4987 |
| Число обращений | 130 | 1273 | 1562 | 78 | 352 | 600 | 240 | 420 | 150 | 182 |
Итак, получили, что в каждом из всех оптимальных вариантов размещения БД по узлам сети, суммарное количество обращений ко всем БД, т.е. суммарные затраты, составляют 4987
.
-
Распределение баз данных по узлам сети с учетом репликаций
Необходимо определить вариант рационального размещения предметных баз данных в распределенной информационной системе для случая, когда каждая база данных может иметь произвольное число репликаций (копий), размещаемых на любых узлах (размещается только в одном узле сети главная репликация мастер-репликация). Обрабатывающие процессы (приложения) не являются распределенными. При этом считать, что если некоторый процесс обращается за данными к базе, находящейся в другом узле, сетевые затраты на одно обращение составляют “t” секунд, независимо от местонахождения узла в сети и дисциплины обслуживания. Если процесс обращается к базе данных, находящейся в том же узле, где выполняется процесс, то считать, что “t = 0”.
На создание и поддержку репликаций средние приведенные затраты назначаем согласно следующей формуле:
где N значение из таблицы 23;
k значение коэффициента из таблицы 24;
N2 исходное значение затрат на создание и поддержку репликаций БД, соответствующее варианту задания.
Рассчитанные значения N2 приведены в таблице 28
Таблица 28. Исходные данные для варианта с репликациями
| Узел | Коэф | Проц. | БД1 | БД2 | БД3 | БД4 | БД5 | БД6 | БД7 | БД8 | БД9 | БД10 |
| У2 | 1,2 | П4 | 0 | 75 | 38 | 0 | 0 | 25 | 0 | 0 | 0 | 0 |
| 0,96 | П10 | 0 | 0 | 75 | 0 | 28 | 0 | 0 | 0 | 13 | 0 | |
| У3 | 1,3 | П1 | 23 | 0 | 0 | 14 | 0 | 35 | 0 | 0 | 0 | 32 |
| 0,8 | П4 | 0 | 113 | 56 | 0 | 0 | 38 | 0 | 0 | 0 | 0 | |
| 0,8 | П5 | 0 | 0 | 0 | 0 | 32 | 0 | 113 | 0 | 11 | 0 | |
| 0,55 | П9 | 0 | 191 | 164 | 0 | 0 | 55 | 0 | 218 | 0 | 0 | |
| 0,7 | П10 | 0 | 0 | 103 | 0 | 39 | 0 | 0 | 0 | 17 | 0 | |
| У4 | 0,87 | П1 | 34 | 0 | 0 | 21 | 0 | 52 | 0 | 0 | 0 | 48 |
| 1,1 | П4 | 0 | 82 | 41 | 0 | 0 | 27 | 0 | 0 | 0 | 0 | |
| 0,5 | П9 | 0 | 210 | 180 | 0 | 0 | 60 | 0 | 240 | 0 | 0 | |
| 0,8 | П10 | 0 | 0 | 90 | 0 | 34 | 0 | 0 | 0 | 15 | 0 | |
| У6 | 1,3 | П1 | 23 | 0 | 0 | 14 | 0 | 35 | 0 | 0 | 0 | 32 |
| 0,6 | П9 | 0 | 175 | 150 | 0 | 0 | 50 | 0 | 200 | 0 | 0 | |
| 0,7 | П10 | 0 | 0 | 103 | 0 | 39 | 0 | 0 | 0 | 17 | 0 | |
| У7 | 0,9 | П4 | 0 | 100 | 50 | 0 | 0 | 33 | 0 | 0 | 0 | 0 |
| 1,2 | П5 | 0 | 0 | 0 | 0 | 21 | 0 | 75 | 0 | 8 | 0 | |
| 0,9 | П10 | 0 | 0 | 80 | 0 | 30 | 0 | 0 | 0 | 13 | 0 |
Сгруппируем данные по процессам одного узлам, отнесенные к одной и той же БД так, чтобы в каждой клетке новой таблицы 29 было число, равное приведенным затратам на создание и поддержку репликации БД при помещении ее в этот узел
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
