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

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

Пусть некоторый процесс pа, расположенный в графе Гt на уровне U1 порождает процессы pс и pb, расположенные соответственно на уровнях U2 и U3. При этом для нормальной работы процесса pа требуются ресурсы r1, r2,r3, где r3 – ресурс типа «память» с сегментами r3,r32,r33. Для работы процессора pb требуются ресурсыr1,r4,r5, а для pc – ресурсы r1,r6. Необходимо построить граф Гt=<Гtp(pa), Гtr(pa)>.

Требуемый граф изображен на рис. 6.1. Ребра, указывают, что процессы pb и pс являются потомками pа; ребра sа, sb, sc, устанавливают связи между вершинами pa, pb, pc, соответствующими им графами Гtr(pa), Гtr(pb), Гtr(pc). Ребро указывает, что процессы pb и pс используют общий ресурс r1, ребра {s1a, s2a}, {s1b, s2b}, {s1c, s2c} соединяют ресурсы процессов pa, pb, pc соответственно. Ребра sj, j=1,...,13 устанавливают отношения иерархического подчинения в графе ресурсов Гtr(pa).

Над графом Гt можно выполнить следующие базовые операции: F = {f1, f2, f3, f4, f5, f6}, где

f1 – добавление новой вершины σj в граф Гt (например, при формировании процесса pj, порождаемого процессом pi);

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

f2 – установление связи (добавление ребра) между вершиной σj и графом Гt (например, добавление ребра (pi, pj)) после выполнения операции f1 над процессами pi и pj;

f3 – удаление элемента σi из графа Гt (например, уничтожение процесса pi);

f4– удаление связей (ребер) между вершиной σiи ( Гt\σl ); например, после применения операции f3 в случае уничтожения процесса pj уничтожается весь подграф Гtr(pi) и все связи Гtp\ Гtp (pi) с Гtp (pi);

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

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

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

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

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

σ0→ σ1, σ2, σ3, 2, 0,0

σ1 → σ11, σ12, 3, 0,0

σ2 → σ12, σ22, σ23, 4, 0,0

σ3 → σ11, σ23, σ33, конец, 0,0

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

Граф Гt, порождаемый из σ0с помощью правил из данного множества Е, представлен на рис. 6.2. Видно, что вершины σ1 и σ2 используют одновременно элемент σ12, а вершины σ1 и σ3 используют одновременно элемент σ11. Введенный формализм позволяет анализировать и оценивать реальные ОС, а также рассматривать вопросы проектирования ОС, вне зависимости от структуры реальной вычислительной установки.

Рис. 6.2. Граф Гtp

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