Идеей написания этой статьи автор обязан… посещению книжного рынка. Базар, он, как говорится, и в Африке базар — даже если на нем "торгуют" просвещением. На фоне необъятного количества ставших по очевидным причинам сверхпопулярными книг, обещающих или быстрое освоение методов скорого обогащения, или, на худой конец, мгновенное (и без затрат) "перенесение себя" в высокооплачиваемую категорию специалистов, совершенно не видно литературы серьезной. Допустим, еще можно поверить в эффективность издания с названием "Как стать умным за 24 часа", но вот обещанию азбучного изучения, например C++ за пять уроков (каждый по два часа), автор никогда не поверит (и читателям верить не советует). Такая ситуация неизбежно приводит к одному забавному явлению. Так, компьютерная терминология стала модной, но со значением отдельных, уже ставших общеупотребительными, понятий, почти никто не знаком… Один из таких "загадочных незнакомцев" — термин "виртуальная память".
История и предпосылки
В наши дни, когда "взлет" цен на модули ОЗУ на несколько десятков процентов расценивается как трагедия, трудно представить себе времена, когда десятки килобайт несоизмеримо более медленных вариантов RAM (память с произвольным доступом) стоили… десятки тысяч долларов. Компьютеров в те времена, естественно, было немного, и использовались они вовсе не для игр или покупок по Internet. На них считали, и успешному выполнению этой рутинной, тяжелой и неинтересной работы мы обязаны сегодняшним расцветом полупроводниковых технологий, авиации и машиностроения. Естественно, что расчеты расчетам рознь — для некоторых достаточно единиц ячеек памяти и мизерного быстродействия, но результаты таких "компьютерных" исследований мало кого интересуют — все это можно сделать вручную. А вот когда речь заходит о вещах куда более сложных, требующих (в идеале) компьютера с чуть ли не бесконечной памятью и высокой производительностью… как быть в этом случае? Программисты, севшие за компьютер в те времена, когда монстры семейств IBM 360/370 уже находились в полуразобранном состоянии, а рабочие столы стали украшаться разнообразными ПК, хорошо знакомы с одной крайне неприятной особенностью "операционных систем" класса MS-DOS: без использования дивных ухищрений "персоналки" не позволяли обрабатывать массивы данных, превышающие по размеру емкость оперативной памяти машины. Утилизация сравнительно высокой производительности ПК, особенно оснащенных математическими сопроцессорами, становилась задачей крайне непростой (что, к слову, позволило оттянуть казавшуюся тогда неминуемой гибель "больших" ЭВМ на неопределенный срок). Еще в худшем положении находились многозадачные и мультипользовательские системы — ведь в них проблема несоответствия объема физической оперативной памяти и сложности приложений возрастает пропорционально числу задач (пользователей). Еще в 1969 г. в журнале CACM вышла статья Панкруста (Pankhrust R. J), посвященная первому частному методу решения указанных проблем. Слово "оверлей" надолго заняло почетное место в лексиконе системных и прикладных программистов. Затем (в 1972 г.) в издательстве "McGraw-Hill" увидела свет книга Уотсона (Watson R. W.) "Концепции проектирования систем разделения времени", в которой были сформулированы основные постулаты многообещающих механизмов управления памятью, получивших название "виртуального хранилища". И наконец, в 1974 г. в журнале "IBM Systems Journal" появилась расставляющая точки над "i" публикация Вилера (Wheeler T. F.) о полностью "виртуальной" памяти компьютера с подробным описанием и анализом основных механизмов ее реализации. Казалось бы, что сегодня, когда 128 MB ОЗУ уже никого не удивляют на недорогом "десктопе", все эти сложности неинтересны… Но, как известно, аппетит приходит во время еды — и сравнительно небольшая программка, например оптимизации или вычисления сложных интегралов методом Монте-Карло, вполне способна за несколько десятков часов "жужжания" на пятисотмегагерцевом процессоре "выесть" пару гигабайтов жесткого диска. И при этом авторы программы понятия не имели о конкретном объеме памяти вашего компьютера и, не мудрствуя лукаво, считали доступной… чуть ли не всю адресуемую 32-разрядным процессором память, составляющую, без учета ограничений со стороны операционной системы, 4 GB.
Вначале были оверлеи
Вместе с ними была и головная боль… Оверлей — понятие совершенно примитивное, точнее, настолько примитивное, что даже не соответствует требованиям Эйнштейна к простоте ("Делайте все как можно проще, но не проще, чем возможно"). Отсюда и сложности их реального применения. Ответ на вопрос "что такое оверлей?" заключается в самом названии этого механизма: объединение двух английских слов "over" и "lay" означает (не дословно) "размещать поверх". Соответственно, оверлейная программа состояла из отдельных "кусков", которые загружались для выполнения в оперативную память по мере надобности. Реализация оверлеев не требовала дополнительных сложных аппаратных средств, но… Во-первых, оверлейное программирование — занятие, граничащее с искусством (это автор испытал "на собственной шкуре" в конце 80-х). Во-вторых, оверлеи облегчают программирование систем с объемом исполняемого кода, превышающего физическую емкость ОЗУ, но совершенно ничем не помогают в более распространенном случае, когда маленькая программа обрабатывает большой объем данных. В-третьих, оверлеи достаточно медленны. Ну и, наконец, в-четвертых: оверлеи и многопользовательская среда — понятия хотя и совместимые, но уж очень уродливые в реальности. Единственным красивым исключением в истории оверлеев является давно забытая уникальная система RDOS компании Data General (DG), основанная на идее так называемых виртуальных оверлеев. В ней каждый оверлейный фрагмент ("кусок") имел фиксированную длину (ровно 256 байтов, что соответствовало размеру сектора жесткого диска машин DG) и был реентерабельным. Как автору не хотелось избежать этого термина, без него все равно не обойтись: реентерабельной (или повторно входимой) программой называется любая подпрограмма, допускающая адресацию только находящихся в ней самой или в общесистемной области данных. Кроме реентерабельности, виртуальный оверлей от Data General обладал еще одной очень интересной особенностью: вызовы подпрограмм из других оверлейных "кусков" осуществлялись только через специальную общесистемную таблицу, всегда находящуюся в оперативной памяти. Такая интересная и простая организация программ позволяла организовать автоматическое (а не определяемое программистом, как в случае с классическими оверлейными фрагментами) и достаточно эффективное использование 256-байтовых "окон" в физическом ОЗУ. Несмотря на простоту реализации, идеи, заложенные в RDOS, кажутся очень симпатичными и сегодня, особенно для микропроцессоров и операционных систем, основанных на нетрадиционных принципах (например, для стековых машин FORTH или Java).
Виртуальность — штука реальная…
Оверлеи оверлеями, а растущие вычислительные потребности вынуждали разработчиков компьютерных архитектур искать решения, пусть не вдохновляющие простотой реализации, но дающие возможность использовать дорогие вычислители на все 100%. Это сегодня на своей рабочей машине (32 MB ОЗУ, операционная система FreeBSD) автор может смело запустить на выполнение примитивную, но забавную и поучительную программку и получить вразумительный результат (см. листинг).
Не знакомым с языком программирования C поясню, в чем вся прелесть: объем физической памяти машины составляет всего 32 MB, причем в этой памяти находятся и операционная система, и куча всяких-разных приложений, но… при необходимости обработать массив данных размером 50 MB (переменная MEM_SIZE) операция выделения памяти (calloc) не предъявляет никаких претензий к программе (или, Боже упаси, к работоспособности машины) — память действительно выделена и начинается с адреса 804b000 (в шестнадцатеричном формате). Теперь в нее можно писать данные, их можно читать и вообще делать все, что вздумается (главное — не забыть выполнить операцию ее "освобождения" командой free). Причем делается это одной единственной командой — без всяких там выкрутасов и сложностей. После мучительных ухищрений в "операционных системах" MS-DOS/DR-DOS (и именно потому они именуются автором как ОС в кавычках) все до невероятности просто… За такую простоту, естественно, приходится расплачиваться. Но "так ли страшен черт" — в этом нам и предстоит разобраться.
Собственно говоря, сущность виртуальной памяти заключается в одной-единственной дополнительной абстракции Логического Адресного Пространства (ЛАП). В отличие от своего физического аналога (лимитируемого емкостью установленной в вашем компьютере оперативной памяти), ЛАП дает в распоряжение каждой отдельной выполняющейся задаче ВСЕ (или почти все) адреса, к которым можно обратиться с помощью регистров процессора. Таким образом, для 32-разрядных процессоров обычными цифрами являются единицы гигабайтов, доступных каждой задаче. Естественно, что никакого противоречия с "законом сохранения всего" здесь не наблюдается: даже при виртуальной памяти получить возможность обрабатывать объемы данных, превышающие свободное место дешевых накопителей на жестких дисках, невозможно. Уже из этого предупреждения понятно, что виртуальную память можно представить некоторым программно-аппаратным механизмом, "увязывающим" дорогую и быструю оперативную и медленную, но дешевую "вторичную" память (например, 100 MHz SDRAM ОЗУ и IDE "винчестер") в нечто единое, с точки зрения программиста и программ, подчиняющееся порядку адресов ЛАП. Исходя из тех же соображений ясны и потенциальные проблемы реализаций виртуальной памяти: во-первых, быстродействие (объединение быстрого и медленного, как очевидно, высокой скорости не гарантирует); во-вторых, справедливость (в многозадачной системе с ограниченными ресурсами "отнимать и делить" эти самые ресурсы нетрудно, но когда участников столь увлекательного процесса несколько, или все-таки нужны хоть какие-нибудь законы, или система работать вообще не будет). Ну и, наконец, последнее наводящее соображение — раз уж процесс "отнимания и деления" неизбежен, значит, он должен поддерживаться (скажу даже так — обязан поддерживаться) эффективно реализованным принципом "разделяй и властвуй" (без его соблюдения рушились великие империи, а уж такая "мелочь", как виртуальная память, работать не будет изначально).
Ну вот, теперь пора приподнять занавес… На какой бы вычислительной машине вы не работали, независимо от операционной системы, механизм виртуальной памяти будет соответствовать приведенным выше особенностям, ограничениям и требованиям, а его реализацию практически всегда можно будет объяснить с помощью следующих понятий: виртуальный адрес, проектор адреса (mapper), блок и алгоритм замещения (replacement block и algorithm соответственно). Общий принцип безукоризненно прост: в соответствии с правилом "разделяй и властвуй" ЛАП является упорядоченным множеством маленьких блоков замещения, виртуальный адрес представляет собой номер блока замещения и "локальный адрес" в пределах этого блока (что позволяет точно определять положение любой "ячейки памяти" в ЛАП-пространстве), проектор адреса отвечает за установление соответствий между ЛАП-адресами и адресами реального ОЗУ для отдельных блоков замещения, а алгоритм замещения определяет набор правил, по которым выполняются операции удаления из дорогой и быстродействующей памяти "ненужных" блоков. В динамике все эти "ужасы" приобретают стройность и прозрачность. Предположим, что процессор обращается к данным, находящимся по виртуальному адресу V1 (рис. 1), который содержит (по определению) номер блока замещения N и адрес в этом блоке M. Проектор адресов, выполнив "отображение" (mapping), определяет, что блок замещения N находится в оперативной памяти и начинается с физического адреса F. В случае, если блок N не загружен в оперативную память (рис. 2), проектор адресов определяет местонахождение этого блока во вторичной памяти (например, на жестком диске), выявляет свободный фрагмент физического ОЗУ, начинающийся с адреса E, и записывает в этот фрагмент содержимое блока. Если же свободных фрагментов в физическом ОЗУ нет, mapper на основании алгоритма замещения выявляет фрагмент-кандидат на замещение (вот откуда взялось это название), сохраняет его содержимое во вторичной памяти и место переписывает (замещает его) содержимым блока N.
Если вы добрались до этих строк — поздравляю. Основы основ уже за плечами. Остается самое неприятное — нюансы, содержащие намного больше сложностей и подводных камней. Во-первых, если размер блока замещения в конкретной системе фиксирован и не изменяется в ходе работы системы, речь идет о так называемой страничной организации памяти. В противном случае (а он вполне возможен) и при существовании некоторого логического правила, выявляющего несколько типов блоков замещения в зависимости от их содержания (например, код программы и данные), организацию виртуальной памяти называют сегментной. Существуют и гибридные реализации, совмещающие страничную и сегментную организации (опять же на основании принципа "разделяй и властвуй", такое двойное разделение позволяет более гибко управлять физическими ресурсами компьютера), например, организация сегментов переменного размера как групп из разного числа страниц фиксированной длины. Страничность или сегментированность виртуальной памяти обычно реализуются программными способами и в большей степени являются свойствами операционной системы. В отличие от них проектор адресов (mapper) основывается на аппаратных средствах конкретного процессора, если таковые присутствуют: далеко не все процессоры оснащены MMU (Memory Management Unit — устройство управления памятью). Из предыдущего объяснения функции проектора адресов понятны, но вот как их реализовать, чтобы выполнение программы, содержащей только виртуальные адреса, не замедлялось до безобразия — ведь в таком случае каждое обращение по виртуальному адресу требует вмешательства со стороны mapper, а на это расходуется время. В полном соответствии с еще одним любимым автором принципом "не умножай сущности без необходимости" разработчики систем виртуальной памяти решили обойтись очень простыми структурами данных, обеспечивающими высокую скорость доступа, а точнее, таблицами. Работа mapper основывается на двух важнейших таблицах — страниц и карты диска. Первая обычно содержит несколько информационных полей, минимально обязательными из которых являются: признак нахождения страницы в физической памяти (R), признак использования страницы (U — осуществлялись ли операции чтения из этой страницы), признак модификации страницы (W — осуществлялись ли операции записи в страницу) и начальный адрес страницы в физическом ОЗУ. Карта диска хранит местоположение во вторичной памяти (на жестком диске, например) сохраненных в ней блоков замещения (страниц). Если при обращении к странице N проектор адресов определяет, что в строке с номером N таблицы страниц не установлен признак R, то он (проектор страниц) подает сигнал SOS операционной системе. Этот "вопль" mapper’а называется "сбоем страницы" (page fault) и обязует соответствующие модули ОС (или самого проектора страниц) осуществить операцию загрузки в память блока замещения N.
Теперь начинается самое интересное — а где и как разместить таблицы, столь необходимые для управления виртуальной памятью? Очевидный ответ — в регистрах процессора, ведь именно к ним возможен самый быстрый доступ в любом компьютере. Увы, очевидность этого факта никак не влияет на перспективность решений на его основе — регистры процессора вещь дорогая, намного дороже оперативной памяти. Их надо экономить. Значит, выход один: размещать таблицы в оперативной памяти и тем самым снижать производительность всего компьютера в целом в два (!) раза (почему так, судите сами: на каждое обращение по виртуальному адресу потребуется как минимум одно "лишнее" обращение к физическому ОЗУ — к таблице страниц). Принципиально избавиться от замедления, свойственного виртуальной памяти, ни в одном процессоре не удалось, но задача нахождения компромисса между производительностью и стоимостью давно и успешно решена с помощью так называемой ассоциативной памяти. В отличие от обычной RAM, в которой критерием самого быстрого поиска ячейки памяти является ее адрес, для ассоциативной памяти в его роли выступает… содержимое самой ячейки. Не вдаваясь в подробности реализации, массив ячеек ассоциативной памяти можно представить как множество параллельно работающих "машинок сравнения", сравнивающих содержимое каждой ячейки с предъявленным к поиску значением. Думаю, что доказывать сложность и дороговизну ассоциативной памяти после такого короткого знакомства не требуется… Но столь полезное свойство, как "реактивный поиск", вынудило разработчиков процессоров обязательно реализовывать в составе MMU пусть небольшой, но ассоциативный фрагмент таблицы страниц, предназначенный для ускорения выполнения программ. Отдельные элементы этого фрагмента — специальные регистры — обычно называют TLB (Translation Lookaside Buffers) и размещают в них записи о наиболее часто использующихся страницах. Естественно, что при такой организации механизма виртуальной памяти первый этап в работе mapper заключается в быстрой проверке TLB, и только в случае отрицательного результата этой операции в ход пускаются более медленные механизмы поиска в таблице страниц. Несмотря на кажущуюся неэффективность, TLB обеспечивают существенный прирост производительности, замедляя среднее время доступа к реальной памяти на считанные проценты. Оценка эффективности TLB зависит от многих факторов и архитектурных решений и определяется термином "отношение попаданий" (hit ratio). Например, у процессора Intel 80486 (всего 32 TLB в составе MMU) отношение попадания составляет 98%, что для модели DX50 (внутренняя и внешняя тактовые частоты одинаковы и составляют 50 MHz) гарантирует максимальное время доступа к ОЗУ с быстродействием 100 нс не более 122 нс — среднее замедление в системах на основе подобных процессоров за счет использования механизмов виртуальной памяти составляет 22%. Далеко не все типы CPU обладают столь ограниченным набором TLB, например, занявшие прочные позиции на рынке встраиваемых процессоров представители семейства MIPS могут быть оснащены куда более впечатляющим количеством TLB-регистров (даже недорогие модели производства IDT содержат в MMU более 90 TLB).
Естественно, что достаточно высокие показатели быстродействия могут быть реализованы только с помощью очень "умных" алгоритмов замещения. В целом, тема их совершенствования по сей день остается открытой, а каждое новое достижение в этой области становится явлением чуть ли не мирового масштаба. Формальных методов создания алгоритмов замещения не существует — слишком много частностей приходится учитывать их разработчикам, да и сама задача по определению является многокритериальной (а в этом случае не существует одного единственного "наилучшего" во всех смыслах решения). Интересно заметить, что даже маленький успех или красота построения алгоритма замещения могут зародить жизнь в громадных программных проектах (именно так было с Linux, начинавшейся с подсистемы управления памятью и процессами, разработанной Торвальдом). К хорошо известным и изученным алгоритмам замещения относятся FIFO (первыми из физической памяти замещаются страницы, которые первыми и были в нее записаны), LRU (первыми замещаются страницы, к которым давно не было обращений) и WS (замещаются страницы, к которым не было обращений за установленный интервал времени).
Память и многозадачность
Если уж такую реальную вещь, как виртуальную память, назвали "виртуальной", то употребление термина "многозадачность" без этого префикса можно считать непростительной оплошностью. Да и на самом деле, один процессор в один момент времени может выполнять всего одну команду (даже если это кристалл пост-x86 с внутренним распараллеливанием микрокоманд — все равно он выполняет одну-единственную команду x86). А уж быстрое переключение между задачами, создающее иллюзию непрерывного одновременного выполнения нескольких задач, иначе как виртуальной мультизадачностью не назовешь. Естественно, что эффективность реализации виртуальной памяти в мультизадачных системах — один из главных критериев качества всей компьютерной системы в целом. Разные стратегии управления виртуальной памятью, воплощенные в различных алгоритмах замещения, наглядно наблюдаются даже по поведению той или иной ОС, например при запуске новых задач: MS Windows "жадно урчит винчестером", экономная Linux стремится к минимизации процессов замещения, надежная и ориентированная на серверные приложения FreeBSD упорно добивается максимума свободной физической памяти (чтобы быстрее запустить еще один процесс в случае необходимости).