Системное программное обеспечение

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

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

первый подходящий участок;

самый подходящий участок;

самый неподходящий участок.

Впервом случае список свободных областей упорядочивается по адресам (напри­ мер, по возрастанию адресов). Диспетчер памяти просматривает этот список и выделяет задаче раздел в той области, которая первая подойдет по объему. В этом случае, если такой фрагмент имеется, то в среднем необходимо просмотреть половину списка. Правило «первый подходящий» приводит к тому, что память для небольших задач преимуществен­ но будет выделяться в области младших адресов и, следовательно, это будет увеличивать вероятность того, что в области старших адресов будут образовываться фрагменты доста­ точно большого объема.

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

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

Как ни странно, самым эффективным правилом является последнее, по которому для нового раздела выделяется самый неподходящий фрагмент свободной памяти. Для этой дисциплины список свободных областей упорядочивается по убыванию объема сво­ бодного фрагмента.

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

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

31

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

7.2.3. Сегментная, страничная и сегментно-страничная организация памяти.

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

В современных компьютерных системах процесс отображения выполняется на аппарат­ ном уровне с помощью устройства управления памятью (MMU – Memory Management Unit), обеспечивая высокую скорость трансляции. ОС осуществляет управление этим про­ цессом.

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

На рис. 7.2 показана взаимосвязь между виртуальным и физическим адресным про­ странством.

Рис. 7.2. Виртуальное и физическое адресное пространство

32

Сегментный способ организации виртуальной памяти

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

Физически имя сегмента (или порядковый номер) будет соответствовать некоторо­ му адресу, с которого этот сегмент начинается при его размещении в памяти, и смещение должно прибавляться к этому базовому адресу.

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

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

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

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

Во-вторых, некоторые программные модули могут быть разделяемыми. Эти про­ граммные модули являются сегментами, и в этом случае относительно легко организовать доступ к таким сегментам. Сегмент с разделяемым кодом располагается в памяти в

33

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

Недостатком данного метода распределения памяти является фрагментация на уровне сегментов и более медленное по сравнению со страничной организацией преоб­ разование адреса.

Страничное распределение

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

Вся оперативная память машины также делится на части такого же размера, назы­ ваемые физическими страницами (или блоками).

Размер страницы обычно выбирается равным степени двойки: 512, 1024 и т.д., это позволяет упростить механизм преобразования адресов.

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

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

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

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

 дольше всего не использовавшаяся страница,

34

первая попавшаяся страница,

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

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

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

Странично-сегментное распределение

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

7.2.4. Свопинг

Разновидностью виртуальной памяти является свопинг.

Для загрузки процессора на 90% достаточно всего трех счетных задач. Однако для того, чтобы обеспечить такую же загрузку интерактивными задачами, выполняющими ин­ тенсивный ввод-вывод, потребуются десятки таких задач. Необходимым условием для вы­ полнения задачи является загрузка ее в оперативную память, объем которой ограничен. В этих условиях был предложен метод организации вычислительного процесса, называемый свопингом. В соответствии с этим методом некоторые процессы (обычно находящиеся в состоянии ожидания) временно выгружаются на диск. Планировщик операционной систе­ мы не исключает их из своего рассмотрения, и при наступлении условий активизации не­ которого процесса, находящегося в области свопинга на диске, этот процесс перемещается в оперативную память. Если свободного места в оперативной памяти не хватает, то выгру­ жается другой процесс.

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

35

8. ПОДСИСТЕМА УПРАВЛЕНИЯ ВВОДОМ-ВЫВОДОМ

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

8.1. Физическая организация устройств ввода-вывода

Устройства ввода-вывода условно можно разделить на два типа: блок-ориентиро­ ванные устройства и байт-ориентированные устройства. Блок-ориентированные устрой­ ства хранят информацию в блоках фиксированного размера, каждый из которых имеет свой собственный адрес. Самое распространенное блок-ориентированное устройство – диск. Байт-ориентированные устройства не адресуемы и не позволяют производить опера­ цию поиска, они генерируют или потребляют последовательность байтов. Примерами та­ ких устройств являются терминалы, строчные принтеры, сетевые адаптеры.

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

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

ОС выполняет ввод-вывод, записывая команды в регистры контроллера. Например, контроллер гибкого диска IBM PC принимает 15 команд, таких как READ, WRITE, SEEK, FORMAT и т.д. Когда команда принята, процессор оставляет контроллер и занимается другой работой. При завершении команды контроллер организует прерывание для того, чтобы передать управление процессом ввода-вывода операционной системе, которая должна проверить результаты операции. При этом процессор получает результаты опера­ ции и статус устройства ввода-вывода, читая информацию из регистров контроллера.

8.2. Организация программного обеспечения ввода-вывода

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

Программное обеспечение ввода-вывода целесообразно разделить на четыре слоя (рис. 8.1):

36

Обработка прерываний,

Драйверы устройств,

Независимый от устройств слой операционной системы,

Пользовательский слой программного обеспечения.

Рис. 8.1. Многоуровневая организация подсистемы ввода-вывода

Обработка прерываний

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

Драйверы устройств

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

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

37

секторами, цилиндрами, временем установления головки и другими факторами, обеспечи­ вающими правильную работу диска.

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

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

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

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

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

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

обеспечение общего интерфейса к драйверам устройств,

именование устройств,

защита устройств,

обеспечение независимого размера блока данных,

буферизация,

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

распределение и освобождение выделенных устройств,

уведомление об ошибках.

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

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

38

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

Другой категорией программного обеспечения ввода-вывода является подсистема спулинга (spooling). Спулинг – это способ работы с выделенными устройствами в мульти­ программной системе. Рассмотрим типичное устройство, требующее спулинга – строчный принтер. Хотя технически легко позволить каждому пользовательскому процессу открыть специальный файл, связанный с принтером, такой способ опасен из-за того, что пользова­ тельский процесс может монополизировать принтер на произвольное время. Вместо этого создается специальный процесс – монитор, который получает исключительные права на использование этого устройства. Также создается специальный каталог, называемый ката­ логом спулинга. Для того, чтобы напечатать файл, пользовательский процесс помещает выводимую информацию в этот файл и помещает его в каталог спулинга. Процесс-мони­ тор по очереди распечатывает все файлы, содержащиеся в каталоге спулинга.

8.3. Синхронный и асинхронный ввод/вывод

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

Поэтому любые операции по управлению вводом/выводом объявляются привилеги­ рованными и могут выполняться только кодом самой ОС. Для обеспечения этого принци­ па в большинстве процессоров даже вводятся режимы пользователя и супервизора. Как правило, в режиме супервизора выполнение команд ввода/вывода разрешено, а в пользо­ вательском режиме – запрещено. Использование команд ввода/вывода в пользовательском режиме вызывает прерывание и управление через механизм прерываний передается коду ОС.

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

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

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

39

ся специальный системный процесс по указанию супервизора ввода/вывода. Итак, для рассмотренного случая вывод будет асинхронным, если, во-первых, в запросе на ввод/вы­ вод было указано на необходимость буферирования данных, а во-вторых, если устройство ввода/вывода допускает такие асинхронные операции.

Можно организовать и асинхронный ввод данных. Однако для этого необходимо не только выделить область памяти для временного хранения считываемых с устройства дан­ ных и связать выделенный буфер с задачей, заказавшей операцию, но и сам запрос на опе­ рацию ввода/вывода разбить на две части (на два запроса). В первом запросе указывается операция на считывание данных подобно тому, как это делается при синхронном вводе/выводе. Однако в запросе указывается еще по крайней мере один дополнительный параметр – имя того системного объекта, которое получает задача в ответ на запрос и ко­ торое идентифицирует выделенный буфер. Получив имя буфера, задача продолжает свою работу. Здесь очень важно подчеркнуть, что в результате запроса на асинхронный ввод данных задача не переводится в состояние ожидания завершения операции ввода/вывода, а остается в состоянии выполнения или в состоянии готовности к выполнению. Через не­ которое время, выполнив код, который был определен программистом, задача выдает вто­ рой запрос на завершение операции ввода/вывода. В этом втором запросе к тому же устройству задача указывает имя буфера для асинхронного ввода данных и в случае успешного завершения операции считывания данных тут же получает их из системного буфера. Если же данные еще не успели до конца переписаться с внешнего устройства в системный буфер, супервизор ввода/вывода переводит задачу в состояние ожидания за­ вершения операции ввода/вывода и далее все напоминает обычный синхронный ввод дан­ ных.

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

Аппаратуру ввода/вывода можно рассматривать как совокупность аппаратурных процессов, которые способны работать параллельно относительно друг друга, а также от­ носительно центрального процессора. На таких «процессорах» выполняются так называе­ мые внешние процессы. Например, для устройства ввода/вывода внешний процесс может представлять собой совокупность операций, обеспечивающих перевод печатающей го­ ловки, продвижение бумаги на одну позицию, смену цвета чернил или печать каких-то символов. Внешние процессы, используя аппаратуру ввода/вывода, взаимодействуют как между собой, так и с обычными программными процессами, выполняющимися на цен­ тральном процессоре. Важным при этом является то обстоятельство, что скорости внеш­ них процессов будут существенно отличаться от скорости выполнения обычных процес­ сов. Для своей нормальной работы внешние и внутренние процессы обязательно должны синхронизироваться. Для сглаживания эффекта сильного несоответствия скоростей между внутренними и внешними процессами используют упомянутое выше буферирование. Та­ ким образом, можно говорить о системе параллельных взаимодействующих процессов (см. разд. 5.6).

40