Лекция: ДИСПЕТЧЕРИЗАЦИИ ПРОЦЕССОВ И ПОТОКОВ
Принципы планирования процессов и потоков
Переход от одного потока к другому осуществляется в результате планирования и диспетчеризации. Работа по определению того, в какой момент необходимо прервать выполнение текущего активного потока и какому потоку предоставить возможность выполняться, называется планированием. Планирование реализуется компонентой ОС, называемой планировщиком (scheduler).
Планирование потоков осуществляется на основе информации, хранящейся в описателях (дескрипторах) процессов и потоков. При планировании могут приниматься во внимание приоритет потоков, время их ожидания в очереди, накопленное время выполнения, интенсивность обращений к вводу-выводу и другие факторы. ОС планирует выполнение потоков независимо от того, принадлежат ли они одному или разным процессам. Так, например, после выполнения потока некоторого процесса ОС может выбрать для выполнения другой поток того же процесса или же назначить к выполнению поток другого процесса. Планирование потоков, по существу, включает в себя решение двух задач /1/:
1) определение момента времени для смены текущего активного потока;
2) выбор для выполнения потока из очереди готовых потоков.
Существует множество различных алгоритмов планирования потоков, по-своему решающих каждую из приведенных выше задач. Алгоритмы планирования (иногда их называют дисциплины диспетчеризации) могут преследовать различные цели и обеспечивать разное качество мультипрограммирования.
Например, в одном случае выбирается такой алгоритм планирования, при котором гарантируется, что ни один поток/процесс не будет занимать процессор дольше определенного времени, в другом случае целью является максимально быстрое выполнение «коротких» задач, а в третьем случае – преимущественное право занять процессор получают потоки интерактивных приложений. Именно особенности реализации планирования потоков в наибольшей степени определяют специфику операционной системы, в частности, является ли она системой пакетной обработки, системой разделения времени или системой реального времени.
В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line), то есть решения принимаются во время работы системы на основе анализа текущей ситуации. ОС работает в условиях неопределенности – потоки и процессы появляются в случайные моменты времени и также непредсказуемо завершаются. Динамические планировщики могут гибко приспосабливаться к изменяющейся ситуации и не используют никаких предположений о мультипрограммной смеси. Для того чтобы оперативно найти в условиях такой неопределенности оптимальный в некотором смысле порядок выполнения задач, ОС должна затрачиваться значительные ресурсы.
Другой тип планирования – статический (off-line) – может быть использован в специализированных системах, в которых весь набор одновременно выполняемых задач определен заранее, например, в системах реального времени. Планировщик называется статическим (или предварительным планировщиком), если он принимает решения о планировании не во время работы системы, а заранее.
Соотношение между динамическим и статическим планировщиками аналогично соотношению между диспетчером железной дороги, который пропускает поезда строго по предварительно составленному расписанию, и регулировщиком на перекрестке автомобильных дорог, не оснащенном светофорами, который решает, какую машину остановить, а какую пропустить, в зависимости от ситуации на перекрестке.
Результатом работы статического планировщика является таблица, называемая расписанием, в которой указывается, какому процессу/потоку, когда и на какое время должен быть предоставлен процессор. Для построения расписания планировщику нужны как можно более полные предварительные знания о характеристиках набора задач, например о максимальном времени выполнения каждой задачи, ограничениях предшествования, ограничениях по взаимному исключению, предельным срокам и т.д.
После того как расписание готово, оно может использоваться ОС для переключения потоков и процессов. При этом накладные расходы ОС на исполнения расписания оказываются значительно меньшими, чем при динамическом планировании, и сводятся лишь к диспетчеризации потоков/процессов.
Диспетчеризация заключается в реализации найденного в результате планирования (динамического или статического) решения, то есть в переключении процессора с одного потока на другой. Прежде чем прервать выполнение потока, ОС запоминает его контекст, с тем, чтобы впоследствии использовать эту информацию для последующего возобновления выполнения данного потока. Контекст отражает, во-первых, состояние аппаратуры компьютера в момент прерывания потока: значение счетчика команд, содержимое регистров общего назначения, режим работы процессора, флаги, маски прерываний и другие параметры. Во-вторых, контекст содержит параметры операционной среды, а именно ссылки на открытые файлы, данные о незавершенных операциях ввода-вывода, коды ошибок выполняемых данным потоком системных вызовов и т.д. Процесс диспетчеризации осуществляется диспетчером (dispatcher) ОС.
Диспетчеризация сводится к следующему:
1)сохранению контекста текущего потока, который требуется сменить;
2)загрузке контекста нового потока, выбранного в результате планирования;
3)запуску нового потока на выполнение.
Поскольку операция переключения контекстов существенно влияет на производительность ВС, программные модели ОС выполняют диспетчеризацию потоков совместно с аппаратными средствами процессора.
Классификация алгоритмов планирования (вытесняющие и невытесняющие, бесприоритетные и приоритетные алгоритмы)
С самых общих позиций все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие алгоритмы планирования /1,7,8,10/.
Невытесняющие (non-preemptive) алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению поток.
Вытесняющие (preemptive) алгоритмы – это такие способы планирования потоков, в которых решение о переключении процессора с выполнения одного потока на выполнение другого потока принимается ОС, а не активной задачей.
Основным различием между вытесняющими и невытесняющими алгоритмами является степень централизации механизма планирования потоков. При вытесняющем мультипрограммировании функции планирования потоков целиком сосредоточены в операционной системе и программист разрабатывает свое приложение, не заботясь о том, что оно будет выполняться одновременно с другими задачами. При этом операционная система выполняет следующие функции: определяет момент снятия с выполнения активного потока, запоминает его контекст, выбирает из очереди готовых потоков следующий, запускает новый поток на выполнение, загружая его контекст.
При невытесняющем мультипрограммировании механизм планирования распределен между ОС и прикладными программами. Прикладная программа, получив управление от ОС, сама определяет момент завершения очередного цикла своего выполнения и только затем передает управление ОС с помощью какого-либо системного вызова. ОС формирует очереди потоков и выбирает в соответствии с некоторым правилом (например, с учетом приоритетов) следующий поток на выполнение. Такой механизм создает проблемы как для пользователей, так и для разработчиков приложений.
Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме.
Поэтому разработчики приложений для операционной среды с невытесняющей многозадачностью вынуждены, возлагая на себя часть функций планировщика, создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам. Для этого в программе должны быть предусмотрены частые передачи управления ОС. Крайним проявлением «не дружественности» приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм имеет возможность снять зависшую задачу с выполнения.
Однако распределение функций планирования потоков между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложения самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент возвращения управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко решаются проблемы совместного использования данных: задача во время каждого цикла выполнения использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит данные. Существенным преимуществом невытесняющего планирования является более высокая скорость переключения с потока на поток.
В большинстве современных ОС, например, Windows 2000/XP используются вытесняющие алгоритмы планирования/11/.
Далее среди множества алгоритмов планирования выделяются два больших класса – бесприоритетные и приоритетные алгоритмы (рис.3.1) /7,8,12/.
При бесприоритетном планировании выбор процессов или потоков производится в соответствие с некоторым заранее установленным порядком без учета их относительной важности и времени обслуживания.
При реализации приоритетных дисциплин обслуживания отдельным процессам и потокам предоставляется преимущественное право перейти в состояние выполнения в соответствии с установленными для них приоритетами. Приоритеты могут быть фиксированным (постоянными) и динамическими (изменяемыми в ходе вычислительного процесса), что, конечно, требует дополнительных ресурсов ВС на вычисление приоритетов и усложняет ОС.
Линейные алгоритмы планирования
Эти алгоритмы планирования реализуют выполнение процессов и потоков в порядке очереди, которая организуется согласно тем или иным соглашениям/7,8,12/.
Самой простой в реализации является дисциплина обслуживания, при которой процессы и потоки выполняются (обслуживаются) в порядке их появления в ВС. Этот алгоритм называется «первым пришел – первым обслужен» или FCFS (First come – First Served). Те процессы и потоки, которые были заблокированы в процессе выполнения, например, попали в состояние ожидания из-за операций ввода-вывода, после перехода в состояние готовности вновь ставятся в очередь готовности. При этом возможны два варианта.
В первом наиболее простом варианте разблокированный процесс или поток ставится в конец очереди готовых процессов и потоков.
Во втором варианте планировщик помещает разблокированный процесс или поток перед теми процессами или потоками, которые еще не выполнялись. Таким образом, образуются две очереди: одна очередь образуется из новых процессов или потоков, а вторая очередь — из ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать стратегию обслуживания «закачивать выполнение процессов или потоков в порядке их появления». Рассмотренный алгоритм относится к невытесняющим.
Примечание. Простой аналогией рассмотренному алгоритму может служить прием экзаменов у студентов, когда к преподавателю образуется две очереди: первая – студентов, отвечающих на вопросы экзаменационных билетов, а вторая – студентов, уже ответивших на вопросы билетов и готовящих ответ на дополнительные вопросы преподавателя.
К основным преимуществам этого алгоритма можно отнести его простую реализацию, справедливость (в том же смысле, в каком справедлива любая очередь) и малые затраты системных ресурсов на формирование очереди задач.
Существенным недостатком алгоритма является рост среднего времени ожидания обслуживания при увеличении загрузки ВС, причем короткие процессы, требующие небольших затрат машинного времени, вынуждены ожидать столько же, сколько и трудоемкие.
Избежать указанного недостатка позволяет невытесняющий алгоритм, при котором планировщик выбирает первым для выполнения самый короткий процесс (задачу). Этот алгоритм называется «кратчайший процесс (задача) – первый» или SJN (Shortest Job Next)/7,8,12/. Алгоритм позволяет уменьшить оборотное время – среднее время от момента поступления процесса (задачи) на выполнение до завершения выполнения.
Пусть имеется четыре процесса со временем выполнения первого — a, второго — b, третьего – c и четвертого — d. Тогда первый процесс выполнится через время ta=a, второй – через время tb=a+b, третий через время tc=a+b+c, а четвертый через время td=a+b+c+d. Следовательно, среднее оборотное время toвычисления четырех процессов равно to=(ta+tb+tc+td)/4 =(4a+3b+2c+d)4. Очевидно, что вклад времени a в среднее больше, чем всех остальных интервалов времени, поэтому первым должен выполняться самый короткий процесс, а последним – самый длинный, вносящий вклад, равный собственному оборотному времени. Этот вывод справедлив для любого количества процессов и потоков.
Пример 3.1. Положим, имеется четыре процесса со временем выполнения первого a=10, второго b=8, третьего c=6 и четвертого d=4 единиц времени.
Вычислим среднее оборотное время to1 четырехпроцессов для случая выполнения в порядке a-b-c-d. Это время равно to1=(4a+3b+2c+d)4=20.
Вычислим среднее оборотное время to2 четырехпроцессов для случая выполнения в порядке «кратчайший процесс — первый», т.е. d-c-b-a. Это время равно to2=(4d+3c+2b+a)4=15. Очевидно, to1> to2.
Рассмотренный алгоритм прост и эффективен, но предполагает, что времена выполнения процессов известны заранее, что не всегда возможно. Более того, пользователь может злоупотреблять возможностями алгоритма и указывать заведомо меньшее время выполнения некоторых процессов, чтобы получить результаты этих процессов раньше других. Для этого планировщик дополняют функциями сравнения указанного времени выполнения и реально затраченного времени и в случае значительного превышения реальных затрат над заказанными, производит перестановку процесса в очереди процессов.
Следующей версией предыдущего алгоритма планирования является алгоритм наименьшего оставшегося времени выполнения или SRT (Shortest Remaining Time)/7,8,12/. В соответствии с этим алгоритмом планировщик всякий раз выбирает на выполнение процесс с наименьшим оставшимся временем выполнения. Когда появляется новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса. Если время выполнения нового процесса меньше, текущий процесс приостанавливается и управление передается новому процессу. Этот алгоритм позволяет быстро обслуживать короткие процессы.
Упражнение 3.1. В каком порядке в зависимости от уровня подготовки студентов преподавателю целесообразно проводить опрос студентов на экзамене, чтобы экзамен не был чрезмерно долгим? В каком порядке в зависимости от сложности вопросов в экзаменационном билете студенту целесообразно отвечать на вопросы в билете, чтобы сократить сроки ответа?
Алгоритмы планирования, основанные на квантовании
В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени – квант (time slice). Этот алгоритм получил название циклического (карусельного) или RR (Round Robin) /1,7,8,12/.
Смена активного потока происходит, если:
поток завершился и покинул систему;
произошла ошибка;
поток перешел в состояние ожидания;
исчерпан квант процессорного времени, отведенный данному потоку.
Кванты, выделяемые потоками, могут быть одинаковыми для всех потоков или различными. Рассмотрим, например, случай, когда всем потокам предоставляются кванты одинаковой длины q. Если в системе имеется n потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оценить как q(n-1). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q(n-1) все равно будет достаточно мало для того, чтобы пользователь не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет единицы — десятки миллисекунд.
Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании ВС). Действительно, поскольку время ожидания между двумя циклами выполнения равно q(n-1), а количество циклов B/q, где B – требуемое время выполнения, то W=(B\q)xq(n-1)=B(n-1).
Заметим, что это соотношение основано на предположении, что B>>q. При этом не учитывается, что потоки могут использовать кванты не полностью, что часть времени они могут потратить на ввод-вывод, что количество потоков в системе может динамически меняться и т.д.
Чем больше квант, тем выше вероятность того, что потоки завершатся в результате первого же цикла выполнения, и тем менее явной становится зависимость времени ожидания потоков от их времени выполнения. При достаточно большом кванте алгоритм квантования вырождается в алгоритм последовательной обработки, присущий однопрограммным системам, при котором время ожидания задачи в очереди вообще никак не зависит от ее длительности.
Кванты, выделяемые одному потоку, могут быть фиксированной величины, а могут и изменяться в разные периоды жизни потока. Пусть, например, первоначально каждому потоку назначается довольно большой квант, а величина каждого следующего кванта уменьшается до некоторой заранее заданной величины. В таком случае преимущество получают короткие задачи, которые успевают выполняться в течение первого кванта, а длительные вычисления будут производиться в фоновом режиме. Можно представить себе алгоритм планирования, в котором каждый следующий квант, выделяемый определенному потоку, больше предыдущего. Такой подход позволяет уменьшить накладные расходы на переключение задач в том случае, когда сразу несколько задач выполняют длительные вычисления.
Потоки получают для выполнения квант времени, но некоторые из них используют его не полностью, например, из-за необходимости выполнить ввод или вывод данных. В результате возникает ситуация, когда потоки с интенсивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени. Алгоритм планирования может исправить эту «несправедливость» /1/.
В качестве компенсации за неиспользованные полностью кванты потоки получают привилегии при последующем обслуживании. Для этого планировщик создает две очереди готовых потоков (рис.3.2). Очередь 1 образована потоками, которые пришли в состояние готовности в результате исчерпания кванта времени, а очередь 2 – потоками, у которых завершилась операция ввода-вывода. При выборе потока для выполнения, прежде всего просматривается вторая очередь, и только если она пуста, квант выделяется потоку из первой очереди.
Алгоритмы планирования, основанные на приоритетах
Другой важной концепцией, лежащей в основе многих вытесняющих алгоритмов планирования, является приоритетное обслуживание. Приоритетное обслуживание предполагает наличие у потоков некоторой изначально известной характеристики – приоритета, на основании которой определяется порядок их выполнения/1,7,8,12/. Приоритет – это число, характеризующее степень привилегированности потока при использовании ресурсов вычислительной машины, в частности процессорного времени: чем выше приоритет, тем выше привилегии, тем меньше времени будут проводить поток в очередях.
Приоритет может выражаться целым или дробным, положительным или отрицательным значением. В некоторых ОС принято, что приоритет потока тем выше, чем больше (в арифметическом смысле) число, обозначающее приоритет. В других системах, наоборот, чем меньше число, тем выше приоритет.
В большинстве ОС, поддерживающих потоки, приоритет потока непосредственно связан с приоритетом процесса, в рамках которого выполняется данный поток. Приоритет процесса назначается ОС при его создании. Значение приоритета включается в описатель процесса и используется при назначении приоритета потокам этого процесса. При назначении приоритета вновь созданному процессу ОС учитывает, является ли этот процесс системным или прикладным, каков статус пользователя, запустившего процесс, было ли явное указание пользователя на присвоение процессу определенного уровня приоритета. Поток может быть инициирован не только по команде пользователя, но и в результате выполнения системного вызова другим потоком. В этом случае при назначении приоритета новому потоку ОС должна принимать во внимание значение параметров системного вызова.
Во многих ОС предусматривается возможность изменения приоритетов в течение жизни потока. Изменение приоритета могут происходить по инициативе самого потока, когда он обращается с соответствующим вызовом к операционной системе, или по инициативе пользователя, когда он выполняет соответствующую команду. Кроме того, ОС сама может изменять приоритеты потоков в зависимости от ситуации, складывающейся в системе. В последнем случае приоритеты называются динамическими в отличие от неизменяемых, фиксированных, приоритетов.
От того, какие приоритеты назначены потокам, существенно зависит эффективность работы всей вычислительной системы. В современных ОС во избежание разбалансировки системы, которая может возникнуть при неправильном назначении приоритетов, возможности пользователя влиять на приоритеты процессов и потоков стараются ограничивать. При этом обычные пользователи, как правило, не имеют права повышать приоритеты своим потокам, это разрешено делать (да и то в определенных пределах) только администраторам. В большинстве же случаев ОС присваивает приоритеты потокам по умолчанию.
Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.
В обоих случаях выбор потока на выполнение из очереди готовых осуществляется одинаково: выбирается поток, имеющий наивысший приоритет.
Однако проблема определения момента смены активного потока решается по-разному.
В системах с относительными приоритетами (рис.3.3) активный поток выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (или же произойдет ошибка, или поток завершится).
В системах с абсолютными приоритетами (рис.3.4) выполнение активного потока прерывается еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока. В этом случае прерванный поток переходит в состояние готовности.
В системах с абсолютными приоритетами время ожидания потока в очередях может быть сведено к минимуму, если ему назначить самый высокий приоритет. Такой поток будет вытеснять из процессора все остальные потоки (кроме потоков, имеющих такой же наивысший приоритет). Это делает планирование на основе абсолютных приоритетов подходящим для систем управления объектами, в которых важна быстрая реакция на событие.
Смешанные алгоритмы планирования
Во многих ОС алгоритмы планирования построены с использованием как концепции квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора потока из очереди готовых определяется приоритетами потоков.
В таких случаях удобно сгруппировать процессы в классы по приоритетам и использовать приоритетное планирование среди классов, но циклическое планирование внутри каждого класса.
Подобным образом реализовано планирование в системах Windows NT/2000, в которых квантование сочетается с динамическими абсолютными приоритетами. На выполнение выбирается готовый поток с наивысшим приоритетом и ему выделяется квант времени. Если во время выполнения в очереди готовых потоков появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток. Вытесняющий поток возвращается в очередь готовых, причем он становится впереди всех остальных потоков имеющих такой же приоритет.
В UNIX – подобных ОС планировщик управляет процессами в зависимости от того, как долго они занимают процессор, без перехода в состояние ожидания. У тех процессов, которые потребляют большие периоды процессорного времени без перехода в состояние ожидания, приоритет снижается, а у тех процессов, которые часто уходят в состояние ожидания после короткого периода использования процессора, приоритет повышается. Таким образом, хотя низкоприоритетный процесс и не работает так часто, как высокоприоритетный, зато на этапе выполнения ему выделяется больше процессорного времени.
ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ