СТРАНИЧНАЯ ОРГАНИЗАЦИЯ

Как разделы с разными фиксированными размерами, так и разделы переменного размера недостаточно эффективно используют память. Результатом работы первых становится внутренняя фрагментация, результатом работы последних — внешняя. Предположим, однако, что основная память разделена на одинаковые блоки относительно небольшого фиксированного размера. Тогда блоки процесса, известные как страницы (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,а).

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

СЕГМЕНТАЦИЯ

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

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

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

Еще одно следствие того, что сегменты имеют разные размеры, состоит в отсутствии простого соотношения между логическими и физическими адресами. Аналогично страничной организации, схема простой сегментации использует таблицу сегментов для каждого процесса и список свободных блоков основной памяти. Каждая запись таблицы сегментов должна содержать стартовый адрес сегмента в основной памяти и его длину, чтобы обезопасить систему от использования некорректных адресов. При работе процесса адрес его таблицы сегментов заносится в специальный регистр, используемый аппаратным обеспечением. Рассмотрим адрес из п+т бит, где крайние слева п бит являются номером сегмента, а правые т бит — смещением. В нашем примере, помещенном на рис. 7.11,в, n = 4 и т — 12. Таким образом, макси­мальный размер сегмента составляет 2¹² = 4096. Для трансляции адреса необходимо выполнение следующих действий.

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

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

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

• Требуемый физический адрес представляет собой сумму физического адреса начала сегмента и смещения.

В нашем примере имеется логический адрес 0001001011110000, представляющий собой сегмент номер 1, смещение 752, Предположим, что этот сегмент располагается в основной памяти начиная с физического адреса 0010000000100000. Тогда интересующий нас физический адрес равен 0010000000100000+001011110000 = 0010001100010000 (см. рис. 7.12,6).

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

РЕЗЮМЕ, КЛЮЧЕВЫЕ ТЕРМИНЫ И КОНТРОЛЬНЫЕ ВОПРОСЫ

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

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

Ключевые термины

Абсолютная загрузка Логическая организация Совместное использование

Внешняя фрагментация Логический адрес Страница

Внутренняя фрагментация Относительный адрес Страничная организация

Динамическая загрузка Перенос Таблица страниц

времени исполнения Переносимая загрузка Уплотнение

Динамическое распределение Распределение Управление памятью

Динамическое связывание Редактор связей Физическая организация

Загрузка Связывание Физический адрес

Защита Сегментация Фиксированное

Кадр Система двойников распределение

Контрольные вопросы

7.1. Каким требованиям должно удовлетворять управление памятью?

7.2. Почему желательно обеспечить возможность переноса процессов?

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

7.4. По каким причинам может потребоваться обеспечение доступа к одной области памяти нескольким процессам?

7.5. В чем состоит преимущество использования разделов разного размера при использовании схемы фиксированного распределения?

7.6. В чем состоит отличие между внутренней и внешней фрагментацией?

7.7. В чем заключается различие между логическим, относительным и физическим адресами?

7.8. В чем разница между страницей и кадром?

7.9. В чем разница между страницей и сегментом?

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

Книги, рекомендованные для чтения в разделе 2.9, включают материал, посвященный вопросам управления памятью.

Поскольку распределение вытесняется технологиями виртуальной памяти, большинство книг предлагают только поверхностный обзор рассматриваемых в данной главе методов. Одной из наиболее полных и интересных работ является [MILE92]; обсуждение стратегий распределения памяти имеется и в [KNUT97].

Вопросы компоновки и загрузки рассматриваются во многих книгах, посвященных разработке программ, архитектуре компьютеров и операционным системам. Здесь можно порекомендовать обратиться к книгам [ВЕСК90] и [CLAR98].

ВЕСК90 BeckL. System Software, — Reading, MA: Addison-Wesley, 1990.

CLAR98Clarke D., Merusi D. System Software Programming: The Way Thing Work. — Upper Saddle River, HJ: Prentice Hall, 1998.

KNUT97Кнут Д.Э. Искусство программирования. Том 1. Основные алгоритмы, 3-е изд. — М.: Издательский дом "Вильяме", 2000.

MILE92Milenkovic M. Operating Systems: Concepts and Design. — New York: I- McGraw-Hill, 1992.

ЗАДАЧИ

7.1. В разделе 2.3 были перечислены пять целей управления памятью, а в разделе 7.1 — пять требований. Обоснуйте взаимосвязанность этих списков.

7.2. Рассмотрите схему динамического распределения. Покажите, что в среднем количество свободных блоков памяти ("дыр") в два раза меньше количества выделенных процессам разделов.

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

7.4. Рассмотрите еще один алгоритм размещения при динамическом распределении — метод наихудшего подходящего, при котором для размещения процесса используется наибольший свободный блок памяти. Каковы его достоинства и недостатки по сравнению с другими рассмотренными методами? Какова средняя длина поиска при этом методе?

7.5. Система двойников используется для распределения блока размером 1 Мбайт.

а. Изобразите в виде, подобном приведенному на рис. 7.6, результат выполнения такой последовательности запросов: запрос А = 70 Кбайт, запрос В = 35 Кбайт, запрос С = 80 Кбайт, освобождение А, запрос D = 60 Кбайт, освобождение В, освобождение D, освобождение С.

б. Приведите представление системы двойников в виде бинарного дерева после освобождения В.

7.6. Рассмотрим систему двойников, в которой некий только что выделенный блок имеет адрес 011011110000.

а. Если размер блока равен 4, то каков бинарный адрес его двойника?

б. Если размер блока равен 16, то каков бинарный адрес его двойника?

7.7. Пусть buddy_k (x) — адрес того блока размером 2^k, который является двойником блока по адресу х. Запишите выражение для buddy_k (х) .

7.8. Последовательность Фибоначчи определяется следующим образом:

F₀=0, F_l=l,...,F_n+2=F_n+1+F_n, n>0

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

б. Каким достоинством должна обладать такая система двойников по сравнению с описанной в данной главе?

7.9. Во время выполнения программы процессор увеличивает содержимое регистра команд (счетчика кода) на одно слово после выборки каждой команды. Однако если встречаются команды ветвления или вызова подпрограммы, то содержимое данного регистра вызывает продолжение выполнения в некотором другом месте программы. Рассмотрим рис. 7.8. Имеется альтернатива.

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

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

Какой подход следует предпочесть?

7.10. Виртуальный адрес а в страничной системе представляет собой пару (p,w), в которой р — номер страницы, a w — номер байта этой страницы. Пусть z —количество байтов в странице. Найдите формулу, представляющую р и w как функции от z и а.

7.11. Рассмотрим память, в которой смежные сегменты S₁, S₂, ..., S_n размещаются в порядке их создания от одного конца памяти к другому, как показано ниже:

При создании сегмента S_n+1 он размещается непосредственно после сегмента S_nдаже если некоторые из сегментов S₁, S₂, ..., S_n были к этому моменту удалены. Когда граница между сегментами (используемыми или удаленными) и свободной памятью достигает конца памяти, используемые сегменты уплотняются, а. Покажите, что доля времени F, затрачиваемая на уплотнение, удовлетворяет следующему неравенству:

Здесь

s — средняя длина сегмента в словах,

t — среднее время жизни сегмента (в обращениях к памяти),

f — доля памяти, не используемая в установившихся условиях.

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

б. Определите F для f = 0.2, t = 1000 и s = 50.