Открытая память (продолжение)

Описанные выше алгоритмы распределения памяти используются не операционной системой, а библиотечными функциями, присоединенными к программе. Однако ОС, которая реализует одновременную загрузку (но не обязательно одновременное исполнение: MS DOS — типичный пример такой системы) нескольких задач, также должна использовать тот или иной алгоритм размещения памяти. Отчасти такие алгоритмы могут быть похожи на работу функции malloc. Однако режим работы ОС может вносить существенные упрощения в алгоритм.
Перемещать образ загруженного процесса по памяти невозможно: даже если его код был позиционно-независим и не подвергался перенастройке, сегмент данных может содержать (и почти наверняка содержит) указатели, которые при перемещении необходимо перенастроить. Поэтому при выгрузке задач из памяти перед нами в полный рост встает проблема внешней фрагментации (рис. 4.13).

Рис. 4.13. Фрагментация при загрузке и выгрузке задач

 

Управление памятью в OS/360
В этой связи нельзя не упомянуть о поучительной истории, связанной с управлением памятью в системах линии IBM System 360. В этих машинах не было аппаратных средств управления памятью, и все программы разделяли общее виртуальное адресное пространство, совпадающее с физическим. Адресные ссылки в программе задавались 12-битовым смещением относительно базового регистра. В качестве базового регистра мог использоваться, в принципе, любой из 16 32-битовых регистров общего назначения. Предполагалось, что пользовательские программы не модифицируют базовый регистр, поэтому можно загружать их с различных адресов, просто перенастраивая значение этого регистра. Таким образом, была реализована одновременная загрузка многих прО" грамм в многозадачной системе OS/360.
Однако после загрузки программу уже нельзя было перемещать по памяти: например, при вызове подпрограммы адрес возврата сохраняется в виде абсолютного 24-битовог.о адреса (в System 360 под адрес отводилось 32-разрядное слово, но использовались только 24 младших бита адреса. В System 370 адрес стал 31-разрядным) и при возврате базовый регистр не применяется. Аналогично, базовый регистр не используется при ссылках на блоки параметров и сами параметры подпрограмм языка FORTRAN (в этом языке все параметры передаются по ссылке), при работе с указателями в PL/I и т. д. Перемещение программы, даже с перенастройкой базового регистра, нарушило бы все такие ссылки.
Разработчики фирмы IBM вскоре осознали пользу перемещения программ после их загрузки и попытались как-то решить эту проблему. Очень любопытный документ "Preparing to Rollin-Rollout Guideline" (Руководство по подготовке [программы] к вкатыванию и выкатыванию; к сожалению, автору не удалось найти полного текста этого документа) описывает действия, которые программа должна была бы предпринять после перемещения. Фактически программа должна была найти в своем сегменте данных все абсолютные адреса и сама перенастроить их.
Естественно, никто из разработчиков компиляторов и прикладного программного обеспечения не собирался следовать этому руководству. В результате, проблема перемещения программ в OS/360 не была решена вплоть до появления машин System 370 со страничным или странично-сегментным диспетчером памяти и ОС MVS.

В данном случае проблема фрагментации особенно остра, так как типичный образ процесса занимает значительную часть всего доступного ОЗУ. Если при выделении небольших блоков мы еще можем рассчитывать на "закон больших чисел" и прочие статистические закономерности, то самый простой сценарий загрузки трех процессов различного размера может привести нас к неразрешимой ситуации (см. рис. 4.13).
Разделы памяти (см. разд. Разделы памяти) отчасти позволяют решить проблему внешней фрагментации, устанавливая, что процесс должен либо использовать раздел Целиком, либо не использовать его вовсе. Как и все ограничения на размер единицы выделения памяти, это решение загоняет проблему внутрь, переводя внешнюю фрагментацию во внутреннюю. Поэтому некоторые системы предлагают другие способы наложения ограничения на порядок загрузки и выгрузки задач.

Управление памятью в MS DOS
Так, например, процедура управления памятью MS DOS рассчитана на случай, когда программы выгружаются из памяти только в порядке, обратном тому, в каком они туда загружались (на практике, они могут выгружаться и в другом порядке, но это явно запрещено в документации и часто приводит к проблемам). Это позволяет свести управление памятью к стековой дисциплине.
Каждой программе в MS DOS отводится блок памяти. С каждым таким блоком ассоциирован дескриптор, называемый МСВ — Memory Control Block (рис. 4.14). Этот дескриптор содержит размер блока, идентификатор программы, которой принадлежит этот блок, и признак того, является ли данный блок
последним в цепочке. Нужно отметить, что программе всегда принадлежит несколько блоков, но это уже несущественные детали. Другая малосущественная деталь та, что размер сегментов и их адреса отсчитываются в параграфах размером 16 байт. Знакомые с архитектурой процессора 8086 должны вспомнить, что адрес МСВ в этом случае будет состоять только из сегментной части с нулевым смещением.
После запуска corn-файл получает сегмент размером 64Кбайт, а ехе — всю доступную память. Обычно ехе-модули сразу после запуска освобождают ненужную им память и устанавливают brklevel на конец своего сегмента, а потом увеличивают brklevel и наращивают сегмент по мере необходимости.
Естественно, что наращивать сегмент можно только за счет следующего за ним в цепочке МСВ, и MS DOS разрешит делать это только в случае, если этот сегмент не принадлежит никакой программе.
При запуске программы DOS берет последний сегмент в цепочке и загружает туда программу, если этот сегмент достаточно велик. Если он недостаточно велик, DOS говорит: "Недостаточно памяти" и отказывается загружать программу. При завершении программы DOS освобождает все блоки, принадлежавшие программе. При этом соседние блоки объединяются. Пока программы, действительно, завершаются в порядке, обратном тому, в котором они запускались, — все вполне нормально. Другое дело, что в реальной жизни возможны отклонения от этой схемы. Например, предполагается, что TSR-программы (Terminate, but Stay Resident - Завершиться и остаться резидентно (в памяти)) никогда не пытаются по-настоящему завершиться и выгрузиться. Тем не менее, любой уважающий себя хакер считает своим долгом сделать резидентную программу выгружаемой. У некоторых хакеров она в результате выбрасывает при выгрузке все резиденты, которые заняли память после нее. Другой пример — отладчики обычно загружают программу в обход обычной DOS-овской функции LOAD & EXECUTE, а при завершении отлаживаемой программы сами освобождают занимаемую ею память.
Автор в свое время занимался прохождением некоторой программы под управлением отладчика. Честно говоря, речь шла о взломе некоторой игрушки... Эта программа производила какую-то инициализацию, а потом вызывала функцию DOS LOAD & EXECUTE. Я об этом не знал и, естественно, попал внутрь новой программы, которую и должен был взламывать.
После нескольких нажатий комбинаций клавиш <CTRL>+<Break> я наконец-то вернулся в отладчик, но при каком-то очень странном состоянии программы. Покопавшись в программе с помощью отладчика в течение некоторого времени и убедившись, что она не хочет приходить в нормальное состояние, я вышел из отладчика и увидел следующую картину: системе доступно около 100 Кбайт в то время, как сумма длин свободных блоков памяти более 300 Кбайт, а размер наибольшего свободного блока около 200 Кбайт. Отладчик выходя, освободил свою память и память отлаживаемой программы, но не освободил память, выделенную новому загруженному модулю. В результате посредине памяти ос-тался никому не нужный блок изрядного размера, помеченный как используемый (рис. 4.15). Самым обидным было то, что DOS не пыталась загрузить ни одну программу в память под этим блоком, хотя там было гораздо больше места, чем над ним.

Рис. 4.14. Управление памятью в MS DOS

Рис. 4.15. Нарушения стекового порядка загрузки и выгрузки в MS DOS

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

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

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