Abstract
В этой статье описывается реализация алгоритма управления виртуальной памятью, которую я осуществил на PDP-11 в середине 1980-х гг.
Проект
Это было на моей работе в ВИРе. У нас была Электроника 100-25, советский клон PDP-11, миникомпьютера DEC (Digital Equipment). На самом деле его следует писать как «мини»-компьютер, потому что он занимал целую большую комнату. DEC разработала прекрасную систему управления базами данных под названием Datatrieve-11 , которая была мощной и надежной, но, к сожалению, имела два недостатка: в то время она не поддерживала создание хороших отчетов (а нам нужно было много хороших отчетов) и, мягко говоря, она была не быстрой. Она была настолько не быстрой, что нам ее почти не удалось использовать для практических целей.
Задача
Я должен был написать что-то более эффективное чем Datatrieve-11. Я так и сделал. Я написал полную среду программирования для управления базами данных, пользовательского интерфейса и создания отчетов. Она генерировала хорошие отчеты, и работала быстро. Проект занял около года программирования на Macro-11, ассемблере DEC. Я назвал систему DBCalc. Жаль, что это было в СССР еще в коммунистические времена. Если бы я написал эту систему в Америке в 1984 году, я бы немного заработал и жил бы теперь на Гаваях.
Проблема
DBCalc поддерживал языка программирования моего изобретения: полностью на русском, ключевые слова и все остальное. Он компилировал исходный код во внутренний байт-код , который затем интерпретировался. Формат байт-кода был частично основан на формате, используемом компилятором / интерпретатором Фортрана IV (да, Фортран IV на PDP-11 был интерпретируемым языком).
Проблемы начались, когда приложения, написанные на DBCalc, начали разрастаться за пределы памяти. На Элекртонике было всего 64 КБ на всё про всё: интерпретатор, среду выполнения, скомпилированный код приложения, стек вызовов и данные. Все это вместе просто не умещалось в 64 КБ.
Решение
Решением была естественно виртуальная память. Среда исполнения Фортрана IV включала поддержку виртуальной памяти, но сама среда исполнения Фортрана занимала огромное количество памяти, которой, как я объяснил, у меня не было. Так-что я реализовал свою собственную виртуальную память.
- Мне нужно было иметь возможность загружать любую функцию в любом месте адресного пространства. Формат байт-кода уже был полностью перемещаем, так что эту часть менять не пришлось.
- Я поменял компилятор чтобы он преобразовал исходный код в файл библиотеки, который начинался с оглавления, каждая запись которого включала абсолютный адрес и длину соответствующей функции в самом файле библиотеки.
- Я изменил команду байт-кода CALL. Перед изменением, в качестве аргумента использовался адрес функции. После изменения, вместо адреса стал использовался индекс функции в оглавлении.
- Когда приложение запускалось, оно сначала загружало оглавление в память и выделяло массив адресов соответствующей длины. Этот массив Address_Array содержал адреса функций в памяти. Он был инициализирован нулями. Нуль означал, что в настоящее время функции нет в памяти.
- Байт-код каждой функции имел поле заголовка под названием LRU_Index, которое использовалось для упорядочивания функции LRU . Последняя вызванная функция имела наивысшее значение LRU_Index.
- Вдобавок у меня была глобальная целочисленная переменная Next_LRU_Index. Она была инициализирована нулем.
- Свободные фрагменты памяти были огранизованы в двусвязный список.
Вот как это все работало:
Когда функция вызывалась (или возвращалась из вложенного вызова), мы сначала проверяли, находится ли она в памяти, проверяя ее ячейку в Address_Array.
Если оказывалось, что она в памяти, мы увеличивали переменную Next_LRU_Index (наблюдая за целочисленным переполнением) и помещали ее значение в LRU_Index функции.
Если требуемой функции не было в памяти, мы сначала проверяли, есть ли достаточно памяти для ее загрузки. Если есть, то мы загружали ее и продолжали вызов, как описано выше. В противном случае нам нужно было выбросить из памяти какую-нубудь другую функцию. Мы перебрали все загруженные в текущий момент функции и находили функцию с наименьшим LRU_Index. Я экспериментировал с двусвязным списком, но пришел к выводу, что линейный поиск в целом более эффективен. Мы заменяли адрес функции в Address_Array на NULL, освобождали память и повторяли попытку. Если у нас все еще было недостаточно памяти, мы выбрасывали еще одну функцию и т. д. Когда больше не было функций для замены, мы попытались сжать всю память. Если и это не помогло, значит нам официально не хватило памяти.
Конечно, это была примитивная виртуальная память, но она была простой, компактной и выполняла поставленную задачу. DBCalc по-прежнему был намного быстрее, чем Datatrieve.
Не по существу
Русифицированная версия Datatrieve-11 называлась ФОБРИН, сокращенно ФБР (В ОС RSX-11M программы запускались по трехбуквенному коду). Соотвественно, было много шуток о причастности ФБР к управлению советскими базами данных. Это было до Интернета, наш компьютер не был подключен ни к каким сетям, поэтому мы не боялись шпионажа. В основном мы шутили об опасности саботажа. «Как вы думаете, ФБР может в прямом смысле износить наши диски до алюминиевой подложки?»
Как понятно, ФБР не имело никакого отношения к нашему исследовательскому институту, но КГБ определенно имело. В 40е годы они убили потрясающего ученого, основателя ВИРа, Николая Ивановича Вавилова . Затем они продолжали наблюдать за всей научной деятельностью института из своего офиса в главном здании. Табличка на двери гласила: «Отдел №1». По традиции КГБ был первым отделом в каждой организации, поэтому в просторечии вместо того, чтобы сказать «Я разговаривал с КГБ», вы бы сказали «Я был в Первом отделе». Их официальная работа заключалась в обеспечении надлежащего обращения с секретной информацией. Когда я решил уволиться с работы в 1990 году, мне привелось провести два часа в этом офисе. Все, что мне было нужно, это подпись в моем выписном листе. Вместо того, чтобы просто удостовериться, что у меня нет секретных документов, товарищ КГБшник усадил меня и захотел узнать обо мне все: подробности работы с которой я уходил, моей новой работы, историю моей семьи и т. д. Он получил удовольствие от допроса, а я точно не получил.