Алгоритм замещения 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.



Дата добавления: 2016-11-04; просмотров: 1617;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.006 сек.