Тема 3.2 Планирование заданий

Введение в планирование. Категории алгоритмов планирования. Задачи алгоритмов планирования. Планирование в системах пакетной обработки данных. Планирование в интерактивных системах. Планирование в системах реального времени.

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

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

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

· по принципу стека, или, как иногда говорят, по дисциплине LCFS (last come - а прерывания по нарушению питания;

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

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

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

Когда говорят о внешней памяти (например, память на магнитных дисках), то собственно память и доступ к ней считаются разными видами ресурса. Каждый из этих ресурсов может предоставляться независимо от другого. Но для полной работы с внешней памятью необходимо иметь оба этих ресурса. Собственно внеш­няя память может разделяться одновременно, а доступ к ней — попеременно.

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

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

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

Повторно используемые программные модули, в свою очередь, могут быть не­привилегированными, привилегированными и реентерабельными.

Привилегированные программные модули работают в так называемом привилеги­рованном режиме, то есть при отключенной системе прерываний (часто говорят, что прерывания закрыты), так, что никакие внешние события не могут нарушить естественный порядок вычислений. В результате программный модуль выполня­ется до своего конца, после чего он может быть вновь вызван на исполнение из другой задачи (другого вычислительного процесса). С позиций стороннего на­блюдателя по отношению к вычислительным процессам, которые попеременно (причем, возможно, неоднократно) в течение срока своей «жизни» вызывают не­который привилегированный программный модуль, такой модуль будет высту­пать как попеременно разделяемый ресурс. Структура привилегированных про­граммных модулей изображена на рис. 5. Здесь в первой секции программного модуля выключается система прерываний. В последней секции, напротив, вклю­чается система прерываний.

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

В противоположность этому, реентерабельные программные модули (reente­rable) допускают повторное многократное прерывание своего исполнения и по­вторный их запуск по обращению из других задач (вычислительных процессов). Для этого реентерабельные программные модули должны быть созданы таким образом, чтобы было обеспечено сохранение промежуточных вычислений для прерываемых вычислений и возврат к ним, когда вычислительный процесс во­зобновляется с прерванной ранее точки. Это может быть реализовано двумя спо­собами: с помощью статических и динамических методов выделения памяти под сохраняемые значения. Основной, наиболее часто используемый динамический — способ выделения памяти для сохранения всех промежуточных результатов вы­числения, относящихся к реентерабельному программному модулю, может быть проиллюстрирован с помощью рис. 6.

Рис. 5. Структура привилегированного программного модуля

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

Рис. 6. Реентабельный программный модуль

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

Кроме реентерабельных программных модулей существуют еще повторно входимые (от re-entrance). Этим термином называют программные модули, которые тоже допускают свое многократное параллельное использование, но в отличие от реентерабельных их нельзя прерывать. Повторно входимые программные мо­дули состоят из привилегированных секций и повторное обращение к ним воз­можно только после завершения какой-нибудь из таких секций. После выпол­нения очередной привилегированной секции управление может быть передано супервизору, и если он предоставит возможность выполняться другому процес­су, то возможно повторное вхождение в рассматриваемый программный модуль. Другими словами, в повторно входимых программных модулях четко предопре­делены все допустимые (возможные) точки входа. Следует отметить, что по­вторно входимые программные модули встречаются гораздо чаще реентерабель­ных (повторно прерываемых).

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

Алгоритмы планирования могут преследовать различные цели и обеспечивать разное качество мультипрограммирования. Например, в одном случае выбирается такой алгоритм планирования, при котором гарантируется, что ни один поток/процесс не будет занимать процессор дольше определенного времени, в другом случае целью является максимально быстрое выполнение «коротких» задач, а в третьем случае — преимущественное право занять процессор получают потоки интерактивных приложении. Именно особенности реализации планирования потоков в наибольшей степени определяют специфику операционной системы, в частности, является ли она системой пакетной обработки, системой разделения времени или системой реального времени.

Дата добавления: 2013-12-12