Щеглов А.Ю. Защита компьютерной информации от несанкционированного доступа

Подождите немного. Документ загружается.

Глава

18.

Разработка и оптимизация механизма уровневого контроля

ального

времени, за счет реализации эффективного управления ис-

пользованием вычислительного ресурса заявками в результате вве-

дения приоритетного обслуживания. Обычно это является «узким

местом» системы. Получаемый выигрыш в производительности си-

стемы в целом здесь может составить десятки раз, возрастая при

увеличении числа типов заявок (очередей) в системе М.

2. Получаемый от реализации приоритетного расписания выигрыш

снижается при увеличении коэффициента k, или при опережаю-

щем росте

lp3in

над

7^,

что определяет переход к классу сосредо-

точенных систем.

3. При k > 1 из (18.1) имеем

=\,

то есть отсутствует

выигрыш как таковой. Это

может"

иметь место для некоторых при-

ложений сосредоточенных систем,

когда

7^.

В этом случае

теряет актуальность задача при-

оритетного обслуживания заявок с

целью эффективного использова-

ния ресурса.

Нетрудно показать, что предельным

случаем системы, где наиболее эффек-

тивно включение приоритетного обслу-

живания и «узким местом» которой бу-

дет общий вычислительный ресурс

ресурс,

можно считать

многозадачную

рис

1дг

Ил

ация

операционную систему реального вре- выигрыша в производительности

мени, т.е. именно те приложения, ко- системы реального времени при

торые

нами рассматриваются в работе. реализации приоритетного

обслуживания

Выводы

С учетом сказанного можем сформулировать цель назначения приорите-

тов при обслуживании запросов по расписанию для систем реального вре-

мени. При этом помним, что в этих

системах

имеется общий ресурс и

именно он является «узким местом».

Итак, цель реализации приоритетного обслуживания в системах реаль-

ного времени состоит в перераспределении прав между заявками (очере-

дями заявок) на доступ к ресурсу в соответствии с заданными ограниче-

ниями времени

реакции

системы на входное воздействие. Выполнение

данных ограничений при минимальной производительности ресурса до-

стигается при выполнении условия:

m = \,...,M. Таким образом,

условие

можно считать условием оптимальности приоритетной

дисциплины

обслуживания реального времени.

311

Часть V. Контроль корректности функционирования механизмов защиты

18.3. Реализация приоритетных

расписаний в современных ОС

Принципы приоритетного обслуживания заявок

в современных универсальных ОС

Прежде чем перейти к дальнейшему рассмотрению вопросов синтеза

приоритетных расписаний для рассматриваемых приложений, рассмотрим,

каким образом можно реализовать обслуживание заявок по расписаниям

в современных ОС.

В большинстве современных универсальных ОС алгоритм передачи управ-

ления (системных ресурсов центрального процессора) базируется на меха-

низме назначения относительных приоритетов. В соответсвии с этим меха-

низмом каждой программе может быть назначен свой приоритет. Диапазон

приоритетов в разных ОС колеблется от 6 до нескольких десятков.

Диспетчер задач распределяет кванты времени между задачами в соот-

ветствии с их приоритетами. При этом ресурсы центрального процессо-

ра будут переданы той задаче, у которой более высокий приоритет. При

этом до истечения кванта выданного ей процессорного времени, програм-

ма не может быть прервана (если только сама не отдаст управление). Та-

ким образом, речь идет об обслуживании заявок по дисциплине с отно-

сительными приоритетами. Эта дисциплина не позволяет корректно

реализовать расписания реального времени.

Если же у всех текущих задач приоритеты равны, то в общем случае

ресурсы центрального процессора будут передаваться задачам в порядке

их поступления (бесприоритетная дисциплина обслуживания, но опять

же не реального времени).

Основу реализации приоритетного расписания на базе дисциплины обслу-

живания с относительными приоритетами составляет изменение относи-

тельных приоритетов по расписанию. Другими словами, в каждый момент

времени реализуется дисциплина обслуживания с относительными приори-

тетами, которые изменяются в процессе функционирования системы (при

каждом предоставлении ресурса задаче). Таким образом и реализуется

приоритетное расписание. Возникает вопрос: «Какое средство (задача) будет

осуществлять перераспределение относительных приоритетов по расписа-

нию?» Поиском ответа мы и займемся в следующем пункте.

Подход к реализации в современных ОС управления

по приоритетным расписаниям

Рассмотрим подход к реализации в ОС передачи управления в соответ-

ствии с приоритетным расписанием. Данный подход состоит в следующем:

» Выделяются задачи, реализующие собственно защиту от НСД механиз-

мом

уровневого

контроля списков. Им назначается высокий относитель-

ный приоритет.

312

Глава

18.

Разработка и оптимизация механизма уровневого контроля

» Среди данных задач выделяется одна, осуществляющая диспетчериза-

цию заявок (передачу полномочий между заявками на занятие ресурса)

- ей назначается максимальный относительный приоритет.

« Выделяются прикладные задачи. Им назначается низкий приоритет.

Таким образом, из очереди будет выбираться всегда задача, имеющая мак-

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

Получив управление, задача может либо занять вычислительный ресурс,

либо передать его на квант

вре-

-I

-птптп-

мени (обозначим это время как

^квант)

прикладным задачам. Т.е.

задача, реализующая защиту от

НСД, будет распределять время

между собой и прикладными за-

Рис. 18.2. Схема

передачи

дачами (реализовывать расписа-

управления

между задачами

ние).

Схема такой передачи уп-

равления приведена на рис.

18.2.

На схеме обозначен входной поток задач

Л.

Прибор постановки в оче-

редь (А) выбирает из входного потока задачи и распределяет их по оче-

редям в соответствии с их приоритетами.

В случае, если задача принудительно отдала управление на заданное

время, прибор постановки отложит размещение этой задачи в очередь.

Прибор выбора задачи из очереди (В) выбирает задачи из очередей в со-

ответствии с их приоритетами и передает их на обслуживание в цент-

ральный процессор (ЦП).

На схеме задачам одного приоритета выдается одна очередь, из которой

происходит выборка опять же в соответствии с расписанием.

Выводы

Подытожить вышесказанное можно следующими высказываниями:

1. В современных универсальных ОС основу подхода к приоритетному

обслуживанию заявок на контроль событий в реальном времени мо-

жет составлять обслуживание с динамическими относительными при-

оритетами, изменяемыми по расписанию, при каждом занятии вычис-

лительного ресурса.

2. Посредством реализации рассмотренного подхода, в большинстве

современных ОС можно реализовывать расписания (обслуживание

в реальном времени) любого уровня сложности. При этом переда-

чей управления занимается уже не диспетчер задач ОС (он осуще-

ствляет это на более низком уровне), а тот механизм, который

специально наделен такими функциями.

313

Часть V. Контроль корректности функционирования механизмов защиты

18.4. Построение и использование

эффективных приоритетных расписаний

18.4.1. Основы построения приоритетных расписаний

Основные понятия

Идея рассматриваемого подхода состоит в реализации дисциплин обслу-

живания реального времени с передачей прав по расписанию (ДОР), по

средством смены относительных приоритетов

(ДООП)

по расписанию [20].

При этом система должна быть построена таким образом, чтобы в лю-

бой момент времени

относительный приоритет (ОП) не мог совпасть

у заявок из нескольких очередей. Если данное условие не будет выпол-

нено, то в системе неминуем конфликт при занятии ресурса, т.к. несколь-

ко абонентов одновременно получат право занять ресурс после

его

осво-

бождения.

Для описания ДООП используем матрицу приоритетов (МП), пред-

ставляющую собою квадратную матрицу

£?

[#,;,]

размерности

МхМ

по числу М абонентов. Элемент матрицы

задает ОП заявки

по

отношению к

(здесь и далее имеется в виду очередь или, соответ-

ственно, класс заявок):

«О»—

нет приоритета, «1»

есть приоритет.

Например, первая строка первой таблицы

«0111»

означает, что пер-

вая заявка имеет более высокий приоритет чем вторая, третья и чет-

вертая заявки. Для описания ДОР (в общем случае

ДОСП)

исполь-

зуем граф изменения матрицы ОП в моменты времени

— моменты

занятия ресурса в соответствии с расписанием.

На рис 18.3 представлен пример графа бесприоритетной ДОР, реали-

зуемой методом динамической смены ОП, для случая М =

цикл рас-

писания которой имеет вид: (1, 2, 3, 4). Соответственно, в каждый мо-

мент времени состояние системы описывается своей МП.

Бесприоритетность расписания обеспечивается тем, что каждый абонент

входит в расписание равное число раз. Причем это число в общем слу-

чае может быть более одного, например (1, 1, 2, 2, 3, 3, 4, 4).

ill

г-

1234

i/i

0111

0 0 1

—

0001

0000

1234

i/i

0000

1 0 1

1—

»2

1001

1000

1234

i/j

0100

000

—

1101

1100

1234

0110

0010

—

оооо

1110

Рис. 18.3. Пример графа бесприоритетной дисциплины обслуживания

314

Глава

18.

Разработка и оптимизация механизма

уровневого

контроля

Требования к матрице приоритетов

Элементы МП должны удовлетворять следующим требованиям:

<7/=>

т.к.

между заявками одного класса

не

могут быть установле-

ны приоритеты;

» если

q,j

= 1 , то

= 0 , т.е., если заявки класса

имеют приоритет по

отношению к заявкам класса j, то последние не могут иметь приори-

тет по отношению к заявкам

* в матрице приоритетов не должны совпасть любые две строки

любые два

столбца

у,

;';

\,...,

М,

i*m,

j,j'=\,...,M,

j".

В графе смены МП (в цикле расписания), по крайней мере, по одному

разу должны присутствовать МП, задающие высший ОП каждого из М

классов заявок.

Правило высших относительных приоритетов

Для реализации приоритетной ДОР в цикле расписания по крайней мере

двум классам заявок высший относительный приоритет должен присва-

иваться различное число раз, например (1, 2, 1, 3, 1, 4).

В противном случае получим совпадение значений

г0т

т.е. при совпа-

дении значений параметров

грз/а

получаем равный приоритет заявок -

совпадают

грСт

Правило изменения относительных приоритетов

Изменение ОП заявок по расписанию в процессе функционирования

системы должно быть реализовано по следующему правилу.

Относительные приоритеты (ОП) в рамках ДОР однозначно задаются рас-

писанием, где в каждый момент времени

приоритет заявок соответ-

ствует порядку передачи полномочий, исключая повторные передачи прав

одной очереди в цикле ОР (эта возможность реализуется изменением

длины кванта времени). Например, для расписания

(1,

2, 1, 3) в момент

времени

}

-- ОП [1, 2, 3], в момент времени

(

-- [2, 1, 3], в момент

времени

(

— [1, 3, 2], в

— [3, 1, 2].

Для дисциплин обслуживания с динамическими ОП, изменяемыми по рас-

писанию, функция изменения приоритета заявки т,

= \,...,М имеет вид:

где:

- исходный ОП заявки поступающей в момент t", соответству-

ющий

5-му

состоянию цикла расписания, длиной

Да

т(/

— приращение приоритета заявки, получаемое при смене состо-

яний цикла расписания

= \,...,G (может иметь отрица-

тельные значения).

315

Часть V. Контроль корректности функционирования механизмов защиты

Для заявок, обслуживаемых с ОП, для

Acc

mrf

= 0 и для

s =

{,...,G,

= const.

Режимы использования относительного приоритета

Рассмотренный подход позволяет комбинировать в одной системе обслу-

живание заявок и по расписаниям и с относительным приоритетом (по-

средством смены относительных приоритетов). Естественно, что если

какой-либо заявке относительный приоритет не изменять в процессе

функционирования системы, то запросы данной заявки будут тем самым

исключены из расписания. В дальнейшем будем обозначать дисциплину

осблуживания

со смешанными приоритетами (относительного и реаль-

ного времени) квадратными скобками.

Можно выделить два режима использования относительного приори-

тета, которые определяются его отношением к приоритетам реально-

го времени:

Первый режим предполагает задание относительного приоритета за-

явки относительно заявок, обслуживаемых в реальном

времени,

на-

пример, [1, (2, 3,

4)].

Данный режим может выделяться для внеочер-

дного обслуживания каких-либо заявок (в нашем примере заявка 1

всегда приоритетнее, чем заявки 2, 3, 4, которые обслуживаются меж-

ду собой по бесприоритетному расписанию).

Этот режим может использоваться для задания относительного при-

оритета задаче, осуществляющей диспетчеризацию заявок.

» Второй режим предполагает задание относительного приоритета зая-

вок реального времени относительно остальных заявок, например,

[(1,

2, 3), 4] (в нашем примере заявка 4 всегда менее приоритетна,

чем заявки 1, 2, 3, которые обслуживаются между собой по бесприо-

ритетному расписанию).

Данный режим может выделяться для фонового обслуживания каких-

либо заявок (в нашем примере заявка 4 будет обслуживаться в фоно-

вом режиме, например, в фоновом режиме могут обслуживаться заяв-

ки приложений).

18.4.2. Теоретические основы синтеза

приоритетных расписаний

Детерминированная задача синтеза расписаний реального времени

Выше отмечалось, что под приоритетным понимается расписание, в цикле

которого различные классы или очереди заявок встречаются различное чис-

ло раз. Возникает вопрос сравнения между собой приоритетных расписаний

316

Глава

18.

Разработка и оптимизация механизма уровневого контроля

с целью выработки требований к их оптимальности. Например, рассмотрим

два расписания (1, 1, 2, 3) и (1, 2, 1, 3). В обоих расписаниях первый абонент

имеет более высокий приоритет (в 2 раза чаще встречается в цикле, чем вто-

рой и третий абоненты). Возникает вопрос — одинаковы или различны эти

расписания с точки зрения эффективности их применения в системах реаль-

ного времени. Попытаемся проанализировать данный вопрос и выработать

требования к оптимальному приоритетному расписанию [22].

Пусть имеем R различных приоритетов заявок в системе, обслуживаемых

по

расписанию.

Соответственно,

r =

l,...,R,u

заявок

имеют

равный

приоритет

\,...,M

,т'

\,...,М

Таким

об-

разом, система содержит М очередей заявок, которым соответствует R

уровней приоритетов.

Детерминированная задача синтеза расписаний реального времени мо-

жет быть сформулирована следующим образом :

М\1\Т

ои>г

max,

Т»*,,

гоп,

\,...,M

r =

\,...,R,

где

ОШг

—

характеристика обслужи-

вания

/я-й

очереди заявок

r-го

приоритета,

го1Яг

- ограничение, накла-

дываемое на время обслуживания заявки системой, функционирующей

в реальном масштабе времени.

Оптимальное приоритетное расписание и радиальный граф

С учетом сформулированной задачи синтеза расписаний реального вре-

мени дадим определение канонического (в данном случае — оптималь-

ного)

расписания.

Под каноническим (оптимальным) расписанием будем понимать расписа-

ние, обеспечивающее минимальные значения характеристик

гаШг

в рам-

ках заданного разбиения М классов заявок на R уровней приоритета,

получаемое поочередной передачей прав очередям заявок в рамках ра-

диального графа.

Под радиальным графом передачи прав понимается граф, удовлетворяю-

щий следующим условиям:

» Этот граф содержит

вершин приоритета r, r = \,...,R, причем в

каждую вершину нижестоящего приоритета входит только одна дуга

от одной вершины вышестоящего приоритета.

Из каждой вершины всех приоритетов, кроме

Л-го,

выходит

r+l

]

дуг, где [а] — есть большее целое числа а.

* Все

вершины

приоритета R соединяются дугой с вершиной приорите-

та 1 (из вершин R выходит только одна дуга) — в этом случае дуга

направлена в сторону вершины 1, в то время как в остальных случаях

дуга направлена в вершину, соответствующую очереди заявки с более

низким приоритетом.

Радиальный граф передачи прав представлен на рис. 18.4.

317

Часть V. Контроль корректности функционирования механизмов защиты

Уровень Число

приоритета

вершин

Рис. 18.4. Радиальный граф передачи прав на занятие ресурса

Радиальный граф, у которого по крайней мере одна вершина

/--го

(не

R-то)

уровня приоритета соединена только с одной вершиной приоритета уров-

ня

+ 1, назовем вырожденным. Соединение двух вершин одной дугой

является альтернативным способом задания равного приоритета двум

абонентам системы. Под предельно вырожденным понимаем граф, в ко-

тором из каждой вершины только одна дуга выходит и в каждую верши-

ну только одна дуга входит — этот граф задает бесприоритетное распи-

сание, соответствующее обслуживанию в циклическом порядке.

Радиальный граф с поочередной передачей прав

Под поочередной будем понимать такую передачу прав на занятие ресур-

са заявками, при которой заявки одного приоритета получают полномо-

чия на доступ к ресурсу с равной частотой или бесприоритетно друг от-

носительно друга. Для радиального графа такая очередность может быть

определена в результате выполнения приведенной ниже итерационной

процедуры. При этом, в общем случае реализуется R итераций.

1. Произвольным образом через одну вершину каждого приоритета

проводится первый путь.

2. Второй путь должен пройти через вершины всех приоритетов, кроме

первого (через первый путь проходит всегда), не соединенные пер-

вым путем; третий — не соединенные первыми двумя путями и т.д.

3. Если не осталось на рассмотрении вершин г-го приоритета, через

которые не прошел по крайней мере один путь (для невырожден-

ного графа прежде всего это приоритет 2) из проведенных

путей

(2 путей). Дуга

+ 1 проходит как и первая, но уже через другие

вершины приоритета

+ 1 и т.д., вплоть до соединения путями

вершины первого приоритета со всеми вершинами приоритета R.

4. Все вершины R приоритета соединяются дугой с вершиной высше-

го приоритета.

318

Глава

18.

Разработка и оптимизация механизма уровневого контроля

5. Нумеруются пути в соответствии с очередностью их получения.

Именно в соответствии с этой нумерацией (с этим порядком) в

системе должны передаваться полномочия на доступ к ресурсу.

6. Для каждого полученного пути определяется очередность передачи

полномочий между вершинами графа (очередями заявок) перечис-

лением очередности появления соответствующих вершин на пути.

Иллюстрация получения поочередной передачи прав, с использованием

приведенной процедуры представлена на рис. 18.5.

Итерация

Номер пути Очередность

передачи

прав

передачи

(в общей после- прав в пути

довательности)

1-2-4-1

1-3-6-1

1-2-5-1

1-3-7-1

Рис. 18.5. Радиальный граф с поочередной передачей прав

Свойства канонических (оптимальных)

расписаний реального времени

Можно выделить следующие свойства канонических расписаний реаль-

ного времени:

1. В общем случае для каждой очереди заявок в цикле расписания

может быть несколько очередностей передачи прав на доступ к

ресурсу

!,.

..,S,

например, (1, 2, 1, 3, 4). При этом параметры

обслуживания заявок определяются гарантированной продолжитель-

ностью обслуживания

„^

и средней продолжительностью гарантированного обслуживания тре-

бований с учетом различных очередностей

319

1=1

Часть V. Контроль корректности функционирования механизмов защиты

Таким образом, в общем случае при нескольких очередностях в систе-

ме, дисциплина обслуживания реального времени задается

параметра-

ми

Тя

т(5>

^„,

Д-™

канонического расписания значения

Т^

(5)

Т^,

соответственно совпадают для заявок всех R приоритетов.

2. В системе реализуются минимально возможные значения

^„

для всех

заявок всех R приоритетов.

3. Относительный уровень (коэффициент) приоритетности заявок

вырожденного графа при минимальных

составляет:

(RM,-\)

(RM.-l)-

Соответственно, ограничением на общность построения радиаль-

ного графа будет:

Выводы

Из анализа свойств канонических расписаний можем сделать следующие

выводы:

1. В основе синтеза расписаний реального времени должно находиться

построение канонического расписания, с последующей его модифи-

кацией, учитывающей особенности конкретной задачи

синтеза.

2. При минимизации значений параметра

ео

для

всех очередей за-

явок всех уровней приоритета системы R (эффективное использо-

вание ресурса) строго задается соотношение уровней коэффициен-

та приоритетности заявок.

3. Исходное соотношение коэффициентов приоритетности может быть

изменено либо подбором соответствующих значений параметров

гр

гт

в рамках канонического расписания, либо изменением

значений

или

(в общем случае они могут не совпадать),

путем их увеличения для заявок отдельных уровней приоритета

(уменьшить их уже невозможно, что следует из второго свойства

канонических расписаний).

18.4.3. Задача включения приоритетного

обслуживания в механизм контроля списков

Практическая реализация

Очевидно, что затраты на контроль необходимо минимизировать. Это

позволит более эффективно использовать вычислительный ресурс для

решения прикладных задач. На простом примере проиллюстрируем за-

дачу включения в схему контроля приоритетного обслуживания.

320