Этюды для программистов

Распределение памяти для процессора также не простая задача. Потребность в памяти для любой из структур — нейтральной цепочки, активной цепочки, стека аргументов и памяти бланков — может превзойти любую заранее установленную границу. Если для этих структур выделяются фиксированные области памяти, то любая из них может переполниться, в то время как в остальных свободного пространства будет хоть отбавляй. Имеется стандартный путь решения этой проблемы. Рассмотрим сначала нейтральную и активную цепочки. Поскольку нейтральная цепочка естественно смотрится слева от активной, выделим им одну область памяти на двоих; в этой области нейтральная цепочка будет расти от левого края вправо, а активная цепочка, наоборот, от правого края влево. При таком способе действий переполнение памяти не наступит, пока активная и нейтральная цепочки не используют в сумме всю выделенную им память. Стек аргументов можно таким же образом объединить с памятью бланков; один из двух промежутков между объединенными парами можно использовать для временного хранения цепочек, переписываемых с одного места на другое.

Возможны дальнейшие усовершенствования. Выделим память для всех динамических структур в одной большой области, в которой разместим слева направо нейтральную цепочку, растущую вправо, свободный промежуток, активную цепочку, растущую влево, без всякого промежутка стек аргументов, свободный промежуток и память бланков, растущую влево. Если теперь активная и нейтральная цепочки израсходуют все пространство, в то время как между стеком аргументов и памятью бланков еще что-то останется, то передвинем активную цепочку и стек аргументов как единое целое вправо на некоторое расстояние, передавая тем самым часть пространства из правого свободного промежутка в левый. Разумеется, тот же прием работает и в другую сторону, так что процессор не останется без памяти, пока ему будет откуда ее взять.

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

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

Инструментовка. На примере этой задачи можно еще раз изучить влияние языка на программирование. Если вы изберете язык высокого уровня типа Паскаля с его многочисленными мерами безопасности, то обнаружите, что большую часть процессора до абсурда легко закодировать, но за эту легкость, вероятно, придется заплатить потерей эффективности и трудностями при реализации распределения памяти. Если, напротив, остановитесь на языке ассемблера, то вполне может случиться, что ваша программа будет эффективной как по памяти, так и по времени, но она будет очень длинной и трудной для отладки, причем вам придется написать многие из тех подпрограмм, которые предоставляются другими языками программирования. Использование языков промежуточного уровня: XPL, BLISS или Фортрана — быть может, объединит преимущества (и, возможно, недостатки) двух крайних подходов. Не исключено также, что некоторые части программы придется написать на одном языке, а остальную программу — на другом. Как бы то ни было, в документации необходимо обосновать выбор языка и привести соображения, которые возникнут у вас по окончании работы.

Длительность исполнения. Для решения этой задачи в одиночку потребуется 7 недель, вдвоем — 4 недели, втроем — 3 недели.