Библиотека
ИБЕРНЕТИЧЕСКОГО
БОРНИКА
1Я|Е!
1 • v •
s®SS
шшш
жгт,
ШШЁШШ
■
фщщ0 Щф11
ШЁ№£№
ятШятш
шш
щ	-
К ■ \
шт
,
мШШШтттШШж,
ШшЩ&Щ
шшш
ЯЙНаШР &ш± v ШШШШ
i^tel йМШЩ!
^вЁшВЖ№Яй(><ШдХЮ№&Я№&
>;ы. >п>л&
Ш1
;rj5JS
ШщШ$
ЙЙЙЖйШж
-
принципы построения
базовой машины

COMPUTER MONOGRAPHS
General Editor: Stanley Gill
BASIC MACHINE
PRINCIPLES
J. K. ILIFFE
INTERNATIONAL COMPUTERS
AND TABULATORS LIMITED
MACDONALD: LONDON
1968

Библиотека
„ Кибернетического
Сборника “
ДЖ. АЙЛИФ
ПРИНЦИПЫ ПОСТРОЕНИЯ
БАЗОВОЙ МАШИНЫ
Перевод с английского
Е. Б. ДОКШИЦКОЙ и Н. Б. ФЕЙГЕЛЬСОН
Под редакцией
И. Б. ЗАДЫХАЙЛО
ИЗДАТЕЛЬСТВО «МИР»
МОСКВА 1973

УДК 681.142.2
В книге описан принципиально новый и весьма перспектив¬
ный подход к конструированию вычислительных машин. Предла¬
гается «поднять квалификацию» ЭВМ путем включения в аппа¬
ратуру новых возможностей, приводится модель Базового
языка такой «высококвалифицированной» машины и дается
анализ этой модели; при этом рассматриваются как общие во¬
просы, так и конкретный вариант машины.
Книга представляет большой интерес для специалистов в
области программирования и логики ЭВМ, а также для широ¬
кого круга читателей — от студентов до научных работни¬
ков, — интересующихся вычислительной техникой, применением
и эксплуатацией ЭВМ.
Редакция литературы по математическим наукам
3314-025
041(01 )-73

ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Прошло всего два с половиной десятилетия с тех пор, как
появились первые ЭВМ, а мы уже знакомимся с их четвер¬
тым поколением. Минули те времена, когда с восторгом вос¬
принималась каждая новая вычислительная машина, превос¬
ходившая по каким-либо эксплуатационным параметрам
своих предшественниц. В настоящее время основную роль
начинает играть «квалификация» машины, которая опреде¬
ляется ее математическим обеспечением. Огромные програм¬
мные системы, насчитывающие миллионы команд, облегчают
доступ человека к машине, дают ему возможность формули¬
ровать задачи в терминах тех понятий, которые сложились
в различных областях науки, техники и производства. К со¬
жалению, большая часть математического обеспечения со¬
здается на языке команд конкретной машины, поэтому исполь¬
зование ее на новой машине связано с большой работой по
перепрограммированию, которая уже сейчас превышает по
трудоемкости и стоимости затраты на создание аппаратуры.
Однако программные системы, имеющиеся в настоящее
время, являются лишь незначительным ядром, на базе кото¬
рого можно рассчитывать повысить «интеллектуальный» уро¬
вень вычислительных систем. Поэтому можно предсказать
стремительный рост математического обеспечения в будущем.
Вторая основная тенденция в области вычислительных
машин состоит в том, что чрезвычайно быстро развиваются
возможности аппаратного решения различных операций, ко¬
торые могут резко повысить эффективность вычислительной
системы за счет погружения многих функций, реализуемых
пока программным образом, в аппаратуру. Разработки спе¬
циализированных вычислительных машин, «понимающих»
языки высокого уровня (Алгол, Фортран и др.)» отражают
это направление. Однако такой путь не исключает, а лишь
подчеркивает необходимость создания машинного языка, ко¬
торый явился бы хорошей базой для создания единого мате¬
матического обеспечения и не тормозил развития аппаратуры
Построение такого языка, естественно, предполагает выяснение

6
Предисловие редактора перевода
той границы, до которой разумно доводить аппаратуру в рам¬
ках сформулированной задачи.
В предлагаемой читателю книге делается попытка найти
такую границу между аппаратурой и программным обеспече¬
нием, которая выражается в виде Базового языка, предлагае¬
мого автором. Дж. Айлиф предпринимает ревизию прин¬
ципов построения вычислительных машин и предлагает
включать в ее логику лишь элементы, основанные на матема¬
тических понятиях, опираясь в первую очередь на те из них,
которые используются в языках высокого уровня. Читатель
может найти более широкое, чем в книге, идейное обоснова¬
ние такого подхода в трудах конгресса IFIP, состоявшегося
в Эдинбурге в 1968 г. (Scarrott G. G. and Iliffe J. К., The Ba¬
sic Language).
В первой главе критикуются некоторые аспекты нейманов¬
ской схемы вычислительной машины, определяются основные
принципы построения новой модели и обсуждаются те пре¬
имущества, которые могут быть достигнуты при ее реали¬
зации.
Вторая глава посвящена краткому описанию тех вычис¬
лительных систем, в которых уже имеются определенные эле¬
менты, развиваемые автором в его модели.
В третьей главе описывается конкретная реализация ма¬
шины и ее система команд, на основе которой в четвертой
главе формулируется Базовый язык.
В пятой главе приводятся основные направления, в кото¬
рых можно развивать модель, построенную автором.
В книге обсуждается много интересных вопросов, связан¬
ных с построением современных систем: структура памяти,
методы эффективного представления программ и данных,
использование аппарата прерываний, мультипрограммирова¬
ние, организация процессов и т. д. Она доступна широкому
кругу читателей.
Следует, однако, отметить некоторую неоднородность из¬
ложения. В одних местах материал дается излишне подробно,
а в других нарочито туманно. Можно порекомендовать чита¬
телю не слишком придираться к книге в этом отношении.
Чтобы не давать слишком много сносок для выравнивания
текста, редактор ограничился в основном замечаниями тер¬
минологического характера.
Для читателя, который заинтересуется вопросами выбора
границы между аппаратурой и программным обеспечением,
можно порекомендовать следующую литературу:
1.	Джермейн К., Программирование на IBM/360,
изд-во «Мир», М., 1971.

Предисловие редактора перевода
7
2. Вычислительная система IBM/360. Принцип рабо¬
ты, изд-во «Советское радио», М., 1969.
3. Камынин С. С., Любимский Э. 3., Алгорит¬
мический машинно-ориентированный язык — АЛМО,
сборник «Алгоритмы и алгоритмические языки», вып. 1,
изд-во ВЦ АН СССР, М., 1967.
4. Смирнов В. К., Мямлин А. Н., Входной язык
вычислительной машины с магазинной памятью, Кибер¬
нетика, 1967, № 6.
5. Глушко в В. М., Сто гний А. А., Молча¬
нов И. Н., Алгоритмический язык малой электронной
цифровой вычислительной машины МИР, т. II, кн. 1,
изд-во «Наукова думка», Киев, 1971.
6. Задыхайло И. Б., Камынин С. С., Любим¬
ский Э. 3., Проект системы математического обеспече¬
ния БЭСМ-6 (технические условия), изд-во ИПМ АН
СССР, М., 1967.
7. 3 а д ы х а й л о И. Б., К а м ы н и н С. С., Любим¬
ский Э. 3., Вопросы конструирования вычислительных
машин из блоков повышенной квалификации, изд-во
ИПМ АН СССР, М., 1971, препринт № 68.
8. Rice R., Smith W. R., SYMBOL—A major de¬
parture from classic software dominated von Neumann
computing sistems, Proc. AFIPS, V. 38, SJCC-71.
И. Б. Задыхайло

ИЗ ПРЕДИСЛОВИЯ АВТОРА
В этой книге затрагиваются вопросы определения вычис¬
лительной системы с точки зрения программирования. Она
будет интересна в первую очередь конструкторам логических
схем и программистам, которые занимаются сопряжением
аппаратного и программного оборудования вычислительной
машины. Однако решения, принятые на этом уровне, имеют
далеко идущие последствия, и ожидается, что они заинтере¬
суют также конструкторов вычислительных машин и поль¬
зователей, которые косвенно зависят от логических возмож¬
ностей и скорости универсальных машин и стремятся эффек¬
тивно их использовать.
Определение машины дается в терминах символьного язы¬
ка, фундаментальное значение которого отражено в названии
«Базовый язык». Определенные и устоявшиеся принципы, вы¬
текающие из практических требований, воплощены в Базовой
машине, а сам язык реализован посредством общей системы
логических схем и хранящихся в памяти программ, которые
вместе составляют машину с Базовым языком, или BLM.
Относительно длительную и дорогую часть исследований
ее свойств нельзя было бы предпринять без поддержки мно¬
гих коллег и друзей, чью помощь я высоко ценю.
Дж. Д. Айлиф

1
ОБЩИЕ ПРИНЦИПЫ
Конечная цель создания вычислительной машины состоит
в том, чтобы довести дело до ее производства и убедиться
в ее эффективном применении для решения актуальных науч¬
ных проблем и типичных задач по обработке информации и
в быстром приспосабливании ее к новым сферам применения.
Как характер современного производства аппаратуры, так и
размеры капиталовложений в разработку программных си¬
стем требуют, чтобы принципы конструирования были об¬
щими для большого числа машин различного объема и
быстродействия и сохраняли силу на протяжении некоторого
промежутка времени, в течение которого, судя по опыту по¬
следних лет, новые компоненты систем будут появляться
с поразительной регулярностью. Поэтому исследование фун¬
даментальных принципов построения вычислительных машин
имеет большое экономическое значение, хотя эти принципы
и сами по себе требуют внимательного изучения.
Вероятно, самый главный принцип, которому обязаны
своим существованием все сложные устройства, состоит в том,
что вычислительную машину подразделяют на много состав¬
ных частей и определяют каждую путем описания того, как
она реагирует на действия своих соседей. Обычный метод раз¬
работки проекта заключается в том, что сначала строят тео¬
ретическую модель каждой составной части и убеждаются
в том, что она удовлетворяет функциональным требованиям
системы. После этого конструктор может применить свое ма¬
стерство, чтобы найти допустимый компромисс между стои¬
мостью и производительностью машины при условии, что за¬
коны, положенные в основу модели, не будут нарушены. Если
модель выбрана хорошо, то будет обнаружено много различ¬
ных способов ее реализации и соответственно возрастает чи¬
сло возможных областей ее применения.
Эквивалентным способом анализа вычислительной си¬
стемы является описание системы в терминах границ, или со¬
пряжений1), между каждой составной частью системы и
В оригинале interface. — Прим. ред.

10
/. Общие принципы
соседними с ней частями. В зависимости от точки зрения кон¬
структора любая граница может приобрести основное значе¬
ние, что позволит характеризовать данную машину как шаг
вперед по сравнению с предшествующими. Например, о ны¬
нешнем поколении вычислительных машин можно сказать,
что наиболее важным из разработанных понятий является
«стандартное сопряжение» между центральной частью си¬
стемы и периферийными устройствами ввода-вывода данных.
В этой книге нас будет интересовать граница между блоком
центрального процессора и комплексом непосредственно адре¬
суемой памяти, т. е. способ представления программ в па¬
мяти во время их выполнения. Именно на этой границе стал¬
кивались во времена первых вычислительных машин програм¬
мисты и инженеры, и традиция представлять вычислительную
машину, описывая ее язык (систему команд), отмирает мед¬
ленно, несмотря на то что большинство современных про¬
граммистов, вероятно, с пренебрежением восприняли бы та¬
кую информацию о машине.
Однако мы описываем BLM1) таким образом не из сенти¬
ментальных побуждений. Благодаря программам-ассембле-
рам перед программистом обычно предстает вторая «грани¬
ца» — символьный вводной язык, выражения которого мо¬
гут быть переработаны в программу на языке машины. При
более внимательном изучении обнаруживается, что в дей¬
ствительности это вовсе не граница, поскольку язык опреде¬
ляется в терминах порождаемых им двоичных программ и
не существует эффективного способа предотвратить случай¬
ное или преднамеренное использование программистом по¬
рождаемых кодов некорректным образом.
Одна из основных задач этой книги и состоит в обоснова¬
нии того, что символьный вводной язык действительно дол¬
жен быть элементарной основой сопряжения между програм¬
мистом и блоками центрального процессора и должен опре¬
деляться независимо от двоичного языка машины. Легко
видеть, что структура традиционной машины не может удо¬
влетворить этому требованию; мы же опишем такую машину,
которая обладает желаемыми свойствами. Фактически мы
только применим уже упомянутый принцип: определять от¬
дельную часть вычислительной машины (в данном случае —
множество предложений первичного языка команд), указав,
что она делает, а не что она собою представляет. Хотя непо¬
1 В дальнейшем мы будем иногда употреблять следующие сокращения:
BL (Basic Language) — Базовый язык, описанный подробно в гл. 4 этой
книги; BLM, или просто ВМ (Basic Language Machine и Basic Machine
соответственно), — машина с Базовым языком, или Базовая машина, опи¬
санная в гл. 3 этой книги. — Прим. перев.

1.1. Разработка модели
11
средственные последствия восстановления границы, которая
сейчас совершенно незаметна в глубине всей вычислительной
системы, могут показаться незначительными, представляется
почти несомненным, что их влияние будет чувствоваться в ко¬
нечном счете во всем комплексе программного обеспечения
и в методах его построения.
В этой главе мы продолжим изучение исходных принци¬
пов и выделим некоторые понятия, которые, надо надеяться,
получат применение в программных системах. Наши умоза¬
ключения ни в коей мере не претендуют на абсолютную но¬
визну; в гл. 2 мы получим возможность исследовать, как
некоторые из тех же самых основных принципов были осу¬
ществлены на практике. Таким образом, вооруженные апри¬
орными теоретическими соображениями и обзором практиче¬
ских работ, мы перейдем в гл. 3—4 к описанию особенностей
аппаратной реализации центрального процессора и входного
языка BLM. В заключение мы рассмотрим некоторые свой¬
ства построенной системы и те дополнения к ней, которые
сразу же можно предложить.
1.1.	Разработка модели
Обычно говорят, что большинство современных машин
в конструкции центрального процессора следует «модели фон
Неймана», предложенной в основополагающей монографии
Бёркса, Голдстейна и фон Неймана [1]. В действительности
применявшаяся в машине фон Неймана схема выполнения
операций, которую можно назвать «односумматорной», была
довольно быстро вытеснена многосумматорными предше¬
ственницами современных вычислительных систем, которые
в отношении доступа к данным имели преимущество перед
описанной фон Нейманом моделью. Она была постепенно усо¬
вершенствована и в других отношениях: была предоставлена
возможность менять отдельные операции, выполняемые на
каждом шаге вычислительного процесса; размер памяти из¬
менился приблизительно с 1000 до 200 000 слов и более;
длина слова изменилась с шести до шестидесяти четырех би¬
тов; простое правило «каждый раз — один шаг» стало выдер¬
живаться не так строго в связи с разрешением делать вычис¬
ления параллельно с обменом информацией между оператив¬
ной памятью и внешними устройствами, этот режим работы
во многих машинах должен учитывать сам программист;
а появление постоянного набора «системных программ» изба¬
вило пользователя от капризов более медленных частей вы¬
числительной системы.

12
1. Общие принципы
Однако, быть может, самой важной отличительной чертой
модели фон Неймана остается принцип единой «линейной па¬
мяти», которая адресуется последовательными номерами
ячеек (обычно от 0 до т, где т — некоторая степень числа
2) и в которой команды неотличимы от данных. В ранних
описаниях техники программирования подчеркивались важ¬
ность и трудность такого принципа [2], и, несмотря на то что
после введения модификации команд такая организация па¬
мяти перестала быть существенным свойством программы
в машинном коде, в течение еще двенадцати лет не было
предпринято никаких попыток отказаться от нее [3].
Если рассмотреть какой-нибудь набор задач математиче¬
ского и информационно-логического характера (например,
комплекс задач, возникающих в бюро обслуживания), то
крайне маловероятно, что требования, которые эти задачи
предъявляют к размещению своих данных и программ, будет
легко совместить с линейным характером памяти машины.
Такое совмещение тем менее вероятно, чем в более общем
виде сформулирована задача. Если количество данных мо¬
жет меняться, то следует оставить достаточно места для рас¬
ширения области данных до максимального размера; если
ход вычислений сложен, то заботы о том, чтобы требуемые
программы и данные находились на своих местах на каждом
этапе вычислений, тяжким бременем ложатся на програм¬
миста, а помощь, предоставляемая ему системой, часто при¬
водит к неудобным для программирования ограничениям.
В следующей главе мы рассмотрим некоторые проблемы, свя¬
занные с распределением памяти, а в данный момент доста¬
точно упомянуть о том, что традиционные средства трансляции
и выполнения программ действуют как фильтр, допускающий
к постановке на машине только те задачи, решение которых
оправдывает стоимость трансляции их на язык машины,
имеющей жесткую структуру памяти.
Поэтому мы не должны удивляться тому, что усилия по¬
строить модель вычислительной машины, подходящую для
современных применений, обычно оканчиваются созданием
машины, подобной машине фон Неймана. Действительно, мо¬
жно было бы предположить, что стоимость современных про¬
граммных систем исключает радикальное изменение кон¬
струкции машины и что быстрое развитие техники следует
использовать для того, чтобы просто выполнять те же работы
и таким же образом, но дешевле. Конечно, главное требова¬
ние ко всякому новому проекту состоит именно в том, чтобы
он удовлетворял современным нормам программирования
как можно более эффективно. Обычные «проблемно-ориенти¬
рованные» языки хорошо отражают и структуру традицион¬

1.1. Разработка модели
13
ных вычислительных машин, и некоторые задачи, для реше¬
ния которых эти языки созданы; затраты на развитие про¬
граммирования, например на Фортране и Коболе, можно
оправдать, перенося подобные стандарты на будущие маши¬
ны. Однако ясно, что, приняв метод проектирования, исходя¬
щий из традиционных допущений о сущности машинной
памяти и команд, можно разве только укрепить механизм
фильтрации: задач, которые будут проходить через фильтр,
может стать больше, но качественно набор задач останется
прежним.
Что дает нам право считать, что возможности традицион¬
ных машин приспосабливаться к решению различных типов
задач близки к пределу? Верно ли, что они универсальны и
их можно применить для решения любой задачи? В матема¬
тическом смысле эго верно, но, как мы отмечали, стоимость
решения может оказаться такой высокой, что экономически
выгодное решение задачи станет невозможным. Большинство
программистов могут привести примеры из собственной прак¬
тики, когда возникала необходимость приспособить задачу
к линейной памяти, но это оказывалось либо трудным, либо
дорогим делом. Здесь, однако, следует отметить, что сами
профессиональные программисты подвергаются тому же про¬
цессу искусственного отбора, что и их задачи. Скорее именно
непрофессиональный пользователь жалуется на ограничи¬
тельные правила языка, которым он вынужден пользоваться,
и на «бестолковое» поведение машины в не предусмотренных
им ситуациях. Он может резонно спросить, есть ли необходи¬
мость в том, чтобы навсегда сохранить такое положение
вещей.
Пример
Чтобы проиллюстрировать некоторые из затронутых нами
спорных вопросов, рассмотрим одну простую задачу. Предпо¬
ложим, что проводится исследование движения автомобилей,
состоящее в следующем: на некотором участке дороги оста¬
навливают все частные автомобили, следующие в любом на¬
правлении, и о каждом из них записывают такие данные:
а) название пункта, откуда выехал автомобиль;
б) название места назначения;
в) количество пассажиров.
Полученная таким образом информация вводится в ма¬
шину в виде записей заданного формата. Требуется написать
программу, которая бы подвела итоги исследования, напеча¬
тав, какое количество автомобилей без пассажиров, с одним,
с двумя, с тремя, с четырьмя и более пассажирами соответ¬
ствует каждому зарегистрированному маршруту.

14
7. Общие принципы
Будем действовать следующим образом. Поскольку списки
пунктов отправления и назначения не заданы, программа
должна сформировать их в виде двух таблиц, содержащих
названия. Пусть для определенного исследования 5 и D —
таблицы соответственно пунктов отправления и назначения.
В начале работы эти таблицы пусты; они заполняются по
мере того, как новые названия выбираются из вводимых
в машину записей. Обозначим количество машинных слов, от¬
веденных под таблицу 5, через «длина (S)» и аналогично для
таблицы D. Предположим, что любое название помещается
в одном машинном слове. Тогда при помощи этих таблиц
можно каждую запись свести к целому числу п (количество
пассажиров, которое по условию задачи не превосходит четы¬
рех) и паре неотрицательных целых чисел (s, d), где 5 и d —
номера позиций в таблицах названий соответственно пунктов
отправления и назначения.
Для каждой пары (s, d) следует хранить в памяти таб¬
лицу из пяти чисел, характеризующую загруженность авто¬
мобилей пассажирами. Если эти таблицы расположить в па¬
мяти единым массивом В, то их можно упорядочить таким
образом, что таблица, соответствующая некоторой паре (s, d),
будет начинаться с &-й позиции относительно первого слова
массива В, где
k = 5*s* длина {D) + 5*d.	(1.1.1)
(Отметим, что относительный адрес первого слова каждой
таблицы принят равным нулю.) Теперь задача программы со¬
стоит в том, чтобы прочитать каждую запись; просмотрев
таблицы S и О, найти пару (s, d) \ вычислить номер ft; и в за¬
висимости от значения п прибавить единицу к содержимому
соответствующей ячейки массива В. В заключение программа
должна напечатать сводку результатов.
Суть этой задачи в том, что количество данных, которые
надо хранить в памяти, переменно. Допустим, что величины
длина (D) и длина (S) не будут превосходить ста; в этом
случае под массив В нужно отвести до 50 000 ячеек, большин¬
ство из которых, вероятно, не будет использоваться. Предпо¬
ложим, что будет использоваться не более 1000 пар (s, d).
Тогда можно завести промежуточную таблицу Л, в которой
пары (s, d) расположены некоторым произвольным образом,
т. е. k-м элементом таблицы будет некоторая пара (s, d)\
таблица А заменит приведенное выше соотношение между k
и индексами s н d: номер позиции k будет вычисляться не по
формуле (1.1.1), а посредством просмотра таблицы А. Тогда
место, необходимое для таблицы Л, составит 1000 слов, но

1.2. Основные цела
15
зато длина таблицы результатов уменьшится с 50 000 слов
до 5000.
Таким образом, при помощи определенных предположе¬
ний, основанных на знании природы задачи, она была дове¬
дена до размеров, допустимых для постановки ее на машине.
Поскольку последняя формули¬
ровка задачи не вполне совпа¬
дает с первоначальной, инженеру-	S
автодорожнику при использова¬
нии нашей программы придется
иметь в виду соответствующие	D
ограничения, а позднее он может
потребовать другое «решение»
той же задачи, но с иными огра- А
ничениями.
На рис. 1 изображены основ- ^
ные массивы памяти и их распо¬
ложение в линейной памяти ма¬
шины. Заштрихованные участки	£
соответствуют областям памяти
переменной длины; их размеры	f
обычно нужно фиксировать перед
началом вычислений. Очевидно,
что логика, порождаемая меха-	^
низмом управления памятью,
здесь уже сложнее, чем арифме¬
тическая часть программы; такое
положение дел бывает и в реаль- Рис. 1. «Линейная» програм-
ных программах. Несомненно,	мная	память,
многие опытные программисты
считают, что это в порядке вещей, и легко могли бы предло¬
жить другие варианты решения, основанные на иных допу¬
щениях. Однако сама задача остается прежней, и, принимая
во внимание стоимость выбора метода решения и его
программирования, разумно поставить вопрос:	оправды¬
ваются ли все эти допущения той экономией усилий машины
и человека, которую они дают? В следующих главах мы по¬
пытаемся обосновать отрицательный ответ на этот вопрос.
1.2.	Основные цели
Первое требование модели фон Неймана состояло в том,
что физические компоненты вычислительной системы должны
быть описаны таким образом, чтобы для нее можно было
писать программы. Адресуемую память, например, представ¬
ляли так, что она точно отражала аппаратные аспекты
Пункты
отправления
Пункты
назначения
Пары (s, d)
Таблица
результатов
Byqpep
ввода- вывода
Буфер
ввода-вывода
БомандЫ

16
/. Общие принципы
существующих способов хранения информации и механизма
выборки. Однако, как показывает пример многих современных
машин, теперь уже нет необходимости определять границу
между машиной и программистом при помощи прямых физи¬
ческих характеристик, зато к числу вопросов, которым при¬
дается наибольшее значение, принадлежит математическое
содержание подлежащих решению задач и самого процесса
вычисления. Поэтому при первом подходе к выбору системы
машинных команд следует двигаться «снаружи внутрь», до
тех пор пока не будет найдено выгодное с экономической
точки зрения аппаратное сопряжение. Существует, конечно,
много абстрактных подходов к предмету вычисления и «вы¬
числимости», но их цели не имеют большого практического
значения. Для того чтобы можно было конкурировать в бы¬
стродействии с существующими машинами, необходимо по¬
требовать, чтобы элементарные шаги вычислений были по
крайней мере такой же степени сложности, как действия, за¬
даваемые отдельными командами этих машин; нельзя позво¬
лить себе игнорировать тот факт, что массивы данных должны
каким-то образом представляться в конечной физической
памяти; следует принимать во внимание практические аспек¬
ты написания, развития и выполнения программ. Именно эти
положения могут послужить нам отправной точкой для того,
чтобы точно сформулировать ряд целей, к которым мы стре¬
мимся.
Структура программ
С математической точки зрения задача, которую мы толь¬
ко что рассматривали, включает в себя действия над матри¬
цей М с элементами AJS)d, каждый из которых есть вектор,
имеющий пять целочисленных координат. Отношения между
отдельными частями программы выражают ее структуру. Эле¬
ментарная математика пользуется терминами, характеризую¬
щими структуру (матрица, вектор), и формулами (MSyd). Эти
средства удобны для того, чтобы приводить простые примеры,
но недостаточно выразительны в применении к ряду задач,
которые решаются на вычислительных машинах, и мы зай¬
мемся расширением запаса таких средств. Однако структура,
которую распознает вычислительная машина неймановского
типа, — это всего-навсего единственный вектор, содержащий
данные и команды.
Приведение задачи к линейной форме — дело программи¬
ста, и делает он это путем погружения структуры в логику
программы. Достигнуть такого результата можно, либо введя
в задачи ограничения на переменные таким образом, что

1.2. Основные цели
17
правила погружения станут исключительно простыми и реа¬
лизуемыми на традиционной аппаратуре, либо возложив пол¬
ную ответственность за распределение памяти на самое про¬
грамму, которая будет использовать хранящиеся в памяти
подпрограммы для «интерпретации» обращения к данным.
Классическим примером первого подхода является Фортран;
другой подход отражен в языках для обработки списков. Для
того чтобы попытаться обойтись без ограничений, не теряя
скорости, необходимо рассмотреть третью возможность: пусть
аппаратура распознает внутреннюю структуру программ, т. е.
логика программы избавляется от погруженной в нее струк¬
туры, а распознавание выполняется с высокой относительно
цикла ферритовой памяти скоростью.
Развитие системного программирования для мультипро¬
граммных машин ставит проблемы, которые нельзя эффек¬
тивно решить при помощи погружения. Каждая программа
для такой машины, написанная независимо от других, дол¬
жна считать, что у нее есть собственная линейная память
с «адресами» от 0 до некоторого т, зависящего от конкрет¬
ной программы. В реальной ферритовой памяти каждой про¬
грамме может быть отведен диапазон последовательных
ячеек, внутри которого программные «адреса» используются
как относительные номера. Эта ситуация в высшей степени
похожа на изображенную на рис. 1, за исключением того, что
каждый отдельный блок памяти соответствует самостоятель¬
ной программе. Системная программа рассматривает все ос¬
тальные программы как набор векторов, общая потребность
которых в оперативной памяти изменяется непредсказуемо и
поэтому должна удовлетворяться динамически, т. е. когда она
фактически возникает.
Первый шаг состоит в том, что каждой программе при¬
дается неявная база, или адрес b «начала информации»1),
который содержится в быстром регистре и который автомати¬
чески модифицирует каждый программный «адрес». Также
автоматически производится проверка того, что программный
адрес не превосходит заданной верхней границы т. Комби¬
нация чисел т и Ь точно описывает местоположение про¬
граммы в памяти и хранится в виде «граничной пары»:
Граничная
пара
!) В дальнейшем вместо термина «начало информации» в тех случаях,
когда речь будет идти об адресе b, мы будем говорить просто «начало». —
Прим. tie рев.
т
Верхняя начало
граница .

18
1. Общие принципы
Именно путем распознавания таких элементарных описа-
ний при помощи аппаратуры и удовлетворяются сделанные
программой запросы произвольных квантов памяти. По¬
скольку эти описания используются неявно, они не влияют
на приемы программирования в пределах одной программы.
Для самой системной программы граничные пары должны
быть доступны, чтобы она имела возможность перераспреде¬
лять память динамически: если программа пользователя пере¬
носится на новое место, начало которого в памяти опреде¬
ляется адресом Ь\ то в граничной паре этой программы b
заменяется на bвеличина т остается прежней, а в самое
программу также нет необходимости вносить какие-либо из¬
менения.
Структурные свойства программ пользователей тоже мо¬
гут быть описаны при помощи граничных пар, если предоста¬
вить средства для использования последних в сфере обычного
программирования. Однако нужно четко понимать, что про¬
граммист не должен иметь возможность так же свободно об¬
ращаться с граничной парой, как при работе с двоичной ин¬
формацией, поскольку при этом структуры утратили ,бы
свойство независимости.
Рассмотрение некоторых задач из области системного про¬
граммирования проиллюстрирует некоторые следствия, выте¬
кающие из принятия нелинейной структуры памяти. Если ка¬
ждая программа строго ограничивается собственным диапа¬
зоном памяти, то относительно просто обеспечить перед ее
выполнением загрузку правильной граничной пары в нужный
регистр, так чтобы значения элементов граничной пары соот¬
ветствовали любому перемещению программы в оперативной
памяти. Если же одна программа должна обратиться к па¬
мяти другой (так, например, поступает системная программа,
выполняющая задание программы пользователя), то она дол¬
жна обращаться к одной области памяти при выборе команд
и к другой —при работе с данными. Здесь уже недостаточно
неявной граничной пары; в дополнение к ней должен суще¬
ствовать способ прямого доступа, связанный с привилегиро¬
ванным, или «системным», режимом работы. Если, кроме
того, в системном режиме разрешается изменять значения
граничных пар, то аппаратура теряет возможность постоянно
следить за правильностью структуры, и системный програм¬
мист должен при создании «программного оборудования»1)
изобрести и соблюдать правила, которые сохраняли бы при¬
нятую структуру памяти. Таким образом, существовала тен¬
денция развивать системное программирование как самостоя¬
*) В оригинале software. — Прим. ред.

1.2. Основные цели
19
тельную область, требующую не только высококвалифициро¬
ванных программистов, но также и особого режима работы
вычислительной системы при отладке системных программ,
даже если логика лишь очень небольшой части программы
может потребовать привилегированных возможностей.
Здесь следует привести доводы в пользу внутренней со¬
гласованности разрабатываемой модели. Машина фон Ней¬
мана обладает этим свойством, что делает невозможным
каким-либо способом нарушить правила управления маши¬
ной. Однако мы уже видели, что модель с линейной памятью
для некоторых задач, в частности для реализации мультипро¬
граммирования, не подходит. Чем шире класс пользователей,
требования которых модель может удовлетворить, тем она
ценнее; исходя из этого, мы могли бы сформулировать цель
проекта следующим образом: принципиальная схема струк¬
туры памяти в разрабатываемом проекте должна включать
в себя то, что требуется как для системного программирова¬
ния, так и для традиционных структур данных. Такой подход
позволяет надеяться, что удастся сузить брешь, которая суще¬
ствует сейчас между «системным» и «пользовательским» ре¬
жимами работы.
Мы попытались оправдать введение явного распознавания
структуры программ тем, что рабочие программы станут более
универсальными и эффективными, чем они были бы при линей¬
ной памяти, и, следовательно, капиталовложения в програм¬
мирование и машиное время принесут больше выгоды.
В определенной ситуации, а именно при развитии про¬
граммы в самом широком смысле, когда особо важным слу¬
чаем является оперативное1) взаимодействие с программой
во время ее выполнения, можно привести еще одно веское
соображение в пользу структурной памяти машины. Здесь мы
опять имеем дело с непредсказуемой структурой памяти,
даже если структура окончательной рабочей программы
легко может быть приспособлена к линейной памяти. Ча¬
стично отлаженная программа состоит из нескольких групп
команд и данных, каждая из которых может подвергнуться
исправлению, когда будут найдены ошибки. По мере того
как уточняется постановка задачи, в программу вносятся до¬
полнения, временные куски программы удаляются, обнаружи¬
ваются и учитываются особые случаи, форма представления
результатов обсуждается с разработчиком задачи и т. д. Все
эти работы могут потребовать изменений в структуре, а если
программа не может выполняться не будучи приведена к ли¬
нейной структуре, то каждое изменение повлечет за собой по
1) В оригинале on-line interaction. — Прим. ред.

20
/. Общие принципы
меньшей мере частичное реассемблирование, которое никоим
образом не является тривиальной операцией для системы.
При этом приходится расплачиваться как ресурсами машины,
затрачиваемыми на загрузку, так и трудом программистов на
переделку программ независимо от того, в каком режиме про¬
изводится работа: пакетном или оперативном.
Поэтому если разрабатываемая модель распознает струк¬
туру сегментов программы, переделка последней может быть
значительно упрощена. К общим целям нашего проекта надо
добавить то, что такое распознавание, как уже отмечалось
выше, должно быть применимо и при работе со структурными
данными. Побочная, но важная выгода от такой согласован¬
ной структурной интерпретации состоит в том, что ошибки
в программах обнаруживаются быстрее, чем при линейной
памяти, поскольку структурное описание предполагает более
строгую проверку границ массивов информации. Отсюда же
вытекает еще одно следствие: состояние программы можно
сообщать пользователю в терминах ее структуры, что облег¬
чает диагностику ошибок. Если мы примем точку зрения, что
многие программы большую часть времени своего существова¬
ния находятся в стадии развития, а некоторые никогда из нее
не выходят, то сохранение структуры в нашей модели, несом¬
ненно, должно играть очень большую роль.
Управление
После исследования некоторых из основных трудностей,
связанных с линейностью памяти, естественно перейти к эле¬
ментам управления, чтобы посмотреть, не обнаружатся ли
там недостатки, сравнимые с разобранными ранее. В машине
фон Неймана управление осуществляет единственная после¬
довательность команд, каждая из которых выполняет опера¬
цию над указанными операндами, перед тем как передать
управление следующей. Если формат команд строго опреде¬
лен, то можно вычислить положение команды в памяти и вы¬
полнить условный или безусловный переход на нее. Кроме
того, как уже отмечалось, существует возможность совер¬
шать арифметические действия над командами, и это можно
использовать для достижения особых логических эффектов.
Во-первых, следует отметить, что если память описывается
некоторым нелинейным образом, то система команд должна
быть приспособлена к выборке операндов и команд с учетом
этого факта. Мы уже указывали на необычный характер гра¬
ничных пар как операндов. Во-вторых, именно возможность
вычислять положение команд и выполнять над ними арифме¬
тические действия препятствует легкому переводу программ

1.2. Основные цели
21
с одной машины на другую (арифметические и адресные опе¬
рации моделируются проще). Поскольку экономическая зна¬
чимость модели определяется отчасти накопленными для нее
программами, то чем свободнее конструктор может, не нару¬
шая правил, приспосабливать коды команд к новым ситуа¬
циям, тем лучше. Поэтому имеет смысл стремиться к такому
представлению команд, чтобы их легко можно было перево¬
дить из одного формата в другой, не затрагивая интересов
человека, т. е. нельзя фиксировать точную форму, в которой
команды, подлежащие выполнению, хранятся в памяти.
В-третьих, заметим, что при практическом программирова¬
нии почти во всех случаях данные и команды представляются
на символьном языке ассемблера, который позволяет полно¬
стью распоряжаться всеми возможностями машины. Если бы
обычные команды удалось определить в аналогичной сим¬
вольной форме, то это был бы, вероятно, важный практиче¬
ский шаг вперед в использовании машины; но следует заме¬
тить, что сущность символьного языка как составной части
системы состоит в том, что он дает возможность распоря¬
жаться формированием всех последовательностей команд и
включать проверки, которые в противном случае необходимо
было бы выполнять динамически. Например, можно сделать
так, чтобы все возможные пути передач управления внутри
сегмента полностью контролировались во время трансляции
программы, а во время ее выполнения не нужно было бы
проверять законность переходов. Мнемоническая ценность
вводного языка имеет несколько меньшее значение, особенно
в связи с тем, что его легко изменить, не затрагивая кон¬
струкцию машины. В гл. 4 мы воспользуемся этим фактом
для упрощения представления Базового языка.
Параллелизм
Можно привести много примеров современных машин,
применяющих при выполнении последовательностей команд
параллельное управление, чтобы достичь высокой произво¬
дительности. Для образования независимых параллельных
последовательностей команд достаточно, чтобы они работали
с различными наборами переменных данных. На уровне цент¬
ральных регистров машинная логика позволяет проверять,
выполняется ли это условие; желательно, чтобы регистры
были организованы таким образом, чтобы подобные проверки
были относительно просты и эффективны. На системном уров¬
не две любые независимые программы, очевидно, можно вы¬
полнять параллельно или при любом другом соотношении
времен, обеспечивающем экономию в рамках данной системы.

22
1. Общие принципы
Особый случай представляет собой обмен с периферийными
устройствами: здесь требуется физическая блокировка, по¬
тому что оба участвующих процесса не независимы; необхо¬
димо решить, следует ли в разрабатываемой модели этот
механизм «вытаскивать на поверхность» и является ли отра¬
жение локального параллелизма в самом деле полезной чер¬
той системы команд.
Конечно, если системное программирование само должно
быть составной частью разрабатываемой модели, то необхо¬
димо иметь возможность образовывать параллельные про¬
цессы. К тому же, если предполагается программировать
определенные задачи моделирования, может оказаться удоб¬
ным представлять их в виде параллельных процессов, не го¬
воря уже о значительном выигрыше в производительности,
который, возможно, при этом получится.
Мы уже договорились, что некоторое структурное пред¬
ставление данных необходимо; естественно сделать вывод,
что в первом приближении наличие структуры должно давать
возможность изоляции набора данных при параллельном вы¬
полнении программ, автоматически обеспечивать блокировки,
когда доступ к памяти запрещен, и разрешать вопрос о «хо¬
зяине» в тех случаях, когда допускается совместное исполь¬
зование информации. Именно эти требования и налагают до¬
вольно строгие ограничения на характер тех свойств структу¬
ры, которые могут распознаваться вычислительной системой.
Элементарные операнды
Отдельный шаг вычисления обычно состоит из выполнения
операции над одним или двумя операндами, взятыми из ука¬
занных позиций памяти, и помещения результата в третью
позицию (возможно, в одну из первых двух). Конечный диа¬
пазон номеров позиций увеличивается за счет возможности
выбора одного из взаимоисключающих представлений в пре¬
делах отдельного кода операции. Обычно предоставляется
выбор различных типов представления операндов: с плаваю¬
щей или фиксированной запятой, целое или дробное число,
в десятичном виде с различной точностью; при этом исполь¬
зование различия между типами обеспечивается выбором
операции, а не выбором самих данных. Если машина распо¬
знает, скажем, четыре типа операндов и шесть элементарных
операций над ними, то возможно около 96 межрегистровых
операций, а если каждый операнд может находиться в опера¬
тивной памяти, то их количество увеличивается до 384.
При традиционном подходе, когда код типа операндов
включается в код операции, потребуется выделить 9-разряд-

1.2. Основные цели
23
ное поле только для спецификации отдельной арифметической
операции. На практике список операций жестко (и до некото¬
рой степени произвольно) урезают, чтобы использовать поле
команды более эффективно. Однако главный недостаток от¬
деления указания типа от информации остается: программист
сам должен следить за тем, чтобы для каждого типа пред¬
ставления данных использовалась соответствующая операция,
чтобы там, где необходимо, был запрограммирован перевод
кз одной формы представления в другую, чтобы аргу¬
менты, задаваемые для подпрограмм, представлялись в. пра¬
вильной форме и т. д. Если правила не соблюдаются, то по¬
лучаются некоторые курьезные арифметические результаты,
которые в большинстве случаев можно рассматривать как
ошибки.
Противоположный подход состоит в том, чтобы всегда
связывать тип с данными. При условии, что представления
адресов и чисел различаются по типу кода операции, в коман¬
де остается только указать арифметическую операцию,
а дальнейший анализ осуществляется при помощи типов дан¬
ных. Количество разрядов, требуемых для кода операции
в команде, доводится таким образом до минимума, а трудно¬
сти такого рода, как те, о которых шла речь выше, устра¬
няются в обмен на небольшое число неудобств, которые за¬
ключаются в том, что невозможно получить «хитрые» ариф¬
метические результаты, которые, правда, можно достичь и
другими путями.
На первый взгляд кажется, что каких бы преимуществ мы
ни добились, упрощая кодирование команд, они сводятся на
нет присоединением двух или более разрядов, кодирующих
тип, к каждому элементу данных; в машине, где сами эле¬
менты данных могут занимать только 8 разрядов, это могло
бы означать ощутимые дополнительные расходы памят Од¬
нако практические наблюдения показывают, что элементы ин¬
формации большей частью встречаются в виде конечных
упорядоченных наборов с единой формой представления эле¬
ментов, например: строки символов, последовательности це¬
лых чисел и т. д., поэтому если мы сумеем устроить так, что¬
бы информация о типах представляла собой часть «описания
набора», то потребность в дополнительной памяти будет
в действительности очень мала. Таким образом, рассмотрение
машинных операций приводит нас снова к описанию про¬
граммных структур, которые мы приняли в качестве основной
цели разрабатываемого проекта; следовательно, источник ин
формации о типах должен быть сам описанием структуры
Т. е. обобщением граничной пары.

24
U Общие принципы
Чтобы уметь различать данные, команды и адреса, необ¬
ходима какая-то форма кодирования, отличная от той, кото¬
рая позволяет задавать различные формы представления
данных. Уже предлагалось скрыть двоичные команды от
пользователя; поэтому любая попытка прочесть или написать
их должна обнаруживаться и рассматриваться как ошибка.
Аналогично с адресом, который будет содержать граничную
пару, следует обращаться не так, как с числовыми данными.
Оказывается, способ кодирования, который применялся для
того, чтобы отличать один тип числовых данных от другого,
можно использовать и в этом более общем случае. Мы смо¬
жем сразу понять «структуру» программы, воплощенной
в форме наборов команд, наборов данных и наборов адресов;
остается определить их взаимосвязь при помощи соображе¬
ний, основанных на свойствах задачи и системы и ведущих
к экономному способу решения.
Прерывания
Точное описание даже относительно простой вычислитель¬
ной машины — трудная задача, которую редко удается завер¬
шить до ее аппаратной реализации. Полное определение си¬
стемы команд для современной вычислительной системы не
только практически невозможно, но на уровне аппаратного
оборудования *) и нежелательно просто из-за того, что метод
реализации многих действий может зависеть от установки
конкретной машины, от свойств данной операционной систе¬
мы или даже от программы, выполняемой в данный момент.
Это вовсе не означает, что простейшее определение операции
сложения может меняться от случая к случаю. Постоянная
часть системы команд должна быть достаточно представи¬
тельной: в нее должны входить элементарные арифметиче¬
ские и логические операции, операции поиска и запоминания
информации, операции передач управления, чтобы можно
было написать большинство программ в предположении, что
не возникнет никаких особых обстоятельств. Однако если об¬
наруживаются такие события, как арифметическое перепол¬
нение, или недопустимый адрес, или ошибка при пересылке
информации, то обычно следует обратиться за помощью к
хранящимся в памяти командам, чтобы завершить интерпре¬
тацию данной операции.
Задача аппаратного оборудования — обнаружить исклю¬
чительные обстоятельства и обратиться к соответствующей
интерпретирующей программе. В этом смысле в Базовой ма-
1) В оригинале hardware. — Прим. ред.

1.3. Основные выводы
25
шине употребляются термины «прерывание» и «программа
обработки прерывания». Если прерывание выполняется мед¬
ленно, то его использование ограничивается редкими собы¬
тиями, такими, как ошибки в программах или отказы
периферийных устройств. С другой стороны, если вход в про¬
грамму обработки прерывания происходит быстро и ее пара¬
метры легкодоступны, то механизм прерываний становится
удобным для практического завершения определения системы
команд.
Мы увидим далее, что аппарат прерываний широко приме¬
няется в Базовой машине. Его используют программы, управ¬
ляющие памятью, для осуществления временной «защиты»
совместно используемых данных; он применяется для авто¬
матического обращения к носителям вспомогательной памяти,
для различных целей при работе монитора и управлении по¬
рядком выполнения программ; он используется при обнару¬
жении недопустимой или «неопределенной» информации и для
разрешения противоречий при необычных комбинациях типов
операндов. Он может также привести прямо к функциональ¬
ным определениям данных, что может часто использоваться
в определенных ситуациях. По этим причинам желательно в
нашем проекте машины предусмотреть реализацию быстрых
прерываний и формализовать их применение во вводном языке.
Важно также отметить, что поскольку программа обработки
прерывания может быть подготовлена пользователем или
одной из резидентных системных программ, то существен¬
ное значение имеет гибкая система адресации. Явное рас¬
познавание структуры программ соответствует этому тре¬
бованию.
1.3. Основные выводы
В Базовой машине к двум составным частям хранимой
в памяти информации, с которыми мы уже знакомы, — коман¬
дам и данным добавляется третья — описание структуры. Мо¬
жно обсудить здесь следующее возможное возражение про¬
тив нашего проекта. Известно, что существующие языки
«высокого уровня» уже в большой степени достигли целей, по¬
ставленных перед Базовой машиной. Они, несомненно, сим¬
вольные; они, очевидно, содержат структуры данных и раз¬
личные типы элементарных операндов; в них уже заложены
возможности образования параллельных процессов и работы
по прерываниям. Нельзя ли придумать язык программирова¬
ния со всеми необходимыми возможностями для реализации
его на традиционной машине? Краткий ответ таков: можно,
но выполнение программ на этом языке обошлось бы слишком

26
/. Общие принципы
дорого. Существующие компиляторы только «распознают»
структуру на основании ограничений вводного языка,
что дает возможность погрузить ее в программу во время
трансляции, путем использования интерпретирующих (и по¬
тому медленных) режимов выполнения или, как будет пока¬
зано в гл. 2, выполняют при трансляции лишь «грубую» работу,
предоставляя программисту самостоятельно защищаться от
ошибок.
При условии, что блоки информации велики по сравнению
со словом памяти, обработка структуры путем интерпретации
дает удовлетворительные результаты. Так, программы работы
с файлами и «пакеты» матричной арифметики возникли еще
на заре эры вычислительных машин. Все характерные свой¬
ства Базовой машины должны основываться на применении
аппаратного оборудования для детальной интерпретации
структур, откуда следует, что ее особые преимущества дол¬
жны возникать из-за скорости интерпретации, а ее недостат¬
ки—из-за явного уменьшения гибкости и большей стоимости.
Подведем итог тем преимуществам, которые мы надеемся
получить в нашей модели.
(a) Разносторонность. Информационную структуру, пред¬
ставляющую собой программу, можно на каждом шаге вы¬
бирать таким образом, чтобы она точно соответствовала
структуре, принятой программистом при описании задачи,
вплоть до блоков информации, имеющих размеры такого по¬
рядка, как поле символа или слова. Класс задач, которые мо¬
гут быть решены достаточно экономно, шире, чем для тради¬
ционных машин (т. е. машин фон Неймана), поскольку он
включает в себя задачи с переменной структурой.
(b) Точность представления. Возможно строгое выполнение
требований вводного языка в том смысле, что проверки допу¬
стимых диапазонов определяются отдельными частями струк¬
туры информации, а не всем полем программы. Следователь¬
но, важный класс программистских ошибок можно обнару¬
живать автоматически, а в диагностических сообщениях
можно использовать информацию о структуре с тем, чтобы
составить вразумительные тексты. Поэтому следует ожидать,
что обнаружение и исправление ошибок в программах на Ба¬
зовом языке будет дешевле, чем на других.
(c) Интеграция системы. Базовый язык1) представляет воз¬
можность работать и со скалярными, и с нескалярными ве¬
личинами. Он распределяет память динамически, т. е. по
командам, выполняемым в ходе работы программы, или в от-
1)	К сожалению, здесь автор явно забегает вперед. Базовый язык будет
введен значительно позже. — Прим. редь

1.3. Основные выводы
27
Вет на запросы системы; память, отведенная под некоторую
программу на любом имеющемся носителе, может быть увели¬
чена, уменьшена или перераспределена. Базовый язык можно
применить для управления параллельными или выполняемы¬
ми в режиме разделения времени процессами. Следовательно,
он обладает необходимыми чертами языка операционных
систем и фактически объединяет в себе команды символьного
языка и директивы операционной системы. Сама система
может воспользоваться преимуществом структурного пред¬
ставления программ, чтобы объединить основной и вспомо¬
гательный уровни памяти и управлять асинхронными процес¬
сами, не требуя дополнительного аппаратного оборудования.
(d) Недоступность нечисловой части программ. Команды ма¬
шинной программы в том виде, в котором они представ¬
ляются непосредственно для выполнения, защищены. Ни
команды, ни адреса нельзя использовать как данные; их фор¬
мат можно менять в целях увеличения производительности
машин в определенных областях, например на самых грани¬
цах сферы применения машин, не принося в жертву капита¬
ловложения, использованные на накопление программ на Ба¬
зовом языке.
(e) Новые приложения. Базовая машина дает возможность
применить методы программирования, которые до сих пор
были неэкономичны и остаются в значительной степени неис¬
следованными. Можно надеяться, что развитие использования
типов в проекте языка и в управлении данными, использова¬
ние прерываний и приспосабливание структурного представ¬
ления к требованиям как системы, так и пользователя
приведут к совершенствованию системы приемов, имеющих
значительные преимущества перед принятыми в современной
практике.
Этим доводам можно противопоставить стоимость обслу¬
живания структуры и системы адресации при ее применении.
(а)	Стоимость выполнения. Поскольку структура данных
может во время выполнения программы содержаться в па¬
мяти1), иногда потребуются дополнительные обращения к по¬
следней, чтобы получить определенный элемент информации,
в то время как в линейной памяти можно было бы обратиться
к нему прямо по адресу.
(Ь)	Первоначальная стоимость и дополнительные расходы.
Первоначальное образование структуры и последующее уп¬
равление относительно сложной системой распределения па¬
мяти вызывают дальнейшие дополнительные расходы и Moryi
уменьшить общую производительность системы.
‘) А не на быстрых регистрах. — Прим. ред.

•28
/. Общие принципы
(с)	Ограничения на программирование. Хотя была высказана
мысль, что, получив разрешение использовать в качестве ин¬
формации граничные пары, программист достигнет известной
степени гибкости, можно возразить, что необходимые при
этом ограничения на использование граничных пар фактиче¬
ски лишают программиста некоторых удобств, которыми он
прежде пользовался. В самом деле, любая попытка формали¬
зовать понятия программирования (такие, как тип или блоч¬
ная структура) до такой степени, чтобы их могла распознать
«аппаратная» часть системы, обязательно приводит к проте¬
стам со стороны людей, которые предпочитают интерпрети¬
ровать данные по-своему. Это, вероятно, главное возражение
против программирования на любом языке высокого уровня.
В нашем случае, однако, будет показано, что большинство
традиционных методов по-прежнему можно будет применять,
если программист согласится со связанными с ними ограни¬
чениями. Законный протест может возникнуть только в том
случае, если большая общность. Базовых машин в действи¬
тельности приведет к снижению производительности системы.
Приведенные выше критические соображения, а также
преимущества, на которые претендует BLM, очевидно, тре¬
буют тщательного изучения; они являются предметом продол¬
жающейся программы исследований. Несмотря на то что пол¬
ный обзор всех этих доводов не входит в нашу задачу, мы
еще ненадолго вернемся к ним в последней главе.

2
НЕКОТОРЫЕ РОДСТВЕННЫЕ СИСТЕМЫ
Память в машине с Базовым языком можно в первом
приближении описать как «древовидную структуру». Одина¬
ковые в идейном отношении элементы памяти объединяются
в наборы различных типов. В основном это наборы команд
и данных, но их расположение друг относительно друга зада¬
ется при помощи одного из видов структурной информа¬
ции— обобщенной формы граничной пары, для обозначения
которой используется термин «кодослово» [4]. Кодослова
также объединяются в наборы, которые располагаются в
«точках ветвления» дерева. Описываемую структуру харак¬
теризуют следующие свойства: каждый набор имеет только
одно кодослово, и каждое кодослово, за единственным ис¬
ключением, принадлежит набору с кодословом «более высо¬
кого уровня». Исключение составляет главное кодослово
структуры, находящееся на самом высоком уровне данного
дерева. Понятие «уровня» используется для указания числа
шагов, которое необходимо затратить на то, чтобы, исхо¬
дя из главного кодослова, добраться до заданного элемента,
двигаясь через промежуточные точки ветвления; чем больше
число шагов, тем ниже уровень. (Читатель заметит, что в Ба¬
зовой машине деревья при развитии структуры растут либо
вниз, либо в сторону, слева направо.)
В схематической форме кодослово можно представить так:
Я
t
/77
Ъ
Кодослово
Вид Тип	Начало
В Базовой машине значение верхней границы любого на¬
бора на единицу меньше его длины. Видно, что к информации
о верхней границе набора и о его начале присоединены еще
Два поля. Понятие типа кодослова t введено в основном для
описания элементов того набора, на который ссылаются при
помощи m и Ь. Чтобы избежать разногласий с последующим

30
2. Некоторые родственные системы
развитием этого понятия в гл. 3, здесь используются такие
значения кодов типа:
тип / = 0,	относится	к двоичным	числовым	элементам;
тип t = 4,	относится	к командам;
тип /==8,	относится	к кодословам.
Не всегда кодослова	ссылаются на	явно	определенные	на¬
боры, к которым есть доступ; во время построения древовид¬
ной структуры может, например, случиться так, что многие
кодослова останутся «неопределенными» до более позднего
этапа вычислений, и поэтому все попытки использовать эти
кодослова для прямого доступа к данным должны приво¬
дить к вмешательству монитора. Чтобы различать такие си¬
туации, вводится понятие вида g со следующими значе¬
ниями:
g= 1, если кодослово требует интерпретации
по прерыванию;
g = 2, если кодослово интерпретируется обычным,
образом.
Другие коды вида будут введены в следующей главе. Исполь¬
зование прерываний будет разобрано в описываемых далее
системах.
Поскольку параметр b имеет значение только для приви¬
легированных программ управления памятью, резонно не ис¬
пользовать его в схематических представлениях, а ввести
стрелку, указывающую из кодослова на первый элемент оп¬
ределяемого им набора, который изображается отдельным
блоком.
5 \ 2\t\	/77
/77
Первый элемент
(] + с)-й элемент
Последний элемент
Элементы в наборе различаются по значениям индексов
(они написаны сбоку), представляющих собой неотрица¬
тельные целые числа. Они могут задаваться при помощи
констант или переменных, которые получают значения в

2. Некоторые родственные системы
31
процессе счета, в тех случаях, когда не может возникнуть
двусмысленность. Можно использовать такие выражения,
как «номер (или команда) i» для обозначения элемента (или
команды) в i-u индексной позиции или «кодослово S» для
указания значения кодослова 5-й позиции. Но так как кодо¬
слово может описывать и набор элементов, выражения на¬
бор 5, массив1) S или программа S тоже разрешается упот¬
реблять при ссылке на полную подструктуру, определяемую
кодословом 5.
На рис. 2 представлено гипотетическое, во многом упро¬
щенное состояние системной памяти, содержащей две про¬
граммы. Кодослова Р и Q самого высокого для этих про¬
грамм уровня принадлежат набору, определяемому главным
кодословом [/. Предполагается, что Р состоит из единствен¬
ного блока команд в соответствии с неймановским представ¬
лением о линейной структуре программной памяти. С дру¬
гой стороны, Q — структурная программа, состоящая из
шести компонент, и кодослово Q (вид 2, тип 8) ссылается на
набор кодослов, состоящий из шести элементов (т = 5).
Выбранная нами структура программы Q — это новое пред¬
ставление памяти, описанной в примере из гл. 1 (стр. 15).
Следует сравнить эти два представления. Заметим, что од¬
на из компонент (индекс 4) ссылается на пару кодослов Е и
F, определяющих буфера ввода-вывода, которые находятся
на более низком уровне, чем остальные наборы.
Теперь становится совершенно ясно, почему мы начали из¬
ложение с введения общего понятия древовидной структуры.
Во-первых, это простое и широко используемое понятие, реа¬
лизация которого не требует сложных технических разрабо¬
ток для внедрения в систему. Во-вторых, оно представляет
собой обобщение линейной памяти и можно предполагать,
что любые достижения в области распределения памяти для
традиционных машин будут с успехом использованы и при
Древовидной структуре памяти. В-третьих, такая структура
памяти обладает весьма желательными свойствами: она фак¬
тически бесконечна по объему и допускает изменение формы
представления. Наконец, в ней сравнительно легко обеспечи¬
вается выделение частей структуры, что очень важно для
реализации параллельных процессов; при этом подструктуры
обладают теми же общими свойствами, что и породившая их
структура: например, у каждой подструктуры есть свое «глав¬
ное кодослово», определяющее древовидную структуру со
своим порядком вычисления уровней.
!) В оригинале file. В дальнейшем для перевода этого термина будет
употребляться также выражение внешний массив. Прим. ред.

32
2. Некоторые родственные системы
Три уровня, на которых желательно так или иначе разде¬
лять память, проиллюстрированы при помощи схемы, изобра¬
женной на рис. 2.
Рис. 2. Древовидная структура программы.
(1) В мультипрограммной машине, чтобы отделить одну
программу от другой. В схеме — кодослова Р и Q.
(2) В отдельной программе, для разделения независи¬
мых наборов данных или команд. В схеме — А, В, С
и т. д. Наборы, разделяемые на этом уровне, принято
называть программными сегментами.
(3) В отдельном сегменте, для описания данных или ко¬
манд, которые могут естественным образом образо¬
вывать иерархическую структуру. В схеме — Еу F.
Изучим теперь условия, при которых можно использовать
разделение структуры. Информации, содержащейся в кодо-
слове (если его вид равен 2), достаточно для получения ад¬
реса (а, следовательно, и значения) любого элемента в на¬
боре, определяемом этим кодословом. Например, опираясь
на адрес £/, можно получить доступ к любому элементу па¬

2. Некоторые родственные системы
33
мяти. С другой стороны, нельзя добраться до кодослова S,
исходя из адреса элемента из набора S, т. е. двигаться по
схеме против направлений стрелок. Следовательно, опираясь
на кодослово Р, можно получить доступ только к элементам
из программы Я, и аналогично для Q. Отсюда следует, что
программы только тогда полностью разделены, когда из них
возможен доступ только к их собственным кодословам и не¬
возможен доступ к кодословам более высокого структурного
уровня.
Временную изоляцию некоторой подструктуры, как это
бывает необходимо при автономной переписи данных, мож¬
но обеспечить, присвоив виду кодослова, определяющего дан¬
ную подструктуру, значение 1. В этом случае любая попыт¬
ка получить доступ к изолированной области памяти при¬
ведет к прерыванию, которое исключит возможность доступа
до тех пор, пока вид кодослова не изменится. Обращаясь
опять к рис. 2, можно сказать, что таким способом кодосло¬
ва Е и F могут попеременно «защищаться» во время переда¬
чи данных.
Техника адресации в системе с древовидной структурой
находит свое отражение в методах написания программ. Если
задан символ 5, обозначающий адрес кодослова, можно оп¬
ределить последовательность значений индексов iu h, ...
..., ihy при помощи которой можно выбрать элемент, распо¬
ложенный на k уровней структуры памяти ниже относитель¬
но 5, если такой уровень существует. В Базовом языке такой
выбор задается выражением вида «S.i\.h	4», которое на¬
зывается составным именем с базой S. Если база выбрана
либо на уровне, либо ниже уровня кодослова данной про¬
граммы, ее автор не может сослаться на элементы, находя¬
щиеся за пределами своей области памяти; хотя в дальней¬
шем мы увидим, что существуют определенные ситуации, в
которых такие ссылки допустимы.
Характер вычислительной системы весьма сильно зависит
от того, какие формы составных имен допустимы: как за¬
даются базы и индексы, как реализована операция «точ¬
ка»1), какая наибольшая длина последовательности индек¬
сов (длина пути) допустима и какая вспомогательная ин¬
формация становится доступной в процессе обработки состав¬
ного имени. Решение этих вопросов влияет в свою очередь на
способ управления памятью и на ту степень гибкости,
которая предоставляется программисту в данной системе.
*) В оригинале dot. Эта операция порождается точкой, стоящей в со¬
ставном имени. Она связана с необходимостью выбора пути при ветвлении
дерева. Более точный ее смысл будет ясен из дальнейшего изложения. —
Прим. ред.
2 За к. 233

34
2. Некоторые родственные системы
В большинстве современных машин имеются весьма ограни¬
ченные древовидные структуры, но уже было сделано много
попыток создания более общих систем; они будут обсуждаться
в настоящей главе после краткого обзора альтернативной воз¬
можности— объединения каждой из составных программ в
единый блок памяти.
2.1.	Функции отображения памяти
Структурные особенности некоторой задачи, не находя¬
щие адекватного выражения в данной вычислительной сис¬
теме, приходится принимать во внимание и отражать в ко¬
мандах, выполняемых в процессе решения. В гл. 1 мы уже
говорили о процессе «погружения» структуры в программу.
Точнее говоря, это означает, что при помощи некоторой фор¬
мулы задается соответствие между каждой частью абстракт¬
ной (т. е. введенной для удобства решения задачи) струк¬
туры памяти и положением этой части в памяти вычисли¬
тельной машины. Интересно рассмотреть, что влекут за со¬
бой попытки погружения древовидной структуры в линейную
память. Если для обозначения элементов дерева используют¬
ся составные имена, задача состоит в отыскании функции
Loc(т]), где ц—составное имя, а значением функции являет¬
ся адрес в линейной памяти, т. е. номер ячейки, в которой
располагается элемент, обозначенный через ц.
Существует много различных способов для того, чтобы
объединять в блоки машинных слов элементы заданного де¬
рева, находящиеся на самом низком уровне, и размещать эти
блоки в линейной памяти. Если просматривать элементы де¬
рева в определенном порядке, местонахождение в памяти ма¬
шины любого набора можно определить, складывая длины
тех отрезков линейной памяти, которые требовались для раз¬
мещения наборов, расположенных на просмотренных рань¬
ше ветвях. Если данное дерево подчиняется какому-либо ло¬
кальному закону построения, суммирование можно оптимизи¬
ровать, заменив его вычислением по простой формуле, как
было сделано в гл. 1 (стр. 14). Выведенная там формула в
символике настоящей главы (пусть у обозначает матрицу
результатов) имеет следующий вид:
Loc («y.s.d») = f + 5*5* длина (у.0) + 5*d,	(2.1.1)
где значение / зависит от объема той части памяти, которую
занимают размещенные раньше наборы.
Вообще для любого правильного массива S размерности
k справедливо соотношение вида
Loc («S.i. Л2	//;») = а0 + a\ix + aj2 f ... -f aj.{, (2.1.2)

2.1. Функции отображения памяти
35
где а0 зависит от предшествующих элементов дерева, а
аи а2, . • • > ak получены из длин по каждому из измерений.
Выражения вида (2.1.1), (2.1.2) обычно называют «функ¬
циями отображения памяти» (SMF — сокращенное Storage
Mapping Functions). Ассемблер или транслятор, линеаризую¬
щий структуру, должен порождать SMF, согласующиеся с
правилами исходного языка, и вставлять команды, которые
реализуют соответствующие вычисления. Оптимизирующий
транслятор может достичь весьма значительных размеров,
так как должен уметь получать соответствующие (2.1.2) при¬
ращения при переходе от одной позиции памяти к другой,
чтобы избежать пересчета заново всех SMF. Если в момент
трансляции известны значения некоторых aj и (/=1,
.й), то такой транслятор также может вычислить отдель¬
ные части формулы.
Вообще SMF можно свести к двум частям: постоянной а
и переменной Ь. В традиционной машине переменная часть
вычисляется, когда возникает необходимость, и хранится в
регистре модификации X. Тогда, для доступа к нужным дан¬
ным, достаточно применить команду с адресным полем, со¬
держащим а, и кодом модификатора, соответствующим реги¬
стру X. Если для вычисления SMF применяются найденные
приращения, значение адресного поля может быть нулем
или небольшим целым числом; если переменная часть отсут¬
ствует, модификатор будет нулевым, а доступ к данным —
прямым при условии, что адресное поле достаточно велико
для указания а. В момент трансляции точный размер а обыч¬
но еще не известен, и то, что в командах, получаемых ас¬
семблером, должны быть отражены «худшие» случаи, может
привести к потере эффективности. Для повышения последней
можно применить механизмы косвенной адресации в сочета¬
нии с различными режимами модификации, но следует заме¬
тить, что они ничего не добавляют к характерным особен¬
ностям структуры памяти, представленной в виде единой по¬
следовательности одинаковых по размеру элементов.
Стоимость тех команд, о которых говорилось выше, т. е.
стоимость погружения структуры в программу, меняется в
зависимости от свойств машины и решаемой задачи. Если
размеры адресного поля достаточно велики, чтобы вместить
любое значение а, то с точки зрения эффективности програм¬
мирования не так важно, какой именно структуре команд от¬
дано предпочтение; но если адресное поле сравнительно не¬
велико, использование относительного взаиморасположения
становится весьма важным для достижения эффективного
кодирования команд. Однако важнее всего то, что подобная
техника погружения применима только к фиксированным,
2*

36
2. Некоторые родственные системы
правильным структурам данных с элементами одинаковой
длины, когда предшествующие элементы дерева занимают
фиксированный объем ферритовой памяти и когда выбран¬
ный операнд определяет один элемент данных.
Кроме того, выражения SMF в такой форме, как они оп¬
ределены в (2.1.2), имеют смысл только при условии, что
значения индексов удовлетворяют следующим соотношениям:
О ^ 1Х < длина (S),
0</2< длина (S.ix),
длина (SJ{J2 h-\\
(2.1.3)
Поэтому вычисление выражений (2.1.2) должно сопровож¬
даться проверкой, удовлетворяются ли соотношения (2.1.3),
На практике это настолько увеличивает время счета, что
включение таких дополнительных проверок обычно остав¬
ляют на усмотрение программиста. Вытекающие отсюда за¬
траты времени на программирование и устранение ошибок
точно не известны, но почти наверняка велики.
Можно было бы сделать вывод, что об использовании
SMF нельзя сказать ничего хорошего и что они будут со
временем забыты. Такое мнение столь же неразумно, как и
намерение твердо придерживаться неймановского принципа в
конструировании машин. Дело в том, что структуры с постоян¬
ными границами изменения индексов или с такими индексами,
что для их значений легко доказать соблюдение соотношений
(2.1.3), используются (хотя бы локально) в очень многих
задачах, а при соблюдении перечисленных условий выраже¬
ния для SMF необычайно сокращаются (почти исчезают) и
представляют собой лучший способ решения проблемы. Ме¬
тоды, используемые для отображения структуры в единую
линейную память, точно так же можно применять и к от¬
дельным наборам данных; в этих случаях SMF скорее по¬
рождают не значения индексов, а номера ячеек. Совсем в
стороне от задач, в которых использование SMF в указан¬
ных целях напрашивается само собой, стоят задачи, в кото¬
рых подобные функции применяются в некоторых языках для
определения структур [5], что является новым аргументом в
пользу сохранения SMF. Наконец, будет показано, что при¬
менение SMF не ограничивается сферой представления дре¬
вовидных структур и что эти функции широко используются
при работе с данными, имеющими сложную локальную взаи¬
мосвязь, так что, несмотря на общие недостатки этих функ¬
ций, они будут и в дальнейшем отражаться в системах ко¬
манд,

2.2. Вычислительная машина университета Риса
37
2.2.	Вычислительная машина университета Риса
До 1958 года появились по меньшей мере два важных
принципа программирования. Первый заключался в том, что
для развития программ использовалось разделение их на
сегменты; это позволяло исправлять и перетранслировать от¬
дельные части программы, не прибегая к перетрансляции
всей программы целиком. Метод загрузки, или объединения
программ, позволил эффективно осуществить этот принцип.
При этом величины а, используемые в SMF, вычисляются и
заносятся в память в машинные команды непосредственно
перед их выполнением. Второй принцип тесно связан с язы¬
ками обработки списков [6]: в них структура памяти должна
рассматриваться как некоторое понятие, не зависящее от ма¬
шинных команд и данных, определение которого дается в об¬
щей, абстрактной форме. Было естественным попытаться
приложить второй принцип к первому [41; полученные при та¬
кой попытке результаты оказали значительное влияние на
структуру Базовой машины.
Вычислительная машина Rice не является мультипро¬
граммной, и введение древовидной структуры памяти мотиви¬
ровалось необходимостью представления структур только на
уровне сегментов и ниже. Кодослово в ней кроме информа¬
ции, описанной раньше, содержит
«внешнее» значение индекса с, используемое программи¬
стом для ссылки на первый элемент набора, и адрес мо¬
дификатора X.
Местоположение набора в ферритовой памяти указывает¬
ся при помощи запоминания в кодослове номера ячейки b,
в которой хранится первый элемент, причем этот номер
уменьшен на величину с. Основная операция «точка» состоит
<5[Ш
/7?ГХ
Кодослово
Вычислительная
машина Rice
Описание блока
с+т
в том, что, исходя из кодослова S, надо сделать один шаг и
получить адрес /-го элемента набора, определяемого этим
Кодословом. Операция выполняется так: сначала значение

38
2. Некоторые родственные системы
индекса i загружается в модификатор, выбираемый при по¬
мощи адреса X; затем происходит обращение к кодослову S;
результатом является номер ячейки b—с + i. (Таким обра¬
зом, значение индекса, равное с, приведет в результате к ячей¬
ке Ьу в которой находится первый элемент.) Однако, если по
значению типа t видно, что набор состоит из кодослов, эта
адресная операция автоматически вызывает продвижение еще
на один шаг. Вообще говоря, на новом уровне по кодослову
будет выбран следующий модификатор, который к этому вре¬
мени должен быть загружен. Так будет продолжаться до тех
пор, пока значение типа t не укажет, что удалось добраться
до набора команд или данных. Проверка, лежит ли значение
индекса i в области
с ^ i ^ с + т,
не производится, так что операция «точка» не всегда ведет к
правильному результату, хотя можно установить значение
вида кодослова g таким, чтобы вызвать прерывание и произ¬
вести сравнение при помощи его интерпретации.
Недостаток этого процесса в машине Rice состоит в том,
что используемые на каждом структурном уровне значения
модификаторов нужно присваивать им заранее. При обыч¬
ном программировании можно употреблять только простые
правила присваивания значений, так что ошибки, связанные
с пересечением значений модификаторов, здесь почти неиз¬
бежны. Некоторое неудобство есть и в том, что индексное
значение определяется раньше, чем адрес кодослова S; на
практике чаще принято считать S постоянным, a i — пере¬
менным, чем наоборот.
После того как описания наборов формализованы, можно
ввести в систему команд вычислительной машины операции
над этими наборами. Основные операции над структурами,
осуществляемые при помощи системы управления памятью
вычислительной машины, позволяют создавать и уничтожать
наборы и вставлять в них (или удалять из них) элементы.
Методы реализации ввода, вывода и арифметических опера¬
ций над матрицами и векторами получаются при этом как
прямое следствие [7], а язык, употребляемый для работы на
машине, широко использует древовидную структуру. В вы¬
числительной машине Rice все такие операции выполняются
в режиме интерпретации; однако, поскольку «нескалярные»
величины распознаются уже на уровне разработанной моде¬
ли, они могут быть аргументами машинных команд. Выпол¬
няются эти команды непосредственно «аппаратным оборудо¬
ванием» или нет — не имеет значения для рассмотрения са¬
мой модели,

2.2. Вычислительная машина университета Риса
39
Дерево памяти основывается на двух наборах кодослов,
а именно «базе системы» и «базе программы». Первый набор
определяет таблицы и стандартные программы, постоянно хра¬
нящиеся в системе, многие из них доступны пользователю.
Второй набор определяет данные и команды одной выпол¬
няемой в данный момент программы. К элементам базы об¬
ращаются по символическим именам, которые выбирает
программист; для связи этих имен с базовыми индексами ор¬
ганизуются две таблицы. База системы занимает в памяти
фиксированное место, и поэтому, обращаясь к ней, удобнее
использовать номер ячейки, а не «главное кодослово», База
“| Команды
I
Таблица
связей
База
программы
Р и с. 3. Использование таблицы связей.
программы является элементом системной базы со значением
индекса, равным 82 (см. рис. 3). Поэтому составное имя вида
S.i{J2	(2.2.1)
переводится ассемблером в последовательность команд, со¬
ответствующих вычислению выражения
г'о-Мг,	(2.2.2)
если индекс S в базе системы равен to, или вычислению вы-
ражения
82 J0Jl.i2y	(2.2.3)
если 5 находится в базе программы. Нужно, однако, принять
во внимание тот факт, что в любой системе, допускающей
разделение на сегменты, значение i0 (если S находится в ба¬
зе программы) может быть еще неизвестно в момент транс¬
ляции составного	имени, базирующегося	на	«5».	Поэтому
Удобно	все	ссылки на	базу программы	из	сегмента,	содержа¬
щего команды, реализовать через «таблицу связей», распо-

40
2. Некоторые родственные системы
ложенную в конце сегмента; в этой таблице имеется место
для каждого элемента, на который может произойти ссылка
(см. рис. 3). Таблица связей заполняется во время загрузки
сегмента. Строка таблицы, относящаяся к S, содержит сим¬
волическое имя «5» и адрес, эквивалентный выражению
«82д'о», так что длина пути, ведущего от машинной команды,
равна длине пути в (2.2.2).
Основное, бросающееся в глаза неудобство древовидной
структуры памяти — большое число отдельных шагов, необхо¬
димых для доступа к элементу информации. Средство избав¬
ления от этого недостатка напрашивается само собой — об¬
разование баз на самых нижних уровнях структуры. В при¬
менении к вычислительной машине Rice это просто означает,
что программисту разрешено самому вычислять адрес ячей¬
ки, в которой расположен один из элементов, и изменять его
для получения доступа к соседним элементам путем алгеб¬
раического прибавления к этому адресу небольших по мо¬
дулю целых чисел.
Подобным же образом работает регистр управления: ад¬
реса, используемые для передачи управления и обращения
к данным внутри сегмента, вычисляются относительно зна¬
чения управляющего регистра, и, таким образом, сегменты
программ не зависят от своего местоположения в памяти.
Тогда повторяющиеся действия над наборами будут програм¬
мироваться обычным образом. Такими средствами можно
долю обращений к памяти, вызванных продвижением по де¬
реву памяти, сократить до 5—10%. За это мы расплачиваем¬
ся тем, что структура памяти иногда становится частично
зависимой от номера ячейкиу что порождает ограничения и
на определения наборов, и на хранение ссылок, и на использо¬
вание параметров; эти ограничения в свою очередь неприят¬
ным образом отражаются на реализации используемых для
данной машины языков программирования.
Хотя совокупность всех перечисленных выше ограничений
оказывается много меньше тех, которые имеются при исполь¬
зовании традиционной системы памяти, первым не хватает
простоты формулировки — нельзя просто сказать: «Ты не
должен...» Поэтому важно постараться избавиться и от этих
ограничений.
Изучая машину Rice, можно извлечь еще один полезный
урок. Описываемая система запрещает хранить кодослова в
наборах, содержащих команды, так как работа с кодослова-
ми в этом случае неэкономична. Поэтому любая величина
с явно заданной структурой должна трактоваться как «внеш¬
няя» по отношению к последовательности команд, даже если
она логически является «внутренней» для данного набора или

2.3. Вычислительная машина Burroughs В5000
41
если ее использование локализовано в нем. Неверно в прин¬
ципе устанавливать искусственные отношения между двумя
независимыми понятиями, что в этом случае лишний раз под¬
тверждается на практике. Возможность иметь структурную
информацию внутри сегмента важна не только для достиже¬
ния единообразия при программировании, но и для того, что¬
бы повысить эффективность работы системы путем умень¬
шения необходимого дробления памяти. В описание Базо¬
вой машины вводится понятие относительного кодослова, ко¬
торое служит этой цели.
В течение последних лет появилось несколько сообщений
о различных реализациях древовидной структуры памяти в
вычислительных машинах в условиях монопрограммной ра¬
боты; среди них EULER [8], ICES [9], система SPAN [10] и
JOSS [11], причем JOSS особенно хорошо иллюстрирует ис¬
пользование оперативного управления структурами. Все эти
реализации базируются на обычных машинах, так что их эф¬
фективность, измеряемая скоростью выполнения, невысока.
Они интересны с точки зрения изучения свойств языков про¬
граммирования, необходимых для управления составными
именами, прерываниями, использованием типов и операциями
над внутренними массивами. Динамическую древовидную
структуру памяти можно обслуживать без особых затрат в
отличие от систем обработки списков. Это объясняется тремя
основными причинами:
(1) количество независимых блоков памяти сравнитель¬
но невелико;
(2) единственным типом ссылок, которые требуют особой
обработки, являются сами кодослова (если местопо¬
ложение базы программы не меняется, не нужно из¬
менять таблицы связей); и, наконец,
(3) если обычные методы отображения структуры памя¬
ти удобны, их можно использовать и в рамках дре¬
вовидной структуры. Следовательно, можно дока¬
зать, что затраты на организацию и содержание дре¬
вовидной структуры памяти не являются полностью
«накладными расходами», потому что программист
может останавливать свой выбор на древовидной
структуре памяти только в тех случаях, когда это
дает ему какие-либо преимущества.
2.3.	Вычислительная машина Burroughs В5000
Первой коммерческой вычислительной системой, использо¬
вавшей древовидную структуру памяти, была машина Bur¬
roughs В5000, название которой часто упоминают и в связи

42
2. Некоторые родственные системы
с использованием стековой памяти для хранения операндов
[3]. Это, вероятно, единственная машина, использующая в ка¬
честве языков программирования почти исключительно языки
высокого уровня (варианты Алгола, Кобола и Фортрана).
В дальнейшем мы рассмотрим, как сказались эти свойства на
особенностях конструкции системы, но сейчас важнее отме¬
тить, что подробную информацию о технике программирова¬
ния на языке такой машины получить трудно. Последую¬
щее краткое описание несколько упрощено для того, чтобы
сконцентрировать внимание на структурных аспектах ма¬
шины; при изложении материала используется терминология,
введенная раньше при описании вычислительной машины
Rice.
Применение древовидной структуры памяти мотивируется
необходимостью отделять программы одну от другой в муль¬
типрограммной вычислительной машине, различать сегменты
внутри одной программы, в частности автоматически защи¬
щать отдельные сегменты на время обмена с периферийным
устройством и автоматически объединять барабаны и ферри-
товую память системы в «память одного уровня». Сравни¬
тельно мало внимания уделяется подструктуре сегментов. Па¬
мять системы можно рассматривать как множество кодослов,
каждое из которых определяет базу программы. Однако на¬
боры элементов любой базы представляют собой смесь из
числовых данных и кодослов, различающихся при помощи
специального поля размером в один бит. Это поле, имею¬
щееся в каждом слове, задает вид элемента. Кроме обычной
информации, кодослова содержат поле начальной позиции d
размещения каждого набора в барабанной памяти.
9
V
Числовой элемент
Burroughs В5000
9
t
d
m
b
Кодослово
В машине со стековой памятью те операнды, которые по¬
мещаются в вершину стека, автоматически «проталкивают»
вниз элементы, уже находящиеся в стеке. Все арифметические
операции выполняются над двумя верхними элементами сте¬
ка. В В5000 их называют регистрами А и В, причем А рас¬
положен в стеке выше, чем В. Команды машины либо опре¬
деляют операцию над подразумеваемыми операндами из А и
В, лцбо следующим образом загружают регистр А;

2.3. Вычислительная машина Burroughs В5000
43
(a) целым числом; или
(b) адресом элемента базы программы; или
(c) значением элемента базы программы.
Однако, если в случаях (Ь) и (с) элементом базы является
кодослово S и регистр В содержит число i, результатом при¬
менения команды может быть соответственно:
(Ь') адрес элемента 5 . i,
(с') значение элемента S.i.
Продолжить процесс выбора элемента так, как требует вы¬
ражение S.ii, i2, непросто.
Основная операция «точка» включает проверки: является
ли базовый элемент S кодословом; находится ли множество,
на которое кодослово ссылается, в ферритовой памяти и за¬
щищено ли оно; является ли индекс i положительным и не
превышает ли он верхней границы т. Если набор находится
не в ферритовой памяти, а на барабане, должно быть найде¬
но место в ферритовой памяти, куда этот набор переписы¬
вается, после чего выполняемая команда повторяется. Если
набор защищен, выполнение команды приостанавливается до
тех пор, пока перепись данных не будет закончена. Если зна¬
чение индекса не попадает в допустимые границы, печатает¬
ся сообщение о нарушении границ памяти. Таким образом,
интерпретация значений gum аппаратным оборудованием
машины обеспечивает задуманную при разработке системы
защиту сегментов и наборов и объединение барабанной и
ферритовой памяти.
Было показано, что можно сформировать и поместить в
стек адрес некоторого элемента массива, обозначаемого вы¬
ражением S.i, и затем начать перепись на периферийное
устройство данных, включающих S, сохраняя во время перепи¬
си адрес S в стеке и не защищая набор S. Чтобы избежать
при этом неверных результатов, достаточно просмотреть все
элементы стека в поисках адресов, ссылающихся на набор 5,
и установить в них значение вида, вызывающее прерывание
при обращении к этим элементам. Однако могут быть априор¬
ные соображения, позволяющие сделать вывод об отсутствии
в стеке таких элементов: в программах, сгенерированных при
помощи языков высокого уровня, режим использования стеков
часто отличается от обычного тем, что в момент обращения
к командам ввода или вывода используемых в этих коман¬
дах адресов уже не остается в стеке, а в случае необходи¬
мости, адрес элемента S.i вычисляется заново по адресу ко¬
дослова; во многих других случаях, прежде чем переписы¬
вать данные, их нужно напечатать, объединить в блоки или

44
2. Некоторые родственные системы
как-то иначе обработать при помощи отлаженных системных
стандартных программ, тогда области, участвующие в пе¬
реписи, будут недоступны программе пользователя. Следова¬
тельно, можно сделать такой общий вывод: было бы необос¬
нованно просматривать стек и защищать адреса, если про¬
граммист этого не потребует; желание же воспользоваться
таким режимом может возникнуть при отладке части про¬
граммы.
В связи с любыми изменениями в структуре или с физиче¬
ской реорганизацией памяти возникают более серьезные про¬
блемы, которые заключаются в том, что для реализации из¬
менений может потребоваться, чтобы программы управления
памятью нашли все адреса, указывающие на набор S, и за¬
менили их на новые. Поэтому очень важной становится воз¬
можность просмотреть стек, содержащий программу, и вы¬
делить в нем адреса, указывающие на данную область па¬
мяти. Насколько это важно и по другим соображениям, будет
показано в гл. 5. но на примере системы В5000 можно лиш¬
ний раз убедиться в том, что употребление обычных языков
высокого уровня может привести к упрощению запросов па¬
мяти. Например, в языках Кобол и Фортран наборы (т. е.
массивы и подпрограммы) никогда не меняют структуры и
не уничтожаются до тех пор, пока не закончится программа,
а в этот момент стек тоже уничтожается.
Помеченная память !)
Введение набора, каждый элемент которого имеет свое
собственное значение вида, ликвидирует логическую брешь,
заделывать которую в вычислительной системе Rice приходи¬
лось программисту. Адресоваться к такому набору — как к
стеку, по примеру вычислительной машины Burroughs, или
более общим способом — вопрос независимый и отчасти вто¬
ростепенный. Использование этих наборов дает возможность
формировать последовательности элементов различного ти¬
па. Это важно для вводного языка, где такие объекты часто
возникают в виде списков «параметров». Это важно также
для конструирования машин, так как позволяет выгодно ис¬
пользовать группы центральных регистров общего назначе¬
ния в кодах команд, не принося гои этом в жертву защит¬
ные свойства правил интерпретации типов. В гл. 3 будет
показано, как те виды, которые были связаны с кодословами,
будут обобщены для удовлетворения более общих требова¬
ний.
!) Помеченной будем в дальнейшем называть такую память, каждый
элемент которой имеет свое собственное значение вида. — Прим. персе.

2.3. Вычислительная машина Burroughs В5000
45
Вычисление адресов
Вспомогательную память, которая необходима для зане¬
сения числовых результатов, можно задавать в виде набора
данных (тип 0); с адресами же все обстоит иначе, так как
вся запоминаемая адресная информация (тип 8) ограничена
кодословами, предназначенными для сохранения древовид¬
ной структуры. Возможность записывать на места кодослов
адреса или числовую информацию значительно увеличила бы
расходы по эксплуатации памяти. (При рассмотрении маши¬
ны В5000 было видно, например, что не так-то просто сфор¬
мировать адрес кодослова в базе программы.) Следователь¬
но, помеченная память является единственной областью, в
которой можно хранить промежуточные адреса. Для иллю¬
страции того, насколько важна такая возможность, обратим¬
ся опять к рис. 2 и рассмотрим вычисление адресов в буфере
Е, в котором составное имя «U.QA.O.i» базируется на ко-
дослове U. Можно допустить, что первые два шага, в резуль¬
тате которых мы получили «U.QA», сделаны командами вы¬
бора базы при помощи таблицы связей. От выбора элемента
в наборе Е нас отделяют еще две операции «точка»; ясно,
что, если для каждого значения i придется полностью повто¬
рять поиск с начала составного имени, процесс окажется ма¬
лоэффективным. С другой стороны, если бы постоянную часть
имени «U.QA.0» можно было вычислить и хранить в виде
адреса в регистре X, то пересчитывать заново пришлось бы
только «ХЛ». Еще удобнее вычислить заранее значение
«U.QA.0.0» как адреса первого элемента множества Е и зна¬
чение верхней границы, тогда просмотр буфера мог бы осу¬
ществляться последовательными модификациями адреса и
был бы сравним по эффективности с обычными методами вы¬
числений адресов.
Описанные выше методы получили полное развитие в Ба¬
зовой машине, у которой есть набор регистров, допускающих
прямую адресацию. В машине В5000 стековый механизм не
приспособлен для хранения промежуточных результатов, в
ней следует больше полагаться на пересчет адресов и ограни¬
чение используемой глубины дерева для того, чтобы длина
адресного пути была короче.
Совместное использование памяти
При выполнении двух или более программ в мультипро¬
граммном режиме возникает вопрос о том, могут ли они
пользоваться одними и теми же стандартными программами
или таблицами констант. Для того чтобы предоставить

46
2. Некоторые родственные системы
любым двух независимым программам такую возможность,
необходимо, чтобы разделяемая (т. е. используемая обеими
программами) информация была инвариантной, и, следова¬
тельно, аппаратное оборудование вычислительной машины
должно следить за выполнением режима «только чтение» для
разделяемых наборов.
В вычислительной машине В5000 такой режим невозмо¬
жен по отношению к наборам данных, однако для наборов
Р и с. 4. Разделяемая подпрограмма 5.
команд он вполне допустим, поскольку любая попытка полу¬
чить доступ к набору команд воспринимается как передача
управления первой команде набора. Таким образом, две
программы Р и Q могут разделять общую подпрограмму S,
принадлежащую третьей программе /?, так, как это изобра¬
жено на рис. 4. Целью такого разделения является исключи¬
тельно экономия места в памяти, логически же оно эквива¬
лентно наличию двух копий подпрограммы S, одной для Р и
другой для Q. Типовая ситуация состоит в том, что в про¬
грамме R объединяются несколько подпрограмм, каждая из
которых может одновременно использоваться несколькими
программами без лишних затрат памяти.
Использование разделяемой информации порождает ряд
следствий, справедливых для любой системы адресации. Оче¬

2.3. Вычислительная машина Burroughs В5000
47
видно, что процесс объединения, рассмотренный в разде¬
ле 2.1, не может быть применен одновременно к трем про¬
граммам, таким, как Я, Q и R, если необходимо оставить
только одну копию подпрограммы S. При применении режи¬
ма разделения памяти подразумевается, что адреса уже не
имеют тех простых арифметических свойств, которые при¬
сущи неймановской модели. Система кодослов позволяет до¬
статочно хорошо распознавать отдельные области памяти и
обеспечивает средства управления вычислением адресов, но
метод ссылок на другой объект, свойственный таблице свя¬
зи, нельзя, вообще говоря, приложить к такой программе,
как S. Рассмотрим случай использования программой S на¬
бора W рабочих переменных. Так как программа S инвари¬
антна, набор W должен быть определен по отношению к S
как внешняя величина и содержаться в базе каждой про¬
граммы, обращающейся к S. Таким образом, в каждой из
программ Р, Q и R будет собственный вариант 5, и при по¬
мощи метода ссылок должен быть выбран именно тот ва¬
риант W, который соответствует программе, обращающейся
к S в данный момент времени. Это можно сделать, например,
неявным образом выбирая некоторый элемент в базе текущей
программы.
Однако описанный выше механизм нельзя оставить в
прежнем виде, так как при этом нужно было бы вводить со
стороны в базу каждой программы входы для W и входы,
необходимые для всех других программ, употребляемых в
режиме совместного использования памяти. Для использова¬
ния весьма ограниченной группы часто употребляемых сис¬
темных подпрограмм можно было бы пойти по этому пути,
но для разрешения вопросов, возникающих в развивающейся
системе, он совершенно непригоден, так как базы стали
бы несоизмеримо большими и потому неуправляемыми.
Правда, на вычислительных машинах, допускающих много¬
уровневые структуры с небольшим количеством кодослов
высшего уровня, применение такого метода обошлось бы не
так дорого.
Наиболее общее решение состоит в динамическом обра¬
щении к таблице, связывающей такие символы, как W, с ин¬
дексами базы. Поскольку у каждой программы имеются свои
таблицы, значения индексов могут меняться от базы к базе
в соответствии с локальными требованиями. Это означает,
что доступ к W будет медленным, но, получив однажды адрес,
можно потом некоторое время хранить его в помеченной па¬
мяти, что позволит обращаться к W обычным образом. Про¬
блемы адресации помеченной памяти некоторым постоянным

48
2. Некоторые родственные системы
образом менее трудны и могут быть решены путем разумного
использования индексных регистров.
Методы совместного использования памяти оказали влия¬
ние на способы распределения и восстановления памяти. Об¬
ращаясь снова к рис. 4, заметим, что если физическое распо¬
ложение набора 5 в памяти изменится, адрес начала дан¬
ных в кодослове, определяющем S, и другие адреса, указы¬
вающие на набор S, должны быть также соответствующим
образом скорректированы. Этот процесс включает в себя
просмотр помеченных областей памяти, относящихся не толь¬
ко к программе R, но и к программам Р, Q, а также ко всем
остальным программам, которые могут использовать S.
2.4.	Схемы сегментирования
Было показано, что наибольшие затруднения при исполь¬
зовании памяти с древовидной структурой вызывает длина
составных имен. Разрешение вычислять и хранить адреса,
чтобы затем по ним обращаться к памяти, позволяет преодо¬
леть эти трудности. Поскольку адреса данных и ссылки на
точки программы содержат номера ячеек, нужно приписать
этим элементам определенное значение вида и хранить их в
памяти, чтобы в случае изменения структуры или физическо¬
го расположения дерева их легко можно было бы изменить.
Противоположным решением является уменьшение глуби¬
ны дерева (например, за счет пренебрежения структурой
подсегментов) и использование индексной формы представ¬
ления составных имен во всей программе. Каждое составное
имя вида S.ii приводится к базовому индексу i0l соответст¬
вующему 5, и сегментному индексу i\. Значение каждого ин¬
декса можно хранить в памяти как двоичный «адрес» со зна¬
чением 2(Н0 + ii, где 2? — максимум длины любого отдельно¬
го сегмента. Если допускается 2^ сегментов, то все адреса
имеют длину р + q битов, практически около 30 битов.
Адрес
элемента
сегмента
Механизм адресации таков: при каждом обращении к па¬
мяти io используется для выборки кодослова данного сег¬
мента, которое затем модифицируется значением индекса iu
чтобы получить адрес нужного элемента. Вычисленные на
промежуточных этапах адреса в дальнейшем никогда не ис¬
пользуются, их значения не сохраняются и поэтому особен¬
ной необходимости в помеченной памяти здесь нет, Меха¬

2.4. Схемы сегментирования
49
низм, воплощающий такой подход к организации «сегменти¬
рованной» памяти, был использован в конструкции ряда со¬
временных машин [12, 13]. Логические и практические след¬
ствия, вытекающие из использования этого метода, резко
отличаются от тех, которые вытекают из нашей системы адре¬
сации при помощи кодослов.
Как уже отмечалось, в системах, которые мы сейчас об¬
суждаем, дерево памяти имеет только один уровень ниже
базы программы, т. е. вся структура подсегментов должна
быть погружена в команды программ. Временную изоляцию
части структур можно осуществить обычным путем при по¬
мощи кодослов со значением вида 1 (прерывание), причем
это обеспечивает полную защиту, так как кодослово находит¬
ся на единственном пути, ведущем к данному сегменту. Сле¬
довательно, при использовании этого метода не нужны ни¬
какие специальные свойства помеченной памяти и относя¬
щиеся к ней правила программирования. Отсюда вытекают
два важных следствия.
Во-первых, используя только центральные регистры такой
вычислительной машины, невозможно автоматически устано¬
вить различия ни между адресами и данными, ни между раз¬
ными представлениями чисел. Это необходимо делать обыч¬
ным путем, при помощи кодов команд.
Во-вторых, несмотря на то что физическое распределение
сегментов в памяти может свободно меняться для обеспече¬
ния требований системы, изменения, допустимые внутри са¬
мих структур, сводятся к возможности присоединять или уда¬
лять элементы только на одном конце сегмента. Запрещает¬
ся вставлять или же удалять элементы как в самое начало
сегмента (т. е. перед первым элементом), так и внутрь на¬
бора. Для реализации такой возможности необходимо было
бы менять все адреса, которые затрагиваются данной опера¬
цией, что исключает возможность ее использования.
Метод связей между сегментами переносится прямо из
системы кодослов. В неделимых сегментах таблица связей
содержит индексы текущей базы программы. В разделяемых
сегментах некоторые индексы могут иметь фиксированные
значения для любой программы (в машине ICT Atlas более
половины номеров сегментов резервируются для нужд систе¬
мы). Однако, вообще говоря, ссылки сначала делаются в
символической форме. Такая ссылка превращается в индекс
базы текущей программы при помощи таблицы поиска; най¬
денное значение индекса сохраняется для прямого использо¬
вания в дальнейшем. Практически удобно условиться, что
два индекса сегментов (например, 1 и 2) зарезервированы в
каждой программе: первый — для ее таблицы символов, а

50
2. Некоторые родственные системы
второй —■ для набора, в котором хранятся ее индексы. По¬
следний организован на манер стека и управляется механиз¬
мами входа в подпрограмму и выхода из нее. Если в нем был
запомнен индекс ссылки на некоторый объект, то в момент
обращения к программе, которая сейчас выполняется, его
можно выбрать, адресуясь относительно вершины стека при
помощи выражения «2./». Причем сам адрес, соответствую¬
щий этому выражению, хранится в регистре-модификаторе.
Наиболее очевидный практический результат применения
механизма сегментации в системе адресации заключается в
том, что при каждой попытке получить доступ к памяти пе¬
ред тем, как будет найден хранящийся в памяти элемент дан¬
ных или команд, происходит обращение к базе программы.
Поэтому номинальный объем работы, необходимый в случае
простой памяти, удваивается; если же на сегментированную
структуру памяти накладывается механизм страничной памя¬
ти с постоянным размером листа, объем работ может воз¬
расти в три-четыре раза, а использование такой косвенной
адресации, какую требует таблица связей, может эту циф¬
ру удвоить.
В настоящее время в литературе по вычислительным ма¬
шинам встречается очень много статей, в которых предла¬
гаются способы уменьшения накладных расходов, вытекаю¬
щих от принятия различных схем сегментирования памяти;
одна такая схема в течение ряда лет успешно применяется
на машине ICT Atlas [13]. Сейчас очень мало известно о
том, насколько эффективны некоторые наиболее сложные
системы, разработанные для того, чтобы обеспечить возмож¬
ность разделения ресурсов, в частности разделения памяти.
Однако очевидно, что любая логическая схема связи, органи¬
зуемая между процессором и оперативной памятью, неиз¬
бежно приведет к небольшому замедлению доступа к памяти,
как бы хорошо она ни была разработана. Хотя общий эффект
от такого замедления может компенсироваться другими об¬
стоятельствами, попытки, направленные на то, чтобы вновь
приблизиться к нормальной скорости, требуют значительных
логических усилий, которые могли бы пригодиться в другом
месте.

3
БАЗОВАЯ МАШИНА
В этой главе рассматриваются центральные регистры,
система команд и правила управления последовательностью
выполнения действий в Базовой машине. Для обеспечения
защиты, увеличения скорости и большей общности в предла¬
гаемой модели, определяемой Базовым языком, конструкция
некоторых частей машины намеренно утаивается от пользова¬
теля. В машинах неймановского типа тем же целям служат
регистры приписки, особые области памяти и операции, кото¬
рые могут использоваться только в привилегированном режи¬
ме работы; однако в Базовом языке, как мы увидим, введение
«культа защиты адреса и команды» дает возможность приме¬
нять более изощренную тактику утаивания. Пока нам нужно
рассмотреть только работу отдельного центрального процес¬
сора Базовой машины, считая, что остальные ее части опре¬
делены традиционным образом.
Древовидная структура была предложена в первую оче¬
редь для того, чтобы отделять одну программу от другой и
различать отдельные сегменты внутри программы. Практиче¬
ски «кодослова программ» совершенно несущественны, и не¬
обязательно обеспечивать их распознавание непосредственно
при помощи аппаратного оборудования, поскольку структура
и использование базы программы позволяют обращаться к ней
при помощи адресации через таблицу связей.
Практика показывает также, что первоначальное понятие
дерева несколько видоизменяется в связи с наличием вычис¬
ляемых адресов, обеспечивающих прямой доступ к наборам
данных, команд и кодослов. Разграничение элементов дости¬
гается тогда путем управления адресами с помощью мони¬
тора и на основании свойств внутреннего языка машины, т. е.
системы команд, которую он определяет. И адреса, и команды
Должны храниться в памяти в таком виде, чтобы их можно
было различить, ибо только при этом условии возможно такое
представление программ на внутреннем языке. Таким обра¬
зом, возникает необходимость придумать какой-то формаль¬
ный способ распознавания команд и адресов и потребовать,
чтобы он был реализован аппаратно.
Оказывается, в точности такой же механизм необходим и
для того, чтобы обеспечить динамическое распознавание

52
3. Базовая машина
типов операндов и лишить большинство программистов воз-
можности локально оптимизировать свои программы, исполь¬
зуя их конкретное представление в коде машины. Таким
образом, описанные ниже соглашения помогают успешно ре¬
шить три основные задачи из числа тех, которые ставились
при разработке модели. Как часто бывает при проектирова¬
нии логических систем, стоит только включить в проект
какой-то элемент, исходя из одной или двух главных причин,
как возникают и другие изменения в конструкции, вызванные
стремлением полностью использовать появляющиеся при этом
возможности.
Следующие разделы посвящены менее общим свойствам
процессора Базовой машины. Во многих отношениях перед
проектировщиком Базовой машины стоит по существу та же
задача, что и при создании традиционной машины; мы не бу¬
дем обсуждать здесь эти вопросы, в частности не будем ка¬
саться роли центрального процессора в управлении перифе¬
рийными каналами ввода-вывода данных.
Для того чтобы детально продемонстрировать приемы
внутреннего представления команд, мы будем пользоваться
такими единицами информации: байт (8 битов), слово (32
бита) и двойное слово (64 бита). Преимущества использова¬
ния элементов памяти, размер которых кратен некоторым де¬
лителям размера слова, очевидны, но конкретная длина слова
не имеет принципиального значения для нашей системы. На
практике длина слова обычно определяется наиболее упо¬
требительными размерами данных. Предполагается, что все
наборы однородных элементов упакованы плотно, а поиск
элемента набора реализован так, что программист не должен
заботиться о границах слов и других физических параметрах
памяти.
3.1.	Представление вида и типа
на внутреннем языке машины
В Базовой машине используются два рода меток: код вида
для отдельных элементов и код типа для наборов однородных
элементов. Преимущество использования типов состоит в том,
что они требуют очень мало дополнительной памяти по отно¬
шению к содержательной информации, так как на практике
большая часть информации может быть организована в виде
наборов однородных элементов. В тех важных случаях, когда
внутри набора метки вида могут меняться от элемента к эле¬
менту, можно каждый элемент снабдить некоторым кодом
вида; такие наборы называются наборами смешанного типа.
Количество памяти, требуемое для хранения любого элемента

3.1. Представление вида и типа на внутреннем языке машины 53
набора, называется размером элемента; он зависит от типа
набора. Под любой элемент набора смешанного типа необхо¬
димо отводить поле максимального размера (в нашем случае
64 бита, включая вид).
В табл. 1 приведены коды видов Базовой машины (для
того чтобы можно было в дальнейшем увеличить число видов,
в формате данных под вид отведено 3 бита). Слова, представ¬
ляющие собой двоичные данные, которые участвуют в элемен¬
тарных арифметических и логических операциях, помечаются
значением вида, равным нулю. Если они выступают в качестве
арифметических величин, то рассматриваются как целые чи¬
сла, представленные в дополнительном коде. Сам код вида не
является частью целого числа; заштрихованная часть регистра
(см. рис. ниже) не используется.
Двоичное
слова
29
32
Вид 0
Вид 1 используется для обозначения элементов, непосред¬
ственное аппаратное распознавание которых невозможно, та¬
ких, например, как численный результат, выходящий за допу¬
стимый диапазон представления чисел, или как некоторый
неопределенный элемент. Если элемент с видом 1 оказывается
аргументом машинной операции, обычно происходит прерыва¬
ние и передача управления программе его обработки. Инфор¬
мация, передаваемая программе обработки прерывания для
интерпретации, включает в себя до 32 информативных битов
плюс код типа прерывания; программа обработки прерывания
может либо разрешить продолжение счета, либо передать
управление в заранее указанную часть программы. (В табл. 6
приведены коды типов прерывания.)
3
5
24
32
Вид
1
t
п
Тип
Иедействи-.
тельный
элемент
Видом 2 помечается адрес последовательности, состоящей
из m элементов данного типа и начинающейся с ячейки Ь
(т. е. b — адрес первого байта первого элемента последова¬
тельности). Адрес имеет следующий формат:
24
\6
<6
Вид j 2 I t \
I !.. Л.
Тип
m
Ячейка
Верхняя
граница
Адрес

54
3. Базовая машина
Если /?2 = 0, то говорят, что адрес «простой»1), поскольку он
указывает на последовательность, состоящую только из одного
элемента2). Максимальная длина любой адресуемой последо¬
вательности— 65 536 элементов любого размера. Значения
типа (/) приведены в табл. 2 и будут рассмотрены ниже. (Фор¬
мат адреса допускает увеличение числа различных типов до
тридцати двух.)
Класс чисел, представимых посредством числовых элемен¬
тов (вид 3), шире, чем в случае вида 0. Предполагается, что
целые числа входят в класс числовых элементов в соответ¬
ствии с традиционным представлением чисел «с плавающей
запятой». В настоящем контексте точный формат числового
элемента несуществен, но предполагается, что в арифметиче¬
ских операциях используется до 61-го бита.
Следует заметить, что командам не поставлен в соответ¬
ствие никакой вид:	невозможно (и нет смысла) извлечь
команду из программы в коде машины и произвести над ней
какие-нибудь операции. Ассемблер составляет программу
в коде машины в виде совокупности наборов двоичных слов
и, после того как они полностью построены, меняет описания
их типа на «команды». Это делается в специальном режиме
работы программами, управляющими памятью.
Типы, приведенные в табл. 2, следует сравнить с видами
из табл. 1. Вообще вид, который приписывается элементу при
выборке из памяти, определяется типом, указанным в его
адресе (это неверно лишь для типов 10 и 11, так как в этих
случаях вид содержится в самих элементах). Механизм до¬
ступа к памяти таков: при выборке элемента по адресу фор¬
мирование вида совмещается с перестройкой самого элемен¬
та; нет необходимости хранить элемент в памяти точно в та¬
кой форме, какую он принимает, будучи снабжен меткой вида.
Например, наборы, принадлежащие типам 0, 1, 2 и 3, поро¬
ждают элементы вида 0; при этом в случае байтовых элемен¬
тов (типы 1, 3) происходит расширение байта до 32 битов,
которое состоит в распространении знакового разряда. Исклю¬
чение составляют логические операции, для которых расши¬
рение состоит в распространении «нуля». Аналогично число¬
вые элементы могут храниться в памяти в длинном или
коротком формате; применение последнего позволяет вдвое
сократить объем памяти, требуемой для хранения данных
малой точности. Элементы, представимые в короткой форме,
образуют подмножество элементов вида 3.
!) В оригинале singular. — Прим. перев.
2)	Такую последовательность мы в дальнейшем для единообразия тоже
будем именовать «простой». — Прим. перев.

3.2. Кодослона
55
В случае наборов целых или числовых элементов и наборов
смешанного типа признаком того, что последовательность мо¬
жет использоваться только для чтения, служат отдельные ко¬
ды типов. Режим «только чтение» предназначен для защиты
постоянной информации; в этом отношении он полезен про¬
граммисту, так как защищает его от собственных ошибок, и
необходим для защиты данных, к которым обращаются неза¬
висимые процессы. Программист не может изменить признак
«только чтение», но он имеет возможность скопировать любой
набор и пользоваться копией по своему усмотрению. Наборы
команд имеют признак «только выполнение» по определению,
а код типа используется для указания различных режимов ра¬
боты, которыми распоряжается программист.
3.2.	Кодослова
Процесс получения адреса по элементу набора кодослов
(типы 8 и 9) называется «вычислением кодослова». Это осо¬
бенно важный пример того, как можно переопределить эле¬
мент перед тем, как его обрабатывать. Машинные операции
определены так, что невозможно заслать адрес обратно в на¬
бор кодослов, который поэтому можно рассматривать как на¬
бор с признаком «только чтение».
Обычно кодослово содержит ту же самую информацию, что
и адрес, указывающий на последовательность расположенных
в памяти элементов определенного типа. Термин «набор» при¬
меняется в случае последовательности, которая определена
кодословом. Вычисленный по кодослову адрес указывает на
ту же самую последовательность, но машинные операции над
адресами допускают адресацию подпоследовательностей ис¬
ходной последовательности. Отсюда следует, что последова¬
тельность, определенная адресом, есть всегда либо набор,
либо часть набора, но никогда не может выходить за его
границы. На этом факте основана система защиты памяти.
Если кодослово не содержит явной ссылки на набор, то его
вид равен 1, а его вычисление вызовет программную интерпре¬
тацию. Во всех остальных случаях вид кодослова равен двум.
Ячейка а
а + ъ
a+b+m
2\t\jn\ b
I
|	Относительное
I	пойослово

56
3. Базовая машина
Номер ячейки (6), содержащийся в кодослове, представ¬
ляет собой адрес памяти, либо заданный явно, либо вычис¬
ленный (в байтах) относительно ячейки, в которой находится
само кодослово. Этим двум возможностям соответствуют аб¬
солютное (тип 8) и относительное (тип 9) кодослова, причем
элементы определяемых ими наборов имеют одинаковый фор¬
мат1). Относительная форма кодослова удобна, если удается
разместить его в том же «блоке» памяти, что и информацию,
на которую оно указывает, поскольку программы распределе¬
ния памяти работают с блоками как с неделимыми объекта¬
ми, игнорируя всю их внутреннюю структуру.
Ассемблер Базового языка формирует относительные ко¬
дослова в процессе построения блоков. Блок устроен таким
образом, что в нем не может быть элементов типа 8, 10 или
11, а все относительные адреса указывают на содержание
того же блока. В относительных кодословах под m и Ь отве¬
дено по 12 разрядов, с тем чтобы они поместились в одном
слове. Таким образом, количество элементов относительного
набора ограничивается 4096, и начинаться такой набор дол¬
жен не далее чем в 4096-м байте после определяющего его
кодослова. Абсолютные наборы ограничиваются диапазоном
существующих адресов.
Обозначения, связанные с видами
Выполнение машинных операций сильно зависит от видов
аргументов и поэтому удобно ввести специальные обозначе¬
ния для различных комбинаций типов и видов. Вообще об
элементе, имеющем вид 2 и тип t (здесь не имеет значения —
адрес это или кодослово), говорят, что он имеет вид 2(t).
Таким образом, адрес последовательности байтов имеет вид
2(1) (или 2(3), если она имеет признак «только чтение»).
Объединив некоторые типы в классы, примем для элементов
вида 2 следующую систему обозначений:
вид 2 (N) — элемент указывает на последовательность целых
или на числовую последовательность (типы 0, 1
2, 3, 12, 13, 14, 15);
вид 2(1) — элемент указывает на последовательность команд
(типы 4, 5, 6, 7);
вид 2 (М) — элемент указывает на смешанную последователь¬
ность (типы 10, 11);
вид 2 (С) — элемент указывает на последовательность кодо¬
слов (типы 8,9).
9 То есть формат не зависит от того, ссылается на набор абсолютное
или относительное кодослово. — Прим. ред.

3.3. Распределение регистров
57
Аналогично вид 1 (t) соответствует содержимому регистра
или кодослову, вызывающим прерывание и имеющим тип t.
Так, адресу внешнего массива соответствует вид 1(7), и опе¬
рации, которые предназначены для работы с внешними мас¬
сивами, обычно требуют, чтобы один или несколько аргумен¬
тов принадлежали этому виду.
3.3.	Распределение регистров
В Базовой машине предусмотрена прямая адресация шест¬
надцати элементов. Обращение к ним осуществляется по име¬
нам: ХО, XI, .Х9, ХА, ..., XF, причем последние четыре
регистра используются в машине специальным образом. Обыч¬
но регистр применяется для временного хранения элемента,
снабженного видом, поэтому размер каждого регистра 64 бита;
форматы элементов, которые он может содержать, описаны
в разд. 3.1. Регистры как группа ячеек памяти эквивалентны
последовательности элементов смешанного типа. Для реали¬
зации Базового языка не требуется других непосредственно
адресуемых элементов. Как мы увидим в гл. 5, этого коли¬
чества регистров более чем достаточно.
Специальным образом используются следующие регистры.
Регистр текущей команды ХС. Регистр ХС содержит адрес
выполняемой команды и поэтому имеет вид 2(1). Значение
верхней границы в регистре ХС опущено, так как оно не имеет
особого смысла применительно к последовательности команд.
Код типа I указывает режим выполнения, а два других бита
с используются в качестве индикаторов условий, значение
которых можно проверять и которые устанавливаются машин¬
ными операциями.
Регистр
текущей
команды
Содержимое регистра ХС меняется при передачах управ¬
ления: при относительных передачах управления приращение
вычисляется и контролируется ассемблером, и поэтому не ну¬
жна проверка выхода за границы последовательности; абсо¬
лютные передачи управления происходят через адреса или
через кодослова вида 2(1), причем при выполнении операции
передачи управления проверяется вид, чтобы убедиться в кор¬
ректности перехода. При относительных передачах управле¬
ния I и с не изменяются; при абсолютных переходах, реали¬
зуемых через кодослово, в с заносится 0, а I устанавливается
в соответствии со значением типа в кодослове, определяющем
набор, на который осуществляется переход.
24
30
Вид 2

58
S. Базовая машина
Содержимое регистра ХС можно переслать в другой ре¬
гистр или в память программы для того, чтобы получить
связку1). В машине предусмотрены специальные операции,
передающие управление по связке. Хотя машинной операцией
значение регистра ХС можно устанавливать путем копиро¬
вания в него информации, в Базовом языке не отражено на¬
личия регистра текущей команды среди центральных реги¬
стров.
Регистр базы процесса XD. Идея отдельной базы програм¬
мы для каждой конкретной самостоятельной работы, харак¬
терная для систем, описанных в гл. 2, не реализована в Ба¬
зовой машине. Вместо этого для каждой независимой по¬
следовательности команд определена так называемая «база
процесса», представляющая собой разновидность помеченной
памяти. Адрес базы процесса содержится в регистре XD и
имеет вид 2(10).
В базе процесса различаются три отдельные области.
(a) Регистровая память. Первые шестнадцать элементов по¬
следовательности XD отождествляются с центральными ре¬
гистрами.
(b) Продолжение регистровой памяти. Элементы с индексами
больше 16 можно использовать для хранения копий значений
регистров. В Базовом языке продолжение регистровой па¬
мяти имеет символьную адресацию; значения индексов при¬
сваиваются транслятором. Длина этой последовательности
определяется для каждой самостоятельной работы в момент
ее образования и обычно составляет около 50 слов.
(c) Регистровый стек. За продолжением регистровой памяти
располагается последовательность переменной длины, орга¬
низованная в виде стека. Значение верхней границы в реги¬
стре XD определяет текущий размер стека. Предусмотрены
специальные операции для пересылки элементов с вершины
стека в центральные регистры и обратно.
Можно заметить, что в сущности регистр XD содержит две
базы адресации: одну — для регистров и продолжения реги¬
стровой памяти, и другую — для вершины стека. Физиче¬
ская верхняя граница последней отмечена особым элементом
стека.
Регистры прерываний ХЕ и XF. Чтобы обеспечить быстрое
выполнение действий по прерыванию, описанных в гл. 1, в
машине имеются два центральных регистра, предназначенные
для связи с интерпретирующими программами. Подробности
использования этих регистров сильно зависят от аппаратного
0 Связка — это форма, в которой запоминается адрес перехода.—
Прим. ред.

3.4. Правила обращения к памяти
59
оборуД°вания машины, рассмотрение которого выходит за
пределы описания нашей модели. Непривилегированные про¬
граммы, написанные на Базовом языке, не имеют прямого
доступа к регистрам ХЕ и XF, и действия в случае прерыва¬
ния, определяемые пользователем, должны быть описаны либо
в виде обычных операций над регистрами ХО—Х9, либо в ви¬
де особых операций над регистрами ХЕ и XF, задаваемых
специальными выражениями, которые распознаются трансля¬
тором. Регистры прерывания могут быть использованы также
для обеспечения быстрой реакции на определенные виды внеш¬
них событий, обрабатываемые программами пользователей
(включая изменения состояния периферийных устройств).
3.4.	Правила обращения к памяти
Машинные операции перерабатывают хранимую в памяти
информацию, используя адреса, содержащиеся в регистрах.
Несмотря на то что адрес обычно определяет несколько эле¬
ментов информации, операция выполняется только над пер¬
вым элементом последовательности, если в определении этой
операции нет специальной оговорки. Поэтому отдельный чи¬
словой операнд может быть представлен либо регистром с ви¬
дом 0 или 3, если регистр содержит сам операнд, либо реги¬
стром с видом 2(N), если он содержит адрес операнда. Во
всех арифметических операциях и операциях над адресами,
когда требуется числовое значение, оно автоматически полу¬
чается из аргумента вида 2 (N) выборкой первого адресуе¬
мого элемента с соответствующим ему кодом вида 0 или 3.
Такую интерпретацию аргумента мы будем называть автовы¬
боркой или правилом А/В. Оно неприменимо к аргументам
видов 2(C) или 2(1). В случае вида 2(М) первый адресуемый
элемент выбирается со своим кодом вида, тут же к нему при¬
меняется правило А/В, и, если нужно, этот процесс повто¬
ряется.
Большинство арифметических и логических операций
имеют по два аргумента и засылают полученный результат
на место первого из них. Если значение первого аргумента
было получено при помощи правила А/В, то результат дол¬
жен быть записан на место первого элемента последователь¬
ности заданного типа и поэтому должен быть представим
как элемент того же типа. Вообще результат с видом 3 пре¬
образуется в формат целого числа перед занесением его
в последовательность с типом 0 или 1, а результат с видом О
преобразуется в элемент с видом 3 перед занесением его в по¬
следовательность с типом 12 или 13. В случае типов 1 и 13
необходимо некоторое усечение результата; в первом случае

60
3. Базовая машина
в результате арифметических операций теряются старшие
разряды, и если они не нулевые, то вырабатывается сигнал
о некорректном результате. Записи в последовательности с ти¬
пами 2, 3, 14 или 15 не происходит, так как эти последователь¬
ности предназначены только для выборки. Приведенные вы¬
ше правила записи в последовательность применяются авто¬
матически, когда вид первого аргумента арифметической
функции 2(N). Мы будем называть их автозаписыо, или пра¬
вилом А/3. Они не применяются к аргументам с видами 2(C)
и 2(1). Для копирования значений регистров в наборы сме¬
шанного типа предусмотрены специальные команды.
3.5.	Правила последовательности выполнения команд
После выполнения команды к содержимому регистра
управления ХС обычно прибавляется столько байтов, сколько
нужно, чтобы получить очередную команду последователь¬
ности. Передачи управления внутри последовательности осу¬
ществляются путем сложения содержимого регистра ХС
с относительным номером ячейки (с учетом знака). Програм¬
ма-ассемблер осуществляет необходимые проверки, с' тем
чтобы в результате обычной последовательности выполнения
или при передачах управления не произошло нарушения гра¬
ниц памяти. Относительные переходы могут делаться в зави¬
симости от состояния индикаторов условий с (содержащихся
в регистре управления ХС) или от значения, содержащегося
в заданном регистре.
Можно передавать управление любому элементу с видом
2(1), играющему роль связки. Заметим, что связка не может
быть модифицирована, поскольку программисту неизвестны
форматы команд; но в ассемблере специально предусмотрена
возможность построения наборов относительных кодослов, об¬
разующих своеобразные переключатели. В тех случаях, когда
элемент, на который передается управление, определяется ад¬
ресом с видом 2(1), к командам перехода применяется прави¬
ло, аналогичное автовыборке.
Связки с метками
Предусмотрена возможность запоминания в регистровом
стеке связки вместе с меткой а, которая может иметь целые
значения в диапазоне от 0 до 7.
Связка (в стеке)
24
Вид
3 2

3.5. Правила последовательности выполнения команд
61
Машинная операция RET (возврат) просматривает стек
с вершины в поисках связки, метка которой не меньше задан¬
ной в команде величины, одновременно уменьшая значение
верхней границы стека в XD. Когда связка найдена, она уда¬
ляется из стека, и выполняется соответствующая передача
управления. Поскольку операционная система записывает в
начало стека связку с меткой 7, поиск в стеке всегда заканчи¬
вается успешно. Любые другие попытки выбрать такой эле¬
мент вызывают определенную реакцию монитора.
Такие метки и правила работы с ними предназначены для
того, чтобы дать возможность устанавливать в стеке иерар¬
хию точек, с которой можно синхронизировать последователь¬
ность передач управления, не рассматривая промежуточных
результатов. Типичными примерами таких управляющих точек
являются выходы из подпрограмм, повторные входы в про¬
грамму и выходы в случае ошибки. Связку можно также за¬
помнить в регистре, а потом скопировать в стек; в этом слу¬
чае ее метка равна 0.
Прерывания
Возможность нормального выполнения операции зависит
от видов, типов и значений ее аргументов. Причины аварий¬
ных ситуаций могут быть классифицированы следующим об¬
разом:
(a) Недопустимый вид аргумента. Операция не определена
для данных комбинаций видов и типов ее аргументов. Сюда
относится, например, случай, когда арифметическая операция
применяется к регистру с признаком вида 2(C) или когда
один или оба аргумента имеют вид 1.
(b) Некорректный результат. Результат выходит за пределы
диапазона представимых в машине чисел; например, в слу¬
чае арифметического переполнения.
(c) Не проходит А/3. Усеченная по правилу автозаписи вели¬
чина потеряла некоторые существенные разряды; например,
при засылке целого числа, большего 127, на место, предна¬
значенное для байта.
При обнаружении ошибки дальнейшие действия зависят
от соглашений локального характера. Недопустимый тип ар¬
гумента всегда влечет за собой уход на набор системных или
Указанных пользователем программ, которые в зависимости
от конкретных условий либо продолжат вычисления, либо
обеспечат аварийный выход из программы. Некорректные ре¬
зультаты могут быть представлены как элементы с видом 1
(ср. табл. 6) или без прерывания программы, или вызывая
прерывание для обработки ошибок, в зависимости от режима.

62
3. Базовая машина
установленного программистом. Если результат представляет
собой элемент вида 1, программист может обрабатывать его
немедленно, проверив индикаторы условий, или позднее, про*
верив код вида результата; таким образом можно использо¬
вать преимущества как «машинного», так и «программного»
обнаружения переполнения.
Режимы
В Базовой машине имеются два указателя режимов общего
назначения. Первый — о нем мы уже упоминали — управляет
реакцией на некорректный результат (IR). Второй обеспечи¬
вает возможность трассировки1); он может проверяться спе¬
циальной машинной командой (JNT) и используется для того,
чтобы организовать избирательный вывод промежуточных ре¬
зультатов, связок и значений регистров с использованием раз¬
личных способов интерпретации, соответствующих структуре
программы и символике Базового языка2). Индикаторы усло¬
вий и указатели режимов запоминаются в виде частей связки.
Поэтому они восстанавливаются при выполнении соответст¬
вующей передачи управления. При переходе в новую последо¬
вательность команд через кодослово режим последней «сме¬
шивается» 3) с текущим режимом, т. е. если при выполнении
перехода через кодослово действует режим трассировки (или
IR), то он сохраняется, каково бы ни было значение I в ко-
дослове.
3.6.	Выбор системы машинных команд
Рассмотрим главные факторы, влияющие на выбор системы
команд Базовой машины. (Выбранные для них названия взя¬
ты из Базового языка в тех случаях, когда они подходили по
смыслу, но каждую команду следует понимать как операцию,
которой соответствует свой числовой код.) В принципе осно¬
ванием для аппаратной реализации команды является ча¬
стота ее употребления или соответствие ее принятым методам
генерации команд, но на практике почти все время процес¬
сора занимает выполнение очень небольшого числа часто
встречающихся команд, и именно «простота использования»
обычно является определяющим фактором при выборе ко¬
манд. Поэтому для рассматриваемого нами Базового языка
традиции программирования имеют решающее значение.
1) Трассировка — контроль «трассы» при выполнении программы.—
Прим. пер ев.
2) Список команд с расшифровкой сокращений приведен в табл. 3 г
конце книги. — Прим. ред.
3) То есть логически складывается.— Прим. перев.

3.6. Выбор системы машинных команд
63
Алфавитный список команд приведен в табл. 3. Они раз¬
деляются на четыре группы:
группа А: арифметические и логические операции;
группа В: операции над базой;
группа С: операции управления;
группа D: операции над адресами.
Большинство команд имеет по два аргумента; при выпол¬
нении команды результат записывается на место операнда,
определяемого первым аргументом, а в регистре ХС могут
устанавливаться индикаторы условий. На Базовом языке код
операции принято писать между первым и вторым аргумен¬
тами. Например, команда
ХЗ ADD Х5
выполняется так: операнды для сложения выбираются при
помощи регистров ХЗ и Х5, результат засылается на место
первого операнда.
Арифметические и логические операции (группа А)
Большинство операций этой группы не требует объяснений
при той степени подробности изложения, которая нас здесь
интересует. Правила автовыборки и автозаписи применяются
к обоим аргументам, а индикаторы условий устанавливаются
в зависимости от знака и величины результата. Например,
операция ADD может быть использована для сложения двух
любых числовых или целых элементов любого размера, т. е.
вместо любой из 64 «операций сложения», которые понадоби¬
лись бы, если бы каждой возможной комбинации длинных и
коротких операндов и адресов соответствовал свой код опера¬
ции. Если происходит переполнение, то вырабатывается при¬
знак некорректного результата, который может вызвать пре¬
рывание, как описано в разд. 3.5. (Результат сложения двух
Целых чисел всегда может быть представлен как элемент вида
3 и не должен считаться некорректным до тех пор, пока не
будет сделана попытка заслать его в последовательность це¬
лых чисел.) Перемещения элементов в памяти с учетом видов,
которые имеют операнды, выполняются при помощи операции
MOVE, которая выполняет все необходимые преобразования
Для того чтобы проверить точность целого или числового ар¬
гумента, прежде чем пытаться записать его в память, преду¬
смотрена операция SIZE. Для операндов вида 3 логические
операции (AND, NEQ, NOT, OR, SHIFT) не определены.

64
3. Базовая машина
Операции над базой (группа В)
Операции над базой предназначены для перемещения эле¬
ментов, снабженных видом, с одного места на другое без ин¬
терпретации, которая подразумевается в других группах опе¬
раций. Базовые операции можно применять к последователь¬
ности смешанного типа вообще, и в частности к самой базе
процесса, адрес которой находится в регистре XD. Так, опе¬
рация COPY используется для переноса содержимого одного
регистра (полностью) в другой, какими бы ни были до этого
их виды. Команда RF переносит первый элемент смешанной
последовательности в заданный регистр. Команда RS записы¬
вает содержимое указанного регистра в качестве первого эле¬
мента заданной последовательности, имеющей тип 10. В этих
случаях правила автозаписи и автовыборки не применяются.
Доступ к регистровому стеку осуществляется при помощи
операций DUMP и UNDUMP; в качестве операндов задают
произвольную группу регистров из имеющихся шестнадцати,
содержимое которых требуется перенести в стек (DUMP) (или
наоборот (UNDUMP)), начиная с текущей вершины, указан¬
ной в регистре XD. Признаком того, что стек переполнен или
исчерпан, служат ненулевые метки, находящиеся в первой и
последней позициях стека; кроме того, при выполнении опе¬
рации UNDUMP ненулевая метка в любой позиции вызывает
определенную реакцию монитора.
При засылке в регистровый стек регистры, указанные в ко¬
манде, переписываются в него в порядке возрастания номе¬
ров, а при чтении из стека его содержимое передается на ре¬
гистры в обратном порядке; для того чтобы организовать ка¬
кой-нибудь другой порядок перебора регистров, потребуется
более одной команды.
Для обращения к постоянной базе системы из привилеги¬
рованных программ и для программирования обращений к
системным подпрограммам предусмотрены две специальные
операции: LPB и JPB.
Операции передачи управления (группа С)
Условные передачи управления могут осуществляться толь¬
ко по относительным адресам, которые вычисляются ассемб¬
лером. В табл. 4 приведены восемь мнемонических кодов ус¬
ловий, используемых в Базовом языке. Эти коды включаются
непосредственно в двоичный формат команды. Кроме того,
пользуясь командами JL и JNL, можно выполнить условный
переход в зависимости от значения, содержащегося в регистре
(для аргументов с видом 0 или 3 признак конца последова¬

3.6. Выбор системы машинных команд
тельности, на который реагируют эти команды, состоит в том,
что аргумент равен нулю; для аргумента вида 2— в том, что
0н является «простым» адресом). Условный переход совме¬
щается с модификацией адреса на единицу, или с вычитанием
единицы из счетчика, это дает возможность компактно про¬
граммировать обычные счетчики и циклы.
Безусловные переходы могут выполняться либо относи¬
тельно содержимого регистра ХС (т. е. относительно положе¬
ния текущей команды в данном сегменте программы), либо
относительно адреса, хранящегося в некотором регистре и
имеющего вид 2(1) или 2(C), причем в последнем случае ад¬
ресуемое кодослово должно быть вида 2(1). Все эти условия
проверяются в процессе выполнения программы, и если они
не удовлетворяются, то команда перехода вызывает преры¬
вание.
При выполнении безусловного перехода можно запомнить
связку, обеспечивающую возврат в программу; в случае ус¬
ловного перехода этого сделать нельзя. В качестве связки за¬
поминается адрес следующей команды. Связку можно запи¬
сать в регистр или в вершину стека; можно снабдить ее мет¬
кой. Так, безусловный переход, заданный командой
Х6 JSL XI
означает передачу управления команде, находящейся по ад¬
ресу, заданному в регистре XI, и засылку адреса возврата в
регистр Х6. Команда
2 JSM -12
передаст управление на 12 команд «назад» по отношению к
текущей команде, и в вершину стека будет записана связка
с меткой 2. А команда
JUMP Х6
передаст управление по адресу, указаному в регистре Х6, без
запоминания адреса возврата, что соответствует обычному
возврату из подпрограммы. Для возврата через элемент стека
можно использовать, например, команду
RET 2
При ее выполнении в стеке будет найдена первая от вершины
стека связка с меткой, не меньшей двух, и будет выполнен
переход по этой связке. При этом верхняя граница стека в
регистре XD будет установлена так, что в вершине стека ока¬
жется элемент, который был загружен в стек непосредственно
перед только что использованной связкой.
3 Зак. 233

66
8. Вазовая машина
Операции над адресами (группа D)
В группу D входят наименее общепринятые операции.
Можно выделить два основных типа действий над адресом:
изменение адреса, такое, чтобы он стал указывать на подпо¬
следовательность исходной последовательности, и выборка на
регистр первого элемента последовательности, на которую
указывает данный адрес. Действия первого типа выполняются
при помощи операций MOD и LIM, которые отсекают элемен¬
ты соответственно от начала и от конца последовательности.
При такой модификации размеры элементов учитываются ав¬
томатически. Действия второго типа выполняются при помощи
операции LOAD. Результаты ее применения к аргументам раз¬
личных видов приведены в следующей таблице:
Вид	Результат
0, 3	Совпадает со значением аргумента
1, 2 (I)	Применение некорректно
2 (N), 2 (М)	Применяется автовыборка
2 (С)	Вычисление кодослова
Следовательно, в операции LOAD используются все упо¬
мянутые выше правила выборки. Когда эта операция приме¬
няется к аргументу вида 2(C), то за ней нередко следует вы¬
деление подмножества. В частности, в результате применения
операции DOT будет получен «простой» адрес заданного эле¬
мента, что в точности соответствует механизму выделения эле¬
мента дерева.
Рассмотрим, например, снова рис. 2 на стр. 32. Предпо¬
ложим, что в регистре Х2 содержится «простой» адрес кодо¬
слова. Тогда по команде
XI	LOAD	Х2
значение кодослова Q засылается в регистр XI (с предвари¬
тельной проверкой того, что вид аргумента равен двум). Те¬
перь содержимое регистра XI указывает на последователь¬
ность, состоящую из шести абсолютных кодослов, так как
значения верхней границы (т) и типа (t) адресуемой после¬
довательности равны соответственно 5 и 8. Если теперь вы¬
полнить команды
XI	MOD	4
XI	LIM	О
то в регистре XI окажется «простой» адрес, указывающий на
пятый элемент набора Q. Тот же результат можно было бы

3.6. Выбор системы машинных команд
67
получить, выполнив вместо трех приведенных выше команд
следующие две:
XI	COPY	Х2
XI	DOT	4
Если после этого выполнить команды
XI	DOT	1
XI	LOAD	XI
то в XI окажется адрес набора F. На время обмена кодослово
F должно быть защищено (вид 1(5)); в таком случае выпол¬
нение последней команды сможет завершиться только после
того, как будет закончен обмен и вид кодослова F будет
снова установлен равным двум.
Для того чтобы найти первый ненулевой элемент набора
F, можно воспользоваться таким циклом:
Х2	LOAD	XI
NZ	JUMP	3
XI	JNL	~2
(продолжение, если все элементы равны нулю),
(продолжение, если искомый элемент найден).
Первая команда загружает в регистр Х2 значение элемен¬
та, полученное с применением автовыборки, и устанавливает
индикаторы условий, которые используются в следующей
команде. Третья команда проверяет, не «простой» ли адрес на¬
ходится в регистре XI; если нет, то адрес в регистре XI изме¬
няется на единицу и управление передается снова первой
команде. Если в регистре XI «простой» адрес (т. е. указывает
на последний элемент набора), то выполняется следующая
команда. Следует заметить, что приведенная выше программа
не зависит от того, из каких элементов состоит набор F: из бай¬
тов, слов или числовых элементов.
При помощи других операций над адресами можно полу¬
чить значение верхней границы аргумента, находящегося в ре¬
гистре (операция INDEX), или проверить значения типа или
вида такого аргумента (операции TTYPE и TTAG соответст¬
венно), сравнивая их с заданными и используя индикаторы
условий. Для сравнения адресов или вообще для выяснения
того, содержится ли одна последовательность в другой (или
совпадает с ней), можно воспользоваться операцией МЕМ.
Вид и тип можно изменить посредством операций WTAG и
WTYPE соответственно. При выполнении операции WTYPE,
если размер элементов нового типа отличен от старого, устана¬
вливается новое значение верхней границы последовательности:
3*

68
3. Базовая машина
3.7.	Форматы команд
По сравнению с традиционными системами команд список
из тридцати девяти операций, приведенных в табл. 3, исклю¬
чительно многогранен. Он может быть еще увеличен за счет
введения новых типов данных (например, десятичных, комп¬
лексных чисел и данных различной длины) и за счет добавле¬
ния новых операций. Тем не менее, пожалуй, .можно без осо¬
бого риска предположить, что шестиразрядного кода опера¬
ции (F) будет достаточно для дальнейшего расширения си¬
стемы команд. Вместе с четырехразрядным полем для первого
аргумента (X) это составит 10 битов в формате команды.
Вторым аргументом чаще всего бывает некоторый ре¬
гистр (У) или целое число (N). Будем считать, что N, как
правило, не требует больше 16 битов, и введем два формата
команды:
2 6 4 4
Короткий формат
2	6	4	4
{6
1 F X
± N
Длинный
литеральный
формат
Остается выбрать еще два способа задания второго аргу¬
мента, основываясь на эффективности кодирования. Можно,
следуя традиции, ввести модификацию адреса (У):
Модифицируемый
адрес
Здесь в качестве второго аргумента берется «простой» адрес,
полученный в результате модификации содержимого ре¬
гистра У числом N (с соблюдением обычной проверки вида и
верхней границы).
Четвертый способ формирования второго аргумента: «про¬
стой» адрес задается относительно содержимого регистра ХС
числом N, а тип аргумента (Т) берется из самой команды:
Формат
с адресацией
относительно ХС
±N
+ N
Тип Т и относительный адрес N вычисляет ассемблер. (Под
Т здесь отведено только четыре разряда вместо пяти, как
предлагалось раньше, но в данных обстоятельствах этого
достаточно.)

3.7. Форматы команд
69
Следовательно, шестнадцати- или тридцатидвухразрядный
формат команды, по-видимому, наиболее пригоден, а самый
выгодный код команды получается, когда второй аргумент
содержится в регистре. Существует много возможностей ча¬
стично оптимизировать приведенные выше общие форматы
команд, и это в самом деле желательно сделать. В Базовом
языке второй аргумент задается в более общем виде, а пе¬
реход к представлению его в коде машины осуществляется
транслятором. Предполагается, что второй аргумент команд,
приведенных в табл. 3, формируется в соответствии с одним
из приведенных выше форматов команды. Исключение со¬
ставляют те команды, для которых в таблице указана лите¬
ральная величина N, при этом применяется один из первых
двух форматов в зависимости от размера N.

4
БАЗОВЫЙ ЯЗЫК
Аппаратная часть Базовой машины распознает структуру
информации вплоть до уровня последовательностей операн¬
дов различных типов. Однако необходимо подчеркнуть, что
беспорядочное употребление команд машины не позволит
управлять структурами и процессами динамически, в то время
как осуществление именно этой возможности было одной из
важнейших целей, поставленных при разработке модели.
В настоящей главе будут введены понятия структуры про¬
граммы, структуры сегмента и иерархии процессов и будет
показано, как реализованы эти понятия при помощи Базово¬
го языка. Для этой цели достаточно представить язык в уп¬
рощенной форме; очевидно, что Базовый язык допускает как
обычные синтаксические расширения, позволяющие, напри¬
мер, задавать в текстах программ статические «блочные
структуры», так и различные алгоритмические дополнения,
которые делают его более интересным средством программи¬
рования; но, поскольку реализация этих расширений языка
не затрагивает аппаратной части, они здесь рассматриваться
не будут.
4.1.	Виды памяти
В машине с Базовым языком, как и в большинстве вычис¬
лительных систем, имеются три вида памяти: регистры, к ко¬
торым обращаются по кодам, непосредственно заданным в
командах; программная память, адресация к которой проис¬
ходит при помощи явной или неявной ссылки на регистры, и
память внешних массивов, содержимое которой можно обра¬
батывать, лишь пересылая его в программную память и об¬
ратно.
Память массивов — это совокупность массивов, каждый
из которых определяется как упорядоченное множество за¬
писей, Мы рассмотрим кратко формат записей, пересылаемых
в программную память, и более подробно формат записей,
представляющих программу на Базовом языке. Часть памя¬
ти массивов непосредственно доступна программисту, и он ие-

4.1. Виды памяти
71
пользует ее для ввода в машину всей своей информации, пред¬
варительно подготовленной в соответствии с определенными
правилами. В силу экономических причин обращение к мас¬
сивам происходит сравнительно медленно. Доступ к масси¬
вам реализуется с помощью программ, которые отражают
связи массивов между собой; степень сложности этих связей
зависит от вычислительной системы.
Можно ввести целый ряд операций, предназначенных
исключительно для работы с массивами, таких, как копиро¬
вание, трансляция, сортировка или слияние с упорядочением,
и включить их в команды языка обработки массивов. Одна¬
ко, поскольку реализация такого языка основана на методе
интерпретаций и такой, видимо, и останется, отдельные де¬
тали построения центрального процессора почти не влияют
на операции с массивами; поэтому описание команд, управ¬
ляющих массивами в Базовом языке, не включено в даль¬
нейшее изложение. Будет отмечено сходство между опреде¬
ленными структурами массивов [14] и древовидной структу¬
рой программы на Базовом языке, но связь между ними не
настолько важна, чтобы изучать ее слишком подробно, так
как технические проблемы, возникающие при аппаратной реа¬
лизации упомянутых структур, различны.
Программная память
Программная память — это древовидная структура, кор¬
нем которой является отдельный набор кодослов, составляю¬
щий базу программы. Это единственный набор, который не
определяется кодословом более высокого уровня; его элемен¬
ты занимают фиксированную последовательность ячеек па¬
мяти, и для обращения к ним служат две специальные коман¬
ды (JPBy LPB). Применение этих команд равносильно явному
использованию элемента с видом 2(8), задающего адрес ука¬
занной ячейки. Разрешается использовать элементы всех тех
типов и видов, которые допустимы в Базовой машине; кроме
того, при помощи программы обработки прерываний обеспе¬
чивается определенная стандартная интерпретация элементов
вида 1.
В неактивной системе база программы всегда определяет
фиксированное множество резидентных системных программ
и констант, необходимых для трансляции с Базового языка и
для запуска и работы процессов. Системные программы ин¬
вариантны и могут быть использованы несколькими процес¬
сами одновременно, но их рабочие поля должны быть неза¬
висимо друг от друга связаны с каждым пользователем.
В ходе вычислений пользователь может присоединять новые

72
4. Базовый язык
наборы к базе программы, сохраняя их адреса для будущих
обращений. Мы будем говорить, что набор принадлежит тому
процессу, который его образовал; свойство набора кодослов
принадлежать какому-либо процессу распространяется на все
подмножества данного набора кодослов. Отсюда следует, что
в любой момент программную память можно разделить на
резидентную часть и несколько непересекающихся областей,
принадлежащих текущим процессам. Позже' будет показано,
каким образом один процесс может обращаться к элементам,
принадлежащим другому процессу, или запоминать свою ин¬
формацию в любом незащищенном наборе данных. Тем не
менее ни одному процессу не разрешается менять никакую
структуру, кроме своей собственной.
Программную память можно распределить по нескольким
физическим носителям так, чтобы часто используемая инфор¬
мация размещалась в более быстродоступных областях па¬
мяти. Такое распределение автоматически производит систе¬
ма управления памятью. Буферная 4) память, которая харак¬
теризуется тем, что в ней невозможно экономным образом
получить доступ к отдельному байту или слову, включается
в общую систему памяти при помощи кодослова вида 1(6).
Оно определяет местоположение и длину блока информации.
При обращении к такому кодослову вычислительный процесс
прерывается на время переноса всего блока в основную па¬
мять (ср. разд. 2.3). Несмотря на то что такие действия
обычно производятся автоматически, программист, исполь¬
зующий Базовый язык, может выяснить, находится ли дан¬
ный блок в основной памяти или нет, и действовать соответ¬
ственно. Ясно также, что описанная форма объединения
памяти требует, чтобы вместе с некоторым набором, находя¬
щимся в основной памяти, в ней же находились и все кодо¬
слова, ведущие от программной базы к этому набору; в про¬
тивном случае могут возникнуть трудности в управлении
распределением памяти. Формулируя свои запросы памяти,
программист должен в особых случаях учитывать это обстоя¬
тельство.
Регистры
Регистры, обозначенные через ХО, XI, ..., Х9, соответ¬
ствуют первым десяти регистрам Базовой машины. Осталь¬
ные регистры Базовой машины ХА, ХВ, ..., XF обычно не
используются. Они могут употребляться только в специаль¬
ной версии языка, которая служит для написания очень не¬
*) В оригинале backstore. — Прим. ред

4.1. Виды памяти
73
большого количества системных стандартных программ. (Та¬
ким образом, общепринятый привилегированный режим вы¬
полнения заменен в BLM специальным режимом ассемблиро¬
вания.)
В систему операций над регистрами в Базовом языке вхо¬
дит большинство тех команд Базовой машины, которые при¬
ведены в табл. 3; однако символическая форма Базового
языка часто позволяет вводить такие команды, которые со¬
ответствуют нескольким машинным (например, передачи уп¬
равления). Определенные ограничения накладываются на
команду TAG (табл. 5); ее можно применять только к эле¬
ментам, имеющим целый или числовой вид и тип, и только
для генерации элементов со значением вида 0 и 3 или с ти¬
пом N (см. стр. 56). Кроме того, нельзя изменять признак
«только чтение».
Из перечисленных выше ограничений следует, что про¬
граммист может управлять представлением только целых и
числовых данных, а форматы адресов, команд и обрабаты¬
ваемых по прерыванию элементов находятся вне сферы его
влияния. Однако и при использовании команды TAG автор
программы должен хорошо продумать возможные последст¬
вия применения этой команды, так как, обойдясь без такой
команды, он мог бы не входить в детали представления дан¬
ных и его программы имели бы соответственно большую общ¬
ность. Не часто удается достичь такого обобщения с эле¬
ментами целочисленного формата (вид 0); в случаях число¬
вых данных (вид 3) можно задавать форму представления,
определяя арифметические свойства элементов, такие, как
точность, размер, правила усечения, а не их двоичную запись,
которую совсем не обязательно знать для эффективного про¬
граммирования. Эти соображения характерны для написания
большинства программ на языках высокого уровня и являются
одним из источников их общности; кроме того, известно, что
если такой язык позволяет менять типы и форматы элемен¬
тов, например, при помощи перераспределения области дан¬
ных, то некоторые программы, использующие это свойство,
можно будет пропускать лишь на машинах с идентичным
представлением числовых элементов. Существование таких
языков и наличие задач с повышенными требованиями к точ¬
ности представления числовых данных явились причиной того,
что в Базовом языке введены команды, меняющие тип и вид
элемента, но со специальной оговоркой по этому поводу.
В регистрах задаются также аргументы административ¬
ных команд (группа Е)1). Эти команды в большинстве
!) В оригинале Executive. — Прим. ред.

74
4. Базовый язык
случаев реализуются постоянно находящимися в памяти
программами в точности так, как это делается при помощи
«экстракодов» или «административных» операций в традицион¬
ных машинах. Команды группы Е, несмотря на более слож¬
ную логику, составляют «аппаратную» часть машины так же,
как и все остальные команды. Желательно, чтобы особенности
их реализации были скрыты от пользователя. Это достигается
путем использования двух регистров ХА и ХВ для передачи
параметров. Административные команды всегда формируются
в виде, который не требует больше двух аргументов; если ре¬
зультат, полученный при выполнении такой команды, имеет
смысл, то он запоминается в том месте, которое определяется
первым аргументом.
Ассемблер отличает команды группы Е от остальных и
вставляет дополнительные команды, копирующие аргументы
в АЛ и в ХВ. Некоторые операции могут потребовать больше
двух аргументов или даже переменное их количество; в этом
случае последовательность аргументов предварительно фор¬
мируется в регистровом стеке (при помощи команд DUMP),
а адрес этой последовательности помещается в ХА или в ХВ
в зависимости от самой операции. Административная про¬
грамма может содержать в себе команды TTAG, TTYPE и
INDEX, чтобы действовать по-разному, в зависимости от
свойств данных.
С точки зрения программиста, регистры представляют со¬
бой часть базы процесса и имеют обычные логические свой¬
ства. Заметим, однако, что явное использование регистров
обычно дает возможность получить эффективную программу:
сокращается объем программы и время ее выполнения.
4.2.	Процессы
Процесс определяется как выполнение последовательности
команд Базового языка, выбираемой в соответствии с переда¬
чами управления и действиями по прерываниям. Рассмотре¬
ние особенностей реализации процесса — в зависимости от
мультипрограммной или мультипроцессорной работы — нахо¬
дится вне сферы разрабатываемой модели. Каждому про¬
цессу соответствует единственная база; через нее он получает
доступ к программной памяти, но не к базам других процес¬
сов. Элементы базы обеспечивают также связь с системой
памяти массивов при помощи адресных элементов массивов
(вид 1 (7)).
Основным требованием при мультипрограммной работе
машины является существование по крайней мере одного
активного процесса, способного управлять остальными.

4.2. Процессы
75
В BLM такой процесс назван системным процессом (я0).
Если принять принцип максимально допустимого уравнива¬
ния прав самой системы с теми правами, которые предостав¬
ляются другим процессам, то из него следует, что каждый
процесс должен иметь возможность взаимодействия с некото¬
рыми другими процессами и возможность образования новых.
Рассмотрим теперь условия, которые должны быть выполне¬
ны, чтобы процесс вычислений был эффективным.
Понятно, что свободное общество процессов, в котором
каждый процесс может повлиять на любой другой, может
привести к хаосу. Поэтому необходимо разумным образом
ограничить взаимодействия между процессами. Основной
принцип формулируется так: если программист хочет образо¬
вать один процесс, не зависящий от других, такая возмож¬
ность должна быть ему предоставлена. Это очень важное
практическое требование. Но нужно оставить какую-нибудь
лазейку, для того чтобы управлять данным процессом в слу¬
чае неожиданных ошибок в нем или внешних прерываний;
для этого достаточно было бы, чтобы каждый процесс имел
ровно один управляющий процесс — супервайзер, а другие
процессы не могли бы вмешиваться в управление данным
(системный процесс не имеет супервайзера).
Будем говорить, что данный процесс является подпроцес¬
сом процесса jtj, если последний — его супервайзер. В Базо¬
вом языке есть команды для запуска и прекращения подпро¬
цессов и для управления ими в промежуточном состоянии.
Количество подпроцессов ограничивается только наличием
ресурсов у супервайзера, так как ресурсы, запрашиваемые
подпроцессом, вычитаются из общего количества ресурсов,
которые имеются в распоряжении данного супервайзера. На¬
пример, не допускается, чтобы суммарные требования под¬
процессов супервайзера превышали объем той части памяти,
которая ему предоставлена. Контроль за выполнением этого
условия может осуществляться по-разному, в зависимости от
метода выделения ресурсов. Можно либо предоставлять ка¬
ждому подпроцессу определенный запас ресурсов в момент
его запуска, либо создавать общий фонд ресурсов для не¬
скольких подпроцессов. Выбор метода можно оставить на
усмотрение программиста. Разделение системных средств,
предназначенных для одновременного обслуживания несколь¬
ких процессов системы, таких, как каналы передачи данных,
производится в интересах оптимизации общей производитель¬
ности системы.
Вырисовывается знакомая картина древовидной структу¬
ры— «дерево процессов», и появляется искушение ввести
в программной памяти такую же структуру для процессов.

76
4. Базовый язык
Однако нет никаких особых причин, по которым отношения
подчинения, возникающие при управлении процессами, дол¬
жны были бы отражаться в структуре памяти, тем более что
использование этих отношений требует режима интерпрета¬
ции. Единственные реальные явные признаки иерархии про¬
цессов— это номер супервайзера и список подпроцессов, ко¬
торые находятся в базе каждого процесса в позициях, доступ¬
ных только системным программам.
Совместное использование памяти
Общепринятым является такое практическое требование:
каждый процесс должен иметь доступ по крайней мере к ча¬
сти памяти своего супервайзера. Этого можно достичь, разре¬
шив процессу искать в базе супервайзера элемент по его
названию и во время поиска двигаться вверх по уровням.
Такая процедура должна продолжаться до тех пор, пока не
будет найден искомый элемент, который копируется в теку¬
щую базу. Если поиск дойдет до уровня я0 и окончится
безрезультатно, создается неопределенный элемент. Не на¬
лагается никаких ограничений на доступ к инвариантной
информации. Но, например, в случае незащищенного набора
данных супервайзеру нужно сообщить, может ли данная об¬
ласть использоваться его подпроцессами; если да, следует ли
защищать ее от подпроцессов, используя возможность зада¬
ния признака «только чтение». Это можно сделать при по¬
мощи описательного оператора,
4.3.	Прагматика
Описание нашего языка, предназначенного для использо¬
вания как в оперативном, так и в пакетном режимах, управ¬
ляющего и скалярными, и нескалярными величинами, служа¬
щего как для развития программ, так и для их выполнения,
должно привести к рассмотрению таких особенностей, кото¬
рые никогда не приходилось учитывать при работе на тра¬
диционных машинах с обычными языками высокого уровня.
Основное назначение Базового языка заключается в опи¬
сании действий над памятью массивов, программной памятью
и иерархией процессов. Проще всего поэтому определить опе¬
рации, служащие этим целям, и символически описать их
вместе с аргументами в форме команд. Последовательность
действий можно выразить в форме последовательности
команд, т. е. в виде массива, элементы которого (записи) —
это наборы байтов, удовлетворяющие правилам языка.
При этом возникает необходимость провести различие ме¬
жду двумя формами представления последовательностей

4.3. Прагматика
77
команд — прямой и непрямой. Во втором случае команды
можно снабдить метками, используя их, как обычно, для ука¬
зания места, в которое может быть передано управление.
При этом предполагается, что исходная последовательность
команд будет перед выполнением целиком оттранслирована
и записана (в двоичной форме) в память. В первом случае
последовательность может содержать лишь ограниченное чи¬
сло команд без меток (даже одну), что ограничивает возмож¬
ности управления порядком следования команд.
Нужно также допустить существование процессов, описан¬
ных при помощи отдельных последовательностей команд, под¬
готовленных разными программистами и независимо друг от"
друга оттранслированных в двоичную форму. Именно такой
последовательностью команд является программный сегмент,
хотя его определение расширено так, что в него на любом
уровне дерева программы можно включить блоки относитель¬
ных кодослов и данных. Сегмент транслируется в отдельный
блок памяти. Для изменения его внутренней структуры необ¬
ходимо заново провести трансляцию с текста, определяющего
новый сегмент в символическом виде, в то время как заме¬
нить один такой блок на другой в самой программе можно
в любой момент. Такой подход отразился в разделении иден¬
тификаторов на два класса — на локальные и глобальные
имена; они позволяют адресоваться к обрабатываемому в на¬
стоящий момент сегменту или к базе процесса соответствен¬
но; однако эти имена равноправны во всех командах, кроме
тех, которые вызывают изменения в структуре.
Подструктура сегмента повторяет в миниатюре древовид¬
ную структуру программы. Форма представления команд
в самом сегменте очень напоминает представление команд
в отдельном блоке программы в машине неймановского типа.
Разница состоит в том, что данные и команды в сегменте раз¬
личаются явно, сама структура данных формализована и за¬
дана при помощи относительных кодослов. Хранить в памяти
древовидную структуру сегмента в целях обеспечения адре¬
сации, вообще говоря, не обязательно, так как ассемблер мо¬
жет сам осуществить необходимую систему ссылок. Однако
надо принять во внимание следующее важное практическое
соображение: для того чтобы получить в удобном виде диаг¬
ностическую информацию, нужно уметь по двоичной форме
сегмента восстанавливать его представление в символическом
виде; если древовидная структура сохраняется в памяти, это
сделать проще.
Всегда желательно иметь в машине возможность работать
с процессами в режиме усовершенствования. В этом случае
приходится возвращаться к ним через короткие или длинные

78
4. Базовый язык
промежутки времени и в значительной мере варьировать
структуру памяти программы и внешних массивов в соответ¬
ствии с изменениями, происшедшими в задаче. Метод пред¬
ставления сегментов в двоичной форме имеет решающее зна¬
чение для успешного осуществления такой возможности. Сег¬
менты не только должны не зависеть от своего физического
расположения в памяти, но и должны допускать возможность
эффективной связи с другими сегментами в условиях и сов¬
местного и раздельного использования ресурсов. При этом они
должны требовать минимума усилий со стороны системы для
работы с ними после обработки ассемблером. Приведен'
ные соображения очень повлияли на форматы сегментов и
административных команд, которые мы рассмотрим в двух
следующих разделах.
4.4.	Программные сегменты
Синтаксические определения даны в приложении и иллю¬
стрируются примерами в этой главе. Любое выражение Ба¬
зового языка может быть «вычислено» на трех различных
уровнях: синтаксическом, уровне сравнения типов и уровйе
автовыборки. Процесс вычисления на каждом из уровней мо¬
жет окончиться неудачей и вызвать уход на монитор соответ¬
ственно при ассемблировании, в случае несоответствия видов
или при получении некорректного результата; следует отме¬
тить, что момент, в который произойдет обращение к мони¬
тору, зависит от «квалификации» транслятора. Правила син¬
таксиса с учетом использования элементов различных типов
приведены в табл. 5, в которой представлена система команд
Базового языка. Изучение этой таблицы приводит к выводу,
что определенного рода вычисления, связанные с типом эле¬
ментов, могли бы выполняться на синтаксическом уровне при
незначительном изменении форматов; вопрос о том, делается
ли это в действительности, в разрабатываемой модели не рас¬
сматривается.
Программный сегмент — это последовательность предло¬
жений, определяющих данные или команды, которые обычно
пишутся в последовательных строках и оформляются в виде
внешнего массива. Для того чтобы процесс а начал выполне¬
ние прямой последовательности команд, представленных мас¬
сивом р, можно воспользоваться командой
a CIS р
(CIS — Command Input Stream — означает ввод потока
команд). При помощи этой же команды обычно вводят в си¬
стему новые документы, в этом случае р разрешается опу¬

4.4. Программные сегменты
79
скать, хотя пользователь может специфицировать различные
интерпретации этой величины. Эта команда предназначена
для обеспечения управления процессами путем ввода команд
Базового языка с клавишных устройств или с перфолент.
Таким образом, любой массив воспринимается сначала
как прямая последовательность команд. Этот режим интер¬
претации содержимого массива разрешается менять на ра¬
боту с непрямой последовательностью, используя команду
SEG:
т] SEG р,
где т)—составное имя, обозначающее абсолютное кодослово,
и |li — неотрицательное целое число, задающее количество
входных точек в блоке, который получится в результате обра¬
ботки ассемблером последующего текста и будет храниться
в памяти под именем г]. Трансляция продолжается в таком
непрямом режиме до тех пор, пока не встретится команда
END.
Внутри такого описания непрямого сегмента все предло¬
жения языка, определяющие данные, должны иметь метки
(иначе ими нельзя воспользоваться). Команды также могут
иметь метки в тех случаях, когда они определяют места
в программе, куда происходят передачи управления. В тек¬
сте программы данные и команды могут перемежаться, но
при обычном режиме выполнения команд происходит пере¬
ход от одной команды к следующей и не делается попыток
«выполнить» встречающиеся в тексте программы данные. От¬
носительные передачи управления можно задавать либо при
помощи меток, либо при помощи счетчика строк. В послед¬
нем случае число строк, определяющее величину сдвига по
программе, подсчитывается относительно номера текущей
команды; однако второй способ рекомендуется применять
только для «коротких» передач управления. Отдельная
команда Базового языка транслируется в одну или несколько
команд в коде Базовой машины, причем изменение величины
сдвига учитывается и корректируется ассемблером.
Формальное разделение идентификаторов на две катего¬
рии вводится для упрощения представления языка, а не яв¬
ляется обязательно присущим ему свойством. Так, глобаль¬
ное имя — это либо имя некоторого регистра, либо любая из
прописных букв латинского алфавита (А, В, ..., Z), соответ¬
ствующая некоторому элементу расширенной регистровой па¬
мяти (не обязательно в таком же порядке). Локальное имя
можно определить только внутри сегмента, т. е. как метку
некоторой команды. Если это имя служит только для внут¬
ренних целей, оно может задаваться одной из строчных букв

80
4. Вазовый язык
латинского алфавита (a, b,	если	на	это	имя	могут
ссылаться другие сегменты, оно обозначается одним из выра¬
жений фО, ф1, . . ., фп, где п + 1 — количество входных то¬
чек. Так как глобальное имя определяет элемент базы про¬
цесса, его значение может меняться; локальное имя, напро¬
тив, обозначает фиксированный адрес, который вписывается
в команды с адресацией относительно ХС.
Составные имена
Формирование глобальных и локальных имен можно срав¬
нить с традиционным методом установления однозначного
соответствия между символьными наименованиями и ячей¬
ками линейной памяти, применяемым при работе ассембле¬
ров. Однако в BLM так адресуется только часть памяти; для
выбора любого другого элемента необходимо задать последо¬
вательность индексов, определяющую путь, который ведет
к этому элементу от указанной базовой позиции. Для этой
цели используется операция «точка», которая была опреде¬
лена ранее (см. стр. 33). В Базовом языке любое имя, как
локальное, так и глобальное, воспринимается как составное;
кроме того, составным именем является выражение, после¬
довательно содержащее составное имя, точку, неотрицатель¬
ное целое число. Примеры составных имен:
«Х6», «Ф 3», «Y», «ф 1.6», «Х4.0.3»
Выражение считается локально или глобально базирован¬
ным в зависимости от того, к какой категории принадлежит
его первая компонента. Если, например, А — сегмент с тремя
входными точками, то в теле сегмента к этим точкам обра¬
щаются как к фО, ф1, ф2; из других же сегментов к ним об¬
ращаются как к «А.О», «А.1», «А.2». В определенном контексте
символ недействительного элемента «Q» можно рассматри¬
вать как составное имя, представляющее элемент вида 1(0).
В терминах абстрактной древовидной структуры памяти
составное имя г\ определяет некоторую (возможно, простую)
последовательность. Если первый элемент этой последова¬
тельности в свою очередь определяет -некоторый набор, то
составные имена «г\. О», «г\. 1» и т. д. служат для обращения
к его элементам; в противном случае эти составные имена не¬
корректны. Операция DOT введена специально для того, что¬
бы механизировать именно такой процесс выбора пути и
обнаруживать ошибки, если составные имена оказываются
некорректными.
Для практических целей определение составного имени
можно было бы расширить так, чтобы в него входили специ¬

4.4. Программные сегменты
81
фикации таких адресных операций, как (MOD, L1M и
LOAD), и чтобы можно было обобщить определение пути,
разрешив использование переменных индексов, значения ко¬
торых вычислялись бы динамически в процессе выполнения
программы. Более компактное описание работы с последова¬
тельностями— вот очевидное преимущество такого метода;
однако и при введенных нами ограничениях можно добиться
тех же результатов при помощи отдельных команд. По суще¬
ству по тому же принципу устроены обобщения, которые по¬
зволяют вместо отдельных переменных использовать выраже¬
ния, содержащие арифметические операции.
Метки
Метка определяется как локально базированное составное
имя, за которым следует двоеточие. Если составное имя со¬
держит больше одной компоненты, то в тексте программы
для каждого уровня адресации должен быть предварительно
описан набор относительных кодослов. Так, например,
в строке
#3.5: Х2 ADD 3
составное имя #3.5 допустимо только тогда, когда в одной из
предшествующих строк имя #3 ввело набор относительных
кодослов со значением верхней границы не меньше 5 (см.
ниже).
Определение локальных констант
Локальная константа определяется как метка, за которой
следует целое число; ненулевым локальным константам при¬
писывается признак «только чтение». Небольшие наборы эле¬
ментов различных типов можно представлять в виде списка
числовых термов, разделенных запятыми и заключенных
в круглые скобки,
р: (0, 12, 1077, —8) Набор из 4 слов (тип 2)
q: (0, 12, 67)	Набор	из 3 байтов (тип 3)
Можно расширить применение круглых скобок для того,
чтобы с их помощью строить многострочные определения или
естественным образом описывать древовидные структуры; но
эти возможности здесь не рассматриваются. Часто употреб¬
ляемые множества нулевых или недействительных эле¬
ментов заданного типа удобно описывать в форме [rty: п2], где
п\ и п2 — числа, которые определяют соответственно тип
в/24 За к. 233

82
4. Базовый язык
множества и его верхнюю границу, например:
г: [9 :5] Набор из 6 неопределенных относительных
кодослов
В этом контексте для допустимы значения 0, 1, 9, 12 и
13. Определив набор, подобный г, в том же программном сег¬
менте можно дополнительно определить поднаборы, на¬
пример:
г.О: [0:99]	Набор из 100 нулевых слов
г.З: X6SUB7	Входная точка программы
и т. д. Порядок определения поднаборов несуществен. Далее,
имеется возможность указать на необходимость увеличения
размера набора в случае исчерпывания его при модификации;
в этом случае в качестве разделителя вместо двоеточия ис¬
пользуется точка с запятой, например [0; 79]. Размер этого
множества автоматически увеличится на 80 элементов, как
только произойдет его переполнение по модификации.
Список разделенных запятыми, локально базированных
составных имен, заключенный в скобки, называется набором
постоянных имен. Он представляется набором относительных
кодослов и обеспечивает специальное отображение памяти
внутри отдельного сегмента, например:
ф2: (ф1, г, и.З) Множество из 3 относительных
кодослов
Такие выражения используются, в частности, для описа¬
ния локальных переключателей. Возможны многоуровневые
ссылки.
В общем случае любую конечную последовательность эле¬
ментов можно задать каким-либо списком, содержащим кон¬
станты или составные имена, представленные элементами
смешанного типа (11). Для некоторых элементов не вводится
точной формы представления. Тогда мы должны прибегнуть
к помощи Базовой машины, т. е. к возможности программной
интерпретации (тип 1 (8)). Такая интерпретация составляет
часть логической конструкции машины и допускает измене¬
ния в такой же степени, как и реализация системы команд.
В командах Базового языка константы могут быть исполь¬
зованы в любом контексте, где защищенный — «только чте¬
ние»— простой адрес имеет смысл. Так, после применения
команды
ХЗ LOAD (а, Ь, с)
ХЗ становится адресом последовательности из трех относи¬
тельных кодослов, т. е, вида 2(9) со значением верхней гра¬

4.4. Программные сегменты
83
ницы, равным 2. Такие выражения удобно применять для
обмена списками параметров между разными частями про¬
граммы.
Команды
Выделение регистров ХА и ХВ для специального исполь¬
зования в машинных командах, полученных после ассембли¬
рования, дает возможность обобщить понятие аргумента до
составных имен, числовых констант и наборов. Константа,
используемая в качестве аргумента, определяется своим адре¬
сом, а набор — адресом своего кодослова. Использование
таких аргументов для указания места записи результата на
уровне автозасылки привело бы к аварийной ситуации; но
противоречия здесь нет, так как это, очевидно, один из тех
описанных выше случаев, когда соответствующие проверки
корректности могут делаться при ассемблировании про¬
граммы.
Арифметические команды точно соответствуют командам
группы А Базовой машины. Аргументами могут быть любые
составные имена или константы. Например, команда
Х6 ADD s.3
транслируется в такую последовательность команд:
ХВ
COPY
ХС (s)
(Т = 9)
ХВ
DOT
3
Х6
ADD
ХВ
Первая из машинных команд использует формат с адре¬
сацией относительно ХС. Здесь s — относительный адрес s,
а код типа (9) показывает, что s — относительное кодослово.
Такие выражения порождают длинные программы на языке
машины, но при определенных обстоятельствах их примене¬
ние оправдывается теми же соображениями, которые приво¬
дятся в защиту расписывания формул и других обобщенных
конструкций. Правила автовыборки, относящиеся к элемен¬
там смешанного типа, были созданы для упрощения косвен¬
ных операций над базой процесса.
В Базовом языке имеется возможность использовать лю¬
бую команду только для установления индикатора условий
(с)	и не заносить результат операции в память; для этого
достаточно пометить идентификатор операции символом
«звездочка». Например, команда
ХЗ SUB* Х6

84
4. Базовый язык
транслируется б команду Базовой машины
ХЗ TEST Х6
Реже для такой установки индикаторов состояния исполь¬
зуется такая команда, как
Х4 ADD* 5
В этом случае при трансляции придется сначала перепи¬
сать содержимое Х4 в ХВ. Предполагается, что при установ¬
лении значения с производятся все подразумеваемые преоб¬
разования. Команды, допускающие этот вариант, помечены
в табл. 5 звездочками.
Обобщенные аргументы нельзя использовать в командах,
полностью или частично оперирующих с адресами (т. е. при¬
надлежащих группам В, D Базовой машины), к которым не¬
применима автовыборка. В таких случаях операндом коман¬
ды обычно служит некоторый элемент базы, и, следовательно,
он выбирается по глобальному имени. Напомним (см. стр. 80),
что набор адресов (возможно, простой), соответствующих
локальным именам, задается неявно, и поэтому они не могут
быть использованы для указания места занесения результа¬
тов. Тем не менее можно употреблять такие локальные имена
вначале для копирования их в позиции базы, а затем произ¬
водить над ними операции, например:
A	COPY	г
A	DOT	2
Для действий над элементами набора смешанного типа
программист должен применять команды RF и RS, соответ¬
ствующие машинным операциям с такими же названиями.
Отметим, что для команд, у которых второй аргумент должен
быть целочисленным (MON, RET), и для команд TAG,
DUMP и UNDUMP, которые являются просто обобщениями
соответствующих команд Базовой машины, предусмотрены
специальные форматы.
Нельзя так просто обобщать регистровые аргументы на
всю базу процесса только для команд передачи управления
(группа С). Объясняется это тем, что при передаче управле¬
ния приходится выполнять команду RS, которая нужна для
записи содержимого ХА или ХВ в расширенную регистровую
память. Первый аргумент команды JUMP служит для специ¬
фикации четырех случаев:
Первый аргумент вида X означает: передать управление
и образовать связку в X, например
Х6 JUMP 5

4.4. Программные сегменты
85
Первый аргумент, представляющий мнемоническое усло¬
вие, задает условный переход, напршмер
ZE JUMP t
Первый аргумент, заданный целочисленной константой,
вызывает передачу управления и запоминание помеченной
связки, например
3 JUMP А. 5
Пустой первый аргумент определяет безусловный переход:
JUMP -3
Место, куда нужно передать управление, определяется
либо величиной относительного сдвига по программе, кото¬
рый задан в строках (случаи 1, 4), либо внутренней меткой
(случай 2), либо, в общем случае, любым составным именем,
которому должен соответствовать элемент с видом 2(1) или
адрес такого элемента.
Представление программных сегментов
Задача представления подструктуры сегмента в системе
команд Базовой машины не слишком отличается от задачи
написания однопроходного ассемблера для традиционной
машины. Наличие регистров ХС и XD дает возможность
сформировать адрес любого локального или глобального
имени, используя соответствующий индекс. Разрешается упо¬
треблять имена прежде, чем станут известны не только ин¬
дексы, но даже базовые адреса (при введенных в этой книге
обозначениях это невозможно). При условии согласованности
запросов памяти в этих случаях сравнительно просто на
более позднем этапе ассемблирования вписать неизвестные
заранее адреса, используя технику организации цепочек. При
обработке локальных имен (определенных внутри сегмента)
в команды вписываются коды типов элементов (разд. 3.7,
формат с адресацией относительно ХС).
Однако, как уже отмечалось во второй главе, индекс
глобального имени обычно не известен во время ассемблиро¬
вания, так как сегмент может быть предназначен для исполь¬
зования в условиях различной рабочей среды; поэтому не¬
обходим некоторый механизм, позволяющий к моменту
использования сегмента определить все его внешние связи.
Рассмотрим две возможности.
Если данный сегмент неделим, т. е. не предназначен для
совместного использования, программы управления памятью
могут записать правильные базовые индексы во время

86
4. Базовый язык
загрузки сегмента в данную рабочую среду, используя при
этом таблицу связей или при помощи модификации XD. При
копировании такого сегмента в пределах той же рабочей сре¬
ды не возникает никаких трудностей. Если же сегмент запи¬
сан в памяти массивов, перед тем, как использовать его в оче¬
редной раз, нужно позаботиться о правильной реорганизации
программных ссылок, описанных в символической форме, так
как индексы базы процесса могли измениться.
Вторая возможность состоит в том, что данный сегмент
используется совместно несколькими процессами или предна¬
значен для такого употребления. Транслятор распознает его
по отсутствию предложений языка, определяющих незащи¬
щенные данные. Значения символических ссылок опреде¬
ляются при каждом обращении к глобальному имени при
помощи интерпретации по прерыванию элемента в таблице
связей. Этот метод малоэффективен, но в гл. 2 уже отмеча¬
лось, что эффективность можно увеличить, если при входе
в программу управления памятью организовывать таблицу
поиска и запоминать в регистрах или в стеке окончательные
адреса на то время, пока они могут понадобиться.
4.5.	Административные команды (группа Е)
Административные команды предназначены для построе¬
ния информационных структур, которые можно описать на
Базовом языке, и для управления такими структурами. К по¬
следним относятся: программная память, память массивов и
иерархия процессов. В связи с таким рзделением структур
команды группы Е тоже делятся на три подгруппы, каждая
из которых описывается отдельно. При описании каждой под¬
группы будет перечислено только минимальное количество ее
команд.
Управление программной памятью
В предыдущем разделе вводились обозначения для набо¬
ров, состоящих из переменных или из констант, включая и
те наборы, которые состоят из одних нулей или из элементов
с видом 1. Способность «приписывать» такие наборы опреде¬
ленным ветвям программной памяти является одной из основ¬
ных функций управления памятью. Эту функцию выполняет
команда EQU. Место, в которое помещается результат, обыч¬
но задается адресом абсолютного кодослова, которое нужно
заменить кодословом, определяющим новый набор. Таким
образом, команда
М EQU [8:5]

4.5. Административные команды (группа Е)
67
определяет М как адрес кодослова, описывающего набор из
6 абсолютных кодослов вида 1(0). Нужно рассмотреть две
возможные ситуации:
(a) М первоначально являлось адресом абсолютного ко¬
дослова и поэтому имело вид 2(8). В этом случае на
место прежнего кодослова записывается новое.
(b) Во всех остальных случаях новое кодослово добав¬
ляется к базе той программы, которая содержит это
определение набора, и адресуется при помощи М.
Например, если Х6 — недействительный элемент, то
команды
Х6	EQU	[13:99]
Х6	LD	Х6
помещают длинный адрес новой последовательности
из 100 «коротких» числовых элементов в Х6.
Легко видеть, что интерпретация команды EQU и интер¬
претация команды MOVE с автозасылкой в известной сте¬
пени аналогичны.
В случае (а) применимо правило принадлежности, о ко¬
тором уже говорилось. Если М ссылается на кодослово, не
принадлежащее текущему процессу, то команда некоррект¬
на— возникает прерывание. В случае (Ь) полученное множе¬
ство принадлежит текущему процессу по определению. В слу¬
чае корректности команды EQU ее выполнение влечет за
собой поиск нужного объема памяти; на это требуется затра¬
тить те или иные усилия в зависимости от типа задачи и ре¬
зервов памяти в данный момент. В гл. 5 в связи с этим вопро¬
сом рассматриваются некоторые практические соображения,
тем не менее очевидно, что, программируя на уровне Базового
языка, нельзя полностью избавиться от необходимости сле¬
дить за экономией памяти. Сам Базовый язык обеспечивает
богатый выбор разнообразных стратегий.
Структуры, хранящиеся в памяти, можно определять,
основываясь на уже существующих наборах кодослов, задан¬
ных описанным выше способом. Так, можно расширить М
при помощи такой команды:
М-3	EQU	[1:39]
Определить множество можно, копируя уже существую¬
щую структуру
A	EQU	М.З
Заметим, что команда COPY копирует только отдельное
слово (с видом), т. е. команда
В	COPY	М-3

88
4. Вазовый язык
помещает адрес М.З в базовую позицию, соответствующую
В (см. рис. 5).
Команда SEG, введенная в начале разд. 4.4, интерпрети¬
руется почти так же, как EQU. Различие проявляется в том,
что команда SEG всегда выполняется непосредственно (без
ссылки на другие объекты) и в соответствии с правилами
Базового языка определяет отдельный блок информации.
Рис. 5.
На основе команды EQU можно создать много операций
для копирования каких-либо структур целиком или частично.
Например, можно определить функцию, которая копирует
только первый уровень некоторого дерева, пользуясь следую*
щей последовательностью команд (М копируется в С);
м
TAG*
2(8)
NZ
JUMP
6
XI
LOAD
M
Х2
INDEX
XI
ХЗ
TYPE
XI
С
EQU
[X3:
RET
0
с
TAG
1(0)
RET
1

4.5. Административные команды (группа Е)
89
Вставляя некоторое количество элементов внутрь набора,
мы изменяем его длину. Эта процедура обычно занимает
много времени, за исключением тех случаев, когда память
машины организована специальным образом (в виде списоч¬
ной структуры). Такой способ организации памяти описан
в гл. 5. Команда
М.6 INSERT 40
вставит после шестого элемента множества М (т. е. перед
М.6) 40 элементов. Если второй аргумент команды отрица¬
тельный, указанное количество элементов, начиная с данной
позиции, выбрасывается и соответственно меняются все адре¬
са. При добавлении элементов в конец набора можно (и вы¬
годно) пользоваться аппаратным обнаружением переполне¬
ния по модификации для автоматического увеличения длины
набора; при этом употребляются обозначения, введенные на
стр. 81. Тогда программисту не нужно проверять, исчерпался
ли набор, чтобы в случае необходимости увеличить длину.
Здесь уместно отметить, что команды перехода JL и JNL
относятся к текущему значению верхней границы и не вызы¬
вают увеличения длины набора.
Управление памятью массивов
Подключение к памяти массивов явно задается в програм¬
ме командой OPEN. Первый аргумент этой команды — гло¬
бальное имя (Р), второй аргумент — имя массива (ф). При
обращении к команде OPEN среди всех имеющихся в рас¬
поряжении массивов ищется тот, имя которого эквивалентно
(в некотором предписанном смысле) имени ф. Затем адрес
найденного массива запоминается в базе процесса в позиции,
соответствующей р. Для дальнейшего управления этим мас¬
сивом необходимо использовать глобальное имя Р; адрес мас¬
сива содержит информацию, с помощью которой системные
подпрограммы определяют, какое именно устройство обеспе¬
чивает доступ к массиву, относительное расположение этого
массива, режим передачи данных и его рабочие характери¬
стики. При соответствующей интерпретации имени ф команду
OPEN можно использовать для создания новых массивов.
Память массивов автоматически отключается, когда не ос¬
тается адресов, которые на нее ссылаются.
Существуют два режима передачи отдельных записей;
режим фиксируется в момент образования массива. Первый
называется режимом передачи данных; массивы, с которыми
работают в этом режиме, называются массивами данных.
Такой режим точно соответствует обычному обмену после¬
довательностями элементарных двоичных величин между
5 Зак, 233

90
4. Базовый язык
буфером в оперативной памяти и внешним устройством. Бу¬
фер определяется заданным адресом кодослова вида 2(N), а
внешнее устройство — адресом массива. В Базовом языке рас¬
положение этих операндов в команде TFER определяет на¬
правление передачи информации, которая производится из
второго операнда в первый. Например, если элемент а имеет
вид 2 (8(N)), а элемент р — вид 1 (7), то
а TFER р Вводит блок в оперативную память
Р TFER а Выводит блок из оперативной памяти
Режим передачи данных неприменим к наборам команд
или кодослов. Достаточно сказать, что разрешение вводить
произвольные двоичные данные и рассматривать их как
команды означало бы грубое нарушение всех правил защиты,
имеющихся в системе. Как раз для работы с командами или
кодословами и предназначен структурный режим; массивы, с
которыми работают в этом режиме, называются структур¬
ными массивами. Адрес источника или места назначения
в оперативной памяти можно задать при помощи любого эле¬
мента с видом. В массив записывается вся структура, опреде¬
ляемая таким элементом, включая и самое структурную ин¬
формацию; если кодослово содержит код «не определен», то' в
массив передается запись особого вида. Когда происходит
чтение записи из структурного массива, содержащаяся в ней
информация служит для точного воссоздания данных, команд
и кодослов, по которым она была сформирована, что позво¬
ляет «запасать» часть программы, с тем чтобы использовать
ее позднее.
Дальше будет показано, что любой массив, который под¬
готавливает пользователь, должен быть из соображений на¬
дежности массивом данных; структурные массивы в основ¬
ном являются средствами хранения информации на промежу¬
точных этапах, хотя их можно использовать и для генерации
содержательных диагностических выдач.
Во многих других отношениях система управления мас¬
сивами Базовой машины предоставляет почти те же возмож¬
ности, что и традиционные машины. Необходимо ввести
специальные операции для «установки» адреса массива при
передаче каждой отдельной записи, для образования и унич¬
тожения массивов, для изменения их имен и для определения
действий при возникновении аварийных ситуаций.
Командам, предназначенным для работы с программной
памятью (EQU, INSERT) и адресами (MOD, DOT, TAG
и др.), можно сопоставить аналогичные операции над систе¬
мой массивов. Степень аналогии зависит от особенностей
представления в массивах древовидной структуры, но, как уже

4.6. Пример
91
отмечалось, детальное определение таких операций зависит
от физических характеристик устройств ввода и вывода.
Управление процессами
Подпроцесс образуется командой PROC. Первый аргумент
команды — некоторое глобальное имя, второй аргумент—имя
процесса (я). Интерпретация значения я определяет метод
распределения и объем ресурсов и позволяет также активизи¬
ровать процесс, хранящийся в памяти массивов. Дальнейшее
управление процессом осуществляется при помощи присвоен¬
ного ему глобального имени с видом 1(9).
Так как процесс мог уже стать активным к моменту обра¬
щения к нему команды CIS, необходимо ввести систему
приоритетов и с ее помощью определять, можно ли разрешать
прерывание процесса, как обслужить очередь, состоящую из
различных потоков команд, которую можно организовать, и
как продолжить вычисления после прерывания. Для достиже¬
ния большинства практических целей одного уровня преры¬
ваний достаточно, чтобы управлять подпроцессом; но прежде
чем принять окончательное инженерное решение, необходимо
провести более детальное исследование.
4.6.	Пример
Для иллюстрации некоторых особенностей программиро¬
вания на Базовом языке рассмотрим простую программу Т,
формирующую некоторую таблицу, и программу Q, которая
обращается к Т. Содержательными элементами таблицы мо¬
гут быть слова или байты, расположенные в соседних пози¬
циях, которые определяются возрастающими последователь¬
ностями индексов, начиная с индекса, равного 2. Первый
элемент таблицы содержит значение индекса, соответствую¬
щее последней занятой в данный момент позиции; первона¬
чально это значение устанавливается равным нулю.
При передаче управления программе Т в регистровом
стеке запоминается связка с меткой 1; адрес кодослова таб¬
лицы находится в хо, а значение аргумента или его адрес —
в XI. При выходе из программы вместо значения аргумента
записывается его номер в таблице. Если данного аргумента
в таблице не было, то он в нее заносится; в случае необходи¬
мости размеры таблицы можно увеличить путем возможной
интерпретации переполнения по модификации. Так как для
хранения промежуточной информации программа Т исполь¬
зует только регистровый стек, она инвариантна и, следова¬
тельно, может применяться в режиме совместного использо
вания.
5*

92
4. Базовый язык
При первом вводе текста программу Т транслируют в
двоичный код и записывают в память массивов под именем
ф{. Предполагается, что этот текст вводится в системный про¬
цесс (я0), поэтому в самом начале текста стоит команда,
образующая подпроцесс (nj), к которому процесс я0 обра¬
щается затем как к «Q». Первые две команды выполняются
непосредственно процессом яо, следующая — процессом я^
Q
Q
Т
PROC
CIS
SEG
О
Образовать новый процесс
Ввести поток команд в Q
Начать построение Т
DUMP
XO, XI, X2
хо
LOAD
xo
XI
LOAD
XI
Х2
COPY
xo
ХО
LIM
xo
Трансляцию последующих строк производит в непрямом
режиме процесс Q, формируя программу Т. Входная точка
(единственная) имеет метку ф 0.
# 0:
Сформировать адрес
таблицы
Вычислить значение
аргумента
Запомнить адрес
таблицы
Установить верхнюю
границу адреса таб¬
лицы
Заметим, что в последней команде ко второму аргументу
применяется автовыборка (чтобы взять текущую верхнюю
границу из первой позиции таблицы); а к первому аргумен¬
ту автовыборку применить нельзя, так как подразумевается,
что он является адресом. Просмотр таблицы и поиск задан¬
ного элемента описывается теперь следующими командами:
Проверить окончание и
модифицировать Х0
К 1-му аргументу при¬
меняется А/В
Определить текущий
индекс Х0 по отноше¬
нию к Х2
е:	unuumf az, ai Восстановить XI, Х2
Запомнить результат
Восстановить Х0
Выйти через связку из
стека
xo
JL
w
xo
TEST
XI
NZ
JUMP
—2
xo
MEM
X2
UNDUMP
X2,
XI
MOVE
XO
UNDUMP
XO
RET
1

4.6. Пример
93
Если найти заданный элемент не удалось, происходит об¬
ращение к такой последовательности команд:
w:	Х2	ADD	1	Увеличить	значение 1-го эле¬
мента в таблице
ХО	LOAD	Х2	Выбрать индекс нового эле¬
мента
Х2	MOD	Х2	(Увеличить	размер таблицы
при переполнении)
Х2	MOVE	XI	Запомнить	новый элемент
JUMP е Переход к заключительной
последовательности команд
END	Конец Т
Далее ввод потока команд происходит снова в прямом ре¬
жиме. Полученный ассемблером блок записывается в память
массивов, и операция CIS заканчивается:
F
F
OPEN
TFER
Ф\
Т
END
Сформировать адрес массива F
Вывести полученный сегмент
Конец ввода команд в про¬
цесс Q
Ниже приводится текст второй части программы, которая
вызывает Т из памяти массивов и применяет ее для проведе¬
ния двух сравнений с наборами тестовых данных S. Резуль¬
таты операций сравнений оформляются в виде таблицы Р.
Программа R обращается к Т для обработки последователь¬
ных аргументов из S. Предполагается, что массив ф2 обеспе¬
чивает печать результатов. Программа начинается так же,
как и предыдущая, и затем определяет R.
#0:
END
Q
PROC
Jt j
Q
CIS
R
SEG
0
V
TFER
s
Печать тестовых данных
ХО
COPY
p
Адрес таблицы
XI
LOAD
s
Адреса тестовых аргументов
1
JUMP
T
Обратиться к Т с первым
аргументом
XI
JNL
—1
Модифицировать аргументы
V
TFER
s
Напечатать индексы
V
TFER
p
Напечатать таблицу
JUMP
X2
Выйти по связке
Конец R

94
4. Базовый язык
В оставшемся куске второй части программы определяется
выводной массив, вызывается программа Т и задаются тесто¬
вые данные. Так как Т заменяет значение аргументов на таб¬
личные индексы, их нельзя задавать в виде констант, т. е. за¬
щищенных наборов. Мы предполагаем здесь некоторую ин¬
терпретацию команды MOVE по прерыванию, с помощью ко¬
торой элементы одного набора переписываются по одному в
другой набор.
Образовать вы¬
водной массив
Вызвать Т в про¬
граммную память
Отвести память
под таблицу (с
возможностью
увеличения)
I, 3,	4)	Первый набор,
тестовых данных
Переход к пер¬
вому сравнению
I, 9,	10)	Второй набор
тестовых данных
Переход ко вто¬
рому сравнению
END	Конец ввода ко¬
манд
Уничтожить Q
V
OPEN
Ф 2
F
OPEN
4>i
Т
TFER
F
Р
EQU
[0; 9]
S
EQU
[1:5]
S
MOVE
(1, 3,
Х2
JUMP
R
S
MOVE
(5, 6,
Х2
JUMP
R
Q
TAG
1

5
ТЕХНИЧЕСКИЕ ПРИЕМЫ
В первой главе уже отмечалось, что Базовая машина спо*
собна распознавать больше деталей в структуре программы,
чем это делают обычные машины, и что полученные на этой
основе достижения следует сравнить с определенными недо¬
статками, которые присущи нашей модели. Из главы 3, одна¬
ко, следует, что при реализации системы команд не возникает
никаких необычных проблем. Проверка и учет видов элемен¬
тов приводят к эффективному увеличению 6-битового кода
команды до 12-битового, причем таким общим способом, что
им можно будет пользоваться при расширении логических кон¬
струкций. Аккуратное сравнение заданных границ массивов,
производимое при выполнении адресных операций, соответ¬
ствует той проверке адресов, которая необходима в мульти¬
программных машинах (следует заметить, что в Базовой ма¬
шине проверка производится только при формировании адре¬
са по модификации, а не при каждом использовании его для
обращения к памяти). Наличие ассемблера позволяет любую
операцию реализовать в виде открытой подпрограммы или в
виде обращения к административной функции в тех случаях,
когда включение соответствующей команды в логику машины
неэкономично. Даже при решении обычных задач на нашей
машине возникают дополнительные обращения к памяти, ко¬
торые вызваны движением по древовидной структуре; однако
они с избытком компенсируются компактностью кода команд
и вытекающей из этого экономией обращений к памяти за
командами.
Для того чтобы обнаружить более серьезные недостатки
в системе, основывающейся на кодословах, нужно оценить
расходы на поддержание древовидной структуры, присущей
системе, и дополнительные расходы на написание программы,
которые придется в связи с этим понести пользователю. Таким
образом, исходя из того, что вся работа, затраченная на под¬
держание структуры памяти и не включающая в себя работу,
непосредственно нужную для проведения вычислений, является
непродуктивной, можно составить себе представление о расхо¬
дах, необходимых для реализации «непродуктивных» действий,

96
5. Технические приемы
и о том, какие параметры системы оказывают на них влияние.
Эти расходы в нашем случае достигают максимальных
размеров, так как предлагаемая система управления па-
мятью направлена на достижение следующих двух основных
целей: во-первых, представить память в той форме, которую
выбирает программист (можно предположить, что это дает
определенную выгоду); во-вторых, объединить.в единую си¬
стему оперативную память и буферные памяти различных ти¬
пов, что должно быть обеспечено теми или иными средствами
на всех машинах. Однако можно предусмотреть наиболее
неблагоприятные обстоятельства и ввести в систему целый
ряд технических приемов, которые позволят удержать непро¬
дуктивные расходы в обычных границах. В настоящей главе
мы изучим ряд таких приемов и отметим ограничения, кото¬
рые налагаются на программирование.
5.1.	Общие вопросы управления памятью
Даже в самых простых схемах распределения памяти на-
любом носителе все имеющиеся в распоряжении блоки па¬
мяти делятся на активные и неактивные; запросы памяти
удовлетворяются путем поиска достаточно большого блока
памяти в неактивной области, причем часть неактивного бло¬
ка переводится затем в разряд активных. Такой процесс мо¬
жет продолжаться до тех пор, пока не обнаружится, что в
неактивной области подходящего блока нет; тогда должны
быть приняты более или менее решительные меры для попол¬
нения неактивной области. Эта ситуация знакома всякому,
кому приходилось упаковывать багаж, отправляясь отды¬
хать; чтобы не откладывать поездку, обычно прибегают к
одной из менее крутых мер, т. е.:
(a) к реорганизации имеющегося распределения, чтобы
получить в распоряжение более крупные неактивные
блоки, например сдвигая все активные элементы в
один конец;
(b) к перенесению некоторых элементов в хранилище
другого вида (например, в багажное помещение);
принимая это решение, обычно основываются на
частоте использования данного блока; этот критерий
влияет на производительность системы;
(c) к увеличению числа элементов неактивной памяти,
основываясь на рассмотрении принадлежности актив¬
ных элементов некоторому процессу и путем передачи
их другим процессам, как только процесс закончится

5.1. Общие вопросы управления памятью
97
(предполагается, что процесс не может закончиться
до тех пор, пока не закончились все его подпроцессы).
Путешественник сталкивается с такой ситуацией,
когда половина участников его группы в конце кон¬
цов отказывается от поездки.
Элементы памяти Базовой машины могут иметь разную
длину: от одного байта до 216 слов двойной длины. Неактив¬
ную память можно представить в виде набора I наборов бай¬
тов, и поиск блока памяти длиной не меньше чем XI опреде¬
лить следующим образом:
хо
LOAD
I
Адрес неактивной последовательности
Х2
LOAD
XO
Адрес первого элемента
Х2
INDEX
X2
Найти длину
Х2
SUB*
XI
Сравнить
GE
JUMP
f
f: блок найден
ХО
JNL
—4
Повторить, если блок мал
(Возможно, что в машине с высокой производительностью
этот цикл будет оформлен как одна команда.)
Затраты, связанные с просмотром неактивных наборов,
почти прямо пропорциональны среднему количеству тех набо¬
ров, которые нужно перебрать, прежде чем поиск увенчается
успехом, а это количество в свою очередь определяется состоя¬
нием всех выполняемых в это время процессов. В предельном
случае, когда длины всех наборов одинаковы, поиск должен
сразу же закончиться успешно при условии, что I непусто, но
практика показывает, что невыгодно требовать выполнения
этого условия в тех случаях, когда длина блоков, определяе¬
мая природой задачи, сильно меняется и средняя длина на¬
много меньше максимальной. Другим решением является вы¬
деление памяти в виде нескольких блоков фиксированной
длины; это достигается путем округления каждого запроса
памяти до нужного целого числа блоков, чтобы не заботиться
об управлении маленькими кусками памяти. Подходящий
фиксированный размер такого блока зависит от локальных
обстоятельств, и, так как распределение памяти производится
при помощи системных программ, можно варьировать длину
до тех пор, пока не будет подобран оптимальный вариант.
Еще один метод, который можно сочетать с предыдущим,
состоит в том, чтобы для сокращения просмотра памяти выде¬
лить несколько неактивных наборов, каждый из которых объ¬
единяет элементы памяти, определяемые некоторым диапазо¬
ном длин. Вообще искушение разработать более тонкие алго¬
ритмы управления памятью подавляется тем обстоятельством,

98
5. Технические приемы
что при средних условиях решения задач на машине запросы
памяти относительно редки и что лучше проводить массовое
перераспределение памяти в те моменты, которые выбирает
для этого операционная система, чем отнимать у пользова¬
теля время на детальную реализацию системы учета, связан¬
ной с распределением памяти.
Реорганизация
Идеальная ситуация, когда каждый запрос памяти можно
удовлетворить при помощи нескольких десятков команд, а по¬
полнение неактивной области происходит за счет естествен¬
ного окончания процессов, может, вероятно, сложиться толь¬
ко в очень больших или специализированных системах. Когда
поиск затребованной памяти заканчивается неудачей, хотя
суммарный объем неактивной области памяти достаточно ве¬
лик для удовлетворения данного запроса, можно прибегнуть
к частичному перераспределению активной памяти. Как отме¬
чалось в гл. 2, при перемещении блока активной памяти все
ссылающиеся на него адреса (включая его кодослово) дол¬
жны быть пересчитаны, и поэтому нужно просмотреть поме--
ченную область памяти, относящуюся к тому процессу, кото¬
рому принадлежит этот блок, и такие же области всех его
подпроцессов. Таким образом, когда отдельный блок переме¬
щается либо для того, чтобы освободить место другому
блоку, либо в результате выполнения команды INSERT или
в случае необходимости увеличения размера блока при пере¬
полнении по модификации (стр. 82), расходы на перераспре¬
деление памяти, грубо говоря, пропорциональны сумме длин
данного блока и помеченной области, взятых в этот момент
времени. При перемещении нескольких блоков связанные
с каждым из них расходы пропорциональны длине соответ¬
ствующего блока и общему количеству адресов в помеченной
области памяти, так что у массовых перемещений есть не¬
большое преимущество.
Частота использования
Мера частоты использования может быть определена
в Базовой машине следующим образом. Любой последова¬
тельности элементов, адрес которой имеется в базе процесса,
приписывается U-значение, равное единице. Кодослово с U-
значением v приписывает набору, который оно определяет,
U-значение, равное v+1; исключениями являются последо¬
вательности, допускающие прямую адресацию. Тогда любому
элементу программной памяти, к которому можно получить

5.1. Общие вопросы управления памятью
99
доступ, приписывается единственное U-значение в пределах
от единицы до числа, равного максимальному рангу дерева.
Заметим, что некоторый элемент можно сделать недоступным
путем освобождения его места в базе процесса или путем за¬
несения новых элементов в базу на место старых. Например,
в результате выполнения команд
Х6	TAG	1	Освободить Х6
Х6	EQU	[0:19]	Набор из 20 слов
Х6	LOAD	10	Запомнить новый	адрес вместо
старого
элементы набора, определяемые второй командой, становятся
недоступными и могут быть включены в неактивную область
памяти.
В предположении, что при генерации команд предприни¬
маются усилия, направленные на рациональное уменьшение
длины адресного пути, такая интерпретация U-значеиий, при
которой в памяти с более быстрым доступом хранятся эле¬
менты самого нижнего уровня, приведет к дальнейшей опти¬
мизации и к повышению производительности системы. Таким
образом, элементы с U-значением, равным единице, должны
храниться вместе с базами процесса в областях памяти с са¬
мым быстрым доступом, а наборы, U-значения которых рав¬
ны или больше двух, становятся кандидатами на изгнание
на более медленные носители, если не удается удовлетворить
запрос при помощи реорганизации. Рекомендуется применять
лишь такие методы, при использовании которых можно изго¬
нять любые элементы, кроме абсолютных кодослов, так как
их присутствие в оперативной памяти облегчает управление
вспомогательной памятью. Более тонкий прием заключается
в том, что периодически каждому абсолютному кодослову
присваивается значение вида 1, а по прерыванию, возникаю¬
щему при попытке использования данного кодослова, его вид
устанавливается равным 2 и работа продолжается обычным
образом. При таком методе в первую очередь изгоняются те
наборы, к которым за данный период времени не было обра¬
щений.
Приостановка процессов
Если в мультипрограммной системе некоторый запрос па¬
мяти не может быть сразу же удовлетворен, то выполнение
процесса, выдавшего этот запрос, обычно временно прекра¬
щается до следующей реорганизации памяти или до очеред¬
ной фазы изгнания. Если и тогда удовлетворить запрос будет

100
5. Технические приемы
невозможно и при этом все процессы окажутся в таком же
состоянии (т. е. приостановлены), останется последнее сред¬
ство— освободить память, переместив все наборы, принадле¬
жащие одному или нескольким процессам, в буферную
память. При этом каждый адрес преобразуется в соответ¬
ствующий адрес буферной памяти. Если приняты особые
меры, позволяющие изменять ссылки на массивы и память
супервайзеров, можно перемещать в буферную память даже
базы процессов. В таком состоянии процессы остаются до тех
пор, пока система не найдет времени и места в памяти для
того, чтобы возобновить их.
5.2.	Специальные представления
С помощью специальных методов, использующих то об¬
стоятельство, что форматы адресов скрыты от программиста,
применяющего Базовый язык, можно уменьшить количество
реорганизаций памяти и расходы на перемещение блоков па¬
мяти. В этом разделе описаны два таких метода. Будет пока¬
зано, что их составной частью являются специальные способы
вычисления значений и модификации кодослов, которые мо¬
гут быть включены в логику машины подобно тому, как это
сделано с относительными кодословами и описано в гл. 3.
Кодослова, определяющие списочную структуру
Есди последовательность, к которой обращается команда
INSERT, хранится в виде списочной структуры, а не в виде
последовательных ячеек блока памяти, время выполнения
этой операции сильно сокращается. В этом случае адрес сле¬
дующего элемента задается явно, а не вычисляется путем
прибавления к адресу данной ячейки одного из чисел: 1, 4
или 8. В абсолютном кодослове есть «резервные» 16 битов
для задания номера следующей ячейки п (двойного слова).
У последнего элемента значение адреса следующей ячейки
равно «нулю».
3 5
24
16
16
Вид
ГГ V
1
п
/77
Следующий
элемент
Кодослово
списочной
структуры
Остальная информация задается так же, как и в «линей¬
ном» кодослове. Для ссылок на организованную в виде спи¬

5.2. Специальные представления
101
сочной структуры последовательность кодослов используется
специальный код типа (вместо обычного значения типа 8);
по этому значению их опознают команды модификации, ко¬
торые используют содержащиеся в них ссылки для перехода
к следующему элементу.
Включение новых элементов в организованный в виде спи¬
сочной структуры набор и вычеркивание элементов из такого
набора производятся сравнительно безболезненно, если не
пытаться привести значения верхних границ в соответствие
со вновь полученной структурой. На практике значение верх¬
ней границы длины кодослова устанавливается равным мак¬
симальной величине—(216—1), а конец набора опреде¬
ляется при помощи команд JL или JNL, которые обычным
образом отличают последний элемент. Однако для формиро¬
вания адреса списочной подструктуры можно, как обычно, ис¬
пользовать команду LIM. Программист не может совершенно
безразлично относиться к тому, как организован набор —
в линейном виде или в форме списочной структуры; на уровне
языка ассемблера это по меньшей мере спорный вопрос. Пре¬
имущество применения списочной структуры заключается
в том, что она обеспечивает большую гибкость, не выходя
при этом за рамки тех соглашений, которые приняты в нашем
языке. При этом приходится расплачиваться тем, что моди¬
фикация выполняется медленно, но все же при помощи ма¬
шинной команды, которая работает значительно быстрее, чем
аппарат, используемый для этой цели в традиционных ма¬
шинах в системах по обработке списков (хотя логически
наша списочная структура не совпадает полностью с поня¬
тием списка).
Страничная память
Часть расходов на реорганизацию памяти вызвана необ¬
ходимостью физически перемещать информацию из одной об¬
ласти памяти в другую. Ее можно существенно сократить,
разделив оперативную память на некоторое количество стра¬
ниц одинакового размера, адресоваться к которым можно
косвенным путем через таблицу страниц. Тогда в физической
реорганизации будет нуждаться только сама эта таблица.
Рассмотрим, например, ферритовую память, состоящую из
218 байтов, разделенную на 210 страниц по 28 байтов в каждой.
Первые восемь страниц (210 полуслов) заняты таблицей стра¬
ниц, а оставшиеся 1016 страниц можно использовать для про¬
граммной памяти. Каждое из последних 1016 полуслов таб¬
лицы страниц содержит адрес страницы, который состоит из

102
5. Технические приемы
десяти двоичных разрядов, определяющих номер страницы
в программной памяти, причем все адреса страниц различны.
Элемент
таблицы
страниц
страницы
Номер ячейки, определенной элементом с видом 2, теперь
можно разделить на восемь младших двоичных разрядов,
определяющих местоположение данного байта и шестнадцать
старших двоичных разрядов (из них значащих разрядов
только десять), которые задают элемент таблицы страниц.
Поэтому теоретически доступ к памяти можно получить, оп¬
ределив по таблице страниц адрес страницы и используя его
вместе с адресом, определяющим местоположение байта, для
выделения заданного элемента из программной памяти.
На практике адрес страницы сохраняется как часть слова
со значением вида 2, и новое обращение к таблице страниц
необходимо лишь в том случае, когда значение Ь выходит за
пр еделы страницы при модификации. Во всех остальных слу¬
чаях адресация остается прямой.
3
5
24
6
10
16
Страничный
адрес
Вид
2
* I
b
р
Методы, применявшиеся раньше для управления всей па¬
мятью, теперь можно приспособить для работы с самой та¬
блицей страниц. Все запросы памяти округляются до целого
числа страниц. Адреса неактивных страниц специальным об¬
разом помечаются — их можно, например, задавать в допол¬
нительном коде, тогда поиск нужного свободного участка па¬
мяти сведется к просмотру таблицы страниц для выявления
требуемого количества последовательных (по расположению
в таблице) неактивных страниц. Если просмотр завершится
неудачей, будет проведена реорганизация памяти, состоящая
в перемещении адресов активных страниц из одного места
таблицы в другое и в обычном изменении адресов и кодослов.
Наконец, фиксированную длину страниц можно использовать
так, как уже делалось раньше для объединения в одно целое
оперативной и вспомогательной памяти.
Виртуальная память
Указанные ранее преимущества использования таблицы
страниц можно развить, увеличивая длину таблицы с целью
уменьшения числа реорганизаций памяти. При этом следует
6 ю
•'••V Р
ЛОрес

5.2. Специальные представления
103
иметь в виду, что выигрыша от удвоения длины таблицы мо¬
жно ожидать только в том случае, если при этом потребуется
проводить реорганизацию памяти по меньшей мере в два
раза реже, так как эта операция будет выполняться в два
раза дольше.
На примере, разобранном выше, мы можем рассмотреть,
какие последствия вызовет увеличение таблицы страниц до
2048 полуслов (шестнадцать страниц). Программа сможет
занимать до 1008 страниц оперативной памяти, и для нахо¬
ждения ее адресов нужно обращаться к таблице страниц.
Остальные 1040 элементов таблицы определяются как сво¬
бодные, и их значения будут заданы нулями. Следовательно,
каждый элемент таблицы является либо активным, либо не¬
активным, либо свободным (мы не рассматриваем переход¬
ные состояния и возможные ссылки на буферную память).
Механизм адресации остается неизменным, за исключе¬
нием того, что адрес элемента в таблице страниц увеличи¬
вается до 11 двоичных разрядов. Для удовлетворения за¬
проса нужно найти последовательность неактивных или сво¬
бодных элементов таблицы, но, так как больше половины
таблицы занимают теперь свободные элементы, шансы на
успех значительно выше, чем раньше. Свободный элемент
таблицы можно использовать только после того, как будет
найден адрес некоторой неактивной страницы и записан на
место этого элемента, но на эту операцию расходуется очень
мало времени. Поэтому программы управления памятью стал¬
киваются лишь с проблемой отображения памяти объемом
до 218 байтов в виртуальную память объемом в 219 байтов, и
надо полагать, что возможность более свободного маневри¬
рования приведет, при известных обстоятельствах, к опреде¬
ленному выигрышу. Однако потенциальная производитель¬
ность системы несколько уменьшится за счет сокращения
объема оперативной памяти.
На обычной машине, такой, как ICT Atlas, успешное раз¬
деление памяти на страницы основывается на возможности
организовать виртуальную память такого размера, что реор¬
ганизация вообще становится ненужной. Так, в машине Atlas
номера ячейки, состоящего из 24 двоичных разрядов, доста¬
точно для доступа к памяти, организованной специальным
образом и состоящей из 4096 страниц по 4096 байтов (зна¬
ков) в каждой; половина номера служит для прямого обра¬
щения к резидентным системным программам, а оставшаяся
часть может использоваться любой программой при помощи
связанной с каждой программой отдельной таблицы страниц.
В машине General Electric 645, допускающей как сегментиро¬
вание памяти, так и разделение ее на страницы, обеспечи¬

104
5. Технические приемы
вается длина адреса в 36 битов. Хотя те же самые принципы
можно применить и к машине, использующей кодослова, сле¬
дует иметь в виду, что при такой организации памяти может
наступить момент, когда расходы на хранение и содержание
виртуальной таблицы страниц превысят то зло (а именно
цену реорганизации памяти), для борьбы с которым была
введена эта таблица; поэтому в такой системе представляется
невозможным извлечь пользу из применения таблицы страниц,
много большей по объему той физической памяти, которая
предусмотрена в Базовой машине. Следует также отметить,
что предложенная выше страничная система памяти не тре¬
бует ни дополнительной быстрой памяти, кроме тех десяти
двоичных разрядов, которые выделяются в страничном адресе
в каждом регистре, ни ассоциативного механизма выборки.
Адресация всегда производится прямым способом, кроме тех
случаев, когда происходит переход через границу страницы.
Во всех системах со страничной памятью некоторый объем
памяти теряется за счет округления каждого запроса до це¬
лого числа страниц, и эти потери можно уменьшить, выбирая
страницы небольшого размера'. Это, однако, влечет за собой
усиление «граничных» эффектов (какая бы схема страничной
памяти ни применялась) и увеличение накладных расходов
на организацию переписи во вспомогательную память и об¬
ратно. В Базовой машине нет необходимости использовать
страничную организацию памяти для небольших по размерам
элементов информации, и мы можем разрешить указанную
дилемму следующим образом. Для работы приблизительно
с 80% оперативной памяти выбирается удобный, достаточно
большой размер страниц, а остальную часть памяти зани¬
мают элементы небольшого размера: наборы данных, кодо¬
слова, элементы списочной структуры и т. д., распределение
которых производится другими методами. При таком подходе,
вероятно, удастся эффективно использовать быструю опера¬
тивную память, не перегружая работой таблицу страниц и
систему управления вспомогательной памятью.
5.3.	Погружение
Исходя из предположения, что структурная информация
не дает никаких ощутимых преимуществ при развитии про¬
грамм и при их выполнении, мы можем рассмотреть шаги,
необходимые для приведения программы к линейной форме
в тех случаях, когда не предвидится никаких изменений в ее
структуре. Используя относительные кодослова, легко пред¬
ставить любую часть дерева программы в виде единого бло¬
ка, хотя при этом, может быть, придется ввести представле¬

5.3. Погружение
105
ние кодослов, охватывающих больший диапазон, чем тот, ко¬
торый рассмотрен в гл. 3. Ассемблер всегда может вычислить
локальные составные имена, такие, как h. 3.0, и выразить их
непосредственно в виде адресов относительно регистра ХС,
так что при формировании большой последовательности
команд произойдет некоторое сокращение путей поиска по
адресу. Но вряд ли можно, не затрагивая Базового языка,
полностью избавиться таким способом от относительных ко¬
дослов и получить при этом какую-то пользу, поскольку со¬
держащаяся в них информация хранится в компактном виде
и эффективно обрабатывается.
Остается рассмотреть самое базу процесса и различные
специальные операции, которые обычно вводятся в действие
при помощи абсолютных кодослов. Если база расположена
вплотную к полю программной области, то на регистр XD
естественно возложить роль граничной пары, определяющей
общий блок памяти, который можно организовать следующим
образом:
1) регистры (128 байтов);
2) продолжение регистровой памяти;
3) программная область;
4) регистровый стек.
Локальные адреса, находящиеся в базе процесса, могли
бы храниться в относительной форме и при использовании
автоматически модифицироваться адресом регистра XD и, та¬
ким образом, не требовали бы внимания со стороны про¬
граммы управления памятью. Сссылки на другие программы
по-прежнему хранились бы в абсолютной форме и при реор¬
ганизации требовали бы корректировки.
Существуют два вида прерывания по абсолютным кодо-
словам, которые не допускаются в относительных кодосло-
вах: при защите памяти (вид 1(5)) и при ссылке на буфер¬
ную память (вид 1(6)). В первом случае можно было бы
снять ограничения с помощью программ управления внеш¬
ними массивами и процессами, а в последнем этого сделать
нельзя, поскольку это противоречит предположению о неиз¬
меняемости тела программы.
Важно рассмотреть, как меняется характер системы при
описанных выше изменениях; сошлемся для этого на выводы,
сделанные в конце гл. 1 (стр. 26). Поскольку структура по-
прежнему существует в форме относительных кодослов, ко¬
дов вида и типа, сохраняется и преимущество точного пред¬
ставления; о программах по-прежнему можно говорить, что
они хорошо приспособлены для решения класса задач, для
которых количество требуемой памяти можно предсказать

106
5. Технические приемы
до начала выполнения. Сохраняется независимость вводного
языка от его внутреннего представления (в силу того, что
оно скрыто от пользователя), но полное преимущество инте¬
грации операционной системы с машиной теряется из-за
жесткой структуры памяти, которая делает маловероятным
осуществление какого-либо продвижения вперед в техниче¬
ском отношении. Затраты на выполнение программы вряд ли
ощутимо изменятся, но дополнительные расходы, связанные
с распределением памяти, можно было бы уменьшить, если
бы приходилось иметь дело только с одним блоком для ка¬
ждого процесса, хотя при наличии буферной памяти полу¬
чаемые преимущества, по-видимому, будут недолговечными.
Наконец, сам Базовый язык, если не считать исчезновения
операторов EQU, INSERT и CIS, изменится очень мало.
Ограничения, касающиеся видов элементов, должны оста¬
ваться до тех пор, пока есть необходимость в утаивании
формы адресов и команд от пользователя.
5.4.	Расширения
Естественно завершить описание достаточно разработан¬
ных аспектов машины с Базовым языком кратким обзором
некоторых расширений, которые можно тут же ввести в нашу
модель.
Данные, образованные несколькими элементами
Предложенный 64-разрядный размер регистра обусловлен
необходимостью обеспечения вычислений с высокой точно¬
стью. В определенных обстоятельствах дальнейшее увеличе¬
ние размера элемента с целью получить еще более высокую
точность вычислений могло бы быть оправданным, но вообще
это привело бы только к бесполезной трате места в регистрах
и базе процесса, поскольку размеры всех элементов смешан¬
ного типа должны быть расширены до максимального. Дру¬
гой подход, который пригоден как для математических, так
и для коммерческих расчетов, состоит в том, что целую после¬
довательность рассматривают как один операнд арифметиче¬
ской операции, введя отличительные коды типов. Например,
если тип 16 соответствует десятичной цифре, изображенной
стандартным образом четырьмя двоичными разрядами, то
адрес вида 2(16) со значением верхней границы, равным т,
определяет число из гп -f- 1 цифры. Программа сложения двух
таких чисел XI и Х2 состоит из одной команды
XI ADD Х2

5.4. Расширения
107
Ее выполнение производится методом последовательной ин¬
терпретации: по одной компоненте за один раз. Аналогично
команда SUB* дает возможность сравнивать поля данных, со¬
стоящие из многих элементов (следует принять меры предо¬
сторожности, чтобы обеспечить правильное сравнение после¬
довательностей байтов (строк символов) при использовании
этой операции).
При образовании подпоследовательностей данных, обра¬
зованных несколькими элементами, адресные операции вы¬
полняются как обычно; преобразование единиц информации,
образованных несколькими элементами, в обычные и обратно
осуществляется операцией TAG. Заметим, что «простую» по¬
следовательность данных, образованных несколькими эле¬
ментами, можно рассматривать как обычную последователь¬
ность отдельных элементов.
Описания
Структурная информация, которая не может быть пред¬
ставлена непосредственно, обычно задается при помощи опи¬
саний, содержание которых погружается в порождаемые
команды. Так поступают с типами и структурой наборов дан¬
ных в традиционных машинах, а в машине с Базовым языком
они распознаются аппаратным оборудованием. Существует
несколько особых случаев, когда метод описаний, по-види¬
мому, стоит применить и в Базовом языке; этим методом
особенно удобно пользоваться при интерпретации иден¬
тификаторов. В одном из таких случаев при помощи описа¬
ния вида
LET а = 2
идентификатору во входном тексте ставится в соответствие
его расширенная форма, заданная в виде строки термов
(в нашем случае а — идентификатор, а 2— его формальное
расширение). Например, элементы набора можно снабдить
идентификаторами посредством описаний:
LET	А = к. О
LET	В = к .1
и т. д. Теперь А, В и т. д. могут на законных основаниях
встречаться в любом контексте, где допустимо использование
составных имен. Можно предложить более компактный спо¬
соб записи подобных отношений, например
LET к = (А, В, С, D)

108
5. Технические приемы
Вместе с описанием наборов переменных и констант опера¬
торы такого рода позволяют ассемблеру аккуратно использо¬
вать небольшие отрезки памяти, что очень важно при ее
жестком распределении. Постоянно используемые расшире¬
ния можно задавать различными способами, доводя их до
параметрической формы; один из наиболее очевидных прие¬
мов—это введение макроопределений операций, которые по¬
зволят определять «машинные команды», создаваемые поль¬
зователем.
Для системы, допускающей описания, необходимо, чтобы
во время ассемблирования была известна полная информа¬
ция о структуре; поэтому ее следует применять к локальным
именам, а не к глобальным. Например, можно попытаться
при помощи описаний «типа» осуществить объединение в одно
целое программной памяти и внешних массивов:
FILE F, G, Н
Это описание идентифицирует адреса внешних массивов и
дает ассемблеру возможность вставлять операции управле¬
ния внешними массивам вместо адресных при обращении
к переменным данным.
Однако нельзя привести никаких доказательств в пользу
запрещения копировать адреса внешних массивов в любую
другую позицию базы, и единственный путь, обеспечивающий
защиту такой системы, — динамическая интерпретация эле¬
ментов с видом 1(7).
Выражения
Введение знаков двуместных операций ( + , —, *, /), со¬
ответствующих машинным операциям ADD, SUB, MPY и
DIV, и построение с их помощью выражений в соответствии
с обычными арифметическими правилами последовательности
действий позволяют расширить язык еще в одном направле¬
нии. Неделимыми членами таких выражений являются кон¬
станты или составные имена, которые, как мы уже отмечали,
сами могут служить подходящими объектами для обобщения.
Предполагается, что выражение будет вычислено в тот мо¬
мент, когда будет достигнута точка в иерархической струк¬
туре программной памяти, в которой оно встречается. Здесь
следует отметить, что было бы разумно обобщить понятие
«вычисление», чтобы можно было выполнять различные фор¬
мальные преобразования выражений.
Одно из следствий принципа защиты команд состоит
в том, что комплект центральных регистров можно распреде¬
лить между различными частями системы оптимальным об¬

5.4. Расширения
109
разом. Распределение регистров, описанное в гл. 3, не обяза¬
тельно оставлять навсегда: регистры ХА, ХВ, .. ., XF можно
использовать и по-другому, поскольку в Базовом языке они
вовсе не упоминаются. При широком использовании алгебра¬
ического аппарата можно рассмотреть вопрос о том, чтобы
отвести больше регистров для специальных целей и ввести
естественные алгебраические операции на уровне Базовой
машины, сохранив форму языка. Действительное количество
аппаратных регистров остается неопределенным; его можно
выбрать в любой момент, исходя из экономической выгодно¬
сти системы и удобства программирования для нее.
Вычисление выражений
Мы опять сталкиваемся с ситуацией, в которой при усло¬
вии, что структура доступна ассемблеру, она может быть лег¬
ко погружена в порождаемую программу. Если выражение
неизвестно во время написания программы, то в нужном ме¬
сте обычно вставляют передачу управления на подпрограмму,
которую предполагают написать позднее. Но может случиться
так, что мы узнаем о необходимости введения выражения
лишь тогда, когда программирование уже закончено. Так об¬
стоит дело со всеми глобальными переменными, и в особенно¬
сти с параметрами, которые могут определяться числовыми
значениями, адресами, недействительными элементами или
формулами, которые надо вычислять динамически. Аппарат
прерываний в Базовой машине обеспечивает необходимый ме¬
ханизм для эффективной обработки таких ситуаций без не¬
удобных описаний «типов» параметров.
Можно предсказать два направления дальнейшего разви¬
тия простейшего способа трансляции выражений. Первое оп¬
ределяется тем, что вычисление выражений частично или пол¬
ностью откладывается до начала выполнения программы,
а преобразование и вычисление выражений производится ди¬
намически; второе (противоположное) опирается на то, что вы¬
ражения частично или полностью вычисляются ассемблером,
использующим постоянную информацию для получения более
эффективной программы. Следующий важный шаг в усовер¬
шенствовании Базового языка может быть сделан при после¬
довательном рассмотрении всего широкого спектра направ¬
лений, в которых развивается вычисление выражений.

ПРИЛОЖЕНИЕ
Введенный в гл. 4 язык основывается на следующих клас¬
сах основных элементов:
Название	Идентифи-	Определение
катор
класса
Имя операции
0
См. табл.
5
Имя регистра
X
<Х0| XI |.
.. | Х9>
Целые числа
.и
(01 1 12 | . .
• ИТ. д.)
Мнемоника условий
У
См. табл.
4
Идентификатор-1
fil
(А|В|...
IZ)
Идентификатор-2
62
(а|b | ...|
z>
Недействительный элемент
Q
Не определен
Следующие постоянные символы также употребляются в даль¬
нейших конструкциях:
Точка
Двоеточие	:
Круглые скобки	( )
Запятая	,
Минус	—
Кроме того, в формальных определениях символ е исполь¬
зуется для обозначения пустой позиции, а символ «точка с за¬
пятой»— для обозначения «новой строки».
Теперь можно определить следующие классы:
Глобальное имя
Р
<xl
б.)
Локальное имя
а
<62
1 #И>
Целое со знаком
Vs
| —И>
Глобальное составное имя
Л2
<Р|
Tfe • И>
Локальное составное имя
Л1
(а|
Л1 • .и)
Составное имя
Л
<*li
|rb|Q>
Обобщенный аргумент
k
Входная точка	ф
Тестовый вариант *
Точка с запятой	;

П риложение
111
Формат задания имен массивов j> и процессов я не фикси¬
руется; такие имена обычно представлены наборами байтов.
Если Я — идентификатор любого класса, то можно опреде¬
лить следующие конструкции:
Список
Я-список
(Я [Я-список, Я)
Отсюда следует:
Константа
а
<О-01 (Г, 1 сг21 ps)
Набор нулей
°о
[р< :|;>р]
Набор констант
(щ-список)
Набор постоянных
имен
<*2
(^-список)
Команды в зависимости от имени операции 0 разде¬
ляются на несколько классов, имеющих различные форматы
с номерами от 1 до 9 (см. табл. 5).
Команда со {щ | со21 со31 со41 со51 соб | со71 ю8 [ со9)
coj	r\Qk
щ ре <Г| I ц>
(о3	pop
С04	Р06
©5	0 6-СПИСОК
Ю6	Г|0Р
<Р|е|ц|у)0^
CDs	0р
со9	0 Р-СПИСОК
Следует отметить, что в тех случаях, когда имеет значе¬
ние лишь вырабатываемый код условия, операцию 0 можно
заменять в приведенных выше форматах на 0* для того,
чтобы обеспечить тестовый вариант «только сравнение» вы¬
полнения команды.
Определение текста программы завершается следующими
конструкциями:
Р	<Pl I Р2>
Pi (ill = I е) ©
р2 Т1,: о
SEGli; р; р; . . . р; END
т2 CIS; (rj со); (tj| со); ... (rjco); END
Строка
Команда
Константа
Непрямой текст
Прямой текст

Тип
О
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ТАБЛИЦЫ
Таблица 1. Коды вида (g)
Вид	Смысловое значение
0	32-разрядное слово
1	Код прерывания (недействительный эле¬
мент)
2	45-разрядный адрес
3	61-разрядный числовой	элемент
Таблица 2. Коды типа (t) и размеры элементов
Смысловое значение	Размер	(в	битах)
Двоичное слово
32
Байт
8
Двоичное слово (только чтение.
32
Байт (только чтение)
8
Команда (режим 0)
32
Команда (режим 1)
32
Команда (режим 2)
32
Команда (режим 3)
32
Абсолютное кодослово
32
Относительное кодослово
32
Смешанный тип
64
Смешанный тип (только чтение)
64
Длинный числовой элемент
64
Короткий числовой элемент
32
Длинный числовой элемент (только чтение)
64
Короткий числовой элемент (только чтение)
32

Таблица 3. Операции Базовой машины
113
Мнемони¬
ческое	Пояснения	к	названию	Группа	Результат	операции
название
ADD	Сложить	А
AND	Умножить (логически)	А
COPY	Скопировать	В
OIV	Разделить	А
DOT	Продолжить по точке	D
(«точка»)
DUMP	Переслать содержимое	В
регистров в стек
INDEX	Вычислить значение верх-	D
ней границы
JUMP	Передать управление	С
JL	Передать управление, ес-	С
ли элемент последний
JNL	Передать управление, ес-	С
ли элемент не послед¬
ний
JNT	Передать управление, ес-	С
ли задан режим транс¬
ляции
Передать управление в	В
базу программы
JSL	Передать управление, за-	С
помнив связку в ре¬
гистре
JSM	Передать управление, за-	С
помнив в стеке связку
с заданной меткой
LDN	Загрузить, изменив знак	D
LIМ	Установить верхнюю гра-	D
ницу
LOAD	Загрузить	D
LPB	Загрузить адрес базы	В
программы
МЕМ	Вычислить индекс одного	D
набора относительно
другого
MOD	Модифицировать	D
MON	Обратиться к монитору	С
MOVE	Переслать с редактиро-	А
ванием
МРУ	Умножить	А
NEQ	Сравнить (логическая не-	А
эквивалентность)
NOT	Получить отрицание	А
OR	Сложить логически	А
RET	Выйти из программы	С
RE	Установить элемент сме-	В
шанной последователь¬
ности на регистр
х + У
Ъ Ау
У
х/у
Х.у
Регистры —в стек (Nie)
Верхняя граница (У)
Передача управления у
при условии N4
Переход, если X послед¬
ний
Переход, если X не по¬
следний
Переход, если нет трас¬
сировки
Переход к базе програм¬
мы Nie
Переход с запоминанием
связки в X
Переход с установкой
метки N3
“У
Установить в X верхнюю
границу у
Значение (У)
Установить адрес базы
программы N16
Индекс X в У
X модифицируется при
помощи у
Код монитора N2
У
X *у
хфу
Гу
X v у
Возврат по метке N3
Элемент смешанной по¬
следовательности выби¬
рается на регистр X

114
Продолжение
Мнемони-
ческое
название
Пояснения к названию
Группа
Результат операции
RS
Запомнить регистр в по¬
следовательности сме¬
шанного типа
В
Содержимое регистра X
запоминается в после¬
довательности смешан¬
ного типа
SCALE
Промасштабировать
А
х *2у ■
SHIFT
Сдвинуть (логически)
А
х сдвигается по у (логи¬
ческая операция)
SIZE
Вычислить точность пред¬
ставления
А
Точность (у)
SUB
Вычесть
А
х — у
TEST
Проверить
А
х — у (устанавливаются
только коды условия,
результат не заносится
на место первого аргу¬
мента)
TTAG
Сравнить или переслать
вид
D
Сравнивается вид X с N3
или вид Y выбирается
на X
TTY PE
Сравнить или переслать
тип
D
Сравнивается тип X с N5
или тип Y выбирается
на X
UNDUMP
Переслать заданные эле¬
менты стека в регистры
В
Элементы стека пересы¬
лаются в регистры (Nie)
WTAG
Присвоить вид
D
Установить вид X рав¬
ным N3
WTYPE
Присвоить тип
D
Установить тип X рав¬
ным N5
Пояснения к обозначениям табл. 3
X — регистр, соответствующий первому аргументу
У—второй аргумент
х — первый операнд, полученный по правилу А/В
у— второй операнд, полученный по правилу А/В
Nj — /-разрядный литеральный аргумент
Таблица 4: Мнемоника условных
переходов
Мнемоника	Проверка
GE	>0
GT	>0
IR	Некорректный результат
LE	<0
LT	<0
NZ	^0
VR Корректный результат
ZE	= 0

Т а б лица 5: Команды Базового языка ])
а*
О
а
а
к
&
£
о.
<
Я
о
&,
с
оз
о
я
s
о
4
5
и
Ч CL) CU
4
я
03
5
о
я
4
о
£
-©*
К
о.
<
S
>>
Я
5
23
03
6
Cl
О
VO
CG СО ^
S
03
4
о>
я
ч
Я 5Д
>» я
О. Я
С S
^ ч
03
03 Ч
СГ о
03 О
4 с
си
о
»я
03
я
и
о.
03
а
к
я
О)
ч
и
я
а,
с
>,
*
03
4
Ч
я
я
я
CL
я
t:
I
с с а с
S.
CG
£9
ся
<
я
a
<
Я
§
<
я
Н
<
я
э
CG
<
CQ
<
сo'
СО
о
a
о
о
a
о
£
о
о
£
о
Я
9
я
9
d
н
я
я
о.
я
я
я
CL
д
ьГ
я
я
о.
я
я
я
CL
я
и
СМ
о
£
о
я
см
<м
см
о
a
о
я
СЗ
a
о
2
о
«я
о
Z
о
*Я
о
•я
о
я
Си
Я
о
я
о
я
•я
о
я
си
я
•я
о
я
VO
я
VO
аГ
VO
2
я
VO
U
VO
2
VO
о
<м
о
ч
я
ч
VO
2
о
VO
2
<м
О
о
о
<М
с;
t=2
<м
см
<м
<м
<М
со
Ч1
,
<М
ю
_
СО
_
ч
ч
см
ч
со
£Г
СЗ
*
<;<WDQ<QGWQWU
и Q Q О
3	>	ь	2	В
§0сл®Г>0?^Осл
O'—lO^J0'5lrpr(_j
<<UUQQQuj~~^
IS
1-5 -J
Q _
<
О Ш
J £
a
§

Имя Группа Условия Формат Виды аргументов Смысловое значение
а
£
§
Си
fc*
Я
К
Я
Я
Я
я
Я
•е-
Я
я
о
S
о
о.
Я
н
я
>*s
II
S
я о
о
S я
5 я
S О)
a S
о я О
03 Я
Я Я
03 о
fcC о.
О) Я
Си С
03 о
а;
я та
S н «
s
Sg.s
<»=:
аз
я
я	та
m	О
S та л о
к м S й
5 s 2 a
о. о S О
н о ^ а
я ° с
s « Я
со О
g Я с
® О
а» О
3 я 4
а s to
^ и сг
- О Я
S
о
Я
к
S «
§ °
К 03
Я н
о ж
и аз
S w S
я Н (D
£2*4
К о Я)
та s
о g а>
О 4	®
к та S
_ оз
н я 5
та g. та
^.9 *
03
Н 03
э'§
о О
та
svo
<D
аз я
о я
аз ,
^я
>я и
о 4
я
й та
о. н
я о
о
к та
г—< со
та vq ^
ЧО^ГСштм
£ s
аз 4
3 ^
•©*
Я о
Си о
<<
о к »я та g
си та та s
та я та г
я	аз	ч
S	cr	о	<■=«	«-t
я?	я	я	*0-	о
та	я	к	'g
к
к
я
я
я
я
О)
03
я
я
я
я
я
я
со
я
я
я
я
я
я
я
о
оз
о
я
о. я
я
о
я
н
V0
н
о
я
о
>4
я
>>
fc(
я
о
я
ч
я
ч
я
3
я
я
я
я
я
я
Q-
я та
я
CL
OQ	$CQCQ CQ	CQ CQ
PQ <	<	CQ	<CQ^
?ffl|	1§§	S	<	§<	§
— 3	3 Н 3	3	м	В н	»
I^l	|§s	1	I	ill
Э	Ы О	О q о	О	/*■*«/»“s, о	о	о	та
О О я	та s a ^ к	о	я с	л ^
к	§я	я Вйс^	сч<м	£	^
s	О Ul	Я Я	.	^ Я	# ^	„	Я	Я	Я	та	^
О. с^г ^ - - =я - =к >я »я g* *&>«	04	’Я
Я	я ^	Ян О О о О о о О та	О	о	►	О
О В4 та я я я 'g я 'g 'gvg°	t^'v§
я vo	\о vo vo	2 \q	2	2 2 ..	\о	'О 2 w 2
<n	оО	OOO^O^o^^Z	О ©О с?	^
04	00—*
Q U< <<<№< WUfflPQ< W	WQ
0 >-СУНы он <0ЩЬЦвЗо wS
о oo а си о & с^о^щ н ел о ш :кЫэ< ц-н
2»	йггооао^в^с^слол -слслслн нн
UNDUMP В 9 Любой Установка элементов стека на ре¬
гистры

Список литературы
117
Таблица 6. Коды прерываний
0 — не определен
1 — вышел за границы допустимого диапазона представления
2 — недопустимый
3 — получено переполнение при модификации
4 — освобожден программой
5 — защищен
6 — должен рассматриваться как адрес буферной памяти
7 — адрес внешнего массива
8 — требует программной (системной) интерпретации
9 — адрес процесса
СПИСОК ЛИТЕРАТУРЫ
[1] Burks A. W., Go Id stine Н. Н., von Neumann J., Preliminary
discussion of the logical design of an electronic computing instrument,
1946. Cm. von Neumann J., Collected Works, vol. 5, 34—79, Pergamon,
1961.
[2] G о 1 d s t i n e H. H., von Neumann J., On the principles of large
scale computing machines, 1946. Cm. von Neumann J., Collected
Works, vol. 5, 1—33, Pergamon, 1961.
[3] The Descriptor, Burroughs Corporation, 1961.
[4] 11 i f f e J. K., J о d e i t Jane G., A dynamic storage allocation scheme,
Computer /., 5, 1962, p. 200.
[5] FORTRAN vs Basic FORTRAN, Commun. Assoc. Comput. Mach., vol. 7,
591—624, 1964. Cm. Section 7.2.1.1.1.
[6] F о s t e г J. М., List processing, Macdonald, 1967.
[7] 11 i f f e J. K-, The use of the Genie system in numeral calculation,
Annual Review in Automatic Programming, vol. 2, 1—28, Pergamon,
1961.
[8] W i r t h N., Weber H., EULER: A Generalization of ALGOL and its
Formal Definition: Part II, Commun. Assoc. Comput. Mach., vol. 9, 89—99,
1966.
[9] R о о s D., ICES System Design, MIT Press, 1966.
[10] SPAN, NCR Elliott 4100 Programming Information, Part 3, Section 3,
1966.
[11] Gimble E. P., JOSS: Problem solving for engineers, RAND memoran¬
dum RM — 5322 —PR, 1967.
[12] Dennis J. B., Segmenting and the design of multiprogrammed compu¬
ter systems, 1965 IEEE International Convention Record, Part 3,
214—225.
[13] Kilburn Т., One-level storage system, IRE Transactions on Electronic
Computers, vol. EC-11, 2, April 1962.
[14] Daley R. C., Neumann P. G., A general purpose file system for se¬
condary storage, Proceedings of the Fall Joint Computer Conference, 27,
Spartan, 1965.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Автовыборка (правило А/В) 59
Автозапись (правило А/3) 59
Административные команды (группа Е)
74, 86
Адреса хранения в памяти 15, 56
Адрес последовательности 53, 55
— «простой» 51
Алгол 42
Ассемблер 54, 85
База системы 39
Вид 28, 52, 53
Вида обозначения 56
Вычисление выражений 78, 108, 109
— кодослов 55, 56
Граничные пары 17, 18, 28
Данные, образованные несколькими эле¬
ментами 106
Дерево 29, 31, 32, 38, 39, 48, 49, 51
Диагностическая информация 20, 77
Память активная 96
— виртуальная 102
— линейная 12, 13
— массивов 70, 89
— неактивная 96
— помеченная 44, 45, 49
— программная 71, 72, 86
— свободная 103
— страничная 50, 101, 102
Параллельное управление 21, 22
Параметры 44, 83
Переполнение по модификации, обнару¬
жение 89
Перестройка хранимой в памяти инфор¬
мации 54
Погружение структуры 17, 34, 104
Подпроцесс 75
Последовательность команд прямая 77
— непрямая 77
Прерывания 24, 25, 30, 53, 58, 59
Признак «только чтение» 55, 73
Поисваивание значений регистрам 57, 58
72, 73. 103, 109
Программы база 39, 51
— загрузка 37
— объединение 37, 47
— структура 17
Записи 70
Имя глобальное 79, 80
— локальное 79, 80
— составное 33, 39, 80, 81
Индикаторы условий 57, 62, 83
Кобол 13, 42, 44
Кодослова, определяющие списочную
структуру 100
Кодослово 29
— абсолютное 56
— главное 29, 31
— неопределенное 30
— относительное 41, 56
Константы 81
Косвенная адресация 35, 50
Размер страницы ЮЗ. 104
— элемента информации 54
Регистр базы процесса (XD) 58
— текущей команды (ХС) 57, 60
Режимы 62
Связей таблица 39, 40, 47, 51, 86
Связка 60, 61
Связки помеченные 60, 61
Сегментации схемы 48, 49, 50
Сегменты программы 32, 37, 77, 78, 85
Символьный вводной язык 10, 21
Системное программирование 17
Системный прогресс 74, 75
Смешанный тип 52
Составное имя 33, 39
Списков обработка 17, 37
Стек 42, 58, 64
Супервайзер 75
Метки 81
Набор 31, 55, 71, 72
Недействительный элемент 53
Некорректный результат 61
Типы 22, 23, 29, 53, 54
— «только чтение» 55
Трассировки режим 62
Уровень в дереве 29, 31
Обмен с периферийными устройствами 22
Оперативное взаимодействие 18
Операции арифметические и логические
(группа А) 63
— над адресами (группа D) 66
  базой (группа В) 64
 наборами 38
— передачи управления (группа С) 64, 65
Операция 37, 43, 67, 83, 84
Описания 107
Памяти восстановление 48, 96
— защита 55
— отображение 34
— принадлежность 22, 72
— разделение 45, 76
Фон Неймана машина 11, 12, 15, 16, 31,36,
51, 77
Форматы команд 68, 69
Фортран 13, 17, 42, 44
Частота изпользовання 96, 98
Числовой элемент 54
Элементарные операнды 22, 23
Burroughs В5000 41, 44
CIS 78
ICT Atlas 49, 103
Rice, вычислительная машина 37, 44

ОГЛАВЛЕНИЕ
Предисловие редактора перевода
Из предисловия автора ....
1. Общие принципы
1.1. Разработка модели
1.2. Основные цели .
1.3. Основные выводы
2. Некоторые родственные системы
2.1. Функции отображения памяти ......
2.2. Вычислительная машина университета Риса .	.
2.3. Вычислительная машина Burroughs В5000
2.4. Схемы сегментирования	.	...
3. Базовая машина .	.	.....
3.1. Представление вида и типа на внутреннем языке машины
3.2. Кодослова .....
3.3. Распределение регистров .	.	.
3.4. Правила обращения к памяти
3.5. Правила последовательности выполнения команд
3.6. Выбор системы машинных команд ...
3.7. Форматы команд . .	.......
4. Базовый язык
4.1. Виды памяти .	•	.
4.2. Процессы
4.3. Прагматика ......
4.4. Программные сегменты	^	■
4.5. Административные команды (группа Е)
4.6. Пример . .	...
5. Технические приемы .	.
5.1. Общие вопросы управления памятью
5.2. Специальные представления .
5.3. Погружение
5.4. Расширения .	     .	.
Приложение .	.	    •
Таблицы .	.	•	    .	.
Список литературы
Предметный указатель
5
8
9
11
15
25
29
34
37
41
48
51
52
55
57
59
60
62
68
70
70
74
76
78
86
91
95
96
100
104
106
110
112
117
118

УВАЖАЕМЫЙ ЧИТАТЕЛЬ!
Ваши замечания о содержании книги,
ее оформлении, качестве перевода и другие
просим присылать по адресу: 129820, Моск¬
ва, И-110, ГСП, 1-й Рижский пер., д. 2, из¬
дательство «Мир».
Дж. Айлиф
ПРИНЦИПЫ ПОСТРОЕНИЯ
БАЗОВОЙ МАШИНЫ
Редактор JI. Н. Бабынина
Художник А. Д. Смеляков
Художественный редактор В. И. Шаповалов
Технический редактор Я. И. Борисова
Корректор И. И. Алексеева
Сдано в набор 20/МЫ972г.Подписано к печати 29/XII 1972 г. Бумага
№ 2 60X907ie * 3,75 бум. л. 7,5 печ. л. Уч.-изд. л, 0,89
Изд. № 1/6638. Цена 49 к. Зак. 233
ИЗДАТЕЛЬСТВО «МИР»
Москва, 1-й Рижский пер., 2
Ордена Трудового Красного Знамени Ленинградская типогра¬
фия № 2 имени Евгении Соколовой «Союзполиграфпрома» при
Государственном комитете Совета Министров СССР по делам
издательств, полиграфии и книжной торговли
г. Ленинград, Л-52, Измайловский проспект, 29

49 коп-