Безопасность операционных систем. Безбогов А.А - 28 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Все алгоритмы внешнего планирования, применяемые в ОС, имеют эвристический характер. При разработке этих алго-
ритмов стараются улучшить качество планирования, показатели которого зависят от режимов использования вычислитель-
ной системы. Планирование может осуществляться с использованием любых дисциплин и режимов обслуживания заявок (с
учетом приоритетов и без их учета, с неизменными и динамическими приоритетами и т.п.).
В системах с разделением времени внешнее планирование осуществляется согласно одного из двух алгоритмов: алго-
ритм бесприоритетного планирования; алгоритм приоритетного планирования.
Алгоритм бесприоритетного планирования предусматривает постановку заданий в очередь в порядке их поступления в
систему. Выбор заданий на обработку из очереди может быть организован либо по принципу FIFO, либо по принципу LIFO.
Алгоритм приоритетного планирования предусматривает занесение заданий в очередь на обслуживание в соответствии
с их приоритетами. Выборка заданий из очереди осуществляется из непустой очереди с наивысшим приоритетом.
В системах с пакетной мультипрограммной обработкой внешнее планирование осуществляется с применением одного
из следующих критериев:
− минимум простое оборудование;
− максимум пропускной способности вычислительной системы;
− минимум времени реакции системы на задания пользователей.
Внешнее планирование в режиме ПМП может выполняться, например, по следующим алгоритмам:
− алгоритм минимизации простоя оборудования;
− алгоритм упорядочивания по требованиям на ресурсы;
− алгоритм упорядочивания по требованиям на загрузку центрального процессора (ЦП).
Алгоритм минимизации простоя оборудования включает в рабочую смесь только те задачи, которые обеспечивают рав-
номерную нагрузку на все устройства системы. Рассмотрим минимизацию времени простоя ЦП и внешних устройств (ВУ).
Пусть
N – количество задач в рабочей смеси. Каждому i-му заданию поставим в соответствие пару чисел: T
ЦП i
– запрос
пользователя на время выполнения задания на ЦП;
T
ВУ i
– запрос пользователя на длительность загрузки внешнего устройст-
ва. Пусть заданы пороговые интервалы времени T
j п
обслуживания заданий j-м ресурсом. Тогда i-е задание является значи-
мым
, относительно j-го ресурса, если длительность времени T
ji
его обслуживания этим ресурсом больше порогового, т.е.
T
ji
> T
j п
.
Введем следующие обозначения:
N
о. ЦП
, N
о. ВУ
– оптимальное количество в рабочей смеси задач, значимых относительно ЦП и ВУ, соответственно;
N
ф. ЦП
, N
ф. ВУ
– фактическое количество в рабочей смеси задач, значимых, соответственно, относительно ЦП и ВУ.
Тогда алгоритм минимизации простоя оборудования для случая ЦП и ВУ может быть представлен двумя информаци-
онно связанными процедурами:
• процедура формирования очередей;
• процедура включения задачи в рабочую смесь.
Процедура формирования очередей обеспечивает распределение всех поступающих в систему заданий в одну из сле-
дующих четырех очередей:
z
0
– для которых T
ЦП i
< T
ЦП п
и T
ВУ i
< T
ВУ п
;
z
1
– для которых T
ЦП i
≥ T
ЦП п
и T
ВУ i
< T
ВУ п
;
z
2
– для которых T
ЦП i
< T
ЦП п
и T
ВУ i
≥ T
ВУ п
;
z
3
– для которых T
ЦП i
≥ T
ЦП п
и T
ВУ i
≥ T
ВУ п
.
Процедура включения задачи в рабочую смесь обеспечивает выборку задания из очередей
z
0
, ..., z
3
, сформированных
процедурой формирования очередей в соответствии со следующими правилами:
−
если N
ф. ЦП
< N
о. ЦП
и N
ф. ВУ
< N
о. ВУ
, то задание выбирается из очередей z
1
, z
2
или z
3
в соответствии с алгоритмом вы-
бора из очередей
z
1
, z
2
, z
3
;
− если N
ф. ЦП
< N
о. ЦП
и N
ф. ВУ
≥ N
о. ВУ
, то задание выбирается из очереди z
1
, а при ее истощении – из z
0
;
− если N
ф. ЦП
≥ N
о. ЦП
и N
ф. ВУ
< N
о. ВУ
, то задание выбирается из очереди z
2
, а при ее истощении – из очереди z
0
;
− если N
ф. ЦП
≥ N
о. ЦП
и N
ф. ВУ
≥ N
о. ВУ
, то задание выбирается из очереди z
0
, а при ее истощении – из очередей z
1
, z
2
или
z
3
по алгоритму выбора из очередей z
1
, z
2
, z
3
.
Алгоритм выбора из очередей
z
1
, z
2
, z
3
должен обеспечить бессбойную выборку заданий из указанных очередей. Здесь
возможно применение различных подходов, например, кольцевая процедура обхода очередей.
Алгоритм упорядочивания по требованиям на ресурсы разбивает задания на очереди в зависимости от объемов требуе-
мых ими ресурсов.
Алгоритм упорядочивания по требованиям на загрузку ЦП для каждого
i-го задания устанавливает приоритет (p
i
) в
зависимости от требуемого времени центрального процессора
Т
ЦП i
.
Несмотря на то, что рассмотренные три алгоритма внешнего планирования достаточно легко реализуемы в ОС, их при-
менение может привести к недопустимо большой задержке обслуживания бесприоритетных или "неудобных" заданий.
3.3.2. Алгоритмы управления задачами на уровне
внутреннего планирования
3.3.2.1. МУЛЬТИЗАДАЧНОСТЬ, ПРОЦЕССЫ И НИТИ
Мультизадачность. В современном мультипрограммировании различают два типа мультизадачности: кооперативная и
вытесняющая.
Кооперативная мультизадачность
– это такой режим работы ОС, когда активный процесс, которому ОС выделило
центральный процессор, монопольно использует его до тех пор, пока ему не потребуется выполнить какие-либо операции с
внешними устройствами.

Страницы