Стальнов А.Ф., Фомин А.И. Операционные системы. Учебное пособие

Подождите немного. Документ загружается.

2.3. Дисциплины распределения ресурсов,

используемые в операционных системах

Сама идея мультипрограммирования непосредственно связана с нали-

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

граммной ЭВМ по очереди предоставляется процессам. Подобные очере-

ди неизбежно имеют место при обращении к каналам, к широко исполь-

зуемым внешним устройствам (например, к устройствам печати), наборам

данных

, модулям операционной системы.

Использование многими процессами того или иного ресурса, который в

каждый момент времени может обслуживать лишь один процесс, осуще-

ствляется с помощью дисциплин распределения ресурса. Их основой яв-

ляются:

1) дисциплины формирования очередей на ресурсы или совокупность

правил, определяющих размещение процессов в очереди;

2) дисциплины обслуживания очереди или совокупность

правил извле-

чения одного из процессов очереди с последующим представлением вы-

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

Основным конструктивным, согласующим элементом при реализации

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

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

Определяющее влияние на сущность (содержание) дисциплины фор-

мирования очередей оказывают:

1) информация о

классах и приоритетах заданий и шагов заданий, ин-

формация о необходимости обращения к тем или иным устройствам, мас-

сивам данных, зафиксированных в операторах языка управления задания-

ми;

2) соглашения о приоритете уровней запросов прерывания и пре-

рывающих программ, принимаемых при проектировании, разработке

ЭВМ;

3) наборы соглашений, принимаемых в вычислительном центре;

4) используемая

дисциплина обслуживания очередей, которая зачастую

определяет и дисциплину формирования очереди.

Дисциплины формирования очередей разделяются на два класса:

статический, где приоритеты назначаются до выполнения пакета зада-

ний; большинство рассмотренных фактов определяет содержание статиче-

ских дисциплин;

динамический, при котором приоритеты определяются в процессе вы-

полнения пакета.

Оба класса широко используются в практике организации

вы-

числительного процесса в ЭВМ.

В ЭВМ не только многопрограммных, но и однопрограммных, одно-

процессорных, многопроцессорных широко используется ряд дисциплин

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

пределения ресурсов часто называют базовыми. Рассмотрим наиболее

часто встречающиеся на практике дисциплины обслуживания.

Дисциплина обслуживания в порядке поступления

(рис. 2.12.а). “Пер-

вый пришел – первый обслуживается”. В литературе эта дисциплина обоз-

начается как FIFO (First in – First out). Все заявки поступают в конец оче-

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

Самая простая и широко используемая на практике.

Очередь

Очередь Ресурс

Новый запрос

Обслуживание

запроса

Новый

запрос

Обслуженный

запрос

Обслуживание

запроса

Квант

обслуживания

а)

б)

в)

Рис. 2.12. Схемы базовых дисциплин обслуживания процессов:

а – первый пришел – первый обслуживается;

б – последний пришел – первый обслуживается;

в – круговой циклический алгоритм

Дисциплина обслуживания в порядке, обратном порядку поступления

(рис. 2.12.б). “Последний пришел – первый обслуживается”. Обозначается

LIFO (Last in – First out). Так же, как и FIFO, проста в реализации и широ-

ко используется на практике. Данная дисциплина является основой по-

строения стековой памяти.

Общим для названных дисциплин является простота их реализации и

определенная “справедливость” в обслуживании всего потока запросов,

поступающих в систему. Среднее время

ожидания запросов в очереди при

некотором установившемся темпе обслуживания и темпе поступления яв-

ляется одинаковым независимо от характеристик процессов-

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

тельное использование ресурсов (отрабатываются “длинные” запросы), а

другие, наоборот, – непродолжительное (отрабатываются “короткие” за-

просы), то и “длинные” и “короткие” запросы будут ожидать в очереди в

среднем одинаково. Дисциплина FIFO помимо функционального отличия

обеспечивает минимизацию дисперсии времени ожидания.

Круговой циклический алгоритм

(рис. 2.12.в). В основе данной дисцип-

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

ограничено и определяется так называемым квантом времени t

. Если за-

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

за время t

(например, программа процесса за время t

полностью выпол-

нена на процессоре), то он покидает очередь. Если этот запрос не успевает

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

конец очереди. Дисциплина широко используется на практике, в частно-

сти при реализации режима разделения времени.

Хотя в данной дисциплине нет явных приоритетов, здесь в наиболее

благоприятных условиях оказываются короткие запросы, т. е. запросы от

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

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

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

ствования коротким запросам тем больше, чем меньше длительность кван-

та мультиплексирования, чем ближе она к длительности интервала

номи-

нального использования ресурса процессом. Однако уменьшение длитель-

ности кванта ведет к увеличению накладных расходов, необходимых для

отработки прерываний и перераспределения ресурса. Это происходит из-

за возрастания частоты прерываний, что особенно неблагоприятно может

сказаться на отработке “длинных” запросов. Поэтому на практике исполь-

зуют различные модификации данного алгоритма.

Все рассмотренные дисциплины

являются одноочередными. В опера-

ционных системах ЭВМ широко используются многоочередные дисципли-

ны (рис. 2.13). Здесь организуется N очередей. Все новые запросы по-

ступают в конец первой очереди. Первый запрос из очереди i (l ≤ i ≤ N)

поступает на обслуживание лишь тогда, когда все очереди от 1 до (i – 1)-й

пустые. На обслуживание выделяется

квант времени t

. Если за это время

обслуживание запроса завершается полностью, то он покидает систему. В

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

номером i + 1.

После обслуживания из очереди i система выбирает для обслуживания

запрос из непустой очереди с самым младшим номером. Таким запросом

может быть следующий запрос из очереди i

или из очереди i +1 (при усло-

вии, что после обслуживания запроса из очереди i последняя оказалась

пустой). Новый запрос поступает в первую очередь (i = l). В такой ситуа-

ции после окончания времени t

, выделенного для обслуживания запроса

из очереди i, будет начато обслуживание запроса 1-й очереди.

Если система выходит на обслуживание заявок из очереди N, то они

обслуживаются либо по дисциплине FIFO (каждая заявка обслуживается

до конца), либо по круговому циклическому алгоритму.

Очередь 1

Ресурс

Новый

запрос

Обслуженный

запрос

Квант

обслуживания (t

)

Очередь 2

Очередь iОчередь i

Очередь N-1

Очередь N

Обслуживание не закончено

(в конец очереди i + 1)

Рис. 2.13. Схема многоочередной дисциплины обслуживания

Данная система наиболее быстро обслуживает все короткие по времени

обслуживания запросы. Недостаток системы заключается в непроизводи-

тельных затратах времени на перемещение запросов из одной очереди в

другую.

Все рассмотренные дисциплины обеспечивают не только обслуживание

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

отсутствие приоритетности запросов при их поступлении в систему. Но

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

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

Существуют многоочередные дисциплины, в которые поступают за-

просы, имеющие определенный приоритет на обслуживание тем или иным

ресурсом (рис. 2.14). Основу этой дисциплины представляет ранее рас-

смотренная

многоочередная дисциплина. Поступающие в систему новые

запросы попадают в очередь в соответствии с имеющимися приоритетами.

В многоочередных дисциплинах возможны различные стратегии пове-

дения системы по отношению к новым запросам, поступающим в систему.

Эти стратегии определяются дисциплинами обслуживания запросов с аб-

солютными и относительными приоритетами.

Обслуживание с абсолютным приоритетом

. В многоочередной дис-

циплине, где вновь поступающий запрос имеет определенный приоритет,

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

Очередь 1

Ресурс

Новый

запрос

Обслужен-

ный запрос

Квант

обслуживания (t

)

Очередь 2

Очередь iОчередь i

Очередь N-1

Очередь N

Обслуживание не закончено

(в конец очереди i + 1)

Поместить в

очередь i

Ni ≤≤1

Рис. 2.14. Схема приоритетной многоочередной

дисциплины обслуживания

Здесь приоритет определяется очередью (ее номером), и первыми об-

служиваются запросы, обладающие наивысшим приоритетом (из очереди

с меньшим номером). Допустим, система обслуживает запрос из очереди с

номером i, где l < i ≤ N и в систему поступает более приоритетный запрос

в очередь, например, с номером

i-1. В таких условиях обслуживание i-ro

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

После окончания его обслуживания происходит дообслуживание прерван-

ного запроса i-го уровня.

В данной дисциплине еще более увеличивается степень дискриминации

по среднему времени ожидания в очереди между высоко- и низкоприори-

тетными запросами. Время ожидания высокоприоритетных

заявок сокра-

щается, но снова за счет большего ухудшения в обслуживании низкопри-

оритетных заявок.

Цена за увеличение степени дискриминации – усложнение логики сис-

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

прерывания. Во-первых, появляются накладные расходы, необходимые

для отработки прерывание процесса выполнения и перераспределения ре-

сурса. Эти расходы при

достаточной интенсивности прерываний могут

стать весьма ощутимыми. Во-вторых, необходимо выбрать наиболее пра-

вомочное правило о дооб-служивании прерываемых процессов – когда

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

вался до прерывания, и т. д.

Обслуживание с относительным приоритетом

. При данной дис-

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

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

ном случае только после окончания обслуживания менее приоритетной

заявки начнется обслуживание более приоритетной.

Все изложенное касается дисциплины распределения ресурсов без уче-

та взаимосвязи процессов. Процессы, как правило, используют различные

ресурсы и этот факт оказывает влияние на рассмотренные дисциплины

распределения. На практике

должна быть построена стратегия распреде-

ления, удовлетворительная не только в отношении некоторого конкретно-

го ресурса, но и согласованная со стратегиями распределения других ре-

сурсов.

Реализация дисциплин распределения на практике также усложнится

из-за необходимости анализа возможности возникновения тупиковых си-

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

сом распределяемого ресурса.

Наряду с рассмотренными дисциплинами распределения ресурсов су-

ществуют и другие, содержание которых определяется спецификой рас-

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

при статическом и динамическом распределении между процессами опе-

ративной памяти.

3. Принципы построения интерфейсов операционных систем

ОС всегда выступает как интерфейс между аппаратурой компьютера и

пользователем с

его задачами. Под интерфейсами операционных систем

здесь и далее следует понимать специальные интерфейсы системного и

прикладного программирования, предназначенные для выполнения сле-

дующих задач:

1. Управление процессами, которое включает в себя следующий набор

основных функций:

запуск, приостанов и снятие задачи с выполнения;

задание или изменение приоритета задачи;

взаимодействие задач между собой (механизмы

сигналов, семафорные

примитивы, очереди, конвейеры, почтовые ящики);

RPC (remote procedure call) – удаленный вызов подпрограмм.

2. Управление памятью:

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

освобождение памяти;

изменение параметров блока памяти (например, память может быть за-

блокирована процессом либо предоставлена в общий доступ);

отображение файлов на память (имеется не во всех системах).

3. Управление вводом/выводом:

запрос на

управление виртуальными устройствами (напомним, что

управление вводом/выводом является привилегированной функцией са-

мой ОС, и никакая из пользовательских задач не должна иметь возможно-

сти непосредственно управлять устройствами);

файловые операции (запросы к системе управления файлами на созда-

ние, изменение и удаление данных, организованных в файлы).

Здесь перечислены основные наборы функций, которые выполняются

ОС по соответствующим запросам от задач. Что касается пользователь-

ского интерфейса операционной

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

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

соответствующем языке (возможно, с использованием графического ин-

терфейса) и транслируют их в обычные вызовы в соответствии с основ-

ным интерфейсом системы. Обычно эти модули называют интерпретато-

ром команд. Получив от пользователя команду, такой модуль после лек-

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

что случается чаще, обращается к другим модулям ОС, используя меха-

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

получили графические интерфейсы (GUI), в которых задействованы соот-

ветствующие манипуляторы типа “мышь” или “трекбол”. Указание курсо-

ром на объекты и щелчок (клик) или двойной

щелчок по соответствую-

щим клавишам приводит к каким-либо действиям – запуску программы,

ассоциированной с указываемым объектом, выбору и/или активизации

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

транслирует “команды” пользователя в обращения к ОС.

3.1. Интерфейс прикладного программирования

3.1.1. Понятие интерфейса прикладного программирования

Прежде всего

необходимо однозначно разделить общий термин API

(application programming interface, интерфейс прикладного программиро-

вания) на следующие направления:

1) API как интерфейс высокого уровня, принадлежащий к библиотекам

RTL;

2) API прикладных и системных программ, входящих в поставку опе-

рационной системы;

3) прочие API.

Интерфейс прикладного программирования, как это и следует из на-

звания, предназначен для использования прикладными программами сис-

темных ресурсов

ОС и реализуемых ею функций. API описывает совокуп-

ность функций и процедур, принадлежащих ядру или надстройкам ОС.

Итак, API представляет собой набор функций, предоставляемых систе-

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

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

программы с целевой вычислительной системой. Целевая вычислительная

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

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

Сама результирующая программа порождается системой программирова-

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

также объектных модулей и библиотек, входящих в состав системы про-

граммирования.

В принципе API используется не

только прикладными, но и многими

системными программами как в составе ОС, так и в составе системы про-

граммирования.

Но дальше речь пойдет только о функциях API с точки зрения разра-

ботчика прикладной программы. Для системной программы существуют

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

Функции API позволяют разработчику строить результирующую при-

кладную программу

так, чтобы использовать средства целевой вычисли-

тельной системы для выполнения типовых операций. При этом разработ-

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

выполнения этих операций.

Программный интерфейс API включает в себя не только сами функции,

но и соглашения об их использовании, которые регламентируются опера-

ционной системой (ОС), архитектурой целевой вычислительной

системы и

системой программирования.

Существует несколько вариантов реализации API:

1) реализация на уровне ОС;

2) реализация на уровне системы программирования;

3) реализация на уровне внешней библиотеки процедур и функций.

Система программирования в каждом из этих вариантов предоставляет

разработчику средства для подключения функций API к исходному коду

программы и организации их вызовов. Объектный код функций

API под-

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

мости.

Возможности API можно оценивать со следующих позиций:

1) эффективность выполнения функций API – включает в себя скорость

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

их выполнения;

2) широта предоставляемых возможностей;

3) зависимость прикладной программы от архитектуры целевой вычис-

лительной системы.

В идеале хотелось бы иметь

набор функций API, выполняющихся с

наивысшей эффективностью, предоставляющих пользователю все воз-

можности современных ОС и имеющих минимальную зависимость от ар-

хитектуры вычислительной системы (еще лучше – лишенных такой зави-

симости).

Добиться наивысшей эффективности выполнения функций API прак-

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

наивысшей эффективности выполнения для любой результирующей про-

граммы. Поэтому об эффективности API можно говорить только в сравне-

нии его характеристик с другим API.

Что касается двух других показателей, то в принципе нет никаких тех-

нических ограничений на

их реализацию.

3.1.2. Реализация функций API на уровне ОС

При реализации функций API на уровне ОС за их выполнение ответст-

венность несет ОС. Объектный код, выполняющий функции, либо непо-

средственно входит в состав ОС (или даже ядра ОС), либо поставляется в

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

ОС. Система программирования ответственна

только за то, чтобы органи-

зовать интерфейс для вызова этого кода.

В таком варианте результирующая программа обращается непосредст-

венно к ОС. Поэтому достигается наибольшая эффективность выполнения

функций API по сравнению со всеми другими вариантами реализации API.

Недостатком организации API по такой схеме является практически

полное отсутствие переносимости не только кода результирующей про-

граммы,

но и кода исходной программы. Программа, созданная для одной

архитектуры вычислительной системы, не сможет исполняться на вычис-

лительной системе другой архитектуры даже после того, как ее объектный

код будет полностью перестроен. Чаше всего система программирования

не сможет выполнить перестроение исходного кода для новой архитекту-

ры вычислительной системы, поскольку многие функции API, ориентиро

ванные на определенную ОС, будут в новой архитектуре просто отсутст-

вовать.

Таким образом, в данной схеме для переноса прикладной программы с

одной целевой вычислительной системы на другую будет требоваться из-

менение исходного кода программы.

Переносимости можно было бы добиться, если унифицировать функ-

ции API в различных ОС. С учетом корпоративных интересов

производи-

телей ОС такое направление их развития представляется практически не-

возможным. В лучшем случае при приложении определенных организа-

ционных усилий удается добиться стандартизации смыслового (семанти-

ческого) наполнения основных функций API, но не их программного ин-

терфейса.

Хорошо известным примером API такого рода может служить набор

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

Windows – WinAPI (Windows API).

3.1.3. Реализация функций API на уровне системы программирования

Если функции API реализуются на уровне системы программирования,

они предоставляются пользователю в виде библиотеки функций соответ-

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

времени исполнения – RTL (run time library). Система программирования

предоставляет пользователю библиотеку соответствующего языка про-

граммирования и обеспечивает подключение к результирующей програм-

ме объектного кода, ответственного

за выполнение этих функций.

Очевидно, что эффективность функций API в таком варианте будет не-

сколько ниже, чем при непосредственном обращении к функциям ОС. Так

происходит, поскольку для выполнения многих функций API библиотека

RTL языка программирования должна все равно выполнять обращения к

функциям ОС. Наличие всех необходимых вызовов и обращений к функ-

циям ОС

в объектном коде RTL обеспечивает система программирования.

Однако переносимость исходного кода программы в таком варианте

будет самой высокой, поскольку синтаксис и семантика всех функций бу-

дут строго регламентированы в стандарте соответствующего языка про-

граммирования. Они зависят от языка и не зависят от архитектуры целе-

вой вычислительной системы. Поэтому для выполнения прикладной про

граммы на новой архитектуре вычислительной системы достаточно заново

построить код результирующей программы с помощью соответствующей

системы программирования.

Единообразное выполнение функций языка обеспечивается системой

программирования. При ориентации на различные архитектуры целевой

вычислительной системы в системе программирования могут потребо-

ваться различные комбинации вызовов функций ОС для выполнения од-

них и тех же

функций исходного языка. Это должно быть учтено в коде

RTL. В общем случае для каждой архитектуры целевой вычислительной

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

того или иного объектного кода RTL для подключения к результирующей

программе система программирования обеспечивает автоматически.

Например, рассмотрим функции динамического выделения памяти в

языках С и Pascal. В

С это функции malloc, realloc и free (в C++ –

new и delete), в Pascal – функции new и dispose. Если использовать

эти функции в исходном тексте программы, то с точки зрения исходной

программы они будут действовать одинаковым образом в зависимости

только от семантики исходного кода. При этом для разработчика исходной

программы не имеет значения

, на какую архитектуру ориентирована его

программа. Это имеет значение для системы программирования, которая

для каждой из этих функций должна подключить к результирующей про-

грамме объектный код библиотеки. Этот код будет выполнять обращение

к соответствующим функциям ОС. Не исключено даже, что для од-

нотипных по смыслу функций в разных языках (например,

malloc в С и