Сист. прогр. Ч2 (Методические указания к выполнению лабораторных работ по СПО), страница 9
Описание файла
Файл "Сист. прогр. Ч2" внутри архива находится в следующих папках: Методические указания к выполнению лабораторных работ по СПО, сист прогр лабы. Документ из архива "Методические указания к выполнению лабораторных работ по СПО", который расположен в категории "". Всё это находится в предмете "операционные системы" из 7 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "операционные системы" в общих файлах.
Онлайн просмотр документа "Сист. прогр. Ч2"
Текст 9 страницы из документа "Сист. прогр. Ч2"
величины
Ниже приведены сравнительные времена для упакованной таблицы, использующей поразрядно-обменную сортировку и двоичный поиск;
Количество попыток для за- Ts = М + М х Iog2 (M) = 55
полнения и сортировки
Среднее число проверок на Тр = Iog2 (М) = 3,58
обнаружение величины
Среднее число проверок на Тп= Iog2 (M) =3,58
отсутствие величины
Таким образом, оказывается, что метод открытой адресации имеет значительное преимущество в скорости, но платит за это тем, что использует таблицу, размер которой приблизительно на 50 процентов больше. Более того, таблица не может быть уплотнена после ее первоначального заполнения, а выделенная область не может быть легко разделена между несколькими таблицами. Последний и очень серьезный недостаток состоит в том, что очень трудно удалить какую-либо величину из таблицы - нельзя просто обнулить эту ячейку, поскольку это может нарушить цепочку адресов.
Интересно рассмотреть ожидаемое время проверок для методов со случайными элементами. Более простым методом для оценки является метод случайного элемента с повторениями. Будем считать, что таблица из N позиций с К— 1 элементами уже заполнена. Определяем плотность р = (К— 1)/N.
Число проверок для запоминания К-го элемента;
Lk = 1 / ( 1-р)
Число проверок для поиска:
Tp = 1/p x loge (1/ (1 — р))
Эти формулы очень интересны и хорошо иллюстрируют зависимость между временем поиска и плотностью таблицы.
Для случая открытой адресации оценки существенно отличаются от приведенных выше. Когда таблица становится плотнее, вероятность появления длинных строк возрастает так, что требуется больше проверок. Можно показать, что число проверок на обнаружение в этом случае приблизительно равно
Tp (p) = 1 + p/2 x 1/ (1 — р)
-а число проверок на отсутствие величины в таблице приблизительно равно
Tn (p) = 1/ (1 — р)
Для плотности р = 12/17 это дает:
Tp = 1 + 6/5 = 2.2
Tn = 17/5 = 3.4
что хорошо согласуется с результатами рассмотренного примера. ГЕНЕРИРОВАНИЕ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ
Существует много алгоритмов генерирования псевдослучайных чисел, причем одним из наиболее часто используемых является метод степенных вычетов. Мы отсылаем читателя к книге Хэмминга (Hamming) [2] или Кнута [3].
РЕЗЮМЕ
Мы рассмотрели структуру двупросмотрового ассемблера. Во время первого просмотра определялись значения символов, а во втором просмотре генерировалась объектная программа. При этом подчеркивалось, что в процессе проектирования ассемблера или любого другого компонента программного обеспечения выделяется шесть основных этапов:
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
Объектные программы готовые к выполне- нию
Загрузчик
Загрузчик