AOP_Tom1 (1021736), страница 65
Текст из файла (страница 65)
Первая программа трассировки была разработана Стэнлн Гиллом (Ясап!еу С!1!) в 1950 году [см. его интересную статью в журнале Ргосеейп8в ог" сЛе Ноуа! Яос!есу оГЕопдоп, вепев А, 206 (1951), 538-554]. В упомянутой выше книге Уилкса. Уилера и Гилла содержится несколько программ трассировки. Наверное, самая интересная из них — это подпрограмма С-10, написанная Д. Дж. Уилером, в которой предусмотрена возможность, позволяющая приостановить трассировку при входе в библиотечную подпрограмму, выполнить эту подпрограмму на полной скорости, а затем продолжить трассировку.
Информация о программах трассировки довольно редко публикуется в общей компьютерной литературе. Это обусловлено, главным образом, тем, что данные методы по своей природе ориентированы на конкретную машину. Автору известна только одна ранняя работа на эту тему — статья Н. У. Мее1с, "Ап Ехрегппепса! Моп!сот!п8 Ноибпе 1ог сЬе 1ВМ 705", Ргос. !)гевсегп,Уо!пс Сотрисег Сопб (1956), 68-70. В ней обсуждается программа трассировки для машины, на которой было чрезвычайно трудно решить одну задачу.
В настоящее время внимание к программам трассировки сместилось в сторону программ, обеспечивающих выборочный вывод результатов и оценок производительности программы; одна из лучших подобных систем была разработана Э. Сэттерсвейтом (Е.
ЯаССегСЬча1Се) и описана в журнале Яойквге Ргасбсе А Ехрепелсе 2 (1972), 197 — 217. Буферизация первоначально выполнялась аппаратным способом, аналогично тому, как это делалось в программе 1.4.4-(3). Внутренняя буферная область, недо- ступная для программиста, играла роль ячеек 2000 — 2099, и команды 1.4.4-(3) выполнялись неявно и незаметно, когда выдавалась команда ввода. В конце 40-х годов первые программисты (!1ч1ЪАС разработали программные методы буферизации, которые особенно полезны для сортировки (см.
раздел 5.5). Хороший обзор основных принципов В/В, преобладавших в 1952 году, можно найти в Трудах конференции Восточного компьютерного объединения, которая проводилась в 1952 году. В компьютере ОУ8ЕАС ]А!ап 1,. 1,е!пег, 3АСМ 1 (1954), 57-81] была реализована идея непосредственной передачи информации между устройствами ввода- вывода и памятью во время работы программы, а затем прерывания программы по ее завершении. Из существования подобных систем следует, что для них были разработаны алгоритмы буферизации, но подробности не были опубликованы. В первой опубликованной работе о методах буферизации в том смысле, в котором мы их описали, представлен крайне сложный подход к этой проблеме [см.
О. Мое)с, С. 3. Бич(с, пРгобгапппей 1прпыОпсрп! Вп((ег!п8", Ртос. АСМ !Чаа Сопб (1958), рарег 19, и 3АСМ 6 (1959), 145-15Ц. (Должен предупредить читателя о том, что в обеих статьях широко используется местный жаргон, для понимания которого придется потратить некоторое время, но вам помогут в этом другие статьи из журнала ,УАСМ 6.) Система прерывания, которая позволяла осуществлять буферизацию ввода и вывода, была независимо разработана Э.
В. Дейкстрой (Е. Ж. Оц!санга) в 1957 и 1958 годах для компьютера Х вЂ” 1, созданного Б. Ж. Лупстрой (В. 3. Ьоорвсга) и К. С. Шолтеном (С. Я. БсЬо!(еп) ]ем. Сошр. Г. 2 (1959), 39 — 43]. В докторской диссертации Дейкстры, аСопппипгсасюп тн!(Ь ап Ап(оп1а(!с Сошрпсегв * (1958), обсуждаются методы буферизации, которые в данном случае были рассчитаны на очень длинные кольца буферов, в то время как в программах рассматривался, в основном, В/В на перфоленты и терминал. В каждом буфере содержался либо один символ, либо одно число. Впоследствии Дейкстра развил эти идеи и пришел к важному общему понятию семафоров, которые лежат в основе управления параллельными процессами любого вцпа, а не только вводом-выводом ]ем.
Ргодгатпттд Ьап8иаяев, ей. Ьу Р. Сеппув (Асайепйс Ргевв, 1968), 43 — 112; В1Т 8 (1968), 174 — 186; Асса ГпГогшабса 1 (1971), 115-138]. В статье 1)ан!й Е. Рег8пвоп, к1прщ-Оп!рис Вп(Гег!п8 апй гО(сТВА."ч", .ГАСМ 7 (1960), 1 — 9, рассматриваются буферные кольца и приводится подробное описание простой буферизации для многих устройств одновременно. Как представляется, примерно 1 000 команд — зто разумный верхний предел сложности задач.
— ГЕРМАН ГОЛДСТАЙН (НЕРМАй ЕОьОЗт!йЕ) и джОн ФОн неймАн (зОнй чОй йецмАйй) (!946) "Связь с помощью автоматического компьютера", — Прим. перев. ГЛАВА г ИНФОРМАЦИОННЫЕ СТРУКТУРЫ Нет, не увижу, это ясно, Поэиы, депеза ппекрзсней — Д>КОЙС КИЛМЕР (ЭО!СЕ КШМЕП) (1913) (ПеРевол Л. МакаРовой) Ах, я с таблицы паияти иоей Все суетные записи сотпу. — пзилет (зкт й сцена 5, строка 9в) (перевод м. лозинского) 2.1. ВВЕДЕНИЕ Пгогглммы овычно оперируют информацией, которая содержится в таблицах. В большинстве случаев эти таблицы представляют собой не просто бесформенную массу численных значений, а элементы данных с важными сгпрцкгпурными взаимосвлзямц.
В простейшем виде таблица может выглядеть так, как простой линейный список элементов, а сведения о ее структурных свойствах можно получить, ответив на следующие вопросы. Какой элемент располагается в списке первым? Какой погледним? Какие элементы предшествуют данному элементу, а какие следуют за ним? Сколько элементов содержится в списке? Ответив на такие вопросы, даже в этом простом случае можно получить богатую информацию о структуре данных (см. раздел 2.2).
В более сложных случаях таблица может иметь структуру двумерного массива (т. е. матрицы или решетки, состоящей из строк и столбцов) или даже и-мерного массива для п больше 2, древовидную структуру (ггее зггисгиге), которая представляет иерархические или разветвляющиеся связи, либо такую сложную многосвязную структуру (шп1$!11п)сей зсгпсгцге) с большим количеством соединений, которая устроена, как человеческий мозг. Для правильного использования компьютера необходимо хорошо знать структурные взаимосвязи между данными, основные методы представления структур внутри компьютера, а также методы работы с ними. В данной главе приводятся наиболее важные сведения об информационных структурах: статические и динамические свойства структур разных типов, средства выделения памяти для хранения и представления структурированных данных, эффективные алгоритмы для создания, изменения, удаления информации о структуре данных, а также для доступа к ней.
В ходе изучения материала на нескольких важных примерах будет проиллюстрировано применение этих методов для решения широкого круга задач. В примерах будут рассмотрены топологическая сортировка, арифметикц многочленов, моделирование дискретных систем, работа с разреженными матрицами, манипулирование алгебраическими формулами, а также создание компиляторов пй операционных систем. Основное внимание здесь будет уделено представлению структуры внушри компьютера; ее преобразование межлу внешними и внутренними представлениями будет подробно рассмотрено в главах 9 и 10. Большая часть представленного здесь материала часто называется обработкой списков, особенно с тех пор как было создано достаточно систем программирования, например ЫЯР, предназначенных специально для работы со структурами общего типа под названием Списки.
(Далее в этой главе слово "Список" с прописной начальной буквой будет использоваться для обозначения отдельного типа структуры, которая более подобно рассматривается в разделе 2.3.5.) Хотя в большинстве случаев системы обработки Списков очень полезны, они часто накладывают на работу программиста не всегда оправданные ограничения. В собственных программах обычно эффективнее непосредственно использовать предлагаемые в этой главе методы, подгоняя для конкретного приложения формат данных и алгоритмы их обработки.
Многие разработчики программного обеспечения все еще считают, что методы обработки Списков очень сложны (и потому вынуждены использовать интерпретаторы сторонних разработчиков или уже готовые наборы процедур) и что обработка Списков может выполняться лишь некоторым строго определенным способом. Как будет показано ниже, ничего сверхъестественного, загадочного или трудного в работе со сложными структурами нет. Приведенные здесь методы являются частью арсенала каждого программиста, и их можно использовать при создании программ на языке ассемблера или на таких алгебраических языках, как РОВТВЛ1ч', С и 3ага.
Методы работы с информационными структурами будут проиллюстрированы здесь на примере компьютера й1Х. Читателю, которого не интересует подробная структура программ для компьютера й1Х, следует изучить хотя бы способы, с помощью которых информация о структуре представляется в памяти компьютера М1Х. Здесь важно определиться с терминами и обозначениями, которые будут довольно часто использоваться. Информация в таблице состоит из набора узлов (повез); некоторые авторы называют их записями (гесогс1э), объектами (епмбеа) или цепочками (Ьеабз) . Иногда вместо термина "узел" будут использоваться термины "предмет" и "элемент".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
