Занятие 8. Планирование потоков и процессов в операционных системах

План занятия:

• Особенности выполнения потоков

• Механизмы и политики планирования

• Использование принципов планирования

• Долговременное планирование

• Средневременное планирование

• Кратковременное планирование

Особенности выполнения потоков

С точки зрения планирования, выполнение потока можно изобразить как цикл чередования периодов вычислений (использование процессора) и периодов ожидания ввода-вывода. Интервал времени, в течение которого поток выполняет только инструкции процессора, называют интервалом использования процессора (CPU burst), интервал времени, когда поток ожидает ввода-вывода, - интервалом ввода-вывода (I/O burst). Чаще всего эти интервалы имеют длину от 2 до 8 мс.

Потоки, которые больше тратят на вычисления и меньше - на ввод-вывод, называют ограниченными возможностями процессора (CPU bound). Они активно используют процессор. Основной их характеристикой является время, затраченное на вычисление, интервалы использования процессора для них длиннее. Потоки, которые большую часть времени находятся в ожидании ввода-вывода, называют ограниченными возможностями ввода-вывода (I/O bound). Такие потоки загружают процессор значительно меньше, а средняя длина интервала использования процессора для них небольшая. Чем выше тактовая частота процессора, тем больше потоков можно отнести ко второй категории.

Механизмы и политики планирования

Следует различать механизмы и политику планирования. К механизмам планирования относятся средства переключения контекста, средства синхронизации потоков и т.п., к политике планирования - методы определения момента времени, когда необходимо переключить контекст. Ту часть системы, которая отвечает за политику планирования, называют планировщиком (scheduler), а алгоритм, используемый при этом, - алгоритмом планирования (scheduling algorithm).

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

Минимальное время отклика. Это важнейший критерий для интерактивных систем. Под временем отклика понимают время, между запуском потока (или введением пользователем интерактивной команды) и получением первого ответа. Для современных систем приемлемым временем отклика считают 50-150 мс.

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

1. Сокращать время бесполезной нагрузки (например, время, необходимое для переключения контекста);

2. Эффективнее использовать ресурсы (для того, чтобы ни процессор, ни устройства ввода-вывода не простаивали).

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

Использование принципов планирования

Принципы планирования потоков применимы прежде всего к многопоточным системам с реализацией схемы 1: 1 (здесь планируются исключительно потоки ядра), а также к системам с реализацией модели процессов. В последнем случае вместо термина «поток» можно употреблять термин «процесс», а информацию, необходимую для планирования, хранить в структурах данных процессов. Сложные принципы планирования используются в многопоточных системах, для которых количество потоков пользователя не совпадает с количеством потоков ядра (схемы 1: М и M: N). Для них нужно два планировщика: один для работы на уровне ядра, другой - в режиме пользователя.

Долговременное планирование

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

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

Средневременное планирование

Средства среднесрочного планирования управляют переходом потоков с приостановленного состояния в состояние готовности и обратно. Сразу же отметим, что управляющие блоки готовых к выполнению потоков организуются в памяти в структуру, которую называют очередь готовых потоков (ready queue). Подробнее рассмотрим эту очередь при изучении краткосрочного планирования.

Переход потока в приостановленное состояние могут вызвать следующие факторы:

• ожидания операции ввода-вывода;

• ожидания окончания выполнения другого потока (присоединения);

• блокирование потока из-за необходимости его синхронизации с другими потоками.

Обычно для корректной организации такого ожидания, кроме очереди готовых потоков, реализуют дополнительный набор очередей. Каждая такая очередь связана с ресурсом, который может вызвать ожидания потока (например, с устройством ввода-вывода); эти очереди еще называют очередями планирования (scheduling queues) или очередями ожидания (wait queues). Среднесрочный планировщик управляет всеми этими очередями, перемещая потоки между ними и очередь готовых потоков.

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

Краткосрочное планирование или планирование процессора (CPU scheduling), является важнейшим видом планирования. Оно позволяет ответить на два базовых вопроса:

• Когда прервать выполнение потока

• Какому потоку из числа готовых к выполнению нужно передать процессор в данный момент

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

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