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

Недостатки:

1. Заметим, прежде всего, что мат­рица сама по себе не полностью отражает структуру сети Петри. Переходы, имеющие как входы, так и выходы из одной позиции (петли), представляются соответствующими элементами матриц , но затем взаимно уничтожаются в матрице .

2. Другая проблема - это отсутствие информации о последова­тельности переходов в векторе запуска.

3. Еще одна трудность заключается в том, что решение уравнения является необходимым для достижимости, но недостаточным (полученные последовательности переходов могут быть не разрешены).

23. Задача достижимости сетей Петри

Задача достижимости. Для заданной сети Петри C с маркировкой μ и маркировки μ’ определить, верно ли, что. μ’R(C, μ), где R(C, μ) – множество достижомсти сети Петри С с маркировкой μ.

Пример:

Для сети изображенной на рисунке и маркировке μ =(1,0,0) непосредственно достижимыми являются две маркировки (1,0,1) и (0,1,0). Из маркировки (1,0,1) можно получить маркировку (0,1,1) и (0,1,2). Из (0,1,0) нельзя достичь не одной маркировки, так как ни один переход не разрешен. Можно показать, что множество достижимостей имеет следующий вид для этой сети R(C,μ)={(1,0,n),(0,1,n)|n>=0}

Задача достижимости для сетей Петри – очень важна, поэтому необходимо показать, что она разрешима, даже если вычисления громоздки и дороги.

Если задача разрешима, то можно искать более эффективные методы решения. Сначала надо показать, что метод решения существует.

Для обоснования существования методов решения обозначим через - сумму векторов запуска f по всем компонентам.

Т. е. если f=(f1+…+fn), то .

Если существует последовательность , переводящая сеть Петри из маркировки μ в μ', то уравнение имеет решение, которое является вектором запуска для любой σ.

Последовательность запусков перехода можно определить из вектора запуска путем простого перебора возможных последовательностей длины . Последовательность должна быть действительной и приводить от μ в μ'.

Для сети Петри с m-переходами количество возможных последовательностей: .

Нам известно, сколько раз запускается переход t1(f1), сколько t2(f2) и т. д. (зная, сколько раз запускается переход, можно уменьшить число перебираемых вариантов). Т. о. необхоимо проверить не более, чем ()!

()! обозначает возможное упорядочение из f1 запуска перехода t1, f2 запуска перехода t2 и т. д. → является ли μ' из μ?

Сначала решаем матричное уравнение:

, где x=f

Если решение не существует, то μ' не достижима из μ.

Если решение f существует, то проверяем все ()! возможных упорядоченных переходов.

Если какая-нибудь из этих последовательностей действительна, то μ' достижима из μ.

В результате получаем последовательность, переводящую сеть Петри из μ' достижима из μ.

Есть препятствие – решение f может быть неоднозначным. Для определения достижимости в этом случае необходимы дополнительные исследования. В простейшем случае может оказаться: или все решения представляются выражением вектора запуска, соотвествующего действительным значениям или ни одного решения.

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

18. Использование сетей Петри для количественных оценок функционирования параллельных КС.

24. Границы возможностей моделирования с помощью сетей Петри.

27. Границы возможностей моделирования с помощью сетей Петри.

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

25. Подклассы сетей Петри

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

К подклассу автоматных графов относятся сети Петри с 1 входной и 1 выходной дугой К маркированным графам относятся ести Петри, имеющие ограничения на число входных и выходных позиций. Для устойчивых сетей Петри при любой маркировке , если два любых перехода tj и tk оказываются возбужденными, то срабатывание одного из них tj не исключает возможности срабатывания другого tk. В сетях Петри, свободных от конфликтов, если позциия pi принадлежит множеству входных позиций tj, то она принадлежит и подножеству выходных позций tj; иначе pi должна иметь не более одной выходной дуги. Если на сеть Петри накладываются ограничения: каждая выходная дуга от позции является либо ее единственных выходомо, либо единственных входом перехода, то такую сеть относят к сетям свободного выбора. Условие выделения подкласса чистых сетей Петри: переход не может иметь pi и в качестве входной и в качестве выходной позиции. Руглярные сети Петри: для них вводится алгебра регулярных сетей. Она сроится с помощью операций над сетями (наложение, разметка, слияние, итерация), что позволяет представить любую регулярную сеть в линейной форменной записи. Признаком выделения простых сетей Петри является наличие у каждого перехода не более чем одной входной позиции и не более одной выходной.

26. Маркированные графы – подкласс сетей Петри.

Маркированный граф – сеть Петри вида

Этот подкласс позволяет моделировать алгоритмы функционирования вычислительных систем, взаимосвязи между подсистемами и ряд других факторов без учета конкуренции между процессами.
28. Покажите, используя матричный метод анализа сетей Петри, что маркировка (0, 7, 0, 1) недостижима из маркировки (1, 0, 1, 0) для сети Петри, изображенной на рисунке.

Матрицы, представляющие входную и выходную функцию:

Составная матрица изменений:

Начальная маркировка: μ=(1,0,1,0).

Маркировка, которую нужно проверить на достижимость: μ’=(0,7,0,1).

Тогда должен существовать такой вектор запусков , что

причем (a, b,c) должны быть неотрицательными целыми числами.

Получим систему уравнений, которая не имеет решения

Т. к. a, b,c должны быть целыми неторицательными числами - маркировка недостижима.

29. Дана последовательность запусков переходов s = t3 t2 t3 t2 t1 сети Петри, изображенной на рисунке. Определите вектор запуска и маркировку m’ сети Петри.

Матрицы, представляющие входную и выходную функцию:

Составная матрица изменений:

Последовательность s = t3 t2 t3 t2 t1 представляется вектором запусков t1 в s встречается 1 раз, t2 – 2 раза, t3 тоже 2 раза, тогда.

Из рисунка начальная маркировка . Маркировка

Ответы

Веткор запуска:

Маркировка μ’=(

30. Определите является ли маркировка (1, 8, 0, 1) достижимой из маркировки (1, 0, 1, 0) для сети Петри, изображенной на рисунке. Найдите последовательность запусков переходов s.

Матрицы, представляющие входную и выходную функцию:

Составная матрица изменений:

Решение:

Начальная маркировка: , маркировка, которую нужно проверить на достижимость , тогда должен существовать такой вектор запусков , что , причем (a, b,c) должны быть неотрицательными целыми числами.

Получим систему уравнений:

,

Что соответствует последовательности запусков s = t3 t2 t3 t2 t3 t2 t3 t2 t3.

Маркировка достижима.

31. Понятие о топологическом синтезе и анализе структур КС

Анализ структурных свойств КС на графе неизбежно приобретает топологический характер - предполагающий использование ряда характеристик, определяющих количественную меру топологии объекта.

1. Структурная сложность - определяется как число элементов и связей, составляющих структуру КС.

2. Адаптируемость КС - приспособленность структуры КС к внешним и внутренним условиям, позволяющая оптимальным образом достигать цели функционирования: выполнения, по крайней мере, минимально возможного количества алгоритмов из заданного набора задач.

3. Диаметр структуры КС - соответствует метрической характеристике, введенной на графе для определения кратчайшего пути между наиболее удаленными вершинами. В ряде случаев разработчики структур оперируют понятием среднего диаметра, имеющим большую системную значимость.

4. Структурная связность КС - способность противостоять разбиению, разделению графа структуры КС на независимые части.

5. Надежность КС - способность структуры КС обеспечить функционирование системы в течение заданного промежутка времени.

6. Живучесть (отказоустойчивость) КС - оценивает сохранение частей структуры КС, обеспечивающих выполнение поставленной задачи.

7. Стоимость КС - характеристика, оценивающая стоимость реализации структуры.

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

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

32. Разбиения чисел. Основные понятия и определения. Принцип Дирихле.

Разбиение натурального числа n, есть его представление неупорядоченной суммой натуральных слагаемых: . Эти слагаемые и называются частями, а их число r – рангом разбиения.

Композиция – это представление натурального числа n упорядоченной суммой натуральных слагаемых

n=6

ранг 1: 6=6;

ранг 2: 6=5+1, 6=4+2, 6=3+3;

ранг 3: 6=4+1+1, 6=3+2+1, 6=2+2+2;и т. д.

ранг 6: 6=1+1+1+1+1+1;

Как найти число композиций натурального числа n=r? Это будет число способов, которыми можно разместить r-1 черточек между n-1 промежутками.

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

Разбиение изображают при помощи векторной записи: .

или в сокращенной записи:

Часть присутствует в разбиении раз, т. о.

Всякое разбиение можно представить в виде , где - целое, неотрицательное число, которое указывает сколько раз число i присутствует в этом разбиении в виде части (-ранг разбиения)

Разбиение можно изобразить графически, с помощью графа Ферре (Ферррер)

Принцип Дирихле.

Если является наименьшим целым n, при котором в каждом разбиении этого n на r частей, найдется часть не меньшая, чем k, то тогда

Принцип Дирихле можно сформулировать в виде размещения (принцип ящика):

при любом размещении r+1 предметов по r ящикам, то найдется ящик с двумя предметами.

33. Вложимость разбиений

Основным соответствием между разбиениями чисел является их вложимость.

Разбиение {k1, … , kt} вложимо в разбиение {n1, … , nr}, если существует отображение φ: {1, … , t}→{1, … , r}, при котором выполняется система неравенств

, , ,

- полный прообраз элемента i при отображении φ: [t] →[r].

Т. е. разбиение {k1, … , kt} вложимо в разбиение {n1, … , nr}, если части kj разбиения можно так сгруппировать в r групп (причем каждая часть kj входит в одну группу и пустые группы допускаются), что по сложении всех частей kj в каждой группе получается r чисел: ,

Если разбиение {k1, … , kt} вложимо в {n1, … , nr}, то можно записать этот факт так:

{k1, … , kt} {n1, … , nr}

(2,2,2) (4,2), поскольку (4,2)=(2+2,2), но

(2,2,2) (3,3), т. к. нельзя три двойки сгруппировать в пару групп, каждая из которых не превосходила бы числа 3.

Основной вопрос вложимости состоит в том, вложимо ли разбиение {k1, … , kt} в разбиение {n1, … , nr}.

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

Простейшие свойства:

Разбиение q вложимо в разбиение p тогда и только тогда, когда разбиение q-(p∩q) вложмио в разбиение p-(p∩q).

Другими словами вопрос о вложимости разбиений эквивалентен вопросу о вложимости разбиений, полученных из исходного разбиения путем удаления в каждом из них одинакового количества одинаковых слагаемых, например:

(1,2,2,3,5) (2,3,3,7) (1,2,5)(3,7)

34. Ранговое условие вложимости; пример использования

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

Пусть t(n,k,r), то наименьшее t, при котором для , , , где - множество всех разбиений числа n ранга r:

t(n,k,r)=max{k- +1,1}

Следствие:

Если n(k,t,r) наименьшее n, при котором для , , , то:

n(k, t,r)=max{k, r(k-t) +1}

35. Принцип полного размещения; пример использования

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

Теорема:

Пусть , r - натуральные числа и n(k1, … , kt; r) –наименьшее n, при котором разбиение (k1, … , kt)├ k вложимо в каждое рзабиение этого n на не более чем r частей.

Тогда справедливо следующее равенство n(k1, … , kt; r)=

Следствие:

Если для натуральных k1>1, , (k1, … , kt)├ k n, через r(k1, … , kt; n) обозначено наибольшее r, при котором в каждое разбиение n на r частей вложимо разбиение (k1, … , kt), то

r(k1, … , kt; n)=

Действительно, искомое r согласно принципу полного размещения есть наибольший целый корень неравенства nn(k1, … , kt; r).

Если k= n(k1, … , kt; r), то каждое размещение k частиц по r ячейкам реализуемо размещением t групп частиц по kj в j-ой группе при условии, что каждая группа целиком размещается в одной ячейке.

36. Вложимость с ограничениями; пример использования

Подчас требуется гарантировать вложимость разбиения (k1, … , kt)├ k отнюдь не во все разбиения числа n на r частей, но лишь в некоторые. Так, например, принцип полного размещения гарантирует вложимость разбиения (3,2,1) в каждое разбиение числа 6 на две части, так как n(3,2,1 ; 2)=6, и ничего не говорит о вложимости (4,1,1) в (5,1) и (4,2).

Экстремальный результат, гарантирующий вложение фиксированного разбиения не во все разбиения данного ранга, может быть представлен следующим утверждением:

Теорема:

Пусть (n2, … , nr), , r – натуральные числа и n(k1, … , kt ; n2, … , nr) – наименьшее n, при котором каждое разбиение (p1, … , pr) этого n на r частей такое, что , , обладает тем свойством, что

(k1, … , kt) (p1, … , pr).

Тогда

n(k1, … , kt ; n2, … , nr) =

37. Комбинаторные модели для исследования процесса распредления памяти КС

Исследования, связанные с увеличением эффективности методов управления распределением памяти направлены на:

- распределение памяти,

- перераспределение памяти,

- реорганизацию памяти.

Распределение памяти – конечная последовательность отображений (I→F)t, t=1,2,…, множества I информационных объектов (или их наименований) во множество физических адресов распределяемой памяти для дискретных момент времени t.

Перераспределение памяти – перенесения ряда инф. объектов из адресного пространства ОП во вспомогательную (долговременную) память с целью освобождения ОП для продолжения вычислений.

Реорганизация памяти – перемещение инф. объектов в адресном пространстве памяти.

Перераспредление и реорганизация памяти – одни из основных методов повышения эффективности использования памяти.

Существует 2 способа распределения памяти:

- статический,

- динамический.

Статический – распредление памяти, при котором отображение (I→F)t выбирается 1 раз до выполнения программы.

Диномческий – каждое отображение (I→F)t выбирается непосредственно в ходе вычислительного процесса, исходя из того, как отображается (I→F)t-1.

Выбор способа зависит от:

- ресурсов,

- свойств программы,

- используемой информации.

Статическое распределение может применятся тогда и только тогда, когда сведения о ресурсах программы и о свойствах ссылок имеются перед выполнением программы.

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

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

Всё вышесказанныое говорит в пользу динамического распределения ОП.

Ислледования, связанные с оценкой эффективности применения различных методов распределения ОП в основном приследуют следующие цели:

1.  освобождение программиста от заботы о распределении памяти,

2.  повышение эффективности использования памяти,

3.  минимизация затрат процессорного времени на управление распределением памяти.

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

1.  стохастический – влияние фрагментации рассматривается как вероятностный процесс

2.  деформационный – сам процесс функционирования КС приводит к заданным при проектировании состояниям фрагментации памяти.

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

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

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

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

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

Применение средств перераспределения или реорганизации влечет дополнительные затраты процессорного времени на управление перераспределением или реорганизацией памяти, в следствие чего происходит снижение производительности КС.

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

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

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

Т. о. уменьшаются затраты процессорного времени на распределение памяти при сегментной организации программы и данных.

Далее будем рассматривать только сегментную организацию памяти, которая имеет следующие преимущества:

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

2.  исключаются потери в эффективности при округлении запросов (до принятого размера страниц – потери на внутреннюю фрагментацию).

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

МОДЕЛЬ 1.

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

1.  количество свободных (занятых) участков памяти,

2.  размер свободных (занятых) участков,

3.  суммарный размер свободной (занятой) памяти.

Запросы на выделение памяти в любой момент функционирования КС достаточно полно характеризуются следующими параметрами:

1.  количество запросов в очереди на выделение памяти,

2.  требуемые размеры непрерывных участков в адресном пространстве памяти или размеры запросов,

3.  суммарный размер памяти, требуемый для распределения запросов из очереди.

Пусть Q – размер ОП, N – суммарный размер свободной памяти, который в процессе работы системы принимает следующие значения:

NZ+, ,

где Z+ - множество целых неотрицательных чисел.

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

Такое отображение может интерпретироваться как вектор:

z(N)=(n1, … ,nr)

, ,

ni – размер i-го участка памяти (свободной),

r – количество таких учатсков.

2 состояни свободной памяти z(N)= (n1, … ,nr) и z’(N)= (n’1, … ,n’r) будем считать различными, если они различны как векторы, т. е. если существует i, при котором ni≠ n’i.

Аналогичным образом любое состояние занятой памяти будет интерпретироваться вектором

g(D) = (d1, … , dl),

dl – размер непрерывного l-го участка памяти,

В – суммарный размер занятой памяти.

Для di≠ d’i будем считать, что эти эти 2 состояния различны.

При моделировании запросов на выделение свободной памяти z(N)=(n1, … ,nr) предполагаем, что они могут поступать либо одновременно, т. е. группами q(k)= (q1, … ,qt), либо по одному, где ki – требуемый размер свободной память для j-го запроса.

Группу запросов будем интерпретировать как вектор, т. е.

q(k)= (q1, … ,qt),

,

Элементы ni, dm, kj векторов z(N), g(D), q(K) можно представить как разбиение чисел N, D, K, т. е.

P(N)= (n1, … ,nr)

P(K)= (k1, … ,kt)

P(D)= (d1, … ,dl)

Части разбиения ni опредлеяют размеры свободных участков памяти, kj – требуемые размеры (размеры запросв на память), dm – размеры непрервыных участков занятой памяти. Ранги разбиений P(N), P(K), P(D) определяют r – число непрерывных участков адресного пространства, t – количество запросов в очереди, l – число непрерывных участков адресного пространства занятой памяти.

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

Интересует: имеются ли в памяти свободные непрервыные участки, необходимые для удовлетворения поступивших запросов на память?

Т. о. не требуется информация о состоянии адресного пространства свободной памяти.

Интерпретация сободной и занятой памяти неупорядоченными разбияниям чисел позволяет моделировать внешнюю фрагментацию памяти без учета ее адресного пространства.

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

Если запросы на память пришли группой, то они дожны быть одновременно удовлетворены. При этом алгоритм распределения запросов может быть любым, поэтмоу Модель 1 является адекватным представлением состояния фрагментации памяти и запросов на выделение памяти.

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

Суммарный объем свободной памяти КС изменяется в пределах

,

Q – размер памяти КС,

, где

- множество разбиений числа Ni.

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