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

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

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

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

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

Рис. 10.5. Страничное распределение памяти

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

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

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

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

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

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

• первая попавшаяся страница;

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

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

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

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

Виртуальный адрес при страничном распределении может быть представлен в виде пары (p, s), где p - номер виртуальной страницы процесса (нумерация страниц начинается с 0), а s - смещение в пределах виртуальной страницы. Учитывая, что размер страницы равен 2 в степени к, смещение s может быть получено простым отделением k младших разрядов в двоичной записи виртуального адреса. Оставшиеся старшие разряды представляют собой двоичную запись номера страницы p.

Виртуальный адрес при страничном распределении может быть представлен в виде пары (р, s_v), где р — порядковый номер виртуальной страницы процесса (нумерация страниц начинается с 0), a s_v — смещение в пределах виртуальной страницы. Физический адрес также может быть представлен в виде пары (n, s_f), где n — номер физической страницы, a s_f — смещение в пределах физической страницы. Задача подсистемы виртуальной памяти состоит в отображении (р, s_v) в (n, s_f).

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

Первое из них состоит в том, что объем страницы выбирается равным степени двойки — 2^k. Из этого следует, что смещение s может быть получено простым отделением k младших разрядов в двоичной записи адреса, а оставшиеся старшие разряды адреса представляют собой двоичную запись номера страницы (при этом неважно, является страница виртуальной или физической). Например, если размер страницы 1 Кбайт (2¹⁰), то из двоичной записи адреса 5071₈ = 101 000 111 001₂ можно определить, что он принадлежит странице в двоичном выражении 10₂, и смещен относительно ее начала на 1 000 111 001₂ байт.

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

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

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

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

1. Из специального регистра процессора извлекается адрес AT таблицы страниц активного процесса. На основании начального адреса таблицы страниц, номера виртуальной страницы р (старшие разряды виртуального адреса) и длины отдельной записи в таблице страниц L (системная константа) определяется адрес нужного дескриптора в таблице страниц: a=AT+(p*L).

Рис. 10.6. Механизм преобразования виртуального адреса в физический при страничной организации памяти

2. Из этого дескриптора извлекается номер соответствующей физической страницы — n.

3. К номеру физической страницы присоединяется смещение s (младшие разряды виртуального адреса).

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

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

Чтобы уменьшить частоту страничных прерываний, следовало бы увеличивать размер страницы. Кроме того, увеличение размера страницы уменьшает размер таблицы страниц, а значит, уменьшает затраты памяти.

С другой стороны, если страница велика, то велика и фиктивная область в последней виртуальной странице каждой программы. В среднем на каждой программе теряется половина объема страницы, что в сумме при большой странице может составить существенную величину. Из приведенных соображений следует, что выбор размера страницы является сложной оптимизационной задачей, требующей учета многих факторов. На практике же разработчики ОС и процессоров ограничиваются неким рациональным решением, пригодным для широкого класса вычислительных систем. Типичный размер страницы составляет несколько килобайт. Например, наиболее распространенные процессоры х86 и Pentium компании Intel, а также операционные системы, устанавливаемые на этих процессорах, поддерживают страницы размером 4096 байт (4 Кбайт). Так, процессор Pentium позволяет использовать также страницы размером до 4 Мбайт одновременно со страницами объемом 4 Кбайт.

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

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

Многоуровневые таблицы страниц. Размер страницы влияет также на количество записей в таблицах страниц. Чем меньше страница, тем более объемными являются таблицы страниц процессов и тем больше места они занимают в памяти. Учитывая, что в современных процессорах максимальный объем виртуального адресного пространства процесса, как правило, не меньше 4 Гбайт (2³²), то при размере страницы 4 Кбайт (2¹²) и длине записи 4 байта для хранения таблицы страниц может потребоваться 4 Мбайт памяти! Выходом в такой ситуации является хранение в памяти только той части таблицы страниц, которая активно используется в данный период времени. Так как сама таблица страниц хранится в таких же страницах физической памяти, что и описываемые ею страницы, то принципиально возможно временно вытеснять часть таблицы страниц из оперативной памяти. Это означает, что сами таблицы страниц становятся объектами страничной организации, как и любые другие страницы.

Чтобы обойти проблему необходимости постоянного хранения в памяти огромных таблиц страниц некоторые процессоры используют многоуровневую таблицу страниц. При такой схеме имеется каталог таблиц страниц, в котором каждая запись указывает на таблицу страниц. Таким образом, если размер каталога – Х, а максимальный размер таблицы – Y, то процесс может состоять максимум из X*Y страниц. Обычно максимальный размер таблицы страниц определяется условием ее размещения в одной странице (как в Pentium).

Именно такой результат может быть достигнут путем более сложной двухуровневой структуризации виртуального адресного пространства, при котором все множество виртуальных адресов процесса делится на разделы, а разделы делятся на страницы (рис. 10.7).

Все страницы имеют одинаковый размер, а разделы содержат одинаковое количество страниц. Если размер страницы и количество страниц в разделе выбрать равными степени двойки (2^k и 2ⁿ соответственно), то принадлежность виртуального адреса к разделу и странице, а также смещение внутри страницы, можно определить очень просто: младшие k двоичных разрядов дают смещение, следующие n разрядов представляют собой номер виртуальной страницы, а оставшиеся старшие разряды (обозначим их количество m) содержат номер раздела.

Для каждого раздела строится собственная таблица страниц. Количество дескрипторов в таблице и их размер подбираются такими, чтобы объем таблицы оказался равным объему страницы. Например, в процессоре Pentium при размере страницы 4 Кбайт длина дескриптора страницы составляет 4 байта и количество записей в таблице страниц, помещающейся на страницу, равняется соответственно 1024. Каждая таблица страниц описывается дескриптором, структура которого полностью совпадает со структурой дескриптора обычной страницы.

Рис. 10.7. Структура виртуального адресного пространства с разделами

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

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

Проследим более подробно схему преобразования адресов для случая двухуровневой структуризации виртуального адресного пространства (рис. 10.8).:

1. Путем отбрасывания k+n младших разрядов в виртуальном адресе определяется номер раздела, к которому принадлежит данный виртуальный адрес.

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

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

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

Страничное распределение памяти может быть реализовано в упрощенном варианте, без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оперативной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю преимуществ работы с виртуальной памятью большого объема, но сохраняет другое достоинство страничной организации — позволяет успешно бороться с фрагментацией физической памяти. Действительно, во-первых, программу можно разбить на части и загрузить в разрозненные участки свободной памяти, во-вторых, при загрузке виртуальных страниц никогда не образуется неиспользуемых остатков, так как размеры виртуальных и физических страниц совпадают. Такой режим работы системы управления памятью используется в некоторых специализированных ОС, когда требуется высокая реактивность системы и способность выполнять переменный набор приложений (пример — ОС семейства Novell NetWare 3.x и 4.x).

Рис. 10.8. Схема преобразования виртуального адреса для двухуровневой структуризации адресного пространства

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

Проблема ускорения поиска решается на уровне архитектуры компьютера.

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

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

Для решения этой проблемы большинство использующихся схем виртуальной памяти используют специальный высокоскоростной кэш для записей таблиц страниц, который обычно называют буфером быстрого преобразования адреса, или буфером поиска трансляции (translation lookaside buffer - TLB), или буфер ассоциативной трансляции, или иногда ассоциативной памятью.

Основываясь на правиле “девяносто к десяти” (правиле локализации), что большинство программ склонно делать огромное количество обращений к небольшому количеству страниц, компьютер снабжается небольшим аппаратным устройством, служащим для отображения виртуальных адресов в физические без прохода по таблице страниц. Оно обычно находится внутри диспетчера памяти и состоит из нескольких записей, от 8 до 4096. Так, в архитектуре Intel-32 таких элементов до Pentium-4 было 32 (что обеспечивается 98% попаданий в кэш), начиная с Pentium-4 - 128.

Так как ассоциативная память содержит только некоторые из записей таблицы страниц, то каждая запись в TLB должна включать поле с номером виртуальной страницы. Кроме этого, каждая запись таблицы ассоциативной памяти содержит информацию об одной виртуальной странице, а именно: бит изменения страницы, код защиты (чтение/запись/выполнение), бит действительности записи (используется ли она в данный момент) и номер физического страничного блока.

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

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

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

Число удачных поисков номера страницы в ассоциативной памяти по отношению к общему числу поисков называется hit (совпадение) ratio (пропорция, отношение). Иногда также используется термин «процент попаданий в кэш». Обращение к одним и тем же страницам повышает hit ratio. Чем больше hit ratio, тем меньше среднее время доступа к данным, находящимся в оперативной памяти.

Предположим, например, что для определения адреса в случае кэш-промаха через таблицу страниц необходимо 100 нс (t1), а для определения адреса в случае кэш-попадания через ассоциативную память – 20 нс (t2). С 90% hit ratio (p – вероятность кэш-попадания) среднее время определения адреса по формуле полной вероятности t = t1(1 - p) + t2p = 100*0,1 + 20*0,9 = 28 нс.

К сожалению, в случае переключения контекста в архитектуре Intel-32 необходимо очистить весь кэш, поскольку для каждого процесса есть своя таблица страниц, и те же самые номере страниц для разных процессов могут отвечать разным фреймам (кадрам) в физической памяти. Таким образом, использование ассоциативной памяти увеличивает время переключения контекста. Рассмотренная двухуровневая (ассоциативная память + таблица страниц) схема преобразования адреса является ярким примером иерархии памяти, основанной на использовании принципа локальности, о чем мы будем говорить в следующей лекции.

Инвертированные таблицы страниц, хеш-таблицы. Традиционные таблицы страниц требуют по одной записи на каждую страницу. Если адресное пространство состоит из 2³² байт с размером страницы 4096 байт, тогда таблица страниц содержит более миллиона записей. При этом таблица страниц будет занимать минимум 4 Мбайт. При 64-разрядном адресном пространстве с размером страницы 4 Кбайт и размером записи таблицы в 8 байт, таблица займет больше 30 Тбайт. Это, конечно, нереально даже в будущем.

Поэтому еще одним подходом к использованию одно- или двухуровневых таблиц страниц является применение инвертированной таблицы страниц. Этот подход применяется на машинах PowerPC, некоторых рабочих станциях Hewlett-Packard, IBM RT, IBM AS/400 и ряде других.

В этой модели таблица содержит по одной записи на каждый страничный кадр физической памяти, а не на страницу в виртуальном адресном пространстве. Существенно, что достаточно одной таблицы для всех процессов. Например, при 64-разрядных виртуальных адресах, при размере страниц 4 Кбайт и 256 Мбайт оперативной памяти инвертированная таблица страниц потребует всего лишь 65536 записей. Каждая запись отслеживает, что (процесс, виртуальная страница) расположено в данном страничном блоке.

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

Выйти из этого положения можно, используя рассмотренный ранее буфер быстрого преобразования адреса (TLB). Но при неудачном поиске в буфере TLB поиск в инвертированной таблице страниц должен выполняться программно. Один из возможных способов усовершенствовать его – поддерживать хеш-таблицу виртуальных адресов.

При таком подходе часть виртуального адреса, представляющего номер страницы, отображается в хеш-таблицу с использованием простой функции хеширования. Например, для N элементов, хранящихся в таблице размером М >= N (причем М не намного больше N), метка элемента преобразуется в почти случайное число n между 0 и М-1 методом деления метки по модулю М.

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

Например, вставка элемента в таблицу происходит следующим образом.

1. Преобразуем метку элемента в почти случайное число n между 0 и М-1 методом деления метки по модулю М.

2. Используем полученное значение n в качестве индекса в хеш-таблице:

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

Б. Если запись уже занята и ее метка соответствует искомой, значит, найден требуемый элемент.

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

Средняя продолжительность поиска элемента при открытой хеш-таблице с использованием таблиц переполнения с цепочками, равная 1 + (N-1)/2M, для больших значений N=M стремится к 1.5, в частности для бинарного поиска в сортированном списке продолжительность поиска элемента равна Log₂M.

Определение наилучшего размера страницы. Зачастую размер страницы является параметром, выбираемым ОС. Даже, если аппаратное обеспечение предусматривает, например, размер страницы 512 байт, ОС может просто рассматривать страницы 0 и 1, 2 и 3, 4 и 5 и т.д. как страницы размером 1 Кбайт, всегда представляя для них два последовательных страничных блока.

Определение наилучшего размера страницы требует уравновешивания нескольких факторов. Поэтому не существует абсолютного оптимального решения. Существует два довода в пользу маленького размера страниц. Случайно выбранный текст, данные или сегмент стека не заполняет целое количество страниц. В среднем половина последней страницы оказывается пустой. Если в памяти n сегментов при размере страницы р байт, то np/2 байт будет потрачено впустую в результате внутренней фрагментации. Это разумный аргумент в пользу страниц небольшого размера.

Другой довод становится очевидным, если представить программу, состоящую из восьми последовательных этапов, по 4 Кбайт каждый. При размере страницы 32 Кбайт программе должно быть постоянно выделено 32 Кбайт. При размере страницы 16 Кбайт ей необходимо только 16 Кбайт. При размере страницы 4 Кбайт, или меньше, программа требует всего лишь 4 Кбайт в любой момент времени. То есть большой размер страницы скорее, чем маленький, станет причиной того, что в памяти находится неиспользуемая часть страницы.

С другой стороны, небольшой размер страницы означает, что программам будет нужно много страниц, следовательно, огромная таблица страниц. Как правило, страница за раз переносится на диск и с него. При этом большая часть времени уходит на поиск цилиндра и задержку вращения. Так что перемещение маленькой страницы занимает почти столько же времени, сколько и большой. Может потребоваться 64*10 мс, чтобы загрузить 64 страницы размером 512 байт, и всего лишь 4*12 мс для загрузки 4-х страниц по 8 Кбайт.

Учитывая все это можно математически проанализировать размер страницы. Пусть средний размер процесса равен S байт, а страницы – Р байт. Кроме того, предположим, что запись для каждой страницы требует Е байт. Тогда приблизительное количество страниц, необходимое для процесса, равно S/P, что займет SE/P байт для таблицы страниц. Потеря памяти в последней странице процесса равна P/2. Таким образом, общие накладные расходы вследствие поддержки таблицы страниц и потери от внутренней фрагментации равны сумме этих составляющих: расход = SE/P + P/2.

Первое слагаемое (размер таблицы страниц) увеличивается при уменьшении размера страниц. Второе слагаемое (внутренняя фрагментация) при увеличении размера страниц возрастает. Оптимальный вариант должен находиться где-то посередине. Если взять 1-ю производную по переменной Р и приравнять ее к нулю, получим равенство: -SE/P² + ½ = 0.

Из этого равенства можно получить формулу, дающую оптимальный размер страниц (принимая во внимание только потери памяти на фрагментацию и размер таблицы страниц). В результате получится: P = √2SE.

Для среднего размера процесса S = 1 Мбайт и размера записи в таблице страниц E = 8 байт оптимальный размер страницы будет равен 4 Кбайт. В современных компьютерах более часто встречаются размеры страниц 4 Кбайт или 8 Кбайт. Так как памяти становится больше, то размер страниц также имеет тенденцию роста (но зависимость нелинейная).