Задания по распределению предметных баз данных по узлам сети.
Задание 1.
Определить вариант рационального размещения предметных баз данных в распределенной информационной системе для случая, когда каждая база данных размещается только в одном узле сети, а обрабатывающие процессы (приложения) не являются распределенными. При этом считать, что если некоторый процесс обращается за данными к базе, находящейся в другом узле, сетевые затраты на одно обращение составляют “t” секунд, независимо от местонахождения узла в сети и дисциплины обслуживания. Если процес обращается к базе данных, находящейся в том же узле, где выполняется и процесс, то считать, что “t=0”.
Исходные данные взять из следующих таблиц:
1. Таблица 1, показывающая использование предметных баз данных обрабатывающими процессами (приложениями) в течение временного интервала и интенсивности их обращений к базам данных (среднее число обращений за рассматриваемый интервал времени):
Таблица 1
| Пр\БД | БД1 | БД2 | БД3 | БД4 | БД5 | БД6 | БД7 | БД8 | БД9 | БД10 |
| П1 | ||||||||||
| П2 | П2 | |||||||||
| П3 | ||||||||||
| П4 | ||||||||||
| П5 | ||||||||||
| П6 | ||||||||||
| П7 | ||||||||||
| П8 | ||||||||||
| П9 | ||||||||||
| П10 |
Таблица 2, показывающая распределение обрабатывающих процессов по узлам:
Таблица 2
| У\П | П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | П9 | П10 | N груп- пы |
| У1 | 1,0 | 1,4 | 1,0 | 0,3 | 0,6 | 0,9 | 1,2,4,5,6,7 | ||||
| У2 | 0,5 | 1,2 | 0,7 | 1,0 | 1.1 | 0,95 | 1,2,3,5,6,7 | ||||
| У3 | 1,3 | 1,05 | 0,8 | 0,8 | 1,15 | 0,55 | 0,7 | 1,2,3,4,6,7 | |||
| У4 | 0,87 | 0,8 | 0,9 | 1,1 | 0,9 | 0,8 | 0,5 | 0,8 | 1,2,3,4,5,7 | ||
| У5 | 1,3 | 1,5 | 1,6 | 1,1 | 0,9 | 1,3,4,5,6,7 | |||||
| У6 | 1,3 | 0,8 | 1,6 | 0,2 | 0,6 | 0,7 | 1,2,3,4,5,6 | ||||
| У7 | 0,6 | 0,95 | 0,9 | 1,2 | 1,4 | 0,7 | 0,9 | 2,3,4,5,6,7 | |||
| N | |||||||||||
| в | |||||||||||
| груп- | |||||||||||
| пе | |||||||||||
| п | |||||||||||
| о | |||||||||||
| с | |||||||||||
| п | |||||||||||
| и | |||||||||||
| с | |||||||||||
| к | |||||||||||
| у | |||||||||||
Коэффициенты в таблице 2 используются для получения количества обращений к базе данных в в исходном варианте задания по формуле:
N1=N*k,
где: N - значение из таблицы 1; k - значение коэффициента из таблицы 2;
N1 - результирующее значение для таблицы учебного варианта задания.
Пример
Например, выбрав из таблиц данные своего варианта, Вы сформировали следующую сводную таблицу исходных данных для Вашей задачи (данные не соответствуют ни одному учебному варианту):
| Узел | Проц. | БД1 | БД4 | БД5 | БД7 | БД8 | БД9 |
| П1 | |||||||
| У1 | П2 | ||||||
| П5 | |||||||
| П7 | |||||||
| П1 | |||||||
| У2 | П4 | ||||||
| П5 | |||||||
| П2 | |||||||
| У3 | П3 | ||||||
| П4 | |||||||
| П5 | |||||||
| П1 | |||||||
| У4 | П6 | ||||||
| П9 | |||||||
| П3 | |||||||
| П6 | |||||||
| У5 | П7 | ||||||
| П8 | |||||||
| П10 | |||||||
| П1 | |||||||
| У6 | П4 | ||||||
| П5 | |||||||
| П10 |
Оценка варианта.
Выполним оценку на примере варианта:
{БД1/ у1, БД4/у1, БД5/у1, БД7/у5, БД8/у5, БД9/у1}
Количественное значение оценки i-го варианта обозначим через Si.
В нашем примере - “S1”:
S1=S1.у1+S1.у2+S1.у3+S1.у4+S1.у5+S1.у6=780t+670t+1470t+230t+860t+1730t=5740t;
где:
S1.у1= S1.у1.п1+ S1.у1.п2+ S1.у1.п5+ S1.у1.п7=0+300t+180t+300t=780t;
S1.у1.п1= S1.у1.п1.БД1+ S1.у1.п1.БД5+ S1.у1.п1.БД9=100*0+60*0+150*0=0;
S1.у1.п2= S1.у1.п2.БД4+ S1.у1.п2.БД7=400*0+300*t=300t;
S1.у1.п5= S1.у1.п5.БД5+ S1.у1.п5.БД8=200*0+180*t=180t;
S1.у1.п7= S1.у1.п7.БД1+ S1.у1.п7..БД7=30*0+300*t=300t;
S1.у2= S1.у2.п1+ S1.у2.п4+ S1.у2.п5=220t+410t+40t=670t;
S1.у2.п1= S1.у2.п1.БД1+ S1.у2.п1.БД5+ S1.у2.п1.БД9=100*t+70*t+50*t=220t;
S1.у2.п4= S1.у2.п4.БД7+ S1.у2.п4.БД8+ S1.у2.п4.БД9=200*t+150*t+60t=410t;
S1.у2.п5= S1.у1.п5.БД5+ S1.у1.п5.БД8=200*0+40*t=40t;
S1.у3= S1.у3.п2+ S1.у3.п3+ S1.у3.п4+ S1.у3.п5=700t+150t+340t+280t=1470t;
S1.у3.п2= S1.у3.п2.БД4+ S1.у3.п2.БД7=300*t+400*t=700t;
S1.у3.п3= S1.у3.п3.БД1+ S1.у3.п3.БД9=50*t+100*t=150t;
S1.у3.п4= S1.у3.п4.БД7+ S1.у3.п4.БД8+ S1.у3.п4.БД9=150*t+150*t+40t=340t;
S1.у3.п5= S1.у3.п5.БД5+ S1.у3.п5.БД8=100*t+180*t=280t;
S1.у4= S1.у4.п1+ S1.у4.п6+ S1.у4.п9=150t+40t+40t=230t;
S1.у4.п1= S1.у4.п1.БД1+ S1.у4.п1.БД5+ S1.у4.п1.БД9=100*t+30*t+20*t=150t;
S1.у4.п6= S1.у4.п6.БД4+ S1.у4.п6.БД8+ S1.у4.п6.БД9=20*t+10*t+10t=40t;
S1.у4.п9= S1.у4.п9.БД1+ S1.у4.п9.БД4=20*t+20*t=40t;
S1.у5= S1.у5.п3+ S1.у5.п6+ S1.у5.п7+ S1.у5.п8+ S1.у5.п10=160t+55t+35t+260t+350t=860t;
S1.у5.п3= S1.у5.п3.БД1+ S1.у5.п3.БД9=60*t+100*t=160t;
S1.у5.п6= S1.у5.п6.БД4+ S1.у5.п6.БД8+ S1.у5.п6.БД9=30*t+5*t+20t=55t;
S1.у5.п7= S1.у5.п7.БД1+ S1.у5.п7.БД7=35*t+450*0=35t;
S1.у5.п8= S1.у5.п8.БД4+ S1.у5.п8.БД5=60*t+200*t=260t;
S1.у5.п10= S1.у5.п10.БД4+ S1.у5.п10.БД8=350*t+400*0=350t;
S1.у6= S1.у6.п1+ S1.у6.п4+ S1.у6.п5+ S1.у6.п10=270t+330t+330t+800t=1730t;
S1.у6.п1= S1.у6.п1.БД1+ S1.у6.п1.БД5+ S1.у6.п1.БД9=100*t+80*t+90*t=270t;
S1.у6.п4= S1.у6.п4.БД7+ S1.у6.п4.БД8+ S1.у6.п4.БД9=200*t+70*t+60t=330t;
S1.у6.п5= S1.у6.п5.БД5+ S1.у6.п5.БД8=150*t+180*t=330t;
S1.у6.п10= S1.у6.п10.БД4+ S1.у6.п10.БД8=400*t+400*t=800t;
Таким образом оценочная функция варианта распределения баз данных по узлам носит аддитивный характер.
Выбор метода решения:
Данная задача нахождения оптимального варианта является комбинаторной задачей распределения, однако учитывая аддитивный характер оценочной функции ее можно рашить не только методом полного перебора (что практически крайне затруднительно), но также методом динамического программирования, например методом ветвей и границ:
минимизировать S=f(x)
при условиях x (- G, где G - полное (конечное) множество вариантов.
Решение задачи:
Исппользуя правило: “Базу данных помещаем в тот узел, где она максимально используется”, составляем таблицу перспективных вариантов:
| БД1 | БД4 | БД5 | БД7 | БД8 | БД9 | |
| У1 | ||||||
| У2 | ||||||
| У3 | ||||||
| У4 | 1540- | |||||
| У5 | ||||||
| У6 | ||||||
| Максималь- ное число обращений к базе |
Из которой выбираем равнозначные оптимальные варианты:
| БД1 | БД4 | БД5 | Б7 | БД8 | БД9 | оценка варианта | |
| Вариант 1 | узел 1 | узел 5 | узел 2 | узел 1 | узел 6 | узел 1 | |
| Вариант 2 | узел 1 | узел 5 | узел 2 | узел 1 | узел 6 | узел 6 | |
| Максималь-ное число Обращений к базе |
Задание 2.
Определить вариант рационального размещения предметных баз данных в распределенной информационной системе для случая, когда каждая база данных может иметь одну репликацию (копию), размещаемую на любом узле, если это необходимо. Обрабатывающие процессы (приложения) не являются распределенными. При этом считать, что если некоторый процесс обращается за данными к базе, находящейся в другом узле, сетевые затраты на одно обращение составляют “t” секунд, независимо от местонахождения узла в сети и дисциплины обслуживания. Если процес обращается к базе данных, находящейся в том же узле, где выполняется и процесс, то считать, что “t=0”. На создание и поддержку репликаций средние приведенные затраты назначить для исходного учебного задания по следующей формуле:
N2=0,3*N*k-1,
где: N - значение из таблицы 1;
k - значение коэффициента из таблицы 2;
N2 - результирующее значение для исходных данных учебного варианта задания.
Приложение 5