Уровень 0. Ресурсы и процессы

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

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

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

В многозадачной системе процесс может находиться в одном из трех основных состояний:

– ВЫПОЛНЕНИЕ (ИСПОЛНЕНИЕ) – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;

– ОЖИДАНИЕ – пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса;

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

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

Уровень 0. Планирование процессов

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

Планирование процессов включает в себя решение следующих задач:

– определение момента времени для смены выполняемого процесса;

– выбор процесса на выполнение из очереди готовых процессов;

– переключение «старого» и «нового» процессов.

Третья задача решается в значительной степени аппаратно, а первые две – программно и представляют собой основной объект алгоритма планирования.

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

1) процесс переводится из состояния ВЫПОЛНЕНИЕ в состояние ЗАВЕРШЕНИЕ;

2) процесс переводится из состояния ВЫПОЛНЕНИЕ в состояние ОЖИДАНИЕ;

3) процесс переводится из состояния ВЫПОЛНЕНИЕ в состояние ГОТОВНОСТЬ;

4) процесс переводится из состояния ОЖИДАНИЕ в состояние ГОТОВНОСТЬ.

В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и для выполнения всегда необходимо выбрать новый процесс. В случаях 3 и 4 планирование можно не проводить, процесс, который исполнялся до прерывания, может продолжать свое выполнение. Если планирование осуществляется только в случаях 1 и 2, говорят, что имеет место невытесняющее планирование. Если планируются все четыре пункта, говорят о вытесняющем планировании. Термин «вытесняющее планирование» возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния ВЫПОЛНЕНИЕ.

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

Вытесняющее планирование обычно используется в системах разделения времени. В этом режиме планирования процесс может быть приостановлен в любой момент своего исполнения и переведен в состояние ГОТОВНОСТЬ. Операционная система устанавливает специальный таймер для генерации сигнала прерывания по истечении некоторого интервала времени – кванта. После прерывания процессор передается в распоряжение следующего процесса. Временные прерывания помогают гарантировать приемлемые времена отклика процессов для пользователей, работающих в диалоговом режиме, и предотвращают «зависание» компьютерной системы из-за зацикливания какой-либо программы.

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

Почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, Windows 2000, Windows XP, Linux), реализована вытесняющая многозадачность. Создание программных приложений для многозадачных ОС называется мультипрограммированием.

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

Уровень 0. Алгоритмы планирования процессов

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

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

– эффективность: по возможности занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании готовых процессов. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90 процентов;

– сокращение полного времени выполнения: обеспечить минимальное время между стартом процесса или постановкой задания в очередь и его завершением;

– сокращение времени ожидания: минимизировать время, которое проводят процессы в состоянии ГОТОВНОСТЬ и задания в очереди;

– сокращение времени отклика: минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.

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

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

– минимум накладных расходов. Если на каждые 100 миллисекунд, выделенных процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, использовать не стоит;

– равномерная загрузка ресурсов вычислительной системы, при этом предпочтение отдается тем процессам, которые занимают малоиспользуемые ресурсы;

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

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

Существует множество различных алгоритмов планирования процессов, по разному решающих вышеперечисленные задачи, преследующих различные цели и обеспечивающих различное качество программирования. Например, это такие алгоритмы как FCFS (First Come, First Served – первым пришел, первым обслужен) – невытесняющий циклический алгоритм, RR (Round Robin) – вытесняющий циклический алгоритм, SJF (Shortest Job First) – первоначально выполняются короткие задачи, алгоритм гарантированного планирования, MQ (Multilevel Queue – многоуровневая очередь) – комбинация FCFS и RR и т.д. В целом алгоритмы можно разделить на три группы:

– алгоритмы, основанные на приоритетах;

– алгоритмы, основанные на квантовании;

– комбинированные алгоритмы.

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

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

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

– процесс завершился и покинул систему;

– произошла ошибка;

– процесс самостоятельно перешел в состояние ОЖИДАНИЕ;

– исчерпан квант процессорного времени, отведенный данному процессу.

Процесс, который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение выбирается новый процесс из очереди готовых. Таким образом, ни один процесс не занимает процессор надолго.

Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов, т.е. комбинированно. Например, в основе планирования лежит квантование, но величина кванта и/или порядок выбора процесса из очереди готовых определяется приоритетом процесса.