Как использование метода подкачки в ОС оправдывает накладные расходы?

Question

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

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

Чтобы процитировать книгу, которую я читаю ( Концепции ОС - Абрахам Зильбершатц, Питер Баэр Галвин, Грег Ганье, 9-е издание): «Из-за преимуществ перед более ранними методами разбиение на страницы в различных формах используется в большинстве операционных систем, от мэйнфреймов до смартфонов».

Я что-то упустил? Как использование подкачки оправдывает накладные расходы? Нам действительно нужно отслеживать каждую страницу? Учитывать ли go некоторые другие вещи при выборе правильного метода, используемого для управления памятью?

Answer 1

Пейджинг - это основа для различных «трюков с виртуальной памятью», например:

• вместо того, чтобы ждать, пока файл загрузится, прежде чем его можно будет использовать; пометьте страницы как «принадлежащие файлу с отображением в память», а затем сделайте вид, что файл был загружен (и извлеките страницы с диска, когда они действительно нужны, возможно, с некоторой стратегией предварительной выборки, происходящей в фоновом режиме). Это снижает потребление ОЗУ и может ускорить такие вещи, как время запуска исполняемого файла.

• вместо выделения реальной физической ОЗУ во время таких вещей, как запуск процесса (для его «.bss-раздела» / неинициализированные данные, «еще не использованное» пространство кучи и т. д. c), и вместо того, чтобы буквально копировать все страницы во время fork(); используйте уловки «копирование при записи», чтобы вам нужно было создавать / копировать данные только тогда, когда они действительно изменены. Это снижает потребление ОЗУ и ускоряет все (особенно, когда большая часть памяти никогда не изменяется).

• если ОЗУ недостаточно, вы можете просто отправить страницы в пространство подкачки (например, диск) и продолжайте работу. Это намного быстрее, чем ждать чего-то, что никогда не произойдет (потому что процесс упал из-за нехватки памяти).

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

Для накладных расходов ; Производители ЦП прилагают много усилий для минимизации накладных расходов (с помощью «буферов просмотра в сторону перевода», стратегий предварительной выборки, выполнения вне очереди, чтобы ЦП был занят, пока он ожидает преобразования, и т. Д. c) . Таким же образом разработчики операционных систем также стараются минимизировать накладные расходы (например, уменьшить количество переключений задач между процессами, попытаться сохранить процессы на одном ядре и т. Д. c). Это означает, что накладные расходы довольно малы по сравнению со многими большими преимуществами.

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

Я не понимаю, почему мы не можем просто разделите программу на произвольное количество сегментов каждый раз, когда мы загружаем ее в оперативную память.

Работа с разными размерами сегментов будет болезненной (меньше "сдвига и маски для поиска нужного индекса в таблице" "and more" выполните линейный поиск по всем сегментам, чтобы найти нужный сегмент "). Если вы используете сегменты фиксированного размера, это будет намного быстрее; но это и есть разбиение по страницам («страница» - это ваш «сегмент фиксированного размера»).

Answer 2

1. Разделение программы на произвольные сегменты.

Они не могут быть совершенно произвольными; например, я мог бы создать очень большой вектор для некоторого приложения:

#define N 10000000
int v[N];
....
for (i = 0; i < N; i++) {
    v[i] = ...
}

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

int *v;
v = malloc(sizeof(*v) * N);
for (i = 0; i < N; i++) {
   v[i] = ...;
}

Обоснование накладных расходов:

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

Вы можете решить эту проблему, превратив ваши скомпилированные языки в псевдоинтерпретируемые языки; но у чего больше накладных расходов: компиляция:

a = v[i];

into:
    ld R0,R1+R2*4    ; + overhead of mmu.
or:
    mov R0, R1+R2*4
    call findseg
    ld R0, R0

В общем случае накладные расходы с точки зрения ОЗУ составляют порядка 0,1%; для конкретного примера 10 байтов для страницы размером 4 КБ на архитектуре ARM64 или AMD64. lib c. Итак, в моей системе linux это около 2M текста + 40k данных; большинство программ используют очень небольшое количество этого. Благодаря подкачке памяти, только используемые биты библиотеки lib c должны занимать память. В системе 64G с 32 процессами экономия только lib c устраняет накладные расходы на таблицу страниц.

3: Отслеживание. Есть несколько способов атаковать это. Один из них - несколько размеров страницы, которые поддерживаются на большинстве архитектур. Во-вторых, ОС не обязана обеспечивать детализацию MMU. Например, в системе с 4 КБ страниц он может настаивать на передаче памяти только блоками по 64 КБ. Таким образом, уменьшаются накладные расходы на управление в 16 раз при незначительном увеличении потерь детализации.