Оптимальный алгоритм замещения.
Рабочая нагрузка состоит из операторов следования и цикла. l - длина программы. V - объем БП. Рассмотрим чисто ассоциативное отображение (S=V).
Какие блоки останутся в БП после 1-го цикла ?
1 2 . . . S-1 S
Дальше в БП надо поместить S+1 блок. Мы будем вытеснять S -ое место БП и ставить последующие блоки на это место, то есть остаются не вытесненными те блоки, которые понадобятся в недалеком будущем.
1 2 . . . S-1 S+1
1 2 . . . S-1 S+2
..........................
1 2 . . . S-1 L
В первом цикле произошло L промахов.
2-ой цикл. До S-1 блока промахов нет. Дальше надо вытеснять c S-1-ого места
1 2 . . . S-2 S L
1 2 . . . S-2 S+1 L
............................
1 2 . . . S-2 L-1 L
Во втором цикле произошло (L-2)-(S-1)+1=L-S промахов
3-ий цикл.
1 2 . . . S-3 S-1 L-1 L
1 2 . . . S-3 S L-1 L
...................................
1 2 . . . S-3 L-2 L-1 L
L-S промахов
S-ый цикл
...................................
L-S+1 L-S+2 . . . L-1 L
S+1-ый цикл.
1 L-S+1 L-S+2 . . . L-1
2 L-S+1 L-S+2 . . . L-1
.......................................
L-S L-S+1 L-S+2 . . . L-1
L-S L-S+1 L-S+2 . . . L-2 L
L-S+1 промахов
S+2 цикл
1 L-S . . . L-2
.......................
L-S-1 L-S . . . L-2
L-S-1 . . . L-3 L-1
L-S-1 . . . L-3 L
S+3 цикл
1 L-S-1 . . . L-3
.........................
L-S-2 L-S-1 . . . L-3
L-S-2 . . . L-4 L-2
L-1
L
В конце концов будет
1 2 . . . S-1 L
Построим зависимость числа промахов от числа циклов
|
Пр. Пусть L=44 T=5 S=8 Найти вероятность промаха
число промахов: 44+36*4
ДЗ. Найти вероятность промаха для чисто ассоциативного отображения для произвольного Т.
Оптимальный алгоритм замещения для группо-ассоциативного
Отображения.
РИСУНОК
ДЗ. Найти вероятность промаха для группо-ассоциативного отображения для произвольного Т.
Лекция №4.
Моделирование алгоритмов замещения при задании рабочей нагрузки посредством Марковской модели.
Пусть имеется n блоков в БП. Введем независимую модель. Она задается вероятностью ( 
) обращения к i-ому блоку. Зависимая (марковская) модель задается 
- вероятность того, что предыдущее обращение было к i-ому блоку, а текущее к j-ому. Такое задание адресной трассы является приближенным. Истинная адресная трасса задается вероятностью, зависящей от всех предыдущих обращений.
Алгоритм замещения LRU.
Пусть БП имеет чисто ассоциативное отображение, следовательно имеется V=S мест. Для того чтобы описать состояние БП типа кэш необходимо использовать вектор длиной S, и элементы этого вектора есть номера блоков, которые находятся в кэш. Пусть блоки в векторе располагаются по принципу: слева - самый «молодой», а справа - самый «старый».
Например пусть для S=4 вектор будет 5,3,7,8. Тогда самый «молодой» будет блок с номером 5, а самый «старый» - 8.
- вероятность того, что вектор, описывающий состояние БП, будет 
Пусть S=2, n=3. Построим граф переходных вероятностей, у которого число состояний - это число размещений n по S.
ДЗ. Достроить граф.
Найдем вероятность 
для этого нужно рассмотреть дуги, входящие в 1,2, и расписать каждое обращение-состояние.
А вероятность промаха будет:
В общем случае
(*)
ДЗ. S=3, n=6. Найти 
.
Мы имеем систему 
уравнений типа (*), но одно из них линейно зависимо. Его отбросим и добавим условие нормировки : 
Выразим из системы все 
и подставим в выражение вероятности промаха:
Двоичное дерево.
Пусть n-произвольное, S=8.
ДЗ. 1) S=8,n=12. 
-?
2) Построить граф переходов для а) равновероятного алгоритма замещения;
б) алгоритма замещения FIFO.
Лекция №5.