Общее оглавление

Аппаратная иерархия памяти

Современные процессоры имеют намного более высокое быстродействие, чем основной вид оперативной памяти — динамическая память (DRAM). Поэтому для снижения временны́х затрат на ожидание выполнения операций с памятью в процессоры добавляют очень быструю, но небольшую по объёму память — кэши caches. Кэши используются для временного хранения данных, полученных из памяти или предназначенных для записи в память. Такой подход оправдан по той причине, что процессору во время работы типичных программ обычно приходится многократно обращаться к одним и тем же ячейкам памяти. Благодаря кэшу он может не ждать завершения операций с памятью а быстро выполнять вычисления с небольшим кусочком данных прямо “в кэше”.

Со временем оказалось, что эффективнее иметь не один кэш на процессор, а разделить кэш на части, обладающие различными характеристиками (и даже, возможно, работающие по разным алгоритмам): очень быстрый, но маленький кэш первого уровня level-1 cache (“L1”) и пусть не такой быстрый, но уже и не такой маленький кэш второго уровня level-2 cache (“L2”).

Более того, кэш L1 обычно разделяют на две параллельно работающих части — кэш инструкций instruction cache (“L1I”) и кэш данных data cache (“L1D”). Такая архитектура позволяет ускорить работу процессора засчёт того, что:

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

Когда появились многоядерные процессоры, фактически объединяющие на одном кристалле несколько отдельных процессоров (которые стали называть “ядрами” cores), появилась необходимость обеспечивать эффективный обмен данными между ними и внешними интерфейсами процессора (память, устройства ввода-вывода).

Теоретически, можно было бы осуществлять обмен через память, но память — внешнее устройство, и это слишком медленно (аналогично случаю с использованием нескольких физически отдельных процессоров). Поэтому для решения этой задачи стали использовать внутреннюю память — кэш. Для этого либо кэш L2 “выносят” из ядра и делают разделяемым ресурсом (типично для “малых”, например, “мобильных” процессоров, так как такой подход позволяет экономить площадь кристалла и потребляемую им энергию), либо добавляют ещё один уровень — уже третий (“L3”). Добавление третьего уровня позволяет сохранить характеристики L2 на уровне одноядерных процессоров (разделяемые ресурсы всегда медленнее выделенных).

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

Ниже приведена упрощённая схема четырёхядерного процессора “серверного” класса, в котором имеются три уровня кэшей и кэши первого уровня разделены на кэши инструкций L1I и данных L1D. Толстой чёрной линией показана внутренняя шина, соединяющая части процессора в единое целое. На схеме она представляет собой кольцо (как, например, у современных процессоров Intel Xeon) из десяти узлов: четыре ядра, четыре банка L3 (каждый банк доступен каждому ядру, хотя и расположен вблизи только одного из ядер), интегрированный контроллер памяти integrated memory controller (“IMC”) и подсистема ввода-вывода (“IO”).

Контроллер памяти управляет передачей данных по каналам памяти (на схеме обозначены как “DRAM PHY”, т.е. интерфейс DRAM физического уровня). К каждому каналу относится свой набор физических модулей памяти и, соответственно, прикреплён участок физического адресного пространства памяти. Увеличение числа каналов (а их может быть и больше двух) позволяет, не ускоряя саму память, кратно поднять её пропускную способность, что может быть эффективно задействовано многоядерными процессорами — разные каналы могут параллельно использоваться разными ядрами.

“SMP links” обозначают каналы связи с другими процессорами, что актуально для многопроцессорных систем. Наличие выделенных каналов связи позволяет поднять эффективность работы системы, упростить обращение процессоров к “чужой” оперативной памяти (каждый процессор распоряжается своей группой физических модулей DRAM, но программе могут понадобиться данные, которые лежат в памяти, принадлежащей другому процессору системы).

Рассмотрим в общих чертах устройство отдельного ядра. На схеме ниже показаны составные элементы ядра. Помимо кэшей это четыре устройства и два регистровых файла (массива непосредственно доступных для выполняемых команд ячеек памяти — регистров). Элементы ITLB, DTLB и L2 TLB являются особыми кэшами (кэши страниц) и ускоряют работу механизма виртуальной памяти (о ней ниже).

Устройство управления занимается загрузкой команд, их первичной обработкой и отправкой на исполнительные устройства и включает в себя особый регистр — счётчик программы program counter (“PC”), в котором хранится адрес следующей команды, загружаемой из L1I. Изменение значения PC приводит к переходу на другую инструкцию в программе. Арифметико-логическое устройство (“ALU”) выполняет операции широкого спектра с целыми числами. Устройство вычислений в плавающей точке floating point unit (“FPU”) обычно существует отдельно от ALU и выполняет операции с числами в плавающей точке. Устройство загрузки-сохранения load-store unit (“LSU”) вычисляет адреса и выполняет чтение из памяти и запись в память данных (через кэш L1D).

Устройство управления и устройство загрузки-сохранения в современных процессорах пытаются прогнозировать адреса, соответственно, очередных переходов (этим занимается “предсказатель ветвлений” branch predictor) и загрузок из памяти (этим занимается “префетчер” prefetcher). Если прогноз оказывается успешным, то нужные команды или данные к моменту использования будут уже готовы. Чем проще характер обращений к памяти, тем успешнее оказывается прогнозирование. Например, перебор значений массива подряд — идеальный случай для прогнозирования.

Пример (для простоты рассмотрим модель с одноуровневым кэшем): пусть нужные данные с вероятностью 50% оказываются в кэше, задержка обращения к которому 2 такта, и с вероятностью 50% оказываются в памяти, задержа обращения к которой 98 тактов. Считаем, что к памяти процессор обращается только в случае промаха, поэтому задержка промаха = 2 + 98 = 100 тактов. Средняя задержка = 2·50% + 100·50% = 51 такт. Пусть добавили префетчер, имеющий в среднем успешность прогноза 70%. Таким образом 70% того, что раньше оказывалось в памяти теперь заранее попадает в кэш (для простоты полагаем, что мгновенно и не вытесняя тех данных, что уже есть в кэше). Итоговые вероятности будут уже не 50/50, а 50 + 0.7·50 и 50 – 0.7·50, т.е. 85% и 15%. Средняя задержка с таким префетчером = 2·85% + 100·15% ≈ 17 тактов, т.е. ускорение втрое.

Упражнение. Посчитайте ускорение от префетчера со средней успешностью прогноза 95%.

Характеристики различных уровней памяти

В качестве примера взят процессор Intel Core i7-4790K, работающий на базовой частоте 4ГГц. Первые три строчки таблицы дают характеристики в расчёте на одно ядро.

Замечания

0. Необходимо различать две независимые и по-своему важные характеристики “скорости” работы: задержку (т.е. через какое время после начала операции она будет завершена) и пропускную способность (сколько операций в “устоявшемся потоке” завершается за единицу времени).
1. Пропускная способность для регистров указана из соображений количества операций, которые теоретически могут быть выполнены процессором с регистрами общего назначения (ширина 64 бита, нижняя граница) и регистрами AVX (ширина 256 бит, верхняя граница).
2. Пропускная способность указана в “десятичных” мегабайтах (миллион байт) и гигабайтах (миллиард байт). Для кэшей указана суммарная пропускная способность в обе стороны. Для уровней выше HDD указана теоретическая пиковая пропускная способность (реальная ниже). Для HDD указана характерная пропускная способность при передаче больших блоков данных.
3. Дополнительная микросхема eDRAM (также называемая “кэшем L4”) ставится далеко не во все системы и модели процессоров. В случае x86-систем это довольно редкий элемент (в частности, в состав Core i7-4790K он не входит), обычно предназначенный для хранения данных интегрированного графического процессора, требующего высокую пропускную способность памяти. В таблице приведены данные eDRAM Intel Crystalwell.
4. Двухканальная память DDR3-1600, данные задержки при случайном доступе из результатов реального тестирования.
5. Высокопроизводительное устройство (видеокарта или твёрдотельный накопитель) на шине PCI Express 3.0 x16. Реальные задержки при обращении центрального процессора к видеопамяти могут быть очень разными (вплоть до десятков миллисекунд).
6. Приведены приближённые характеристики кэша носителя данных, подключаемого через интерфейс SATA 3.0.

Принципы работы кэшей

Ряд описанных ниже терминов и механизмов работы могут применяться не только к реализованным “в кремнии” кэшам процессоров, но и к кэшам вообще, например, программно организованным кэшам дисковых систем (оперативная память используется операционной системой в роли кэша для носителей данных), систем управления базами данных (кэширование отдельных таблиц и результатов запросов), веб-серверов (кэширование отвертов на HTTP-запросы).

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

Пусть память заполнена байтами с кодом 11₁₆. Сам кэш первоначально заполнен нулями.

Предположим, что были выполнены загрузки байт по адресам (все числа в шестнадцатеричной записи) 6A2 (строка 6A), BC0 (строка BC), 1388–1398 (строки 138 и 139) и запись байтов FF по адресам 6A2–6A4 (строка 6A), 60EC–60F3 (строки 60E и 60F) и 12C0 (строка 12C).

Номер строки памяти (12 старших бит адреса байта), которой соответствует строка кэша вычисляется как конкатенация тега (8 бит) и номера строки кэша (4 бита). Таким образом, строка памяти 6A отображается в строку кэша A (тег 6), строка BC в строку кэша C (тег B), строка 138 в строку 8 (тег 13) и т.д.

Итак, например, запрашивается байт по адресу 60F0. Получаем номер строки F и номер байта в строке 0 (младшая часть адреса в массиве строк). Если байт находится в кэше, то тег строки F должен совпасть со старшей частью адреса (60).

Запись по адресу 12C0 приводит к вытеснению из кэша ранее загруженной конфликтующей строки BC при том, что больше половины строк кэша остались незадействованными.

У строки A флаг dirty снят потому что наш виртуальный процессор уже записал эту изменённую строку в память.

Рассмотрим пример ложного разделения данных. Пусть дан массив из 1’000’000 чисел двойной точности (каждое число имеет размер 8 байт, так что восьмёрка чисел укладывается в строку кэша шириной 64 байта) и 4 ядра. Все значения можно обрабатывать независимо от других.

Вариант 1: “плохой”. Каждое ядро обрабатывает элемент с индексом, остаток от деления которого на 4 равен номеру ядра (0–3). В результате имеем, что в каждой строке памяти (кроме, возможно, первой и последней) находятся ровно по два элемента, обрабатываемых каждым ядром, т.е. каждую строку разделяют все четыре ядра, при том что работают они с разными данными.

Вариант 2: “хороший”. Разбить массив на четыре непрерывных участка и назначить каждый одному ядру: ядро 0 обрабатывает элементы 0–249’999, ядро 1 — элементы 250’000–499’999, ядро 2 — элементы 500’000–749’999, наконец, ядро 3 — элементы 750’000–999’999. Ложное разделение возможно только в трёх строчках на границах участков, что не оказывает заметного влияния на время работы.

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

• modified: строка отображена только в этот кэш (нет разделения данных) и установлен флаг dirty (т.е. внесены изменения в кэш, но не в основную память). После записи данных в память строка кэша переходит в состояние exclusive;
• exclusive: строка отображена только в этот кэш (нет разделения данных) и соответствует данным в памяти;
• shared: строка отображена также и в другие кэши (есть разделение данных) и соответствует данным в памяти. В случае модификации такой строки, кэш захватывает владение ею — копии в других кэшах переходят в состояние invalid;
• invalid: строка не используется (снят флаг valid).

Реализация протокола определяет набор сообщений, которыми обмениваются ядра или процессоры, и схему переходов между состояниями строк кэша, а также сопутствующих действий (в виде конечного автомата). Современные версии данного протокола обычно вводят дополнительные состояния с целью увеличения быстродействия (соответственно, используются такие названия как “протокол MOESI”, “протокол MESIF”, протокол “MERSI” и т.п.).

В результате того, что применяются подобные сложные механизмы как обеспечения когерентности, так и повышения быстродействия, особенно из-за наличия более одного уровня кэшей, реальный порядок операций чтения и записи фрагментов физической памяти (DRAM) может не совпадать с тем порядком, который прописан в программе (в машинном коде). Обычная последовательная программа не “замечает” этого, однако программы, взаимодействующие с устройствами через память или содержащие другие элементы параллелизма (задействующие более одного ядра или процессора), могут работать непредсказуемо из-за того, что реальный порядок действий не соответствует порядку, записанному в программе, либо когда происходит наложение действий, воспринимаемых как элементарные, но таковыми не являющимися (“увеличить счётчик на единицу” = три действия: считать из памяти значение в регистр, увеличить регистр на единицу, записать регистр в память). Для борьбы с возникающими нежелательными эффектами используются механизмы синхронизации: атомарные операции, барьеры чтения, записи и чтения-записи (специальные команды процессора, гарантирующие, что после них все начатые ранее операции чтения и/или записи завершены), мьютексы и т.д.

Малая ассоциативность фиксированного уровня — наиболее популярный промежуточный вариант. Такие кэши по-английски называют n-way associative cache, где n > 1 (ассоциативность n). Таким образом, можно сказать, что кэш разбивается на n “путей” (по-русски их также называют “каналами”), по сути являющихся обычными кэшами с прямым отображением, но дополнительными битами в теге, каждый из которых может содержать нужную строку. При выборки строки происходит параллельная выборка по всем путям и проверка тегов. При загрузке строки из памяти для её размещения выбирается один путь (в соответствии с некоторой стратегией вытеснения).

Вернёмся к примеру кэша, приведённому выше. Теперь наш кэш будет содержать два пути 2-way associative cache. Общий объём оставим тем же, что и раньше, поэтому придётся увиличить тег на один бит (этот дополнительный бит указывается особо после апострофа).

Вновь предположим, что были выполнены загрузки байт по адресам (все числа в шестнадцатеричной записи) 6A2 (строка 6A), BC0 (строка BC), 1388–1398 (строки 138 и 139) и запись байтов FF по адресам 6A2–6A4 (строка 6A), 60EC–60F3 (строки 60E и 60F) и 12C0 (строка 12C). Младшие три бита номера строки памяти определяют номер строки кэша, девять старших бит определяют тег строки, загруженной в кэш. Два пути позволяют разместить в кэше до двух строк памяти с совпадающими младшими тремя битами.

На этот раз вытеснения строки BC не произошло. Вместо этого строка 12C была помещена на второй путь.

Наконец, то же самое можно продемонстрировать для четырёх путей. Теперь тег содержит 10 бит, 2 младших бита указаны через апостроф.

Путь 3 остался незадействованным.

Некоторые стратегии вытеснения, применяемые в процессорных кэшах:

• LRU (англ. least recently used) — вытеснять строку, с последнего обращения к которой прошло больше всего времени. В случае двух путей реализуется очень просто с помощью одного дополнительного бита флагов на каждый набор из двух строк (с совпадающими индексами на двух путях), который устанавливается или снимается в зависимости от того, к какому пути происходит обращение.
• PLRU (pseudo LRU) — упрощённый вариант LRU для кэшей с большим количеством путей. Вытесняется любая строка кроме последней использованной.
• MRU (most recently used) — подход, обратный LRU. Вытесняется самая “свежая” строка. На некоторых видах нагрузки превосходит LRU по количеству попаданий.
• LFU (least frequently used) — вытеснять строку, к которой было меньше всего обращений. Для определения количества обращений к каждой строке надо добавить счётчик обращений. Обычно данный метод комбинируется с другими (например, LRU и RR), так как “в чистом виде” неэффективен.
• RR (random replacement) — выбирать строку для вытеснения (псевдо)случайным образом. Весьма прост в реализации, при этом на реальных нагрузках демонстрирует приемлемую эффективность. Данный метод также хорош как элемент комбинированной, например, с LFU или с PLRU стратегии выбора, и используется для выбора из набора строк, имеющих одинаковые шансы на вытеснение.

Виртуальная память

Типичным способом организации работы на компьютерах 50-х и 60-х годов была пакетная обработка batch processing: на вход подавался список команд (задач tasks), каждая из которых запускала некоторую программу. Все они исполнялись строго по очереди. Недостатком такого подхода было отсутствие интерактивности: чтобы работать с компьютером, надо было заранее подготовить все входные данные (и, возможно, собственно программу), встать в расписание работы и затем прийти за результатом в назначенное время. В случае возникновения ошибок приходилось повторять всю процедуру заново. Для планирования работ в таком режиме большую сложность представляло неопределённое время исполнения каждой задачи — если время работы задачи превышало заранее выделенный лимит, оператор просто прерывал её.

Поэтому естественным шагом было создание операционных систем, позволяющих имитировать одновременное исполнение нескольких задач в интерактивном режиме, так, чтобы, с одной стороны, одна задача не могла занимать весь вычислительный ресурс, и, с другой стороны, пользователь мог работать с компьютером в диалоговом режиме, немедленно получая информацию о результатах. Такие системы стали называть системами с разделением времени time-sharing systems. Одним из первых их представителей стала разработанная в MIT и представленная в 1961г. система Compatible Time-Sharing System (CTSS). Под “совместимостью” (“compatible”) понималась совместимость с более ранней системой пакетной обработки Fortran Monitor System (FMS) компьютера IBM 7094, которая достигалась запуском FMS в качестве отдельной задачи.

Принцип разделения времени заключается в том, что создаётся список активных запущенных программ (задач), и система (точнее, её компонент под названием планировщик задач task scheduler) поочерёдно запускает каждую из них на короткий промежуток времени (“квант” или “слот” времени time slice). Само событие смены одной задачи на другую называется переключением контекста context switch и является достаточно довольно по процессорному времени операцией.

При частом переключении между задачами создаётся впечатление одновременного их исполнения. Если же компьютерная система обладает несколькими процессорами и действительно способна одновременно исполнять несколько программ, то на системе с разделением времени это можно сделать “прозрачно” для пользователя. При наличии множества задач параллельные системы демонстрируют высокую эффективность, даже если каждая задача исполняется только на одном процессоре. Другим преимуществом системы разделения времени является достаточно легко реализуемая возможность приостановить выполнение любой задачи “по середине” и отложить её на неопределённый срок, сохранив её состояние на внешний носитель (например, диск), а потом запустить, загрузив с диска.

Но даже при имитации одновременного исполнения задач ряд из них желательно держать в оперативной памяти компьютера одновременно, так как быстродействие дисковых (или, тем более, ленточных) систем всегда было на порядки ниже быстродействия оперативной памяти — переключение между задачами с обязательным сохранением и загрузкой состояния было бы непозволительно медленным (впрочем, CTSS как раз сохраняла состояние задач на ленту — объём доступной оперативной памяти ранних компьютеров был слишком мал для нескольких задач).

Так возникла проблема распределения оперативной памяти компьютера между задачами, а также защиты данных одних задач от повреждения другими задачами (без всякого злого умысла — достаточно ошибок в программах, чтобы они пытались изменять не свои участки памяти). Кроме того, так как одновременно с компьютером могло работать несколько пользователей, понятие “пользователь” и принадлежность данных (файлов) и задач конкретному пользователю должны поддерживаться на уровне операционной системы.

Разрешить возникающие конфликты можно с помощью добавления промежуточного уровня, который будет имитировать компьютер, полностью доступный программе. Данный подход называется виртуализацией. При виртуализации устройств, памяти или компьютера целиком происходит перехват обращений программ к виртуализированным устройствам (на уровне ОС или также с использованием аппаратных средств) и разрешение конфликтов “на лету”. В данном разделе рассматривается виртуализация памяти, которая является основным разделяемым ресурсом системы.

Виртуализация памяти (виртуальная память virtual memory) позволяет решить проблему распределения и защиты (данных в) памяти memory protection — каждая программа “видит” только свою виртуальную память (виртуальное адресное пространство), а система отображает виртуальные адреса в реальные — в физическое адресное пространство (эта операция называется трансляцией адресов).

В системе MULTICS (и затем “по наследству” в Unix), которая разрабатывалась в MIT и AT&T Bell Labs на замену CTSS задачи (называемые процессами) могли сосуществовать в одной физической памяти, разделённые с помощью механизма виртуальной памяти. (Подробнее о CTSS, а также об истории разработки Unix и MULTICS можно прочитать, например, здесь и здесь.) Управлением назначением диапазонов виртуальной памяти и выделением их процессам занимается компонент ОС, называемый менеджером виртуальной памяти virtual memory manager. Устройство, выполняющее трансляцию адресов (обычно это выполняется аппаратно), называется устройством управления памятью memory management unit (MMU).

Наиболее популярным способом организации виртуальной памяти является страничная виртуальная память. Адресное пространство (и виртуальное и физическое) делится на блоки одинакового размера — страницы. Для каждого процесса создаётся таблица соответствий адресов страниц виртуальной памяти страницам физической памяти — таблица страниц page table. Каждой странице может быть сопоставлена дополнительная информация: например, “только для чтения”, “можно исполнять как машинный код”, “хранится на диске” и т.д., что позволяет не только управлять доступом к собственно памяти, но и отображать в виртуальную память содержимое файлов, память устройств, память других процессоров.

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

Рассмотрим простой пример. Пусть виртуальная и физическая память используют 32-битные адреса. Размер страницы зададим в 64 кб. Таким образом, адрес страницы задаётся старшими 16 битами адреса, а смещение данных внутри страницы — младшими 16 битами адресами, т.е. младшие 16 бит виртуального и физического байта всегда совпадают. Пусть есть два процесса, которые в числе прочих выделенных страниц разделяют одну страницу физической памяти (в целях осуществления обмена данными между ними).

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

В случае больших адресных пространств может быть нецелесообразным использовать строго одну таблицу страниц на процесс. Например, стандартный размер страницы на архитектуре x86-32 (i386) — 4 кб, адрес 32 бита (адресное пространство 4 Гб), т.е. всего страниц может быть немногим более миллиона. Создавать на каждый процесс таблицу с миллионом элементов означает затрачивать по 16 Мб реальной памяти на процесс. И это при том, что первые компьютеры с i386 снабжались всего лишь 1–8 Мб оперативной памяти. Конечно, относительно простым решением могло бы быть использование таблиц меньшего размера с сохранением размера текущей таблицы в специальный регистр (так как переводом виртуальных адресов в физические занимается сам процессор). Однако в случае архитектуры x86 был выбран другой подход: вместо одной таблицы создаются иерархические структуры из директорий directories — тоже таблиц, но уже не таблиц страниц, а таблиц других директорий или таблиц страниц. Виртуальный адрес разбивается на несколько частей, определяющих элементы директорий и страницу в конкретной таблице.

Ниже в качестве примера приведена иерархия таблиц, применяемая на современной архитектуре x86-64.

Архитектура x86-64 оперирует 64-битными виртуальными адресами, в которых старшие 16 бит зарезервированы, а в качестве собственно адреса используются младшие 48 бит, что даёт 256 Тб виртуального адресного пространства. Доступны три размера страниц: 4 кб (3 уровня директорий), 2 Мб (2 уровня директорий), 1 Гб (1 уровень). Каждая директория и таблица содержит 512 элементов.

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

Такая схема работы отражается на структуре кэшей. Во-первых, кэши L1 обычно используют виртуальные адреса, а не физические, чтобы при обращении к ним вообще не требовалось проходить через сложный процесс трансляции. Во-вторых, сами директории и таблицы страниц в высокопроизводительных процессорах кэшируются в отдельных кэшах, называемых TLB (“translation lookaside buffer”). Во многих процессорах эти кэши делятся на уровни (обычно только два), и L1 TLB также как “обычный” L1 (и по тем же причинам) разделяется на два буфера — отдельно для инструкций (ITLB) и для данных (DTLB). Промах в TLB может вызвать прерывание и обращение к ОС.

Если в процессе трансляции адреса оказывается, что нужной страницы нет в памяти, возникает особая ситуация, называемая ошибкой страницы page fault (PF), которая обрабатывается ОС (например, выполняется загрузка нужной страницы из своп-файла). Чем меньше уровней в иерархии таблиц страниц, тем быстрее обрабатывается PF. В целом, использование свободной физической памяти операционной системой с поддержкой виртуальной памяти во многом напоминает схему работы кэша: редко используемые страницы записываются (“вытесняются”) на диск (в своп-файл) и загружаются оттуда в случае попытки доступа к ним, вытесняя в своп другие страницы (отсюда термин “своп” от англ. swap — обмен). Операционные системы применяют различные стратегии вытеснения с целью уменьшения среднего числа обращений к своп-файлу.

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

Так как каждый “полноценный” процесс является владельцем различных ресурсов, выделяемых системой, главным из которых является собственное адресное пространство и таблицы страниц, то создавать и переключать процессы довольно дорого. Поэтому современные ОС предлагают альтернативу: “лёгкие” процессы lightweight processes, чаще называемые потоки или нити threads.

Каждая нить привязана к некоторому процессу, при этом каждый процесс содержит по крайней мере одну нить, в которой выполняется его код. Нить владеет своим стеком вызовов и хранилищем локальных данных (TLS), а часто и своей секцией кучи (для ускорения операций с динамической памятью). Все нити разделяют владение ресурсами, которыми владеет родительский для них процесс, и главное — существуют в общем адресном пространстве виртуальной памяти этого процесса, что очень упрощает обмен данными между ними. Переключение ядра процессора между нитями одного процесса может выполняться намного быстрее, чем между разными процессами.

Рекомендации

1. Объекты лучше создавать в автоматической памяти, а не в динамической.
2. Массив лучше списка или дерева на основе объектов, связанных указателями.
3. Перебирать элементы массивов лучше наиболее регулярным доступным способом:
   • с единичным шагом (по очереди), чем с неединичным (пропуская элементы);
   • с постоянным шагом (например, каждый третий), чем с переменным;
   • с малым шагом, а не большим (чем меньше шаг, тем лучше);
   • с линейно изменяющимся шагом (например, увеличивающимся на два на каждой итерации), чем со случайно изменяющимся.
4. Повышать локальность данных: обрабатывать данные лучше поочерёдно (или параллельно) полностью небольшими блоками, чем выполнять последовательные операции на больших наборах. В частности, массивы структур обычно лучше, чем структуры массивов. Эффект локальности, например, хорошо сказывается при сравнении реальной скорости работы алгоритмов быстрой сортировки (высокая локальность) и пирамидальной сортировки (низкая локальность). Последняя обычно на порядок медленнее первой. Однако эту рекомендацию надо рассматривать в сочетании с другими возможностями оптимизации используемых операций. Например, последовательная обработка числовых массивов с применением векторных операций может быть наиболее эффективным методом.
5. Минимизировать разделяемые и глобальные данные. Автоматические и статические локальные переменные лучше глобальных.

Общее оглавление

Кувшинов Д.Р. © 2015