9

Лекция 9. Загальне поняття процесів. Стан процесів та операції над ними. Алгоритми планування процесів та потоків.

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

1. Понятие процесса

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

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

Задание - некоторая пользовательская или системная программа, которая будет запущена на компьютере. После запуска во время своего исполнения задание станет процессом.

2. Состояния процесса

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

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

• заканчивает работу;

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

• в результате возникновения прерывания процесс возвращается в состояние готовность.

Диаграмма состояний процесса приведена на рис 1.

Рис. 1. Диаграмма состояний процесса

При завершении своей деятельности процесс из состояния исполнение попадает в состояние Завершения. В конкретных операционных системах состояния процесса могут быть еще более детализированы, могут появиться некоторые новые варианты переходов из состояния в состояние. Гак. например, модель состояний процессов для операционной системы Windows NT содержит 7 различных состояний, а для операционной системы UNIX — 9. Тем не менее, в принципе, все операционные системы подчиняются изложенной выше модели.

3. Планирование процессов

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

3.1. Критерии планирования и требования к алгоритмам

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

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

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

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

Эффективность: загрузить процессор на все 100% рабочего времени, не допуская простоев. В реальных системах загрузка процессора колеблется от 40 до 90 процентов. Сокращение полного времени выполнения (turnaround time): обеспечить минимальное время между стартом процесса или постановкой очередь и его завершением. Сокращение времени ожидания (waiting time): минимизировать время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки. s Сокращение времени отклика (response time): минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

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

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

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

та же задача будет выполняться разное время.

Минимальное время работы. Время на определение того какой процесс будет

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

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

которые будут занимать малоиспользуемые ресурсы.

Масштабируемость. Должны сохранять работоспособность при увеличении нагрузки.

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

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

3.2. Параметры планирования

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

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

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

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

- Каким пользователем запущен процесс или сформировано задание.

- Насколько важной является поставленная задача, т. е. каков приоритет ее выполнения. - Сколько процессорного времени запрошено пользователем для решения задачи.

- Каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода.

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

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

Алгоритмы планирования в зависимости от перечня используемых параметров могут быть разбиты на такие группы:

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

- Алгоритмы среднесрочного планирования в качестве таких характеристик может выступать следующая информация:

- Сколько времени прошло со времени выгрузки процесса на диск или его загрузки

в оперативную память.

- Сколько оперативной памяти занимает процесс.

- Сколько процессорного времени было уже предоставлено процессу.

- Алгоритмы краткосрочного планирования в дополнение к характеристикам, учитываемым алгоритмами среднесрочного планирования, учитывают и динамические характеристики процессов. Для краткосрочного планирования необходимо еще два динамических параметра:

1. CPU burst Промежуток времени непрерывного использования процессора

2. I/O burst промежуток времени непрерывного ожидания ввода-вывода.

Значения продолжительности последних и очередных CPU burst и I/O burst являются важными динамическими параметрами процесса.

3.3. Алгоритмы планирования

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

1. First-Come, First-Served (FCFS)

2. Round Robin (RR)

3. Shortest-Job-First (SJF)

4. Гарантированное планирование

5. Приоритетное планирование

6. Многоуровневые очереди (Multilevel Queue)

7. Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

3.3.1. First-Come, First-Served (FCFS)

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия — First Come. First Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, организованы в очередь. Когда процесс переходит в состояние готовность, то ссылка на процесс помещается в конец этой очереди.

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

Рассмотрим 3 процесса с разным временем выполнения: Р₀- 13 Врем. Единиц.. Р₁ - 4 и Р₂- 1. В зависимости от последовательности выполнения этих процессов среднее время ожидания и среднее полное время выполнения для процессов будет различно. Возьмем такие последовательности выполнения процессов и вычислим среднее время ожидания и среднее полное время выполнения:

№	Последовательность выполнения процессов	Среднее время ожидания	Среднее полное время выполнения
1	P0, P1, P2	(0+13+17)/3=10	(13+17+18)/3=16
2	Р2, Р1, Р0	(0+1+5)/3=2	(1+5+18)/3=8
3	Р1, Р0, Р2	(0+4+5)/3=3	(4+17+18)/3=13

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