Выделяют следующие критерии по отношению к используемой информации при процессе планирования
Глава 3. Планирование процессов
“Я планов наших люблю громадьё…”
В. В. Маяковский
“Чем тщательнее мы планируем свою деятельность,
тем меньше времени остается на ее осуществление.”
Из анналов Госплана
Всякий раз, когда нам приходится иметь дело с ограниченным количеством ресурсов и несколькими их потребителями, будь то фонд заработной платы в трудовом коллективе или студенческая вечеринка с несколькими ящиками пива, мы вынуждены заниматься распределением наличных ресурсов между потребителями или, другими словами, планированием использования ресурсов. Такое планирование должно иметь четко поставленные критерии (чего мы хотим добиться распределением ресурсов) и алгоритмы, соответствующие критериям и опирающиеся на параметры потребителей. Только при правильном выборе критериев и алгоритмов можно избежать таких вопросов, как “Почему я получаю в десять раз меньше, чем мой шеф?” или “А где мое пиво?”. Настоящая глава посвящена планированию исполнения процессов в мультипрограммных вычислительных системах или, кратко говоря, планированию процессов.
3.1. Уровни планирования
Планирование использования процессора выступает в качестве краткосрочного планирования процессов. Оно проводится, к примеру, при обращении исполняющегося процесса к устройствам ввода-вывода или просто по завершении определенного интервала времени. Поэтому краткосрочное планирование осуществляется весьма часто, как правило, не реже одного раза в 100 миллисекунд. Выбор нового процесса для исполнения оказывает влияние на функционирование системы до наступления очередного аналогичного события, т. е. в течение короткого промежутка времени, что и обусловило название этого уровня планирования — краткосрочное.
В некоторых вычислительных системах бывает выгодно для повышения их производительности временно удалить какой-либо частично выполнившийся процесс из оперативной памяти на диск, а позже вернуть его обратно для дальнейшего выполнения. Такая процедура в англоязычной литературе получила название swapping, что можно перевести на русский язык как перекачка, хотя в профессиональной литературе оно употребляется без перевода — свопинг. Когда и какой из процессов нужно перекачать на диск и вернуть обратно, решается дополнительным промежуточным уровнем планирования процессов — среднесрочным.
3.2. Критерии планирования и требования к алгоритмам
Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых мы хотим достичь, используя планирование. К числу таких целей можно отнести:
Независимо от поставленных целей планирования желательно также, чтобы алгоритмы обладали следующими свойствами:
Многие из приведенных выше целей и свойств являются противоречивыми. Улучшая работу алгоритма с точки зрения одного критерия, мы ухудшаем ее с точки зрения другого. Приспосабливая алгоритм под один класс задач, мы тем самым дискриминируем задачи другого класса. “В одну телегу впрячь не можно коня и трепетную лань”. Ничего не поделаешь. Такова жизнь.
3.3. Параметры планирования
Для осуществления поставленных целей разумные алгоритмы планирования должны опираться на какие-либо характеристики процессов в системе, заданий в очереди на загрузку, состояния самой вычислительной системы, иными словами, на параметры планирования. В этом разделе мы опишем ряд таких параметров, не претендуя на полноту изложения.
Все параметры планирования можно разбить на две большие группы: статические параметры и динамические параметры. Статические параметры не изменяются в ходе функционирования вычислительной системы, динамические же, напротив, подвержены постоянным изменениям.
К статическим параметрам вычислительной системы можно отнести предельные значения ее ресурсов (размер оперативной памяти, максимальное количество памяти на диске для осуществления свопинга, количество подключенных устройств ввода-вывода и т. п.). Динамические параметры системы описывают количество свободных ресурсов в текущий момент времени.
К статическим параметрам процессов относятся характеристики, как правило, присущие заданиям уже на этапе загрузки:
Алгоритмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны). Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают и динамические характеристики процессов. Для среднесрочного планирования в качестве таких характеристик может выступать следующая информация:
Рис 3.1. Фрагмент деятельности процесса с выделением промежутков непрерывного использования процессора и ожидания ввода-вывода.
Для краткосрочного планирования нам понадобится ввести еще два динамических параметра. Деятельность любого процесса можно представить как последовательность циклов использования процессора и ожидания завершения операций ввода-вывода. Промежуток времени непрерывного использования процессора носит на английском языке название CPU burst, а промежуток времени непрерывного ожидания ввода-вывода – I/O burst. На рисунке 3.1. показан фрагмент деятельности некоторого процесса на псевдоязыке программирования с выделением указанных промежутков. Для краткости изложения мы будем использовать термины CPU burst и I/O burst без перевода. Значения продолжительности последних и очередных CPU burst и I/O burst являются важными динамическими параметрами процесса.
3.4. Вытесняющее и невытесняющее планирование
Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh. При таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания завершения операции ввода-вывода или по окончании работы). Этот метод планирования относительно просто реализуем и достаточно эффективен, так как позволяет использовать большую часть процессорного времени на работу самих процессов и до минимума сократить затраты на переключение контекста. Однако при невытесняющем планировании возникает проблема возможности полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей вычислительной системы.
3.5. Алгоритмы планирования
Существует достаточно большой набор разнообразных алгоритмов планирования, которые предназначены для достижения различных целей и эффективны для разных классов задач. Многие из них могут быть использованы на нескольких уровнях планирования. В этом разделе мы рассмотрим некоторые наиболее употребительные алгоритмы применительно к процессу кратковременного планирования.
3.5.1. First-Come, First-Served (FCFS)
Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения своего текущего CPU burst. После этого для выполнения выбирается новый процесс из начала очереди.
Продолжительность очередного CPU burst
Рис 3.2. Выполнение процессов при порядке p0,p1,p2
Рис 3.3. Выполнение процессов при порядке p2,p1,p0
Как видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPU burst, то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала своего выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени. Слишком большим получается среднее время отклика в интерактивных процессах.
3.5.2. Round Robin (RR)
Рис 3.4. Процессы на карусели.
Критерии эффективности и свойства методов планирования процессов, параметры планирования процессов. Критерии планирования и требования к алгоритмам
Для каждого уровня планирования процессовможно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых мы хотим достичь, используяпланирование. К числу таких целей можно отнести следующие:
Справедливость – гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не начинал выполняться.
Эффективность – постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%.
Сокращение полного времени выполнения ( turnaround time ) – обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением.
Сокращение времени ожидания ( waiting time ) – сократить время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки.
Сокращение времени отклика ( response time ) – минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.
Независимо от поставленных целей планированияжелательно также, чтобы алгоритмы обладали следующими свойствами.
Были предсказуемыми. Одно и то же задание должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске.
Были связаны с минимальными накладными расходами. Если на каждые 100 миллисекунд, выделенные процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит.
Равномерно загружали ресурсы вычислительной системы, отдавая предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы.
Обладали масштабируемостью, т. е. не сразу теряли работоспособность при увеличении нагрузки. Например, рост количества процессов в системе в два раза не должен приводить к увеличению полного времени выполнения процессов на порядок.
Многие из приведенных выше целей и свойств являются противоречивыми. Улучшая работу алгоритма с точки зрения одного критерия, мы ухудшаем ее с точки зрения другого. Приспосабливаяалгоритмпод одинклассзадач, мы тем самым дискриминируем задачи другого класса.
Параметры планирования
Для осуществления поставленных целей разумные алгоритмы планированиядолжны опираться на какие-либо характеристики процессов в системе, заданий в очереди на загрузку, состояния самой вычислительной системы, иными словами, напараметры планирования. В этом разделе мы опишем ряд такихпараметров, не претендуя на полноту изложения.
Все параметрыпланированияможно разбить на две большие группы: статическиепараметрыи динамическиепараметры. Статическиепараметрыне изменяются в ходе функционирования вычислительной системы, динамические же, напротив, подвержены постоянным изменениям.
К статическим параметрамвычислительной системы можно отнести предельные значения ее ресурсов (размер оперативной памяти, максимальное количество памяти на диске для осуществления свопинга, количество подключенных устройств ввода-вывода и т. п.). Динамическиепараметрысистемы описывают количество свободных ресурсов на данный момент.
К статическим параметрампроцессов относятся характеристики, как правило присущие заданиям уже на этапе загрузки.
Каким пользователем запущен процесс или сформировано задание.
Насколько важной является поставленная задача, т. е. каков приоритет ее выполнения.
Сколько процессорного времени запрошено пользователем для решения задачи.
Каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода.
Какие ресурсы вычислительной системы (оперативная память, устройства ввода-вывода, специальные библиотеки и системные программы и т. д.) и в каком количестве необходимы заданию.
Алгоритмы долгосрочного планированияиспользуют в своей работе статические и динамическиепараметрывычислительной системы и статическиепараметрыпроцессов (динамическиепараметрыпроцессов на этапе загрузки заданий еще не известны). Алгоритмыкраткосрочногоисреднесрочного планированиядополнительно учитывают и динамические характеристики процессов. Длясреднесрочного планированияв качестве таких характеристик может использоваться следующаяинформация:
сколько времени прошло с момента выгрузки процесса на диск или его загрузки в оперативную память;
сколько оперативной памяти занимает процесс;
сколько процессорного времени уже предоставлено процессу.
Для краткосрочного планированиянам понадобится ввести еще два динамическихпараметра.Деятельностьлюбого процесса можно представить как последовательность циклов использования процессора и ожидания завершения операций ввода-вывода. Промежуток времени непрерывного использования процессора носит названиеCPU burst, а промежуток времени непрерывного ожидания ввода-вывода –I/O burst. Нарисунке 3.1.показан фрагмент деятельности некоторого процесса на псевдоязыке программирования с выделением указанных промежутков. Для краткости мы будем использовать терминыCPU burstиI/O burstбез перевода. Значения продолжительности последних и очередныхCPU burstиI/O burstявляются важными динамическимипараметрамипроцесса.
Критерии планирования (5 основных):
Справедливость – гарантия каждому заданию или процессу определенной части времени использования процессора, недопускание ситуации, когда один процесс исполняется постоянно, а другой (уже запущенный) не имеет доступа к процессору;
Эффективность использования ресурсов – алгоритм должен по максимуму занять процессор (реально процессор занимается на 40-60%);
Сокращение полного времени выполнения – обеспечение минимального времени между стартом процесса и его завершением;
Время ожидания – минимизация времени, которое проводят процессы в состоянии готовности;
Время отклика – минимизация времени на взаимодействие с внешними факторами (как с устройствами, так и с пользователем).
Свойства алгоритмов планирования:
Предсказуемость – одно и то же задание должно выполняться приблизительно за одно и то же время;
Масштабируемость – алгоритмы не должны терять работоспособность при увеличении нагрузки;
Минимальные расходы – соотношения времени выборки процесса на исполнение и времени исполнения должны быть существенны.
Статические параметры – это предельные значения ресурсов системы (объем оперативной памяти, частота процессора).
Динамические параметры – это количество ресурсов в текущий момент времени.
На этапе загрузки процесса появляются статические параметры:
каким пользователем запущен процесс;
сколько процессорного времени запрошено для решения задачи;
каково соотношение процессорного времени и времени, необходимого на операции ввода/вывода;
какие ресурсы, и в каком количестве необходимы (оперативная память, устройства ввода/вывода, специальные библиотеки).
Динамические параметры появляются после первого исполнения:
сколько времени прошло со времени выгрузки процесса на диск или загрузки его в оперативную память;
сколько оперативной памяти занимает процесс;
сколько процессорного времени было предоставлено процессу.
У процесса разделяют два состояния (временных). Эти параметры тоже являются динамическими и они измеряются после каждого очередного исполнения:
CPU burst – промежуток непрерывного исполнения на процессоре;
I/O burst – промежуток ожидания ввода/вывода.
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.
Планирование процессов. Критерии и параметры планирования
Процедура выбора очередного задания для загрузки в машину (порождение соответствующего процесса) называется планированием заданий. Планирование заданий появилось в пакетных системах после того, как для хранения сформированных пакетов заданий стали использоваться магнитные диски. Магнитные диски, являясь устройствами прямого доступа, позволяют загружать задания в компьютер в произвольном порядке, а не только в том, в котором они были записаны на диск. Изменяя порядок загрузки заданий в вычислительную систему, можно повысить эффективность ее использования. Различают три уровня планирования заданий: долгосрочное, краткосрочное и дополнительное среднесрочное.
1.Долгосрочного планирования процессов представляет собой планирование заданий, которое отвечает за порождение новых процессов в вычислительной системе, определяя ее степень мультипрограммирования (количество процессов, одновременно находящихся в вычислительной системе). Если степень мультипрограммирования системы поддерживается постоянной (среднее количество процессов не меняется), то новые процессы могут появляться только после завершения ранее загруженных. Поэтому долгосрочное планирование осуществляется достаточно редко, между появлением новых процессов могут проходить минуты или десятки минут.
Решение о выборе процесса для загрузки оказывает влияние на функционирование вычислительной системы на протяжении достаточно длительного времени. В некоторых операционных системах долгосрочное планирование сведено к минимуму или отсутствует. Например, во многих интерактивных системах разделения времени порождение процесса происходит сразу после появления соответствующего запроса. Поддержание разумной степени мультипрограммирования осуществляется за счет ограничения количества пользователей, которые могут работать в системе, и особенностей человеческой психологии. Если между нажатием на клавишу и появлением символа на экране проходит 20 – 30 секунд, то многие пользователи предпочитают продолжить работу, когда система будет менее загружена.
2.Краткосрочное планирование процессов представляет собой планирование использования процессора, которое возникает в мультипрограммных вычислительных системах для процедуры перевода процесса из состояния готовность в состояние исполнение. Оно проводится, например, при обращении исполняющегося процесса к устройствам ввода-вывода или просто по завершении определенного интервала времени. Поэтому краткосрочное планирование осуществляется, как правило, не реже одного раза в 100 миллисекунд.
3.Среднесрочное планирование процессов (дополнительное, промежуточное) используется для решения о выборе процесса и времени его перекачки на диск и обратно. Выбор нового процесса для исполнения оказывает влияние на функционирование системы до наступления очередного аналогичного события, то есть в течение короткого промежутка времени, чем и обусловлено название этого уровня планирования. В некоторых вычислительных системах бывает выгодно для повышения производительности временно удалить какой-либо частично выполнившийся процесс из оперативной памяти на диск, а позже вернуть его обратно для дальнейшего выполнения. Такая процедура получила название swapping (свопинг) – перекачка.
Для каждого уровня планирования процессов имеется набор специальных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой и целями планирования:
— справедливостью – гарантией каждому заданию или процессу определенной части времени использования процессора, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не начинал выполняться;
— эффективностью – максимальной занятостью процессора, не позволяющей ему простаивать в ожидании процессов, готовых к исполнению (в реальных вычислительных системах загрузка процессора колеблется от 40 до 90%);
— сокращением полного времени выполнения (turnaround time) – обеспечением минимального времени между стартом процесса (или его постановкой в очередь для загрузки) и его завершением;
— сокращением времени ожидания (waiting time) – времени, которое проводят процессы в состоянии готовность в очереди на исполнение;
— сокращением времени отклика (response time) – минимизированием времени, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.
Независимо от целей планирования, алгоритмы планирования должны обладать следующими свойствами:
— быть предсказуемыми, то есть одно и то же задание должно выполняться приблизительно за одно и то же время;
— иметь минимальные накладные расходы по использованию времени процессора (выбор процесса, перевод его из состояния ожидание в состояние исполнение, переключение контекста и пр.);
— равномерно загружать ресурсы вычислительной системы, отдавая предпочтение процессам, занимающим малоиспользуемые ресурсы;
— обладать масштабируемостью – не терять работоспособность при увеличении нагрузки.
Многие из приведенных выше целей и свойств являются противоречивыми. При улучшении работы алгоритма с точки зрения одного критерия, ухудшается его работа с точки зрения другого. Для осуществления поставленных целей алгоритмы планирования должны опираться на параметры планирования, которые подразделяются на две группы: статические и динамические.
Статические параметры – параметры, не изменяющиеся в ходе функционирования вычислительной системы. К ним относятся: предельные значения ресурсов вычислительной системы (размер оперативной памяти, максимальное количество памяти на диске для осуществления свопинга, количество подключенных устройств ввода-вывода и т.п.) и характеристики, которые присущи заданиям на этапе загрузки:
— каким пользователем запущен процесс или сформировано задание;
— каков приоритет задачи, поставленной на выполнение;
— сколько процессорного времени запрошено для решения задачи;
— каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода;
— какие ресурсы вычислительной системы (оперативная память, устройства ввода-вывода, специальные библиотеки и системные программы и пр.) и в каком количестве необходимы заданию.
Динамические параметры системы описывают количество свободных ресурсов на данный момент, в результате чего подвержены постоянным изменениям.
Алгоритмы долгосрочного планирования используют в своей работе статические и динамические параметры вычислительной системы и статические параметры процессов (динамические параметры процессов на этапе загрузки заданий еще не известны). Алгоритмы краткосрочного и среднесрочного планирования дополнительно учитывают динамические характеристики процессов. Для среднесрочного планирования в качестве таких характеристик используется следующая информация:
— сколько времени прошло с момента выгрузки процесса на диск или его загрузки в оперативную память;
— сколько оперативной памяти занимает процесс;
— сколько процессорного времени уже предоставлено процессу.
Для краткосрочного планирования используются два динамических параметра:
— CPU burst – промежуток времени непрерывного использования процессора;
— I/O burst – промежуток времени непрерывного ожидания ввода-вывода.
Деятельность любого процесса можно представить как последовательность циклов использования процессора и ожидания завершения операций ввода-вывода (рис.3.7.).
 |
Процесс планирования, осуществляемый частью операционной системы, называемой планировщиком. Планировщик может принимать решения о выборе для исполнения нового процесса из числа находящихся в состоянии готовность в следующих четырех случаях:
— процесс переводится из состояния исполнение в состояние завершил исполнение;
— процесс переводится из состояния исполнение в состояние ожидание;
— процесс переводится из состояния исполнение в состояние готовность (например, после прерывания от таймера);
— процесс переводится из состояния ожидание в состояние готовность (завершилась операция ввода-вывода или произошло другое событие).
В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и для выполнения необходимо выбрать новый процесс. В случаях 3 и 4 планирование может не проводиться, процесс, который исполнялся до прерывания, может продолжать свое выполнение после обработки прерывания. Если планирование осуществляется только в случаях 1 и 2, то имеет место невытесняющее (nonpreemptiw) планирование. В противном случае – вытесняющее (preempts) планирование. Термин «вытесняющее планирование» возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.
Вытесняющее планирование обычно используется в системах разделения времени. В этом режиме планирования процесс может быть приостановлен в любой момент исполнения. Операционная система устанавливает специальный таймер для генерации сигнала прерывания по истечении некоторого интервала времени – кванта. После прерывания процессор передается в распоряжение следующего процесса. Временные прерывания помогают гарантировать приемлемое время отклика процессов для пользователей, работающих в диалоговом режиме, и предотвращают зависание компьютерной системы из-за зацикливания какой-либо программы.
При невытесняющем режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. Переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания операции ввода-вывода или по окончании работы). Этот метод планирования просто реализуем и достаточно эффективен, так как позволяет выделить большую часть процессорного времени для работы самих процессов и до минимума сократить затраты на переключение контекста. Однако имеется возможность полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В этом случае требуется перезагрузка всей вычислительной системы. Невытесняющее планирование используется в Windows 3.1., Apple Macintosh и др.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет