7.4. Апелляция к ЭВМ

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

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

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

Рис. 7.9. Схема архитектуры ВМ: (I, II) - пульт управления, (II, III, IV, V, VII, III) - программный процессор, (VI, VII) - процессор ввода, (VIII, IX) - процессор выдачи

Схема архитектуры ВМ показана на рис. 7.9. На нем совокупность блоков (VI, VII и b₁) изображает процессор ввода, состоящий из устройства ввода, буфера Б1 и разряда b₁ регистра прерывания R; совокупность блоков (VIII, IX и b₃) - процессор выдачи, состоящий из устройства выдачи, буфера Б3 и разряда b₃ регистра прерывания/?; совокупность блоков (VII, If, III, VIII, IV, V) - программный процессор, состоящий из буферов Б1, Б2, БЗ, устройства управления, оперативной памяти (ОП) и регистра прерываний R, с которым устройство управления имеет две связи (с разрядом b₂ - одностороннюю, и с R в целом - двухстороннюю); совокупность блоков (I, II) - пульт управления, состоящий из собственно пульта и буфера Б2. Направление стрелок на линиях, соединяющих блоки, указывает возможные направления движения информации.

Рис. 7.10. Схема системы запоминающих элементов процессора ввода

Опишу работу каждого процессора в отдельности. Собственное ЗУ процессора ввода на рис. 7.9 не показано. Оно состоит из ячейки s, называемой счетчиком перфокарт, ячейки р, в которую считывается содержимое перфокарты при ее продвижении сквозь читающее приспособление, одноразрядной ячейки я, в которую заносится код "1", если перфокарта действительно прошла через читающее приспособление. Перфокарта может через него и не пройти, если в колоде меньше перфокарт, чем нужно, или перфокарта замялась и "застряла".

Кроме того в состав устройства ввода входит сигнальная ячейка τ, запись кода "1" в которую является пуском устройства, протягивающего перфокарту через читающее приспособление. После одного движения (в прямую и обратную сторону) это устройство автоматически останавливается, записывая при этом код "О" в ячейку τ. Схема системы запоминающих элементов процессора ввода изображена на рис. 7.10. Буфер Б1, входящий в этот процессор, содержит две сигнальные ячейки: u - для записи в нее программным процессором разрешения пользоваться буфером и U - для указания в ней числа перфокарт, с которых должна быть прочитана информация. Кроме того, буфер Б1 содержит n ячеек х₁, х₂, ..., х_n, в которые должны быть помещены (в виде последовательности, начиная с x₁) вводимые коды.

Процессор ввода должен быть реализован как физическая модель алгоритма ввода.

Запись алгоритма ввода

Алгоритм ввода ждет условия = 1; до начала его работы должно быть = 0. После этого он "очищает" счетчик и, если в сигнальной ячейке U записано число кодов, подлежащих вводу с перфокарт, больше нуля, увеличивает на единицу, засылает "0" в ячейку π и включает протяжку перфокарт, делая = 1. Затем ожидает появления в ячейке τ нуля, т. е. окончания протяжки. Если перфокарта прошла (при этом = 1), то производится перенос считанного с нее кода p в ячейку буфера x_s, т. е. в ячейку, номер которой содержится в счетчике; затем, если еще не все коды введены (их число указано в ячейке U), процесс повторяется, начиная с приказа 3. Если же окажется, что перфокарта не прошла через читающее приспособление (т. е. если = 0), то вырабатывается и посылается в регистр прерывания код "1". После этого процесс продолжается, начиная с приказа 5. Устройство ввода ожидает возможности ввести перфокарту.

Алгоритм выдачи очень похож на алгоритм ввода. Процессор выдачи, кроме выходного перфоратора, буфера Б3 и сигнальной ячейки b₃, содержит еще счетчик перфокарт t, ячейку q, в которую нужно записать код для его переноса на перфокарту, подлежащий выдаче, и две одноразрядные ячейки; ε - включатель перфоратора и σ - ячейку для записи в нее признака (в виде кода "1"), что перфокарта прошла через выходной перфоратор. Перфокарта может и не пройти через выходной перфоратор, если заготовлено слишком мало перфокарт или если очередная перфокарта сомнется.

Буфер БЗ в своем составе содержит две сигнальные ячейки: v - для записи программным процессором разрешения обращаться к буферу (в виде кода "1") и V - для указания числа кодов, помещенных программным процессором в буфер для выдачи. Кроме того, буфер содержит n ячеек y₁, y₂, ..., y_n, в котором в виде последовательности (начиная с y₁) записаны коды, подлежащие выдаче. Схема системы запоминающих элементов процессора выдачи приведена на рис. 7.11.

Рис. 7.11. Схема системы запоминающих элементов процессора выдачи

Процессор выдачи должен быть реализован в виде физической модели алгоритма выдачи.

Запись алгоритма выдачи

Смысл алгоритма выдачи читатель поймет, если внимательно просмотрит его запись.

Буфер Б2 принадлежит одновременно пульту управления и программному процессору. Для простоты считаем, что он состоит всего из двух одноразрядных ячеек: w - для записи в нее с пульта (нажимая кнопку "пуск") кода "1", разрешающего программному процессору работать, и λ - для записи в нее программным процессором информации о причине произошедшего прерывания. При нажиме на пульте управления кнопки "пуск" на панели сигнализации загорается неоновая лампочка, которая горит до тех пор, пока в ячейку w не будет записан код "О", что может быть сделано либо программным процессором, либо нажимом на пульте управления кнопки "стоп". Одновременно с нажимом кнопки "пуск" в ячейку λ записывается код "000". Ячейка λ имеет три разряда (по числу разрядов в регистре прерывания), с каждым из которых спарена неоновая лампочка на панели сигнализации, загорающаяся при записи в соответствующий ей разряд кода "1".

Рис. 7.12. Схема системы запоминающих элементов программного процессора

Схема системы запоминающих устройств программного процессора показана на рис. 7.12. Кроме буферов Б1, Б2 и Б3, а также регистра прерываний R, в программный процессор входят блок ячеек z₁, z₂, ..., z_N, называемый оперативной памятью (ОП), и ряд ячеек: r - регистр команд, l - счетчик команд, ω - логическая одноразрядная ячейка, m - регистр маски прерываний; ячейки-дублеры: r' - регистра команд; l' - счетчика команд, ω' - логической ячейки, R' - регистра прерываний. Кроме того имеется еще ячейка l₀, в которой постоянно хранится (реализовано аппаратно) целое положительное число v - адрес первой команды программы обработки прерываний. Это число является также границей, отделяющей так называемую зону рабочих программ (ячейки z₁ - z_v-1) от зоны служебных программ (ячейки z_v - z_N). В реальных ЭВМ ОП делится обычно на большее число зон и тогда для их границ требуется больше ячеек. Зона служебных программ должна быть защищена от воздействий рабочих программ, тогда как служебные программы имеют возможность воздействовать на все ячейки.

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

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

Для определенности я остановился на трехадресной структуре команды, хотя в современных ЭВМ структура команд не фиксирована. В принципе, фиксированной является структура только кода операции, структура же остальной части команды зависит от значения кода операции. Адреса - это номера ячеек ОП. Будем считать, что код операции в команде имеет вполне определенное число разрядов и команда имеет структуру (в соответствии с последней метаформулой) θijk, где θ - код операции, i, j, k - адреса. Ячейку r считаем состоящей из четырех ячеек, как это и показано на рис. 7.12. Зададимся системой команд (ее выбирают с учетом характера задач, которые предстоит программировать). Соответствие между кодами операций и самими операциями представим в виде табл. 7.1.

Таблица 7.1. Код операций

Фиктивные операции для программистов запрещены. Их используют только сама ВМ . Команда с таким кодом операции, будучи включенной в программу, будет воспринята машиной как нарушение защиты памяти (см. с. 132).

Последняя операция, приведенная в табл. 7.1, не имеет кода, так как выполняется вместе с другими операциями, как будет видно ниже. Ее принято обозначать символом sign. Если а произвольное число, то

Это удобно, если вспомнить, что логическое значение "истина" кодируют цифрой 1, а логическое значение "ложь" - цифрой 0.

Перейдем к описанию работы программного процессора.

Запись алгоритма выполнения программ

Группа приказов, которую мы назвали "Подготовка", описывает действия программного процессора, предшествующие его основной работе. Очевидно, прежде всего нужно ввести в ОП программы (как служебные так и рабочие). Для этого должны быть составлены и перенесены на перфокарты подлежащие вводу программы. Но как их ввести в ВМ? Для этого нужно составить еще программу ввода. О ней будет сказано ниже. Пока что допустим, что все программы заготовлены. Их нужно сложить в виде колоды, в которой на первом месте лежат карты с программой ввода, а за ними карты с программами, подлежащими вводу. Далее оператор ВМ (человек) должен действовать так:

1. Нажать на пульте управления сначала кнопку "стоп-1" (связанную с сигнальной ячейкой w'), а затем - кнопку "стоп-2" (связанную с сигнальной ячейкой w). При этом сигнальные лампочки, соответствующие этим ячейкам, должны не гореть (или погаснуть).
2. На тумблерном регистре δ набрать число перфокарт, содержащих программу ввода, а на тумблерном регистре Р - адрес ячейки ОП, в которую должна попасть первая команда программы ввода.
3. Нажать кнопку "пуск-1". В результате этого начнет выполняться "Подготовка". Приказ 2 передаст управление приказу 3 (так как кнопка "пуск-2" еще не нажата); приказы 3 и 4 запретят несанкционированную работу процессоров ввода и выдачи; приказы 5, 6, 7, 8 и 9 сформируют непосредственно в регистре команд г команду ввода (программы ввода) ; приказ 10 вызовет ожидание нажима кнопки "пуск-2".
4. Вложить в читающее устройство колоду перфокарт.
5. Нажать кнопку "пуск-2". После этого приказ 10 передаст управление приказу 12 и произойдет ввод программы ввода.

Приказ 11 вызывает в регистр команд команду, которая в ОП записана по адресу, стоящему в счетчике команд /. При начальном пуске этот приказ пропускается, так как в регистре команд стоит команда, засланная с пульта управления, и начать работу надо с ее выполнения.

Приказы с необычными метками 012 и 0012 предназначены для того, чтобы не допустить выполнение команд с запрещенными кодами операции (12 или 13).

В нижестоящем приказе 13 символом "*" обозначена операция поразрядного умножения. Напомню, что разряды регистра R и его маски m могут быть либо нулями, либо единицами.

Эта группа приказов предусматривает перенос содержимого из регистра команд, счетчика команд, логической ячейки и регистра прерываний в дублирующие ячейки (приказы 14 - 17). Но это производится, только если в регистре прерываний содержатся незамаскированные сигналы прерывания (т. е. такие, которым в регистре маски m соответствует код "1"; сигнал прерывания считается замаскированным, если в отвечающем ему разряде регистра маски стоит код "0"). Затем в счетчик команд засылается содержимое ячейки l₀ (а оно равно адресу первой команды программы обработки прерываний). Засылается в регистр маски код 000 (чтобы новые сигналы прерываний не мешали работе служебных программ) и в регистр прерываний - код 000 (для того чтобы он был готов к приему новых сигналов прерываний). После этого управление передается блоку "Выбор и счет команд". Начинает работать программа обработки прерываний. Так остроумно в современных ЭВМ реализована функция пассивного внимания.

Если сигналов прерывания нет, то приказ 13 сразу передает управление блоку защиты памяти. О такой функции алгоритма выполнения программ выше уже было сказано. В ВМ она реализована так:

Защита памяти ВМ считается нарушенной, если команда, поступившая в регистр команд из рабочей зоны, имеет хотя бы один адрес, принадлежащий служебной зоне (включая и команды ввода и выдачи, в которых один из адресов равен числу кодов). Если защита нарушена, производится выдача сигнала прерывания (приказ 25). Если защита не нарушена, производится расшифровка кода операции, стоящего в соответствующей части

Как видно из приказа 38, любой код операции, отличный от указанных в табл. 7.1, выполняется как код 10. Дальше, алгоритм выполнения программ содержит операции:

При вводе с перфокарт алгоритм выполнения программ должен был бы ждать, пока процессор ввода, получив (при выполнении приказа 801) разрешение работать, запишет в ячейку и код "0", но тогда при возникновении сигнала прерывания программный процессор его не уловил бы и ВМ остановилась бы до тех пор, пока оператор (человек) не заметил бы неблагополучия и его не устранил бы. Чтобы этого не произошло, приказ 802 засылает в регистр команд код фиктивной операции 12 и передает управление блоку "Прерывание", который, если сигнала прерывания нет, передает управление блоку защиты, а затем блоку расшифровки кода операции. Последний передает управление приказу 803, а этот приказ, если снова передает управление блоку "Прерывание", и так до тех пор, пока не станет После этого приказы 804 - 808 забирают введенную информацию из буфера Б1.

Если в начале выполнения операции "выдача на перфокарты" окажется, что выходной процессор еще занят выдачей, которая была начата раньше, т. е. если = 1, то нужно выполнять операцию ожидания условия = 0. Однако такое ожидание сопровождалось бы невозможностью уловить прерывание от выходного процессора. Поэтому предусматривается искусственный прием: запись (приказ 901) в регистр команд кода фиктивной операции 13 и передача управления блоку "Прерывание". Подобный прием мы уже применяли при составлении части алгоритма, выполняющей операцию с кодом 08 (ввод с перфокарт).

Замечу, что одновременно с работой процессора выдачи может продолжаться выполнение других команд программного процессора. При этом во время каждого рабочего цикла программного процессора производится просмотр регистра прерываний. Однако, если почему-либо процесс изменится, то прерывания от процессора выдачи не будут восприниматься до тех пор, пока естественный процесс выполнения команд не восстановится. Нарушение естественного порядка выполнения может произойти из-за нажатия на пульте управления кнопки "стоп-1" или прерывания, не связанного с процессором выдачи.

Приведу описание остальных операций ВМ.

В заключение данного параграфа приведу примеры конкретных команд на языке ВМ.

Команда сложения может иметь вид 01 0001 0002 0003.

Команда ввода 08 0000 0100 0020 гласит: "ввести 100 кодов в ячейки 20,21,..., 119".

Команда выдачи 09 0020 0100 0000 гласит: "выдать 100 кодов из ячеек 20, 21,..., 119".

Команда возврата имеет вид 11 0000 0000 0000.

Из приведенного в этом параграфе примера ЭВМ видна связь между физическими устройствами дискретного преобразования информации и математическим аппаратом коллективов алгоритмов.