Древс Системы реалного времени технические и программные средства 2010

метром, передаваемым этой функции при вызове. Предположим, что задача А вызывает эту функцию с параметром 3, т.е. хочет записать данные в сектор 3. Допустим, что когда переменная WRITE_SECTOR уже равна 3, но сама запись еще не произведена, выполнение задачи А прерывается и начинает выполняться задача В, которая вызывает ту же функцию, но с аргументом 10. После того, как запись в сектор 10 будет произведена, управление рано или поздно вернется к задаче А, которая продолжит работу с прерванного места. Однако теперь переменная WRITE_SECTOR равна 10, и все данные задачи А будут записаны в сектор 10. Из приведенного примера видно, что ошибки, связанные с нереентерабельностью, трудно обнаружить, а последствия они могут вызвать самые катастрофические.

10.3. Диспетчеризация задач и приоритеты

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

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

271

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

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

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

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

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

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

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

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

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

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

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

272

Рис. 10.4

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

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

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

Aнj этих программ (рис. 10.4).

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

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

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

цели её начальный адрес Aнj , хранящийся в зоне адресов. В от-

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

273

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

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

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

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

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

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

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

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

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

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

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

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

274

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

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

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

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

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

взоне заявок. Перед включением подпрограммы этот номер стирается программой-диспетчером. При применении данного способа

275

Рис. 10.5

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

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

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

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

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

276

Рис. 10.7

Рис. 10.6

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

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

В рассматриваемой приоритетной диспетчерской программе так же, как и в рассмотренных ранее бесприори-

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

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

277

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

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

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

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

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

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

278

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

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

10.4. Принципы организации прерываний

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

-сбой в аппаратуре;

-переполнение разрядной сетки;

-деление на нуль;

-выход за пределы области памяти;

-требование операции ввода-вывода.

Фактически возникновение прерывания означает, что параллельно развивается несколько процессов. Для реализации прерывания в ЭВМ есть специальные аппаратурные и программные средст-

279

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

грамм или контроллером прерывания.

Основные функции системы прерывания:

-запоминание состояния прерываемой программы;

-осуществление перехода к прерывающей программе;

-восстановление состояния прерванной программы;

-возврат к прерванной программе.

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

Основные характеристики системы прерывания:

-общее число входов в систему прерывания (число источников запросов прерывания);

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

-время реакции на запрос прерывания tр;

-время, необходимое для запоминания состояния прерываемой программы;

-время, необходимое для восстановления состояния прерванной программы.

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

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

Центральное место в процедуре перехода к прерывающей программе занимают передача из регистра процессора в память (часто

280