Многоразовые операции над процессами
Одноразовые операции всегда связаны с изменением количества процессов в системе (рождение и завершение процессов, освобождение ресурсов).
Запуск процесса.
На запуск выбирается процесс, стоящий в очереди готовых процессов. После того как процесс будет запущен его состояние будет изменено и он перейдет из состояния готовности в состояние исполнения => изменение PCB.
Приостановка процесса.
Работа процесса, находящегося в исполнении приостанавливается, как результат некоторого прерывания при этом сохраняется счетчик команд. Обязательно происходит обработка прерывания. Она производится специальной программой, находящейся по соответствующему адресу. ОС сохраняет динамическую часть системного и регистрового контекста процесса, переводит процесс в состояние готовности и преступает к обработке прерываний.
Блокировка/разблокировка процесса.
Процесс блокируется, если он не может продолжить работу по каким-либо причинам, например, он должен ожидать появления некоторого события.
Предположим, что в ОС произошло некоторое событие, ОС обязательно сначала должна определить что это за событие, тогда системы проверяет, находится ли какой-нибудь процесс в состоянии ожидания данного события, тогда этот процесс переводится в состояние готовности и ставится в очередь готовых к выполнению процессов.
Переключение контекста.
Деятельность мультипрограммной ОС состоит из цепочек операций, выполняемых над различными процессами и сопровождается переключением процессора с одного процесса на другой.
| Выполнение Прерывание Выполенение Восстановление ПРОЦЕСС 1 Кода кода ОС контекста |
| Ожидание сохр Обработка Планирование ПРОЦЕСС 2 Контекста прерывания Исполнение |
Переключение требует времени. Существенно, чтобы сокращались расходы времени на прерывание контекста. Расширенная модель предполагает организацию под процессор.
Планирование процесса.
Планирование процессов нужно, потому что необходимо распределять ресурсы между процессами. В конечном итоге д/б ясно чего мы хотим добится в реализации наших планов.
Уровни планирования
Ранее говорилось о двух видах планирования:
· Планирование заданий;
· Планирование использования процессора.
Изменяя порядок загрузки заданий с диска, можно повысить эффективность использования ВС. Задача – пропустить максимальное количество программ через ВС. Процедуру выбора очередного задания для загрузки, т.е. порождение нового процесса и назвали планированием заданий. Планирование возникает в мультипрограммных системах (МПС), где в состоянии готовности в очереди могут одновременно находиться несколько процессов. Планирование заданий можно назвать долгосрочным планированием. Это планирование отвечает за порождение новых процессов в системе. Долгосрочное планирование, связанное с вводом/выводом заданий – редкое событие. Поддержание разумной степени мультипрограммирования осуществляют за счет ограничений количества пользователей. Планирование использования процессора – это краткосрочное планирование (переключаться с процесса на процесс при фиксированном количестве процессов в системе можно много раз даже в течение одной секунды). Для краткосрочного увеличения производительности бывает выгодно временно удалить частично выполнившийся процесс из оперативной памяти на диск. Эта выгрузка называется «swapping». Когда и какой из процессов перекачать на диск или вернуть обратно, решается дополнительно промежуточным уровнем планирования процесса – среднесрочный уровень.
Критерии планирования и требовании к алгоритмам.
Алгоритм определяется тем, чего мы хотим добиться. Цели планирование:
a) Справедливость – гарантия предоставления каждому заданию/процессу времени процессора;
b) Эффективность – постараться занять процессор на 100%;
c) Сокращение полного времени выполнения – обеспечение минимального времени между стартом задачи и изъятия ее;
d) Сокращение времени ожидания – минимизация времени, в течение которого процессы находятся в очереди и ждут запуска на выполнение;
e) Сокращение времени отклика – минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя
В независимости от цели планирования желательно, чтобы процессы обладали следующими свойствами:
1) Были предсказуемы, т.е. одно и то же задание должно выполняться примерно за одинаковое время;
2) Алгоритм должен иметь минимальные накладные расходы, т.е. время, затрачиваемое на организацию алгоритма планирования не д/б большим;
3) Равномерно должны загружаться ресурсы ВС, т.е. если есть большое количество задач, то надо подбирать их таким образом, чтобы в ВС находились задачи с разным требованием к ресурсам;
4) Обладать масштабируемостью, т.е. алгоритмы не должны терять работоспособность при увеличении загрузки системы
Параметры планирования
Для того, чтобы алгоритмы планирования могли работать они должны опираться на какие-то параметры или какие-то характеристики процесса.
Все параметры можно разбить на:
· Статические – такие, которые не меняются по ходу работы ОС (максимальные значения ресурса, количество переферийных устройств, объемы буферов). Они бывают заранее известны еще до моменты загрузки задачи в ВС:
o Какой пользователь запустил процесс
o Приоритет процесса
o Сколько процессорного времени запросил пользователь
o Каково соотношение процессорного времени и времени, затрачиваемого процессором на ввод/вывод
o Какое количество ресурсов
· Динамические – такие, которые могут меняться.
Алгоритмы долгосрочного планирования используют оба вида параметров. Алгоритмы кратко- и среднесрочного планирования учитывают динамические характеристики:
· Сколько времени прошло с моменты выгрузки процесса на диск или загрузки в оперативную память
· Сколько оперативной памяти занимает процесс
· Сколько процессорного времени было уже предоставлено процессу
Вытесняющие и невытесняющие планирования
Планировщик принимает решения о выборе на исполнение нового процесса из числа находящихся в состоянии готовности в следующих случаях:
1. Если процесс переводится из состояния «исполнение» в состояние «закончил исполнение»
2. Если процесс переводится из состояния «исполнение» в состояние «ожидание»
3. Если процесс переводится из состояния «исполнение» в состояние «готовность»
4. Если процесс переводится из состояния «ожидание» в состояние «готовность»
В 1 и 2 случаях процесс просто не может выполняться дальше, поэтому для продолжения работы необходимо выбрать новый процесс. В 3 и 4 случаях планирование может не проводиться, а работу может продолжить тот же процесс, после обработки прерывания. Говорят, что имеет место невытесняющее планирование, если реализуется 1 и 2 случаи. В 3 и 4 случаях действует вытесняющее планирование.
Наиболее часто вытесняющее планирование используется в системах разделения времени. ОС устанавливает специальный таймер для генерации прерывания по истечении некоторого промежутка времени – кванта, когда квант времени, выделенный процессу, заканчивается, планировщик передает процессор следующему заданию. Правильно выбранный квант позволяет использовать ВС наиболее целесообразным образом.
Алгоритмы планирования
First Come First Served
Первый пришедший первый и обслуживается. Все процессы в ОС находятся в очереди. Когда процесс переходит в состояние «готовность», ссылка на его Process Control Block помещается в конец очереди. Из названия алгоритма ясно, что процесс подлежащий выполнению берется из начала очереди путем удаления PCB из начала очереди.
Этот алгоритм реализует то, что мы называем невытесняющим планированием, причем он захватывает процессор и находится в ВС до конца времени использования процессора. Преимущество алгоритма в том, что его легко реализовать. Наиболее существенный недостаток – среднее время ожидания и среднее полное время выполнения этого алгоритма зависят от порядка алгоритмов в очереди.
Round Robin
Это алгоритм FCFS, реализованный в режиме вытесняющего планирования
| CPU |
При RR планировщики выбирают процесс из начала очереди и устанавливают таймер для подсчета кванта времени. Два варианта:
1. Время непрерывного использования процессора меньше или равно продолжительности два. Тогда оказывается, что процесс сам оставляет процессор и отдает его ОС
2. Продолжительность остатка больше кванта времени, тогда процесс, после отсчета кванта, принудительно прерывается и помещается в конец очереди готовых процессов
Если кванты времени очень большие, тогда алгоритм вырождается в FCFS. При работе системы с квантами можно считать, что есть n виртуальных машин (n – кол-во пользователей) с мощностью N/n.
3.5.3 Shortest Job – First
Для алгоритма FCSF и RR весьма существенным является порядок расположения процессов в очереди. Рассмотрим пример, в котором будем полагать, что вся деятельность процессов ограничивается использованием одного непрерывного промежутка времени использования процессора и что времени перехода с одного процесса на другой очень маленькое; будем полагать, что времена процессов в неких условных единицах и сведено все в таблицу.
| Процесс | Р0 | Р1 | Р2 | Р3 |
| Продолжительность CPU Burst |
Очевидно, что первым на исполнение должен быть поставлен процесс Р3, затем Р1, Р0 и Р2. И время ожидания будет: (0+5+8+15)/4 = 7
| Время | |||||||||||||||||
| Р0 | Г | Г | Г | Г | И | И | И | И | И | ||||||||
| Р1 | Г | И | И | И | |||||||||||||
| Р2 | Г | Г | Г | Г | Г | Г | Г | Г | Г | И | И | И | И | И | И | И | И |
| Р3 | И |
Время ожидания: (0+1+4+9)/4 = 3,5
Можно математически показать, что для заданного набора процессов, если в очереди не появляются новые процессы, алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса всех невытесняющих алгоритмов.
Гарантированное планирование
Пусть работает n-пользователей с данной ОС. Реализовано, чтобы каждый имел 1/n часть процессорного времени. Для каждого пользователя введем величины:
a) Тi – время нахождения пользователя в системе
b) τi – суммарное процессорное время уже выделенное всем процесса пользователя в течение сеанса
c) τi/Тi – пользовательское время
d) αi – коэффициент справедливости, равный τi/(τi/N)
Пусть очередной квант времени будет представляться процессору с наименьшим αi, если это так, то такой алгоритм планирования называется алгоритмом гарантированного планирования.
Приоритетное планирование
Алгоритмы SJF и гарантированного планирования – это частые случаи приоритетного планирования. При таком планирования пользователю присваивается приоритет, опираясь на который планировщик предоставляет процессор процессу с наивысшим приоритетом (0). Если приоритет одинаков, то алгоритм – FCFS.
Принципы назначения приоритетов опираются и на внутренние критерии ВС и на внешние. Внутренние критерии: ограничения по времени использования процессора, требования к памяти, число устройств ввода/вывода и т.д. Внешние критерии: важность процесса. Приоритетное планирование м/б и вытесняющим и невытесняющим.
Чаще всего наиболее просто реализуются алгоритмы со статическими приоритетами. Наиболее гибкие алгоритмы с динамическими приоритетами.
Главная проблема приоритетного планирования в том, что при некорректной реализации низкоприоритетные процессы могут вообще не запускаться. Решение этой проблемы возможно следующим образом – время от времени увеличивать приоритет процессов, находящихся в состоянии «готовность», а когда процесс побывал в состоянии «исполнение» ему восстанавливается первоначальный приоритет.