Список - свободная память
Cтраница 3
Необходимо каким-то образом фиксировать, какие ячейки памяти в данный момент не используются. В IPL все не используемые в данный момент ячейки объединены в список, именуемый Н2, который называется списком свободной памяти. В процессе расшифровки или в любом другом случае, в котором может потребоваться свободная ячейка, в качестве нее выбирается первая ячейка из списка свободной памяти. Подобным же образом ненужные ячейки возвращаются в этот список. Этот механизм освобождает программиста от необходимости решать задачу распределения памяти и позволяет ему свободно пользоваться различными процессами, меняющими структуру памяти. [31]
Последний этап записи модели в банк - корректировка заголовка банка, в который записываются новые адреса свободной части каталога и хранилища. Оператор чтения модели из банка по своей логике значительно проще. По символическому имени модели из каталога банка определяется ее относительный адрес в хранилище и формируется абсолютный адрес на физическом носителе, по которому происходит обмен между оперативной и внешней памятью ЭВМ. Кроме операторов записи и чтения модели фигуры из банка, в наборе управляющих операторов необходим оператор уничтожения модели в банке. Оператор работает таким образом, что уничтожается только символическое имя модели в каталоге и формируется список свободной памяти хранилища, представляющий собой адресные ссылки между записями каталога банка, в которых были записаны имена уничтоженных моделей. [32]
Представим себе, что мы разрабатываем универсальную систему для обработки Списков, которая будет использоваться сотнями других программистов. Для обслуживания, списка свободного пространства предлагается два основных метода: счетчики ссылок и сбор мусора. В методе счетчиков используется специальное поле в каждом узле, в котором учитывается, сколько стрелок указывает на этот узел. За таким счетчиком довольно легко следить во время работы программы, и всякий раз, когда счетчик сбрасывается в нуль, данный узел становится свободным. В этом случае идея состоит в том, что почти все алгоритмы не возвращают узлы в список свободной памяти и программа беззаботно работает до тех пор, пока не исчерпается весь этот список; тогда алгоритм сбора мусора, используя биты маркировки, возвращает в свободную память все узлы, которые в данный момент программе недоступны, после чего программа продолжает работать. [33]
Диагностический монитор можно реализовать как периодически выполняемую задачу ( например, она планируется на каждый час) либо как задачу с низким приоритетом, которая планируется для выполнения в то время, когда система переходит в состояние ожидания. Как и прежде, выполняемые монитором конкретные проверки зависят от специфики системы, но некоторые идеи будут понятны из примеров. Монитор может обследовать основную память, чтобы обнаружить блоки памяти, не выделенные ни одной из выполняемых задач и не включенные в системный список свободной памяти. Он может проверять также необычные ситуации: например, процесс не планировался для выполнения в течение некоторого разумного интервала времени. Монитор может осуществлять попек затерявшихся внутри системы сообщений или операций ввода-вывода, которые необычно долгое время остаются незавершенными, участков памяти на диске, которые не помечены как выделенные и не включены в список свободной памяти, а также различного рода странностей в файлах данных. [34]
 |
Представление кольца и очереди с использованием указателей. [35] |
Эту проблему можно решить путем придания памяти определенной структуры, связав между собой отдельные блоки ( узлы) памяти с помощью указателей. Прямоугольниками на рисунке показаны узлы памяти. Каждый узел состоит из двух полей. Одно поле содержит элемент или более сложную структуру данных, а другое - указатель на следующий узел. Стрелки на рисунке соответствуют значениям указателей. Обе операции используют список свободной памяти - при включении память занимается, а при исключении возвращается в этот список. [36]
В реализации Лиспа стек используется несколько иначе. Здесь также вызовы подпрограмм ( функций) строго вложены, и для активационных записей можно использовать стек. Каждая активационная запись содержит точку возврата и временные переменные для вычисления выражений и передачи параметров. Локальные среды ссылок ( элементы А-списка) можно было бы попытаться расположить в том же стеке, однако программисту разрешается непосредственно манипулировать ассоциациями локальных сред. Поэтому они обычно записываются в отдельный стек, представленный в виде связанного списка, называемого А-списком. Стек, содержащий точки возврата и временные переменные, может быть в этом случае скрыт от программиста и строиться на основе последовательного распределения. Реализация Лиспа требует также области памяти, называемой кучей, которая управляется с помощью списка свободной памяти и сбора мусора, при этом для элементов, занимающих полное слово ( например, для чисел), выделяется специальная область со специальным алгоритмом управления. [37]
Страницы: 1 2 3