Прямой доступ к удаленной памяти – это промежуточная форма между моделями передачи сообщений и общей памятью. RDMA – remote direet memory access.
Парадигмы программирования.
1) Парадигма параллельного программирования – это реализация того или иного типа параллелизма, характерного для некоторого класса алгоритмов. Тип параллелизма отражает структуру приложения или структуру данных. В первом случае имеет место функциональный параллелизм (по управлению), во втором – параллелизм по данным.
2) Парадигма распределения задач.
3) «Одна программа– множественные данные».
4) Парадигма конвейеризации данных.
1. Понятие марковского процесса
2. Уравнение Колмогорова, финальные вероятности
3. Схема гибели и размножения, формула Литтла
4. Задача Эрланга
Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
t<t0 t>t0
Прошлое Будущее
t0 (S0)
Поток событий – это последовательность однородных событий, следующих одно за другим в случайные моменты времени. Важной характеристикой потока событий является его интенсивность l, то есть среднее число событий, приходящееся на единицу времени. Интенсивность может быть как постоянной, так и переменной, зависящей от времени t.
Для простейшего потока с интенсивностью l интервал t между событиями имеет показательное распределение.
l
P(t)=1-e-lt
t>0
t
Если интервал , то такой интервал называют коротким. В расчетах, связанных с потоками событий, удобно пользоваться понятием элемент вероятности.
Рассмотрим на оси Оt простейший поток с интенсивностью l и произвольно расположенный участок времени dt.
Элементом вероятности называется вероятность попадания на этот участок хотя бы одного события потока. . То есть для простейшего потока элемент вероятности равен интенсивности потока, умноженного на длину элементарного участка. Элемент вероятности из-за отсутствия последействия совершенно не зависит от того, сколько событий и когда появлялись ранее.
Пусть имеется 2 узла, причем эти два узла могут находится в следующих состояниях:
· S0 – оба узла исправны
· S1 – 1ый ремонтируется, 2ой исправен
· S2 - 2ой ремонтируется, 1ый исправен
· S3 – оба ремонтируются
S0
S2
S1
S3
m1 m2
l1
l2
l2 l1
m1
m2
m - интенсивность ремонта
l - интенсивность ремонта событий
Стрелка, направленная из S0 в S1, означает переход в момент отказа первого узла, а стрелка, направленная обратно, переход в момент окончания ремонта этого узла.
Вероятностью i-ого состояния называется вероятность Pi(t) того, что в момент t система будет находится в состоянии Si. Очевидно, что для любого момента сумма всех вероятностей состояний равна .
Используя граф состояний, можно найти все вероятности состояний Pi(t) как функции времени. Для этого составляются уравнения Колмогорова.
Рассмотрим вероятность P0(t), придадим t малое приращение Dt и найдем Po(t+Dt) вероятность того, что в момент t+Dt система будет в состоянии S0. Произойти это может тремя способами:
1) Система была в состоянии S0 и не вышла из него за время Dt
2) Система была в состоянии S1, а за время Dt перешла в состояние S0
3) Система была в состоянии S2, а за время Dt перешла в состояние S0
Найдем вероятность первого варианта. Вероятность того, что система была в состоянии S0=P0(t). Суммарный поток событий, выводящий систему из состояния S0 будет равен l1+l2. Значит, вероятность того, что за время Dt система выйдет из состояния S0 равна: (l1+l2) Dt.
Значит вероятность того, что система не выйдет из состояния S0 за время Dt равна: , тогда полная вероятность первого варианта равна
Для второго состояния:
Для третьего состояния:
Складывая вероятности всех вероятностей, получим:
Перенесем в левую часть и разделим обе части на Dt.
Пусть , тогда .
Получаем первое уравнение Колмогорова, аналогично получаются остальные.
Общее правило составления уравнения Колмогорова:
В левой части каждого из них стоит производна вероятности данного состояния, в правой части – сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние на интенсивность
