Л.Е. Карпов - Системы программирования (1114903), страница 15

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

Текст из файла (страница 15)

Единственной трудностью приданном подходе является выбор оптимального размера элементарного блока.Второй вариант обработки явных запросов пользователей основан на болеегибком подходе, при котором размер блоков не фиксируется заранее, а выбирается наоснове параметров запроса и хранится в самом блоке:свободнозанятоЭто позволяет оставить почти без изменения работу системы при захватепамяти, но значительно усложняет ее при освобождении, а особенно при повторномвыделении, которое может потребовать склеивания смежных блоков, а иногда иуплотнения занятых участков.

Сложность процесса уплотнения связана с55необходимостью модифицировать все указатели на объекты, размещенные вперемещаемых блоках.Неявное освобождение памяти проводится в случае автоматическогоуправления распределением памяти, которое выполняет компилятор и программысистемной поддержки в отсутствии явных операторов управления памятью впрограмме пользователя. Существенную роль в процессах освобождения и повторныхзахватах памяти начинает играть процедура “сборки мусора”, то есть поиска ранееосвобожденных участков памяти, которые можно использовать повторно. Если всхемах, выбираемых для обработки явных запросов, практически не возникает никакихнакладных расходов, то при неявном управлении памятью без больших накладныхрасходов памяти обойтись не удается.Выделяемый блок памяти уже не может состоять из фрагмента, нужногопользователю и (может быть) дополнительного небольшого расхода на хранениеразмера блока.

При управлении неявных запросов памяти в состав выделяемого блокаприходится дополнительно включать специальный счетчик числа указателей,связанных с данным блоком, либо специальный признак занятости блока (“пометку”):размер данного блокапамятисчетчик ссылок илипометки занятостиуказатели,ссылающиесяна данный блокпамять, выделяемаяпо запросуВ блок обычно включается также полный список всех указателей, связанных собъектами данного блока. Работа с блоками, выделенными и освобождаемыми понеявным запросам, проводится по-разному, в зависимости от выбираемого алгоритмаопределения занятости блока.Определение занятости блока с помощью счетчика ссылок основано напостоянном контроле числа указателей, имеющихся в программе и содержащих ссылкина объекты, размещенные в данном блоке памяти.

Такой подход связан с контролемвсех операторов присваивания видаp = q;где p и q – указатели на некоторые динамически созданные объекты. Передвыполнением присваивания значение счетчика ссылок блока, на который ссылаетсяуказатель p, уменьшается единицу, одновременно увеличивается на 1 значениесчетчика ссылок блока, на который ссылается указатель q. Только после этого можновыполнять само присваивание.

Блок считается свободным, если значение его счетчикассылок стало равным нулю. Проблемой при таком подходе является обработканедостижимых циклических ссылок:56При работе программ возможно возникновение сложных списочных структур,создающих закольцованные последовательности ссылок. Такие ссылки учитываютсяпри подсчете значений счетчиков ссылок блоков памяти, но сами структуры могутреально оказаться недостижимыми в программе, так как ни один из указателей, невходящих в созданное кольцо (внешних по отношению к этому кольцу), не ссылаетсяни на один из элементов списочного кольца. Такие недостижимые циклические ссылкистановятся препятствием для освобождения ставшей ненужной памяти и создаютреальные проблемы для систем управления памятью.Определение занятости блоков памяти с помощью пометок позволяетизбежать обозначенной проблемы циклических ссылок и необходимости отслеживаниявсех присваиваний указателям за счет организации сложного и затратного механизма“сборки мусора”.

Этот механизм включается в момент, когда перед системойуправления памяти возникает необходимость выделить фрагмент памяти такогоразмера, который невозможно обеспечить, не проведя уплотнения занятых блоковпамяти. Алгоритм работает следующим образом:••••все ранее выделявшиеся блоки памяти помечаются как свободные;анализируются все указатели – переменные программы и помечаютсязанятыми все блоки, на которые они ссылаются;итеративно анализируются все указатели, хранящиеся в виде значений полейобъектов, размещенных в блоках, помеченных, как занятые; процессостанавливается, когда новые занятые блоки перестают возникать;все недостижимые по указателям блоки памяти остаются свободными,занятая ими память может быть уплотнена; одновременно с уплотнениемзанятых блоков осуществляется модификация значений действующихуказателей.Процесс “сборки мусора” запускается системой управления памятью впроизвольные моменты времени, что может влиять на процесс решения сразу многихзадач, работающих в вычислительной системе в одно и то же время.

Эффективнаяреализация этого процесса является одной из важнейших характеристик как системпрограммирования, так и программ системной поддержки.3.3.6. Генерация кодаЗавершающей стадией работы компилятора является генерация кода (команд,констант и т. д.) объектной программы. Генератор кода получает на входпромежуточное представление исходной программы и вырабатывает эквивалентнуюобъектную программу, используя для этой цели всю информацию, накопленную кэтому моменту в информационных таблицах компилятора.Работа генератора не зависит от того, имеется ли перед фазой генерациидополнительная фаза оптимизации, или она отсутствует. Математически проблемагенерации эффективной объектной программы является неразрешимой, но на практике57применяются достаточно эффективные эвристические подходы, дающие хорошиерезультаты, хотя и не абсолютно оптимальные.На вход генератора кода поступает внутреннее, промежуточное представлениекомпилируемой программы, полученное на начальных стадиях компиляции,осуществляющих анализ исходной программы и построение информационных таблицкомпилятора.

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

Одно из самых существенных предположений, которые делаютсяпри разработке генераторов кода, состоит в том, в поступающем на его входвнутреннем представлении программы отсутствуют ошибки (хотя иногда генерациякода выполняется параллельно с семантическим анализом программ).Реальные компиляторы готовят результаты своего труда в виде объектныхпрограмм, для кодирования которых могут использоваться такие виды языков:••••машинные коды в абсолютных адресах;перемещаемый машинный код;язык ассемблера объектной машины;другой язык программирования высокого уровня.Абсолютный машинный язык имеет свои пр еимущества в том, что прогр аммына таком языке могут помещаться в фиксированные места памяти машины инемедленно выполняться. Такие системы обычно используются в целях обученияязыкам и методам программирования.

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

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

Эта же технология используется для быстрого созданияпрототипа компилятора или при проведении процедуры “раскрутки”, когда сначаласоздается компилятор для некоторого языкового ядра (ограниченного варианта языка),а затем последовательными переходами от версии к версии создается сериякомпиляторов для все более и более полных вариантов языка. Например, язык Фортрансвоим стандартом определен через ядро и дополнительные слои, которые можноотключать при компиляции, борясь за эффективность программ, но (может быть) вущерб удобству программирования.Любой генератор кода, независимо от формы внутреннего представленияпрограмм в компиляторе и вида выходного представления результатов компиляциидолжен в своей работе решить две главные задачи:••выполнить распределение памяти для объектов данных и фрагментовкомпилируемой программы,выполнить поиск и подбор семантических эквивалентов конструкциямвнутреннего представления программ.Важной дополнительной функцией генератора кода в таком процессе, заметноусложняющей весь процесс генерации в целом, является проведение одновременно сгенерацией поиска стандартных последовательностей операторов по некоторымшаблонам и локальной оптимизации потока формируемых команд.Поиск по шаблонам помогает обнаруживать в программах некоторые частоиспользуемые ресурсоемкие последовательности операторов, для которых вконкретной аппаратуре объектной машины могут иметься решения, существенноповышающие эффективность их выполнения.

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

Список файлов книги