Алгоритм - замещение - страница
Cтраница 2
Эта реализация оставляет открытым вопрос о размещении алгоритма замещения страниц. Возможно, покажется более удачным расположить его во внешнем обработчике страниц, но тогда возникают некоторые проблемы. Из них принципиально то, что внешний обработчик страниц не имеет доступа к битам R и М для всех страниц. А эти биты играют важнейшую роль во многих алгоритмах страничной подкачки. Таким образом, или необходим какой-либо механизм для передачи содержимого битов внешнему обработчику страниц, или же алгоритм замещения страниц должен находиться в ядре. Во втором случае обработчик прерываний сообщает внешнему обработчику, какую страницу он выбрал для удаления, и предоставляет данные или путем отображения их в адресное пространство внешнего обработчика страниц, или включая их в сообщение. В любом варианте внешний обработчик страниц пишет данные на диск. [16]
Укажите, в чем по-вашему, заключается суть алгоритма LRU замещения страниц. [17]
 |
Состояние массива памяти М после обработки каждого элемента строки обращений. Последовательность расстояний будет обсуждаться в следующем разделе. [18] |
Чтобы прояснить функционирование интерпретатора, рассмотрим конкретный пример, использующий алгоритм замещения страниц LRU. Виртуальное адресное пространство имеет восемь страниц, а в физической памяти есть четыре страничных блока. [19]
 |
Аномалия Билэди. алгоритм FIFO при работе с тремя страничными блоками ( а. алгоритм FIFO при наличии четырех страничных блоков ( б. [20] |
За годы было проведено несколько работ, посвященных теоретическому моделированию алгоритмов замещения страниц. В данном разделе мы обсудим некоторые из этих идей, чтобы увидеть, как работает процесс моделирования. [21]
Чтобы избежать возможных недоразумений, следует прояснить, что полученный протокол обращений к страницам относится только к одной хорошо спланированной программе и, кроме того, к определенным входным данным. Таким образом, алгоритм замещения страниц, выведенный из него, будет характерен только для этой программы с именно этими входными данными. Хотя такой метод полезен для оценки алгоритмов замещения страниц, он не используется в практических системах. Ниже мы изучим алгоритмы, которые являются применимыми в реальных системах. [22]
Независимо от причин группировки запросов этот факт позволяет выбрать наилучшую в данном случае организацию хранения данных. При страничной организации памяти алгоритм замещения страниц может быть устроен так, чтобы данные-е наибольшей частотой использования оставались в основной памяти или на устройствах с минимальным временем доступа. При использовании индекса часто применяют специальные буферы повторного поиска, в которых в оперативной памяти сохраняются адресные ссылки к записям, использовавшимся самыми последними. Поиск записи в ЭВМ начинается с просмотра буфера повторного поиска для определения, нет ли там элемента индекса для требуемой записи. [23]
Над страничным кэшем располагается система виртуальной памяти. В нем вся логика работы со страницами, например алгоритм замещения страниц. Поверх него находится программа отображения файлов на виртуальную память и высокоуровневая программа управления страничными прерываниями. Эта программа решает, что нужно делать при возникновении страничного прерывания. Сначала она проверяет допустимость обращения к памяти и, если все в порядке, определяет местонахождение требуемой страницы и то, как она может быть получена. [24]
С другой стороны, если удаляется страница с наименьшим возрастом, независимо от того, к какому процессу она относится, то будет выбрана страница БЗ, и система попадет в состояние, показанное на рис. 4.26, в. Алгоритм на рис. 4.26, б называется локальным, а про схему на рис. 4.26, в говорят, что это глобальный алгоритм замещения страниц. Локальные алгоритмы соответствуют размещению каждого процесса в фиксированной области памяти. Глобальные алгоритмы динамически распределяют страничные блоки между выполняющимися процессами. Таким образом, количество страничных блоков, предоставленных каждому процессу, изменяется со временем. [25]
С другой стороны, если удаляется страница с наименьшим возрастом, независимо от того, к какому процессу она относится, то будет выбрана страница ВЗ, и система попадет в состояние, показанное на рис. 4.26, в. Алгоритм на рис. 4.26, б называется локальным, а про схему на рис. 4.26, в говорят, что это глобальный алгоритм замещения страниц. Локальные алгоритмы соответствуют размещению каждого процесса в фиксированной области памяти. Глобальные алгоритмы динамически распределяют страничные блоки между выполняющимися процессами. Таким образом, количество страничных блоков, предоставленных каждому процессу, изменяется со временем. [26]
Чтобы избежать возможных недоразумений, следует прояснить, что полученный протокол обращений к страницам относится только к одной хорошо спланированной программе и, кроме того, к определенным входным данным. Таким образом, алгоритм замещения страниц, выведенный из него, будет характерен только для этой программы с именно этими входными данными. Хотя такой метод полезен для оценки алгоритмов замещения страниц, он не используется в практических системах. Ниже мы изучим алгоритмы, которые являются применимыми в реальных системах. [27]
Этот метод часто называют буферизацией файла, и он имеет многочисленные варианты и разновидности. Например, могут выделяться отдельные буферы для каждого файла или же один буфер может использоваться всеми файлами. Принципы выбора эффективной стратегии буферизации весьма напоминают принципы, используемые при выборе алгоритма замещения страниц, рассматриваемые в разд. [28]
Обратим внимание на рис. 4.26, а. Здесь три процесса, А, В и С, составляют набор работоспособных процессов. Предположим, процесс А вызвал страничное прерывание. Должен ли алгоритм замещения страниц пытаться найти наиболее давно использовавшуюся страницу, учитывая только шесть страниц, предоставленные в данный момент процессу А, или же он должен рассматривать все страницы памяти. [29]
Как видно, алгоритм замещения страниц этим пытается заглянуть в будущее. Но, если будущее хоть немного похоже на настоящее, то можно пытаться его прогнозировать. Это и делает алгоритм замещения страниц, реализованный в операционной системе. В результате работы такого алгоритма в оперативной памяти окажутся те страницы памяти, которые чаще нужны для решения текущих задач компьютера. [30]
Страницы: 1 2 3