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

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

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

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

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

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

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

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

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

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

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

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

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 размещаются в порядке их создания от одного конца памяти к другому, как показано ниже:

S1

S2

…

Sn

Свободно

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

Здесь

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

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

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

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

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