Наиболее важную роль в организации мультипрограммного режима работы управляющей ЭВМ играет центральная программа- диспетчер ОС. Эта программа определяет последовательность удовлетворения заявок на включение других основных программ ОС и программ решения функциональных задач и включает в счёт эти программы.

Дисциплина обслуживания заявок определяет порядок выполнения тех или иных программ. Хотя при отсутствии потерь заявок выбор той или иной дисциплины не влияет на уровень суммарной загрузки ЭВМ, от этой дисциплины зависит величина задержки информации в ЭВМ. Правильный выбор соответствующей дисциплины обслуживания заявок позволяет перераспределять время ожидания в очереди между заявками различных типов, то есть уменьшать величину задержки наиболее важной информации за счёт увеличения времени ожидания заявок на решение менее важных задач. Более того, показано, что в ряде случаев использование определённой дисциплины обслуживания сокращает суммарное время ожидания всех заявок в ЭВМ. Таким образом, центральный диспетчер (ЦД) путём рациональной организации вычислительного процесса повышает эффективность использования производительности управляющей ЭВМ.

Наиболее распространёнными дисциплинами обслуживания заявок в алгоритмах являются:

-  кольцевая дисциплина обслуживания заявок;

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

-  приоритетное обслуживание без прерывания вычислений (относительные приоритеты);

-  приоритетное обслуживание с прерыванием вычислений (абсолютные приоритеты).

Перечисленные дисциплины могут также иметь некоторые разновидности, отличающиеся режимом обслуживания заявок каждого типа:

-  одиночное обслуживание (обслуживается только одна заявка данного типа);

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

Кроме того, приоритет программ может быть как фиксированным, так и динамическим. Динамический приоритет изменяется в процессе работы в зависимости от времени ожидания или длительности обслуживания заявок. Часто применяется также принцип группового приоритета, когда один и тот же приоритет обслужива­ния назначается одновременно нескольким типам заявок, порядок обслуживания которых определяется внутренней подпрограммой- диспетчером данной группы подпрограмм.

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

Так как обращения к ЦД производятся после завершения каждой основной программы или группы подпрограмм, то есть весьма часто, то одним из основных требований к диспетчеру является требование экономичности по затратам производительности ЭВМ. Во многих случаях также требуется, чтобы состав, размещение и очерёдность работы основных программ вычислительной машины не были жёстко фиксированными, то есть диспетчер должен иметь элементы настройки на конкретный состав используемых основных подпрограмм. В следующих лекциях рассмотрим некоторые варианты программы- диспетчера ОС ЭВМ, удовлетворяющие этим требованиям.

Контрольные вопросы:

1 Какая с точки зрения ОС информация о задаче является важной?

2 Что характеризует приоритет задачи и для чего он используется?

3 Что такое контекст задачи и для чего он используется?

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

5 Возможности многозадачных ОС.

6 Повторная входимость (реентерабельность).

7 Какую роль играет диспетчер ОС в организации мультипрограммного режима работы управляющей ЭВМ.

8 Перечислите наиболее распространённые дисциплины обслуживания заявок в алгоритмах.

9 Типы приоритетов программ.

10 Основное требование к диспетчеру ОС.

Лекция 25 Программа-диспетчер с кольцевым обслуживанием заявок

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

Эта программа является простейшей и поэтому наиболее распространённой. Она применяется при обработке входной информации ЭВМ, поступающей в буферные зоны от однотипных источников, при организации обмена с аппаратурой передачи данных, а также при включении в счёт равноценных основных подпрограмм.

Для реализации кольцевой дисциплины обслуживания заявок в ОП ЭВМ выделяются две зоны, одна из которых (зона заявок) используется для хранения кодов заявок Zj на включение основных программ, а вторая (зона адресов) - для хранения начальных адресов  этих программ (рис. 25.1).

Каждой основной подпрограмме в зоне заявок и в зоне адресов выделяется определённая ячейка памяти, соответствующая номеру данной программы в системе диспетчеризации.

Рисунок 25.1

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

При необходимости вызова для работы одной из основных программ в процессе функционирования ЭВМ, осуществляется запись в закреплённую за этой программой ячейку зоны заявок определённого кода Zj, называемого безусловной заявкой. Программа- диспетчер, последовательно анализируя содержимое ячеек зоны заявок, находит код безусловной заявки, стирает его и включает в счёт соответствующую основную программу, используя для этой цели её начальный адрес , хранящийся в зоне адресов. В отдельных случаях необходимо, чтобы включение определённой про­граммы происходило лишь в тех случаях, когда имеет место совпадение требований на её работу от нескольких других подпрограмм. В этом случае последние записывают в закреплённую за вызываемой программой ячейку зоны заявок условные заявки, коды которых подбираются таким образом, что совпадение необхо­димого количества условных заявок образует безусловную заявку. Сущность циклического обслуживания заявок заключается в том, что диспетчер, включившись в счёт после выполнения некоторой j-й основной подпрограммы, дальнейший анализ зоны заявок начинает с последующей (j+1)-й ячейки этой зоны, если j+1 < n, или же с начала зоны, если j+1 > n, где n - общее количество ячеек в зоне заявок.

Каждая задача, представляющая собой отдельную подпрограмму, выполняется циклически. При этом надо придерживаться следующих правил:

-  подпрограммы не должны содержать циклов ожидания;

-  подпрограммы должны выполнять свою работу как можно быстрее, чтобы дать возможность работать следующей подпрограмме;

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

Можно отметить следующие преимущества циклического алгоритма:

-  простота использования и прозрачность для понимания;

-  если исключить из рассмотрения прерывания, система полностью детерминирована. Задачи всегда вызываются в одной и той же последовательности, что позволяет достаточно просто произвести анализ «наихудшего» случая и вычислить максимальную задержку;

-  минимальные размеры кода и данных;

-  отсутствуют ошибки, обусловленные «гонками».

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

Иногда (например, при обработке информации, поступающей в ЭВМ от аппаратуры передачи данных) одна и та же основная программа может обслужить не одну, а несколько заявок, количество которых учитывается в некоторой зоне ОП ЭВМ. В этих случаях может устанавливаться некоторое ограничение на количество заявок m_j, обслуживаемых каждой программой при одном включении. Это ограничение может учитываться либо подпрограммами ОС, выполняющими внутреннюю диспетчеризацию процесса обработки данных определённого типа, либо собственно программой, осуществляющей эту обработку. Описанные выше ограничения имеют целью лимитировать длительность работы основных программ в определённых пределах с тем, чтобы не допускать длительных задержек в обслуживании заявок на решение других задач. При этом предполагается, что средняя продолжительность обслуживания одной заявки заранее известна.

В некоторых случаях ограничение может накладываться непосредственно на длительность работы каждой включаемой в счёт программы τ_j. Этот способ, предложенный Ф. Корбато, следует применять в тех случаях, когда длительность работы основных программ заранее неизвестна или же может колебаться в значительных пределах. При реализации данной разновидности дисциплины диспетчеризации выполнение программы, превысившей заданный лимит времени τ_j, прерывается сигналом счётчика относительного времени. Одновременно с этим в зону заявок записывается признак прерывания П_j и заявка на продолжение выполнения прерванной программы. В соответствии с кольцевой дисциплиной обслуживания заявок эта заявка будет обслужена диспетчером в последнюю очередь после анализа всех других ячеек зоны заявок.

Программа-диспетчер с обслуживанием заявок в порядке поступления. Эта программа требует для своей реализации учёта последовательности поступления заявок на включение основных программ. Она может быть реализована двумя способами.

При первом способе заявки на включение основных программ записываются в порядке поступления в специальную буферную зону в виде номера вызываемой программы. Диспетчер последовательно анализирует содержимое буферной зоны заявок и включает в счет вызванные подпрограммы, выбирая необходимый началь­ный адрес из зоны адресов по номеру подпрограммы i, указанному в зоне заявок. Перед включением подпрограммы этот номер стирается программой-диспетчером. При применении данного способа диспетчеризации затрудняется использование принципа условных заявок.

При втором способе (рис. 25.2) заявки на включение каждой основной программы записываются в одну определённую ячейку зоны заявок, как и при кольцевой системе обслуживания. Однако в данном случае кодом заявки является показание СчРВ ЭВМ t_j в момент поступления данной заявки. Стирание заявки осуществляется путем записи вместо данной заявки кода t^max, превышающего максимальное показание СчРВ.

Рисунок 25.2

Реализацию принципа условных заявок можно в данном случае осуществить при помощи признаков блокировки включения той или иной программы Б_j, которые размещаются в старших разрядах ячейки зоны заявок и в совокупности представляют собой позиционный код с числом разрядов, зависящим от количества условий включения данной подпрограммы. При записи условных заявок к текущему показанию СчРВ ЭВМ приформировываются соответствующие признаки блокировки, которые рассматриваются программой-диспетчером как старшие разряды этого счётчика. Поэтому наличие любого признака блокировки предотвращает включение соответствующей основной подпрограммы. Стирание признаков блокировки осуществляется основными или вклинивающимися подпрограммами ЭВМ при выполнении соответствующего условия.

Контрольные вопросы:

1 Для чего применяется программа-диспетчер с кольцевым обслуживанием заявок?

2 Охарактеризуйте зоны, выделяемые для реализации кольцевой дисциплины обслуживания заявок в ОП ЭВМ.

3 Преимущества и недостатки циклического алгоритма выполнения задач.

4 Способы реализации программы-диспетчера с обслуживанием заявок в порядке поступления.

Лекция 26 Программа-диспетчер с фиксированными относительными приоритетами. Программа-диспетчер с фиксированными абсолютными приоритетами

Программа-диспетчер с фиксированными относительными приоритетами. Для размещения информации, обеспечивающей работу данной программы, в оперативной памяти ЭВМ выделяются две зоны. В одной из них хранится таблица установленного приоритета основных программ (рис. 26.1). Каждой основной подпрограмме (или группе подпрограмм равного приоритета) в этой таблице соответствуют две ячейки памяти, в одной из которых указывается порядковый номер и приоритет данной подпрограммы, а в другой ячейке хранится адрес начальной команды этой подпрограммы.

Pисунок 26.1

Вторая зона - шкала приоритетов (рис. 26.2) - используется для хранения заявок на работу тех или иных программ и их порядковых номеров, необходимых для обращения в таблицу приоритетов за начальным адресом программы. Каждой основной программе в этой зоне соответствует одна ячейка памяти, расположенная в порядке убывания установленного для программ приоритета. Кроме того, в фиксированной ячейке ОП ЭВМ указывается общее количество приоритетов п, которое используется в данном режиме работы программ ЭВМ. Выбор программы для включения в счёт в данный момент времени осуществляется диспетчером путём последовательного анализа кодов заявок в шкале приоритетов и начинается всегда с заявки самого высокого приоритета (с начала зоны). Заявки равного приоритета анализируются в порядке их поступления, а их количество учитывается в отдельной буферной зоне памяти.

Pисунок 26.2

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

Описанная выше программа-диспетчер имеет сравнительно небольшой объём (порядка 40 одноадресных команд) и позволяет легко изменять количество используемых основных программ, их приоритет и размещение в памяти ЭВМ. Для этого достаточно лишь соответствующим образом скорректировать информацию в таблице приоритетов.

Программа-диспетчер с фиксированными абсолютными приоритетами. В системах, работающих в режиме реального времени, временные ограничения могут быть очень жёсткими. Поэтому нужно обеспечить прерывание работы процессора в момент появления срочного запроса (даже при выполнении цикла процессора) и выполнить переход к соответствующей программе реакции, которая должна выполняться быстро и, по возможности, не прерываться. Иерархия приоритетов различных программ устанавливается в зависимости от их степени важности и от уверенности в том, что в них не допущены ошибки программирования.

Обычно в системах реального времени имеются два класса планирования: реального и разделенного времени. Класс планирования, как правило, дается не отдельным нитям, а целиком процессам. Процессы реального времени не прерываются по сигналам таймера и могут быть вытеснены только активизацией более приоритетной нити реального времени. Нити процессов разделенного времени вытесняются и друг другом по сигналам таймера, и процессами реального времени по мере их активизации.

Легко заметить, что планирование по методу приоритетной многозадачности может привести к определенным проблемам: к ситуации, когда низкоприоритетные задачи не смогут получить управление. Для решения этой проблемы применяется прием, получивший название «равнодоступность».

Принцип равнодоступности означает, что реализуется адаптивная приоритетность: приоритет задачи, которая выполняется слишком долго, постепенно уменьшается, позволяя менее приоритетным задачам получить свою долю процессорного времени.

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

В общем случае алгоритмы планирования должны соответствовать критериям оптимальности функционирования системы. Однако, если для систем «жесткого» реального времени такой критерий очевиден (всегда все делать вовремя), то для систем «мягкого» реального времени это может быть, например, минимальное максимальное запаздывание или средневзвешенная своевременность выполнения операций. В зависимости от критериев оптимальности могут применяться алгоритмы планирования, отличные от рассмотренных. Например, ЦД может анализировать моменты выдачи критичных во времени управляющих воздействий и запускать на выполнение ту задачу, которая отвечает за ближайшие из них.

Не стоит особенно увлекаться приоритетами. Можно присвоить высокий приоритет «критической» задаче и низкий - всем остальным. Если «критических» задач несколько, то стоит рассмотреть многопроцессорную систему. Вообще говоря, следует иметь в виду, что сложные динамические системы трудно анализировать и отлаживать, поэтому лучше заплатить за более мощный процессор, чем иметь проблемы из-за непредвиденного поведения системы. В связи с этим большинство существующих систем реального времени представляют собой статические системы с фиксированными приоритетами.

Контрольные вопросы:

1 Назначение программы-диспетчера с фиксированными относительными приоритетами.

2 Зоны оперативной памяти ЭВМ, выделяемые для размещения информации, обеспечивающей работу программы-диспетчера с фиксированными относительными приоритетами.

3 Для чего используется зона - шкала приоритетов?

4 Назначение программы-диспетчера с фиксированными абсолютными приоритетами.

5 Охарактеризуйте классы планирования в системах реального времени.

Лекция 27 Принципы организации прерываний. Организация счета времени