Попробуем сформулировать набор требований к аппаратуре управления памятью в Unix-системах.

Одно из первых требований звучит следующим образом: процессы в многопользовательской системе не должны портить память друг друга — кроме, конечно, «официально» разрешенных случаев - использование разделяемой памяти или выполнение процедуры отображения памяти. В операционной системе Unix потенциально возможно только одно нарушение данного принципа. Речь идет о системном вызове vfork, который мы обсудим попозже. Из первого требования непосредственно вытекает необходимость поддержки какого-либо механизма защиты памяти.

Зададимся вопросом, как одновременно в системе может существовать несколько копий одной и той же программы. При кажущейся очевидности ответа на этот вопрос в действительности все не так уж и просто. Попробуем, например, рассмотреть тривиальный фрагмент (естественно, не претендующий на какую-либо практическую ценность):

	int gmgm(void);
	int (*a)(void) = gmgm;
   static int u;
	main(int argc, char **argv)
	{
		int k = 2*2;
		u = atoi(argv[1]) + (*a)() + k;
		printf(«%d
», u);
	}

Видите ли вы в нем что-либо подозрительное? Если попробовать проверить данный код, возникает группа вопросов о том, как конкретно происходит обращение к разнотипным переменным, т.е. к a, k, argv, функции gmgm. Заметим, что инициализация глобальной переменной a должна произойти до начала выполнения программы. Попробуем представить запуск подобного рода процессов в системе реального времени. В подобных системах зачастую не тратятся на поддержку средств управления памятью (отдельный модуль стоит, как правило, не менее отдельные деньги).

Итак, каков же должен быть код данной программы, чтобы он мог корректно работать в системе без поддержки виртуальной памяти? Если мы не хотим, чтобы два различных процесса использовали бы одну и ту же переменную u (иначе мы не можем даже предсказать результат вычислений), то, конечно, они должны использовать различный адрес для данной переменной. Как этого можно добиться?

Используются два основных способа: динамическая настройка и базирование. В первом случае предполагается, что в момент старта программы происходит выделение места под ее переменные и настройка кода и данных на какие-то адреса. Для этого необходимо либо как минимум знать о том, как и какие адреса надо модифицировать (в операционной системе реального времени PDOS несколько лет назад это обнаружилось в виде битовой маски внутри программы), либо вообще хранить файл программы в перемещаемом формате, т.е. вместе с таблицей символов, такой вариант обеспечивает возможность динамического связывания с уже существующими в памяти программами. Такую возможность, например, обеспечивает ОС реального времени VxWorks.

Вариант с базированием выполняется несколько иначе: обращение к процедурам выполняется за счет относительной адресации; при старте программы выделяется место под ее глобальные данные и на это место начинает перманентно смотреть некоторый базовый регистр; далее данные инициализируются в соответствии с требованиями (заметим, что у нас в программе есть переменная a со значением зависящим от позиции кода, но также могло бы быть и значение, зависящее от позиции данных); все обращения к именованным данным происходят через смещение относительно базового регистра. Этот подход поддерживается, например, в OS/9 (OS/9000). Ясно, что работа с базированием потенциально увеличивает длину кода, но позволяет использовать память более эффективно, поскольку всегда можно пользоваться одной копией кода программы в памяти. В первом случае повторное использование кода подпрограмм превращается в определенные требования к разработчикам и самой системе (иначе придется «покупать» себе личную переменную errno). Кроме того, всякая программа, которая «варится» в памяти, должна иметь собственный стек, вообще говоря, весьма вместительных размеров, особенно если мы используем рекурсивные алгоритмы. Выделение пространства под стек превращается в отдельную головную боль... Впрочем, если у вас есть многонитевая программа, то появление этой проблемы возможно в любой системе.

Но о том ли я? Мы же, кажется, говорим о Unix. Там-то это зачем? В Unix обычно используется статическое связывание, однако, достаточно типично и использование динамического связывания. Например, работа с разделяемыми библиотеками может быть реализована по любой из схем, то есть со статическим и динамическим связыванием, но вариант с динамическим связыванием (а оно, как мы видим, тоже может быть различным) оказывается более гибким.

Хотим ли мы иметь головную боль? Нет, и именно поэтому для организации нормальной многозадачной работы хотелось бы использовать механизм виртуальной памяти. При этом код можно собирать статически, но каждый процесс будет иметь по одному и тому же виртуальному адресу (например, переменной u) различные значения. Следующей проблемой является стек. Он должен быть непрерывен в виртуальном пространстве и, возможно, разрывен в реальной памяти. Так мы переходим к понятию страницы. Если виртуальное пространство имеет право дробиться на кусочки (страницы), то можно достаточно безболезненно увеличивать его размер, добавляя свободные страницы из различных областей памяти.

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

Сформулированное подобным образом требование в действительности распадается на два требования к аппаратуре. Во-первых, необходимо как-то хранить в памяти информацию о доступности тех или иных страниц и адреса имеющиеся в памяти. Необходима быстродействующая таблица преобразования адресов с «дырками». С другой стороны и процессор, который, напомним, очень любит изменять порядок выполнения операций для увеличения производительности конвейера, должен суметь вовремя остановиться и в таком состоянии, что процесс можно будет перезапустить с текущей точки. Это же необходимо бывает и для отладки - проблема «точного останова» - желательно, чтобы все регистры выглядели так, как будто программа выполнялась последовательно.

Итак, мы добрались до таблицы адресов. Да и это страшное слово - «страница» — уже произнесено. Что же в нем страшного? Стоит вновь, как и в случае с файловой системой в одном из предыдущих номеров, задать вопрос: «Почем пирожок?» Предположим, что процесс у нас 32-разрядный, задание физического адреса тоже предположим достаточно экономным, те же 32 разряда на страницу, ну и размер страницы положим в 4 Кбайт. Мы хотели бы построить таблицу для всех страниц процесса. 4 Гбайт/4 Кбайт = 1 Мстраница. Итого надо 4 Мбайт памяти для полной адресации процесса - чересчур много, однако. Даже в предположении, что не все страницы находятся в памяти, эти 4 Мбайт надо иметь — просто часть из этих 4 Мбайт должна быть ссылками не на адреса в физической памяти, а на адреса страниц в файлах (код программы или часть данных) или области подкачки.

Вспомним теперь еще и о том, что сама операционная система выполняется в собственном адресном пространстве для каждого процесса (например, описатель текущего процесса, обычно именуемый U-AREA, находится по одному и тому же виртуальному адресу и обычно называется u - так системе удобнее). Значит, и для системы нужна память управления страницами? — Увы, увы, нужна. А для доступа к буферу видеоконтроллера нужна? - Нужна! Ясно, что большая часть отображения страниц для операционной системы будет прямой, и, в принципе, память для описания страниц может быть потрачена зря. Так, может быть, ее и не хранить? А вот это уже как повезет: все зависит от архитектуры процессора.

Теперь перейдем к самой аппаратуре трансляции адреса. Процесс перехода от виртуального адреса к физическому можно описать формально следующим образом:

виртуальный адрес -> контекстное расширение адреса -> поиск адреса в кэше транслятора адресов -> поиск адреса в таблицах памяти

Последний этап нужен только в том случае, если транслятор адреса (ATU, MMU, TLB или как его там в вашей системе называют) не может выполнить этой операции без обращения к памяти. Думаю, все этапы трансляции кроме второго очевидны. А второй-то зачем нужен? Что входит в этот контекст, и о каком таком расширении идет речь? Ясно, что виртуальное адресное пространство разных процессов не совпадает. В одном случае законный адрес указывает на один экземпляр переменной, а в другом на совершенно другой. В принципе, однако, можно рассматривать обобщенное адресное пространство, которое включает в себя адресные пространства всех остальных процессов во всех их состояниях (т.е. в «нормальном» пользовательском и системном режимах). В одних случаях данное построение почти полностью формально, в других все именно так и устроено (например, 32-разрядное адресное пространство процесса погружено в 64-разрядное адресное пространство системы). Что это дает и зачем это может быть нужно?

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

eee pppppp sssssss ttttttt oooooo,

где oooooo - смещение в пределах страницы;

tttttt - смещение в таблице страниц третьего уровня;

sssssss - смещение в таблице страниц второго уровня;

pppppp - смещение в таблице страниц первого уровня;

eee - расширение адреса для выбора таблицы.

В простейшем варианте eee может быть просто указанием системного/пользовательского режима работы. Иногда туда добавляется информация из сегментных или space-регистров, которые в свою очередь либо явно указываются в команде, либо получаются выделением старших разрядов адреса.

Соответственно сам адрес вычисляется многостадийно:

Найти адрес таблицы первого уровня: атаб1 = начало_таблиц[eee];

Найти адрес таблицы второго уровня: атаб2 = атаб1[pppppp];

Найти адрес таблицы второго уровня: атаб3 = атаб2[sssssss];

Найти адрес страницы: астр = атаб3[tttttt];

Получить адрес данных: аданн = астр + oooooo;

На любом из этапов может выясниться, что выполнить преобразование невозможно, поскольку не только страницы, но и самой таблицы нет в памяти. В этом случае выполнение программы приостанавливается, процессор вмешивается в этот процесс, подкачивает страницу и генерирует таблицы всех уровней для доступа к данной странице и снова стартует программу. И это для каждого адреса? Это был бы явный перебор. После каждого полного преобразования виртуального адреса делается попытка запомнить его физический адрес в кэш-памяти (иногда имеется два кэша, соответственно для команд и данных). Точнее, конечно, не весь адрес, а только адрес страницы. Соответственно в кэш-памяти должна появится запись вида: расширенный виртуальный адрес - физический адрес и характеристики страницы. Иногда данная схема модифицируется, например, по расширенному адресу генерируется кэш-значение в виде смещения в таблице, далее проверяется, что данный элемент является ссылкой на требуемую страницу, далее обращение по списку - жизнь бывает достаточно нетривиальной.

Второй вариант предполагает, что каждый раз, когда транслятор не может выполнить преобразование адреса, выполнение программы приостанавливается, и процессор загружает кэш адресов. Это может показаться накладным, однако, когда мы говорим не о 32-разрядной, а о 64-разрядной адресации (размер таблиц можете посчитать сами), то любое чисто аппаратное решение может быть и не очень-то эффективным. Кроме этого, оказывается, отказ от аппаратных решений происходит из-за непредсказуемости времени работы, что может быть неприятно для систем, например, реального времени. Кроме того, при использовании аппаратной загрузки кэша адреса, необходимо, чтобы таблица адресов страниц в памяти имела «аппаратный» вид, но у системы-то есть и собственные структуры, которые ей необходимы для управления страницами, в принципе может потребоваться дублирование части информации для системных нужд - придется все умножить на два.

Перейдем теперь к структуре самой кэш-памяти. Кэш - штука ассоциативная, получение данных делается не по адресу, а по содержимому (хотя в качестве содержимого и выступает «расширенный виртуальный адрес»). К сожалению, память подобного рода с работой на достаточной скорости обычно достаточно мала - формально каждая ячейка такой памяти должна иметь собственный компаратор для того, чтобы все ячейки могли одновременно сравнить свой адрес с тем, который приходит извне. Обычно кэш транслятора адресов вмещает сотню-другую позиций, соответственно позволяет адресовать (при размере страницы, например, 4 Кбайт) в пределах 0,5-1 Мбайт памяти без перезагрузки. Учитывая требуемый для некоторых программ размер памяти, ясно, что перезагрузок, которые, конечно, не улучшают ситуацию с производительностью, не избежать. Что делать? Один из подходов ясен - увеличение размера страниц. Ясно, что такое увеличение может ухудшить использование памяти за счет страничной и внутристраничной фрагментации памяти. С другой стороны, без этого не обойтись (соответственно уменьшаются и размеры всех таблиц). Еще один возможный подход состоит в использовании страниц различного размера (желательный размер, например, может назначаться с точностью до приложения и типа: код/данные) - это не очень сложное изменение с точки зрения аппаратуры, но, конечно, несколько усложняет процедуры выделения памяти в операционной системе.

Что бы еще можно было бы сделать для улучшения работы механизма трансляции адреса, в частности, уменьшения перезагрузок кэш-памяти и уменьшения требуемой памяти для описания страниц? Для того чтобы рассказать о таких механизмах, нам потребуется ввести следующее понятие - область (region). Любая Unix-программа разбита на несколько однородных частей - ее код, данные, неинициализированные данные, стек, разделяемая память, разделяемые библиотеки (тоже, соответственно, код, данные, неинициализированные данные) и т.п. Обычно каждая из этих областей начинается с границы страницы, и все страницы одной области имеют общие характеристики. Например, код программы можно читать и выполнять, но нельзя писать. Страницы данных можно и читать, и писать, и, обычно, выполнять. В общем случае нехорошо, если программа имеет больше прав на страницу, чем следовало бы. Например, стандартный способ получения привилегий через переполнение буферов обычно использует тот факт, что пользователь может выполнять код, который лежит в стеке. Соответственно, если буфер лежит в стеке, то, переполнив его, можно подменить адрес возврата из подпрограммы на адрес записанного в стек кода. Если отказаться от режима «executable stack» (что в некоторых системах задается конфигурационным параметром), то в этом случае мы просто получим некорректную работу программы без выполнения загруженного кода - хотя это не очень улучшает положение: адрес-то мы подменить можем и вредный код в программе может найтись и без стека. Посмотрите еще раз как в Linux-е обрабатывается выход из обработчика сигналов см. номер 9-10 «Открытых систем» за прошлый год, там явно используется стек. Итак, мы нашли первый ряд характеристик, которые мы хотели бы приписать страницам и соответственно хранить не только в памяти, но и в момент выполнения в кэше транслятора адреса - разрешение на чтение, запись, выполнение.

Что дает метод деления пространства процесса на области? Во-первых, появляется возможность попытаться использовать общие структуры для описания разделяемых страниц, соответственно для кода программы (в системе, например, всегда присутствует много экземпляров командного интерпретатора), разделяемой памяти и кода разделяемых библиотек. ОК. Так мы добиваемся уменьшения затрат на некоторые таблицы операционной системы.

Реально, конечно, вычисления со страницами надо проводить для суммы страниц областей. Как правило, для того чтобы защитится от появления одиозных программ в системе, размеры всех областей в системе ограничены некоторыми конфигурационными параметрами. Например, не более 4 Мбайт на стек, не более 16 Мбайт на одну разделяемую область и не более 4 таких областей на процесс.

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

Как необходимо переключать контекст между процессами, или, другими словами, переходить от выполнения кода одного процесса к коду другого? Часть процесса переключения контекста очевидна - необходимо сохранить регистры текущего процесса и восстановить регистры другого. Очевидно, что также надо переключить и механизм трансляции адреса. Возможны следующие пути: устанавливаем новое значение для того регистра, который отвечает за доступ к таблице первого уровня транслятора адреса в памяти; подмена значений в соответствующей таблице какого-нибудь уровня; честное заполнение кэш-памяти; изменение сегментных/space-регистров, если таковые имеются. Любой нормальный процессор в первом случае должен немедленно выбросить из кэша транслятора адреса все записи имеющие отношение к соответствующей таблице - экономия почти исключена. Во втором случае мы предполагаем, что часть адресного пространства совпадает с предыдущим процессом (в некоторых вариантах Unix код операционной системы тоже лежит в адресном пространстве процесса, благодаря чему соответствующие элементы можно не менять), а часть должна быть подменена. После внесения соответствующих изменений в таблицах памяти мы должны «объяснить» транслятору адреса, что определенные диапазоны адресов в нем могут быть некорректны и, если он имеет соответствующие страницы, то должен от них избавиться. В этом случае мы предполагаем, что внесение соответствующих изменений в памяти не должно быть слишком обременительным. Для этого желательно, чтобы деление на области проходило по высшим уровням таблиц преобразования адреса. Вариант с полной или частичной перезагрузкой кэш-памяти и так ясен. На самом деле это выполняется одной командой «объявить область кэша некоректной». Наиболее интересен последний вариант. Предположим, что каждая из областей в памяти описывается собственным space-регистром, который автоматически добавляется к виртуальному адресу (как часть контекстного расширения) и, конечно, тоже хранится в кэше транслятора. В этом случае возможно совершено удивительное явление - при переключении процессов вообще не надо перегружать кэш транслятора адреса (тут я, конечно, слегка утрирую), все, что нам надо сделать заключается в перезагрузке space-регистров, которых, естественно, намного меньше, чем объем кэша транслятора. Если окажется, что два последовательных процесса имеют хотя бы одну общую область, то, возможно, запись в трансляторе адреса одного процесса доживет до момента, когда она потребуется другому. Соответственно, если, например, следующий процесс имеет такой же код программы, как и предыдущий, то значение в регистре этой области будет одинаковым, если нет, то разным.

Реально мы пользуемся в последнем случае тем фактом, что «глобальное виртуальное пространство» системы полностью накрывает все области всех процессов. Это, конечно, влечет и дополнительные накладные расходы. Мы обязаны предусмотреть защиту системы и областей, которые не принадлежат конкретному процессу от его посягательств, это обеспечивается приписыванием каждой области еще и кода защиты. Таков приблизительно механизм работы транслятора адреса микропроцессора PA-RISC.

Уф! Это все, что нужно нам от аппаратуры? Увы, нет. Есть еще один момент, который должна отслеживать аппаратура. Вспоминаем следующее слово - пейджинг (paging) - механизм замены долго неиспользуемых страниц в памяти. Что нужно для поддержки этого процесса? Здесь нам необходимо иметь две возможности: отметить факт обращения к данной странице - это необходимо для того, чтобы объявить данную страницу «используемой недавно»; отметить, что в данную страницу была выполнена запись и, соответственно, данная страница отличается от своей копии, которая, возможно, была на диске в области подкачки или файле. Последний факт необходим для того чтобы принять решение при освобождении памяти, если есть копия на диске, то страницу можно немедленно использовать под другие нужды (естественно, транслятор адреса не должен больше ее находить по старому адресу), если нет, то сначала страницу надо сбросить. Заметим, что здесь мы должны для каждой страницы знать не один адрес (физический), а два - позиция в памяти и позиция предыдущей копии на диске. Вы готовы умножать размеры соответствующих таблиц на два? Не спешите. Два адреса могут быть только у тех страниц, которые есть в памяти. Соответственно для отслеживания этого достаточно статической таблицы с размером пропорциональным размеру памяти. Итак, нам хотелось бы чтобы рядом со страницей появилось бы еще два признака - признак обращения и признак записи. Если вся работа с кэшем транслятора выполняется аппаратно, то и сброс данной информации в память тоже должен выполняться аппаратно (единственный случай, когда транслятор должен не прочитать, а записать в память). В принципе можно обойтись без этих признаков в кэше. Но это приведет к ухудшению производительности. Реально можно периодически (например, это может делать процесс vhand - управление обменом страниц), исключать часть страниц из кэша транслятора (для проверки их необходимости) или устанавливать запрещение на запись (для проверки «замусоривания»). Если страницу соответственно пришлось вернуть в кэш, то она нужна, если пришлось разрешить запись, то она замусорена и должна быть скинута на диск.

Последний механизм позволяет использовать еще один полезный механизм в Unix. Должны ли мы немедленно после выполнения fork выполнять копирование области данных для «сына». Формально они должны иметь каждый собственную копию данных, стека и т.п., но общую копию кода. Это что же копировать мегабайты данных - это же удавиться можно (желающие могут вспомнить, что часть страниц «папаши» находятся на диске, где, возможно, лежат и таблицы размещения их - копируйте на здоровье). Основной принцип Unix в данной ситуации очень прост: скорее всего, не надо делать ничего из того, что запланировано на сегодня, этого скорее всего не потребуется и завтра, и, может быть, не потребуется делать никогда.

Как же поступить? Очень просто. Действует, например, алгоритм «copy on write». Для сына копируются только верхние этажи структуры, которые участвуют в описании адресного пространства процесса папаши и все страницы данных папаши объявляются защищенными от записи (для внесения соответствующих изменений в кэш транслятора адреса, возможно, придется пожертвовать уже внесенными туда данными страниц соответствующих диапазонов - это дешевле переброса данных и обычно выбрасование одного диапазона делается одной командой). До тех пор пока и папаша, и сын пользуются одной страницей для чтения у системы нет необходимости выполненять дополнительные действия. Только в том случае, когда произошла попытка записи, мы делаем копию страницы (и вышележащих управляющих структур). Одну копию страницы получает папаша, другую сын (реально, конечно, папаши/сыны, т.к. количество ссылок на страницу может быть больше двух) и, конечно, правом на запись для требующего этого процесса.

Реально, конечно, страницы имеют больше признаков. Это может быть связано с некоторыми другими архитектурными особенностями. Например, с механизмом выполнения системных вызовов. Существуют два основных варианта реализации: выполнение специальных команд, которые прерывают выполнение программы и (в плане конвейера и т.п.) ничуть не лучше внешнего прерывания или обработки деления на ноль; передача управления командами аналогичными переходу. Во втором случае предполагается, что вы обязаны передать управление в одно из строго определенных мест (gateway), действуя по строго определенным правилам (дабы не было «вне игры»). Только если все было корректно выполнено (реально бывает 2-3 «лишние» команды), то дальнейший код выполняется с другим уровнем привилегий и соответственно может напрямую работать со структурами операционной системы. Фактически некоторые вызовы (например, getpid) получаются в этом случае (но не в первом) достаточно «легковесными» - не намного сложнее, чем обычный C-вызов. Если возвратиться к вопросам управления кэшем транслятора, то права доступа можно установить в виде функции от привилегий, тогда переход в режим системы тоже не требует перезагрузки транслятора.

Реальная картинка с управлением памятью не всегда однородная. Например, рядом с «нормальным» страничным преобразователем адреса может быть еще и блочный (для кода ОС, видеобуферов и т.п.).

В операционных системах, даже если не используется механизм виртуальной памяти в своем классическом стиле (с переопределением адресов), часто используется страничный механизм просто для задания характеристик страниц. Например, системы реального времени могут защищать процессы/нити друг от друга, объявлять, что данная область памяти не кэшируется (например, если она содержит регистры устройств), для данной области запрещено изменение порядка записи - отключение оптимизации (процессорный аналог volatile для области ввода/вывода или для синхронизации каких-либо процессов), для данной области использовать другой порядок байт (дабы MSB-процессор, например, нормально работал с PCI и т.п.), (MSB - most significant byte first).

А это все? Нет. Но это уже другая история. Дополнительные требования могут появлятся в многопроцессорных архитектурах, при наличии «интеллектуального» ввода-вывода и т.п.

И как только Unix со всем этим разбирается? Об этом мы поговорим в следующий раз.

Свои вопросы вы можете направлять по электронной почты по адресу oblakov@bigfoot.com