Страничный обмен
Подкачка, или свопинг (от англ, swapping – обмен) – это процесс выгрузки редко используемых областей виртуального адресного пространства программы на диск или другое устройство массовой памяти. Такая массовая память всегда намного дешевле оперативной, хотя и намного медленнее.
Во многих учебниках по ОС приводятся таблицы, аналогичные табл. 5.2.
Таблица 5.2. Сравнительные характеристики и стоимость различных типов памяти.
| Тип памяти | Время доступа | Цена 1 Мбайта (цены 1995 г.) | Способ использования |
|---|---|---|---|
| Статическая память | 15 нc | $200 | Регистры, кэш-память |
| Динамическая память | 70 нc | $30 (4 Мбайт SIMM) | Основная память |
| Жесткие магнитные диски | 1-10 мс | $3 (1.2Gb HIDE) | Файловые системы, устройства свопинга |
| Магнитные ленты | Секунды | $0.025 (8mm Exabyte) | Устройства резервного копирования |
При разработке системы всегда есть желание сделать память как можно более быстрой. С другой стороны, потребности в памяти очень велики и постоянно растут.
Примечание
Существует эмпирическое наблюдение, что любой объем дисковой памяти будет полностью занят за две недели.
Очевидно, что система с десятками гигабайтов статического ОЗУ будет иметь стоимость, скажем так, совершенно не характерную для персонапьных систем, не говоря уже о габаритах, потребляемой мощности и прочем. К счастью, далеко не все, что хранится в памяти системы, используется одновременно. В каждый заданный момент исполняется только часть установленного в системе программного обеспечения, и работающие программы используют только часть данных.
Эмпирическое правило "80-20", часто наблюдаемое в коммерческих системах обработки транзакций, гласит, что 80% операций совершаются над 20% файла [Heising 1963]. В ряде работ, посвященных построению оптимизирующих компиляторов, ссылаются на правило "90-10" (90% времени исполняется 10% кода) – впрочем, есть серьезные основания сомневаться в том, что в данном случае соотношение именно таково [Кнут 2000, т. 3].
В действительности, удивительно большое количество функций распределения реальных дискретных величин (начиная от количества транзакций на строку таблицы и заканчивая распределением богатства людей или капитализации акционерных обществ) подчиняются закону Парето [Pareto 1897]:
Р = ck 
-1.
Где – число в диапазоне от 0 до 1, k – значение величины (в нашем случае – количество обращений к данной записи), р – количество записей, к которым происходит k обращений, с – нормализующий коэффициент (правило "80-20" соответствует = =log80/log20 = 0.1386) или его частному случаю, распределению Зипфа [Zipf 1949]: р = c/ k.
Детальное обсуждение этого явления, к сожалению, не доходящее до глубинных его причин, приводится в [Кнут 200, т. 3]. Как один из результатов обсуждения предлагается концепция "самоорганизующегося файла" – для ускорения поиска в несортированном массиве предлагается передвигать записи ближе к началу массива. Если обращения к массиву распределены в соответствии с законом Зипфа, наиболее востребованные записи концентрируются в начале массива и поиск ускоряется в c/ ln N раз, где N – размер массива, а с – константа, зависящая от используемой стратегии перемещения элементов.
При произвольном доступе к данным (например, по указателям или по ключам хэш-таблицы) перемещение к началу массива не имеет столь благотворного эффекта – если только вся память имеет одну и ту же скорость доступа. Но мы видели, что разные типы запоминающих устройств резко различаются по этому параметру.
Это различие приводит нас к идее многослойной или многоуровневой памяти, когда в быстрой памяти хранятся часто используемые код или данные, а редко используемые постепенно мигрируют на более медленные устройства. В случае дисковой памяти такая миграция осуществляется вручную: администратор системы сбрасывает на ленты редко используемые данные и заполняет освободившееся место чем-то нужным.
Для больших и сильно загруженных систем существуют специальные программы, которые определяют, что является малоценным, а что – нет. Управление миграцией из ОЗУ на диск иногда осуществляется пользователем, но часто это оказывается слишком утомительно. В случае миграции между кэш-памятью и ОЗУ Делать что-то вручную просто физически невозможно.