ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 18.06.2021
Просмотров: 2547
Скачиваний: 12
Введение ограничивающих предположений о поведении набора задач.
При таком подходе планирование приближается к статическому.
Возвращаясь к планированию независимых задач, рассмотрим классический алгоритм для жестких систем реального времени с одним процессором, разработанный в 1973 году Лью (Liu) и Лейландом (Layland). Алгоритм является динамическим, то есть он использует вытесняющую многозадачность и основан на относительных статических (неизменяемых в течение жизни задачи) приоритетах.
Алгоритм основан на следующих предположениях:
Запросы на выполнение всех задач набора, имеющих жесткие ограничения на время реакции, являются периодическими.
Все задачи независимы. Между любой парой задач не существует никаких ограничений на предшествование или на взаимное исключение.
Срок выполнения каждой задачи равен ее периоду pi.
Максимальное время выполнения каждой задачи ci известно и постоянно.
Время переключения контекста можно игнорировать.
Максимальный суммарный коэффициент загрузки процессора X ci/pi при существовании п задач не превосходит n(21/n - 1). Эта величина при стремлении n к бесконечности приблизительно равна In 2, то есть 0.7.
Суть алгоритма состоит в том, что всем задачам назначаются статические приоритеты в соответствии с величиной их периодов выполнения. Задача с самым коротким периодом получает наивысший приоритет, а задача с наибольшим периодом выполнения получает наименьший .приоритет. При соблюдении всех ограничений этот алгоритм гарантирует выполнение временных ограничений для всех задач во всех ситуациях.
Если же периоды повторения задач кратны периоду выполнения самой короткой задачи, то требование к максимальному коэффициенту загрузки процессора смягчается — он может доходить до 1.
Существуют также алгоритмы с динамическим изменением приоритетов, которые назначаются в соответствии с такими текущими параметрами задачи как, например, конечный срок выполнения (deadline). При необходимости назначения некоторой задачи на выполнение выбирается та, у которой текущее значение разницы между конечным сроком выполнения и временем, требуемым для ее непрерывного выполнения, является наименьшим.
Моменты перепланировки
Для реализации алгоритма планирования ОС должна получать управление всякий раз, когда в системе происходит событие, требующее перераспределения процессорного времени. К таким событиям могут быть отнесены следующие:
Прерывание от таймера, сигнализирующее, что время, отведенное активной задаче на выполнение, закончилось. Планировщик переводит задачу в состояние готовности и выполняет перепланирование.
Активная задача выполнила системный вызов, связанный с запросом на ввод-вывод или на доступ к ресурсу, который в настоящий момент занят (например, файл данных). Планировщик переводит задачу в состояние ожидания и выполняет перепланирование.
Активная задача выполнила системный вызов, связанный с освобождением ресурса. Планировщик проверяет, не ожидает ли этот ресурс какая-либо задача. Если да, то эта задача переводится из состояния ожидания в состояние готовности. При этом, возможно, что задача, которая получила ресурс, имеет более высокий приоритет, чем текущая активная задача. После перепланирования более приоритетная задача получает доступ к процессору, вытесняя текущую задачу.
Внешнее (аппаратное) прерывание1, которое сигнализирует о завершении периферийным устройством операции ввода-вывода, переводит соответствующую задачу в очередь готовых, и выполняется планирование.
Внутреннее прерывание сигнализирует об ошибке, которая произошла в результате выполнения активной задачи. Планировщик снимает задачу и выполняет перепланирование.
1 Подробнее о прерываниях читайте в следующем разделе.
При возникновении каждого из этих событий планировщик выполняет просмотр очередей и решает вопрос о том, какая задача будет выполняться следующей. Помимо указанных существует и ряд других событий (часто связанных с системными вызовами), требующих перепланировки. Например, запросы приложений и пользователей на создание новой задачи или повышение приоритета уже существующей задачи создают новую ситуацию, которая требует пересмотра очередей и, возможно, переключения процессора.
На рис. 4.11 показан фрагмент временной диаграммы работы планировщика в системе, где одновременно выполняются четыре потока. В данном случае неважно, по какому правилу выбираются потоки на выполнение и каким образом изменяются их приоритеты. Существенное значение имеют лишь события, вызывающие активизацию планировщика.
Первые четыре цикла работы планировщика, приведенные на рисунке, были инициированы прерываниями от таймера по истечении квантов времени (эти события обозначены на рисунке как Т).
Следующая передача управления планировщику была осуществлена в результате выполнения потоком 3 системного запроса на ввод-вывод (событие I/O). Планировщик перевел этот поток в состояние ожидания, а затем переключил процессор на поток 2. Поток 2 полностью использовал свой квант, произошло прерывание от таймера, и планировщик активизировал поток 1.
При выполнении потока 1 произошло событие R — системный вызов, в результате которого освободился некоторый ресурс (например, был закрыт файл). Это событие вызвало перепланировку потоков. Планировщик просмотрел очередь ожидающих потоков и обнаружил, что поток 4 ждет освобождения данного ресурса. Этот поток был переведен в состояние готовности, но поскольку приоритет выполняющегося в данный момент потока 1 выше приоритета потока 4, планировщик вернул процессор потоку 1.
Рис. 4.11. Моменты перепланировки потоков
В следующем цикле работы планировщик активизировал поток 4, а затем, после истечения кванта и сигнала от таймера, управление получил поток 2. Этот поток не успел использовать свой квант, так как был снят с выполнения в результате возникшей ошибки (событие ER).
Далее планировщик предоставлял процессорное время потокам 1, 4 и снова 1. Во время выполнения потока 1 произошло прерывание S от внешнего устройства, сигнализирующее о том, что операция передачи данных завершена. Это событие активизировало работу планировщика, в результате которой поток 3, ожидавший завершения ввода-вывода, вытеснил поток 1, так как имел в этот момент более высокий приоритет.
Последний показанный на диаграмме период выполнения потока 1 прерывался несколько раз. Вначале это было прерывание от внешнего устройства (S), затем программное прерывание (R), вызвавшее освобождение ресурса, и, наконец, прерывание от таймера (Т). Каждое из этих трех прерываний вызвало перепланировку потоков. В двух первых случаях планировщик оставил выполняться поток 1, так как в очереди не оказалось более приоритетных потоков, а квант времени, выделенный потоку 1, еще не был исчерпан. Переключение потоков было выполнено только по прерыванию от таймера.
В системах реального времени для отработки статического расписания планировщик активизируется по прерываниям от таймера. Эти прерывания пронизывают всю временную ось, возникая через короткие постоянные интервалы времени. После каждого прерывания планировщик просматривает расписание и проверяет, не пора ли переключить задачи. Кроме прерываний от таймера в системах реального времени перепланирование задач может происходить по прерываниям от внешних устройств — различного вида датчиков и исполнительных механизмов.
Мультипрограммирование на основе прерываний
Назначение и типы прерываний
Прерывания являются основной движущей силой любой операционной системы. Отключите систему прерываний — и «жизнь» в операционной системе немедленно остановится. Периодические прерывания от таймера вызывают смену процессов в мультипрограммной ОС, а прерывания от устройств ввода-вывода управляют потоками данных, которыми вычислительная система обменивается с внешним миром.
Как верно было замечено: «Прерывания названы так весьма удачно, поскольку они прерывают нормальную работу системы»1. Другими словами, система прерываний переводит процессор на выполнение потока команд, отличного от того, который выполнялся до сих пор, с последующим возвратом к исходному коду. Из сказанного можно сделать вывод о том, что механизм прерываний очень похож на механизм выполнения процедур. Это на самом деле так, хотя между этими механизмами имеется важное отличие. Переключение по прерыванию отличается от переключения, которое происходит по команде безусловного или условного перехода, предусмотренной программистом в потоке команд приложения. Переход по команде происходит в заранее определенных программистом точках программы в зависимости от исходных данных, обрабатываемых программой. Прерывание же происходит в произвольной точке потока команд программы, которую программист не может прогнозировать. Прерывание возникает либо в зависимости от внешних по отношению к процессу выполнения программы событий, либо при появлении непредвиденных аварийных ситуаций в процессе выполнения данной программы. Сходство же прерываний с процедурами состоит в том, что в обоих случаях выполняется некоторая подпрограмма, обрабатывающая специальную ситуацию, а затем продолжается выполнение основной ветви программы.
1 Скотт Максвелл. Ядро Linux в комментариях. — К. ДиаСофт, 2000.
В зависимости от источника прерывания делятся на три больших класса:
внешние;
внутренние;
программные.
Внешние прерывания могут возникать в результате действий пользователя или оператора за терминалом, или же в результате поступления сигналов от аппаратных устройств — сигналов завершения операций ввода-вывода, вырабатываемых контроллерами внешних устройств компьютера, такими как принтер или накопитель на жестких дисках, или же сигналов от датчиков управляемых компьютером технических объектов. Внешние прерывания называют также аппаратными, отражая тот факт, что прерывание возникает вследствие подачи некоторой аппаратурой (например, контроллером принтера) электрического сигнала, который передается (возможно, проходя через другие блоки компьютера, например контроллер прерываний) на специальный вход прерывания процессора. Данный класс прерываний является асинхронным по отношению к потоку инструкций прерываемой программы. Аппаратура процессора работает так, что асинхронные прерывания возникают между выполнением двух соседних инструкций, при этом система после обработки прерывания продолжает выполнение процесса, уже начиная со следующей инструкции.
Внутренние прерывания, называемые также исключениями (exeption), происходят синхронно выполнению программы при появлении аварийной ситуации в ходе исполнения некоторой инструкции программы. Примерами исключений являются деление на нуль, ошибки защиты памяти, обращения по несуществующему адресу, попытка выполнить привилегированную инструкцию в пользовательском режиме и т. п. Исключения возникают непосредственно в ходе выполнения тактов команды («внутри» выполнения).
Программные прерывания отличаются от предыдущих двух классов тем, что они по своей сути не являются «истинными» прерываниями. Программное прерывание возникает при выполнении особой команды процессора, выполнение которой имитирует прерывание, то есть переход на новую последовательность инструкций. Причины использования программных прерываний вместо обычных инструкций вызова процедур будут изложены ниже, после рассмотрения механизма прерываний.
Прерываниям приписывается приоритет, с помощью которого они ранжируются по степени важности и срочности. О прерываниях, имеющих одинаковое значение приоритета, говорят, что они относятся к одному уровню приоритета прерываний.
Прерывания обычно обрабатываются модулями операционной системы, так как действия, выполняемые по прерыванию, относятся к управлению разделяемыми ресурсами вычислительной системы — принтером, диском, таймером, процессором и т. п. Процедуры, вызываемые по прерываниям, обычно называют обработчиками прерываний, или процедурами обслуживания прерываний (Interrupt Service Routine, /57?). Аппаратные прерывания обрабатываются драйверами соответствующих внешних устройств, исключения — специальными модулями ядра, а программные прерывания — процедурами ОС, обслуживающими системные вызовы. Кроме этих модулей в операционной системе может находиться так называемый диспетчер прерываний, который координирует работу отдельных обработчиков прерываний.
Механизм прерываний
Механизм прерываний поддерживается аппаратными средствами компьютера и программными средствами операционной системы. Аппаратная поддержка прерываний имеет свои особенности, зависящие от типа процессора и других аппаратных компонентов, передающих сигнал запроса прерывания от внешнего устройства к процессору (таких, как контроллер внешнего устройства, шины подключения внешних устройств, контроллер прерываний, являющийся посредником между сигналами шины и сигналами процессора). Особенности аппаратной peaлизации прерываний оказывают влияние на средства программной поддержки прерываний, работающие в составе ОС.
Существуют два основных способа, с помощью которых шины выполняют прерывания: векторный (vectored) и опрашиваемый (polled). В обоих способах процессору предоставляется информация об уровне приоритета прерывания на шине подключения внешних устройств. В случае векторных прерываний в процессор передается также информация о начальном адресе программы обработки возникшего прерывания — обработчика прерываний.
Устройствам, которые используют векторные прерывания, назначается вектор прерываний. Он представляет собой электрический сигнал, выставляемый на соответствующие шины процессора и несущий в себе информацию об определенном, закрепленном за данным устройством номере, который идентифицирует соответствующий обработчик прерываний. Этот вектор может быть фиксированным, конфигурируемым (например, с использованием переключателей) или программируемым. Операционная система может предусматривать процедуру регистрации вектора обработки прерываний для определенного устройства, которая связывает некоторую подпрограмму обработки прерываний с определенным вектором. При получении сигнала запроса прерывания процессор выполняет специальный цикл подтверждения прерывания, в котором устройство должно идентифицировать себя. В течение этого цикла устройство отвечает, выставляя на шину вектор прерываний. Затем процессор использует этот вектор для нахождения обработчика данного прерывания. Примером шины подключения внешних устройств, которая поддерживает векторные прерывания, является шина VMEbus.
При использовании опрашиваемых прерываний процессор получает от запросившего прерывание устройства только информацию об уровне приоритета прерывания (например, номере IRQ на шине ISA или номере IPL на шине SBus компьютеров SPARC). С каждым уровнем прерываний может быть связано несколько устройств и соответственно несколько программ — обработчиков прерываний. При возникновении прерывания процессор должен определить, какое устройство из тех, которые связаны с данным уровнем прерываний, действительно запросило прерывание. Это достигается вызовом всех обработчиков прерываний для данного уровня приоритета, пока один из обработчиков не подтвердит, что прерывание пришло от обслуживаемого им устройства. Если же с каждым уровнем прерываний связано только одно устройство, то определение нужной программы обработки прерывания происходит немедленно, как и при векторном прерывании. Опрашиваемые прерывания поддерживают шины ISA, EISA, MCA, PCI и Sbus.