Взаимосвязь процессов и ресурсов

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

Пусть некоторый процесс p_а, расположенный в графе Г_t на уровне U ₁ порождает процессы p_с и p_b, расположенные соответственно на уровнях U ₂ и U ₃. При этом для нормальной работы процесса p_а требуются ресурсы r ₁, r ₂, r ₃, где r ₃ – ресурс типа «память» с сегментами r ₃, r ₃₂, r _33. Для работы процессора p_b требуются ресурсы r ₁, r ₄, r ₅, а для p_c – ресурсы r ₁, r ₆. Необходимо построить граф Г_t= < Г_t^p (p_a) ,Г_t^r (p_a)>.

Требуемый граф изображен на рис. 6.1. Ребра , указывают, что процессы p_b и p_с являются потомками p_а; ребра s _а, s _b, s _c, устанавливают связи между вершинами p_a, p_b, p_c, соответствующими им графами Г_t^r (p_a), Г_t^r (p_b), Г_t^r (p_c). Ребро указывает, что процессы p_b и p_с используют общий ресурс r ₁, ребра {s₁ ^a, s₂ ^a }, {s₁ ^b, s₂ ^b }, {s₁ ^c, s₂ ^c } соединяют ресурсы процессов p_a, p_b, p_c соответственно. Ребра s _j, j= 1,...,13 устанавливают отношения иерархического подчинения в графе ресурсов Г_t^r(p_a).

Над графом Г_t можно выполнить следующие базовые операции: F = { f ₁, f ₂, f ₃, f ₄, f ₅, f ₆}, где

f ₁ – добавление новой вершины σ_j в граф Г_t (например, при формировании процесса p_j, порождаемого процессом p_i);

Рис. 6.1. Граф Г_t

f ₂ – установление связи (добавление ребра) между вершиной σ _j и графом Г_t (например, добавление ребра (p_i, p_j)) после выполнения операции f ₁ над процессами p_i и p_j;

f ₃ – удаление элемента σ _i из графа Г_t (например, уничтожение процесса p_i);

f ₄– удаление связей (ребер) между вершиной σ _i и (Г_t\ σ _l); например, после применения операции f ₃ в случае уничтожения процесса p_j уничтожается весь подграф Г_t^r (p_i) и все связи Г_t^p\ Г_t^p (p_i) с Г_t^p (p_i);

f ₅ – изменение состояния S (σ _l) элемента σ_l (например, при переводе какого-то процесса p_i из активного состояния в блокированное);

f ₆ – изменение значения m (σ _l) элемента σ_l (например, при изменении имени процесса).

Каждая операция над графом Г_t осуществляется с помощью преобразования правил из множества Е, т.е. если σ _i ^* => Г_t (σ _i) для некоторого y_iÌE, то, заменив y_i на y_kÌE, мы получим, что σ _i^* => Г_t^' (σ_i). При этом Г_t^' (σ _i) = f_g (Г_t (σ _i)), f_g – некоторая операция над графом Г_t. Правила замены y_i на y_k в зависимости от f_g приведены в таблице.

Операция	yi	yk
f 1(σ in+ 1), f 2(σ in+ 1)	σ i → σi1 … σ in	σ i → σ i 1σ i 2 … σ in σ in+ 1
f 3(σ in), f 4(σ in)	σ i → σ i 1 … σ in	σ i → σ i 1σ i 2 … σ in σ in- 1
f 5(σ i, )	σ i = (σ i^m, σ i^x, σ i^s)	σ i = (σ i^m, σ i^x, )
f 6(σ i,, )	σ i = (σ i^m, σ i^x, σ i^s)	σ i = (), σ i^x, σ i^s)

Рассмотрим изложенное выше на некоторой ситуации.

Пусть множество правил Е для модели М имеет следующий вид:

σ₀ → σ₁, σ₂, σ₃, 2, 0,0

σ₁ → σ₁₁, σ₁₂, 3, 0,0

σ₂ → σ₁₂, σ₂₂, σ₂₃, 4, 0,0

σ₃ → σ₁₁, σ₂₃, σ₃₃, конец, 0,0

Необходимо построить граф Г_t^p (σ₀) = Г_t. Хотя для каждого графа Г_t^p (σ _j) j= 0,1,2,3,11,12,22,23,33 существует свой граф ресурсов Г_t^r (σ _j), рассматривать их здесь не будем.

Граф Г_t, порождаемый из σ₀ с помощью правил из данного множества Е, представлен на рис. 6.2. Видно, что вершины σ₁ и σ₂ используют одновременно элемент σ₁₂, а вершины σ₁ и σ₃ используют одновременно элемент σ₁₁. Введенный формализм позволяет анализировать и оценивать реальные ОС, а также рассматривать вопросы проектирования ОС, вне зависимости от структуры реальной вычислительной установки.

Рис. 6.2. Граф Г_t^p

Отсюда условие параллельного выполнения процессов: если Г_t^p (σ _i) = Øи Г_t^r (σ _i)=Ø для некоторых i, то соответствующие им σ _i могут обрабатываться одновременно (в параллельном режиме). Рассматривая системные модули ОС (УЗ, УЦП и др.) как элементы М, порождаемые из начального элемента σ, получаем общую модель описания и функционирования ОС.

Дата добавления: 2014-12-29