- •Оглавление.
- •§1.2. Режим реального времени
- •Глава 2. Вычислительные системы §2.1. Классификация вс.
- •§2.2. Показатели качества вс.
- •§2.3. Классификация вс по организации структуры.
- •Глава 3. Распределение ресурсов процессора. §3.1. Принципы упорядочивания ресурсов вс методами теории расписаний.
- •§3.2. Общая постановка задачи упорядочивания.
- •§3.3. Задачи и критерии детерминированного распределения производительности вычислительных систем.
- •Глава 4. Распределение памяти в вс. §4.1. Оптимизация распределения памяти по иерархическим уровням.
- •§4.2. Управление замещением страниц в двухуровневой памяти.
- •§4.3. Класс многоуровневых алгоритмов замещения.
- •§4.4. Модели поведения программ и критерии качества.
- •Глава 5. Классические архитектуры многомашинных и многопроцессорных комплексов. §5.1. Многомашинные комплексы.
- •§5.2. Многопроцессорные комплексы.
- •§5.3. Типы структур мпвк.
- •Глава 6. Примеры многомашинных и многопроцессорных систем. §6.1. Вк на базе ес эвм (ibm).
- •§6.2. Вк на базе см эвм (dec).
- •§6.3. Комплексы на основе микро-эвм и микропроцессоров.
- •Глава 7. Особенности организации вычислительных процессов.
- •Глава 8. Системы параллельной обработки данных. §8.1. Классификация систем параллельной обработки данных.
- •§9.6. Кластерная архитектура.
- •§9.7. Проблемы выполнения сети связи процессоров в кластерной системе.
- •Глава 10. Принципы построения коммуникационных сред. §10.1. Коммутаторы для многопроцессорных вычислительных систем.
- •§10.2. Простые коммутаторы.
- •Алгоритмы арбитража. Статические приоритеты.
- •Динамические приоритеты.
- •Фиксированные временные интервалы.
- •Очередь fifo.
- •Особенности реализации шин.
- •Простые коммутаторы с пространственным разделением.
- •§10.3. Составные коммутаторы.
- •Коммутатор Клоза.
- •Распределенные составные коммутаторы.
- •Глава 11. Примеры построения коммуникационных сред. §11.1. Когерентный интерфейс sci.
- •§11.2.Коммуникационная среда myrinet.
- •Глава 12. Сосредоточенные вычислительные системы высокой производительности. §12.1. Конвейерные системы.
- •§12.2. Иерархия памяти.
- •§12.3. Управление и организация конвейеров.
- •§12.4. Статические конвейеры.
- •§12.5. Диаграмма состояний.
- •§12.6. Генерирование таблиц занятости на основе циклов.
- •§12.7. Конвейеры с динамической конфигурацией.
- •§12.8. Функции управления в конвейерных системах.
- •§12.9. Архитектура конвейерных систем.
- •§12.10. Примеры конвейерных систем.
- •§12.11. Матричные вычислительные системы.
- •Резюме.
- •Список литературы.
§4.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(.) детерминирована, для СЗ – рандомизирована.