Мультипрограммирование в системах разделения времени

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

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

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

Мультипрограммирование в системах реального времени

Еще одна разновидность мультипрограммирования используется в системах реального времени, предназначенных для управления от компьютера различными техническими объектами (например, станком, спутником, научной экспериментальной установкой и т. д.) или технологическими процессами (например, гальванической линией, доменным процессом и т. п.). Во всех этих случаях существует предельно допустимое время, в течение которого должна быть выполнена та или иная управляющая объектом программа. В противном случае может произойти авария: спутник выйдет из зоны видимости, экспериментальные данные, поступающие с датчиков, будут потеряны, толщина гальванического покрытия не будет соответствовать норме. Таким образом, критерием эффективности здесь является способность выдерживать заранее заданные интервалы времени между запуском программы и получением результата (управляющего воздействия). Это время называется временем реакции системы, а соответствующее свойство системы — реактивностью. Требования ко времени реакции зависят от специфики управляемого процесса. Контроллер робота может требовать от встроенного компьютера ответ в течение менее 1 мс, в то время как при моделировании полета может быть приемлем ответ в 40 мс.

В системах реального времени мультипрограммная смесь представляет собой фиксированный набор заранее разработанных программ, а выбор программы на выполнение осуществляется по прерываниям (исходя из текущего состояния объекта) или в соответствии с расписанием плановых работ.

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

Управление задачами в ОС. Планирование и диспетчеризация процессов потоков.

Управление процессами

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

Создание процессов и потоков

• Создать процесс - это прежде всего создать описатель процесса, который необходим ОС для управления им (например: идентификатор процесса, степень привилегированности)
• Примеры описателей процесса:
• Блок управления задачей (ТСВ) в OS/360
• Управляющий блок процесса (РСВ) в OS/2
• Дескриптор процесса в UNIX
• Объект-процесс в Windows
• Создание процесса включает загрузку кодов и данных в оперативную память
• В многопоточной системе при создании процесса ОС создает поток
• Поток-потомок

Планирование и диспетчеризация потоков

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

• Определение момента времени для смены текущего активного потока
• Выбор для выполнения потока из очереди готовых потоков

Диспетчеризация - это реализация решения, найденного в результате планирования Задачи диспетчеризации:

• Сохранение контекста текущего потока
• Загрузка контекста нового потока
• Запуск нового потока на выполнение

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

Управление процессами

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

Состояние потоков

• ВЫПОЛНЕНИЕ - активное состояние потоков, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
• ОЖИДАНИЕ - пассивное состояние потока, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого потока, освобождения какого-либо необходимого ему ресурса;
• ГОТОВНОСТЬ - также пассивное состояние потока, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: поток имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого потока.

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

В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ - несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно " вытеснен" из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

Стратегии планирования и дисциплины диспетчеризации. Граф состояния процессов и потоков.

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

a) по возможности заканчивать вычислительные процессы в том же самом порядке, в котором они были начаты;

b) отдавать предпочтение более коротким процессам;

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

Известно большое количество правил (дисциплин) диспетчеризации, в соответствии с которыми формируется список (очередь) готовых к выполнению задач. Различают два больших класса таких дисциплин – бесприоритетные и приоритетные. При реализации приоритетных дисциплин отдельным задачам предоставляется преимущественное право попасть в состояние исполнения..

Самой простой в реализации является дисциплина FCFS (first come – first served), согласно которой задачи обслуживаются в порядке очереди, т.е. в порядке их появления. Те задачи, которые были заблокированы в процессе работы, после перехода в состояние готовности ставятся в эту очередь перед теми задачами, которые еще не выполнялись, т.е. образуется две очереди – одна из новых задач, а вторая очередь – из ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычислительные процессы в порядке их появления».

К достоинствам этой дисциплины можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач.

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

Дисциплина обслуживания SJN (shortest job next – следующим будет выполняться кратчайшее задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Для этого были разработаны специальные языковые средства, например, язык JCL (job control language – язык управления заданиями). Пользователи должны были указывать предполагаемое время выполнения, а чтобы они не ловчили, ввели подсчет реальных потребностей. Если обнаруживался обман, то задание ставилось в конец очереди или оплата шла по более высоким тарифам.

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

Для устранения этого недостатка была предложена дисциплина SRT (shortest remaining time) – следующее задание требует меньше всего времени для своего завершения.

Все эти три дисциплины могут использоваться для пакетных режимов обработки, когда пользователь сдает свое задание, не ожидает реакции системы, а ему нужен только результат вычислений. Для интерактивных вычислений желательно обеспечить приемлемое время реакции системы и равенство в обслуживании, если система является мультитерминальной. Для однопользовательских систем с возможностью мультипрограммной обработки желательно, чтобы программы, с которыми работают непосредственно, имели лучшее время реакции, чем фоновые задания. Для решения подобных проблем используется дисциплина обслуживания RR(round robin – круговая, карусельная) и приоритетные методы обслуживания.

Граф состояний представляет собой упорядоченный граф, вершинами которого являются возможные состояния S_i и между двумя состояниями существует ребро - стрелка, если возможен непосредственный переход между состояниями.

Принципы планирования процессов и потоков. Классификация алгоритмов планирования.

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

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

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

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

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

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

Классификация алгоритмов планирования (вытесняющие и невытесняющие, бесприоритетные и приоритетные алгоритмы)

Вытесняющие и невытесняющие алгоритмы планирования ОС. Приоритетные и бесприоритетные алгоритмы планирования

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

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

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

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

Далее среди множества алгоритмов планирования выделяются два больших класса – бесприоритетные и приоритетные алгоритмы (рис.3.1) /7, 8, 12/.

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

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

Алгоритмы планирования основанные на квантовании. Обоснование выбора величины квантов времени. Задание квантов времени в мультипрограммных ОС и управление их величиной.

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

Квант — это временной интервал, в течение которого процессу разрешено занимать процессор, т.е. разрешено находиться в состоянии ВЫПОЛНЕНИЯ. Понятие кванта основывается на периоде таймера, который называется тиком. Тик (tick) — минимально возможный временной интервал, который равен дискретному промежутку времени между двумя сигналами таймера, генерируемыми через каждые 55мс.

Квант равен целому числу тиков из промежутка от 1 до 255. Увеличение кванта замедляет реакцию системы при увеличении очереди, а уменьшение — увеличивает долю накладных временных расходов на переключение процессов. Для эффективной работы системы необходимо находить разумный компромисс.

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

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

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

Рис. 4.6. Граф состояний потока в системе с квантованием

Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными. Рассмотрим, например, случай, когда всем потокам предоставляются кванты одинаковой длины q (рис. 4.7). Если в системе имеется п потоков, то время, которое поток проводит в ожидании следующего кванта, можно грубо оценить как q(n-l). Чем больше потоков в системе, тем больше время ожидания, тем меньше возможности вести одновременную интерактивную работу нескольким пользователям. Но если величина кванта выбрана очень небольшой, то значение произведения q(n-l) все равно будет достаточно мало для того, чтобы пользователь не ощущал дискомфорта от присутствия в системе других пользователей. Типичное значение кванта в системах разделения времени составляет десятки миллисекунд.

Рис. 4.7. Иллюстрация расчета времени ожидания в очереди

Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании вычислительной системы). Действительно, поскольку время ожидания между двумя циклами выполнения равно q(n-l), а количество циклов B/q, где В — требуемое время выполнения, то W*B(n-l). Заметим, что эти соотношения представляют собой весьма грубые оценки, основанные на предположении, что В значительно превышает q. При этом не учитывается, что потоки могут использовать кванты не полностью, что часть времени они могут тратить на ввод-вывод, что количество потоков в системе может динамически меняться и т. д.

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

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

Потоки получают для выполнения квант времени, но некоторые из них используют его не полностью, например из-за необходимости выполнить ввод или вывод данных. В результате возникает ситуация, когда потоки с интенсивными обращениями к вводу-выводу используют только небольшую часть выделенного им процессорного времени. Алгоритм планирования может исправить эту «несправедливость». В качестве компенсации за неиспользованные полностью кванты потоки получают привилегии при последующем обслуживании. Для этого планировщик создает две очереди готовых потоков (рис. 4.8). Очередь 1 образована потоками, которые пришли в состояние готовности в результате исчерпания кванта времени, а очередь 2 — потоками, у которых завершилась операция ввода-вывода. При выборе потока для выполнения прежде всего просматривается вторая очередь, и только если она пуста, квант выделяется потоку из первой очереди.

Алгоритмы планирования основанные на приоритетах. Понятие приоритета и очереди процессов. Абсолютные и относительные приоритеты

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

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

Относительные и абсолютные приоритеты

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

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

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

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

Рис. 8. Графы состояний потоков в системах с относительными и абсолютными приоритетами.

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