Лекция: Формальная модель операционной системы
Для упрощения понимания работы различных блоков операционной системы имеет смысл ввести ее формальную модель, функционирующую на некоторой абстрактной вычислительной системе.
Пусть Т=[t0,tk] – время функционирования ОС (от t0– времени инициирования и загрузки системы до tk– времени ее уничтожения). Структуру ОС в некоторый момент времени tÎТ можно представить с помощью графа Гt, вершинами которого являются элементы множеств процессов P={p0,p1,…,pn} и ресурсов R={r0,r1,…,rg}, а ребра устанавливают связи между вершинами, Р и R − конечные непустые множества. Так как ОС является динамически изменяющейся системой, то в некоторые моменты времени t1,t2ÎT, t1¹t2 ее структура может быть представлена соответственно в виде графов Гt1 и Гt2. Проследим изменение Гt – графа, отображающего структуру ОС, в любой момент времени tÎТ. Выделим в некоторое множество s все возможные вершины и ребра, которые могут быть получены на промежутке времени [t0,tk]. В дальнейшем каждый элемент множества s (вершину или ребро) будем обозначать как sj, j³1. Определим множество E как совокупность правил, фиксирующих изменение структуры графа Гtдля любого tÎТ. Каждое правило из множества E имеет вид
Yj,:si®sj1,sj2,…,sjв,yj1,yj2,yj3,
где yj, – номер правила, i=1,2,3 sj, sj1,sj2,…,sjв Îs означает, что элемент sj в момент времени tÎТ заменяется на набор элементов sj1,sj2,…,sjв, yj1,yj2 – соответственно номера правил, на которые осуществляется переход, если элемент sj активен или блокирован,yj3 указывает правило, определяющее для заданного sj либо весь граф ресурсов (если sj – процесс), либо альтернативный ресурс (если sj – ресурс). Обозначим через Y – множество номеров правил из Е. Пусть s0– некоторый начальный процесс, инициирующий работу системы. Тогда M – формальная модель операционной системы, которую можно определить следующим образом:
М=[Т,s, Е,Y, s0].
Пусть каждый элемент sj Îs характеризуется следующей тройкой:
[m(sj),x(sj),S(sj)],
где m(sj) – имя элемента; x(sj) – тип элемента (процесс, процессор, память и т.д.); S(sj) определяет состояние элемента (активен, блокирован и т.д.).
Примем, что некоторый элемент sj в момент времени t порождает цепочку элементов φi,=sj1sj2…sjв (т.е.sj Þφj), если к sjприменимо некоторое правило из Е.
Будем говорить, что граф Гt порождается вершиной sj (т.е.sj*ÞГt(sj)=Гt), если существует набор правил y1,y2,…,yn, для которых справедливо утверждение sj Þφ1Þφ2Þφl=Гt(sj), причем на каждом шаге φi-1=φi выполняется только одно правило из Е.
Обозначим через Гtp(pi)граф процессов, порождаемый процессом рiÎР, P есть подмножество sbв некоторый момент времени t. Если p0– начальный процесс, то Гtp(pi)ÍГtp(p0), piÎР, i=1,2,…,n.
Полагаем, что с каждой вершиной – процессом pj ÎГtp (p0) связан некоторый граф Гtr(pj) ресурсов, требуемых для нормального развития pj, j=0,1,2,...,n. Тогда граф Гt определяется как Гt=<Гtp, Гtr>, где Гtp =Гtp (P0), Гtr =Гtr (P0).
Вершины графа Г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 расположены по уровням, причем на нулевом уровне находится единственная вершина p0. На уровнях Ui³1 помещаем вершины, каждая из которых зависит хотя бы от одной вершины предыдущего уровня Ui-1 и не зависит ни от одной вершины последующих уровней. Одноуровневые вершины не зависят друг от друга.