Сист. прогр. Ч2 (Лекции по СПО), страница 9

1. Постановка задачи.

2. Определение структуры данных.

3. Определение формата структур данных.

4. Выбор алгоритма.

5. Обеспечение модульности алгоритма.

6. Повторение шагов с 1-го по 5-й для каждого модуля.

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

ЗАКЛЮЧЕНИЕ

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

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

Поясним это на примере. Рассмотрим работу ассемблера на вычислительной машине Системы 360, модель 40, которая имеет типичное время выполнения команды 12 микросекунд (т. е. выполняет в среднем 83000 команд в секунду). Предположим, что мы хотим оттранслировать довольно большую исходную программу на языке ассемблера {из 5000 карт), которая содержит около 2000 символов. В среднем каждая карта исходной программы имеет по крайней мере одну символьную ссылку в поле операнда. Вычислим время, затрачиваемое на поиск символов в таблице.

Если используется линейный поиск и он запрограммирован, то для каждого цикла поиска будет выполняться пять команд; таким образом, каждая итерация будет выполняться за время около 5 X 12 = 60 мкс. Число итераций для каждого поиска будет приблизительно равно 1000, половине от общего количества символов в таблице. Наконец потребуется приблизительно один поиск для каждой из 5000 карт, Таким образом, общее время, затрачиваемое на поиск, можно оценить следующим образом:

Общее время = (количество поисков) X

X (число итераций на поиск)Х (время итерации) =

= 300 секунд = 5 минут

С другой стороны, если применить двоичный поиск, то среднее число итераций на поиск составит только log2 (2000) — 1 ≈ 10 сек.

14. ЗАГРУЗЧИКИ

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

Лрограммы, загруженные в помять и, готовые к выполнению

Рис. 14.1. Общая схема загрузки.

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

В частности, загрузчик должен выполнять следующие функции:

1. Выделение места для программ в основной памяти (распределение) .

2. Разрешение символических ссылок между объектными программами (связывание).

3. Настройка всех величин в программе, зависящих от физических адресов, таких, например, как адресные константы, в соответствии с адресами выделенной для программы область памяти (перемещение).

4. Фактическое размещение машинных команд и данных в памяти (загрузка).

В большинстве примеров этого раздела за основу взяты ассемблер и загрузчик Системы 370. Несколько других рассматриваемых схем загрузки относятся к ЭВМ с системой команд, использующей непосредственную адресацию и фиксированный формат, таким, как IBM 7094, IBM 1130, UNIVAC 1108 и GE 635. Для простоты предполагается, что ввод в систему осуществляется с перфокарт. Само собой разумеется, что с равным правом можно было бы говорить о вводе образов перфокарт с накопителя на магнитной ленте или с других внешних запоминающих устройств.

СХЕМЫ ЗАГРУЗКИ

В этом разделе будут рассмотрены различные схемы реализации четырех перечисленных выше функций загрузчика. Для удобства введем термин сегмент, под чем подразумевается информация, рассматриваемая как единое целое, независимо от того, идет ли речь о программе или о данных. Обычно сегментом является отдельная исходная или объектная программа; однако, с помощью псевдокоманды ассемблера CSECT (программная секция), оператора COMMON в ФОРТРАНе или атрибута EXTERNAL STATIC в ПЛ/1 можно задать исходную программу, состоящую из нескольких программных сегментов и сегментов данных..

ЗАГРУЗЧИКИ ТИПА «КОМПИЛЯЦИЯ-ВЫПОЛНЕНИЕ»

Одним из возможных способов выполнения функций загрузчика может быть такая организация работы ассемблера, при которой ассемблер, работая в одной части памяти, помещает машинные команды и данные по мере ассемблирования непосредственно в выделенные для них ячейки памяти (рис. 14.2). После завершения компиляции ассемблер передает управление в точку входа полученной программы. Это очень простое решение, позволяющее обойтись без каких-либо дополнительных процедур. Оно использовано в компиляторе WATFOR с ФОРТРАНа и некоторых других языковых процессорах.

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

Однако эта схема имеет ряд очевидных недостатков. Во-первых, некоторая часть памяти не может быть использована, так как занятая ассемблером память недоступна для объектной программы. Во-вторых, при каждом новом прогоне приходится заново транслировать (ассемблировать) программу пользователя. В-третьих, оказывается весьма затруднительным организовать совместную работу нескольких сегментов программы, особенно в том случае, если исходные программы написаны на разных языках, например одна подпрограмма на языке ассемблера, а другая на ФОРТРАНе или ПЛ/1.

Транслятор типа компиляция -выполнение

Программа, загруженная в память

Ассемблер

Память

Рис. 14.2. Схема загрузки типа «компиляция-выполнение».

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

ОБЩАЯ СХЕМА ЗАГРУЗКИ

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

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

Транслятор

Объектная программа 1

Объектные программы готовые к выполне- нию

Загрузчик

Загрузчик

Рис. 14.3. Общая схема загрузки.

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

АБСОЛЮТНЫЕ ЗАГРУЗЧИКИ

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

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

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

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

1. Распределение - программистом;

2. Связывание - программистом;

3. Перемещение- ассемблером;

4. Загрузка - загрузчиком.

СВЯЗЫВАНИЕ ПОДПРОГРАММ

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

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

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

MAIN START

EXTRN SUBROUT

……………..

L I5,=A(SUBROUT) Вызов
BALR 14,15 подпрограммы SUBROUT

…………..

END

В приведенной последовательности сначала объявляется, что SUBROUT представляет собой внешний символ. Это означает, что в данной программе есть обращения к этому символу, но он в этой программе не определен. Команда загрузки загружает адрес подпрограммы SUBROUT в регистр 15. В результате выполнения команды BALR происходит переход по адресу, определяемому содержимым регистра 15, а именно переход к под­программе SUBROUT, причем адрес команды, следующей за командой BALR, помещается в регистр 14. В большинстве ассемблеров можно воспользоваться макрокомандой CALL SUBROUT, которая транслируется в приведенную выше последовательность команд.

Так как вызывающая и вызываемая программы должны работать согласованно, появляется необходимость в определенных соглашениях по программированию, В Системе 360 принято, что регистр 15 используется для связи программ и как базовый регистр. Обратите внимание на то, что в рассмотренном выше примере вызывающая программа загрузила адрес вызываемой подпрограммы в регистр 15. В связи с этим в вызываемой программе отпадает необходимость загрузки базового регистра. Регистр 14 содержит адрес возврата в вызывающую программу. Программист не должен использовать регистр 14 в подпрограмме, если не обеспечено сохранение его содержимого и последующее его восстановление перед возвратом управления вызывающей программе. Типичная последовательность команд подпрограммы имеет следующий вид;