RASPM с присоединенным вспомогательным хранилищем

Дальнейшее приближение модели к реальным компьютерам и операционным системам основывается на идее присоединенных внешних хранилищ (данных и программ).

Описанные в предыдущем пункте модели ограничены тем, что в чистом виде пригодны только для анализа отдельного алгоритма или программы. Для анализа взаимодействия алгоритмов потребовались бы значительные усилия. Чтобы упростить анализ таких ситуаций имеет смысл ввести в модель вычислительной машины специальную область или ленту, на которой будут храниться данные других программ. Назовем эту область присоединенным вспомогательным хранилищем (Attached Background Storage, ABS). Кроме этого имеет смысл потребовать, чтобы любая выполняющаяся программа имела полный доступ (чтение и запись) к этому хранилищу.

Определение 2.6. Вычислительная машина G с хранением программ в памяти с произвольной выборкой и с присоединенным вспомогательным хранилищем (RASPM с ABS) определяется шестью элементами:

где V - алфавит, состоящий из входных символов, выходных символов, а также символов, которые могут быть записаны на присоединенном вспомогательном устройстве и в ячейках памяти (регистрах), U - непустое конечное подмножество кодов инструкций, U V, T- непустое множество возможных действий процессора, f - однозначная функция f: U T, ставящая в соответствие различным кодам инструкций различные действия процессора, действие процессора f(x), соответствующее коду инструкции x U будет называться командой, q - стартовое значение счетчика операций, M - стартовое наполнение памяти

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

Обозначим значение i-й ячейки памяти как c(i), где i - целое число. Допустимые коды операндов в таком случае представлены в таблице.

Полный код команды в этом случае будет складываться (в буквальном смысле) из кода инструкции и кода операнда. Например, команда ADD [i] будет иметь код 32, а команда GET [[i]] - код C3.

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

Также нужно понимать, что не любой операнд подходит к каждой инструкции. Например, инструкция READ может иметь только операнды типов [i] и [[i]], поскольку записывает значение из ленты в память.

При включении RASPM с ABS счетчик инструкций принимает начальное значение q и процессор немедленно выполняет команду, расположенную по адресу, указанному в q. Дальнейшее выполнение программы определяется командами, записанными в памяти и таким образом полностью определяется начальным содержанием памяти. Завершение работы машины происходит в следующих случаях:

• когда машина выключается пользователем
• когда счетчик указывает на ячейку памяти, содержимое которой не является кодом команды (x V, но x U)
• когда производится попытка выполнить деление на ноль

Таким образом, в отличие от RAM специальная команда для завершения работы машины не используется.

При каждом включении машины содержимое памяти приводится к исходному значению M, а при каждом выключении обнуляется. Содержимое вспомогательного хранилища, напротив, сохраняется от выключения к включению. Можно также допустить, что вспомогательное хранилище разрешается отсоединять от одной машины и присоединять к другой. Естественным расширением RASPM с ABS выглядит возможность одновременного подключения нескольких вспомогательных хранилищ к одной машине. Следовательно можно определить RASPM с несколькими ABS следующим образом.

Определение 2.7. Вычислительная машина с хранением программ в памяти с произвольной выборкой и с несколькими присоединенными вспомогательными хранилищами (Random Access Stored Program Machine with Several Attached Background Storages, RASPM с SABS) определяется так же как и RASPM с ABS, но с некоторыми допущениями:

• к RASPM с SABS может быть одновременно присоединено несколько вспомогательных хранилищ
• все символы на всех вспомогательных хранилищах входят в алфавит V
• множество возможных действий процессора включает дополнительное действия выбора активного вспомогательного хранилища (см. нижеследующую таблицу)
• после выполнения соответствующей команды все инструкции, так или иначе связанные с использованием вспомогательного хранилища, будут относиться к активному хранилищу
• если инструкция, связанная с использованием вспомогательного хранилища, выполняется до команды выбора активного хранилища, она будет использовать первое хранилище
• машина останавливается в тех же случаях, что и RASPM с ABS, а также в случае выполнения команды смены хранилища, если операнд указывает на несуществующее хранилище

Теорема 2.5. RASPM с SABS эквивалентна RASPM с ABS, в том смысле, что каждая из машин может быть проэмулирована другой

Доказательство. Достаточно показать, что RASPM с SABS может быть проэмулирована RASPM с ABS, поскольку симметричное утверждение доказывается тривиально.

Для эмуляции N вспомогательных хранилищ одним хранилищем воспользуемся следующим принципом: пронумеруем ленты вспомогательных хранилищ от 0 до N-1. Перенесем j-й символ i-й ленты в (Nj+i)-ю позицию новой ленты. Кроме этого изменим структуру памяти эмулирующей машины следующим образом:

1. Нулевая ячейка по-прежнему аккумулятор
2. 1-ю ячейку оставим для будущих целей
3. 2-я ячейка содержит адрес ячейки с номером от 3 до N+2, которая хранит номер позиции головки чтения/записи на ленте вспомогательного хранилища
4. i-я ячейка в диапазоне от 3 до N+2 содержит позицию головки чтения/записи (i-3)-й виртуальной ленты вспомогательного хранилища
5. i-я ячейка при i>N+2 содержит то же значение, что и (i-N-2)-я ячейка эмулируемой машины, если при трансляции программа эмулируемой машины не подверглась изменениям (см. ниже), в противном случае сдвиг происходит на большее количество позиций

Команды эмулируемой машины переносятся в память эмулирующей машины без изменений за исключением следующих случаев:

• если исходная программа должна изменить текущее активное хранилище, вместо команды SETDRIVE a выполняется последовательность команд, меняющая номер виртуальной ленты во 2-м регистре:

• если оригинальная программа должна произвести чтение или запись на вспомогательном хранилище (например, PUT a), эмулирующей программе потребуется вычислить соответствующий номер ячейки на реальной ленте и произвести запись в нее путем выполнения следующей последовательности команд:

• если оригинальная программа перемещает головку чтения/записи при помощи команды SEEK a, эмулирующая программа выполняет такую последовательность команд:

• в процессе копирования программы из памяти эмулируемой машины в память эмулирующей, при замене описанных команд на последовательности команд, остальные команды сдвигаются на необходимое число позиций и все ссылки на ячейки памяти пересчитываются соответственно сдвигу

Построенная таким образом симулирующая машина требует не более 7 операций на каждую операцию исходной программы, а значит сложность эмулирующей программы будет не больше 7T(n), где T(n) - сложность эмулируемой программы. Теорема доказана.

Следовательно увеличение количества вспомогательных хранилищ не увеличивает вычислительной способности машины RASPM с ABS. Осознавая этот факт, несложно понять, что вычислительная способность RASPM с ABS не превышает вычислительной способности RASPM, что и утверждается соответствующей теоремой.

Теорема 2.6. Любая машина RASPM с ABS может быть проэмулирована машиной RASPM, и затраты на операции будут отличаться не более чем на постоянный множитель

Доказательство. По аналогии с доказательством предыдущей теоремы можно скомбинировать содержимое памяти и вспомогательного хранилища эмулируемой машины в памяти эмулирующей машины и получить RASPM - машину без вспомогательного хранилища. Основная разница при комбинировании будет заключаться в том, что смешиваться будут не отдельные ячейки, а их блоки, поскольку отрывать значение операнда от кода инструкции нельзя. Также следует учитывать, что для сохранения связности программы потребуется добавить после каждой команды оригинальной программы команду JUMP, чтобы пропустить ячейки памяти относящиеся к виртуальной вспомогательной ленте. В остальном принципы комбинирования остаются теми же, за тем исключением, что нет необходимости использовать несколько регистров для нескольких лент и отдельный регистр для номера ленты - достаточно будет ограничиться только регистром для хранения номера позиции на ленте. На этом неформальное доказательство можно считать законченным. Приводить формальное доказательство смысла нет из-за его относительной громоздкости.

Прямым следствием из теоремы будет следующая теорема:

Теорема 2.7. Вычислительная способность Машины Тьюринга и RASPM с ABS эквивалентны, а их затраты на вычисления находятся в полиномиальной зависимости

Доказательство. Этот результат получается из сопоставления результатов теорем 2.1, 2.2, 2.3 и 2.6.