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

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

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

Y _j,:s _i ®s _j ¹,s _j ²,…,s _j^в, y_j ¹, y_j ², y_j ³,

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

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

Пусть каждый элемент 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 ¹s _j ²…s _j^в (т.е.s _j Þ φ _j), если к s _j применимо некоторое правило из Е.

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

Обозначим через Г_t^p (p_i)граф процессов, порождаемый процессом р_i Î Р, P есть подмножество s _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_а. Неориентированное ребро s _аb=(p_a,p_b) показывает, что существует связь между процессами p_а и p_b. Например, s _аb говорит о том, что p_а и p_b используют общий ресурс r. Вершинами графа Г_t^r будут некоторые ресурсы r_j Î R, R Ìs, которые могут быть соединены между собой ориентированными и неориентированными ребрами. Ориентированное ребро указывает, что ресурс r_b является потомком ресурса r_а. Например, если r_а определяет память, то r_b – это один из сегментов памяти r_а.

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