Домой

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




Скачать 392.84 Kb.
НазваниеРаспределение памяти Распределение памяти
страница1/3
Дата23.04.2013
Размер392.84 Kb.
ТипДокументы
Содержание
Локальная память
Глобальная память
Статическая память
Динамическая память
Явное выделение динамической области памяти
Явное выделение блоков переменного размера.
Неявное выделение/освобождение памяти.
Общие принципы генерации объектного кода.
Машинно-независимые оптимизирующие преобразования.
2. Оптимизация линейных участков программы.
3. Подстановка кода функции вместо ее вызова в объектный код.
4. Оптимизация циклов.
1. Распределение регистров процессора.
2. Оптимизация передачи параметров в процедуры и функции.
3. Оптимизация кода для процессоров, допускающих распараллеливание вычислений.
Другие компоненты классической системы программирования
Интегрированная среда разработки (ИСР).
Продвинутая ИСР
Редакторы текстов.
Редакторы связей. Загрузчики.
...
Полное содержание
Подобные работы:
  1   2   3

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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





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


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

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




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

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

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


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





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

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

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


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


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

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

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

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

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

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

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

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


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


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

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

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


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


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

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

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

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

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

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

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


^ Машинно-независимые оптимизирующие преобразования.


1. Удаление недостижимого кода (задача компилятора найти и убрать его).

Пример: if (1) S1; else S2;  S1; .


^ 2. Оптимизация линейных участков программы.

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

а) Удаление бесполезных присваиваний.

Пример: a=b*c; d=b+c; a=d*c;  d=b+c; a=d*c;


Однако, в следующем фрагменте эта операция уже не бесполезна:

p=&a; a=b*c; d=*p+c; a=d*c;


б) Исключение избыточных вычислений.

Пример: d=d+b*c; a=d+b*c; c=d+b*c;  t=b*c; d=d+t; a=d+t; c=a;


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

Пример: i=2+1; j=6*i+i;  i=3; j=21;


г) Перестановка операций (для дальнейшей свертки или оптимизации вычислений).

Пример: a=2*b*3*c;  a=(2*3)*(b*c);

a=(b+с)+(d+e);  a=(b+(c+(d+e)));


д) Арифметические преобразования (на основе алгебраических и логических тождеств).

Пример: a=b*c+b*d;  a=b*(c+d);

a*1  a, a*0  0, a+0  a .


e) Оптимизация вычисления логических выражений.

Пример: a || b || c || d;  a, если а есть true.

Но! a || f(b) || g(c) не всегда а (при а=true), может быть побочный эффект.


^ 3. Подстановка кода функции вместо ее вызова в объектный код.

Как правило, этот метод применим к очень простым функциям и процедурам, вызываемым непосредственно по адресу, без применения косвенной адресации через таблицы RТTI (Run Time Type Information). Некоторые компиляторы допускают применять его только к функциям, содержащим последовательные вычисления без циклов. Язык С++ позволяет явно указать (inline), для каких функций желательно использовать inline-подстановку.


^ 4. Оптимизация циклов.

а) Вынесение инвариантных вычислений из циклов.


Пример: for (i=1; i<=10; i++) a[i]=b*c*a[i]; 

d=b*c; for (i=1; i<=10; i++) a[i]=d*a[i];


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


Пример: for (i=1; i<=N; i++) a[i]=i*10; 

t=10; i=1; while (i<=N) {a[i]=t; t=t+10; i++;}


Пример: s=10; for (i=1; i<=N; i++) { r=r+f(s); s=s+10;} 

s=10; m=N*10; while (s<=m) {r=r+f(s); s=s+10;}

(избавились от одной индуктивной переменной).


в) Слияние и развертывание циклов.


Пример: for (i=1; i<=N; i++) for (j=1; j<=M; j++) a[i][j]=0; 

k=N*M; for (i=1; i<=k; i++) a[i]=0; (только в объектном коде!)


Развертывание циклов можно выполнить для циклов, кратность выполнения которых известна на этапе компиляции.


Пример: for (i=1; i<=3; i++) a[i]=i; 

a[1]=1; a[2]=2; a[3]=3;

Машинно-зависимые оптимизирующие преобразования.


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


^ 1. Распределение регистров процессора.

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


^ 2. Оптимизация передачи параметров в процедуры и функции.

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

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


^ 3. Оптимизация кода для процессоров, допускающих распараллеливание вычислений.

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

Пример: a+b+c+d+e+f; 

для одного потока обработки данных: ((((a+b)+c)+d)+e)+f;

для двух потоков обработки данных: ((a+b)+c)+((d+e)+f;

для трех потоков обработки данных: (a+b)+(c+d)+(e+f);

^ Другие компоненты классической системы программирования

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


^ Интегрированная среда разработки (ИСР).


Современная ИСР - комплекс программных средств, поддерживающих полный жизненный цикл ПП. Комплекс инструментальных средств, входящих в состав ИСР, иногда называют интегрированным CASE-средством (вспомните первую лекцию).

^ Продвинутая ИСР объединяет в себе следующие компоненты:

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

  • графические средства анализа и проектирования, обеспечивающие создание и редактирование иерархически связанных диаграмм, образующих модели ПП, а также графический пользовательский интерфейс, обеспечивающий взаимодействие с функциями API (Application Program Interface - прикладного программного интерфейса ОС).

  • средства разработки приложений, включая языки 4GL (языки четвертого поколения - four generation languages) и генераторы кодов; 4GL оперируют графическими образами синтаксических структур языка программирования и элементов интерфейса, при этом проектировать и разрабатывать прикладное программное обеспечение может пользователь, не являющийся квалифицированным программистом, зато имеющий представление о предметной области, на работу в которой ориентирована прикладная программа. Описание программы, построенное на основе языков 4GL, затем транслируется в исходный текст и файл описания интерфейса, представляющие собой обычный текст на соответствующем входном языке высокого уровня. С этим текстом уже может работать профессиональный программист-разработчик - корректировать и дополнять его необходимыми функциями. Такой подход позволяет разделить работу проектировщика, отвечающего за общую концепцию всего проекта, дизайнера, отвечающего за внешний вид интерфейса пользователя, и профессионального программиста, отвечающего непосредственно за создание исходного кода;

  • редактор текстов;

  • средства документирования;

  • средства тестирования и отладки;

  • средства управления проектом;

  • средства реинжиниринга (позволяют восстановить логику и структуру программы по ее исходным текстам, с целью модификации или перенесения на другую платформу).

  1   2   3

Скачать 392.84 Kb.
Поиск по сайту:



База данных защищена авторским правом ©dogend.ru 2014
При копировании материала укажите ссылку
обратиться к администрации
Уроки, справочники, рефераты