ПРС/Формуле

Оперативна меморија

Основни појмови

• У реду за чекање увек има послова.
• $S$: величина посла за учитавање у меморију
• $t$: време задржавања програма у меморији
• $U$: искоришћење меморије
  • $\overline{U} = \frac{\sum_{i = 0}^n t_i \cdot S_i}{\sum_{i = 0}^n t_i}$
• Модели величина послова:
  • Модел једнаких величина: сви послови имају једнаке величине
  • Модел једнаковероватних величина: имамо минималну и максималну величину посла, и иста је вероватноћа да се било која величина од њих појави
  • Експоненцијална расподела величина: више има мањих послова или обрнуто
• Модели времена задржавања у меморији:
  • Константно време задржавања
  • Функција од величине програма
• Монопрограмски систем: само један програм је учитан у меморију
• Статичке партиције: у сваку партицију оперативне меморије може бити учитан један програм

Модел статичких партиција

• Величине веће и мање партиције означавамо са $x_b$ и $x_s$.
• Нормализујемо по величини веће партиције: $x_b = 1$
• Мали програми могу да стану у мању партицију, велики не могу.
• Ознаке стања:
  • $E$: празне партиције
  • $BS$: програми учитани и у велику и у малу партицију
  • $BE$: велики програм учитан у велику партицију
  • $SE$: мали програм учитан у велику партицију
    • Ако је време задржавања у меморији константно, ово стање не постоји!
  • $SS$: мали програми учитани у обе партиције
  • $ES$ није могуће стање!
• Искоришћење рачунамо на основу величине просечног програма.
• Статичке вероватноће стања: вероватноћа да се налазимо у неком стању
• Просечно искоришћење: $\overline{U} = \overline{U_{BS}} \cdot p_{BS} + U_{SS} \cdot p_{SS} + ...$
• Рекурентно време стања: $\frac{1}{1 - p}$ где је $p$ вероватноћа да се остаје у стању (извођење преко математичког очекивања и потенцијалног реда)

Кнутов модел

• Равнотежно стање: једнака вероватноћа алокације и деалокације меморије
• Четири сценарија ослобађања блока: HBH, HBB, BBH, BBB
  • Број случајева HBB једнак је броју случајева BBH (један се налази на почетку секвенце блокова а други на крају)
  • У HBH имамо две рупе, у HBB и BBH једну, па на основу тога можемо изразити укупан број рупа.
• Вероватноћа perfect fit тежи нули.
• Кнутов закон: број рупа тежи половини броја блокова.
• Однос величине рупа и блокова: $c = \frac{\overline{H}}{\overline{S}}$
  • Мора бити $c < 1$ јер је ред послова бесконачан.
• Искоришћење меморије: $U = \frac{2}{2 + c}$

Бетериџов модел

• Меморија подељена на $M$ блокова, програми величине 1, 2, 3... блока, а релокација није дозвољена.
• Све величине програма су једнако вероватне, и при прелазима између стања је увек завршио тачно један програм.
• Могућа стања за систем са величином меморије 2: SS, B, SE, ES.
  • Број стања расте експоненцијално са величином меморије.
• Модел статичких страница: програми више не морају да буду тачне величине у блоковима, постоји интерна фрагментација.
  • Одбачени део меморије: $W = \frac{n_{avr}}{2}$ блокова, где је $n_{avr}$ просечан степен мултипрограмирања.

Виртуелна меморија

• $x$: величина једне странице
• $k$: величина улаза у PMT
• $N$: број страница
• $M_{PMT}$: количина меморије која оде на PMT
  • $M_{PMT} = \frac{M}{x} \cdot k$
• Одбачени део меморије: $W = M_{PMT} + \frac{n_{avr} \cdot x}{2}$
• Оптимална величина странице: $x_{opt} = \sqrt{\frac{2Mk}{n_{avr}}}$
• $\frac{1}{R}$: вероватноћа да је последња страница програма у меморији
  • Уколико је дата, онда $W = M_{PMT} + \frac{n_{avr} \cdot x}{2} \cdot \frac{1}{R}$

Дискови

• $T$: време за пренос записа у меморију.
  • $T = T_{am} + T_{rd} + T_{dt}$
  • $T_{am} = \frac{1}{n_{c_1} n_{c_2}} \int_{c_1}^{c_1 + n_{c_1}} \int_{c_2}^{c_2 + n_{c_2}} t(z - x) dx dz$
    • $T_{am}$: access motion време
    • $n_{c_1}$: број цилиндара првог диска
    • $c_1$: први цилиндар првог диска
    • $t(z - x)$: колико диску треба времена да пређе од цилиндра $x$ до цилиндра $z$
    • Уколико се иде са цилиндра једне датотеке на исту датотеку: $T_{am} = \frac{2}{n_c^2} \int_0^{n_c} (n_c - x) t(x) dx$
  • $T_{rev} = \frac{1}{v_{rot}}$
    • $T_{rev}$: време обртања диска
    • $v_{rot}$: брзина обртања диска
  • $T_{rd} = \frac{T_{rev}}{2}$
  • $T_{dt} = c \cdot T_{rev}$
    • $T_{dt}$: data transfer време
    • $c$: који део стазе заузима један запис
    • Уколико се само врши приступ, а не и трансфер података, онда је $T_{dt} = 0$.

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

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

• $\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$ и то је неопходно проверити - иначе ред дивергира и анализа није применљива.
• За непознат али коначан број стања јавља се и геометријски низ (који има коначан број чланова): $1 + \rho + \rho^2 + ... \rho^n = \sum_{i = 0}^{n} \rho^i = \frac{1 - \rho^{n+1}}{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_1, p_2, ..., p_k, p_0$
  • $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$