Пособие по подготовке к экзаменам по дисциплине "Операционные системы и среды"

ПЛАНИРОВАНИЕ ЗАДАНИЙ

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

Категории алгоритмов планирования

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

Системы пакетной обработки данных;
Интерактивные системы;
Системы реального времени.

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

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

     Чтобы разработать алгоритм планирования, необходимо иметь представление о том, что должен делать алгоритм. Некоторые задачи зависят от среды, но есть задачи, одинаковые во всех системах.
     Все системы
     Справедливость - предоставление каждому процессу справедливой доли процессорного времени.
     Принудительное применение политики - контроль за выполнением принятой политики.
     Баланс - поддержка занятости всех частей системы.
     Системы пакетной обработки данных
     Пропускная способность - максимальное количество задач в час.
     Оборотное время - минимизация времени, затраченного на ожидание обслуживания и обработку задачи.
     Использование процессора - поддержка постоянной занятости процессора.
     Интерактивные системы
     Время отклика - быстрая реакция на запросы.
     Соразмерность - выполнение пожеланий пользователя.
     Системы реального времени
     Окончание работы к сроку - предотвращение потери данных.
     Предсказуемость - предотвращение деградации качества в мультимедийных системах.

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

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

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

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

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

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

Вопросы к теме "Планирование заданий"

Что такое планировщик?
О чем должен заботиться планировщик?
Почему в различных средах требуются различные алгоритмы планирования?
Какие существуют среды планирования?
Какие алгоритмы планирования необходимы в системах пакетной обработки данных?
Какие алгоритмы планирования необходимы в интерактивных системах?
Какие алгоритмы планирования необходимы в системах с разделением времени?
Какие задачи планирования ставятся перед всеми системами?
Какие задачи планирования перед системами пакетной обработки данных?
Какие задачи планирования ставятся перед интерактивными системами?
Какие задачи планирования ставятся перед системами реального времени?
Какие существуют алгоритмы планирования систем пакетной обработки данных?
Какие существуют алгоритмы планирования интерактивных систем?
Что играет существенную роль в системах реального времени?
Какими могут быть алгоритмы планирования для систем реального времени?

Тесты по теме "Планирование заданий"

Вариант 1

В каком режиме могут быть активными несколько процессов:
1. Однозадачный;
2. Многозадачный;
3. Многопользовательский;
Какая часть операционной системы отвечает за выбор процессора между процессами:
1. Планировщик;
2. Компоновщик;
3. Сортировщик;
Для какого вида компьютера, на данный момент, планирование играет существенную роль:
1. Мэйнфеймы;
2. Персональные компьютеры;
3. Серверы;
С чем связаны различия в алгоритмах планирования:
1. Различия операционных систем;
2. Различия прикладных программ;
3. Различия операционных систем и приложений;
В какой системе нет пользователя:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
В какой системе процессы знают, что их время ограничено:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
В чем отличие системы реального времени от интерактивной системы:
1. Работают программы, предназначенные для содействия конкретным приложениям;
2. Работают все программы;
3. Работают прикладные программы;
Какая задача предоставляет каждому процессу справедливой доли процессорного времени:
1. Баланс;
2. Справедливость;
3. Планирование;
Какой задачи нет в системе реального времени:
1. Окончание работы к сроку;
2. Предсказуемость;
3. Соразмерность;
Как называется задача, которая поддерживает постоянную занятость процессора:
1. Использование процесса;
2. Использование процессора;
3. Баланс;
К какой системе относится задача пропускной способности:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
В каком виде планирования планировщик каждый раз выбирает процесс с наименьшим временем выполнения:
1. "Первым пришел - первым обслужен";
2. "Кратчайшая задача - первая";
3. Наименьшее оставшееся время выполнения;
В каком виде планирования имеется термин - квант:
1. Циклическое планирование;
2. Приоритетное планирование;
3. "Кратчайшая задача - первая";
На что делится система реального времени:
1. На гибкие системы реального времени;
2. На жесткие системы реального времени;
3. На жесткие и гибкие системы реального времени;
Какое внешнее событие возникает через регулярные промежутки времени:
1. Непериодическое;
2. Периодическое;
3. Системное;

Вариант 2

Какая часть операционной системы отвечает за выбор процессора между процессами:
1. Компоновщик;
2. Планировщик;
3. Сортировщик;
В какой системе время перестало являться дефицитным ресурсом:
1. Система реального времени;
2. Интерактивная система;
3. Система пакетной обработки данных;
Планировщик должен заботится о:
1. Правильном использовании процессора;
2. Эффективном использовании процессора;
3. Справедливом использовании процессора;
В какой системе используется планирование с переключением:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
В чем отличие системы реального времени от интерактивной системы:
1. Работают программы, предназначенные для содействия конкретным приложениям;
2. Работают все программы;
3. Работают прикладные программы;
Какая задача предоставляет каждому процессу справедливой доли процессорного времени:
1. Баланс;
2. Справедливость;
3. Планирование;
К какой системе относится задача пропускной способности:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
В каком виде планирования процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают:
1. Наименьшее оставшееся время выполнения;
2. "Кратчайшая задача - первая";
3. "Первым пришел - первым обслужен";
В каком виде планирования имеется термин - квант:
1. Приоритетное планирование;
2. Циклическое планирование;
3. "Кратчайшая задача - первая";
Какой вид алгоритма планирования доступен только при наличии достоверной информации о работе и о временном графике:
1. Реляционный;
2. Динамический;
3. Статистический;
При каком виде алгоритма планирования решения принимаются по ходу дела:
1. Статистический;
2. Реляционный;
3. Динамический;
Какое внешнее событие возникает через регулярные промежутки времени:
1. Непериодическое;
2. Периодическое;
3. Системное;
В каком виде планирования планировщик каждый раз выбирает процесс с наименьшим временем выполнения:
1. Наименьшее оставшееся время выполнения;
2. "Кратчайшая задача - первая";
3. "Первым пришел - первым обслужен";
Как называется задача, которая поддерживает постоянную занятость процессора:
1. Использование процесса;
2. Использование процессора;
3. Баланс;
В какой системе процессы знают, что их время ограничено:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;

Вариант 3

На что делится система реального времени:
1. На гибкие системы реального времени;
2. На жесткие системы реального времени;
3. На жесткие и гибкие системы реального времени;
Какой задачи нет в системе реального времени:
1. Окончание работы к сроку;
2. Соразмерность;
3. Предсказуемость;
С чем связаны различия в алгоритмах планирования:
1. Различия операционных систем и приложений;
2. Различия прикладных программ;
3. Различия операционных систем;
Какая система использовала в качестве устройства ввода содержимое перфокарт на магнитной ленте:
1. Система реального времени;
2. Интерактивная система;
3. Система пакетной обработки данных;
В каком режиме могут быть активными несколько процессов:
1. Однозадачный;
2. Многозадачный;
3. Многопользовательский;
Какая часть операционной системы отвечает за выбор процессора между процессами:
1. Сортировщик;
2. Компоновщик;
3. Планировщик;
В чем отличие системы реального времени от интерактивной системы:
1. Работают программы, предназначенные для содействия конкретным приложениям;
2. Работают все программы;
3. Работают прикладные программы;
К какой системе относится задача пропускной способности:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
Какой вид алгоритма планирования доступен только при наличии достоверной информации о работе и о временном графике:
1. Реляционный;
2. Статистический;
3. Динамический;
При каком виде алгоритма планирования решения принимаются по ходу дела:
1. Статистический;
2. Реляционный;
3. Динамический;
В каком виде планирования планировщик каждый раз выбирает процесс с наименьшим временем выполнения:
1. "Первым пришел - первым обслужен";
2. "Кратчайшая задача - первая";
3. Наименьшее оставшееся время выполнения;
В какой системе процессы знают, что их время ограничено:
1. Интерактивные системы;
2. Системы реального времени;
3. Системы пакетной обработки данных;
Для какого вида компьютера, на данный момент, планирование играет существенную роль:
1. Серверы;
2. Персональные компьютеры;
3. Мэйнфеймы;
В каком виде планирования имеется термин - квант:
1. "Кратчайшая задача - первая";
2. Приоритетное планирование;
3. Циклическое планирование;
Какая задача предоставляет каждому процессу справедливой доли процессорного времени:
1. Баланс;
2. Справедливость;
3. Планирование;

Вариант 4

Какая задача предоставляет каждому процессу справедливой доли процессорного времени:
1. Баланс;
2. Справедливость;
3. Планирование;
В каком виде планирования процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают:
1. "Первым пришел - первым обслужен";
2. "Кратчайшая задача - первая";
3. Наименьшее оставшееся время выполнения;
При каком виде алгоритма планирования решения принимаются по ходу дела:
1. Статистический;
2. Реляционный;
3. Динамический;
В каком виде планирования планировщик каждый раз выбирает процесс с наименьшим временем выполнения:
1. "Первым пришел - первым обслужен";
2. "Кратчайшая задача - первая";
3. Наименьшее оставшееся время выполнения;
В какой системе процессы знают, что их время ограничено:
1. Системы пакетной обработки данных;
2. Системы реального времени;
3. Интерактивные системы;
Для какого вида компьютера, на данный момент, планирование играет существенную роль:
1. Мэйнфеймы;
2. Серверы;
3. Персональные компьютеры;
В какой системе время является дефицитным ресурсом:
1. Система реального времени;
2. Система пакетной обработки данных;
3. Интерактивная система;
В какой системе нет пользователя:
1. Системы реального времени;
2. Системы пакетной обработки данных;
3. Интерактивные системы;
Как называется задача, которая поддерживает постоянную занятость процессора:
1. Использование процесса;
2. Использование процессора;
3. Баланс;
Какое внешнее событие возникает через регулярные промежутки времени:
1. Периодическое;
2. Непериодическое;
3. Системное;
Какой вид алгоритма планирования доступен только при наличии достоверной информации о работе и о временном графике:
1. Реляционный;
2. Статистический;
3. Динамический;
Какая система использовала в качестве устройства ввода содержимое перфокарт на магнитной ленте:
1. Система реального времени;
2. Интерактивная система;
3. Система пакетной обработки данных;
В каком виде планирования имеется термин - квант:
1. Циклическое планирование;
2. Приоритетное планирование;
3. "Кратчайшая задача - первая";
К какой системе относится задача пропускной способности:
1. Системы пакетной обработки данных;
2. Интерактивные системы;
3. Системы реального времени;
В каком режиме могут быть активными несколько процессов:
1. Однозадачный;
2. Многозадачный;
3. Многопользовательский;