ПРС/Формуле

Поасонов процес

Основни термини

$\bar{s}$ $\bar{s}$ - Средње време обраде посла
- Понекад означено и као $s, S_p$
$\bar{a}$ - Средње време/Очекивано време између два пристизања послова
$\mu$ - Брзина/интензитет обраде посла
$\lambda$ - Брзина/интензитет пристизања послова
$\lambda = \frac{1}{\bar{a}}$
$\mu = \frac{1}{\bar{s}}$

Стања система

Стања система обележавамо бројевима који уједно означавају колико има послова у систему.
Број стања = Број процесора који могу да раде посао + Број места у реду за чекање
Уколико је ред за чекање неограничен/бесконачан, постоји бесконачан број стања.
Свако стање има статичку вероватноћу, ознака $p_i$ , где је $i$ број стања.
$\sum_{i = 0}^n p_i = 1$ - Једначина преклапања. Збир свих стања у систему мора бити 1.
Статичке вероватноће одређују се из балансних једначина.
У системима са бесконачним бројем стања (неограниченим редом за чекање) јављају се редови:
- $1 + \rho + \rho^2 + ... = \sum_{i = 0}^{\infty} \rho^i = \frac{1}{1 - \rho}$ - Геометријски ред. Конвергира само ако $\rho < 1$ и то је неопходно проверити - иначе ред дивергира и анализа није применљива.
- $1 + 2\rho + 3\rho^2 + ... = \sum_{i = 0}^{\infty} (i + 1)\rho^i = \frac{1}{\left(1 - \rho\right)^2}$ - Потенцијални ред. Конвергира само ако $\rho < 1$ и то је неопходно проверити - иначе ред дивергира и анализа није применљива.
За непознат али коначан број стања јавља се и геометријски низ (који има коначан број чланова): $\rho + \rho^2 + ... \rho^n = \sum_{i = 1}^{n} \rho^i = \frac{1 - \rho^n}{1 - \rho}$ $\rho + \rho^2 + ... \rho^n = \sum_{i = 1}^{n} \rho^i = \frac{1 - \rho^n}{1 - \rho}$
- Пазити на случај где $\rho = 1$ . Тада је вредност низа $n\rho$ .

Карактеристике система

$T$ - Просечно/очекивано време обраде послова/време одзива у систему
$T_q$ $T_q$ - Просечно/очекивано време обраде послова/време одзива у реду за чекање
- Веза: $T = T_q + \bar{s}$
$J$ $J$ - Просечан/очекивани број послова у систему
- $J = \sum_{i = 0}^n ip_i$ - где се $i$ слаже са бројем послова у систему.
$J_q$ $J_q$ - Просечан/очекивани број послова у реду за чекање
- Важи иста формула као за J, само што се вероватноће множе са бројем послова у реду за чекање.
$X$ $X$ - Проток кроз систем
- Уједно и проток кроз ред за чекање
- Уколико је ред за чекање бесконачан нема одбијања послова, што значи да је проток исти као и интензитет пристизања послова. $X = \lambda$
- Иначе, проток је $X = (1 - p_{MAX})\lambda$ , где је $p_{MAX}$ последње стање у ком нема места у реду за чекање.
$X' = p_{MAX}\lambda$ - Проток одбијених послова
$T = \frac{J}{X}$ $T = \frac{J}{X}$ - Литлова формула. Важи за цео систем.
- Могуће је посматрати само ред за чекање и ту важи: $T_q = \frac{J_q}{X}$
- Веза: $T = T_q + \bar{s} \iff \frac{J}{X} = \frac{J_q}{X} + \bar{s} \iff J - J_q = \bar{s}X$
$U = \sum_{i = 0}^n U_i p_i$ $U = \sum_{i = 0}^n U_i p_i$ - Искоришћеност система. Искоришћеност неког дела $U_i$ $U_i$ се дефинише као број послова подељен са капацитетом.
- Важи $U = 1 -$ неискоришћени део система.

Циклични модел мултипрограмирања

Проток кроз систем је свуда исти.
Ово значи да време проведено у процесорском делу система и диск делу система има исти проток, па важи: $T_{CPU} = \frac{J_{CPU}}{X}$ , $T_{disk} = \frac{J_{disk}}{X}$
$J_{CPU} + J_{disk} = n$
$R = T_{CPU} + T_{disk} = \frac{n}{X}$ - Round trip time - време проласка једног посла кроз цео систем.
Пошто је проток у целом систему исти, код гранања еквивалентних паралелних сервера важи:
- $X = nX_p = mX_d$ , $n$ број процесора, $m$ број дискова.
Закон искоришћења једног сервера/диска: $U_p = X_pS_p$ $U_p = X_pS_p$
- Пошто је проток свуда исти: $\frac{U_p}{U_d} = \frac{X_pS_p}{X_dS_d}$

Гордон-Њуелов метод

Гордон-Њуелов метод дефинише $x_i$ као потражњу сервера $i$ . Овај фактор је релативан и обично се узима да је потражња првог сервера (процесора) $x_1 = 1$ .
ГЊ систем једначина се формира овако:
- Сваки систем има своју једначину, где са леве стране једнакости стоје $\mu_ix_i$ , а са десне, за сваку грану која улази у систем (тј. његов ред за чекање) $p_i\mu_ix_i$ .
- $p_i$ је вероватноћа уласка у грану.
$G(n)$ - константа система која зависи од броја послова у систему. Најлакше се одређује Бјузеновим методом.
$P[n_j(N) \geq k] = x_j^k \frac{G(N-k)}{G(N)}$ $P[n_j(N) \geq k] = x_j^k \frac{G(N-k)}{G(N)}$ - Вероватноћа да у неком систему има више од $k$ $k$ процеса.
- $N$ је укупан број послова у систему.
- $j$ је редни број система.
- $x_j$ је његов фактор потражње.
$P[n_j(N) = k] = P[n_j(N) \geq k] - P[n_j(N) \geq k + 1] = x_j^k \frac{G(N-k)}{G(N)} - x_j^{k+1} \frac{G(N-k + 1)}{G(N)}$ - Вероватноћа да систем има тачно $k$ послова.
$U_j = P[n_j(N) \geq 1] = x_j \frac{G(N-1)}{G(N)}$ $U_j = P[n_j(N) \geq 1] = x_j \frac{G(N-1)}{G(N)}$ - Искоришћеност сервера
- Сервер који има највећу искоришћеност је уско грло.
$J_i = x_i^1 \frac{G(N-1)}{G(N)} + x_i^2 \frac{G(N-2)}{G(N)} + x_i^3 \frac{G(N-3)}{G(N)} + ... + x_i^n \frac{G(0)}{G(N)}$ - Просечан/очекивани број послова на серверу.
$P_{j_1j_2j_3...j_n} = \frac{x_1^{j_1}x_2^{j_2} ... x_n^{j_n}}{G(N)}$ - Вероватноћа да у систему са $n$ сервера и $N$ послова сваки појединачни сервер има $j_i$ послова.

Интерактивни системи

$\overline{\theta}$ : време размишљања (време током ког се корисник одлучује шта да упише на терминал)
$\overline{w}$ : време проведено у реду за чекање
$\overline{r}$ $\overline{r}$ : време одзива процесора
- $\overline{r} = \overline{w} + \overline{s}$
$T_c$ $T_c$ : време циклуса на процесору
- $T_c = \overline{w} + \overline{s} + \overline{\theta} = \overline{r} + \overline{\theta}$
- Примењена Литлова формула: $T_c = \frac{n}{X}$
$n^*$ $n^*$ : критичан број терминала (колико максимално терминала можемо да имамо у систему тако да остане $\overline{w} = 0$ $\overline{w} = 0$ )
- $n^* = \left\lfloor 1 + \frac{\overline{\theta}}{\overline{s}} \right\rfloor$
Искоришћење у интерактивном систему (опет добијено из Литлове формуле): $U = \frac{n \overline{s}}{T_c}$ $U = \frac{n \overline{s}}{T_c}$
- За $\overline{w} = 0$ важи $U(n) = \frac{n \cdot \overline{s}}{\overline{s} + \overline{\theta}}$
- За систем у засићењу важи: $1 = \frac{n \cdot \overline{s}}{\overline{r}(n) + \overline{\theta}}$
Рекурентна формула за рачунање вероватноћа стања система: $\frac{1}{p_0(n)} = 1 + n\rho \frac{1}{p_0(n-1)}$

Отворене мреже

Џексонова теорема: можемо посматрати сервисне центре као да су независни М/М/1 сервери.
- Време одзива појединачног сервера добијамо као: $R_i = \frac{1}{\mu_i - X_i}$ (примена Литлове формуле за М/М/1 систем)
- Вероватноће стања укупног система се добијају као производи појединачних стања система.
- За М/М/1 важи: $p_0 = 1 - \rho$ , $p_i = \rho^i p_0$ , $J = \frac{\rho}{1 - \rho}$
Једначина отворене мреже са централним сервером: $1 = \frac{V_1}{V_0} + \frac{V_2}{V_0} + ... + \frac{V_k}{V_0} + \frac{1}{V_0}$ $1 = \frac{V_1}{V_0} + \frac{V_2}{V_0} + ... + \frac{V_k}{V_0} + \frac{1}{V_0}$
- Сабирци су редом једнаки: $p_0, p_1, ..., p_n$
- $V_0, V_1, ..., V_k$ : просечан број посета сваком од сервисних центара ( $V_0$ је централни сервер, у задацима, узети да је $V_0 = 1$ )