До версии 3BSD большинство систем UNIX основывались на свопинге (подкачке), работавшем следующим образом. Когда загружалось больше процессов, чем могло поместиться в памяти, некоторые из них выгружались на диск. Выгружаемый процесс всегда выгружался на диск целиком (исключение представляли только совместно используемые текстовые сегменты). Таким образом, процесс мог быть либо в памяти, либо на диске.
Перемещением данных между памятью и диском управлял верхний уровень двухуровневого планировщика, называвшийся свопером (swapper). Выгрузка данных из памяти на диск инициировалась, когда у ядра кончалась свободная память из-за одного из следующих событий:
1. Системному вызову fork требовалась память для дочернего процесса.
2. Системный вызов brk собирался расширить сегмент данных.
3. Разросшемуся стеку требовалась дополнительная память.
Кроме того, когда наступало время запустить процесс, уже достаточно долго находящийся на диске, часто бывало необходимо удалить из памяти другой процесс, чтобы освободить место для запускаемого процесса. Выбирая процесс, который необходимо было удалить из памяти, свопер сначала рассматривал блокированные (например, ожиданием ввода с терминала) процессы. Лучше удалить из памяти процесс, который не может работать, чем работоспособный процесс. Если такие процессы находились, из них выбирался процесс с наивысшим значением суммы приоритета и времени пребывания в памяти. Таким образом, подвергались выгрузки процессы, потребившие большое количество процессорного времени или находящиеся в памяти уже достаточно долгое время. Если блокированных процессов не было, тогда на основе тех же критериев выбирался готовый процесс.
|
|
Каждые несколько секунд свопер исследовал список выгруженных процессов, проверяя, не готов ли какой-либо из этих процессов к работе. Если процессы в состоянии готовности обнаруживались, из них выбирался процесс, дольше всех находящийся на диске. Затем свопер проверял, будет ли это легкий свопинг или тяжелый. Легким свопингом считался тот, для которого не требовалось дополнительное высвобождение памяти. При этом нужно было всего лишь загрузить выгруженный на диск процесс. Тяжелым свопингом назывался свопинг, при котором для загрузки в память выгруженного на диск процесса из нее требовалось удалить один или несколько других процессов. Затем весь этот алгоритм повторялся до тех пор, пока не выполнялось одно из следующих двух условий: на диске не оставалось процессов, готовых к работе, или в памяти не оставалось места для новых процессов. Чтобы не терять большую часть производительности системы на свопинг, ни один процесс не выгружался на диск, если он пробыл в памяти менее 2 с. Свободное место в памяти и на устройстве перекачки учитывалось при помощи связного списка свободных пространств. Когда требовалось свободное пространство в памяти или на диске, из списка выбиралось первое подходящее свободное пространство. После этого в список возвращался остаток от свободного пространства.
|
|
Начиная с версии 3BSD к системе была добавлена страничная подкачка, чтобы предоставить возможность работать с программами больших размеров. Практически во всех версиях системы UNIX теперь есть страничная подкачка по требованию, появившаяся впервые в версии 3BSD. Ниже описывается реализация этого механизма в версии 4BSD. Такая реализация во многом соответствует и версии System V, которая основана на 4BSD.
Идея, лежащая в основе страничной подкачки в системе 4BSD, состоит в том, что процессу для работы не нужно целиком находиться в памяти. Все, что в действительности требуется, – это структура пользователя и таблицы страниц. Если они загружены, то процесс считается находящимся в памяти и может быть запущен планировщиком. Страницы с сегментами текста, данных и стека загружаются в память динамически, по мере обращения к ним. Если пользовательской структуры и таблицы страниц нет в памяти, то процесс не может быть запущен, пока свопер не загрузит их.
Страничная подкачка реализуется частично ядром и частично новым процессом, называемым страничным демоном. Как и все демоны, страничный демон периодически запускается и смотрит, есть ли для него работа. Если он обнаруживает, что количество страниц в списке свободных страниц слишком мало, страничный демон инициирует действия по освобождению дополнительных страниц.
Память в 4BSD делится на три части. Первые две части, ядро операционной системы и карта памяти, фиксированы в физической памяти (то есть никогда не выгружаются). Остальная память машины делится на страничные блоки, каждый из которых может содержать либо страницу текста, данных или стека, либо находиться в списке свободных страниц.
Карта памяти содержит информацию о содержимом страничных блоков. Для каждого страничного блока в карте памяти есть запись фиксированной длины. При килобайтных страничных блоках и 16-байтовых записях карты памяти на нее расходуется менее 2 % от общего объема памяти. Первые два поля записи карты памяти используются только тогда, когда соответствующий страничный блок находится в списке свободных страниц. В этом случае они сшивают свободные страницы в двусвязный список. Следующие три записи используются, когда страничный блок содержит информацию. У каждой страницы в памяти есть фиксированное место хранения на диске, в которое она помещается, когда выгружается из памяти. Еще три поля содержат ссылку на запись в таблице процессов, тип хранящегося в странице сегмента и смещение в сегменте процесса. Последнее поле содержит некоторые флаги, нужные для алгоритма страничной подкачки. При запуске процесс может вызвать страничное прерывание, если одной или нескольких его страниц не окажется в памяти. При страничном прерывании операционная система берет первый страничный блок из списка свободных страниц, удаляет его из списка и считывает в него требуемую страницу. Если список свободных страниц пуст, выполнение процесса приостанавливается до тех пор, пока страничный демон не освободит страничный блок.
Алгоритм замещения страниц выполняется страничным демоном. Раз в 250 мс он сравнивает количество свободных страничных блоков с системным параметром lotsfree (равным, как правило, 1/4 объема памяти). Если число свободных страничных блоков меньше, чем значение этого параметра, страничный демон начинает переносить страницы из памяти на диск, пока количество свободных страничных блоков не станет равно lotsfree. Если же количество свободных страничных блоков больше или равно lotsfree, тогда страничный демон ничего не предпринимает. Если в машине много памяти и мало активных процессов, страничный демон практически все время бездействует.
|
|
Страничный демон использует модифицированную версию алгоритма часов. Это глобальный алгоритм, то есть при удалении страницы он не учитывает, чья это страница. Таким образом, количество страниц, выделяемых каждому процессу, меняется со временем. Основной алгоритм часов работает, сканируя в цикле страничные блоки (как если бы они лежали на окружности циферблата часов). На первом проходе, когда стрелка часов указывает на страничный блок, сбрасывается его бит использования. На втором проходе у каждого страничного блока, к которому не было доступа с момента первого прохода, бит использования останется сброшенным, и этот страничный блок будет помещен в список свободных страниц. Страничный блок в списке свободных страниц сохраняет свое содержание, что позволяет восстановить страницу, если она потребуется прежде, чем будет перезаписана.
Изначально в версии UNIX 4BSD использовался основной алгоритм часов, но затем он был заменен более эффективным алгоритмом часов с двумя стрелками. В этом алгоритме страничный демон поддерживает два указателя на карту памяти. При работе он сначала очищает бит использования передней стрелкой, а затем проверяет этот бит задней стрелкой. После чего перемещает обе стрелки. Если две стрелки находятся близко друг от друга, то только у очень активно используемых страниц появляется шанс, что к ним будет обращение между проходами двух стрелок. Если же стрелки разнесены на 359 градусов (то есть задняя стрелка находится слегка впереди передней), то по сути снова получается исходный алгоритм часов. При каждом запуске страничного демона стрелки проходят не полный оборот, а столько, сколько необходимо, чтобы количество страниц в списке свободных страниц было не менее lotsfree.
|
|
Если операционная система обнаруживает, что частота подкачки страниц слишком высока, а количество свободных страниц все время ниже lotsfree, свопер начинает удалять из памяти один или несколько процессов, чтобы остановить состязание за свободные страничные блоки. Свопинг в системе 4BSD осуществляется по следующему алгоритму. Сначала свопер проверяет, есть ли процесс, который бездействовал в течение 20 и более секунд. Если такие процессы есть, из них выбирается бездействовавший в течение максимального срока и выгружается на диск. Если таких процессов нет, изучаются четыре самых больших процесса, из которых выбирается тот, который находился в памяти дольше всех, и выгружается на диск. При необходимости этот алгоритм повторяется до тех пор, пока не будет высвобождено достаточное количество памяти.
Каждые несколько секунд свопер проверяет, есть ли на диске готовые процессы, которые следует загрузить в память. Каждому процессу на диске присваивается значение, зависящее от времени его пребывания в выгруженном состоянии, размера, значения, использовавшегося при обращении к системному вызову nice (если такое обращение было), и от того, как долго этот процесс бездействовал, прежде чем был выгружен на диск. Эта функция обычно взвешивается так, чтобы загружать в память процесс, дольше всех находящийся в выгруженном состоянии, если только он не крайне большой. Теория утверждает, что загружать большие процессы дорого, поэтому их не следует перемещать с диска в память и обратно слишком часто. Загрузка процесса производится только при условии наличия достаточного количества свободных страниц, чтобы, когда случится неизбежное страничное прерывание, для него нашлись свободные страничные блоки. Свопер загружает в память только структуру пользователя и таблицы страниц. Страницы с текстом, данными и стеком подгружаются при помощи обычной страничной подкачки.
У каждого сегмента каждого активного процесса есть место на диске, где он располагается, когда его страницы удаляются из памяти. Сегменты данных и стека сохраняются на временном устройстве, но текст программы подгружается из самого исполняемого двоичного файла. Для текста программы временная копия не используется.
Страничная подкачка в версии System V во многом схожа с применяемой в системе 4BSD, но тем не менее между этими версиями операционной системы есть интересные различия. Во-первых, в System V вместо алгоритма часов с двумя стрелками используется оригинальный алгоритм часов с одной стрелкой. Более того, вместо того чтобы помещать страницу в список свободных страниц на втором проходе, страница помещается туда только в случае, если она не использовалась в течение нескольких последовательных проходов. Хотя при таком решении страницы не освобождаются так быстро, как это делается алгоритмом в 4BSD, оно значительно увеличивает вероятность того, что освобожденная страница не потребуется тут же снова. Во-вторых, вместо единственной переменной lotsfree в System V используются две переменные: min и max. Когда количество свободных страниц опускается ниже min, страничный демон начинает освобождать страницы. Демон продолжает работать до тех пор, пока число свободных страниц не сравняется со значением max. Такой подход позволяет избежать неустойчивости, возможной в системе 4DSD, например, в ситуации, когда количество свободных страниц на единицу меньше, чем lotsfree. При этом страничный демон освобождает одну страницу, чтобы привести количество свободных страниц в соответствие со значением lotsfree. Затем происходит еще одно страничное прерывание, и количество свободных страниц опять становится на единицу меньше lotsfree, в результате страничный демон снова начинает работать. Если установить значение max существенно большим, чем min, страничный демон, завершив освобождение страниц, создает достаточный запас для своего бездействмя в течение относительно продолжительного времени.
7.4. Ввод-вывод в системе UNIX