Процессы в Windows

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

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

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

Все версии Windows от 1.0 до 3.11 представляли собой достаточно мощные многозадачные системы с невытесняющей диспетчеризацией. Версии, начиная с Windows NT и Windows 95, используют вытесняющую диспетчеризацию.

Занятие 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, может быть очередь с приоритетами, деревом или неупорядоченным связным списком.

Занятие 9. Стратегия и алгоритмы планирования потоков и процессов

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

· Стратегия планирования

· Планирование по принципу FIFO

· Круговое планирование

· Планирование на основе характеристик дальнейшего планирования

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

Существуют несколько вариантов передачи управления от одного потока к другому, а именно:

· После того, как поток перешел в состояние ожидания (например, во время ввода-вывода или присоединения);

· После окончания выполнения потока;

· Явно (поток сам отдает процессор другим потокам на время, пока он не занят полезной работой);

· За прерыванием (например, прерывания от таймера).

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

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

При не выталкивающей многозадачности (non-preemptive multitasking) потоки могут выполняться на протяжении неограниченного времени и не могут быть прерваны ОС. Для не выталкивающей многозадачности передача управления по последнему варианту не реализована, и потоки сами должны отдавать управление ОС для передачи другим потокам или, переходить в состояние ожидания. Если какой-то поток забудет или не сможет это сделать, например займет процессор бесконечным циклом, другие потоки не смогут продолжать свою работу. Такую стратегию было реализовано в ОС Novell NetWare (например, в версии 3.11, которую широко использовали в 90-х годах XX в.)

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

Планирование по принципу FIFO

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

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

· он по определению не выталкивающий;

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

· он подлежит эффекту конвоя (convoy effect).

Круговое планирование

Самым простым для понимания и справедливым вытисняющим алгоритмом является алгоритм кругового планирования (round-robin scheduling). В средние века термином «round robin» называли петиции, где подписи идут по кругу, чтобы нельзя было узнать, кто подписался первым.

Каждому потоку выделяют интервал времени, который называют квантом времени (time quantum, time slice) и в течение которого этому потоку разрешено выполняться. Когда поток все еще выполняется после исчерпания кванта времени, его прерывают и переключают процессор на выполнение инструкций другого потока. Когда он блокируется или заканчивает свое выполнение до истечения кванта времени, процессор тоже передают другому потоку. Длина кванта времени для всей системы одинакова.

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

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

Планирование на основе характеристик дальнейшего планирования

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

Прежде всего, следует отметить алгоритм «первый - с коротким временем выполнения» (Shortest Time to Completion First, STCF), когда с каждым потоком связывают продолжительность следующего интервала использования им процессора и для выполнения каждый раз выбирают поток, у которого этот интервал короткий. В результате чего, потоки, захватывающие процессор на короткое время, получают при планировании предпочтение и быстрее выходят из системы.

Алгоритм STCF является теоретически оптимальным по критерию среднего времени отклика, то есть можно доказать, что для выбранной группы потоков среднее время отклика в случае применения этого алгоритма будет минимальным по сравнению с любым другим алгоритмом. К сожалению, для краткосрочного планирования реализовать его невозможно, так как эта реализация требует предвидения ожидаемых характеристик. Для долгосрочного планирования его используют довольно часто. Отметим также, что оптимальность такого алгоритма неотделима от его «несправедливости» - к потокам с длинными интервалами использования процессора.

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

Вытисняющим аналогом STCF алгоритм «первый - с коротким временем выполнения, что осталось» (Shortest Remaining Time to Completion First, SRTCF). Его отличие от SCTF заключается в том, что, когда в очередь готовых потоков добавляют новый, у которого следующий интервал использования процессора короче, чем время, оставшееся до завершения выполнения текущего потока, что приводит к прерыванию текущего потога, и на его место становится новый поток.

Занятие 10. Различные алгоритмы планирования

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

· Многоуровневые очереди с обратной связью

· Лотерейное планирование

· Планирование процессов реального времени в ядре Linux

· Традиционный алгоритм планирования

· Процедура планирования

· Начало новой эпохи

Многоуровневые очереди с обратной связью

Алгоритм многоуровневых очередей с обратной связью (multilevel feedback queues) является универсальным алгоритмом планирования (с помощью настройки параметров его можно свести почти к любому другому алгоритму), но при этом одним из самых сложных в реализации.

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

Различия между двумя алгоритмами заключаются в том, что:

· потокам разрешено переходить с уровня на уровень (из очереди в очередь);

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

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

Лотерейное планирование

Идея лотерейного планирования заключается в том, что:

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

· планировщик через промежуток времени Т выбирает один случайный лотерейный билет;

· поток, «выигравший», получает управление до следующего розыгрыша.

Лотерейное планирования позволяет:

· эмулировать круговое планирование, выдав каждому потоку одинаковое количество билетов;

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

· эмулировать SRTCF - давать коротким потокам больше билетов, чем длинным;

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

· динамично менять приоритеты, отбирая и добавляя билеты по ходу.

Хотя большинство этих задач может быть решено лотерейным планированием лишь приблизительно, с некоторой вероятностью, на практике получают не удовлетворительные результаты. При этом чем дольше работает система, то ближе будут результаты в теоретических значений (по закону больших чисел). На самом деле лотерейное планирования использует тот факт, что вся идеология планирования в значительной степени является эвристической, поскольку нельзя точно предсказать характер поведения потоков в системе.

Планирование процессов реального времени в ядре Linux

Относительно процессов реального времени, достаточно сказать, что:

· они всегда будут иметь при планировании приоритет перед обычными процессами;

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

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

Традиционный алгоритм планирования

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

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

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

Процедура планирования

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

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

Начало новой эпохи

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

Когда начинается новая эпоха, происходит перечисление квантов для всех процессов системы (не только для процессов в состоянии готовности).

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