Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 132
Текст из файла (страница 132)
Во время выполнения стек и куча растут навстречу друг другу с противоположных концов блока памяти, выделяя память из свободного пространства, расположенного между ними. Предположим, что стек и куча всзрсчаются друг с другом, так как свободное пространство полностью использовано. Объясните доступные для разработчика транслятора варианты решения, если: а) следующий запрос — это запрос на новый блок памяти из стека; б) следующий запрос — запрос на новый блок памяти из кучи. Одно из удивительных свойств сбора мусора как метода восстановления памяти — это то, что его стоимость обратно пропорционпльна количеству восстановленной памяти (то есть чем меньше памяти восстанавливается, тем дороже обходится сбор мусора), 480 Глава 10. Управление памятью а) Объясните, в чем причина такой обратной пропорциональности.
б) Обычно, когда ресурсы памяти почти исчерпаны, программа выполняет несколько раз дорогостоягцую и занимающую много времени процедуру сбора мусора (которая восстанавливает малый объем памяти), прежде чем окончательно остановиться. Предложите метод, позволяющий избежать многократного выполнения таких бесполезных процедур сбора мусора. 6. В одном из ранних расширений языка РОВТВЛХ, предназначенном для обработки списков, у каждого списка имеется специальная голова, в которой содержится счетчик ссылок. Когда какой-нибудь список освобождается, то вместо возвращения его элементов в голову списка свободного пространства возвращается только его головной элемент, причем он помешается в конец списка свободного пространства (для этого используется специальный указатель на конец списка свободного пространства). Таким образом минимизируется стоимость возврашения списка в свободное пространство.
Элементы списка возвращаются в список свободного пространства только тогда, когда голова списка достигнет вершины списка свободного пространства. Какие преимущества дает такой метод, осуществляя перенос затрат на освобождение элементов списка с момента восстановления списка на момент повторного истюльзовалия памяти? 7. Элементы данных размером в целое слово, например числа, представляют проблемы при сборе мусора. Обычно такие элементы данных занимают целиком элемент кучи, не оставляя места для дополнительных битов маркировки. В таких случаях все подобные элементы размером в одно слово располагаются в специальном разделе кучи, а все биты сбора мусора для этих элементов записываются в специальный упакованный массив (битовый веквгор), расположенный за пределами кучи. Предполагая, что все элементы размером в целое слово являются числами (и, следовательно, не содержат указателей на другие элементы кучи), разработайте алгоритм сбора мусора, в котором допускаются указатели на элементы кучи размером в целое слово.
Ллгоритм должен включать маркировку и сбор. Организуйте поддержку отдельного списка свободного пространства для той части кучи, которая содержит элементы размером в целое слово. 8. В тексте утверждается, что в приложениях параллельной обработки пред почтительнее использовать счетчики ссылок для сбора мусора динамически выделяемой памяти. Почему в этой среде использование алгоритма маркировка-сбор было бы менее эффективным7 9.
Предложите алгоритм для накопления блоков, помеченных во время сбора мусора в куче с элементами переменного размера. Предполагается, что первое слово каждого блока содержит бит сбора мусора и идентификатор длины. Во время сбора мусора следует объединять (уплотнить) все смежные свободные блоки. 10. Разработайте систему управления распределением памяти для кучи ц, состоящей из блоков перемен ного размера, при выполнении следующих предположений. 10.6. Задачи и упражнения 481 а) Куча В используется только для хранения массивов вещественных чисел (одно число располагается в одном слове). Каждый массив содержит как минимум два элемента. б) Доступ к любому блоку массива осуществляется только через единственный внешний указатель, хранящийся в дескрипторе массива.
Вседескрипторы массивов хранятся в блоке А, расположенном отлельно от кучи В. в) Во время выполнения запросы на выделение блоков из кучи происходят случайным образом (и достаточно часто). г) Блоки явным образом возвращаются в своболное состояние при разрушении массивов. Это также происходит в случайные моменты времени и достаточно часто. д) Постоянные потери памяти вследствие ее фрагментации недопустимы. (Заметим, что свободный блок из одного слова никогда не может быть использован повторно.) Эти предположения в основном реализованы в АРЕ. Ваш проект должен специфицировать: 1) пачалыгую органшацию блока кучи В, а также все специальные внешние структуры, необходимые для управления памятью (например, голову списка свободного пространства); 2) механизм выделепил памяти на запрос блока длиной йгслов из кучи В; 3) механизм восстановления пиняти при обращении к менеджеру памяти для освобождения блока из М слов с заданным адресом; 4) механизм уплотнения памяти (если он необходим), включая спецификацию его работы и моментов времени, когда он вызывается.
11. В различных реализациях языка Рааса( операция С1зрозе обрабатывается различными способами, Ниже перечислены применяемые методики обработки: а) Операция з1зрозе(Р) всего лишь присваивает значение пН переменной- указателю Р. Предложите реализацию управления кучей с использованием одного указателя на текущую вершину (первое свободное место) кучи. Перемещайте указатель на новос место для выделения памяти, когда выполняется операция пеи. Не допускается перемешать указатель в обратном направлении. б) Предложите реализацию управления кучей с использованием, как в предыдушем случае, единственного указателя, который передвигается вперед в результате выполнения операции пен, однако теперь операция е1 грозе не только присваивает значение п|1 указателю Р, но н перемещает указатель вершины кучи назад на количество элементов, занимаемых объектом данных, на который указывает Р, так что эта область памяти восстанавливается и возвращается в кучу.
(Подсказкгп рассмотритс последовательность пен(Р); пен(О); е1зрозе(Р):.) в) Предложите способ реализации кучи с использованием списка свободного пространства для блоков памяти переменного размера, как описано 482 Глава 10. Управление памятью в разделе 1ОА. Используйте стратегию первого подходящего или наиболее подходящего блока для выделения памяти, запрошенной операцией пен. Реализуйте операцию бл»ро»е так, чтобы опа устанавливала свой параметр-указатель равным значению пл1 и возвращала блок памяти, на который указывает параметр-указатель Р, в список свободного пространства.
Рассмотрите проблемы мусора, повисших ссылок и фрагментации для кажлого из приведенных способов реализации операций б1»ро»е и пеил 12. Для создания связанных списков удобно применять указатель 0и». Рассмотрим следующее определение класса (с1а»»). с1в»» Шелесты»т (роб11с. Аббто1я»Ы1ялиебю»1 *Х1 П Добавляеи Х и слисиу рпувте: 11ляеббя»Г *Ргеюоо»1л»11»ее, *Кех»11»11тее,), Разработайте код для метода Аг1бТо1.~»С, который вставляет в список переданный ему аргумент в позицию, следуяощую за текущей (отмеченной указателем Сп ~ »), как это делается в коде: 1~лхеош »1 А1101. ялт и Овставляеи А[11лосле А1я 1 АИ 1.АООтог »11АА111> Глава 11. Распределенная обработка данных Технология компьютерных вычислений прошла путь от замкнутой работы на одной машине в 50-х и 60-х гг.
до интеграции совместных работ, часто проводимых в разных точках земного шара. Системы клиент-сервер, локальные сети и Всемирная паутина ЮЖЖ вЂ” это примеры того, когда множество компьютеров, находящихся в разных местах, должно взаимодействовать между собой для того, чтобы обработать определенную информацию. Основная проблема, которую пытаются решить перечисленные технологии, заклк>чается в том, что отдельный компьютер не является достаточно большим и быстрым, чтобы решить стоящие перед нами современные вычислительные задачи, что неизбежно приводит к совместному использованию нескольких компьютеров для решения одной задачи. В этой главе мы рассмотрим эволюцию идеологии языков программирования, позволившую осуществить переход к распределенной обработке данных.
11.1. Различные варианты управления подпрограммами В этом разделе мы обсудим различные варианты конструирования подпрограхьм. Активация процедур по методу простого вызова-возврата (см. раздел 9.1) со статическими и динамическими связями с объектами данных основывалась на правилах области видимости, что позволило нам реализовать многие языки программирования. Но для того, чтобы наша структура подпрограммы предоставляла некоторые дополнительные возможности, например реализацию сопрограмм, исключений и задач, нам следует рассмотреть некоторые вариации этого основного механизма. В первую очередь вспомним, что связь подпрограмм, описанная в разделе 9.1, основывалась нв следующих пяти предположениях: 1) подпрограммы не могут быть рекурсивными; 2) требуется явный оператор вызова подпрограммы; 3) подпрограммы должны полностью выполняться при каждом вызове; 4) управление в подпрограмму должно передаваться непосредственно в точке ее вызова; 5) должна существовать одна последовательность выполнения.
484 Глава 11. Распределенная обработка данных Первое предположение, касающееся рекурсии, мы уже рассмотрели достаточно подробно. Теперь мы попробуем изменить другие предположения и исследуем форму механизма подпрограмм, к которым приводят эти изменения. 11.1.1. Исключения и обработчики исключений Во время выполнения программы часто встречаются собьпия и условия, которые могут рассматриваться как исключения. Вместо нормального продолжения выполнения программы в этом случае необходимо вызвать подпрограмму, которая осуществляет специальную обработку, включая способность справляться со следующими ситуациями.
1. Сбойные ситуации, связанные с возникновением таких ошибок, как, например, переполнение при выполнении арифметической операции или ссылка на элемент массива с индексом вне допустимого диапазона, 2. Ньт1редсказуемые ситуации, возникающие при нормальном выполнении программы, как, например, генерация специальных заголовков в конце выводимой на принтер страницы или обработка признака конца вводимого файла. 3. Трассировка и мониторинг во время тестирования программы, например вывод трассировочной печати, когда меняется значение какой-либо переменной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
