Классификация параллельных КС по структурно-функциональным признакам (стр. 5 )

или, используя мощность множества:

, где - множество разбиений чисел ранга r.

Можно показать, что множество состояний фрагментированной свободной памяти КС размера Q определяется множеством разбиений чисел.

Утверждение.

Разбиение соответствует одному из состояний свободной памяти КС размера Q тогда и только тогда, когда , где r(p) – ранг разбиения p(N).

□:

По определению внешней фрагментации между ni и ni+1 существует сегмент занятой памяти Dj. Если принять Dj1, то число занятых участков памяти будет lr(p)-1.

Тогда размер занятой памяти:

Fr(p)-1, т. к. r(p) – ранг разбиения, то F Q-N и это будет необходимое условие.

■

38. Особенность распредления памяти в КС с сегментной организацией программ и данных (Модель 2). Приведите пример

Процесс распределения свободной памяти КС еще включает процесс удовлетворения запросов в адресном пространстве свободной памяти. Формализовать этот процесс позволяет Модель 2.

МОДЕЛЬ 2.

Особенностю распределения памяти КС с сегментной организацией программы и данных является неделимость поступающих запросов на выделение памяти. Т. е. для удовлетворения каждого запроса требуется непрерывный участок адресного пространства различной длины.

Такая организация распределения памяти применяется в системах телеобработки, при распределении ОП в многопроцессорных выч. комплексах (Эльбрус) и др.

Удовлетворение любого запраса на память реализуется соответствующим выполнением 2 процессов:

1.  поиск свободных непрерывных участков,

2.  выделение найденной свободной памяти под запрос

Оба эти процесса могут быть реализованы различными алгоритмами. В итоге их работы найденный участок свободной памяти полностью исключается из списка свободных участков, либо в всписке свободной памяти учитывается остаток.

В следствие этого процесса в одном свободном участке памяти может удовлетворяться более 1 запроса, поэтому процесс удовлетворения запросов на память можно моделировать понятием вложенности разбиений чисел.

Пусть интерпретируемому разбиению (k1, … , kt)├ k необходимо удволетворять памяти, свободные участки которой соответствуют разбиению (n1, … , nr)├ n и . В соответствии с определением вложимости разбиение (k1, … , kt) вложимо в (n1, … , nr), если части ki можожно так сгруппировать в r групп (каждая часть ki входит в одну группу + допускаются пустые группы) таких, что после сложения всех частей ki в каждой группе получается , , причем в процессе конкретной вложимости каждое nj из (n1, … , nr) используется не более одного раза, т. е. фрагмент nj, в котором группа запросов заняла объем уже больше не используется для размещения запросов ki даже при условии, что .

Т. о. понятие вложимости разбиения является адекватной интерпретацией процесса удовлетворения запросов на память КС.

Пример. Пусть группа запросов на память состоит из объемов (5, 2, 1), а системаа участков свободной памяти - из объемов (6, 3, 3), тогда одновременное удовлетворение всех этих запросов осуществимо, причем не единственным способом: (6 содержит 5 и 1; 3 сод-т 2; 3 сод-т 0), (6 сод-т 5; 3 сод-т 2 и 1; 3 сод-т 0), (6 сод-т 5; 3 сод-т 2; 3 сод-т 1). Таким образом, группа запросов для их размещения в участках свободной памяти в точности отражает реальную работу алгоритмов динамического распределения памяти.

39. Комбинаторная модель для оценки необходимого размера памяти КС (модель 3).

Размер ОП КС оказывает существенное влияние на работу КС. Увеличение ОП повышает производительность КС. При проектировании КС вопросам размещения ОП уделяется большое внимание на всех этапах создания системы. С этой целью создаются имитационные модели, с помощью которых исследуется поведение КС при типовых нагрузках. Проведение этих исследований требует затрат на разработку и увеличение времени создания ВС.

Эффективное функционирование КС в реальном времени невозможно без выполнения важного условия: в результате проектирования ПО должно соответствовать аппаратуре. Под аппаратурой понимается структура ВС. В настоящее время используются подходы для решения задач распределения памяти, которые позволяют решить эту задачу, однако проявляется это уже на этапе эксплуатации.

Выводы:

1.  Методы решения задачи проектирования управления распределения памяти должны минимаизировать затраты вычислительных ресурсов и обеспечить получения теоретически обоснованного алгоритма уже на этапе проектирования КС.

2.  Метод управления распределения памяти должен учитывать особенности структуры программных средств КС

3.  Метод управления распределения памяти должен минимизировать затраты процессорного времени на ее распределение и обеспечивать эффективное выполнение функций КС при пиковой нагрузке

4.  Метод управление распределения памяти КС должен накладывать как можно меньше ограничений на очередь запросов к памяти и обеспечивать быстрое освобождение уже не используемых ее участков.

Для решения этих задач можно использовать ряд комбинаторных моделей. Последовательность представления таких моделей выбирается в соответствии с априорной информацией о процессе функционирования КС

В рассматриваемых моделях необходимо учитывать возможность группового удовлетворения запросов. Преимуществом такого способа является наличие дополнительной априорной информации о характере запросов на память, которые учитываются путем рассмотрения упорядоченных по размеру групп запросов.

МОДЕЛЬ 3.

Рассмотрим функционирование КС, в которой запросы на выделение памяти поступают группами. Пусть размеры запросов группы, которая поступает в произвольный момент времени соответствует разбиению (k1,…kt) – k.

Свободная память в рассматриваемый момент времени t представляется r-участками суммарным размером n. Тогда в соответствии принципом полного размещения:

(*) при условии

обеспечивает нахождение такого суммарного размера свободной памяти и этот суммарный размер представляется любым разбиением на r участков (свободных и непрерывных) адресного пространства и позволяет полностью разместить все k1,…,kt без реорганизации и перераспределения.

Из формулы (*) видно, что для решения этой задачи не требуется информации о размерах свободных участков памяти, а следовательно на каждого из запросов группы нет необходимости просматривать список свободной памяти КС, достаточно проверить справедливость неравенства: (**)

,

где r – количество фрагментов, которыми представлена свободная память размером n.

Если (**) выполняется, то из (*) следует, что для удовлетворение запросов k1,…,kt можно использовать любой алгоритм динамического распределения памяти, учитывающий упорядоченность запросов по убыванию их размеров. То есть все запросы k1,…kt можно одновременно удовлетворить в свободной памяти (n1,…,nr), например, по алгоритму динамического распределения памяти first-fit, НО при условии, что при выборе запросов из очереди учитывается их упорядоченность по убыванию размеров.

Вывод: принцип полного размещения может быть использован при проектировании методов динамического распределения памяти КС.

Примечание: метод first fit состоит в размещении данных в первом подходящем по размеру для этого блоке памяти.

40. Комбинаторные модели, позволяющие произвести расчет оценки сверху необходимого размера оперативной памяти КС

МОДЕЛЬ 4.

Пусть имеется m групп запросов при моделировании памяти. Размеры запросов j группы соответствуют частям разбиения , где

В соответствии с принципом полного размещения можно показать

при условии

обеспечивает нахождение суммарного размера свободной памяти, причем свободная память разбита на не более, чем r непрерывных адресных участков. Тогда обеспечивается полное удовлетворение запросов на память любой j-й группы

Алгоритм распределения такой же как в модели 3

МОДЕЛЬ 5.

Пусть множество состояний занятой памяти интерпретируется как множество разбиений чисел

где любая часть i-го разбиения dir — размер r-го занятного участка памяти, а vi — количество занятых участков, представленных частями i-го разбиения числа

Для каждого i-го состояния занятой памяти известно множество групп запросов. Каждая из этих групп в процессе функционирования КС может потребовать одновременного удовлетворения всех своих запросов при i-м состоянии занятой памяти.

Пусть множество разбиений чисел соответствует множеству групп запросов для i-го состояния занятой памяти

Части этих разбиений соответствуют размерам запросов на память, а ранг tj соответствует количеству запросов в j-й группе

Учитывая влияние внешней фрагментации полагаем, что в процессе функционирования КС при удовлетворении запросов каждой группы, причем эти запросы соответствуют i-му состоянию занятой памяти, и, следовательно, свободная память КС оказывается раздробленной на не более чем Vi+1 участков, где Vi – число занятых участков памяти, соответствующих i-му состоянию. Тогда оценка сверху V необходимого размера памяти КС, которая в процессе функционирования будет доступна для удовлетворения любой поступающей группы запросов на память с учетом принципа полного разбиения вычисляется по следующему выражению:

при где величина определяется по формулам принципа для каждого разбиения , а - суммарный размер занятой памяти при удовлетворении запросов группы.

Такой подход к выбору ОП предполагает возможность использования алгоритма динамического распределения памяти. Алгоритмы должны учитывать запросы группы в порядке убывания их размера. Однако в настоящее время в большинстве КС не используют групповой метод удовлетворения запросов на память. Построить аналогичную модель для оценки выбираемого размера памяти при реализации одиночного метода позволяет иная формулировка комбинаторной модели: пусть имеется группа запросов на выделение памяти (k1,...,kt)

Эти запросы необходимо удовлетворить по одному в порядке поступления. Все запросы должны быть одновременно удовлетворены в свободной памяти. Свободная память это r непрерывных участков адресного пространства. Одиночное удовлетворение запросов предполагает порядок чисел (k1,...,kt). В соответствии с принципом полного размещения:

В любом порядке очередности чисел (k1,...,kt) выполняется неравенство:

и для оценки требуемого размера свободной памяти КС при одиночном удовлетворении запросов необходимо найти максимальное значение F(k1,...,kt). Этот максимум будет равен:

Нахождение этого результата не является окончательным решением этой задачи, следовательно, прежде чем решить задачу одиночного метода удовлетворения запросов на память необходимо сформировать алгоритм по которому осуществляется вложимость. Алгоритм, реализующий вложимость при произвольном порядке частей разбиения (k1,...,kt) можно сформулировать в следующем виде: пусть задано разбиение (k1,...,kt)-k и (n1,...,nr)- n, для которых справедливо неравенство:

Тогда причем эта вложимость может обеспечить алгоритм, который:

1)  части ki для размещения выбирает по одной в порядке их нумерации

2)  каждую часть kj размещает в первой подходящей по размеру части ni, то есть ni выбирается по следующему правилу:

3)  при выборе ni>kj остается остаток в виде nj=ni-kj>0

41. Диаграммы Ферре и инверсии в бинарных последовательностях

Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Ферре. Диаграмма Ферре разбиения — подмножество первого квадранта плоскости, разбитое на ячейки, каждая из которых представляет собой точку. Ячейки рамещаются в строки, первая строка имеет длину k1, над ней расположена строка длиной k2, и т. д. до m-ой строки длины km. Строки выровнены по левому краю.

Более формально, диаграмма Ферре — это замыкание множества точек (x, y) таких, что

x, y > 0 и

где [x] обозначает целую часть x.

. Например разбиение числа 4 (1,22,32,4) будет выглядеть следующим образом:

J

J J

J J

J J J

J J J

J J J J

Такие изображения разбиений удобны для представления различных преобразований разбиения. Например, если эту диаграмму повернуть следующим образом:

J

J J J

J J J J J

J J J J J J

то получится граф (1,3,5,6), сопряженный графу (1,22,32,4)

Для описания совокупности разбиения натуральных чисел с числом слагаемых, не превосходящих α можно использовать прямоугольники Ферре, содержащие α*β квадрата.

В каждом столбце содержится α квадратов, а в каждом столбце β.

Диаграмма Ферре соответствует разбиению: ; ;

Строится следующим образом. В первой строке заштриховывается квадрат, во второй квадрата и т д. Заштрихованная ступенчатая фигура называется диаграммой Ферре и соответсвует разбиению числа n.

α = 7; β = 11; n=22=8+6+6+1+1;

0 - что касается горизонтали

1 – что касается вертикали

α + β =

Т о. между разбиением числа n и последовательностью длинны α + β состоящей из α единиц и β нулей и имеющей n инверсий установлено взаимно-однозначное соответствие, откуда вытекает что J(n,α,β)- число бинарных последовательностей с αединицами и β нулями и n инверсиями.

Тогда J(n,α,β)=R(n,α,β) , где R – количество разбиений натурального числа n на не более чем α слагаемых, величина которых не превосходит значение β.

В скобках - коффициент Гаусса.

Пусть есть n мерное векторное пространство содержащее , где p простое число, систем из r независимых векторов равно:

Тогда число базисов в пространстве будет равно:

Вектор выбирается из простраства линейно независимых векторов способом.

Число подпространств выражается следующей формулой:

42. Влияние топологии на технические характеристики сетей

Сложность сети растет с ростом количества узлов и ребер. Для связной сети число ребер не может быть меньше числа узлов минус 1 : m≥(n-1). Связанные сети с максимальной однородностью при числе узлов >2 представляют собой кольца с числом узлов, равным числу ребер. Для неориентированных сетей в качестве показателя сложности можно использовать показатель однородности ее элементов, определенный через систему числовых инвариант. Сложность сети зависит не только от числа элементов, но и от их взаимосвязи. В свою очередь это соотношение связано с разностью числа ребер и числа узлов (l=m-n).

При изменении l от 0 до n(n-3)/2 сложность сети увеличивается за счет увеличения валентности от 2 до n-1.

Разнообразие узлов по валентности усложняет сеть за счет снижения унификации в оборудовании узлов

Сложность сети во многом определяет ее стоимостные характеристики. Суммарная стоимость элемента сети будет равна С=С1n+C2m, где С1 – стоимость оборудования узла, C2 – стоимость оборудования канала связи.

Для сравнения со стоимостью других сетей необходимо использовать относительную дополнительную стоимость:

Труднее всего оценить стоимость эксплуатации сети, зависящую от показателя однородности, который влияет на сложность организации взаимодействия в процессе решения задач.

Пропускная способность сети и ее диаметр:

Для вычисления среднего диаметра пользуются одним из вариантов – ветвление узлов.

Узловая мода сети: для каждого xi найдем разбиение множества X0 на подмножества такие, что

Для неориентированной сети:

Подмножество назовем слоем j для узла xi. Обозначим . Тогда модой узла xi будет вектор .

43. Классы характеристик КС

1) Структурная сложность – число элементов и связей, составляющих структуру КС. Выделенные элементы соответствуют висячим тупиковым вершинам графа. Наличие в графе изолированных вершин говорит об ошибке при формировании структуры ВС. Исследование числа и особенностей связей между элементами структур направлено на выявление в соответствующем графе контуров и сильносвязанных подграфов. Структурная сложность может быть оценена числом остовных деревьев.