Сети Петри для моделирования управления ресурсами в операционных системах

Материал из HNKN
Перейти к навигации Перейти к поиску

Резюме[править | править код]

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

Ключевые слова Сети, Ресурсы, Избежание взаимоблокировок, Операционные системы, позиция16, переход, .

Введение[править | править код]

Модель-это простое и понятное представление структуры и поведения исследуемой системы, которое в большинстве случаев может быть выражено математическими формулами. Правила принятия решений могут быть получены непосредственно из шаблона[10,11]. Фактически, используя модель, мы можем получить знания и информацию о моделируемом явлении, не испытывая затрат и рисков, связанных с реальным явлением. Точно так же сети Петри используются для получения информации о структуре и функциях моделируемых систем. Сети Петри были разработаны Карлом Адамом Петри в 1962 году[1]. Его исследования были сосредоточены на информационных системах. В Германии и ряде других стран были созданы многочисленные группы для проведения исследовательских проектов по применению сетей Петри. В этой статье, после краткого введения в Сети Петри, рассмотрена проблема моделирования управления ресурсами в операционной системе с использованием сетей Петри.

Сети петри[править | править код]

Сети Петри основаны на теории графов. Они являются исполняемыми и имеют возможность графического описания сложных систем. Теория сетей Петри развивалась в двух направлениях[4]: прикладная теория сетей Петри; теория сетей Петри. Целью разработок в прикладной области является обеспечение необходимых инструментов, методов и взаимосвязей для применения сетей Петри. Фактически, теория струн является предпосылкой для более эффективных приложений. Разработки в теоретическом направлении считают, что сети Петри полезны для реальных задач. Соответственно, в данной статье учитываеются как теоретические, так и прикладные аспекты. Сначала определяются некоторые формулы, а затем описывается мощность и применение этого инструмента.

Основные определения[править | править код]

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

Структура сетей Петри[править | править код]

Поскольку Сети Петри (PN) являются особой формой графов, будут рассмотрены основные понятия из теории графов[5].

Определение 1. Граф состоит из двух компонентов, узлов и ребер, и способа соединения этих элементов[6].

Другими словами граф G(V,E,Q)состоит из непустого множества V, которое называется множеством вершин графа, множества E, называемого ребрами графа, и отображения Q из множества E на множество пар v Если пара узлов, соединенных ребром, является упорядоченной парой, то ребро направлено и Стрелка помещается на ребро, чтобы обозначить этот факт. Если все ребра графа направлены, то граф называется направленным графом (орграфом). Два узла, Соединенные ребром графа, называются смежными узлами. Узлы необязательно должны быть обозначены точками; они могут быть показаны с помощью кругов, полос, коробок или любой другой обычной формы. Когда граф содержит направленные параллельные ребра (ребра, соединяющие идентичную пару узлов), этот граф называется мультиграфом. Несколько примеров мультиграфов показаны на Рис. 1.Свойство сетей Петри как графов состоит в том, что они являются двудольными графами, т. е. у них есть два вида узлов. Чтобы различить эти два вида узлов, для их представления используются различные формы. Первый тип узлов называется узлами размещения (позиции), и они показаны кругом или эллипсом. Второй тип узлов называется узлами перехода (переходы) и обозначается сплошной полосой или прямоугольником. Края сетей Петри называются дугами и всегда направлены. Двудольный граф обладает особыми свойствами. Ребро может соединять только два узла разных типов. Таким образом, ребра могут быть дугами, образующими дугу от позиции к переходу или от перехода к позиции. Невозможно, чтобы дуга соединяла одно позицию с другой позицией или переход с другим переходом[9]. На рис. 1 показаны два примера примеров графиков

TwoRandomGraphs.png

Рис. 1: Два примера графов.

Определение 2. Сеть Петри состоит из четырех компонентов[1,14]:

- P = {p1, p2,..,pk} k > 0 является конечным множеством позиций.
- T = {t1, t2,..,tl} l > 0 является конечным множеством переходов (где P ∪ T ≠ 0 и P ∩ T = 0 ),
- I:P×T→N является входной функцией, определяющей веса дуг, направленных от мест к переходам,
- O:P×T→N является выходной функцией, которая задает веса дуг, направленных от переходов к позициям,

Функции ввода-вывода являются мостом переходов (T) и позиций (P), а также соединяют T,P, пары друг с другом. Функция ввода определяет набор входных данных позиций I(ti) для каждого перехода ti, в то время как выходная функция определяет набор выходных позиций O(ti) для каждого перехода ti[7]. Структура сети Петри определяется позициями, переходами, входными и выходными функциями. На рис. 2 показан пример сети Петри.

Рис 2. Пример сети Петри

Рис 2. Пример сети Петри

Обозначения в сетях петри[править | править код]

Обозначение m обозначает размещение ряда меток на позициях сети Петри. Каждая метка имеет первоначальный понятие T, P в Сети Петри. После метки определяется и ставится в места (Р) сети, число и состояние меток может изменяться во время выполнения. Другими словами, метки используются для определения порядка выполнения. M = (C, m) - сеть Петри, где C = (P,T,I,O) и m обозначения. Это часто пишется как[6]: M = (P,T,I,O,m)

Вектор m показывает количество меток для каждой позиции Pi. mi это количество меток в месте Pi т.е M(Pi) =mi.

Правила обработки Сетей Петри[править | править код]

Сети Петри выполняются с помощью горящих переходов[8]. А сеть есть выполняется с помощью отдельных индексированных меток. Метки ставятся на места и контролируют исполнение переходов. Переход T выполняется путем удаления меток из входных позиций и создание новых отдельных меток в местах вывода. Переход срабатывает только в том случае, если он доступен или активен, и каждый из входные места имеют по крайней мере количество меток, равное входным дугам этого перехода (которые являются стрелками с позиции P к переходу). Количество меток, необходимых для входные дуги для активации перехода t называются метками активации. Переход Ti в подписанную сеть Петри C = (P, T, I, O) со знаком m активируется, когда количество предоставленных токенов pi больше или равно минимальное количество входящих дуг в Ti[1,12,13].

Пример. На рис. 3 t1 выстреливается, когда имеется хотя бы одина метка в p1 и t1 срабатывает, когда есть одна метка p3. При срабатывании перехода он выталкивает весь активатор меток и отправляет их в места вывода.

PetriCalculation.png

Рис. 3 Позиции, переходы и условия перехода.

Операционная система, правила и методы моделирование[править | править код]

(на переводе)

Моделирования взаимоблокировок[править | править код]

(на переводе)

Заключение[править | править код]

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

Источники[править | править код]

  1. Shams, Fereydun, Zinati Safa, An algorithm for modeling expert systems using fuzzy colored Petri Nets, M.Sc. degree thesis, Shahid Beheshti University, July 2008.
  2. Silberschatz, Abraham, Operating System Concepts, translated by Atamazhuri, Parisima, Tehran, Iran: Ashian 1999.
  3. Jalili, Rasul, Modeling vulnerabilities of computer networks using colored Petri Nets, Eleventh International Computer Conference of Iranian Computer Association, Computer Science Research Institute, Tehran, Iran, 2005.
  4. Barzamini, Ruhollah, Petri Nets and modeling internet-based remote control systems using Petri Nets, The First National Conference on Computer Engineering, Islamic Azad University,Lahijan, Iran, 2007.
  5. James L.Peterson," Petri Nets " , computing surveys , Vol 9 , No.3 , September , 1977.
  6. J. Peterson, Petri Net theory and the Modeling of Systems,, prentice-Hall,N.J.,1981.
  7. Kurt Jensen , " A Brief Introduction to Coloured Petri Nets " , Computer science Department, University of Aarhus, Denmark.1997.
  8. T. Murata, Petri Nets:"Properties, Analysis And Applications" , Proceedings of IEEE 77 (1989) 540–541.
  9. Burcin Bostan-Korpeoglu,Adnan Yazici ,A Fuzzy Petri Net Model For Intelligent Database, Data & Knowledge Engineering (2006), Elsevier,2006.
  10. A. Karimov, S. Moharrami, " Automatic Classification with Neural Networks Using New Decision Rule ", International Journal of Applied Mathematics & Statistics, Vol. 19, No. D10, 2010, pp. 90-96.
  11. A. Karimov, S. Moharrami, " On Approaches To Automatic Classification Of Object States Based On New Decision Rule", in First International Conference on Soft Computing Technologiesin Economy, November 2007,Baku,Azerbaijan, Vol. 1, pp. 107-116.
  12. K. Jensen, "Colored Petri nets (CPN) ", http://www.daimi.au.dk.
  13. Burcin Bostan-Korpeoglu,Adnan Yazici ,A Fuzzy Petri Net Model For Intelligent Database, Data & Knowledge Engineering (2006), Elsevier,2006.
  14. Motameni,H,et al "Using Markov Theory For Deriving Non-Functional Parameters On Transformed Petri Net From Activity Diagram]" ,proc of software engineering conference (russia), 16-17 November 2006,Moscow, Russi, (presented).
  15. Перевод статьи IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 1, No 3, January 2012 ISSN (Online): 1694-0814 www.IJCSI.org
  16. Сети Петри