Материал: 6261

151

6.5 Алгоритм разделения времени

Все стратегии планирования реализуются конкретными алгоритмами планирования.

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

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

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

•переключение контекстов "старого" и "нового" процессов.

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

Среди этого множества алгоритмов рассмотрим подробнее две группы наиболее часто встречающихся алгоритмов:

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

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

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

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

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

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

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

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

Граф состояний процесса, при таком подходе, соответствует классической модели состояний, показанной ранее на рисунке 6.4.

Таким образом, ни один процесс не занимает процессор надолго, поэтому квантование широко используется в системах разделения времени.

Замечание

Традиционно, ОС UNIX и Linux относятся к системам разделения времени. Разработчики ориентировали эти ОС на создание среды пакетной обработки данных и среды интерактивных систем:

•максимальная пропускная способность решения задач в единицу времени;

•минимизация времени на ожидание обслуживания и обработку задачи;

•поддержка постоянной занятости процессора;

•быстрая реакция на запросы;

•выполнение пожеланий пользователя.

Кванты времени, выделяемые процессам, могут быть:

•одинаковыми для всех процессов или различными;

•фиксированной величины для одного процесса или изменяться в разные пери-

152

оды жизни процесса.

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

По разному может быть организована очередь готовых процессов:

•циклически, по правилу "первый пришел - первый обслужился" (FIFO);

•по правилу стека - "последний пришел - первый обслужился" (LIFO).

Другая группа алгоритмов использует понятие "приоритет" процесса.

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

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

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

Приоритет может назначаться:

•директивно администратором системы в зависимости от важности работы или внесенной платы;

•вычисляться самой ОС по определенным правилам;

•оставаться фиксированным на протяжении всей жизни процесса: статические приоритеты;

•изменяться во времени в соответствии с некоторым законом: динамические

приоритеты.

Существует две разновидности приоритетных алгоритмов:

•алгоритмы, использующие относительные приоритеты;

•алгоритмы, использующие абсолютные приоритеты.

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

По разному решается проблема определения момента смены активного процесса:

•в системах с относительными приоритетами активный процесс выполняет-

ся до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ или же произойдет ошибка, или процесс завершится, что показано вариантом a) на рисунке 6.6;

•в системах с абсолютными приоритетами выполнение активного процесса

прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса; в этом случае, прерванный процесс переходит в состояние ГОТОВНОСТЬ, что показано вариантом б) на рисунке 6.6.

Замечание

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

153

Примениельно к алгоритмам, существует два типа процедур планирования:

•вытесняющая многозадачность;

•невытесняющая многозадачность.

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

Рисунок 6.6 — Переходы состояний для относительного и абсолютного приоритетов

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

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

•проблема синхронизации - задача борьбы процессов за один ресурс, рассматриваемая в последующих подразделах, на примере разделяемой памяти;

154

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

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

6.6 Четыре подхода к управлению процессами

Рассмотрев работу ядра ОС на уровне стратегии и алгоритмов планирования мультипрограммного режима функционирования, вернемся к «Главному родительскому процессу», который организует управление всеми процессами, функционирующими в пользовательском режиме.

По традиции, этот процесс назван init, что никоим образом не ограничивает его возможности, а является следствием решения проблемы переключения режимов работы ядра ОС: из активного режима в пассивный.

Более того, создаваясь первым, этот процесс является:

•родительским процессом для всех остальных процессов;

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

•отслеживает завершение всех процессов в режиме пользователя и становит-

ся прямым родителем процессов, родители которых завершили свою работу (процессы зомби);

•завершает работу последним, одновременно завершая работу ядра ОС.

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

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

Вчастности init, с помощью системного вызова exec(...), может вместо себя загрузить любую другую программу, которая будет выполнять роль «Главного родительского процесса».

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

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

Мы рассмотрим наиболее известные четыре подхода: монопольный, System V, upstart и systemd.

Монопольный подход к управлению процессами применяется:

•во встроенных системах, когда вычислительный процесс решает одну или

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

•в узко специализированных системах, требующих централизованного управ-

155 ления всеми вычислительными аспектами приложения;

•в монопольном режиме работы администратора ОС, необходимом для настройки или восстановления работы ОС;

•при загрузке современных ОС, предполагающей промежуточный этап работы

ОС перед загрузкой и монтированием основной файловой системы. Например, ОС Linux, используя универсальный загрузчик GRUB, указывает в файле grub.cfg местоположение ядра ОС (vmlinuz) и файл initrd — сжатой временной файловой системы ОС.

GRUB обеспечивает:

•загрузку и распаковку ядра vmlinuz;

•загрузку файла initrd;

•передачу ядру параметров, указанных в grub.cfg, и координат initrd;

•передачу управления ядру ОС перед завершением работы.

Ядро ОС:

•инициирует внутренние параметры;

•распаковывает в память ЭВМ временную ФС initrd;

•находит в корне временной ФС файл init или linuxrc;

•создает первый процесс init или shell, если init — скрипт.

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

Подход UNIX System V ориентирован на универсальное применение. Фактически он является классическим примером, организующим управление процессами в UNIX и Linux системах, применяемым и до настоящего времени.

UNIX System V — одна из версий ОС UNIX, разработанная компанией AT&T и выпущенная в 1983 году. Всего было выпущено четыре версии. Версия UNIX System V Release 4 (SVR4) была наиболее удачной. Разработчики SVR4 выпустили стандарт — System V Interface Definition (SVID), описывающий работу этой ОС.

Многие разработчики UNIX-подобных систем стали ориентироваться на этот стандарт. В частности, переняли от нее сценарии инициализации системы «SysV init scripts», отвечающие за запуск и выключение ОС. Такие сценарии традиционно находятся в директории /etc/init.d/.

Замечание

К концу 90-х годов, значение SVID снизилось и были выпущены, независимые от производителя ОС, стандарты POSIX и Single UNIX Specification (SUS).

ОС Linux не сертифицирует свои дистрибутивы и использует, основанный на SUS, стандарт Linux Standard Base (LSB).

Основная идея System V — ядро и ОС в целом могут работать на различных уровнях, показанных в таблице 6.1. Для определения, на каком уровне работает ОС, используется утилита runlevel, которая выдает два символа, разделенных пробелом:

•первый символ — уровень, на котором система находилась (значение N показывает, что предыдущий уровень не был установлен);