Какую стратегию управления памятью может реализовать алгоритм выталкивания страниц lru

Обновлено: 06.07.2024

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

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

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

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

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

Свойство локальности проявляется как во времени, так и в пространстве.

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


Локальность в пространстве означает, что обращения к памяти, как правило, концентрируются так, что в случае обращения к некоторой ячейке памяти с большой вероятностью можно ожидать обращение к близлежащим ячейкам.

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

Для оценивания эффективности стратегий управления памятью в операционных системах применяют показатель “пространство-время”, вычисляемый по формуле

где S - показатель “пространство-время”; V - объем первичной памяти, занимаемый процессом; T - длительность ожидания процессом подкачки необходимой страницы или сегмента.

Уменьшение значения показателя S за счет снижения периодов ожидания процессом нужных ему страниц или сегментов является важнейшей целью всех стратегий управления памятью.

Стратегии вталкивания (подкачки)

Для управления вталкиванием применяются следующие стратегии:

· вталкивание (подкачка) по запросу (по требованию);

· вталкивание (подкачка) с упреждением (опережением).

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

К положительным сторонам относятся:

  • гарантировано, что в первичную память будут переписываться только те страницы (сегменты), которые необходимы для работы процесса;
  • накладные расходы на то, чтобы определить, какие страницы или сегменты следует передавать в первичную память, минимальны.

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

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

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

Стратегии размещения

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

Для систем с сегментной организацией виртуальной памяти применяются такие же стратегии размещения, какие используются в системах распределения памяти переменными разделами (см. П.4.2), а именно:

· размещение с выбором первого подходящего свободного участка;

· размещение с выбором самого подходящего свободного участка;

· размещение с выбором наименее подходящего свободного участка.

Подробное описание действий для реализации перечисленных стратегий размещения приведено в п.4.2.3.

Стратегии выталкивания

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

  • выталкивание случайных страниц или сегментов;
  • выталкивание первой пришедшей страницы или сегмента (FIFO);
  • выталкивание дольше всего не использовавшихся страниц или сегментов (LRU);
  • выталкивание наименее часто использовавшихся страниц или сегментов (LFU);
  • выталкивание не использовавшихся в последнее время страниц или сегментов (NUR).

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

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

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

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

Стратегия выталкивания не использовавшихся в последнее время страниц или сегментов (NUR-стратегия) также является близкой к стратегии LRU и характеризуется относительно небольшими издержками на свою реализацию. Согласно NUR-стратегии из первичной памяти выталкиваются те страницы (сегменты), к которым не было обращений в последнее время. В соответствии со свойством локальности во времени (см.п.4.4.1) к страницам (сегментам), не использовавшимся в последнее время, вряд ли будет обращение в ближайшем будущем, так что их можно заменить на вновь поступающие страницы.

Поскольку желательно заменять те страницы (сегменты), которые в период нахождения в основной памяти не изменялись, реализация NUR-стратегии предусматривает введение двух аппаратных бит-признаков на страницу (сегмент):

· бит-признак b0 обращения к странице (сегменту);

· бит-признак b1 модификации страницы (сегмента).

Первоначально все b0 и b1 устанавливаются в 0. При обращении к странице (сегменту) соответствующий бит-признак b0 устанавливается в 1. В случае изменения содержимого страницы (сегмента) соответствующий бит-признак b1 устанавливается в 1. NUR-стратегия предусматривает существование четырех групп страниц (сегментов), показанных в табл. 4.5.

Таблица 4.5.Группы страниц (сегментов)

Группа b0 b1

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

Учет времени, в течение которого к страницам (сегментам) не было обращений, осуществляется периодическим сбрасыванием в 0 всех битов-признаков, выполняемым операционной системой.

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

Контрольные вопросы

1. Часто единственным достоинством виртуальной памяти называют возможность обеспечить для процесса объем виртуального адресного пространства, превышающий объем реальной памяти. Назовите другие достоинства виртуальной памяти.

2. В чем достоинства и недостатки преобразования виртуальных адресов в реальные во время выполнения программы? Какая часть работы по этому преобразованию выполняется аппаратным обеспечением, а какая - ОС?

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

4. Почему при поиске свободной памяти стратегия "самый подходящий" оказывается хуже, чем "первый подходящий".

5. Сравните сегментную и страничную модели виртуальной памяти. Какая из них представляется Вам лучшей и почему?

6. Дополните приведенные в разделе 3.5. соображения по поводу выбора размера страницы.

7. Смоделируйте ситуацию применения дисциплины вытеснения FCFS, в которой увеличение числа реальных страниц приведет к увеличению числа страничных отказов.

8. Что такое кластерная подкачка страниц? Почему в современных ОС она становится все более популярной?

9. Каким образом ОС может определять, к каким страницам будут обращения в ближайшее время?

10. Большой размер виртуальной памяти процесса может приводить к тому, что даже таблица страниц не будет помещаться в реальной памяти. Какими путями решается эта проблема в современных ОС?

11. Каким образом снижение стоимости памяти влияет на дисциплины управления памятью?

12. Какие принципиальные изменения в концепции памяти может повлечь за собой увеличение разрядности адреса?

Лекция 6. Планирование процессов

6.1 Основные понятия планирования процессов

Планирование- обеспечение поочередного доступа процессов к одному процессору.

Планировщик - отвечающая за это часть операционной системы.

Алгоритм планирования - используемый алгоритм для планирования.

Ситуации, когда необходимо планирование:

  1. Когда создается процесс
  2. Когда процесс завершает работу
  3. Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.
  4. При прерывании ввода/вывода.

Алгоритм планирования без переключений(неприоритетный) - не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу.

Алгоритм планирования с переключениями (приоритетный) - требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.

Необходимость алгоритма планирования зависит от задач, для которых будет использоваться операционная система.

Основные три системы:

  1. Системы пакетной обработки - могут использовать неприоритетный и приоритетный алгоритм (например: для расчетных программ).
  2. Интерактивные системы - могут использовать только приоритетный алгоритм, нельзя допустить чтобы один процесс занял надолго процессор (например: сервер общего доступа или персональный компьютер).
  3. Системы реального времени - могут использовать неприоритетный и приоритетный алгоритм (например: система управления автомобилем).

Задачи алгоритмов планирования:

  1. Для всех систем
    Справедливость - каждому процессу справедливую долю процессорного времени
    Контроль над выполнением принятой политики
    Баланс - поддержка занятости всех частей системы (например: чтобы были заняты процессор и устройства ввода/вывода)
  2. Системы пакетной обработки
    Пропускная способность - количество задач в час
    Оборотное время - минимизация времени на ожидание обслуживания и обработку задач.
    Использование процесса - чтобы процессор всегда был занят.
  3. Интерактивные системы
    Время отклика - быстрая реакция на запросы
    Соразмерность - выполнение ожиданий пользователя (например: пользователь не готов к долгой загрузке системы)
  4. Системы реального времени
    Окончание работы к сроку - предотвращение потери данных
    Предсказуемость - предотвращение деградации качества в мультимедийных системах (например: потерь качества звука должно быть меньше чем видео)

Планирование в системах пакетной обработки

6.2.1 "Первый пришел - первым обслужен" (FIFO - First In Fist Out)

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

Рассмотрим пример применения данного алгоритма с той же строкой запроса и с четырьмя максимально возможными фреймами у каждого процесса:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Нетрудно видеть, что будет иметь место всего 6 отказов страниц (в отличие от алгоритма FIFO с 10 отказами страниц).

Пример использования оптимального алгоритма замещения страниц с той же строкой запроса, которая применялась на рис. 18.9 для алгоритма FIFO , приведен на рис. 18.11.

Пример использования оптимального алгоритма замещения страниц.


увеличить изображение
Рис. 18.11. Пример использования оптимального алгоритма замещения страниц.

Алгоритм Least Recently Used (LRU)

Данный алгоритм замещения страниц основан на следующем принципе: Замещается та страница, которая раньше всего использовалась.

Для примера со строкой запросов: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 число отказов страниц равно всего 4.

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

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

Пример использования алгоритма замещения страниц LRU с той же строкой запроса, что и на рис. 18.9 и рис. 18.11 для других алгоритмов, приведен на рис. 18.12.

Пример использования алгоритма замещения страниц LRU.


увеличить изображение
Рис. 18.12. Пример использования алгоритма замещения страниц LRU.

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

На рис. 18.13 приведен пример использования стека в алгоритме LRU для хранения самых недавних обращений к страницам.

Использование стека в алгоритме LRU для хранения самых недавних обращений к страницам.


Рис. 18.13. Использование стека в алгоритме LRU для хранения самых недавних обращений к страницам.

Алгоритмы, близкие к LRU

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

  1. Бит ссылки (reference bit).В данном алгоритме с каждой страницей связывается бит, первоначально равный 0. При обращении к странице бит устанавливается в 1. Далее, при необходимости замещения страниц, заменяется та страница, у которой бит равен 0 (если такая существует), т.е. страница, к которой не было обращений. Данная версия алгоритма позволяет избежать поиска по таблице страниц. Однако она, очевидно, менее оптимальна, чем LRU .
  2. Второй шанс (second chance).В данной версии алгоритма используются ссылочный бит и показания часов, которые хранятся в каждом элементе таблицы страниц . Замещение страниц основано на показаниях часов. Если страница, которую следует заместить (по показаниям часов), имеет ссылочный бит, равный 1, то выполняются следующие действия:
    • Установить ссылочный бит в 0;
    • Оставить страницу в памяти;
    • Заместить следующую страницу (по показаниям часов), по тем же самым правилам.

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

Мы будем под кэшированием понимать сохранение результатов вычислений в ответ на некоторые запросы. То есть, повторный результат запроса не всегда вычисляется заново, но иногда берется из таблицы, называемой кэшем. Сложно переоценить роль кеширования в современных системах. При этом часто возникает проблема, связанная с недостатком памяти. Действительно, что делать, если запросов много, а памяти хватает лишь для хранения ограниченного числа результатов? В этом случае, как правило, кеш стрится следующим образом. Фиксируется размер кэша, пусть будет N, и сохраняются результаты только для N самых «популярных» запросов.

То есть сохраняются результаты вычислений, которые скорее всего запросят заново.
Как определять эти «популярные» запросы? Наиболее известным способом является LRU, о котором я и расскажу в этой статье.

LRU (least recently used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.

  1. Хеш-таблица hashTable, которая будет хранить непосредственно закэшированные значения.
  2. Очередь с приоритетамиtimeQueue. Структура, которая поддерживает следующие операции:
    • Добавить пару значение и приоритет timeQueue.Add(val, priority).
    • Извлечь (удалить и вернуть) значение с наименьшим приоритетом timeQueue.extractMinValue().

Предположим, что для исходных вычислений использовался метод calculate(x). Мы заменим метод calculate на новый calculateWithCache, который пополняет кеш, выталкивает устаревшие значения и запрашивает результат у calculate, если не найдет в кеше.

Так будет выглядеть алгоритм работы calculateWithCache:

Вот и все. Теперь вместо необходимости сбрасывать кэш пользователю необходимо задать размер кэша. При этом приветствуется задание разумного значения по-умолчанию.

Если воспользоваться эффективной реализацией очереди с приоритетами, то оверхед, который требует LRU — O(log N).

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

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

Можно найти более сложные эвристики, учитывающие время вычисления calculate для данного ключа key, или объем результата, или что-то еще.
Но в большинстве задач LRU наиболее адекватно определяет самые «популярные» запросы.

Примечание 1: Можно ограничить объем памяти на кэш, а не количество хранимых значений. Алгоритм практически не изменится, только вместо длины будет занимаемая память + память для хранения нового значения.
Примечание 2: Специально избегал вопросов многопоточности, так как это не тема данной статьи.

Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q

1. Стратегии управления памятью. Стратегии выталкивания страниц: выталкивание случайной страницы; выталкивание по принципам: FIFO, LRU, LFU, NUR; рабочие множества). Стратегии вталкивания (подкачка страниц по запросу; подкачка страниц с упреждением).

2. Реализация управления памятью в различных ОС (самостоятельно см. дополнительные темы докладов).

· [Дейтел 87] Дейтел Г., Введение в операционные системы. М."Мир",1987.

· [Кейлингерт 85] Кейлингерт П., Элементы операционных систем, М."Мир", 1985.

· [Кейслер 86] Кейслер С., Проектирование операционных систем для малых ЭВМ, М."Мир", 1986.

· [Колин 75] Колин А., Введение в операционные системы, М."Мир", 1975.

· [Цикритзис 77] Цикритзис Д., Бернстайн Ф., Операционные системы, М."Мир", 1977.

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

- когда осуществляется выборка новой программы в памяти: по запросам системы или с предупреждением их; (1)

- в какое место оперативной памяти будет помещаться программа: как можно более плотно с занятием свободных “дыр”, чтобы свести к минимуму потери памяти; или необходимо стремиться к возможно более быстрому размещению программы, чтобы свести к минимуму потери машинного времени; (2)

- если при размещении новой программы, оперативная память уже заполнена, то по какому критерию выводить из памяти находящиеся в ней программы: замещать в памяти программы, которые находились в ней дольше других или те, которые использовались наименее часто. (3)

В зависимости от того, как решаются эти вопросы, стратегии управления памятью делятся на следующие категории.

(1) Стратегии выборки(вталкивания):

· стратегии выборки по запросу;

· стратегии упреждающей выборки.

(2) Стратегии размещения.

(3) Стратегии замещения(выталкивания).

Применительно к системам виртуальной памяти стратегии можно подразделить следующим образом.

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

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

При размещении новых программ, поступающих в ОП реализуют, как правило одну из трех стратегий:

· стратегия наиболее подходящего, когда задание помещеют в наиболее подходящий по размеру учесток, где остается меньше свободной памяти;

· стратегия первого подходящего, когда задание размещается в первом подходящем по размеру участке;

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

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

Читайте также: