Состояния потока

За время своего существования в системе поток может многократно находиться в одном из трех состояний:

· выполнение – активное состояние, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

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

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

Возможные переходы между состояниями:

· Поток выбран на выполнение;

· Поток ожидает завершения ввода/вывода;

· Ввод/вывод завершен (событие произошло);

· Поток вытеснен.

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

17. Планирование и диспетчеризация потоков, моменты перепланировки

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

Планирование включает в себя решение двух задач:

· определение момента времени для смены текущего активного потока;

· выбор для выполнения потока из очереди готовых потоков.

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

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

Диспетчеризация сводится к следующему:

· сохранение контекста текущего потока, который требуется сменить;

· загрузка контекста нового потока, выбранного в результате планирования;

· запуск нового потока на выполнение.

Ситуации, когда необходимо планирование:

1) Время, отведенное активной задаче на выполнение, закончилось. Планировщик переводит задачу в состояние готовности и выполняет перепланирование.

2) Активная задача выполнила системный вызов, связанный с запросом на ввод/вывод или на доступ к ресурсу, который в настоящий момент занят. Планировщик переводит задачу в состояние ожидания и выполняет перепланирование.

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

4) Завершение периферийным устройством операции ввода/вывода переводит соответствующую задачу в очередь готовых, и выполняется планирование.

5) Внутреннее прерывание сигнализирует об ошибке, которая произошла в результате выполнения активной задачи. Планировщик снимает задачу и выполняет перепланирование.

18. Алгоритм планирования, основанный на квантовании

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

· поток завершился и покинул систему;

· произошла ошибка;

· поток перешел в состояние ожидания;

· исчерпан квант процессорного времени, отведенный данному потоку.

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

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

19. Приоритетное планирование

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

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

Рисунок 2. Приоритеты потоков в Windows NT

Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.

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

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

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

20. Алгоритмы планирования ОС пакетной обработки: «первым пришел – первым обслужен», «кратчайшая задача – первая», «наименьшее оставшееся время выполнения»

В таких ОС критерием эффективности служит максимальная загрузка аппаратуры.

Алгоритмы планирования:

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

· Кратчайшая задача - первая. Нужно знать время выполнения задачи! Критерий - минимальное среднее оборотное время. Оборотное время - время, прошедшее от начала выполнения до получения результата.

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

21. Алгоритмы планирования в интерактивных ОС: циклическое, приоритетное, гарантированное, лотерейное, справедливое планирование

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

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

Преимущества:

· простота;

· справедливость (как в очереди покупателей, каждому только по килограмму).

Недостатки:

· слишком малый квант времени (по сравнению с временем переключения контекстов) приводит к частому переключению процессов и снижению производительности;

· слишком большой квант может привести к увеличению времени ответа на интерактивный запрос.

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

Гарантированное планирование. ОС гарантирует существующим потокам, что они получат гарантированную справедливую часть процессорного времени. n потоков, 1/n частей процессорного времени каждому. Стс должна вести учет времени, получаемого каждым потоком, в момент перепланировки вычисляется отношение фактически получаемого воремени к времени гарантированному. На выполнение выбирается тот поток, у которого это отношение наименьшее.

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

Справедливое планирование. Учитывается принадлежность процессов пользователям, в отличие от других алгоритмов. Процессорное время делится между пользователями.

22. Алгоритм планирования Windows NT

Алгоритм планирования нитей в Windows NT объединяет в себе обе базовых концепции - квантование и приоритеты. Как и во всех других алгоритмах, основанных на квантовании, каждой нити назначается квант, в течение которого она может выполняться. Нить освобождает процессор, если:

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

· в очереди готовых появляется более приоритетная нить.

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

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

Планирование в ОС реального времени

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

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

· жесткие - несоблюдение временных ограничений приводит к катастрофическим последствиям; в таких системах время завершения выполнения каждой из критических задач должно быть гарантировано для всех возможных сценариев работы системы;

· гибкие - нарушения временного графика нежелательны, но допустимы, это позволяет использовать менее затратные способы планирования.

Внешние события, на которые система должна реагировать, делятся:

· периодические – начиная с момента первоначального запроса все будущие моменты возникновения задачи можно определить заранее;

· спорадические - моменты возникновения запросов заранее неизвестны.

Планировщик бывает:

· Статический: до запуска системы составляется расписание. Все решения сделаны заранее, во время выполнения реализуется это расписание;

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