ПРС/Формуле

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

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

• $\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 = 1$. Тада је вредност низа $n\rho$.

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

• $T$ - Просечно/очекивано време обраде послова/време одзива у систему
• $T_q$ - Просечно/очекивано време обраде послова/време одзива у реду за чекање
  • Веза: $T = T_q + \bar{s}$
• $J$ - Просечан/очекивани број послова у систему
  • $J = \sum_{i = 0}^n ip_i$ - где се $i$ слаже са бројем послова у систему.
• $J_q$ - Просечан/очекивани број послова у реду за чекање
  • Важи иста формула као за J, само што се вероватноће множе са бројем послова у реду за чекање.
• $X$ - Проток кроз систем
  • Уједно и проток кроз ред за чекање
  • Уколико је ред за чекање бесконачан нема одбијања послова, што значи да је проток исти као и интензитет пристизања послова. $X = \lambda$
  • Иначе, проток је $X = (1 - p_{MAX})\lambda$, где је $p_{MAX}$ последње стање у ком нема места у реду за чекање.
• $X' = p_{MAX}\lambda$ - Проток одбијених послова
• $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_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$
  • Пошто је проток свуда исти: $\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)}$ - Вероватноћа да у неком систему има више од $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)}$ - Искоришћеност сервера
  • Сервер који има највећу искоришћеност је уско грло.
• $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{w} + \overline{s}$
• $T_c$: време циклуса на процесору
  • $T_c = \overline{w} + \overline{s} + \overline{\theta} = \overline{r} + \overline{\theta}$
  • Примењена Литлова формула: $T_c = \frac{n}{X}$
• $n^*$: критичан број терминала (колико максимално терминала можемо да имамо у систему тако да остане $\overline{w} = 0$)
  • $n^* = \left\lfloor 1 + \frac{\overline{\theta}}{\overline{s}} \right\rfloor$
• Искоришћење у интерактивном систему (опет добијено из Литлове формуле): $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}$
  • Сабирци су редом једнаки: $p_0, p_1, ..., p_n$
  • $V_0, V_1, ..., V_k$: просечан број посета сваком од сервисних центара ($V_0$ је централни сервер, у задацима, узети да је $V_0 = 1$)

МВА анализа

• Улазни параметри:
  • $n$: укупан број послова у систему
  • $Z$: средње време размишљања терминала, ако систем није интерактиван онда је 0
  • $S_j$: време опслуживања једног посла на сервисном центру $j$
  • $V_j$: просечан број посета сервисном центру $j$
  • $D_j$: потражња сервисног центра $j$
    • Користи се у другој варијанти алгоритма, и добија се као $S_j \cdot V_j$.
• Променљиве:
  • $Q_j(n)$: број послова у сервисном центру $j$
  • $r_j(n)$: задржавање у сервисном центру $j$
  • $R(i)$: време задржавања посла у систему (време одзива)
  • $R_j(i)$: време задржавања посла у сервисном центру $j$
  • $X(i)$: проток кроз систем
  • $X_j(i)$: проток кроз сервисни центар $j$
  • $U_j(i)$: искоришћење сервисног центра $j$