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

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

Пусть Т=[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ÎТ. Выделим в некоторое множество 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 и не зависит ни от одной вершины последующих уровней. Одноуровневые вершины не зависят друг от друга.