7.7. Задачи
В разделе 2.3 были перечислены пять целей управления памятью, а в разделе 7.1 — пять требований. Обоснуйте взаимосвязанность этих списков.
Рассмотрите схему динамического распределения. Покажите, что в среднем количество свободных блоков памяти ("дыр") в два раза меньше количества выделенных процессам разделов.
Для реализации различных алгоритмов распределения, обсуждавшихся при рассмотрении динамического распределения (раздел 7.2), необходима поддержка списка свободных блоков памяти. Какова средняя продолжительность поиска для каждого из рассмотренных методов (наилучшего, первого и следующего подходящего)?
Рассмотрите еще один алгоритм размещения при динамическом распределении — метод наихудшего подходящего, при котором для размещения процесса используется наибольший свободный блок памяти. Каковы его достоинства и недостатки по сравнению с другими рассмотренными методами? Какова средняя длина поиска при этом методе?
Система двойников используется для распределения блока размером 1 Мбайт.
а. Изобразите в виде, подобном приведенному на рис. 7.6, результат выполнения такой последовательности запросов: запрос А = 70 Кбайт, запрос В = 35 Кбайт, запрос С = 80 Кбайт, освобождение А, запрос D = 60 Кбайт, освобождение В, освобождение D, освобождение С.
б. Приведите представление системы двойников в виде бинарного дерева после освобождения В.
7.6. Рассмотрим систему двойников, в которой некий только что выделенный блок имеет адрес 011011110000.
а. Если размер блока равен 4, то каков бинарный адрес его двойника?
б. Если размер блока равен 16, то каков бинарный адрес его двойника?
Пусть buddyk (x) — адрес того блока размером 2k, который является двойником блока по адресу х. Запишите выражение для buddyk (х) .
Последовательность Фибоначчи определяется следующим образом:
F0=0, Fl=l,...,Fn+2=Fn+1+Fn, n>0
а. Можно ли использовать эту последовательность для разработки системы двойников?
б. Каким достоинством должна обладать такая система двойников по сравнению с описанной в данной главе?
7.9. Во время выполнения программы процессор увеличивает содержимое регистра команд (счетчика кода) на одно слово после выборки каждой команды. Однако если встречаются команды ветвления или вызова подпрограммы, то содержимое данного регистра вызывает продолжение выполнения в некотором другом месте программы. Рассмотрим рис. 7.8. Имеется альтернатива.
В регистре команд использовать относительный адрес и выполнять трансляцию адресов динамически, с содержимым регистра команд в качестве входных данных. Команды ветвления или вызова подпрограммы генерируют относительный адрес, который и заносится в регистр команд.
В регистре команд содержать абсолютный адрес. В этом случае команды ветвления или вызова подпрограммы генерируют относительный адрес, который динамически транслируется, и результат трансляции заносится в регистр команд.
Какой подход следует предпочесть?
Виртуальный адрес а в страничной системе представляет собой пару (p,w), в которой р — номер страницы, a w — номер байта этой страницы. Пусть z —количество байтов в странице. Найдите формулу, представляющую р и w как функции от z и а.
Рассмотрим память, в которой смежные сегменты S1, S2, ..., Sn размещаются в порядке их создания от одного конца памяти к другому, как показано ниже:
|
S1 |
S2 |
… |
Sn |
Свободно |
При создании сегмента Sn+1 он размещается непосредственно после сегмента Sn даже если некоторые из сегментов S1, S2, ..., Sn были к этому моменту удалены. Когда граница между сегментами (используемыми или удаленными) и свободной памятью достигает конца памяти, используемые сегменты уплотняются, а. Покажите, что доля времени F, затрачиваемая на уплотнение, удовлетворяет следующему неравенству:
Здесь
s — средняя длина сегмента в словах,
t — среднее время жизни сегмента (в обращениях к памяти),
f — доля памяти, не используемая в установившихся условиях.
Указание: найдите среднюю скорость, с которой рассматриваемая граница движется по памяти, и предположите, что копирование одного слова требует как минимум двух обращений к памяти.
б. Определите F для f = 0.2, t = 1000 и s = 50.