Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Формальная модель операционной системы




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

Пусть Т= [ t 0 ,tk ] – время функционирования ОС (от t 0 – времени инициирования и загрузки системы до tk – времени ее уничтожения). Структуру ОС в некоторый момент времени t Î Т можно представить с помощью графа Гt, вершинами которого являются элементы множеств процессов P= { p 0 ,p 1 ,…,pn } и ресурсов R= { r 0 ,r 1 ,…,rg }, а ребра устанавливают связи между вершинами, Р и R − конечные непустые множества. Так как ОС является динамически изменяющейся системой, то в некоторые моменты времени t 1 ,t 2Î T, t 1¹ t 2 ее структура может быть представлена соответственно в виде графов Гt 1 и Гt 2. Проследим изменение Гt – графа, отображающего структуру ОС, в любой момент времени t Î Т. Выделим в некоторое множество s все возможные вершины и ребра, которые могут быть получены на промежутке времени [ t 0 ,tk ]. В дальнейшем каждый элемент множества s (вершину или ребро) будем обозначать как s j, j ³1. Определим множество E как совокупность правил, фиксирующих изменение структуры графа Гt для любого t Î Т. Каждое правило из множества E имеет вид

Y j,:s i ®s j 1,s j 2,…,s jв, yj 1, yj 2, yj 3,

где yj, – номер правила, i =1,2,3 s j, s j 1,s j 2,…,s jв Î s означает, что элемент s j в момент времени t Î Т заменяется на набор элементов s j 1,s j 2,…,s jв, yj 1, yj 2 – соответственно номера правил, на которые осуществляется переход, если элемент s j активен или блокирован, yj 3 указывает правило, определяющее для заданного s j либо весь граф ресурсов (если s j – процесс), либо альтернативный ресурс (если s j – ресурс). Обозначим через Y – множество номеров правил из Е. Пусть s0 – некоторый начальный процесс, инициирующий работу системы. Тогда M – формальная модель операционной системы, которую можно определить следующим образом:

М= [ Т, s ,Е,Y, s0].

Пусть каждый элемент s j Îs характеризуется следующей тройкой:

[ m (s j) ,x (s j) ,S (s j)],

где m (s j) – имя элемента; x (s j) – тип элемента (процесс, процессор, память и т.д.); S (s j) определяет состояние элемента (активен, блокирован и т.д.).

Примем, что некоторый элемент s j в момент времени t порождает цепочку элементов φ i,=s j 1s j 2…s jв (т.е.s j Þ φ j), если к s j применимо некоторое правило из Е.

Будем говорить, что граф Гt порождается вершиной s j (т.е.s j* Þ Гt (s j) t), если существует набор правил y 1, y 2, …,yn, для которых справедливо утверждение s j Þ φ1 Þ φ2 Þ φ lt (s j), причем на каждом шаге φ i- 1 = φ i выполняется только одно правило из Е.

Обозначим через Гtp (pi)граф процессов, порождаемый процессом рi Î Р, P есть подмножество s b в некоторый момент времени t. Если p 0 – начальный процесс, то Гtp (piГtp (p 0), pi Î Р, i= 1, 2 ,…,n.

Полагаем, что с каждой вершиной – процессом pj Î Гtp (p0) связан некоторый граф Гtr (pj) ресурсов, требуемых для нормального развития pj, j= 0,1,2 ,...,n. Тогда граф Гt определяется как Гt= < Гtptr >, где Гtp = Гtp (P0), Гtr = Гtr (P 0).

Вершины графа Гtp (т.е. процессы) могут быть соединены ориентированными или неориентированными ребрами. Ориентированное ребро указывает, что вершина pb находится в отношении иерархического подчинения к вершине pа, т.е. процесс pb является потомком процесса pа. Неориентированное ребро s аb=(pa,pb) показывает, что существует связь между процессами pа и pb. Например, s аb говорит о том, что pа и pb используют общий ресурс r. Вершинами графа Гtr будут некоторые ресурсы rj Î R, R Ìs, которые могут быть соединены между собой ориентированными и неориентированными ребрами. Ориентированное ребро указывает, что ресурс rb является потомком ресурса rа. Например, если rа определяет память, то rb – это один из сегментов памяти rа.

Будем считать, что все вершины графа Гt расположены по уровням, причем на нулевом уровне находится единственная вершина p 0. На уровнях Ui³ 1 помещаем вершины, каждая из которых зависит хотя бы от одной вершины предыдущего уровня Ui- 1 и не зависит ни от одной вершины последующих уровней. Одноуровневые вершины не зависят друг от друга.




Поделиться с друзьями:


Дата добавления: 2014-12-29; Просмотров: 540; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.