На этом шаге мы рассмотрим функции и переменные, применяемые для управления памятью.
В результате вычислений в памяти может возникать мусор - это структуры, на которые уже больше нельзя сослаться. Это происходит в тех случаях, когда вычисленная структура не сохраняется с помощью функций типа SETQ или когда теряется ссылка на старое значение в результате побочного эффекта нового вызова SETQ или другой функции. Например:
$ (SETQ SPISOK ((Это станет мусором) А эта часть нет))
Приведем графическое представление построенного списка:
Рис.1. Графическое представление списка
После присваивания нового значения:
$ (SETQ SPISOK (CDR SPISOK))
уже нельзя будет "добраться" до трех списочных ячеек. Говорят, что эти ячейки стали мусором.
Это достаточно очевидно, если взглянуть на графическое представление списка SPISOK.
Рис.2. Графическое представление списка
Мусор возникает и тогда, когда результат вычислений не связывается с какой-нибудь переменной. Например, значение вызова функции CONS:
$ (CONS A (LIST B))
лишь выводится на экран дисплея, после чего соответствующая ему структура останется в памяти мусором.
Для повторного использования ставшей мусором памяти в LISP-системах предусмотрен специальный сборщик мусора, который автоматически запускается, когда в памяти остается мало свободного места. Сборщик мусора перебирает все ячейки и собирает являющиеся мусором ячейки в список свободной памяти для того, чтобы их можно было использовать заново.
При ограниченной области памяти, доступной пользователю, сборка мусора часто существенно замедляет интерактивный доступ к ЭВМ. Этим обусловлено замечание Лооса: "Возможно, единственный путь к оптимизации процесса сборки мусора и к ограничению его влияния заключается в разработке специального алгоритмического языка, позволяющего связать воедино все аспекты вычисления, включая сборку мусора."
Функция RECLAIM управляет работой сборщика мусора и возвращает количество свободной памяти в области данных. Т.к. управление памятью в muLISP полностью автоматизировано, RECLAIM используется только для определения количества свободной памяти или для минимизации количества "сборок мусора" в процессе работы программы. Если требуется, выполняется также перераспределение памяти. Возвращается итоговое число байтов, доступных под области атомов, векторов, указателей и стековые области. Синтаксис функции:
$ (RECLAIM)
Замечание. Динамическое автоматическое управление памятью дает системе muLISP85 большое преимущество. Это освобождает программиста от необходимости заранее распределять имеющуюся память под задачу. Такое распределение перед выполнением задания является очень трудным делом (если, вообще, возможным!) для большинства задач искусственного интеллекта.
На стадии инициализации системы muLISP85 вычисляется размер памяти ввода-вывода, имеющейся в распоряжении системы. Память затем разпределяется на четыре непересекающихся области данных.
Область атомов - это участок памяти для хранения информации об атомах и числах (четырех элементов-указателей, требуемых для каждого атома и числа).
Область векторов - это участок памяти для хранения Р-имен атомов и числовых двоичных векторов каждого числа.
Область указателей - это область памяти, отведенная под два элемента-указателя, требуемые для каждой точечной пары, и под D-код, требуемый для каждого определения функции. Так как точечная пара - это основная простейшая структура данных muLISP, то область указателей обычно бывает самой большой из всех областей данных.
Область стеков - это область памяти для контрольного стека и переменного стека. Эти два стека расположены на противоположных концах области стеков.
Если muLISP85 работает на ЭВМ семейства Intel 8086, то память разделяется на сегменты по 64К. Это накладывает ограничение на размер каждой области данных muLISP.
Следовательно, память, доступная для области векторов, составляет 128К: 64К для Р-имен и 64К для векторов чисел.
Область памяти, доступная для элементов-указателей обьектов данных (т.е. атомов, чисел и точечных пар) составляет 25К.
Область памяти, доступная для D-кодов и стеков, составляет 64К.
Область памяти, доступная для начальных выражений и машинных кодов, определяемых пользователем, составляет 64К.
Следовательно, система muLISP требует для работы 512К плюс память, требуемая для операционной системы.
В системе muLISP85 используется алгоритм сборки мусора с двумя просмотрами (пометки-чистки).
Первый просмотр алгоритма заключается в пометке всех активных обьектов данных. Это те обьекты, доступ к которым обеспечивается посредством сцепления с помощью элементов-указателей, начиная с элементов списка значений и свойств всех символов системы, или со стека переменных, или с D-кодов. Символы с авто-ссылкой, которые не имеют свойств и текущих определений функций, не помечаются. Такие символы автоматически удаляются из списка в ходе второго просмотра.
В процессе второго просмотра сборки мусора все помеченные обьекты данных уплотняются и собираются в одном из концов соответствующей области данных. Это позволяет сохранить остатки имеющихся в распоряжении областей данных для вновь создаваемых обьектов.
После сборки мусора какая-либо одна (или несколько) из четырех областей данных muLISP85 может иметь недостаточное количество свободной памяти для того, чтобы программы могли продолжить выполнение, несмотря на то, что другие области данных имеют достаточно свободной памяти. Если возникает такая ситуация, то осуществляется перераспределение областей данных путем деления областей, добавления недостающей памяти одной или нескольким областям. (Однако, ограничения на размер для каждой области данных, как описывалось выше, при распределении должны соблюдаться).
Хотя сборка мусора и перераспределение областей данных происходят автоматически, их появление не проходит незаметно для пользователя, т.к. они вызывают короткую паузу в работе программ.
Точная сумма времени для сборки мусора и перераспределения зависит от количества данных в системе. Сборка мусора обычно занимает менее секунды. Точно так же, менее секунды обычно происходит и перераспределение областей данных. В действительности, это не должно заботить пользователя, но при разработке систем реального времени, использующих систему muLISP85, данный вопрос требуется рассматривать.
Явление, известное как "Thrashing" ("взбучка") возникает в том случае, когда система вынуждена затрачивать непредвиденное время на сборку мусора для "очень маленького" возврата области данных. Признаком "Thrashing" является значительное возрастание времени выполнения задачи. Эта проблема может быть разрешена путем увеличения размера памяти ЭВМ (до 512К) и (или) модификации программы с целью уменьшения ее требований к памяти.
Ниже мы опишем некоторые функции и системные переменные, используемые при управлении памятью.
- Если N - положительное целое число, то функция (ALLOCATE N) освобождает N байтов
памяти в 8086-кодовом сегменте, следующем за машинным кодом muLISP, и возвращает базовый адрес вновь выделенной памяти.
Если нельзя освободить N байтов, то функция ALLOCATE возвращает NIL.
Функция (ALLOCATE) возвращает текущий базовый адрес начала свободной области в 8086-кодовом сегменте, следующем за машинным кодом muLISP. Например:
$ (ALLOCATE 100) $ (ALLOCATE) 32400 32512
- Если системная переменная RECLAIM равна NIL, на консоль высвечивается информационная статистика до и после
работы всех сборщиков мусора и перераспределения памяти.
Первая строка статистики показывает, какая область является доступной для работы до работы сборщика мусора.
Вторая строка показывает доступную область после работы сборщика.
Строки, начинающиеся с "GC", означают статистику сборщика мусора. Строки, начинающиеся с "RA", означают статистику процесса перераспределения области данных.
Формат строки статистики следующий:
nnnn, aaaa, vvvv, pppp, ssss и tttt - это шестнадцатеричные числа. nnnn - это количество сборок мусора с момента начала выполнения muLISP.GC : nnnn aaaa/aaaa vvvv/vvvv pppp/pppp ssss/ssss tttt/tttt
Первые числа aaaa, vvvv, pppp и ssss в каждой паре чисел - это сумма свободной памяти в байтах в областях атомов, векторов, указателей и стеков соответственно. Первое число tttt пары - это полная сумма свободных областей (сумма aaaa, vvvv, pppp и ssss).
Числа, следующие за "/" - это полный обьем соответствующих областей, включающих и свободные, и занятые области.
Для каждой ячейки указателя в областях указателей, стеков и атомов требуется два байта. Один байт требуется для каждого символа в Р-имени, два байта - для размещения длины Р-имени. Числовые векторы используют столько слов, сколько необходимо для размещения числа в двоичном виде.
Данная статистика сильно зависит от того, как работает muLISP, и не зависит от пользователя. Данная статистика появляется еще и тогда, когда возникает ошибка "Memory full" и указывает, какая часть памяти переполнилась. Например:
$ (SETQ RECLAIM NIL) NIL $ (LOOP (OBLIST)) GC: 0001 2258/2600 1C8C/1C8E 00000/119C0 1AAA/1AC0 0598C/1770E GC: 0001 2258/2600 1C8C/1C8E 117D0/119C0 1AAA/1AC0 1715C/1770E RA: 0001 09C0/0D68 09C2/09C4 13CFE/13EEE 20DE/20F4 1715C/1770E GC: 0002 09C0/0D68 09C2/09C4 00002/13EEE 20DE/20F4 03460/1770E GC: 0002 09C0/0D68 09C2/09C4 13E1A/13EEE 20DE/20F4 17278/1770E GC: 0003 09C0/0D68 09C2/09C4 00002/13EEE 20DE/20F4 03460/1770E GC: 0003 09C0/0D68 09C2/09C4 13E1A/13EEE 20DE/20F4 17278/1770E
Три строки статистики сборщика мусора номер 1 означают, что произошло перераспределение памяти. Было выделено больше памяти под область указателей из-за того, что OBLIST "требует" новые точечные пары. Последующие сборщики мусора не выполняют перераспределения, т.к. размеры областей данных уже были оптимизированы. Однако, если программа изменилась и "обратилась к" области атомов, может произойти другое перераспределение с целью увеличения размера этой области за счет других.
Числа, приведенные выше, зависят от размеров памяти ЭВМ; здесь они даны для версии 8086/8088 muLISP85.
- Функциям-конструкторам обычно "требуются" новые точечные пары. Если значение системной переменной *FREE-LIST* -
атом, то область для новых точечных пар берется из области памяти, которая называется областью указателей. Если вся область указателей
была исчерпана на создание предыдущих точечных пар, то для восстановления областей под точечные пары
автоматически запускается сборщик мусора.
Однако если значение *FREE-LIST* есть точечная пара, то эта точечная пара используется тогда, когда для системы muLISP85 требуется новая точечная пара.
В примере осуществляется добавление 6 (но не 9) точечных пар к *FREE-LIST*:
$ (SETQ JUNK '(A B (C D E) 3 4 5)) $ (SETQ *FREE-LIST* *NCONC JUNK *FREE-LIST*)
- Если ADDRESS - нуль или положительное целое, меньшее, чем область памяти микропроцессора, на котором работает
muLISP85, функция (MEMORY ADDRESS) передает байт (8-битовое значение) в ADDRESS.
Если VALUE - нуль или положительное целое число, меньшее, чем 256, функция (MEMORY ADDRESS VALUE) запоминает значение VALUE байта по адресу ADDRESS и возвращает первоначальное значение байта.
Если FLAG не равен NIL, то функция (MEMORY ADDRESS VALUE FLAG) передает слово (16-битовое значение) в адрес ADDRESS. Если VALUE - нуль или положительное целое, меньшее, чем 65536, то функция (MEMORY ADDRESS VALUE FLAG) запоминает значение VALUE слова по адресу ADDRESS и возвращает первоначальное значение слова. Например:
$ (SETQ *PRINT-BASE* 16 *READ-BASE* 16) 10 ; Шестнадцатеричный ввод-вывод $ (MEMORY 12) 0 ; Байт 12H $ (MEMORY 12 NIL T) 0F000 ; Слово 12H $ (MEMORY 12 5) 0 ; Сохранили 5 по адресу 12H $ (MEMORY 12) 5 ; Байт 12H $ (MEMORY 12 NIL T) 0F005 ; Слово 12H $ (MEMORY 12 0) 5 ; Восстановили байт $ (SETQ *PRINT-BASE* 0A *READ-CHAR* 0A) ; Десятичный ввод-выводПредупреждаем, что функция MEMORY должна использоваться очень осторожно, т.к. отсутствует защита от разрушения интерпретатора muLISP85 или операционной системы.
- Функции CSMEMORY и DSMEMORY доступны только тогда, когда система muLISP85
работает на ЭВМ семейства микропроцессоров Intel 8086. Эти функции подобны функции MEMORY, за
исключением того, что здесь первый аргумент - это шестнадцатибитовое поле сегмента, а не двадцатибитовый физический
адрес. Первое поле CSMEMORY подобно сегменту кода. В DSMEMORY первое поле соответствует
сегменту данных.
Если OFFSET - нуль или положительное целое число, меньшее, чем 65536, то функции (CSMEMORY OFFSET) и (DSMEMORY OFFSET) пересылают байт в поле со смещением OFFSET.
Если VALUE - нуль или положительное целое число, меньшее, чем 256, то функции (CSMEMORY OFFSET VALUE) и (DSMEMORY OFFSET VALUE) записывают значение байта VALUE в поле со смещением OFFSET и возвращают первоначальное значение байта.
Если FLAG - не NIL, то функции (CSMEMORY OFFSET NIL FLAG) и (DSMEMORY OFFSET NIL FLAG) возвращают слово в поле со смещением OFFSET.
Если VALUE - нуль или положительное целое число, меньшее чем 65536, то функции (CSMEMORY OFFSET VALUE FLAG) и (DSMEMORY OFFSET VALUE FLAG) запоминают VALUE слова в поле со смещением OFFSET и возвращает первоначальное значение слова. Например:
$ (SETQ *PRINT-BASE* 16 *READ-BASE* 16) ; Шестнадцатеричный ввод-вывод $ (CSMEMORY 100) 0E9 ; Байт в CS:100H $ (CSMEMORY 100 NIL T) 3E9 ; Слово в CS:100H $ (CSMEMORY 100 41) 0E9 ; Сохранение 41H в CS:100H $ (CSMEMORY 100) 41 ; Байт в CS:100H $ (CSMEMORY 100 NIL T) 341 ; Слово в CS:100H $ (CSMEMORY 100 0E9) 41 ; Восстановили исходное значение $ (SETQ *PRINT-BASE* 0A *READ-CHAR* 0A) ; Десятичный ввод-выводПредупреждаем, что функциями CSMEMORY и DSMEMORY надо пользоваться осторожно, т.к. защита программ muLISP от разрушения отсутствует!
- Если PORT - нуль или положительное целое меньшее, чем 65536, то функция (PORTIO PORT)
вводит и возвращает значение байта из PORT.
Если значение VALUE - нуль или положительное целое меньшее, чем 256, то функция (PORTIO PORT VALUE) передает значение VALUE в PORT и возвращает NIL.
Если FLAG - не NIL, то функция (PORTIO PORT NIL FLAG) вводит и выдает значение слова из PORT.
Если VALUE - нуль или положительное целое меньшее, чем 65536, то функция (PORTIO PORT VALUE) передает значение VALUE в PORT и возвращает NIL.
Данная функция используется для пересылки значений байта или слова в выходные порты и получения значений байта или слова из входных портов. Это может быть использовано в программах muLISP, когда требуется обеспечить связь с такими внешними устройствами, как сенсоры, роботы и др. Пример:
$ (SETQ *PRINT-BASE* 16 *READ-BASE* 16) ; Шестнадцатеричный ввод-вывод $ (PORTIO 72) <?> ; Ввели байт из порта 72H $ (PORTIO 72 10) NIL ; Вывели 10H в порт 72H $ (SETQ *PRINT-BASE* 0A *READ-CHAR* 0A) ; Десятичный ввод-вывод - Элементы указателей, входящие в состав объектов, запоминаются в отдельных сегментах данных по одинаковым адресам
полей. Функция (LOCATION OBJECT) возвращает первое поле (Offset) элементов обьекта OBJECT из базы сегментов данных.
Т.к. все элементы занимают ровно 2 байта, то функция LOCATION всегда возвращает четное целое число.
Отметим, что система muLISP автоматически выполняет сборку мусора и перераспределение памяти, что может изменить расположение обьекта. Функция LOCATION, в основном, предназначается для компиляторов, которые генерируют машинные коды и должны знать, как располагаются символы в памяти. Например:
$ (LOCATION NIL) 256 $ (LOCATION 2) 3458 $ (LOCATION '(A . B)) 9376
- Функция (REGISTER N M) размещает M в псевдорегистре muLISP N, если M - это неотрицательное целое меньшее, чем
65536, и возвращает NIL.
Если M не является таковым, то возвращается содержимое псевдорегистра N. По умолчанию значение для всех регистров берется равным 0. Например:
$ (REGISTER 2) 0 $ (REGISTER 2 100) NIL $ (REGISTER 2) 100
- Функция (INTERRUPT N) загружает в регистры микропроцессора значение псевдорегистров muLISP, выполняет прерывание
с номером N, сохраняет значения регистров, выданные при прерывании, в псевдорегистрах и возвращает NIL.
Отметим, что функция INTERRUPT доступна только тогда, когда muLISP работает на ЭВМ семейства микропроцессоров Intel 8086.
В muLISP имеется 10 псевдорегистров (с 0 по 9). Соответствие между ними и регистрами 8086 приведено в следующей таблице:
Псевдорегистры: 0 1 2 3 4 5 6 7 8 9 Регистры 8086 : AX BX CX DX SI DI BP DS ES FLAG
Функции REGISTER и INTERRUPT обеспечивает взаимосвязь между внешними шаблонами на машинном языке и программами muLISP посредством 256 векторов прерывания микропроцессора 8086. Технические рекомендации ЭВМ и руководства по ОС содержат информацию о сервисе, который предоставляют вектора прерывания.
Например, прерывание с номером 33 (21Н) используется MS-DOS для системных вызовов. Если регистр АН содержит 44 (2АН), то (Interrupt 33) вернет: год - СХ (1980-2099), месяц - DH (1-12) и день - DL (1-31). Например:
$ (SETQ *PRINT-BASE* 16 *READ-BASE* 16) $ (REGISTER 0 2A00) NIL $ (INTERRUPT 21) NIL $ (SETQ *PRINT-BASE* 0A *READ-BASE* 0A) $ (REGISTER 2) 1985 $ (DIVIDE (REGISTER 3) 256) (1 . 5)
- Если OFFSET - положительное целое меньшее, чем 65536, то функция (BINARY-LOAD DRIVE:NAME.TYPE OFFSET)
загружает файл NAME:TYPE на устройство DRIVE в сегмент кодов в поле со смещением OFFSET и возвращает
количество загруженных байтов.
Если .TYPE отсутствует, то используется текущее зафиксированное устройство. Если OFFSET не из этой области или файл не найден, то функция BINARY-LOAD возвращает NIL.
Функция BINARY-LOAD обычно используется в совокупности с функцией ALLOCATE.
- Если ADDRESS - нуль или положительное целое меньшее, чем адресная область микропроцессора, на котором работает
muLISP, а N - положительное целое число меньшее, чем 65536, то функция (SNAPSHOT ADDRESS N) возвращает атом, Р-имя
которого состоит из N байтов памяти, начиная с адреса ADDRESS.
Если SYMBOL - это символ, то функция (SNAPSHOT ADDRESS SYMBOL) размещает байты в Р-имени символа SYMBOL в памяти, начиная с адреса ADDRESS, и возвращает Т.
Функцию SNAPSHOT особенно удобно использовать для манипулирования видео-экранной памятью IBM PC. Например:
$ (SETQ *PRINT-BASE* 16 *READ-BASE* 16) $ (SNAPSHOT 0B0000 200) <Первые 512 байтов видеопамяти PC> $ (SETQ *PRINT-BASE* 0A *READ-BASE* 0A)
На следующем шаге мы рассмотрим простейшие модификаторы.
