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

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

Пусть Т=[t₀,t_k] – время функционирования ОС (от t₀ – времени инициирования и загрузки системы до t_k – времени ее уничтожения). Структуру ОС в некоторый момент времени tТ можно представить с помощью графа Г_t, вершинами которого являются элементы множеств процессов P={p₀,p₁,…,p_n} и ресурсов R={r₀,r₁,…,r_g}, а ребра устанавливают связи между вершинами, Р и R − конечные непустые множества. Так как ОС является динамически изменяющейся системой, то в некоторые моменты времени t₁,t₂T, t₁t₂ ее структура может быть представлена соответственно в виде графов Г_t1 и Г_t2. Проследим изменение Г_t – графа, отображающего структуру ОС, в любой момент времени tТ. Выделим в некоторое множество  все возможные вершины и ребра, которые могут быть получены на промежутке времени [t₀,t_k]. В дальнейшем каждый элемент множества  (вершину или ребро) будем обозначать как _j, j1. Определим множество E как совокупность правил, фиксирующих изменение структуры графа Г_t для любого tТ. Каждое правило из множества E имеет вид

Y _j,: _i_j¹, _j²,…, _j^в, y_j¹, y_j², y_j³,

где y_j, – номер правила, i=1,2,3 _j, _j¹, _j²,…, _j^в  означает, что элемент _j в момент времени tТ заменяется на набор элементов _j¹, _j²,…, _j^в, y_j¹, y_j² – соответственно номера правил, на которые осуществляется переход, если элемент _j активен или блокирован, y_j³ указывает правило, определяющее для заданного _j либо весь граф ресурсов (если _j – процесс), либо альтернативный ресурс (если _j – ресурс). Обозначим через Y – множество номеров правил из Е. Пусть ₀ – некоторый начальный процесс, инициирующий работу системы. Тогда M – формальная модель операционной системы, которую можно определить следующим образом:

М=[Т,,Е,Y, ₀].

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

[m(_j),x(_j),S(_j)],

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

Примем, что некоторый элемент _j в момент времени t порождает цепочку элементов φ_i,=_j¹_j²…_j^в (т.е. _j φ_j ), если к _j применимо некоторое правило из Е.

Будем говорить, что граф Г_t порождается вершиной _j (т.е. _j^*Г_t(_j)=Г_t), если существует набор правил y₁, y₂, …,y_n , для которых справедливо утверждение _j φ₁φ₂φ_l=Г_t(_j), причем на каждом шаге φ_i-1=φ_i выполняется только одно правило из Е.

Обозначим через Г_t^p(p_i) граф процессов, порождаемый процессом р_iР, P есть подмножество _b в некоторый момент времени t. Если p₀ – начальный процесс, то Г_t^p(p_i) Г_t^p(p₀), p_iР, i=1,2,…,n.

Полагаем, что с каждой вершиной – процессом p_j  Г_t^p (p₀) связан некоторый граф Г_t^r(p_j) ресурсов, требуемых для нормального развития p_j, j=0,1,2,...,n. Тогда граф Г_t определяется как Г_t=<Г_t^p,Г_t^r>, где Г_t^p = Г_t^p (P₀), Г_t^r = Г_t^r (P₀).

Вершины графа Г_t^p (т.е. процессы) могут быть соединены ориентированными или неориентированными ребрами. Ориентированное ребро указывает, что вершина p_b находится в отношении иерархического подчинения к вершине p_а, т.е. процесс p_b является потомком процесса p_а. Неориентированное ребро _аb=(p_a,p_b) показывает, что существует связь между процессами p_а и p_b. Например, _аb говорит о том, что p_а и p_b используют общий ресурс r. Вершинами графа Г_t^r будут некоторые ресурсы r_jR, R, которые могут быть соединены между собой ориентированными и неориентированными ребрами. Ориентированное ребро указывает, что ресурс r_b является потомком ресурса r_а. Например, если r_а определяет память, то r_b – это один из сегментов памяти r_а.

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