PRS/Formule

Poasonov proces

$\bar{s}$ $\bar{s}$ - Srednje vreme obrade posla
- Ponekad označeno i kao $s, S_p$
$\bar{a}$ - Srednje vreme/Očekivano vreme između dva pristizanja poslova
$\mu$ - Brzina/intenzitet obrade posla
$\lambda$ - Brzina/intenzitet pristizanja poslova
$\lambda = \frac{1}{\bar{a}}$
$\mu = \frac{1}{\bar{s}}$

Stanja sistema obeležavamo brojevima koji ujedno označavaju koliko ima poslova u sistemu.
Broj stanja = Broj procesora koji mogu da rade posao + Broj mesta u redu za čekanje
Ukoliko je red za čekanje neograničen/beskonačan, postoji beskonačan broj stanja.
Svako stanje ima statičku verovatnoću, oznaka $p_i$ , gde je $i$ broj stanja.
$\sum_{i = 0}^n p_i = 1$ - Jednačina preklapanja. Zbir svih stanja u sistemu mora biti 1.
Statičke verovatnoće određuju se iz balansnih jednačina.
U sistemima sa beskonačnim brojem stanja (neograničenim redom za čekanje) javljaju se redovi:
- $1 + \rho + \rho^2 + ... = \sum_{i = 0}^{\infty} \rho^i = \frac{1}{1 - \rho}$ - Geometrijski red. Konvergira samo ako $\rho < 1$ i to je neophodno proveriti - inače red divergira i analiza nije primenljiva.
- $1 + 2\rho + 3\rho^2 + ... = \sum_{i = 0}^{\infty} (i + 1)\rho^i = \frac{1}{\left(1 - \rho\right)^2}$ - Potencijalni red. Konvergira samo ako $\rho < 1$ i to je neophodno proveriti - inače red divergira i analiza nije primenljiva.
Za nepoznat ali konačan broj stanja javlja se i geometrijski niz (koji ima konačan broj članova): $\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}$
- Paziti na slučaj gde $\rho = 1$ . Tada je vrednost niza $n\rho$ .

$T$ - Prosečno/očekivano vreme obrade poslova/vreme odziva u sistemu
$T_q$ $T_q$ - Prosečno/očekivano vreme obrade poslova/vreme odziva u redu za čekanje
- Veza: $T = T_q + \bar{s}$
$J$ $J$ - Prosečan/očekivani broj poslova u sistemu
- $J = \sum_{i = 0}^n ip_i$ - gde se $i$ slaže sa brojem poslova u sistemu.
$J_q$ $J_q$ - Prosečan/očekivani broj poslova u redu za čekanje
- Važi ista formula kao za J, samo što se verovatnoće množe sa brojem poslova u redu za čekanje.
$X$ $X$ - Protok kroz sistem
- Ujedno i protok kroz red za čekanje
- Ukoliko je red za čekanje beskonačan nema odbijanja poslova, što znači da je protok isti kao i intenzitet pristizanja poslova. $X = \lambda$
- Inače, protok je $X = (1 - p_{MAX})\lambda$ , gde je $p_{MAX}$ poslednje stanje u kom nema mesta u redu za čekanje.
$X' = p_{MAX}\lambda$ - Protok odbijenih poslova
$T = \frac{J}{X}$ $T = \frac{J}{X}$ - Litlova formula. Važi za ceo sistem.
- Moguće je posmatrati samo red za čekanje i tu važi: $T_q = \frac{J_q}{X}$
- Veza: $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$ - Iskorišćenost sistema. Iskorišćenost nekog dela $U_i$ $U_i$ se definiše kao broj poslova podeljen sa kapacitetom.
- Važi $U = 1 -$ neiskorišćeni deo sistema.

Protok kroz sistem je svuda isti.
Ovo znači da vreme provedeno u procesorskom delu sistema i disk delu sistema ima isti protok, pa važi: $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 - vreme prolaska jednog posla kroz ceo sistem.
Pošto je protok u celom sistemu isti, kod grananja ekvivalentnih paralelnih servera važi:
- $X = nX_p = mX_d$ , $n$ broj procesora, $m$ broj diskova.
Zakon iskorišćenja jednog servera/diska: $U_p = X_pS_p$ $U_p = X_pS_p$
- Pošto je protok svuda isti: $\frac{U_p}{U_d} = \frac{X_pS_p}{X_dS_d}$

Gordon-Njuelov metod definiše $x_i$ kao potražnju servera $i$ . Ovaj faktor je relativan i obično se uzima da je potražnja prvog servera (procesora) $x_1 = 1$ .
GNj sistem jednačina se formira ovako:
- Svaki sistem ima svoju jednačinu, gde sa leve strane jednakosti stoje $\mu_ix_i$ , a sa desne, za svaku granu koja ulazi u sistem (tj. njegov red za čekanje) $p_i\mu_ix_i$ .
- $p_i$ je verovatnoća ulaska u granu.
$G(n)$ - konstanta sistema koja zavisi od broja poslova u sistemu. Najlakše se određuje Bjuzenovim metodom.
$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)}$ - Verovatnoća da u nekom sistemu ima više od $k$ $k$ procesa.
- $N$ je ukupan broj poslova u sistemu.
- $j$ je redni broj sistema.
- $x_j$ je njegov faktor potražnje.
$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)}$ - Verovatnoća da sistem ima tačno $k$ poslova.
$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)}$ - Iskorišćenost servera
- Server koji ima najveću iskorišćenost je usko grlo.
$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)}$ - Prosečan/očekivani broj poslova na serveru.
$P_{j_1j_2j_3...j_n} = \frac{x_1^{j_1}x_2^{j_2} ... x_n^{j_n}}{G(N)}$ - Verovatnoća da u sistemu sa $n$ servera i $N$ poslova svaki pojedinačni server ima $j_i$ poslova.

$\overline{\theta}$ : vreme razmišljanja (vreme tokom kog se korisnik odlučuje šta da upiše na terminal)
$\overline{w}$ : vreme provedeno u redu za čekanje
$\overline{r}$ $\overline{r}$ : vreme odziva procesora
- $\overline{r} = \overline{w} + \overline{s}$
$T_c$ $T_c$ : vreme ciklusa na procesoru
- $T_c = \overline{w} + \overline{s} + \overline{\theta} = \overline{r} + \overline{\theta}$
- Primenjena Litlova formula: $T_c = \frac{n}{X}$
$n^*$ $n^*$ : kritičan broj terminala (koliko maksimalno terminala možemo da imamo u sistemu tako da ostane $\overline{w} = 0$ $\overline{w} = 0$ )
- $n^* = \left\lfloor 1 + \frac{\overline{\theta}}{\overline{s}} \right\rfloor$
Iskorišćenje u interaktivnom sistemu (opet dobijeno iz Litlove formule): $U = \frac{n \overline{s}}{T_c}$ $U = \frac{n \overline{s}}{T_c}$
- Za $\overline{w} = 0$ važi $U(n) = \frac{n \cdot \overline{s}}{\overline{s} + \overline{\theta}}$
- Za sistem u zasićenju važi: $1 = \frac{n \cdot \overline{s}}{\overline{r}(n) + \overline{\theta}}$
Rekurentna formula za računanje verovatnoća stanja sistema: $\frac{1}{p_0(n)} = 1 + n\rho \frac{1}{p_0(n-1)}$

Džeksonova teorema: možemo posmatrati servisne centre kao da su nezavisni M/M/1 serveri.
Jednačina otvorene mreže sa centralnim serverom: $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}$
- $V_0, V_1, ..., V_k$ : prosečan broj poseta svakom od servisnih centara (<math>V_0 je centralni server)