Модели многозадачности.

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

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

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

1) Режим переключения задач.

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

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

Это диспетчеризация без перераспределения процессорного времени. При реализации данной модели планировщик встраивался в ОС в этом случае предоставление процессорного времени каждому приложению или задаче осуществлялся по схеме на
Рис. 6.

Рис. 6. Невытесняющая многозадачность.

Не вытесняющая многозадачность реализована в операционной системе Windows 3x и ранних версиях OS/2, и суть заключается в том, что не операционная система, а сами процессы освобождают процессорное время другим процессам.

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

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

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

Например, в ныне уже забытой операционной среде Windows 3.x приложения этой системы разделяли между собой процессорное время именно таким образом. И программисты сами должны были обеспечивать «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая управление ядру системы.

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

3) Вытесняющая многозадачность.

Диспетчеризация с перераспределением процессорного времени между задачами появился в месте с 32 разрядными операционными системами OS/2 и Windows 9x, Windows NT. Её суть заключается в том, что операционная система сама предоставляет запущенным процессом квант времени. Формированием квантов времени занимается системный таймер, который обеспечивает переключение между процессами 20 или 50 раз в секунду (Рис. 7).

Рис. 7. Вытесняющая многозадачность.

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

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

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

Рис. 8. Синхронизация последовательности выполнения потоков.

Рассмотрим выполнение двух задач, которые разделены на потоки (Рис. 8). Если запустить одновременно сразу все потоки от 1 до 7, то это приведёт к не предсказуемым результатам. Поэтому необходимо синхронизировать последовательность выполнения потоков. О приемах синхронизации будет подробнее изложено в главе 4.

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

Уровни планирования

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

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

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

В некоторых вычислительных системах бывает выгодно для повышения их производительности временно удалить какой-либо частично выполнившийся процесс из оперативной памяти на диск, а позже вернуть его обратно для дальнейшего выполнения. Такая процедура в англоязычной литературе получила название swapping, что можно перевести на русский язык как перекачка, хотя в профессиональной литературе оно употребляется без перевода — свопинг. Когда и какой из процессов нужно перекачать на диск и вернуть обратно, решается дополнительным промежуточным уровнем планирования процессов — среднесрочным.

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

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

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

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

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

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

.

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

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

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

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

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

2) Насколько важной является поставленная задача, т. е. каков приоритет ее выполнения.

3) Сколько процессорного времени запрошено пользователем для решения задачи.

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

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

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

1) Сколько времени прошло со времени выгрузки процесса на диск или его загрузки в оперативную память.

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

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

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

Вытесняющее и невытесняющее планирование

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

В случаях 1 и 2 процесс, находившийся в состоянии исполнение, не может дальше исполняться, и для выполнения всегда необходимо выбрать новый процесс. В случаях 3 и 4 планирование может не проводиться, процесс, который исполнялся до прерывания, может продолжать свое выполнение после обработки прерывания. Если планирование осуществляется только в случаях 1 и 2, говорят, что имеет место невытесняющее планирование. В противном случае говорят о вытесняющем планировании. Термин “вытесняющее планирование” возник потому, что исполняющийся процесс помимо своей воли может быть вытеснен из состояния исполнение другим процессом.

Невытесняющее планирование используется, например, в MS Windows 3.1 и ОС Apple Macintosh. При таком режиме планирования процесс занимает столько процессорного времени, сколько ему необходимо. При этом переключение процессов возникает только при желании самого исполняющегося процесса передать управление (для ожидания завершения операции ввода-вывода или по окончании работы). Этот метод планирования относительно просто реализуем и достаточно эффективен, так как позволяет использовать большую часть процессорного времени на работу самих процессов и до минимума сократить затраты на переключение контекста. Однако при невытесняющем планировании возникает проблема возможности полного захвата процессора одним процессом, который вследствие каких-либо причин (например, из-за ошибки в программе) зацикливается и не может передать управление другому процессу. В такой ситуации спасает только перезагрузка всей вычислительной системы.

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

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

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

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

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

Таблица 1.

Преимуществом алгоритма FCFS является легкость его реализации, в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса П₀, П₁ и П₂, для которых известны времена их очередных процессорного времени. Эти времена приведены в таблице 1 в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка процессорного времени (ПВ), что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

Если процессы расположены в очереди процессов готовых к исполнению в порядке П₀, П₁, П₂, то картина их выполнения выглядит так, как показано на рисунке 9а. Первым для выполнения выбирается процесс П₀, который получает процессор на все время своего ПВ, т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс П₁, занимая процессор на 4 единицы времени. И, наконец, возможность работать получает процесс П₂. Время ожидания для процесса П₀ составляет 0 единиц времени, для процесса П₁ — 13 единиц, для процесса П₂ — 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае — (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса П₀ составляет 13 единиц времени, для процесса П₁ — 13 + 4 = 17 единиц, для процесса П₂ — 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

Рис. 9. Работа алгоритма планирования FCFS для процессов из Таблицы 1 в прямом (а) и обратном (б) порядке.

Если те же самые процессы расположены в порядке П₂, П₁, П₀, то картина их выполнения будет соответствовать рисунку 9б. Время ожидания для процесса П₀ равняется 5 единицам времени, для процесса П₁ — 1 единице, для процесса П₂ — 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса П₀ получается равным 18 единицам времени, для процесса П₁ — 5 единицам, для процесса П₂ — 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 6 единиц времени, что почти в 2,7 раза меньше чем при первой расстановке процессов.

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

3.4.2. Round Robin (RR)

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически — процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 - 100 миллисекунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

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

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

Рассмотрим предыдущий пример с порядком процессов П₀, П₁, П₂ и величиной кванта времени равной 4 (Рис. 10а). Первым для исполнения выбирается процесс П₀. Продолжительность его ПВ больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид П₁, П₂, П₀. Следующим начинает выполняться процесс П₁. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов П₂, П₀. Процессор выделяется процессу П₂. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу П₀ — единственному, не закончившему к этому моменту свою работу. Время ожидания для процесса П₀ составляет 5 единиц времени, для процесса П₁ — 4 единицы времени, для процесса П₂ — 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса П₀ составляет 18 единиц времени, для процесса П₁ — 8 единиц, для процесса П₂ — 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6(6) единицам времени.

Рис. 10. Работа алгоритма планирования RR при длительности кванта времени равной 4 мс (а) и 1 мс (б).

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

На производительность алгоритма RR сильно влияет величина кванта времени. Рассмотрим тот же самый пример c порядком процессов П₀, П₁, П₂ для величины кванта времени равной 1 (Рис. 10б). Время ожидания для процесса П₀ составит 5 единиц времени, для процесса П₁ — тоже 5 единиц, для процесса П₂ — 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой ПВ до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на своем собственном виртуальном процессоре с производительностью ~1/n от производительности реального процессора. Правда, это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов. В реальных условиях при слишком малой величине кванта времени и, соответственно, слишком частом переключении контекста, накладные расходы на переключение резко снижают производительность системы.

3.4.3. Shortest-Job-First (SJF)

При рассмотрении алгоритмов FCFS и RR было видно, насколько существенным для них является порядок расположения процессов в очереди процессов готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если знать ПВ для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью ПВ. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название “кратчайшая работа первой” или Shortest Job First (SJF).

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

Рассмотрим пример работы невытесняющего алгоритма SJF. Пусть в состоянии готовность находятся четыре процесса П₀, П₁, П₂ и П₃, для которых известны времена их очередных ПВ. Эти времена приведены в таблице 2. Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка ПВ, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

Таблица 2.

Таблица 3.4.

При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс П₃, имеющий наименьшее значение очередного ПВ (Рис. 11а). После его завершения для исполнения выбирается процесс П₁, затем П₀ и, наконец, П₂.

Как видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать, что для алгоритма FCFS при порядке процессов П₀, П₁, П₂, П₃ эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в 2 раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса всех невытесняющих алгоритмов.

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов П₀, П₁, П₂ и П₃ с различными ПВ и различными моментами их появления в очереди процессов готовых к исполнению (см. таблицу 3).

Таблица 3.

В начальный момент времени в состоянии готовность находятся только два процесса П₀ и П₄. Меньшее ПВ оказывается у процесса П₃, поэтому он и выбирается для исполнения (см. Рис. 11б). По прошествии 2-х единиц времени в систему поступает процесс П₁. Его ПВ меньше, чем остаток ПВ у процесса П₃, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2-х единиц времени процесс П₁ завершается, и для исполнения вновь выбирается процесс П₃. В момент времени t = 6 в очереди процессов готовых к исполнению появляется процесс П₂, но поскольку ему для работы нужно 7 единиц времени, а процессу П₃ осталось трудиться всего 2 единицы времени, то процесс П₃ остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы П₀ и П₂, из которых выбирается процесс П₀. Наконец, последним получит возможность выполняться процесс П₂.

Рис. 11. Реализация невытесняющего (а) и вытесняющего (б) алгоритма SJF.

Основную сложность при реализации алгоритма SJF представляет невозможность точного знания ПВ для исполняющихся процессов. В пакетных системах количество процессорного времени, требующееся заданию для выполнения, указывает пользователь при формировании задания. Мы можем брать эту величину для осуществления долгосрочного SJF планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать получения результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При краткосрочном планировании мы можем делать только прогноз длительности следующего ПВ, исходя из предыстории работы процесса. Пусть t(n) – величина n-го ПВ, T(n + 1)– предсказываемое значение для n + 1-го ПВ, α – некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение

T(n+1) = α t(n) + (1- α)T(n)

T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При α = 0 мы перестаем следить за последним поведением процесса, фактически полагая

T(n) = T(n-1) = T(0)

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

Положив α = 1, мы забываем о предыстории процесса. В этом случае мы полагаем, что время очередного ПВ будет совпадать со временем последнего ПВ:

T(n+1) = t(n)

Обычно выбирают

α = 1/2

для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выбор a удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным ПВ и полученную сумму разделить на 2, например, с помощью ее сдвига на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJF планирования.

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

При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении ~ 1/N часть процессорного времени. Пронумеруем всех пользователей от 1 до N. Для каждого пользователя с номером i введем две величины: T_i - время нахождения пользователя в системе, или, другими словами длительность сеанса его общения с машиной, и t_i - суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение T_i/N процессорного времени. Если

t_i << T_i/N

то i - й пользователь несправедливо обделен процессорным временем. Если же

t_i >> T_i/N

то система явно благоволит к пользователю с номером i. Вычислим для каждого пользовательского процесса значение коэффициента справедливости

t_iN/T_i

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

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

Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение — приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего ПВ. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше приоритет у процесса.

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

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

Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и для вытесняющего алгоритма SJF, только им дополнительно еще присвоены приоритеты (см. таблицу 4). В вычислительных системах не существует определенного соглашения, какое значение приоритета - 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т.е. наиболее приоритетным в нашем примере является процесс p₃, а наименее приоритетным — процесс p₀.

Таблица 4.

Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времени t = 0 выбирается процесс П₃, как обладающий наивысшим приоритетом (Рис. 12). После его завершения в момент времени t = 5 в очереди процессов готовых к исполнению окажутся два процесса П₀ и П₁. Больший приоритет из них у процесса П₁ он и начнет выполняться (см. таблицу 4). Затем в момент времени t = 8 для исполнения будет избран процесс П₂ и лишь потом процесс П₀.

Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования (Рис. 13). Первым, как и в предыдущем случае, исполняться начнет процесс П₃, а по его окончании процесс П₁. Однако в момент времени t = 6 он будет вытеснен процессом П₂ и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше будет исполнен процесс П₀.

Рис. 12. Невытесняющее приоритетное планирование.

Рис. 13. Вытесняющее приоритетное планирование.

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

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут быть не запущены неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетсском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз, по истечении определенного промежутка времени, значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, восстанавливается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.