рефераты конспекты курсовые дипломные лекции шпоры
- Раздел История
- /
- Управление замещением страниц в двухуровневой памяти.
Реферат Курсовая Конспект
Управление замещением страниц в двухуровневой памяти.
Управление замещением страниц в двухуровневой памяти. - раздел История, Краткая историческая справка Рассмотрим Вопросы Обмена Информацией Между Первыми Двумя Наиболее Быстродейс...
Рассмотрим вопросы обмена информацией между первыми двумя наиболее быстродействующими уровнями памяти. Эти уровни будем будем называть основной памятью (ОП) и вспомогательной (ВП). Такой обмен характерен при использовании кэш-памяти. Так как наибольшее распространение получила страничная организация памяти, то здесь рассмотрим математические модели управления замещения страниц в двух- уровневой памяти. Алгоритм замещения определяет состав страниц в более быстродействующей основной памяти. Минимальную частоту обращения к ВП давал бы алгоритм, замещающий те страницы в ОП, обращение к которым произойдет через максимально долгое время. Однако реализовать такой алгоритм невозможно, так как заранее не известна информация о будущих обращениях.
Основной вопрос, возникающий при синтезе алгоритмов замещения, заключается в нахождении алгоритмов, которые дают приемлемую частоту обращений к ВП для самых различных программ, структура которых заранее неизвестна. В процессе работы объемы ОП, выделяемые программе, либо фиксируются, либо определяются динамически в ходе выполнения программ. В качестве примера можно привести 3 алгоритма замещения для фиксированного объема памяти ОП:
1. Случайное замещение (СЗ). В этом случае с заданной на множестве страниц ОП вероятностью замещается любая страница в ОП.
2. Раньше пришла – раньше ушла (РПРУ). При этом замещается страница, которая дольше всех находилась в ОП.
3. Замещение наиболее давно использованной страницы (НДИ). В этом случае замещается страница, которая дольше всех не запрашивалась.
Среди алгоритмов замещения, рассчитанных на переменный объем ОП, выделяемый программе, наиболее известен алгоритм рабочего комплекта (РК). Согласно ему, в любой момент времени в ОП хранятся только те страницы, к которым происходили обращения на интервале (t-τ,t), где τ – фиксированный параметр. При использовании алгоритма РК, в отличие от таких алгоритмов как СЗ, РПРУ, НДИ, можно уменьшать или увеличивать объем ОП, отводимый программе, в зависимости от ее поведения. Поэтому алгоритм РК можно использовать для динамического распределения ОП. Пусть ε=(1,2…,n) – совокупность страниц данной программы. Предположим, что все n страниц постоянно хранятся в ВП и только m<n страниц могут храниться в ОП.
Поведение программы опишем последовательностью страниц х1, х2, ..., к которым происходят обращения в процессе ее выполнения. Обозначим эту последовательность через ω = (x1,x2,…). Если xt = i, то это означает, что обращение к странице i происходит в момент t. Будем говорить, что при обращении к странице, отсутствующей в ОП, происходит страничный сбой. Пусть 
– совокупность страниц в ОП в момент t.
Физически реализуемый алгоритм замещения А – это алгоритм, который для любого t = 1,2,… определяет множество 
в зависимости от наблюдаемой предыстории 
, 
и 
. СЗ, РПРУ, НДИ, РК – физически реализуемы.
Среди всех алгоритмов замещения выделим важный класс – алгоритм замещения по запросу.
Df. Пусть объем ОП, отведенный программе составляет m страниц. Алгоритм замещения A по запросу определяет множество по формуле:
,
где 
– замещающая граница.
СЗ, РПРУ, НДИ – примеры алгоритмов по запросу.
Упорядочение в любой момент t список страниц 
будем называть состоянием ОП. Например, если 
- состояние ОП в момент t-1, то для РПРУ страница 
- поступила раньше в ОП чем страница
, страница
раньше чем страница 
при к>l.
При РПРУ состояние ОП изменяется только в моменты страничных сбоев. Если в момент t запрашивается страница 
, то страница замещается и новое состояние ОП есть 
. Для алгоритма НДИ состояние ОП изменяется и при обращении к страницам, находящимся в ОП. Если и 
, то 
. При страничном сбое состояние ОП для НДИ изменяется так же, как и для РПРУ. Среди физических реализаций алгоритмов по запросу выделим класс марковских алгоритмов с конечной памятью, который при определении замещения страницы не использует информацию об обращениях 
.
Алгоритм замещения А называется марковским с конечной памятью, если 
. Правило f(.) может быть детерминированным или рандомизированным. Такие алгоритмы удобны при реализации.
Алгоритмы СЗ, РПРУ, НДИ - марковские с конечной памятью. Для РПРУ, НДИ f(.) детерминирована, для СЗ – рандомизирована.
– Конец работы –
Эта тема принадлежит разделу:
Краткая историческая справка
Оглавление... Глава Введение... Краткая историческая справка Режим реального времени Глава Вычислительные системы...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Управление замещением страниц в двухуровневой памяти.
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.026 сек.
Новости и инфо для студентов