МОДЕЛ (774295), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Пусть имеется 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.

Опережающая обработка информации.

Имеется тракт ОП-ЦП. ЦП вырабатывает адрес обращения, по которому происходит считывание команды. Во время считывания работает ОП, а ЦП простаивает. Пусть команда будет с непосредственной адресацией, следовательно во время ее выполнения в ЦП ОП будет простаивать. Производительность была бы выше, если бы ЦП постоянно выполняла бы команды, для этого нужно при выполнении очередной команды прочитать следующую, которую мы поместим в специальный буфер команд. Естественно, когда команда поступает из БП в ЦП, она затирается в БП. БП служит согласующим звеном между ОП и ЦП. Если время выполнения одной команды в ЦП меньше либо равна времени выборки команды из ОП, тогда БП не нужна. Но в действительности эти времена не постоянны.

Пусть время выполнения одной команды в ЦП изменяется от minT_оп до maxT_оп , время выборки команды из ОП лежит в диапазоне от minT_цп до maxT_цп . Для простоты будем считать, что передача информации из ОП в ЦП через БП происходит за нулевое время. И емкость буфера равна n.

Определим Т_оп и Т_цп как

ì t₁ c вероятностью p₁

Т_оп = ít₂ c вероятностью p₂ (*)

ê....................................

ît_k c вероятностью p_k

ìt₁ c вероятностью q₁

Т_цп = ít₂ c вероятностью q₂ (**)

ê....................................

ît_k c вероятностью q_k

Нас интересует производительность системы, то есть появление команд на выходе.

Пусть S - среднее время выполнение команды этой системой.

_цп = - среднее время выполнения одной команды в ЦП. _оп = - среднее время выборки одной команды из ОП. Р_цп - вероятность простоя ЦП. Р_цп - вероятность простоя ОП. Тогда .

Так как БП имеет ограниченную емкость, то если в момент поступления команды из ОП в БП, последняя полностью заполнена, то возникает проблема. Существует два решения этой проблемы: 1) команда теряется и будет происходит считывание с тем же адресом обращения до тех пор пока ЦП не обработает очередную команду и следующая команда поступит на обработку из БП. 2) Считанная команда остается на внутренних регистрах ОП и при этом происходит блокировка работы памяти. Будем считать, что у нас вторая дисциплина.

Рассмотрим тракт ОП-БП-ЦП, в котором время работы устройств подчинены различным законам распределения.

Дискретное распределение.

Определим состояние системы тремя параметрами U₁U₂U₃, где U₁ - указывает сколько времени осталось до завершения считывания команды из ОП; U₂ - количество команд в буфере; U₃ - указывает сколько времени осталось до завершения выполнения команды в процессоре.

Построим граф переходов данной системы.

Граф переходов содержит 6(n+1) состояний. Найдем - вероятность пребывания в состоянии . Для этого составим систему уравнений. Уравнение для некоторой вершины графа в левой части содержат , а в правой части - сумму произведений пометок дуг, входящих в выбранную вершину, на вероятности с пометками вершин, из которых эти дуги исходят.

ДЗ. Выписать все уравнения и определить вероятности простоя как ЦП, так и ОП.

Лекция №6.

Геометрическое распределение.

Системы (*) и (**) (см. прошлую лекцию) определяют функцию распределения времени выполнения команды в устройстве. В этом случае граф переходов будет очень сложным и определить в явном виде вероятности простоя сложно. Если мы зададим функцию распределения более упрощенно, то мы продвинемся в решении задачи. В связи с выше сказанным введем для описания времени выполнения команды в устройстве геометрический закон распределения.

Геометрическое распределение характеризуется двумя параметрами периодом (t) и вероятностью (p) повторения данного периода.

Посмотрим, как геометрическое распределение вводится для нашего случая: с вероятностью 1-p время выполнения команды равно t; с вероятностью (1-p)p время выполнения равно 2t; и т.д. с вероятностью (1-p)p^i-1 время выполнения команды равно it. Таким образом в конце любого периода с вероятностью p команда продолжает выполнятся, а с дополнительной вероятностью (1-p) закончит свое выполнение.

Пример.

Определим состояние системы тремя параметрами U₁U₂U₃, где U₁ - указывает сколько времени осталось до завершения считывания команды из ОП; U₂ - количество команд в буфере; U₃ - показывает выполняется (1) или не выполняется (0) команда в ЦП.

Построим граф переходов данной системы.

Составим систему уравнений

В данной системе одно уравнение линейно зависимо, следовательно надо отбросить любое уравнение и добавить уравнение нормировки. Решается эта система любым из известных способов.

Найдем _цп

Лекция №7.

Экспоненциальное распределение.

Экспоненциальное распределение является непрерывным распределением и является приближением геометрического распределения, т.к. при стремлении такта к 0 геометрическое распределение стремиться к экспоненциальному.

Определение: - вероятность того, что выполнение команды завершится к моменту времени t.

Для экспоненциального закона распределения .

Дополнении к функции распределения: - вероятность того, что выполнении команды не закончиться к моменту t.

Плотность вероятности:

ДЗ. Просмотреть свойства экспоненциального закона распределения. Математическое ожидание, дисперсия, первый и второй моменты.

Рассмотрим такую модель:

Поскольку время выполнения команды не зависит от того сколько данная команда выполнялась до этого нет необходимости вводить параметр, который будет содержать информацию о том сколько времени уже выполняется команда в процессоре, или в памяти, или одновременно и там и там, следовательно достаточно указать сколько находиться команд в системе (от 0 до n+1). Рассмотрим состоянии системы в некоторый момент времени t. Введем Р_i(t) - вероятность того, что в момент наблюдения t в системе находится ровно i команд. При i=0,1,...,n+1 ОП не может быть заблокировано. Введем n+2 состояние и будем считать, что в этом состоянии ОП заблокировано.

Найдем Р_i(t). Для этого рассмотрим малый интервал времени Dt и пусть в момент t+Dt система находиться в состоянии i. Найдем вероятность P_i(t+Dt) для всех значениях i. В момент времени t система могла находиться в любом состоянии. Посмотрим как можно из состояния системы в момент времени t попасть в состояние i в момент времени t+Dt.

1. 0<i<n+2

вероятность того, что ни ОП, ни ЦП не завершит обработку команды или оба устройства выполнят одно и тоже число команд.

Определим вероятность того, что за Dt ни ОП, ни ЦП не завершит обработку команды:

ДЗ. Разложение е^х.

Символ О(Dt) означает величины, для которых справедливо O(Dt )/ Dt ®0 при Dt®¥. Вероятность того, что за Dt устройствами будет выполнено ровно по к команд равняется О(Dt).

Действительно: .

Поэтому:

+ вероятность того, что за время Dt 1) ЦП выполнит 1 команду, а ОП - 0 команд, либо 2) ЦП выполнит на 1 команду больше чем ОП.

Определим вероятность первого события: .

Вероятность второго события равна О(Dt). Следовательно:

+

вероятность того, что 1) ЦП выполнит 2 команды, а ОП ни одной, либо 2) ЦП выполнит на 2 команды больше, чем в ОП.

Определим вероятность первого события: .

Вероятность второго события равна О(Dt). Отсюда вероятность попадания в состояние i из состояния i+2 равна О(Dt), аналогично и из состояния i-2. Следовательно и из состояний i±3, i±4,...,i±k вероятность попадания в состояние i равна О(Dt).

Мы получили формулу полной вероятности того, что система окажется в момент времени t+Dt в состоянии i (0<i<n+2):

+

( возьмем предел каждой части равенства при Dt®¥)

Характеристики

Список файлов лекций