Смешанные алгоритмы планирования и Планирование в системах реального времени

Задачи алгоритмов планирования

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

Все системы

Справедливость – предоставление каждому процессу справедливой доли процессорного времени

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

Системы пакетной обработки данных

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

Интерактивные системы

Время отклика – быстрая реакция на запросы.

Соразмерность- выполнение пожеланий пользователя.

Системы реального времени

Окончание работы к сроку- предотвращение потери данных.

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

31 билет.Планирование в системах пакетной обработки данных.

Планирование в системах пакетной обработки данных

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

32 билет. Планирование в интерактивных системах.

Планирование в интерактивных системах

     "Циклическое планирование".       Каждому процессу предоставляется некоторый интервал времени процессора - квант. Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Первоначальный процесс переносится в конец очереди. Значение кванта около 20-50 мс является оптимальным. В этом типе алгоритма есть важное допущение о том, что все процессы равнозначны.       "Приоритетное планирование".       Основная идея: каждому процессу присваивается приоритет, и управление передается готовому к работе процессу с самым высоким приоритетом. Чтобы предотвратить бесконечную работу процессов с высоки приоритетом, планировщик может уменьшит приоритет процесса с каждым тактом часов (то есть при каждом прерывании по таймеру). Если в результате приоритет текущего процесса окажется ниже, чем приоритет следующего процесса, произойдет переключение. Возможно предоставление каждому процессу максимального отрезка времени работы. Как только время кончилось, управление передается следующему по приоритету процессу. 

33. Планирование в системах реального времени

Планирование в системах реального времени

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

34 билет. Обслуживание ввода-вывода. Последовательность действий при обработке прерываний. Стандартные программы обработки прерываний.