Алгоритм - замещение
Cтраница 2
Если блок данных передается на более высокий уровень, он замещает один из блоков, находящихся на этом уровне; поэтому для каждого уровня системы памяти необходимо иметь алгоритм замещения. Исключение составляет только нижний уровень иерархической системы памяти, где данные хранятся постоянно. [16]
Страница, данные которой изменяются при работе процессора, должна храниться на уровне 1 до тех пор, пока изменение данных не будет завершено или пока страница не будет замещена в результате работы алгоритма замещения. Если же измененных данных в странице нет, то она просто затирается. В противном случае они просто затираются. [17]
Для данной программы, порождающей некоторый поток обращений к памяти, существует по крайней мере одна такая последовательность замещений страниц, которая дает минимальное для этой программы число страничных сбоев - минимально возможную последовательность замещений. При конструировании алгоритма замещений стремятся приблизить реализуемую этим алгоритмом последовательность замещений к минимальной. [18]
Время доступа к данным в многоуровневой системе памяти зависит от уровня иерархии, на котором находится запрашиваемая страница. Задача определения алгоритма замещения и организации данных заключается в максимизации вероятности нахождения страницы в момент запроса на верхних уровнях иерархической системы памяти. [19]
Следует ли знать размер листа для того, чтобы разместить элементы программы в одном и том же листе. Следует ли знать алгоритм замещения. Насколько нужно быть осторожным в выборе адресации. В общем случае, программа, спланированная под окружение с виртуальной памятью, будет работать лучше той, в которой не учитывается этот аспект машины. [20]
Тогда для ряда алгоритмов замещения ( СЗ, ИДИ, ПППУ и некото рых других) процесс изменения состояния верхнего уровня описывается однородной конечной эргодической цепью Маркова, что указывает на существование стационарных вероятностей пребывания процесса в определенных состояниях и, как следствие этого, стационарных вероятностей страничных сбоев. [21]
Тогда для ряда алгоритмов замещения ( СЗ, ИДИ, ПППУ и некоторых других) процесс изменения состояния верхнего уровня описывается однородной конечной эргодическои цепью Маркова, что указывает на существование стационарных вероятностей пребывания процесса в определенных состояниях и, как следствие этого, стационарных вероятностей страничных сбоев. [22]
Это решение называется алгоритмом замещения. [23]
При запуске программы следует спросить пользователя об алгоритме страничного замещения, выбирая из FIFO, LRU и, по крайней мере, еще одного. На каждом цикле считывайте номер страницы, к которой обращаются, из файла. Сформируйте листинг, аналогичный рис. 4.23, но повернутый на 90, так чтобы каждая новая страница увеличивала длину выходного файла на одну строку. [24]
Свойство включения является свойством алгоритма замещения элемента, который использовался раньше всех остальных. Этот алгоритм рассмотрен в примерах на рис. 33.3 и 33.4. Алгоритм замещения наименее часто используемого элемента и большинство других алгоритмов замещения также обладают этим свойством. [25]
На рис. 33.9 проведено сравнение значений F C) для алгоритма замещения элемента, который использовался раньше всех остальных, и алгоритма замещения наименее часто используемого элемента. Из этого сравнения видно, что для памяти емкостью 3 - 7 страниц алгоритм замещения наименее часто используемого элемента дает лучшие результаты. Это верно не для всех потоков запросов. Выбор типа алгоритма, который будет работать наиболее эффективно, во многом зависит от взаимосвязи запросов в потоке. [26]
Оптимальный алгоритм является алгоритмом замещения стеков. Стековые интервалы, показанные на рис. 33.10, соответствуют оптимальному алгоритму на рис. 33.9. Из этого примера видно, что алгоритм замещения наименее часто используемого элемента для данного случая приближается по своим характеристикам к оптимальному. [27]
Колонки в таблице упорядочены в соответствии с увеличением числа затребованных страниц. Самой нижней в колонке является та страница, которая должна перезаписываться в соответствии с принятым алгоритмом замещения. Поскольку в качестве примера на рис. 33.6 рассматривался алгоритм замещения самой ранней из использованных страниц, то последней в колонке является страница, которая использовалась раньше всех остальных, а сами колонки упорядочены по времени их участия в обработке запросов. Эти колонки называются стеками, а иногда вероятностными стеками. [29]
Во втором случае происходит обращение к странице, отсутствующей в памяти верхнего уровня. Эта ситуация называется страничным сбоем, так как программа не может дальше выполняться, пока нужная страница q, не будет переписана из памяти нижнего уровня в память верхнего уровня, что сопряжено с потерями времени. Такая процедура называется процессом замещения страниц, а правило, по которому при возникновении страничного сбоя выбирается страница vteS, для удаления из памяти верхнего уровня, - алгоритмом замещения. [30]
Страницы: 1 2 3