Алгоритм - замещение - страница
Cтраница 1
 |
Карта памяти в 4BSD. [1] |
Алгоритм замещения страниц выполняется страничным демоном. [2]
Алгоритм замещения страниц работает следующим образом. Система Linux пытается поддерживать некоторые страницы свободными, чтобы их можно было предоставить при необходимости. Конечно, этот пул страниц должен постоянно пополняться, поэтому реальный алгоритм страничной подкачки заключается в том, как это происходит. Во время загрузки процесс init запускает страничный демон kswapd, который работает раз в секунду. Он проверяет, есть ли достаточное количество свободных страниц. Если да, он отправляется спать еще секунду, хотя он может быть разбужен и раньше, если внезапно понадобятся дополнительные страницы. Страничный демон состоит из цикла, который выполняется до шести раз с возрастающей срочностью. Вероятно, автор программы думал, что четырех будет недостаточно, а восемь будет слишком много. В отдельных местах операционная система Linux реализована именно так. [3]
 |
Карта памяти в 4BSD. [4] |
Алгоритм замещения страниц выполняется страничным демоном. [5]
Алгоритм замещения страниц работает следующим образом. Система Linux пытается поддерживать некоторые страницы свободными, чтобы их можно было предоставить при необходимости. Конечно, этот пул страниц должен постоянно пополняться, поэтому реальный алгоритм страничной подкачки заключается в том, как это происходит. Во время загрузки процесс init запускает страничный демон kswapd, который работает раз в секунду. Он проверяет, есть ли достаточное количество свободных страниц. Если да, он отправляется спать еще секунду, хотя он может быть разбужен и раньше, если внезапно понадобятся дополнительные страницы. Страничный демон состоит из цикла, который выполняется до шести раз с возрастающей срочностью. Вероятно, автор программы думал, что четырех будет недостаточно, а восемь будет слишком много. В отдельных местах операционная система Linux реализована именно так. [6]
Работу алгоритмов замещения страниц обычно проверяют путем моделирования. Предположим, что вам нужно написать моделирующую программу для виртуальной памяти со страничной организацией для машины, содержащей 64 страницы по 1 Кбайт. Программа должна поддерживать одну таблицу из 64 элементов, один элемент на страницу. Каждый элемент таблицы содержит номер физической страницы, который соответствует данной виртуальной странице. Моделирующая программа должна считывать файл, содержащий виртуальные адреса в десятичной системе счисления, по одному адресу на строку. Если соответствующая страница находится в памяти, просто записывайте наличие страницы. Если ее нет в памяти, вызовите процедуру замещения страниц, чтобы выбрать страницу, которую можно выкинуть ( то есть элемент таблицы, который нужно переписать), и записывайте отсутствие страницы. Никакой передачи страниц не происходит. Создайте файл, состоящий из непоследовательных адресов, и проверьте производительность работы двух алгоритмов: LRU и FIFO. А теперь создайте файл адресов, в котором х процентов адресов находятся на 4 байта выше, чем предыдущие. [7]
Теперь рассмотрим алгоритм замещения страниц, основанный на рабочем наборе. Его базовая идея заключается в том, чтобы найти страницу, не включенную в рабочий набор, и выгрузить ее. На рис. 4.20 изображена часть таблицы страниц для некоторой машины. Поскольку в качестве кандидатов на удаление рассматриваются только те страницы, которые в настоящее время находятся в памяти, отсутствующие в памяти страницы этим алгоритмом игнорируются. [8]
Если используется алгоритм замещения страниц FIFO в системе с четырьмя страничными блоками и восемью страницами, сколько страничных прерываний произойдет для последовательности обращений 0172327103 при условии, что четыре страничных блока изначально пусты. [9]
Как видно, алгоритм замещения страниц этим пытается заглянуть в будущее. [10]
В ходе рассмотрения алгоритмов замещения страниц мы видели, как выбирается страница для удаления. Мы почти ничего не сказали о том, в какое место на диске она помещается после выгрузки из памяти. [11]
 |
Частота страничных прерываний как функция от количества предоставленных процессу страничных блоков. [12] |
Важно отметить, что некоторые алгоритмы замещения страниц могут работать как с локальной политикой замещения страниц, так и с глобальной. Выбор между локальной и глобальной политикой в некоторых случаях не зависит от алгоритма. [13]
В системе управления виртуальной памятью - алгоритм замещения страниц ( сегментов), при использовании которого откачиваются страницы, обращения к которым происходят наименее часто. [14]
С другой стороны, для некоторых алгоритмов замещения страниц имеет смысл только локальная стратегия. В частности, алгоритмы рабочий набор и WSClock относятся к конкретному процессу и должны применяться именно в этом контексте. Реально для машины в целом не существует понятия рабочего набора, и если попытаться использовать объединение всех рабочих наборов, то это непременно приведет к потере характерных свойств и хорошо работать не будет. [15]
Страницы: 1 2 3