Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Учебник по ОС.doc
Скачиваний:
5
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆

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

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

Пусть некоторый процесс 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а; ребра а,b, c, устанавливают связи между вершинами pa, pb, pc, соответствующими им графами Гtr(pa), Гtr(pb), Гtr(pc). Ребро указывает, что процессы pb и pс используют общий ресурс r1, ребра {1a, 2a}, {1b, 2b}, {1c, 2c} соединяют ресурсы процессов pa, pb, pc соответственно. Ребра j, 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 ) для некоторого yiE, то, заменив yi на ykE, мы получим, что σi* => Гt'( σi ). При этом Гt'( σi )= fg(Гt( σi )), fg – некоторая операция над графом Гt. Правила замены yi на yk в зависимости от fg приведены в таблице.

Операция

yi

yk

f1( σin+1 ), f2( σin+1 )

σi → σi1 … σin

σi → σi1 σi2 … σin σin+1

f3( σin ), f4( σin )

σi → σi1 … σin

σi → σi1 σi2 … σin σin-1

f5( σi, )

σi = (σim, σix, σis)

σi = (σim, σix, )

f6( σi, , )

σi = (σim, σix, σis)

σi = ( ), σix, σis)

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

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

σ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 могут обрабатываться одновременно (в параллельном режиме). Рассматривая системные модули ОС (УЗ, УЦП и др.) как элементы М, порождаемые из начального элемента σ, получаем общую модель описания и функционирования ОС.