Волкова немного о её семинарах (1119514)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Распределение памяти

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

Область памяти - это блок ячеек памяти, выделяемых для данных и каким-то образом объединенных логически.

Распределение памяти выполняется после фазы анализа текста исходной программы на этапе подготовки к генерации объектного модуля (перед генерацией кода объектного модуля, т.к. его результаты должны быть использованы в процессе генерации кода). Как правило, исходными данными для процесса распределения памяти в компиляторе служат таблица идентификаторов, построенная лексическим анализатором и информация, полученная синтаксическим анализатором при анализе декларативной чисти программы.

Современные компиляторы, в основном, работают с относительными, а не с абсолютными адресами ячеек памяти.

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

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

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

Компилятор также должен решать проблему выравнивания границ областей памяти, отводимых для различных лексических единиц, поскольку архитектура многих современных вычислительных систем предусматривает, что обработка данных выполняется более эффективно, если адрес, по которому выбираются данные, кратен определенному числу байт (2,4,8 или 16).

Выделяемую память можно разделить на локальную/глобальную и статическую/динамическую.

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

Глобальная память - это область памяти, которая выделяется один раз при инициализации результирующей программы и действует все время выполнения программы. Как правило, глобальная область памяти доступна из любой части исходной программы, но многие ЯП позволяют накладывать ограничения на доступ к каким-то фрагментам глобальной памяти (например, в С - с помощью квалификатора static).

Распределение памяти на локальные и глобальные области целиком определяется семантикой языка исходной программы.

Статическая память - это область памяти, размер которой известен на этапе компиляции.

Для статической памяти компилятор порождает некоторый адрес (как правило, относительный), и дальнейшая работа с ней происходит относительно этого адреса.

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

Для динамической памяти компилятор порождает фрагмент кода, который отвечает за распределение памяти (ее выделение и освобождение). Как правило, с динамическими областям памяти связаны многие операции с указателями и с экземплярами объектов (классов) в ООЯП.

Динамические области памяти можно разделить на динамические области памяти, выделяемые пользователем (если в тексте исходной программы явно используются функции, связанные с распределением памяти - например, new, delete в языке С++ - и за выделение и освобождение памяти отвечает сам разработчик, а не компилятор) и непосредственно компилятором (если в программе используются типы данных, операции над которыми предполагают перераспределение памяти - например, многие операции над экземплярами объектов (классов) в ООЯП; многие компиляторы ООЯП используют для этих целей специальный менеджер памяти).

Как статические, так и динамические области памяти сами по себе могут быть локальными или глобальными.

Остановимся поподробнее на способах динамического распределения памяти. Память при этом обычно берется из кучи (heap, часть памяти времени исполнения, наряду с памятью для хранения кода, статических данных и стека).

Явное выделение динамической области памяти

Явное выделение блоков фиксированного размера.

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

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

Свободные блоки можно «подшивать» между собой, используя часть блока для хранения указателей, с помощью которых осуществляется объединение свободной памяти в список. Когда очередной блок свободной памяти выделяется программе, он удаляется из списка, а начальный указатель принимает значение указателя на следующий свободный блок памяти. Когда какой-то блок памяти освобождается, он добавляется в список свободной памяти.

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

Явное выделение блоков переменного размера.

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

Один из методов выделения блоков переменного размера называется методом первого подходящего. При выделении блока размера s находится первый свободный блок размера f>=s. Затем этот блок разбивается на два - с размерами s и f-s. Поиск подходящего блока приводит к определенным накладным расходам времени. Но мы можем и не найти такой фрагмент. Тогда необходимо приостанавливать выполнение программы и начинать реорганизацию кучи. Надо искать все использованные фрагменты и перемещать их например на дно кучи. Тогда есть шанс получить необходимое свободное пространство.

Существует много других алгоритмов выделения и освобождения блоков памяти (см., например, книгу Ахо, Хопкрофта, Ульмана «Структуры данных и алгоритмы»).

Неявное выделение/освобождение памяти.

Неявно выделяемые блоки памяти также могут быть фиксированного или переменного размера.

При неявном динамическом выделении и освобождении блоков памяти, выделяемые блоки обычно имеют следующую структуру:

• размер блока (если блок фиксированного размера, то соответственно эта информация в нём не хранится.);

• счётчик ссылок, пометка (обычно есть либо одно, либо другое):

Счетчик ссылок подсчитывает количество указателей в программе, которые ссылаются на этот блок (если происходит присваивание указателей, например, p = q, то соответственно, один счётчик (для блока, на который указывал указатель p) уменьшается на единицу, а другой увеличивается), если счётчик равен нулю, то блок не используется и его можно освободить. Существует проблема циклических ссылок, когда счётчики всегда >0.

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

• указатели на блоки

• то, что досталось пользователю, заказавшему этот блок.

Общие принципы генерации объектного кода.

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

В случае М-языка программа, представленная в ПОЛИЗе достаточно легко, операция за операцией переводится в машинные команды.

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

Оптимизация.

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

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

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

Принципиально различаются два основных вида оптимизирующих преобразований:

• машинно-независимые преобразования исходной программы в форме ее внутреннего представления, основанные на хорошо известных математических и логических преобразованиях;

• машинно-зависимые преобразования результирующей объектной программы, зависящие от архитектуры вычислительной системы, на которой будет выполняться результирующая программа (может учитываться объем кэш-памяти, методы организации работы процессора). Эти преобразования, как правило, являются "ноу-хау", и именно они позволяют существенно повысить эффективность результирующего кода.

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов семинаров