Страничная организация

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

На рис. 7.9 показано использование страниц и кадров. В любой момент времени некоторые из кадров памяти используются, а некоторые свободны. Операционная система поддерживает список свободных кадров. Процесс А, хранящийся на диске, состоит из четырех страниц. Когда приходит время загрузить этот процесс в память, операционная система находит четыре свободных кадра и загружает страницы процесса А в эти кадры (рис. 7.9,6). Затем загружаются процесс В, состоящий из трех страниц, и процесс С, состоящий из четырех страниц. После этого процесс В приостанавливается и выгружается из основной памяти. Позже наступает момент, когда все процессы в памяти оказываются заблокированы, и операционная система загружает в память новый процесс D, состоящий из пяти страниц.

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

На рис. 7.10 показаны различные таблицы страниц, после того как процесс D оказывается загруженным в страницы 4, 5, 6, 11 и 12. Таблица страниц содержит по одной записи для каждой страницы процесса, так что таблицу легко проиндексировать номером страницы, начиная с 0. Каждая запись содержит номер фрейма в основной памяти (если таковой имеется), в котором хранится соответствующая страница. Кроме того, операционная система поддерживает единый список свободных (т.е. не занятых никаким процессом и доступных для размещения в них страниц) кадров.

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

Для удобства работы с такой схемой добавим правило, в соответствии с которым размер страницы (а, следовательно, и размер кадра) должен представлять собой степень 2. При использовании такого размера страниц легко показать, что относительный адрес, который определяется относительно начала программы, и логический адрес, представляющий собой номер кадра и смещение, идентичны. Соответствующий пример приведен на рис. 7.11. Здесь используется 16-битовый адрес и страницы размером 1 Кбайт = 1024 байт. Относительный адрес 1502 в бинарном виде записывается как 0000010111011110. При размере страницы в 1 Кбайт поле смещения требует 10 бит, оставляя 6 бит для номера страницы. Таким образом, программа может состоять максимум из 2⁶ = 64 страниц по 1 Кбайт каждая. Как показано на рис. 7.11, относительный адрес 1502 соответствует смещению 478 (0111011110) на странице 1 (000001), что дает то же бинарное число 0000010111011110.

Использование страниц с размером, равным степени двойки, приводит к таким следствиям. Во-первых, схема логической адресации прозрачна для программиста, ассемблера и компоновщика. Каждый логический адрес (номер страницы и смещение) программы идентичен относительному адресу. Во-вторых, при этом относительно просто реализуется аппаратная функция преобразования адресов во время работы. Рассмотрим адрес из п+т бит, где крайние слева п бит представляют собой номер страницы, а крайние справа m бит — смещение. В нашем примере (рис. 7.11,6) п = 6 и т = 10. Для преобразования адреса необходимо выполнить следующие шаги.

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

• Используя номер страницы в качестве индекса в таблице страниц процесса, найти номер кадра k.

• Начальный физический адрес кадра — k´2'", и интересующий нас физический адрес представляет собой это число плюс смещение. Такой адрес не надо вычислять — он получается в результате простого добавления номера кадра к смещению.

В нашем примере имеется логический адрес 0000010111011110, представляющий страницу номер 1 и смещение 478. Предположим, что эта страница размещена в кадре основной памяти номер 6 (бинарное представление — 000110). В таком случае физический адрес представляет собой кадр 6, смещение 478, т.е. 0001100111011110 (рис. 7.12,а).

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