Глава 5. Сегментная и страничная виртуальная память 5.0 Начало Главы

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


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


     Такая адресация реализуется аппаратно. Процессор имеет специальное устройство, называемое диспетчером памяти или, как его называли в старой русскоязычной литературе, УУП (Устройство Управления Памятью, ср. MMU - Memory Management Unit). В некоторых процессорах, например в MC68020 или MC68030 или в некоторых RISC-системах, это устройство реализовано на отдельном кристалле; в других, таких как х86 или современные RISC-процессоры, диспетчер памяти интегрирован в процессор.
     В PDP-11 сегментов всего восемь, поэтому дескрипторы каждого из них размещаются в отдельном регистре (на самом деле, регистров не восемь, а шестнадцать - восемь для пользовательского адресного пространства и восемь для системного). На 32-разрядных машинах количество сегментов измеряется тысячами, а страниц - иногда и миллионами, поэтому приходится прибегать к более сложной схеме.
     Диспетчер памяти содержит регистр - указатель на таблицу трансляции. Эта таблица размещается где-то в ОЗУ. Ее элементами являются дескрипторы каждой страницы/сегмента. Такой дескриптор содержит права доступа к странице, признак присутствия этой страницы в памяти и физический адрес страницы/сегмента. Для сегментов в дескрипторе также хранится его длина.
     Большинство реальных программ используют далеко не все адресное пространство процессора, соответственно таблица трансляции не обязательно содержит все допустимые дескрипторы. Поэтому практически все диспетчеры памяти имеют еще один регистр - ограничитель длины таблицы трансляции. Страницы или сегменты, селектор которых превосходит ограничитель, не входят в виртуальное адресное пространство процесса.
     Как правило, диспетчер памяти имеет также кэш (cache) дескрипторов - быструю память с ассоциативным доступом. В этой памяти хранятся дескрипторы часто используемых страниц. Алгоритм доступа к памяти по виртуальному адресу page:offset состоит из следующих шагов (рис. 5.3).


     Видно, что такая схема адресации довольно сложна. Однако в современных процессорах все это реализовано аппаратно и, благодаря кэшу дескрипторов и другим ухищрениям, скорость доступа к памяти получается почти такой же, как и при прямой адресации. Кроме того, эта схема имеет неоценимые преимущества при реализации многозадачных ОС.
     Во-первых, мы можем связать с каждой задачей свою таблицу трансляции, а значит и свое виртуальное адресное пространство. Благодаря этому даже в многозадачных ОС мы можем пользоваться абсолютным загрузчиком. Кроме того, программы оказываются изолированными друг от друга, и мы можем обеспечить их безопасность.
     Во-вторых, мы можем сбрасывать на диск редко используемые области виртуальной памяти программ - не всю программу целиком, а только ее часть. В отличие от оверлейных загрузчиков, программа при этом вообще не обязана знать, какая ее часть будет сброшена.
     Другое дело, что в системах реального времени программе может быть нужно, чтобы определенные ее части никогда не сбрасывались на диск. Система реального времени обязана гарантировать время реакции, и это гарантированное время обычно намного меньше времени доступа к диску. Код, обрабатывающий событие, и используемые при этом данные должны быть всегда в памяти.
     В-третьих, программа не обязана занимать непрерывную область физической памяти. При этом она вполне может видеть непрерывное виртуальное адресное пространство. Это резко упрощает борьбу с фрагментацией памяти, а в системах со страничной адресацией проблема внешней фрагментации физической памяти вообще снимается.
     В большинстве систем со страничным диспетчером свободная память от-слеживается при помощи битовой маски физических страниц. В этой маске свободной странице соответствует 1, а занятой - 0. Если кому-то нужна страница, система просто ищет в этой маске установленный бит. В результате виртуальное пространство программы может оказаться отображено на физические адреса очень причудливым образом, но это никого не волнует - скорость доступа ко всем страницам одинакова (рис. 5.4).


     В-четвертых, система может обеспечивать не только защиту программ друг от друга, но в определенной мере и защиту программы от самой себя - например, от ошибочной записи данных на место кода или попытки исполнить данные.
     В-пятых, разные задачи могут использовать общие области памяти для взаимодействия или, скажем, просто для того, чтобы работать с одной копией библиотеки подпрограмм.
     Перечисленные преимущества настолько серьезны, что считается невоз-можным реализовать многозадачную систему общего назначения, такую как UNIX или System/390 на машинах без диспетчера памяти.
     Для систем реального времени, впрочем, виртуальная память оказывается скорее вредна, чем бесполезна: наличие диспетчера памяти увеличивает объем контекста процесса (это понятие подробнее обсуждается в разд. 8.2), воспользоваться же главным преимуществом - возможностью страничного обмена - задачи реального времени в полной мере не могут. Поэтому такие системы, даже работающие на процессорах со встроенным диспетчером памяти, часто этот диспетчер не используют. Даже если виртуальная память и доступна, система РВ (реального времени) обязана предоставлять средства блокировки кода и данных (не обязательно всех) пользовательского процесса в физической памяти.
     Отдельной проблемой при разработке системы со страничной или сегмент-ной адресацией является выбор размера страницы или максимального размера сегмента. Этот размер определяется шириной соответствующего битового поля адреса и поэтому должен быть степенью двойки.
     С одной стороны, страницы не должны быть слишком большими, так как это может привести к внутренней фрагментации и перекачке слишком больших объемов данных при сбросе страниц на диск. С другой стороны, страницы не должны быть слишком маленькими, так как это приведет к чрезмерному увеличению таблиц трансляции, требуемого объема кэша дескрипторов и т. д.
     В реальных системах размер страницы меняется от 512 байт у машин семей-ства VAX до нескольких килобайт. Например, х86 имеет страницу размером 4 Кбайт. Некоторые диспетчеры памяти, например у МС6801/2/30, имеют переменный размер страницы - система при запуске программирует диспетчер и устанавливает, помимо прочего, этот размер, и дальше работает со страницами выбранного размера. У процессора i860 размер страницы переключается между 4 Кбайтами и 4 Мбайтами.
     С сегментными диспетчерами памяти ситуация сложнее. С одной стороны, хочется, чтобы один программный модуль помещался в сегмент, поэтому сегменты обычно делают большими, от 32 Кбайт и более. С другой стороны, хочется, чтобы в адресном пространстве можно было сделать много сегментов. Кроме того, может возникнуть проблема: как быть с большими неразделимыми объектами, например хэш-таблицами компиляторов, под которые часто выделяются сотни килобайт.
     В результате ряд машин предоставляет двухступенчатую виртуальную память - сегментную адресацию, в которой каждый сегмент, в свою очередь, разбит на страницы. Это дает ряд мелких преимуществ, например, позволяет давать права доступа сегментам, а подкачку с диска осуществлять постранично. Таким образом, организована виртуальная память в IBM System 370 и ряде других больших компьютеров, а также в х86. Правда, в последнем виртуальная память используется несколько странным образом.

Адресное пространство x86

Вернуться наверх

5.1 Сегменты, страницы и системные вызовы

О, порождение Земли и Тьмы, мы приказываем
тебе отречься... - твердым, повелительным
тоном начал Гальдер.
Смерть кивнул.
- ДА, ДА. ЗНАЮ Я ВСЕ ЭТО. ВЫЗЫВАЛИ-
ТО ЧЕГО?
Т. Пратчетт

     Реализовав страничную или сегментную виртуальную память, мы сталкиваемся с той же проблемой, о которой шла речь в разд. 4.5: пользовательские программы не имеют доступа к адресным пространствам друг друга и к таблице дескрипторов, но ведь им надо иметь возможность вызывать системные сервисы и передавать им параметры!
     Один из основных способов решения этой проблемы сродни методу, применяемому в системах с базовой адресацией: вводятся два режима работы процессора, "системный" и "пользовательский", в которых используются разные таблицы дескрипторов. Переключение из пользовательского режима в системный осуществляется специальной командой, которая вызывает определенную процедуру в системном адресном пространстве.
     Известную сложность при этом представляет передача параметров: как отмечалось выше, пользовательское адресное пространство может быть отображено на физические адреса весьма причудливым образом. Для разрешения указателя в этом адресном пространстве нам либо необходимо анализировать пользовательскую таблицу дескрипторов вручную, либо каким-то способом временно переключить диспетчер памяти на использование этой таблицы.
     Большинство процессоров с диспетчером памяти предоставляют команды копирования данных из пользовательского адресного пространства в системное и обратно. Конечно же, доступны эти команды только из системного режима.
     Некоторые архитектуры предоставляют и более изощренные способы реализации системных вызовов и передачи управления между системой и прикладной программой.
     
Виртуальная память и режимы процессора VAX
     
Уровни доступа 80286
     Многоуровневый доступ, основанный на концепции колец, не имеет принципиальных преимуществ по сравнению с двумя уровнями привилегий. Как и в двухуровневой системе, пользовательские модули вынуждены полностью доверять привилегированным, привилегированные же модули не могут защититься даже от ошибок в собственном коде. Самое лучшее, что может сделать Windows XP, обнаружив попытку обращения к недопустимому адресу в режиме ядра, - это нарисовать на синем экране дамп регистров процессора. В OS/2, фатальная ошибка в привилегированных модулях, исполняемых во втором кольце защиты, не обязательно приводит к остановке ядра, но подсистема, в которой произошла ошибка, оказывается неработоспособна. Если испорчен пользовательский интерфейс или сетевая подсистема, система в целом становится бесполезной и нуждается в перезагрузке.
     Кроме того, разделение адресных пространств создает сложности при разделении кода и данных между процессами: разделяемые объекты могут оказаться отображены в разных процессах на разные адреса, поэтому в таких объектах нельзя хранить указатели (подробнее см. разд. 5.4). Стремление обойти эти трудности и создать систему, в которой сочетались бы преимущества как единого (легкость и естественность межпроцессного взаимодействия), так и раздельных (защита процессов друг от друга) адресных пространств, многие годы занимало умы разработчиков аппаратных архитектур.
     Например, машины фирмы Burroughs предоставляли пользователю и системе единое адресное пространство, разбитое на сегменты (единую таблицу дескрипторов сегментов). При этом возникает вопрос: если все задачи используют одну таблицу, как может получиться, что разные задачи имеют разные права на один и тот же сегмент?
     Решение этого вопроса состоит в том, что права доступа кодируются не дескриптором, а селектором сегмента. Таким образом, разные права доступа на один сегмент - это, строго говоря, разные адреса. Понятно, что такое разделение работает лишь постольку, поскольку пользовательская программа не может формировать произвольные селекторы. В компьютерах Burroughs это достигалось теговой архитектурой: каждое слово памяти снабжалось дополнительными битами, тегом (tag), который определял тип данных, хранимых в этом слове, и допустимые над ним операции. Битовые операции над указателями не допускались. Благодаря этому задача не могла сформировать не только произвольные права доступа, но и вообще произвольный указатель.
     Аналогичным образом реализована защита памяти в AS/400 [redbooks.ibm.com sg242222.pdf]. Пользовательские программы имеют общее адресное пространство. Первоначально это общее пространство имен, в процессе же преобразования имени в адрес бинарное представление селектора сегмента снабжается и битами доступа, которые затем обрабатываются точно так же, как в машинах Burroughs, и точно так же недоступны пользовательскому коду для модификации.
     Реализации языка С для этой архитектуры допускают использование указателей только в пределах одного сегмента кода или данных, но не позволяют формировать средствами С произвольные селекторы сегментов, остальные же языки, используемые на этой платформе (Cobol, RPG, языки хранимых процедур СУБД) вообще не имеют указателя как понятия.
     Еще дальше в том же направлении продвинулись разработчики фирмы Intel, создавая экспериментальный микропроцессор iАРХ432, описанный в следующем разделе.

Вернуться наверх

5.2. Взаимно недоверяющие подсистемы

- Вы куда?
- У меня там портфель!
- Я нам его принесу!
- Я вам не доверяю. У меня там ценный веник.
("Ирония судьбы или С легким паром!")
Г. Горин

     С точки зрения безопасности, основной проблемой систем с кольцами защиты является неспособность таких систем защитить себя от ошибок в модулях, исполняющихся в высшем кольце зашиты. В свете этого, очень привлекательной концепцией представляется идея взаимно недоверяющих подсистем.
     Согласно этой концепции, пользовательская задача не должна предоставлять системе доступа ко всем своим данным. Вместо этого задача должна выдавать мандат на доступ к буферу или нескольким буферам, предназначенным для обмена данными. Все акты обмена данными как между пользовательской задачей и системой, так и между двумя пользовательскими задачами или двумя модулями системы, также осуществляются при помощи передачи мандатов.
     Например, при исполнении системного вызова int read(int file, void * buf, size_t size) программа должна передать системе мандат на право записи в буфер buf размером size байт (рис. 5.11). При этом буфер будет ото-бражен в адресное пространство подсистемы ввода/вывода, но эта подсистема не получит права записи в остальное адресное пространство нашей задачи. Впрочем, этот подход имеет две очевидные проблемы.


     Первая проблема является чисто технической - она приводит лишь к тому, что мы можем построить такую систему только на основе сегментного УУП, в котором размер сегмента задается с точностью до байта или хотя бы до слова. Сегментированная память страдает от внешней фрагментации, но иногда такую цену стоит заплатить за повышение надежности.
     Функции модуля, управляющего выдачей мандатов, оказываются слишком сложны для аппаратной и даже микропрограммной реализации. Этот модуль должен выполнять следующие функции.
     Но еще больше проблем создает операция уничтожения мандата. Легко показать необходимость уничтожения мандата той же задачей, которая его создала.
     В свете этого возможность для задачи, выдавшей мандат, в одностороннем порядке прекращать его действие представляется жизненно необходимой. Отказ от этой возможности или ее ограничение приводит к тому, что задача, выдающая мандат, вынуждена доверять тем задачам, которым мандат был передан, т. е. можно не городить огород и вернуться к обычной двухуровневой или многоуровневой системе колец защиты.
     Для прекращения действия мандата мы должны отыскать в нашей общесистемной базе данных все ссылки на интересующий нас объект и объявить их недействительными. При этом мы должны принять во внимание возможности многократной передачи мандата и повторной выдачи мандатов на отдельные части объекта. Аналогичную задачу нужно решать при перемещении объектов в памяти во время дефрагментации, сбросе на диск и поиске жертвы (см, разд. 5.5.1) для такого сброса.
     Структура этой базы данных представляется нам совершенно непонятной, потому что она должна отвечать следующим требованиям.
     Последнее требование непосредственно не следует из концепции взаимно недоверяющих подсистем, но диктуется простым здравым смыслом. Если мы и смиримся с двух- или более кратным увеличением потребностей в памяти, оправдывая его повышением надежности, нельзя забывать, что даже простой просмотр многомегабайтовых таблиц не может быть быстрым.
     В системах, использующих страничные диспетчеры памяти, решить эти проблемы намного проще, потому что минимальным квантом разделения памяти является страница размером несколько килобайтов. Благодаря этому мы смело можем связать с каждым разделяемым квантом несколько десятков байтов данных, обеспечивающих выполнение первых двух требований.
     Если же минимальным квантом является байт или слово памяти, наши структуры данных окажутся во много раз больше распределяемой памяти.
     Автор оставляет читателю возможность попробовать самостоятельно разработать соответствующую структуру данных. В качестве более сложного упражнения можно рекомендовать записать алгоритм работы с такой базой данных на псевдокоде, учитывая, что мы хотели бы иметь возможность реализовать этот алгоритм аппаратно или, по крайней мере, микропрограммно.
     Дополнительным стимулом для читателя, решившего взяться за эту задачу, может служить тот факт, что разработчики фирмы Intel не смогли найти удовлетворительного решения.

Архитектура i432

Вернуться наверх

5.3. Сегменты, страницы и системные вызовы (продолжение)

     Аппаратные схемы тонкого разделения доступа к адресному пространству не имели большого успеха не только из-за высоких накладных расходов, но и из-за того, что решали не совсем ту проблему, которая реально важна. Для повышения надежности системы в целом важно не обнаружение ошибок и даже не их локализация с точностью до модуля сама по себе, а возможность восстановления после их возникновения.
     Самые распространенные фатальные ошибки в программах - это ошибки работы с указателями и выход индекса за границы массива (в наш сетевой век ошибки второго типа более известны как "срыв буфера"). Эти ошибки не только часто встречаются, но и очень опасны, потому что восстановление после них практически невозможно.
     Ошибки работы с указателями еще можно попытаться устранить, искоренив само понятие указателя. Примерно этой логикой продиктован запрет на формирование указателей в машинах Burroughs, именно из этих соображений в Java и некоторых других интерпретируемых языках указателей вообще нет.
     Однако искоренить понятие индексируемого массива уже не так легко. А ошибки индексации присущи всем компилируемым языкам, начиная с Fortran и Algol 60. Вставка проверок на границы индекса перед каждой выборкой элемента массива создает накладные расходы, но тоже не решает проблемы: ошибка все равно обнаруживается не в момент совершения (в тот момент, когда мы вычислили неверный индекс), а позже, когда мы попытались его использовать. В момент индексации обычно уже невозможно понять, какой же элемент массива имелся в виду. Программе остается только нарисовать на экране какое-нибудь прощальное сообщение вроде "Unhandled Java Exception", и мирно завершить свой земной путь.
     Понятно, что реакция пользователя на подобное сообщение будет ничуть не более адекватной, чем на хрестоматийное "Ваша программа выполнила недопустимую операцию - General Protection Fault" (впрочем, кто знает, может быть, такая реакция и является самой адекватной?).
     Прогресс в решении этой проблемы лежит уже в сфере совершенствования технологий программирования, и вряд ли может быть обеспечен усложнением диспетчеров памяти. Уровень же надежности, обеспечиваемый современными ОС общего назначения с разделением памяти, по-видимому, оптимален в том смысле, что улучшения в сфере защиты памяти могут быть достигнуты лишь ценой значительных накладных расходов без принципиального повышения наработки на отказ.

Вернуться наверх

5.4. Разделяемые библиотеки

     Ранее мы упоминали разделяемые библиотеки как одно из преимуществ страничных и сегментных диспетчеров памяти перед базовыми и банковыми. При базовой адресации образ каждого процесса должен занимать непрерывные области как в физическом, так и в логическом адресном пространстве. В этих условиях реализовать разделяемую библиотеку невозможно. Но и при использовании страничной адресации не все так просто.
     Использование разделяемых библиотек и/или DLL (в данном случае разни-ца между ними не принципиальна) предполагает ту или иную форму сборки в момент загрузки: исполняемый модуль имеет неразрешенные адресные ссылки и имена библиотек, которые ему нужны. При загрузке эти библиотеки подгружаются и ссылки разрешаются. Проблема здесь в том, что при подгрузке библиотеки ее нужно переместить, перенастроив абсолютные адресные ссылки в ее коде и данных (см. главу 3). Если в разных процессах библиотека будет настроена на разные адреса, она уже не будет разделяемой (рис. 5.14)! Если разделяемые библиотеки могут иметь неразрешенные ссылки на другие библиотеки, проблема только усугубляется - к перемещаемым ссылкам добавляются еще и внешние.


     В старых системах семейства Unix, использовавших абсолютные загружаемые модули формата a.out, разделяемые библиотеки также поставлялись в формате абсолютных модулей, настроенных на фиксированные адреса. Каждая библиотека была настроена на свой адрес. Поставщик новых библиотек должен был согласовать этот адрес с разработчиками системы. Это было весьма непрактично, поэтому разделяемых библиотек было очень мало (особенно если не считать те, которые входили в поставку ОС).
     Более приемлемое решение этой проблемы реализовано в OS/2 2.x и Win32 (обе эти архитектуры являются развитием систем с единым адресным пространством). Идея состоит в том, чтобы выделить область адресов под загрузку DLL и отображать эту область в адресные пространства всех процессов. Таким образом, все DLL, загруженные в системе, видны всем (рис. 5.15).
     Очевидным недостатком такого решения (как, впрочем, и предыдущего) является неэффективное использование адресного пространства: при сколь-нибудь сложной смеси загруженных программ большей части процессов большинство библиотек будет просто не нужны. В те времена, когда эта архитектура разрабатывалась, это еще не казалось серьезной трудностью, но сейчас, когда многим приложениям становится тесно в 4 Гбайт и серверы с таким объемом оперативной памяти уже не редкость, это действительно может стать проблемой.


     Менее очевидный, но более серьезный недостаток состоит в том, что эта архитектура не позволяет двум приложениям одновременно использовать две разные, но одноименные DLL - например, две разные версии стандартной библиотеки языка С. Поэтому либо мы вынуждены требовать от всех разделяемых библиотек абсолютной (bug-for-bug) совместимости версий, либо честно признать, что далеко не каждая смесь прикладных программ будет работоспособна. Первый вариант нереалистичен, второй же создает значительные неудобства при эксплуатации, особенно если система интерактивная и многопользовательская.
     Лишенное обоих недостатков решение предлагают современные системы семейства Unix, использующие загружаемые модули формата ELF. Впрочем, для реализации этого решения пришлось, ни много, ни мало, переделать компилятор и научить его генерировать позиционно-независимый код (см. разд. 3.5).

Разделяемые библиотеки формата ELF

Вернуться наверх

5.5. Страничный обмен

     Подкачка, или свопинг (от англ, swapping - обмен) - это процесс выгрузки редко используемых областей виртуального адресного пространства программы на диск или другое устройство массовой памяти. Такая массовая память всегда намного дешевле оперативной, хотя и намного медленнее.
     Во многих учебниках по ОС приводятся таблицы, аналогичные табл. 5.2.

Таблица 5.2. Сравнительные характеристики и стоимость различных типов памяти.
Тип памятиВремя доступаЦена 1 Мбайта (цены 1995г.)Способ использования
Статическая память15 нс$200Регистры, кэш-память
Динамическая память70 нс$30 (4Мбайт SIMM)основная память
Жесткие магнитные диски1-10 мс$3 (1.2Gb EIDE)Файловые системы, устройства своппинга
Магнитные лентыСекунды$0.025 (8мм Exabyte)Устройства резервного копирования

     При разработке системы всегда есть желание сделать память как можно более быстрой. С другой стороны, потребности в памяти очень велики и постоянно растут.
     Очевидно, что система с десятками гигабайтов статического ОЗУ будет иметь стоимость, скажем так, совершенно не характерную для персональных систем, не говоря уже о габаритах, потребляемой мощности и прочем. К счастью, далеко не все, что хранится в памяти системы, используется одновременно. В каждый заданный момент исполняется только часть установленного в системе программного обеспечения, и работающие программы используют только часть данных.
     Эмпирическое правило "80-20", часто наблюдаемое в коммерческих системах обработки транзакций, гласит, что 80% операций совершаются над 20% файла [Heising 1963]. В ряде работ, посвященных построению оптимизирующих компиляторов, ссылаются на правило "90-10" (90% времени испол-няется 10% кода) - впрочем, есть серьезные основания сомневаться в том, что в данном случае соотношение именно таково [Кнут 2000, т. 3].
     В действительности, удивительно большое количество функций распределения реальных дискретных величин (начиная от количества транзакций на строку таблицы и заканчивая распределением богатства людей или капитализации акционерных обществ) подчиняются закону Парето [Pareto 1897]: рk = ckO-1, где O - число в диапазоне от 0 до 1, k - значение величины (в нашем случае - количество обращений к данной записи), р - количество записей, к которым происходит k обращений, с - нормализующий коэффициент (правило "80-20" соответствует O = log 80/log 20 - 0,1386) или его частному случаю, распределению Зипфа [Zipf 1949]: р = c/k.
     Детальное обсуждение этого явления, к сожалению, не доходящее до глубинных его причин, приводится в [Кнут 200, т. 3]. Как один из результатов обсуждения предлагается концепция "самоорганизующегося файла" - для ускорения поиска в несортированном массиве предлагается передвигать записи ближе к началу массива. Если обращения к массиву распределены в соответствии с законом Зипфа, наиболее востребованные записи концен-трируются в начале массива и поиск ускоряется в c/ln(N) раз, где N - размер массива, а с - константа, зависящая от используемой стратегии перемещения элементов.
     При произвольном доступе к данным (например, по указателям или по ключам хэш-таблицы) перемещение к началу массива не имеет столь благотворного эффекта - если только вся память имеет одну и ту же скорость доступа. Но мы видели, что разные типы запоминающих устройств резко различаются по этому параметру.
     Это различие приводит нас к идее многослойной или многоуровневой памяти, когда в быстрой памяти хранятся часто используемые код или данные, а редко используемые постепенно мигрируют на более медленные устройства. В случае дисковой памяти такая миграция осуществляется вручную: администратор системы сбрасывает на ленты редко используемые данные и заполняет освободившееся место чем-то нужным. Для больших и сильно загруженных систем существуют специальные программы, которые определяют, что является малоценным, а что - нет. Управление миграцией из ОЗУ на диск иногда осуществляется пользователем, но часто это оказывается слишком утомительно. В случае миграции между кэш-памятью и ОЗУ делать что-то вручную просто физически невозможно.

Вернуться наверх

5.5.1. Поиск жертвы

... и вот мы обрадовались вашему приходу, -
может, вы согласитесь принести себя в жертву
А. Тутуола

     Естественно, для того чтобы автоматизировать процесс удаления "барахла" - редко используемых данных и программ - мы должны иметь какой-то легко формализуемый критерий, по которому определяется, какие данные считаются редко используемыми.
     Один критерий выбора очевиден - при прочих равных условиях, в первую очередь мы должны выбирать в качестве "жертвы" (victim) для удаления тот объект, который не был изменен за время жизни в быстрой памяти. Действительно, вы скорее удалите с винчестера саму игрушку (если у вас есть ее копия на дискетах), чем файлы сохранения!
     Для ручного переноса данных очевиден и другой критерий: нужно удалять (Для блоков данных, которые не подверглись изменению за время пребывания в быстрой памяти, удаление будет состоять в уничтожении копии. Для модифицированных же блоков новое значение данных должно быть скопировано обратно в медленную память, и только после этого можно произвести собственно удаление.) то, что дольше всего не будет использоваться в будущем. Конечно, любые предположения о будущем имеют условный характер, все может неожиданно измениться. Мы делаем предположения о том, что будет использоваться, только на основании накопленной статистики обращений к страницам. Такая экстраполяция не совсем корректна логически, поэтому может оказаться целесообразным смириться с некоторой неточностью или неполнотой этой статистики.
     Самая простая стратегия - выбрасывать случайно выбранный объект. При этом не надо собирать никакой статистики о частоте использования и т. д., важно лишь обеспечить равномерность распределения генерируемых псевдослучайных чисел. Очевидно, что при этом удаленный объект совершенно необязательно будет ненужным
     Можно также удалять то, что дольше всего находится в памяти. Это называется алгоритмом FIFO (First In, First Out, первый вошел, первый вышел). Видно, что это уже чуть сложнее случайного удаления - нужно запоминать, когда мы что загружали.
     Пул свободных страниц, в который входят как действительно свободные, так и отобранные у задач в качестве "жертв" страницы, в той или иной форме поддерживают все ОС, использующие страничный обмен, однако обычно этот пул отделяют от дискового кэша и при полной загрузке он не превос-ходит нескольких процентов ОЗУ. При запросах ядра и страничных отказах система выделяет страницы из этого пула, и только при падении его объема ниже некоторого предела, начинает поиск жертв в адресных пространствах активных процессов.
     Наиболее справедливым будет удалять тот объект, к которому дольше всего не было обращений в прошлом LRU (Least Recently Used). Такой подход требует набора сведений обо всех обращениях. Например, диспетчер памяти должен поддерживать в дескрипторе каждой страницы счетчик обращений, и при каждой операции чтения или записи над этой страницей увеличивать этот счетчик на единицу. Это требует довольно больших накладных расходов - в ряде работ, например, в [Краковяк 1987], утверждается, что они будут недопустимо большими.
     Остроумным приближением к алгоритму LRU является так называемый clock-алгоритм, применяемый во многих современных ОС, в том числе в системах семейства Unix. Он состоит в следующем (рис. 5.21).
  • Дескриптор каждой страницы содержит бит, указывающий, что к данной странице было обращение. Этот бит называют clock-битом.
  • При первом обращении к странице, в которой clock-бит был сброшен, диспетчер памяти устанавливает этот бит.
  • Программа, занимающаяся поиском жертвы, циклически просматривает все дескрипторы страниц. Если clock-бит сброшен, данная страница объявляется жертвой, и просмотр заканчивается до появления потребности в новой странице. Если clock-бит установлен, то программа сбрасывает его и продолжает поиск.


         Название clock, по-видимому, происходит от внешнего сходства процесса циклического просмотра с движением стрелки часов (рис. 5.22). Очевидно, что вероятность оказаться жертвой для страницы, к которой часто происходят обращения, существенно ниже. Накладные расходы этого алгоритма гораздо меньше, чем у LRU: вместо счетчика мы храним только один бит и изменяем его не при каждом обращении к странице, а только при первом обращении после прохода "стрелки".


         Практически все известные автору современные диспетчеры памяти пред-полагают использование clock-алгоритма. Такие диспетчеры хранят в дескрипторе страницы или сегмента два бита - clock-бит и признак модификации. Признак модификации устанавливается при первой записи в страницу/сегмент, в дескрипторе которой этот признак был сброшен.
         Экспериментальные исследования показывают, что реальная производительность системы довольно слабо зависит от применяемого алгоритма поиска жертвы. Статистика исполнения реальных программ говорит о том, что каждая программа имеет некоторый набор страниц, называемый рабочим множеством, который ей в данный момент действительно нужен. Размер такого набора сильно зависит от алгоритма программы, он изменяется на различных этапах исполнения и т. д., но в большинстве моментов мы можем довольно точно указать его.
         Если рабочий набор запущенных программ превосходит оперативную память, частота страничных отказов резко возрастает. При нехватке памяти программе почти на каждой команде требуется новая страница, и производительность системы катастрофически падает. Это состояние по английски называется thrashing (общепринятого перевода для этого слова нет) и является крайне нежелательным.
         В системах коллективного пользования размер памяти часто выбирают так, чтобы система балансировала где-то между состоянием, когда все программы держат свое рабочее множество в ОЗУ, и трэшингом.
         Точное положение точки балансировки определяется в зависимости от соотношения между скоростью процессора и скоростью обмена с диском, а также от потребностей прикладных программ. Во многих старых учебниках рекомендуется подбирать объем памяти так, чтобы канал дискового обмена был загружен на 50% [Краковяк 1987].
         Еще одно эмпирическое правило приводится в документации фирмы Amdahl: сбалансированная система должна иметь по мегабайту памяти на каждый MIPS (Million of Instructions Per Second - миллион операций в секунду) производительности центрального процессора. Если система не использует память, определенную по этой формуле, есть основания считать, что процессор также работает с недогрузкой. Иными словами, это означает, что вы купили слишком мощный для ваших целей процессор и заплатили лишние деньги.
         Это правило было выработано на основе опыта эксплуатации больших компьютеров четвертого поколения, в основном на задачах управления базами данных. Скорость дисковой подсистемы в этих машинах была примерно сравнима с дисковыми контроллерами современных персональных компьютеров, поэтому в первом приближении этот критерий применим и к ПК, особенно работающим под управлением систем с виртуальной памятью - OS/2, Windows NT и системами семейства Unix. В любом случае, для выдачи рекомендаций требуется анализ смеси приложений, которая будет исполняться в системе, и других требований к ней.
         В современных персональных системах пользователь, как правило, работает в каждый момент только с одной-двумя программами, и задержки в исполнении этих программ существенно снижают наблюдаемую скорость системы. Поэтому в таких системах память обычно ставят с большим запасом, так, чтобы при обычной деятельности рабочие множества программ даже близко не подходили к размеру ОЗУ. Отчасти это обусловлено тем, что в наше время динамическая память становится все дешевле и дешевле.

    Вернуться наверх

    5.6. Управление своп-файлом

         Для хранения образов модифицированных страниц система должна выделить какое-то пространство на диске. Для этого может использоваться как раздел диска, так и файл, место для которого выделяется наравне с файлами данных. Большинство современных систем может использовать как тот, так и другой методы, и поддерживает динамическое подключение и отключение своп-файлов и своп-разделов.
         При наличии в системе нескольких дисков рекомендуется разделить своп-пространство между всеми (или хотя бы между менее используемыми) дисками. Дело в том, что операции чтения и записи требуют времени на позиционирование считывающей головки. Пока один накопитель передвигает головку, второй вполне может передавать данные. Понятно, что линейного роста производительности с увеличением числа дисков таким способом не получить: всегда есть вероятность, что все требуемые данные окажутся на одном диске, да еще и находятся в разных местах, но все равно выигрыш в большинстве случаев оказывается значительным.
         В те времена, когда компьютеры были большими, для свопа часто использовались не диски, а специальные устройства, магнитные барабаны. В отличие от диска, который имеет одну или, реже, несколько головок чтения-записи, барабан имел по одной головке на каждую дорожку. Конечно, это повышало стоимость устройства, но полностью исключало потери времени на позиционирование (рис. 5.23).


         В своп-файл попадают только страницы, которые изменились с момента загрузки процесса. Если ОС использует абсолютную загрузку или позиционно-независимый код, исполняющийся код не отличается от своего образа в загрузочном файле, поэтому страницы кода вполне можно подкачивать оттуда, и нет никакой необходимости копировать их в своп. Часто при загрузке программы система помещает в память только страницу, на которую указывает стартовый адрес, а весь остальной используемый код и данные подгружаются механизмом страничного обмена.
         При загрузке статически инициализированных данных обычно используется стратегия copy-on-write (копирование при модификации): первоначально страница подкачивается из файла. Если она не будет модифицирована и ее объявят жертвой, то при повторном обращении ее снова подгрузят из того же файла (рис. 5.24). Только если страница будет изменена, ей выделят место в своп-файле.


         Если же используется относительная загрузка или та или иная форма сборки в момент загрузки (разделяемые библиотеки или DLL), при загрузке кода происходит перенастройка адресов. В этом случае возможны два подхода: копировать перенастроенный код в своп или производить перенастройку заново после каждого страничного отказа.
         Даже когда место под своп-файл выделяется динамически, система обычно предоставляет возможность ограничивать его рост. У интерактивных систем при приближении к границе емкости своп-файла система часто начинает выдавать предупреждения пользователю. Однако основным видом реакции на переполнение или превышение лимитов роста своп-файла является отказ выделять память прикладным программам. Поэтому грамотно написанные программы всегда должны проверять, нормально ли завершился запрос на выделение памяти, и по возможности разумно обрабатывать ненормальное завершение. Это нужно не только в том случае, когда программа будет переноситься в систему без виртуальной памяти, но и во вполне штатной (хотя и относительно редкой) ситуации переполнения свопа.
         Иногда, впрочем, система может выделять память (точнее, не память, а только адресное пространство) программам без оглядки на то, сколько есть свободного свопа. Эта довольно опасная стратегия, называемая overcommit, на первый взгляд кажется бессмысленной или полезной только в очень специальных случаях, например при использовании разреженных массивов. В действительности эта стратегия оправдана и тогда, когда мы можем быть уверены, что большинство выделенных процессу страниц никогда не будут использованы, например, при широком применении стратегии copy-on-write.

    Вернуться наверх

    5.7. Одноуровневая память

    И каждый уже десять лет учит роли,
    О которых лет десять как стоит забыть
    Б. Гребенщиков

         Эффективное управление рабочими наборами пользовательских программ и, с другой стороны, эффективное кэширование запросов к дискам позволяют если и не скрыть полностью, то в значительной мере сгладить различие в производительности оперативной и внешней памяти компьютера. Поэтому сразу же после возникновения первых машин с виртуальной памятью начались попытки спрятать все остальные различия между этими двумя типами памяти от программиста, реализовав так называемую одноуровневую память.
         Интерес к этой идее сохраняется до сих пор. Например, на сайте [dz.yandex.ru] в конце 2000 года была серия публикаций и довольно бурная дискуссия о достоинствах и недостатках "персистентных объектов" - объектов в терминах объектно-ориентированного программирования, которые переживают перезагрузки и выключения питания системы. Для хранения таких объектов может использоваться как флэш-память, так и другие формы энергонезависимой памяти, те же жесткие диски. Владелец сайта и инициатор дискуссии, Дмитрий Завалишин, отстаивал тезис о том, что такие объекты представляют собой сокровенную мечту и своего рода Священный Грааль всего программирования и развития вычислительной техники.
         Для того чтобы понять, возможна ли полностью одноуровневая память, и если да, то в какой мере, давайте сначала установим различия между ОЗУ и наиболее распространенным типом внешней памяти, жестким магнитным диском.
         Во-первых, объем оперативной памяти в современных компьютерах измеряется десятками и сотнями мегабайт, а у систем коллективного пользования достигает нескольких гигабайт. Характерная емкость жесткого диска начинается с нескольких гигабайт (диски меньшего объема просто не производятся) и заканчивается сотнями гигабайт. Если мы хотим адресовать все это единым образом, мы должны расширить адресное пространство. 32 бит явно недостаточно, 64 бит на ближайшие годы хватит, но рост емкости дисковых массивов идет по экспоненте.
         Впрочем, расширение адресного пространства само по себе не представляет большой проблемы - мало 64 бит, сделаем 128, тем более что речь идет не об адресной шине процессора, используемой только для адресации ОЗУ, а о виртуальном адресе. Современные технологии без особых проблем позволяют упаковать арифметико-логическое устройство и регистры такой разрядности в один кристалл, сделать корпус с надлежащим числом ног, печатную плату, в которую можно впаять такой корпус и автоматическую линию, которая будет распаивать корпуса по платам. Да, это будет не Spectrum, вручную не спаяешь - но и материнскую плату современного PC-совместимого компьютера вручную невозможно развести и спаять. Ну и что?
         Во-вторых, оперативная память теряет свое содержимое при выключении питания, а жесткий диск - сохраняет, поэтому нередко используется еще одна характеристика дисковой памяти как противопоставление оперативной - постоянная память. Можно вспомнить и о промежуточных решениях, например о флэш-памяти и ее аналогах, которые адресуются почти как ОЗУ, а данные хранят почти как жесткий диск. Наличие промежуточных решений наводит на мысль, что особых проблем с этой стороны ждать не приходится. На самом деле, проблема здесь есть, но обсудим мы ее чуть позже.
         В-третьих, и это связано сразу с обеими вышеназванными причинами, человек снисходит до ручного наведения порядка на диске (удаления мусора и пр.) гораздо чаще, чем до выполнения той же операции в ОЗУ. Поэтому жесткие диски обычно снабжаются еще одной схемой адресации, ориентированной на использование человеком: когда вместо адреса, представляемого целым числом, используется символическое имя.
         Трансляция имени в адрес (сектор, поверхность и дорожку жесткого диска) осуществляет файловая система. Вопросы организации файловых систем, каталогов и управления структурами свободной и занятой дисковой памяти обсуждаются в главе 10.
         Единственная из используемых в настоящее время архитектур, предоставляющая "честную" одноуровневую память, AS/400, имеет два представления указателя, неразрешенное - с именем в качестве селектора сегмента, и разрешенное - с бинарным представлением этого селектора. Можно себе представить и другие механизмы трансляции имен в адреса, например получение указателя посредством исполнения системного вызова
         void *resolve(char * object_name, int flags)
         или чего-нибудь в этом роде. Особых технических проблем это не представляет, вопрос в том, надо ли это.
         Изложение одного из доводов в пользу того, что это надо далеко не всегда, мы предлагаем начать издалека, а именно с весьма банального тезиса, что писать программы без ошибок человечество до сих пор не научилось и вряд ли научится в обозримом будущем. Исполнение программы, содержащей ошибки, может порождать не только обращения по неверным указателям и выход за границы массивов (наиболее разрушительные типы ошибок, от которых сегментные и страничные диспетчеры памяти предоставляют определенную защиту), но и более тонкие проблемы - фрагментацию и/или утечку свободной памяти и различные рассогласования (в СУБД применяют более точный термин - нарушения целостности данных).
         Накопление этих ошибок рано или поздно приводит к тому, что программа теряет способность функционировать. Потеря этой способности может быть обнаружена и пользователем ("что-то прога глючит", "зависла"), и системой (исчерпание квоты памяти или других ресурсов, превышение лимитов роста своп-пространства или доступ по недопустимому адресу), и даже самой программой - если существуют формальные критерии целостности данных, в различных местах кода могут встречаться проверки этих критериев.
         Учебники по программированию, например [Дейкстра 1978], настоятельно рекомендуют вырабатывать такие критерии и вставлять соответствующие проверки везде, где это целесообразно. Понятно, что забывать о здравом смысле и вставлять их после каждого оператора, или даже лишь перед каждой операцией, для исполнения которой требуется целостность, далеко не всегда оправдано с точки зрения производительности, так что при реальном программировании надо искать баланс.
         Иногда в ходе таких проверок даже удается восстановить целостность (примеры алгоритмов проверки и восстановления структур файловой системы приводятся в главе 12), но очевидно, что далеко не всегда это возможно. В этом случае остается лишь проинформировать пользователя, что у нас "Assertion failed" (предположение нарушено) и по возможности мирно завершиться (рис. 5.25).
         Сохранять при этом данные в постоянную память опасно: если мы не можем восстановиться, мы часто не можем и знать, насколько далеко зашло нарушение целостности, поэтому сохранение чего бы то ни было в таком состоянии чревато полной или частичной (что тоже неприятно) потерей информации. В частности, именно из этих соображений ОС общего назначения, обнаружив ошибку в ядре, сразу рисуют регистры на консоли (рискуя при этом целостностью файловых систем и пользовательских данных), а не предлагают пользователю предпринять какие-либо меры по сохранению данных.
         Смысл останова задачи или всей системы с последующим ее перезапуском состоит в том, чтобы заново проинициализировать структуры данных, используемые при работе программного обеспечения. Это действие можно описать как '"контролируемое забывание" всего плохого, что накопилось в памяти за время работы программы, и начало с более или менее чистого листа.


         Сервис автоматического перезапуска в различных формах предоставляется многими приложениями, ОС и даже аппаратными архитектурами.
         Например, практически обязательным элементом современных микроконтроллеров является watchdog timer (сторожевой таймер, дословно - "сторожевая собака"), часто работающий от собственного осциллятора, а не от общего тактового генератора машины. Программа микроконтроллера должна периодически сбрасывать сторожевой таймер, иначе, досчитав до конца, он делает вывод, что программа "зависла" и инициирует системный сброс.
         Именно сторожевой таймер несколько раз перезагружал бортовой компьютер посадочного модуля "Аполлона-11" и, по-видимому, спас этим жизни астронавтов и лунную программу США [NASA 182505].
         Аналогичные схемы часто применяются во встраиваемых приложениях, особенно ориентированных на длительную автономную работу. Действительно, встраиваемое приложение может оказаться в весьма неприятном для человека месте, например, вблизи от активной зоны реактора или ускорителя (понятно, что для таких применений необходимо специальное исполнение микросхем, например на сапфировой подложке). В этих случаях иногда выводят кнопку системного сброса в "чистые" области многометровым кабелем. Но, скажем, для управляющего компьютера космического аппарата такое решение просто нереализуемо. Бывают и ситуации, когда выводить кнопку системного сброса наружу нежелательно по более банальным, эргономическим и т. д., соображениям, например из-за опасности случайного нажатия.
         О чем-то аналогичном такому сервису часто мечтают администраторы серверов. В Новосибирском FIDO однажды вполне серьезно обсуждалась такая схема автоматизированного перезапуска: сервер каждые пять минут перепрограммирует источник бесперебойного питания на то, чтобы он через десять минут от текущего момента выключился и снова включился. В FIDO встречаются описания и более экстравагантных решений, например "деглюкатор" (устройство, включаемое в шину ISA и по запросу программы выполняющее сброс внешнего модема) или рычажный механизм, посредством которого компьютер, выдвинув поднос CD-ROM, может сам себе нажать на кнопку сброса (рис. 5.26) (полезен в ситуациях, когда система еще условно работоспособна, но с высокой вероятностью может "зависнуть" при попытке нормальной перезагрузки).


         Понятно, что все вышеперечисленные решения не могут заменить собой отладку и исправление ошибок в прикладных и системных программах и являются скорее последней линией обороны (если даже не действиями, предпринимаемыми от отчаяния) в борьбе с системными сбоями. Но пока человечество не научится писать программы без ошибок, возможность "привести в чувство" обезумевшую программу путем ее перезапуска остается жизненно необходимой.
         Понятно также, что если программа полностью сохраняет свое состояние в постоянной памяти, ее перезапуск нам ничем не поможет: программа честно восстановит весь тот мусор, который накопился в ее сегментах и файлах данных за время предыдущей сессии, и честно воспроизведет снова тот сбой, из-за которого и потребовался рестарт.
         В этом смысле крайне желательно держать под контролем перенос данных из постоянной памяти в оперативную, а особенно в обратном направлении, избегая его полной "прозрачности". Каждая дополнительная точка сохранения состояния системы повышает риск воспроизведения сбоя или даже возникновения новых проблем, порожденных в файлах сохранения состояния во время чрезмерно "жесткого" перезапуска.
         В свете вышеприведенных рассуждений, полезно разделять оперативные и хранимые объекты не только по способу адресации, но и по представлению данных. Эти представления должны удовлетворять различным и не всегда совместимым требованиям: при выборе внутреннего, оперативного представления данных основные критерии - это скорость, удобство доступа и умопостижимость кода, который будет с этими данными работать, а для внешнего, хранимого представления - прежде всего легкость проверки и, если это возможно, восстановление целостности данных. При разработке внешнего формата данных желательно также принять во внимание соображения межмашинной совместимости - возможные различия в порядке байтов и даже битов в целочисленных значениях, особенности представления чисел с плавающей точкой, различия кодировки текста и так далее.
         Если хранимое и оперативное представления объектов различны, одноуров-невая память для нас скорее вредна, чем бесполезна: прежде чем программа сможет работать с объектом, она должна преобразовать его во внутреннее представление (в объектно-ориентированных языках это может делать один из конструкторов объекта). Эту процедуру обычно оказывается целесообразно совместить со считыванием внешнего представления объекта из файла. "Прозрачная" же для пользовательской программы запись данных во внешний формат бывает и просто опасна - нередко для обеспечения целостности данных оказывается необходим контроль над порядком записи тех или иных полей и структур.
         Объединение оперативной и долговременной памяти, таким образом, оказывается применимо лишь в тех ситуациях, когда нам, во-первых, удалось разработать модель данных, одновременно удовлетворяющую требованиям, предъявляемым и к оперативному, и к хранимому представлениям, и во-вторых, когда нас не беспокоит опасность нарушения нашей модели данных из-за неполного их сохранения в момент системного сбоя (или когда мы имеем какие-то средства предотвращения этой опасности),
         Безусловно, средства для отображения файлов в память лучше иметь, чем не иметь. К тому же их можно использовать и для других целей, кроме собственно организации одноуровневого доступа к данным - для загрузки программ, выделения памяти или эмуляции сегментов данных, разделяемых между задачами и даже между машинами (при доступе к файлу по сети).
         Важно еще подчеркнуть, что разделение представлений данных на внешние и внутренние не обязано полностью соответствовать способу их хранения -в ОЗУ или на диске. Кроме хранения оперативных данных в своп-пространстве и разного рода "виртуальных дисков" можно привести и более радикальный пример: таблицы, индексы и прочие файлы данных сервера реляционной СУБД представляют собой, скорее, оперативное представление данных, роль же хранимого представления в данном случае играют форматы, используемые для экспорта и резервного копирования содержимого таблиц.
         Благодаря этому примеру становится понятнее, почему единственная из коммерчески применяемых в настоящее время систем с одноуровневой адресацией - AS/400 - ориентирована на использование в качестве сервера СУБД. В литературе, особенно в рекламной, даже встречается ее описание как "аппаратного сервера баз данных".

    Вернуться наверх