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

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

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

Таким образом, виртуальный адрес для этого способа будет состоять из двух по­лей — номера сегмента и смещения относительно начала сегмента. Соответствую­щая иллюстрация приведена на рис. 3.4 для случая обращения к ячейке, виртуаль­ный адрес которой равен сегменту с номером 11 со смещением от начала этого сегмента, равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19700.

Итак, каждый сегмент, размещаемый в памяти, имеет соответствующую информа­ционную структуру, часто называемую дескриптором сегмента. Именно операци­онная система строит для каждого исполняемого процесса соответствующую табли-цу дескрипторов сегментов, и при размещении каждого из сегментов в оперативной или внешней памяти отмечает в дескрипторе текущее местоположение сегмента. Если сегмент задачи в данный момент находится в оперативной памяти, то об этом делается пометка в дескрипторе. Как правило, для этого используется бит при­сутствия Р (от слова «present»). В этом случае в поле адреса диспетчер памяти записывает адрес физической памяти, с которого сегмент начинается, а в ноле дли­ны сегмента (limit) указывается количество адресуемых ячеек памяти. Это поле используется не только для того, чтобы размещать сегменты без наложения друг на друга, но и для того, чтобы контролировать, не обращается ли код исполняю­щейся задачи за пределы текущего сегмента. В случае превышения длины сегмен-

88_____________________ Глава 3. Управление памятью в операционных системах

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

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

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

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

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

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

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

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

При поиске свободного места используется одна из вышеперечисленных дисцип­лин работы диспетчера памяти (применяются правила «первого подходящего»

90_____________________ Глава 3. Управление памятью в операционных системах

и «самого неподходящего» фрагментов). Если свободного фрагмента памяти дос­таточного объема нет, но, тем не менее, сумма этих свободных фрагментов превы­шает требования по памяти для нового сегмента, то в принципе может быть при­менено «уплотнение памяти», о котором мы уже говорили в подразделе «Разделы с фиксированными границами» раздела «Распределение памяти статическими и динамическими разделами».

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

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

□ правило FIFO (First In First Out — первый пришедший первым и выбывает);

□ правило LRU (Least Recently Used — дольше других неиспользуемый);

□ правило LFU (Least Frequently Used — реже других используемый);

□ случайный (random) выбор сегмента.

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

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

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

¹ Их называют «дисциплинами замещения».

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

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

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

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

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

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

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

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

Поэтому следующим способом разрывного размещения задач в памяти стал спо­соб, при котором все фрагменты задачи считаются равными (одинакового разме-

92_____________________ Глава 3. Управление памятью в операционных системах

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

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

OS/2 v.l поддерживала распределение памяти, при котором выделялись сегмен­ты программы и сегменты данных. Система позволяла работать как с именованны­ми, так и с неименованными сегментами. Имена разделяемых сегментов данных имели ту же форму, что и имена файлов. Процессы получали доступ к именован­ным разделяемым сегментам, используя их имена в специальных системных вызо­вах. Операционная система OS/2 v. 1 допускала разделение программных сегмен­тов приложений и подсистем, а также глобальных сегментов данных подсистем. Вообще, вся концепция системы OS/2 была построена на понятии разделения памяти: процессы почти всегда разделяют сегменты с другими процессами. В этом состояло существенное отличие системы OS/2 от систем типа UNIX, которые обычно разделяют только реентерабельные программные модули между процес­сами.

Сегменты, которые активно не использовались, могли выгружаться на жесткий диск. Система восстанавливала их, когда в этом возникала необходимость. Так как все области памяти,'используемые сегментом, должны были быть непрерывными, OS/2 перемещала в основной памяти сегменты таким образом, чтобы максимизи­ровать объем свободной физической памяти. Такое переразмещение сегментов называется уплотнением памяти (компрессией). Программные сегменты не вы­гружались, поскольку они могли просто перезагружаться с исходных дисков. Об­ласти в младших адресах физической памяти, которые использовались для запус­ка DOS-программ и кода самой OS/2, в компрессии не участвовали. Кроме того, система или прикладная программа могла временно фиксировать сегмент в памя­ти с тем, чтобы гарантировать наличие буфера ввода-вывода в физической памяти до тех пор, пока операция ввода-вывода не завершится.

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

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

' OS/2 v.l начала создаваться в 1984 году и поступила в продажу в 1987 году.

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

Было организовано в OS/2 и динамическое присоединение обслуживающих про­грамм. Программы OS/2 используют команды удаленного вызова. Ссылки, гене­рируемые этими вызовами, определяются в момент загрузки самой программы или ее сегментов. Такое отсроченное определение ссылок называется динамическим присоединением. Загрузочный формат модуля OS/2 представляет собой расшире­ние формата загрузочного модуля DOS. Он был расширен, чтобы поддерживать необходимое окружение для свопинга сегментов с динамическим присоединени­ем. Динамическое присоединение уменьшает объем памяти для программ в OS/2, одновременно делая возможными перемещения подсистем и обслуживающих про­грамм без необходимости повторного редактирования адресных ссылок к приклад­ным программам.