Программист обращается к памяти с помощью некоторого набора логических имен. Имена переменных и входных точек модулей составляют область имен. Физическая память представляет собой множество ячеек, которые пронумерованы, к каждой ячейке можно обратиться, указав ее порядковый номер (адрес). Количество ячеек физической памяти ограничено и фиксировано. Системное программное обеспечение должно связать каждое указанное пользователем имя с физической ячейкой памяти, т.е. осуществить отображение пространства имен на физическую память компьютера. Это происходит в два этапа (рис. 10.1):
1) посредством системы программирования;
2)
| Виртуальное адресное пространство |
| Виртуальный адрес |
| Физическая память компьютера |
| Ячейка оперативной памяти (физический адрес) |
| Логическое (символьное) имя |
| Пространство имён программы |
| Система программирования |
| Операционная система |
посредством операционной системы (с помощью специальных программных модулей управления памятью и использования соответствующих аппаратных средств вычислительной системы).
Рис. 10.1.
Между этими этапами обращение к памяти имеет форму виртуального или логического адреса. Множество всех допустимых значений виртуального адреса для некоторой программы определяет ее виртуальное адресное пространство или виртуальную память.
Если система программирования генерирует абсолютную двоичную программу, то виртуальные адреса точно соответствуют физическим. Часть программ любой ОС должны быть абсолютными двоичными программами, размещаться по фиксированным физическим адресам и обеспечивать размещение остальных программ на различных физических адресах.
В простейшем случае транслятор-компилятор генерирует относительные адреса, которые являются виртуальными и впоследствии настраиваются на один из непрерывных разделов. Второе отображение осуществляется перемещающим загрузчиком. После загрузки виртуальный адрес теряется, и доступ выполняется непосредственно к физическим адресам.
Термин виртуальная память фактически относится к системам, которые сохраняют виртуальные адреса во время исполнения. Второе отображение осуществляется в процессе выполнения задачи, поэтому адреса физических ячеек могут изменяться.
Простое непрерывное распределение – это самая простая схема, согласно которой вся память условно может быть разделена на три части:
Ø область, занимаемая операционной системой;
Ø область, в которой размещается исполняемая задача;
Ø незанятая ничем (свободная) область памяти.
Эта схема предполагает, что ОС не поддерживает мультипрограммирования, поэтому не возникает проблемы распределения памяти между несколькими задачами. Чтобы предоставить задачам максимальный объем памяти, ОС строится таким образом, чтобы постоянно в памяти располагалась только самая нужная ее часть – ядро ОС, остальные модули загружаются при необходимости.
Эта схема влечет два вида потерь:
Ø потери процессорного времени из-за простоя в связи с вводом/выводом;
Ø потери самой оперативной памяти, так как она не всегда используется полностью.
Для организации мультипрограммного режима необходимо обеспечить одновременное расположение в оперативной памяти нескольких задач (целиком или частично). Самая простая схема распределения памяти между несколькими задачами предполагает, что память, незанятая ядром ОС, может быть разбита на несколько непрерывных частей (зон, разделов). Это способ организации памяти носит такое название, как распределение памяти статическими и динамическими разделами. Разделы характеризуются:
Ø именем;
Ø типом;
Ø границами (начало раздела и его длина).
Разбиение памяти на несколько разделов может быть:
Ø фиксированным (статическим);
Ø динамическим (выделение нового раздела памяти происходит непосредственно при появлении новой задачи).
При использовании распределения памяти статическими разделами в каждом разделе в каждый момент времени может располагаться по одной программе (задаче). По этой схеме строились первые мультипрограммные ОС, т.к. она является несложной и обеспечивает возможность параллельного выполнения программ. Основным же недостатком такого способа распределения памяти является наличие порой достаточно большого объёма неиспользуемой памяти, т.е. фрагментация памяти. Чтобы сократить значительные потери памяти, разработчиками были реализованы другие решения распределения памяти, а именно:
Ø выделять раздел ровно такого объёма, который нужен под текущую задачу, т.е. использование распределения памяти с динамическими разделами;
Ø размещать задачу не в одной непрерывной области памяти, а в нескольких областях.
Что касается первого решения, т.е. использования распределения памяти с динамическими разделами, то с помощью специального планировщика (диспетчера памяти) ведется список адресов свободной оперативной памяти. При появлении новой задачи диспетчер памяти просматривает этот список и выделяет для задачи раздел, объём которого либо равен необходимому, либо чуть больше, если память выделяется не ячейками, а некими дискретными единицами. При этом модифицируется список свободной памяти. При освобождении раздела диспетчер памяти пытается объединить освобождающийся раздел с одним из свободных участков, если таковой является смежным. При этом список свободных участков может быть упорядочен либо по адресам, либо по объёму. Выделение памяти под новый раздел может осуществляться одним из трех способов:
Ø первый подходящий участок;
Ø самый подходящий участок;
Ø самый неподходящий участок.
В первом случае список свободных областей упорядочивается по адресам (например, по возрастанию адресов). Диспетчер памяти просматривает этот список и выделяет задаче раздел в той области, которая первой подойдет по объёму. В этом случае, если такой фрагмент имеется, то в среднем необходимо просмотреть половину списка. При освобождении раздела необходимо просмотреть половину списка. Правило «первый подходящий» приводит к тому, что память для небольших задач преимущественно будет выделяться в области младших адресов и, следовательно, это будет увеличивать вероятность того, что в области старших адресов будут образовываться фрагменты достаточно большого объёма.
Способ «самый подходящий» предполагает, что список свободных областей упорядочен по возрастанию объёма этих фрагментов. В этом случае при просмотре списка для нового раздела будет использован фрагмент свободной памяти, объём которой наиболее точно соответствует требуемому. Требуемый раздел будет определяться по-прежнему в результате просмотра в среднем половины списка. Однако оставшийся фрагмент оказывается настолько малым, что в нём уже вряд ли удастся разместить какой-либо ещё раздел и при этом этот фрагмент попадет в самое начало списка. Поэтому в целом такую дисциплину нельзя назвать эффективной.
Как ни странно, самым эффективным правилом является последнее, по которому для нового раздела выделяется «самый неподходящий» фрагмент свободной памяти. Для этой дисциплины список свободных областей упорядочивается по убыванию объёма свободного фрагмента. Очевидно, что если есть такой фрагмент памяти, то он сразу же и будет найден, и поскольку этот фрагмент является самым большим, то, скорее всего, после выделения из него раздела памяти для задачи оставшаяся область памяти ещё сможет быть использована в дальнейшем.
Однако очевидно, что при любой дисциплине обслуживания, по которой работает диспетчер памяти, из-за того, что задачи появляются и завершаются в произвольные моменты времени и при этом они имеют разные объёмы, то в памяти всегда будет наблюдаться сильная фрагментация. При этом возможны ситуации, когда из-за сильной фрагментации памяти диспетчер задач не сможет образовать новый раздел, хотя суммарный объём свободных областей будет больше, чем необходимо для задачи. В этой ситуации возможно организовать так называемое «уплотнение памяти». Для уплотнения памяти все вычисления приостанавливаются, и диспетчер памяти корректирует свои списки, перемещая разделы в начало памяти (или, наоборот, в область старших адресов). При определении физических адресов задачи будут участвовать новые значения базовых регистров, с помощью которых и осуществляется преобразование виртуальных адресов в физические. Недостатком этого решения является потеря времени на уплотнение и, что самое главное, невозможность при этом выполнять сами вычислительные процессы.
Данный способ распределения памяти, тем не менее, применялся достаточно длительное время в нескольких операционных системах, поскольку в нем для задач выделяется непрерывное адресное пространство, а это упрощает создание систем программирования и их работу.
Методы распределения памяти, при которых задаче уже не предоставляется сплошная (непрерывная) область памяти, называются разрывными. Для реализации этого метода нужно иметь соответствующую аппаратную поддержку – относительную адресацию: если указать адрес начала текущего фрагмента программы и величину смещения относительно этого начального адреса, то можно указать необходимую переменную или команду. Виртуальный адрес можно представить состоящим из двух полей:
Ø указатель на часть программы (с которой идет работы) для определения местоположения этой части;
Ø относительный адрес нужной ячейки памяти (по отношению к найденному адресу).
Программист может самостоятельно разбивать программу на фрагменты или возложить эту задачу на систему программирования.
Для сегментного способа организации виртуальной памяти программу нужно разбить на части и уже каждой части выделить физическую память. Каждый программный модуль или их совокупность могут быть восприняты как отдельные сегменты. Каждый сегмент размещается в оперативной памяти как самостоятельная единица. Логически обращение к элементам программы производится как указание имени сегмента и смещения относительно его начала. Физически имя (или порядковый номер) сегмента соответствует некоторому адресу, с которого этот сегмент начинается при его размещении в памяти, и смещение должно прибавляться к этому адресу.
| Регистр таблицы сегментов (таблицы дескрипторов сегментов) |
| 31 500 |
| + |
| Сегмент №11 |
| 19 700 |
| 20 312 |
| Виртуальный адрес |
| S(Segment) D(Destination) |
| Таблица дескрипторов текущей задачи |
| Адрес начала сегмента |
| Длина сегмента |
| Права доступа |
| 19 700 |
| 1 300 |
| R-X |
| + |
Таким образом, виртуальный адрес для этого способа будет состоять из двух полей – номер сегмента и смещение относительно начала сегмента. Соответствующая иллюстрация приведена на рис. 10.2. На этом рисунке изображен случай обращения к ячейке, виртуальный адрес которой равен сегменту с номером 11 и смещением от начала этого сегмента, равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19 700.
Рис. 10.2.
Каждый сегмент, размещаемый в памяти, имеет соответствующую информационную структуру, часто называемую дескриптором сегмента. Именно операционная система строит для каждого исполняемого процесса соответствующую таблицу дескрипторов сегментов и при размещении каждого из сегментов в оперативной или внешней памяти в дескрипторе отмечает его текущее местоположение.
Если сегмент задачи в данный момент находится в оперативной памяти, то об этом делается пометка в дескрипторе. Как правило, для этого используется «бит присутствия» (present). В этом случае в поле «адрес» диспетчер памяти записывает адрес физической памяти, с которого сегмент начинается, а в поле «длина сегмента» (limit) указывается количество адресуемых ячеек памяти. Это поле используется не только для того, чтобы размещать сегменты без наложения один на другой, но и для того, чтобы проконтролировать, не обращается ли код исполняющейся задачи за пределы текущего сегмента. В случае превышения длины сегмента вследствие ошибок программирования мы можем говорить о нарушении адресации и с помощью введения специальных аппаратных средств генерировать сигналы прерывания, которые позволят фиксировать (обнаруживать) такого рода ошибки.
Если бит present в дескрипторе указывает, что сейчас этот сегмент находится не в оперативной, а во внешней памяти (например, на винчестере), то названные поля адреса и длины используются для указания адреса сегмента в координатах внешней памяти. Помимо информации о местоположении сегмента, в дескрипторе сегмента, как правило, содержатся данные о его типе (сегмент кода или сегмент данных), правах доступа к этому сегменту (можно или нельзя его модифицировать, предоставлять другой задаче), отметка об обращениях к данному сегменту (информация о том, как часто или как давно/недавно этот сегмент используется или не используется, на основании которой можно принять решение о том, чтобы предоставить место, занимаемое текущим сегментом, другому сегменту).
При передаче управления следующей задаче ОС должна занести в соответствующий регистр адрес таблицы дескрипторов сегментов этой задачи. Сама таблица дескрипторов сегментов, в свою очередь, также представляет собой сегмент данных, который обрабатывается диспетчером памяти операционной системы.
При таком подходе появляется возможность размещать в оперативной памяти не все сегменты задачи, а только те, с которыми в настоящий момент происходит работа. С одной стороны, становится возможным, чтобы общий объём виртуального адресного пространства задачи превосходил объём физической памяти компьютера, на котором эта задача будет выполняться. С другой стороны, даже если потребности в памяти не превосходят имеющуюся физическую память, появляется возможность размещать в памяти как можно больше задач. А увеличение коэффициента мультипрограммирования позволяет увеличить загрузку системы и более эффективно использовать ресурсы вычислительной системы. Очевидно, однако, что увеличивать количество задач можно только до определенного предела, ибо если в памяти не будет хватать места для часто используемых сегментов, то производительность системы резко упадет. Ведь сегмент, который сейчас находится вне оперативной памяти, для участия в вычислениях должен быть перемещен в оперативную память. При этом если в памяти есть свободное пространство, то необходимо всего лишь найти его во внешней памяти и загрузить в оперативную память. А если свободного места сейчас нет, то необходимо будет принять решение – на место какого из ныне присутствующих сегментов будет загружаться требуемый.
Итак, если требуемого сегмента в оперативной памяти нет, то возникает прерывание и управление передаётся через диспетчера памяти программе загрузки сегмента. Пока происходит поиск сегмента во внешней памяти и загрузка его в оперативную, диспетчер памяти определяет подходящее для сегмента место. Возможно, что свободного места нет, и тогда принимается решение о выгрузке какого-нибудь сегмента и его перемещение во внешнюю память. Если при этом ещё остается время, то процессор передаётся другой готовой к выполнению задаче. После загрузки необходимого сегмента процессор вновь передаётся задаче, вызвавшей прерывание из-за отсутствия сегмента. Всякий раз при считывании сегмента в оперативную память в таблице дескрипторов сегментов необходимо установить адрес начала сегмента и признак присутствия сегмента.
При поиске свободного места используется одна из вышеперечисленных дисциплин работы диспетчера памяти (применяются правила «первого подходящего» и «самого неподходящего» фрагментов). Если свободного фрагмента памяти достаточного объёма сейчас нет, но, тем не менее, сумма этих свободных фрагментов превышает требования по памяти для нового сегмента, то в принципе может быть применено «уплотнение памяти».
В идеальном случае размер сегмента должен быть достаточно малым, чтобы его можно было разместить в случайно освобождающихся фрагментах оперативной памяти, но достаточно большим, чтобы содержать логически законченную часть программы с тем, чтобы минимизировать межсегментные обращения.
Для решения проблемы замещения (определения того сегмента, который должен быть либо перемещен во внешнюю память, либо просто замещен новым) используются следующие дисциплины:
Ø правило FIFO (first in – first out, т.е. «первый пришедший первым и выбывает»);
Ø правило LRU (least recently used, т.е. «последний из недавно использованных» или, иначе говоря, «дольше всего неиспользуемый»);
Ø правило LFU (least frequently used, т.е. «используемый реже всех остальных»);
Ø случайный (random) выбор сегмента.
Первая и последняя дисциплины являются самыми простыми в реализации, но они не учитывают, насколько часто используется тот или иной сегмент и, следовательно, диспетчер памяти может выгрузить или расформировать тот сегмент, к которому в самом ближайшем будущем будет обращение. Безусловно, достоверной информации о том, какой из сегментов потребуется в ближайшем будущем, в общем случае иметь нельзя, но вероятность ошибки для этих дисциплин многократно выше, чем у второй и третьей дисциплины, которые учитывают информацию об использовании сегментов.
Алгоритм FIFO ассоциирует с каждым сегментом время, когда он был помещён в память. Для замещения выбирается наиболее старый сегмент. Учет времени необязателен, когда все сегменты в памяти связаны в FIFO-очередь и каждый помещаемый в память сегмент добавляется в хвост этой очерёди. Алгоритм учитывает только время нахождения сегмента в памяти, но не учитывает фактическое использование сегментов. Например, первые загруженные сегменты программы могут содержать переменные, используемые на протяжении работы всей программы. Это приводит к немедленному возвращению к только что замещенному сегменту.
Для реализации дисциплин LRU и LFU необходимо, чтобы процессор имел дополнительные аппаратные средства. Минимальные требования – достаточно, чтобы при обращении к дескриптору сегмента для получения физического адреса, с которого сегмент начинает располагаться в памяти, соответствующий бит обращения менял свое значение (например, с нулевого, которое установила ОС, в единичное). Тогда диспетчер памяти может время от времени просматривать таблицы дескрипторов исполняющихся задач и собирать для соответствующей обработки статистическую информацию об обращениях к сегментам. В результате можно составить список, упорядоченный по длительности не использования (для дисциплины LRU) либо по частоте использования (для дисциплины LFU).
Важнейшей проблемой, которая возникает при организации мультипрограммного режима, является защита памяти. Для того чтобы выполняющиеся приложения не смогли испортить саму ОС и другие вычислительные процессы, необходимо, чтобы доступ к таблицам сегментов с целью их модификации был обеспечен только для кода самой ОС. Для этого код ОС должен выполняться в некотором привилегированном режиме, из которого можно осуществлять манипуляции с дескрипторами сегментов, тогда как выход за пределы сегмента в обычной прикладной программе должен вызывать прерывание по защите памяти. Каждая прикладная задача должна иметь возможность обращаться только к своим собственным сегментам.
При использовании сегментного способа организации виртуальной памяти появляется несколько интересных возможностей. Во-первых, появляется возможность при загрузке программы на исполнение размещать её в памяти не целиком, а «по мере необходимости». Действительно, поскольку в подавляющем большинстве случаев алгоритм, по которому работает код программы, является разветвлённым, а не линейным, то в зависимости от исходных данных некоторые части программы, расположенные в самостоятельных сегментах, могут быть и не задействованы; значит, их можно и не загружать в оперативную память. Во-вторых, некоторые программные модули могут быть разделяемыми. Эти программные модули являются сегментами, и в этом случае относительно легко организовать доступ к таким сегментам. Сегмент с разделяемым кодом располагается в памяти в единственном экземпляре, а в нескольких таблицах дескрипторов сегментов исполняющихся задач будут находиться указатели на такие разделяемые сегменты.
Однако у сегментного способа распределения памяти есть и недостатки. Прежде всего, из рис. 10.2 видно, что для получения доступа к искомой ячейке памяти необходимо потратить намного больше времени. Мы должны сначала найти и прочитать дескриптор сегмента, а уже потом, используя данные из него о местонахождении нужного нам сегмента, можем вычислить и конечный физический адрес. Для того чтобы уменьшить эти потери, используется кэширование – то есть те дескрипторы, с которыми мы имеем дело в данный момент, могут быть размещены в сверхоперативной памяти (специальных регистрах, размещаемых в процессоре).
Несмотря на то, что этот способ распределения памяти приводит к существенно меньшей фрагментации памяти, нежели способы с неразрывным распределением, фрагментация остается. Кроме этого, мы имеем большие потери памяти и процессорного времени на размещение и обработку дескрипторных таблиц. Ведь на каждую задачу необходимо иметь свою таблицу дескрипторов сегментов. А при определении физических адресов необходимо выполнять операции сложения.
Поэтому следующим способом разрывного размещения задач в памяти стал способ, при котором все фрагменты задачи одинакового размера и длины, кратной степени двойки, чтобы операции сложения можно было заменить операциями конкатенации (слияния). Это – страничный способ организации виртуальной памяти.
Страничный способ организации виртуальной памяти – способ разрывного размещения задач в памяти, при котором все фрагменты задачи имеют одинаковый размер, кратный степени двойки (чтобы вместо операции сложения для получения физического адреса можно было использовать операцию конкатенации). При таком способе все фрагменты программы, на которые она разбивается (кроме последней части) получаются одинаковыми. Одинаковыми должны быть и единицы памяти, предоставляемые для размещения фрагментов программы. Эти одинаковые части называются страницами:
Ø оперативная память разбивается на физические страницы;
Ø программа разбивается на виртуальные страницы.
Часть виртуальных страниц располагается в оперативной памяти, а часть – во внешней (файл подкачки, страничный файл, swap-файл).
Итак, разбиение всей оперативной памяти на страницы одинаковой величины, причем величина каждой страницы выбирается кратной степени двойки, приводит к тому, что вместо одномерного адресного пространства памяти можно говорить о двумерном. Первая координата адресного пространства – это номер страницы, а вторая координата – номер ячейки внутри выбранной страницы (его называют индексом). Таким образом, физический адрес определяется парой (Pp, i), а виртуальный адрес – парой (Pv, i), где Pv – это номер виртуальной страницы, Pp – это номер физической страницы и i – это индекс ячейки внутри страницы. Количество битов, отводимое под индекс, определяет размер страницы, а количество битов, отводимое под номер виртуальной страницы, – объём возможной виртуальной памяти, которой может пользоваться программа. Отображение, осуществляемое системой во время исполнения, сводится к отображению Pv в Pp и приписывании к полученному значению битов адреса, задаваемых величиной i. При этом нет необходимости ограничивать число виртуальных страниц числом физических, то есть не поместившиеся страницы можно размещать во внешней памяти, которая в данном случае служит расширением оперативной.
Для отображения виртуального адресного пространства задачи на физическую память, как и в случае с сегментным способом организации, для каждой задачи необходимо иметь таблицу страниц для трансляции адресных пространств. Для описания каждой страницы диспетчер памяти ОС заводит соответствующий дескриптор, который отличается от дескриптора сегмента прежде всего тем, что в нем нет необходимости иметь поле длины – ведь все страницы имеют одинаковый размер. По номеру виртуальной страницы в таблице дескрипторов страниц текущей задачи находится соответствующий элемент (дескриптор). Если бит присутствия имеет единичное значение, значит, данная страница сейчас размещена в оперативной, а не во внешней памяти и мы в дескрипторе имеем номер физической страницы, отведенной под данную виртуальную страницу. Если же бит присутствия равен нулю, то в дескрипторе мы будем иметь адрес виртуальной страницы, расположенной сейчас во внешней памяти. Таким образом осуществляется трансляция виртуального адресного пространства на физическую память. Этот механизм трансляции проиллюстрирован на рис. 10.3.
Защита страничной памяти, как и в случае с сегментным механизмом, основана на контроле уровня доступа к каждой странице. Как правило, возможны следующие уровни доступа: только чтение; чтение и запись; только выполнение. В этом случае каждая страница снабжается соответствующим кодом уровня доступа. При трансформации логического адреса в физический сравнивается значение кода разрешенного уровня доступа с фактически требуемым. При их несовпадении работа программы прерывается.
При обращении к виртуальной странице, не оказавшейся в данный момент в оперативной памяти, возникает прерывание и управление передаётся диспетчеру памяти, который должен найти свободное место. Обычно предоставляется первая же свободная страница. Если свободной физической страницы нет, то диспетчер памяти по одной из вышеупомянутых дисциплин замещения (LRU, LFU, FIFO, random) определит страницу, подлежащую расформированию или сохранению во внешней памяти. На её место он разместит ту новую виртуальную страницу, к которой было обращение из задачи, но её не оказалось в оперативной памяти.
| Регистр таблицы страниц |
| 32 000 |
| + |
| Страница №23 |
| 23 000 |
| 23 612 |
| Виртуальный адрес |
| P(Page) I(Index) |
| Таблица страниц текущей задачи |
| Номер физической страницы или адрес на диске |
| Права доступа |
| R-X |
| || |
Рис. 10.3.
Для использования дисциплин LRU и LFU в процессоре должны быть соответствующие аппаратные средства. В дескрипторе страницы размещается бит обращения (подразумевается, что на рис. 10.3 этот бит расположен в последнем поле), и этот бит становится единичным при обращении к дескриптору.
Если объём физической памяти небольшой и даже часто требуемые страницы не удается разместить в оперативной памяти, то возникает так называемая «пробуксовка». Другими словами, пробуксовка – это ситуация, при которой загрузка нужной нам страницы вызывает перемещение во внешнюю память той страницы, с которой мы тоже активно работаем. Очевидно, что это очень плохое явление. Чтобы его не допускать, желательно увеличить объём оперативной памяти (сейчас это стало самым простым решением), уменьшить количество параллельно выполняемых задач либо попробовать использовать более эффективные дисциплины замещения. В абсолютном большинстве современных ОС используется дисциплина замещения страниц LRU как самая эффективная.
В ряде ОС с пакетным режимом работы для борьбы с пробуксовкой используется метод «рабочего множества». Рабочее множество – это множество «активных» страниц задачи за некоторой интервал Т (т.е. тех страниц, к которым было обращение за этот интервал времени). Реально количество активных страниц задачи (за интервал Т) все время изменяется, и это естественно, но, тем не менее, для каждой задачи можно определить среднее количество её активных страниц. Это среднее число активных страниц и есть рабочее множество задачи. Наблюдения за исполнением множества различных программ, приведенные в литературе, показали, что даже если Т равно времени выполнения всей работы, то размер рабочего множества часто существенно меньше, чем общее число страниц программы. Таким образом, если ОС может определить рабочие множества исполняющихся задач, то для предотвращения пробуксовки достаточно планировать на выполнение только такое количество задач, чтобы сумма их рабочих множеств не превышала возможности системы.
Как и в случае с сегментным способом организации виртуальной памяти, страничный механизм приводит к тому, что без специальных аппаратных средств он будет существенно замедлять работу вычислительной системы. Поэтому обычно используется кэширование страничных дескрипторов.
Итак, основным достоинством страничного способа распределения памяти является минимально возможная фрагментация. Т.к. на каждую задачу может приходиться по одной незаполненной странице, поэтому память можно использовать достаточно эффективно; этот метод организации виртуальной памяти был бы одним из самых лучших, если бы не два следующих обстоятельства.
Первое – это то, что страничная трансляция виртуальной памяти требует существенных накладных расходов. В самом деле, таблицы страниц нужно тоже размещать в памяти. Кроме этого, эти таблицы нужно обрабатывать; именно с ними работает диспетчер памяти.
Второй существенный недостаток страничной адресации заключается в том, что программы разбиваются на страницы случайно, без учета логических взаимосвязей, имеющихся в коде. Это приводит к тому, что межстраничные переходы, как правило, осуществляются чаще, нежели межсегментные, и к тому, что становится трудно организовать разделение программных модулей между выполняющимися процессами.
Для того чтобы избежать второго недостатка, постаравшись сохранить достоинства страничного способа распределения памяти, был предложен ещё один способ – сегментно-страничный. Правда, за счёт дальнейшего увеличения накладных расходов на его реализацию.
При сегментно-страничном способе организации виртуальной памяти программа разбивается на логически законченные части – сегменты, виртуальный адрес содержит указание на номер соответствующего сегмента. Вторая составляющая виртуального адреса – смещение относительно начала сегмента, может состоять из двух полей:
Ø виртуальной страницы;
Ø индекса.
Виртуальный адрес состоит из трех компонентов:
Ø сегмента;
Ø страницы;
Ø индекса.
| Регистр таблицы сегментов (таблицы дескрипторовсегментов) |
| 32 000 |
| + |
| 32 017 |
| Виртуальный адрес |
| S(Segment) P(Page) I(Index) |
| Таблица сегментов текущей задачи |
| Адрес начала сегмента |
| Число страниц |
| Права доступа |
| 11 000 |
| R-X |
| + |
| Страница №23 |
| 23 000 |
| 23 612 |
| Номер физической страницы |
| Права доступа |
| R-X |
| || |
Получение физического адреса и извлечение из памяти необходимого элемента для этого способа представлено на рис. 10.4.
Рис. 10.4.
Из рис.10.4 видно, что этот способ организации виртуальной памяти вносит ещё большую задержку доступа к памяти. Необходимо сначала вычислить адрес дескриптора сегмента и прочитать его, затем вычислить адрес элемента таблицы страниц этого сегмента и извлечь из памяти необходимый элемент, и уже только после этого можно к номеру физической страницы приписать номер ячейки в странице (индекс). Задержка доступа к искомой ячейке получается по крайней мере в три раза больше, чем при простой прямой адресации. Чтобы избежать этой неприятности, вводится кэширование, причем кэш, как правило, строится по ассоциативному принципу. Другими словами, просмотры двух таблиц в памяти могут быть заменены одним обращением к ассоциативной памяти.
Принцип действия ассоциативного запоминающего устройства предполагает, что каждой ячейке памяти такого устройства ставится в соответствие ячейка, в которой записывается некий ключ (признак, адрес), позволяющий однозначно идентифицировать содержимое ячейки памяти. Сопутствующую ячейку с информацией, позволяющей идентифицировать основные данные, обычно называют полем тега. Просмотр полей тега всех ячеек ассоциативного устройства памяти осуществляется одновременно, то есть в каждой ячейке тега есть необходима