Книга известного американского специалиста в области программирования представляет собой учебное пособие по системному программированию. Она охватывает широкий круг вопросов применениями проектирования ассемблеров, макрогенераторов, за-грузчикоа, компиляторов и управляющих программ операционных систем ЭВМ.
Книга написана автором согласно рекомендациям Ассоциации вычислительных машин для учебных курсов по данной тематике. Изложение ведется с использованием языка ПЛ/1 и прин-инпов построения Системы IBM 360 и 370 и сопровождается большим числом удачно подобранных примеров и задач.
Книга предназначена как для специалистов, так и для самостоятельно изучающих современное программирование. Методические достоинства делают ее ценным учебным пособием для студентов университетов и вузов, специализирующихся в области программирования.
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
.За последнее время издано немало книг, посвященных про-, граммному обеспечению современных вычислительных машин; Большинство из них содержит описание конкретных систем или' отдельных частей программного обеспечения. В предлагаемой вниманию читателя книге Дж. Донована «Системное програм-; мирование» рассматриваются основные вопросы системного* программирования, т. е. вопросы проектирования программного обеспечения. Автор стремится выявить те общие особенности! программного обеспечения и методов его проектирования, которые применимы к самым разным компонентам, будь то тр-анслЗк торы с языков программирования высокого уровня, ассемблеры^ загрузчики или управляющие программы операционных систем!; Некоторые из приведенных примеров построены на основе Системы 360 и 370 фирмы IBM и языка ПЛ/1. При описании современных методов управления памятью и информацией используются сведения о системе MULTICS. Это, однако, нисколько не уменьшает общности .изложения, которое в основном не зависит от специфических решений, принятых в тех или иных конкретных системах.
Естественно, что при столь широком круге рассматриваемых вопросов автор в рамках одной книги не мог, да и не ставил перед собой цели исчерпывающе изложить детали проектирования программного обеспечения, между тем в постановочном плане ему удалось осветить многие важные проблемы системного программирования. Поэтому книга может служить хорошим введением в предмет, побуждающим к более углубленному самостоятельному изучению. Для читателей, желающих подробно изучить рассматриваемые вопросы, автор приводит обширную библиографию. ••;"
Книга построена как учебник и содержит большое количе-, ство упражнений, подобранных таким образом, чтобы научить, самостоятельной работе. В упражнениях приведено много инфори. мации, существенно дополняющей основной текст. , Книга представляет интерес для преподавателей, аспиранте^ и студентов и может быть полезна специалистам в области Сй4 стемного и прикладного программирования.
Главы 3, 4, 6, 7, 8 переведены С. Н. Флоренцевым.
Л. Д. Райков
ОГЛАВЛЕНИЕ
Предисловие редактора перевода................ о-
Из предисловия автора ...... ........ ..... 6
Глава 1. ВВЕДЕНИЕ.................... II
1.1. Машинная структура................. 12
1.2. Эволюция компонентов систем программирования....... 14
1.2.1. Ассемблеры . . ... . . . . . . . . . . • •• • • 14
1.2.2. Загрузчики................... 15
1.2.3. Макроояределеиия ......".......... 17
1.2.4. Компиляторы................... 18-
1.2.5. Формальные системы................ 18
1.3. Эволюция операционных систем ........... 18-
1.4. Операционная система с точки зрения пользователя. Функции системы......................
1.5. Операционная система с точки зрения пользователя. Язык управ-
ления заданиями .................. 22'
1.6. Операционная система с точки зрения пользователя. Услуги. . .25
1.7. Резюме...................... 26-
Упражнения...................... 26-
Глава 2. СТРУКТУРА МАШИНЫ, МАШИННЫЙ ЯЗЫК И ЯЗЫК
АССЕМБЛЕРА . '.................... . 32
2.1. Общая структура машины ................ 32"
2.1.1. Общий подход к новой машине............ 35
2.1.2. Машинная структура Системы 360 и 370 ........ 36
. 2.2. Машинный язык................... 48
2.2.1. Программирование без циклов............ 49
2.2.2. Модификация адресов непосредственно в командах . . . . 51
2.2.3. Модификация адресов с использованием индексных регистров 53 2;2.4. Циклы.................... . 54
2.3. Язык ассемблера . . . _................ 56 •
2.3.1. Программа на языке ассемблера . ,......... 57
2.3.2. Пример с использованием литералов.......... 59
2.4. Резюме........................ 61
,- Упражнения...................... 62'
Глава 3. АССЕМБЛЕРЫ................... 73
3.1. Общая процедура проектирования............ 74
3.2. Проектирование ассемблера.............. 74-
3.2.1. Постановка задачи................ -^ -
3.2.2. Структура данных.......,.....• • . . 7Т *
3.2.3. Формат баз данных................81
3.2.4. Алгоритм.................... 88 *
3.2.5. Обеспечение модульности алгоритма.......... 94 •
3.3. Обработка таблиц: поиск и сортировка.......... 9ft '
3.3.1. Линейный поиск................. 97
. 3.3.2. Двоичный поиск................ . 93 •
3.3.3. Сортировка . . .*................ 101^
3.3.3.1. Обменная сортировка.............. 101 '
3.3.3.2. Сортировка Шелла............... 10$
3.3.3.3. Сортировка поразрядным группированием...... 104
3.3.3.4. Поразрядно-обменная сортировка.......... !05
3.3.3.5. Сортировка вычислением адреса.......... 107
3.3.3.6. Сравнение сортировок.............. 109 {
3.3.4. Поиск методом прямого доступа......'..... 110',
3.4. Резюме...................... 114 >
3.5. Заключение...................- ... 114
Упражнения...................... 11(5
Слава 4. МАКРОЯЗЫК И МАКРОПРОЦЕССОР......... 131
4.1. Макрокоманды ................... '32
4.2. Особенности макроязыка............... 134
4.2.1. Операнды макрокоманд.............. 134
4.2.2. Условное макрорасширение............. 1§8'
4.2.3. Макровызовы внутри макроопределений ........ 140
v 4.2.4. Макрокоманды, определяющие макроопределения..... ,142*
4.3. Реализация..................... 143
4.3.1. Ограниченная реализация: двупросмотровый алгоритм . . . 144
4.3.2. Однопросмотровый алгоритм.......'.,.... 152
4.3.3. Реализация макровызовов внутри макроопределений . . . 156
4.3.4. Реализация внутри ассемблера............ 163
4.4. Резюме....................... 165
Упражнения . ,..................... 165
Глава 5. ЗАГРУЗЧИКИ................... 172
5.1. Схе*мы загрузки.................• • I73V
5.1.1. Загрузчики типа «компиляция-выполнение»......• '73.
5.1.2. Общая схема загрузки............... 174'
5.1.3. Абсолютные загрузчики.............. '75 ^
5.1.4. Связывание подпрограмм.............• '77;
5.1.5. Настраивающие загрузчики............• '^0
5.1.6. Непосредственно связывающие загрузчики ....... •;
5.1.7. Другие схемы загрузки — объединители, связывающие загруз- ; чики, перекрывающие загрузчики, динамические объединители 189-
194
5.2. Проектирование абсолютного загрузчика.........
5.3. Проектирование непосредственно связывающего загрузчика . . 19э
5.3.1. Постановка задачи.....,.......• . . .
5.3.2. Определение структур данных......•.....
5.3.3. Формат баз данных..............• •
5.3.4. Алгоритм....................
5.4. Резюме......................
215 Упражнения.....................
Глава 6. ЯЗЫКИ ПРОГРАММИРОВАНИЯ.......... ~. 226-
оой
6.1. Значение языков высокого уровня............^iv>
OOQ.
6.2. Свойства языка высокого уровня...........• **у
6.3. Типы и структуры данных......• • •......235-
6.3.1. Символьная строка................ 23!
6.3.2. Строка битов.................. • 23'^
6.3.3. Структуры данных................23J
6.4. Распределение памяти и область действия имен.......23&
6.4.1. Типы памяти...................23
6.5. Гибкость доступа к данным..............23S
6.5.1. Указатели....................235
6.5.2. Переменные типа метки и массивы меток........238-
6.6. Функциональная модульность..............239-
6.6.1. Процедуры................; . . 24)
6.6.2. Рекурсия .................... 24!)
6.7. Асинхронное выполнение операций............240
6.7.1. Условия.................... 241
6.7.2. Сигналы....................242-
6.7.3. Мультизадачный режим............. . 243
6.8. Расширяемость и макрокоманды времени компиляции ( .... 244
6.9. Разное...................... 244
6.10. Резюме...................... 244
Упражнения...................... 245-
Глава 7. ФОРМАЛЬНЫЕ СИСТЕМЫ И ЯЗЫКИ ПРОГРАММИРОВАНИЯ. ВВЕДЕНИЕ ................... .
7.1. Использование формальных систем в языках программирования
7.1.1. Описание языка .................257
7.1.2. Синтаксически-ориентированные компиляторы......257
7.1.3. Изучение сложности структуры............258
7.1.4. Анализ структуры..................258
7.2. Формальное описание языка..............259
7.2.1. Введение в формализацию.............239/
7.2.2. Построение формального описания..........261
7.3. Формальные грамматики.........-.....}
7.3.1. Примеры формальных грамматик........ . , «<
7.3.2. Вывод предложений................'
7.5.3. Сентенциальные формы и предложения......../
7.4. Иерархия языков.................. щ
7.5* Форма Бэкуса — Наура или бэкусова нормальная форма (БНФ); 7.6.' Канонические системы............ . . . ^
7.6.1. Пример: Описание синтаксиса............,'
7.6.2. Описание трансляции............., j.
7.6.3. Алгоритм распознавания и трансляции.....•• . . . „
7.7. Канонические системы и формальные системы.......
7.8. Резюме ......."..............„
Упражнения ..... ........
Глава 8. КОМПИЛЯТОРЫ Часть 1
8.1. Постановка задачи . .................
8.1.1. Задача № 1 — распознавание базовых элементов . . . . .
8.1.2. Задячг № 2 — распознавание синтаксических единиц и интерпретация их значений .....' ..........
^8.1.3. Промежуточная форма ...............
8.1.3.1. Арифметические операторы . . . ." ........
8.1.3.2. Неарифметические операторы ........... ,
8.1.3.3. Неисполняемые операторы ... ........ >
8.1.4. Задача № 3 — распределение, памяти .........
8.1.5. Задача № 4 — генерация 'кода .... ....... ,,(>
8.1.5.1. Оптимизация (машинно-независимая) ........
8.1.5.2. Оптимизация (машинно-зависимая) . ..... . . ,;
8.1.5.3. Фаза сборки ........ . ........ Ч
8.1.6. Общая схема компилятора ... ........ *', т'
Часть 2
•> ( ч*
8.2. Фазы компилятора ........ ........ ', • ч)
8.2.1. Лексическая фаза ............. . .'1
8.2.1.1. Задачи ..... . V . . . . . ..... / V|
8.2.1.2. Базы данных . . . ..... ........
85.1.3. Алгоритм ".-........ ..... . . *,• *-
8.2.1.4. Пример .......... ....... j
8,22. Синтаксическая фаза ........ ..... >,
8.2.2.1. Базы данных ............
8.2.2.2. Алгоритм ... . . .... . . . ......
8.2.2.3. Пример ....." ...............
8.2.3. Фаза интерпретаций ...... ......'
8.2.3.1. Базы данных ....... г ......... 321
8.2.3.2. Алгоритм....................323
8.2.3.3. Пример................'... 323
8.2.4. Оптимизация ................... 327
8.2.4.1. Базы Данных ................. 331
8.2.4.2. Алгоритм ........^...........,-332
8.2.5. Распределение памяти................336-
8.2.5.1. Базы данных................. 336
8.2.5.2. Алгоритм...........•.......337
8.2.6. Генерация кода...................341
8.2.6.1. Базы данных................. 341
8.2.6.2. Алгоритм . . ;................ . 342
8.2.6.2.1. Простая машинно-зависимая оптимизация ..... 342
' 8.2.6.2.2. Простой алгоритм машинно-зависимой оптимизации . 343
8.2.6.2.3. Оптимизация группы регистров........ . 346
8.2.6.2.4. Практические рекомендации . . . .......348
8.2.7. Фаза сборки................... 349
8.2.7.1. Базы данных................. 349
' 8.2.7.2. Алгоритм...................349
8.2.8. Просмотры компилятора.............. . 350
8.2.9. Предварительное замечание..............352
Часть 3
8.3. Структуры данных . . . . . . . . . . . .......352
8.3.1. Постановка задачи................ 352
8.3.2. Реализация...................357
8.4. Рекурсии, обращения и операторы возврата........358
8.5. Типы памяти — использование............. 363
8:5.1. Статическая память................364
8.5.2. Автоматическая память...............364
8.5.3. Внутренняя управляемая память........... 365
8.5.4. Внешняя управляемая память............ 365
8.5.5. Базированная память..............' . 366
8.6. Реализация.................... 366
8.6.1. Статическая память................ 366
8:6.2. Автоматическая память............... 367
8.6.3. Управляемая и базированная .память.........368
8.7. Блочная структура . . . . . . . '......... . / . 369
8.7.1. Доступ к информации при блочной структуре ...... 371
,- 8.7.2. Распределение памяти для блочной структуры .. .... . 37л)
":( 8.8. Нелокальные операторы перехода.............376
\"-' 8.9. Прерывания . . . . . . . . . . . ." . ... . . . . 377
t 8.10. Указатели........ . . . . .~ . . . . . . . . 377
8.11, Резюме...................... ?78
Упражнения.......... ........... 379
Глава 9. ОПЕРАЦИОННЫЕ СИСТЕМЫ ...... - . . 388
9.1. Программирование ввода-вывода: мультипроцессорные системы и механизмы прерываний................389
9.1.1. Эволюция мультипроцессорных систем.........3S9
9. .2. Программирование ввода-вывода........... 392
9. .3. Структура процессора ввода-вывода.......... 392
9. .4. Примеры программ ввода-вывода............ -395
9. .5. Связь между центральным процессором и каналом .... 397
9. .6. Структура и обработка прерываний.......... 399
9.1.7. Пример обработки прерывания от ввода-вывода..... 402
9.1.8. Мультипроцессорные системы............ 406
9.2. Управление памятью ................. 407
9.2.1. Одиночное непрерывное распред'еление........-. 407
9.2.2. Распределение разделами.............. 403
9.2.3. Распределение перемещаемыми разделами....... 411
9.2.4. Распределение страницами ............. 415
9.2.5. Распределение страницами по запросам........ 418
9.2.6. Распределение сегментами ............. 421
9.2.7. Сегментно-страничное распределение *......... . 429
9.3. Управление процессорами............... 431
9.3.1. Планировщик ..................433
9.3.2. Регулировщик..................436
9.3.3. Условие соперничества...............437
9.3.4. Клинч.....................438
9.3.5. Мультипроцессорные системы............439
•9.4. Управление устройствами...............445
9.4.1. Характеристики устройств..............445
9.4.2. Методы управления устройствами...........449
•9.5. Управление информацией...............452
9.5.1. Развитие файловых систем............. 453
9.5.2. Структура обобщенной файловой системы........ 455
9.5.3. Пример файловой системы............. 456
9.5.4. Средства обобщенной файловой системы........ 460
9.5.5. Еще раз об общей модели файловой системы...... 470
9.5.6. Сегментация................... 472
9.5.7. Файловая система MULTICS и общая модель...... 480
9.6. Резюме ...................... 480
Упражнения..................... . 481
Глава 10. БИБЛИОГРАФИЯ И РЕКОМЕНДАЦИИ ДЛЯ ДАЛЬНЕЙШЕГО ЧТЕНИЯ................... . 491
Приложение А........................502
Приложение Б....................... 526
Предметный указатель....................532
Цена: 300руб.
