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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

О правило FIFO (first in — first out, что означает: «первый пришедший первым и выбывает»);

О правило LRU (least recently used, что означает «последний из недавно исполь­зованных» или, иначе говоря, «дольше всего неиспользуемый»);

0 правило LFU (least frequently used, что означает: «используемый реже всех ос­ тальных»);

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

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

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

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

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

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

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

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

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

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

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

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

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