Системы с виртуальной памятью сегодня весьма распространены. Иногда даже кажется, что так было всегда. Но это не так. И файл подкачки (своп, swap), или раздел подкачки, далеко не всегда были неотъемлемой части операционных систем.
Темы виртуальной памяти я касался в некоторых статьях. Последний раз в статье
Наверное имеет смысл рассмотреть связанные с виртуальной памятью вопросы более подробно. Но сегодня мы поговорим о том, что было до массового распространения виртуальной памяти.
Памяти много не бывает
Это было актуально всегда. И в уже почти былинные времена первых ЭВМ. И в наши дни. Точно так же, всегда существовала необходимость обрабатывать очень большие объемы данных, которые не помещаются в доступную программе память. Проблема решалась обработкой больших объемов данных небольшими порциями. Наиболее известной является, пожалуй, сортировка на магнитных лентах. Но сегодня речь пойдет не об этом.
Но бывают ситуации, когда объем доступной памяти превышает уже сам программный код. Простейший способ решения этой проблемы - разбиение программы на несколько отдельных программ, которые выполняются последовательно. При этом и данные, которая программа обрабатывает, должны сохраняться на внешних носителях между запуском отдельных фрагментов, на которые программа разбивается.
Выполнение цепочки программ действительно было популярным методом. Но такое возможно не всегда. Например, сам алгоритм решения задачи может быть сложным. И состоять из отдельных больших шагов, которые выполняются итерационно. Преобразовать такую программу в цепочку с жестким числом элементов весьма непросто.
Вот для таких программ и был разработан метод перекрытий. И этот метод можно считать предшественником виртуальной памяти. Давайте посмотрим, что лежит в основе метода и как он работает.
Обобщенная структура программ
Что бы понять, как устроены и работают перекрытия, нужно разобраться в структуре обобщенной программы для ЭВМ. Крайне редко программа бывает одним неразрывным и непрерывным блоком кода. В подавляющем большинстве случаев программа состоит из основной программы и вызываемых ей подпрограмм. Даже если и основная программа, и все подпрограммы, находятся в одном общем исходном файле.
Это верно даже для случая, когда программа написана на языке высокого уровня без разбиения на подпрограммы. Компилятор далеко не всегда преобразует исходный текст программы непосредственно в машинные коды. Чаще всего, генерируется код вызывающий подпрограммы так называемой среды времени выполнения (run-time).
Таким образом, можно, в первом приближении, представить структуру программы примерно так
Если вы сторонник объектно-ориентированного подхода, то вынужден вас разочаровать. После компилятора ваша программа будет иметь такой же вид. Вся логическая объектная структура, вся семантика, будет реализовываться на старом добром процедурном уровне. Это не злой умысел, это просто реальность сегодняшнего уровня развития процессоров.
Каждая подпрограмма может иметь собственные данные, собственные переменные. Это не автоматические переменные, которые размещаются в стеке. Это могут быть статические переменные модуля (не путать с подпрограммой), могут быть переменные в старых языках, например, Fortran.
Автоматические переменные размещаются в стеке, который является общим для всех подпрограмм и для основной программы. И логически стек относится именно к основной программе. Глобальные переменные тоже размещаются в области основной программы.
Мы можем построить "дерево вызовов" подпрограмм. Каждый лист или узел дерева будет соответствовать отдельной подпрограмме, а ветви будут показывать путь прохождения вызова этой подпрограммы. При этом все узлы и листья должны быть уникальными.
Давайте рассмотрим небольшой пример
Это дерево показывает не очередность или последовательность вызова подпрограмм. Дерево показывает пути вызова и возможность вызова. Понятно, что основная программа может вызвать любую подпрограмму. Но подпрограммы могут вызывать друг друга только в том случае, если они лежат на одном пути от этих подпрограмм до корня, которым является основная программа. Кажется слишком сложным? На самом деле все довольно просто.
Поскольку все пути сходятся в корне, основная программа действительно имеет возможность вызова любой подпрограммы. Но давайте рассмотрим подпрограмму, например, F. Путь от этой подпрограммы до корня включает в себя подпрограммы F, D, A, собственно основная программа. Вот в пределах этого пути и возможен взаимный вызов подпрограмм.
Красным цветом я выделил тот самый путь в дереве, о котором говорил. Подпрограмма F может вызвать подпрограммы A и D. Подпрограмма D может вызвать подпрограммы A и F. И так далее. Но ни одна из подпрограмм A, D, F не может вызвать какие либо другие подпрограммы.
Если вы считаете это ограничением, то вы ошибаетесь. На самом деле, дерево построено на основании того, какие программы как вызывают друг друга. А не на основании возможности вызова. Но при модификации программы уже приходится учитывать и возможность вызова. Если изменяются взаимосвязи подпрограммы, то она должна быть перемещена на новое место в дереве вызовов.
Предположим, что подпрограммам F и G потребовалось вызывать подпрограмму E, в результате модификации. А подпрограмма I должна быть доступна всем другим подпрограммам. Тогда измененное дерево вызовов получится таким
Видно, что подпрограммы E и I переместились ближе к корню. Повторюсь, дерево вызовов отражает взаимосвязь подпрограмм внутри программы и строится по результатам анализа программы. Оно вторично, а не первично. С точки зрения самой программы и ее разработки.
Дерево программы и возможность совместного использования памяти
Давайте внимательно посмотрим на деревья вызовов. Можно выделить несколько независимых путей идущих от корня. Давайте раскрасим их разными цветами, для наглядности
Корень дерева (основная программа) и подпрограмма I имеют отношение ко всем путям. Три независимых пути показаны синим, зеленым, желтым цветами. Подпрограммы в этих независимых путях никогда не вызывают друг друга. Все вызовы между этими путями проходят через общую часть всех путей. В данном случае, это подпрограмма I и основная программа.
Но это означает, что независимые пути могут занимать одну и ту же область памяти. Только не одновременно, а по очереди. Они могут перекрывать друг друга. Отсюда и сам термин - программа с перекрытиями. Общая часть (красный цвет) всегда будет располагаться в памяти. Пока вызовы идут в пределах одного пути, никаких дополнительных усилий не требуется. Если вызов, он обязательно будет идти от корня, коснется подпрограммы в другом пути, нам потребуется сначала как то разместить его в памяти, ранее занятой другим путем.
Давайте рассмотрим возможное распределение памяти программы
Область памяти выше подпрограммы I является разделяемой. Размер этой области определяется максимальным суммарным размером всех подпрограмм входящих в независимые пути. Если в этой области памяти располагаются подпрограммы более короткого пути, то часть памяти остается свободной, но использоваться для других целей не может.
Однако, имеет смысл строить дерево вызовов не на основе взаимосвязей подпрограмм, а группировать подпрограммы. Вот так, например
Фактически, мы перешли от подпрограмм к модулям, группам подпрограмм. И такой подход позволяет изменить возможное распределение памяти программы
Мы распространили подход к выделению путей в дереве вызовов на пути исходящие из узла, а не только из корня. Это позволило еще больше сократить объем требуемой программе памяти.
Построить дерево вызовов и создать на его основе карту распределения памяти модулей может компилятор. Во всяком случае, теоретически. Однако, компиляторы того времени оставляли составление дерева вызовов программисту. Но сами размещали подпрограммы среды времени выполнения в сформированном программистом дереве. И такое дерево уже называлось не деревом вызовов, а деревом перекрытий.
Давайте посмотрим, как могло выглядеть составленное программистом описание дерева.
Root-I-(A-D-E-(F,G),B-H,J-(K,L))
Возможно, это выглядит страшновато. Но на самом деле, все достаточно просто. В скобках, через запятую, перечисляются подпрограммы (модули), которые могут занимать одну и ту же область памяти. Через дефис (знак минус) перечисляются подпрограммы (модули), которые размещаются в памяти последовательно.
В нашем примере, подпрограммы F и G могут размещаться в одной области памяти, так как они не вызывают друг друга. И в описании дерева это записывается как (F,G). Аналогично и для подпрограмм K и L. Подпрограммы A, D и E не могут занимать одну область памяти и должны размещаться последовательно. Поэтому и запись выглядит как A-D-E.
Вы можете самостоятельно разобрать оставшуюся часть описания дерева и убедиться, что запись в точности соответствует структуре памяти.
Управление памятью программы с перекрытиями
Совершенно очевидно, что работа программы с перекрытиями требует дополнительных усилий для управления перекрывающимися областями памяти. Более того, и образ программы на внешнем носителе, например, диске, должен быть специально подготовлен.
Образ программы на диске должен включать в себя информацию о местоположении отдельных модулей перекрытий в файле образа, и размере этих модулей. Это необходимо для загрузки и перезагрузки модулей в память на отведенные им места, согласно описанному программистом дереву перекрытий.
А вот управление перекрытиями во время работы программы рассмотрим подробнее.
Как и для любой обычной программы, операционная система определяет необходимый объем памяти. Только для программы с перекрытиями этот объем будет определяться максимальным суммарным объемом памяти для пути самого большого объема, а не общим объемом все подпрограмм и модулей. И этот объем, как видно из иллюстраций, будет меньше, чем для той же задачи без перекрытий.
В выделенную таким образом программе область памяти загружается только корневой модуль (основная программа) и ему передается управление. На этом процесс запуска считается завершенным.
Когда из корневого модуля вызывается подпрограмма находящаяся в другом модуле, управление получает подсистема управления перекрытиями. Она включается в каждую программу с перекрытиями на этапах компиляции и компоновки. Подсистема управления перекрытиями проверяет, что модуль, который содержит эту подпрограмму, загружен в память. Если модуль загружен, управление передается вызываемой подпрограмме. Если модуль не загружен, то он загружается и управление передается вызываемой подпрограмме.
Подсистема управления перекрытиями ведет учет модулей и их состояний загружен/нет. Когда в область перекрытия (например, (F,G)) загружается новый модуль, другие модули в этой области помечаются как не загруженные.
Загрузка необходимого модуля осуществляется из образа программы на диске. Не правда ли, все очень похоже на сегменты кода с атрибутом discardable в всем известной Windows? Механизм действительно очень похож. С той лишь разницей, то управление перекрытиями выполняет не ОС.
А что с данными?
Да, мы немного поговорили о данных в начале статьи, а потом о них совсем забыли. Данные, речь идет о статических и глобальных переменных и константах, должны иметь время жизни и область видимости независящие от наличия или отсутствия перекрытий. Область видимости определяется компилятором. А вот время жизни можно обеспечить только с помощью размещения данных в корне.
Перекрытия использовались в задачах выполняющихся в ОС без виртуальной памяти, без файла подкачки. Поэтому возможности временно сохранить и восстановить данные просто не было. И область памяти глобальных и статических переменных просто размещалась в области памяти корневого модуля. Или в отдельном сегменте данных, который не участвует в работе перекрытий. Это же касается и области стека.
Заключение
Программы с перекрытиями ушли в прошлое. Но идеи, которые лежат в основе управления перекрытиями, остались с нами. Сегменты кода и констант, которые можно безболезненно отбросить и отдать занимаемую ими память для других целей, а потом просто восстановить их с диска из образа программы, это те самые перекрытия, их наследники. Только теперь они не связаны с деревом вызовов.
Вот такой небольшой исторический экскурс получился. Но имеющий и прямое отношение к дню сегодняшнему.
Приглашаю читателей посетить дружественный канал Робототехника.
