PRS/Formule

Operativna memorija

Osnovni pojmovi

• U redu za čekanje uvek ima poslova.
• $S$: veličina posla za učitavanje u memoriju
• $t$: vreme zadržavanja programa u memoriji
• $U$: iskorišćenje memorije
  • $\overline{U} = \frac{\sum_{i = 0}^n t_i \cdot S_i}{\sum_{i = 0}^n t_i}$
• Modeli veličina poslova:
  • Model jednakih veličina: svi poslovi imaju jednake veličine
  • Model jednakoverovatnih veličina: imamo minimalnu i maksimalnu veličinu posla, i ista je verovatnoća da se bilo koja veličina od njih pojavi
  • Eksponencijalna raspodela veličina: više ima manjih poslova ili obrnuto
• Modeli vremena zadržavanja u memoriji:
  • Konstantno vreme zadržavanja
  • Funkcija od veličine programa
• Monoprogramski sistem: samo jedan program je učitan u memoriju
• Statičke particije: u svaku particiju operativne memorije može biti učitan jedan program

Model statičkih particija

• Veličine veće i manje particije označavamo sa $x_b$ i $x_s$.
• Normalizujemo po veličini veće particije: $x_b = 1$
• Mali programi mogu da stanu u manju particiju, veliki ne mogu.
• Oznake stanja:
  • $E$: prazne particije
  • $BS$: programi učitani i u veliku i u malu particiju
  • $BE$: veliki program učitan u veliku particiju
  • $SE$: mali program učitan u veliku particiju
    • Ako je vreme zadržavanja u memoriji konstantno, ovo stanje ne postoji!
  • $SS$: mali programi učitani u obe particije
  • $ES$ nije moguće stanje!
• Iskorišćenje računamo na osnovu veličine prosečnog programa.
• Statičke verovatnoće stanja: verovatnoća da se nalazimo u nekom stanju
• Prosečno iskorišćenje: $\overline{U} = \overline{U_{BS}} \cdot p_{BS} + U_{SS} \cdot p_{SS} + ...$
• Rekurentno vreme stanja: $\frac{1}{1 - p}$ gde je $p$ verovatnoća da se ostaje u stanju (izvođenje preko matematičkog očekivanja i potencijalnog reda)

Knutov model

• Ravnotežno stanje: jednaka verovatnoća alokacije i dealokacije memorije
• Četiri scenarija oslobađanja bloka: HBH, HBB, BBH, BBB
  • Broj slučajeva HBB jednak je broju slučajeva BBH (jedan se nalazi na početku sekvence blokova a drugi na kraju)
  • U HBH imamo dve rupe, u HBB i BBH jednu, pa na osnovu toga možemo izraziti ukupan broj rupa.
• Verovatnoća perfect fit teži nuli.
• Knutov zakon: broj rupa teži polovini broja blokova.
• Odnos veličine rupa i blokova: $c = \frac{\overline{H}}{\overline{S}}$
  • Mora biti $c < 1$ jer je red poslova beskonačan.
• Iskorišćenje memorije: $U = \frac{2}{2 + c}$

Beteridžov model

• Memorija podeljena na $M$ blokova, programi veličine 1, 2, 3... bloka, a relokacija nije dozvoljena.
• Sve veličine programa su jednako verovatne, i pri prelazima između stanja je uvek završio tačno jedan program.
• Moguća stanja za sistem sa veličinom memorije 2: SS, B, SE, ES.
  • Broj stanja raste eksponencijalno sa veličinom memorije.
• Model statičkih stranica: programi više ne moraju da budu tačne veličine u blokovima, postoji interna fragmentacija.
  • Odbačeni deo memorije: $W = \frac{n_{avr}}{2}$ blokova, gde je $n_{avr}$ prosečan stepen multiprogramiranja.

Virtuelna memorija

• $x$: veličina jedne stranice
• $k$: veličina ulaza u PMT
• $N$: broj stranica
• $M_{PMT}$: količina memorije koja ode na PMT
  • $M_{PMT} = \frac{M}{x} \cdot k$
• Odbačeni deo memorije: $W = M_{PMT} + \frac{n_{avr} \cdot x}{2}$
• Optimalna veličina stranice: $x_{opt} = \sqrt{\frac{2Mk}{n_{avr}}}$
• $\frac{1}{R}$: verovatnoća da je poslednja stranica programa u memoriji
  • Ukoliko je data, onda $W = M_{PMT} + \frac{n_{avr} \cdot x}{2} \cdot \frac{1}{R}$

Diskovi

• $T$: vreme za prenos zapisa u memoriju.
  • $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 vreme
    • $n_{c_1}$: broj cilindara prvog diska
    • $c_1$: prvi cilindar prvog diska
    • $t(z - x)$: koliko disku treba vremena da pređe od cilindra $x$ do cilindra $z$
    • Ukoliko se ide sa cilindra jedne datoteke na istu datoteku: $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}$: vreme obrtanja diska
    • $v_{rot}$: brzina obrtanja diska
  • $T_{rd} = \frac{T_{rev}}{2}$
  • $T_{dt} = c \cdot T_{rev}$
    • $T_{dt}$: data transfer vreme
    • $c$: koji deo staze zauzima jedan zapis
    • Ukoliko se samo vrši pristup, a ne i transfer podataka, onda je $T_{dt} = 0$.

Poasonov proces

Osnovni termini

• $\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

• 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): $1 + \rho + \rho^2 + ... \rho^n = \sum_{i = 0}^{n} \rho^i = \frac{1 - \rho^{n+1}}{1 - \rho}$
  • Paziti na slučaj gde $\rho = 1$. Tada je vrednost niza $n\rho$.

Karakteristike sistema

• $T$ - Prosečno/očekivano vreme obrade poslova/vreme odziva u sistemu
• $T_q$ - Prosečno/očekivano vreme obrade poslova/vreme odziva u redu za čekanje
  • Veza: $T = T_q + \bar{s}$
• $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$ - 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$ - 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}$ - 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$ - Iskorišćenost sistema. Iskorišćenost nekog dela $U_i$ se definiše kao broj poslova podeljen sa kapacitetom.
  • Važi $U = 1 -$ neiskorišćeni deo sistema.

Ciklični model multiprogramiranja

• 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$
  • Pošto je protok svuda isti: $\frac{U_p}{U_d} = \frac{X_pS_p}{X_dS_d}$

Gordon-Njuelov metod

• 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)}$ - Verovatnoća da u nekom sistemu ima više od $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)}$ - 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.

Otvorene mreže

• Džeksonova teorema: možemo posmatrati servisne centre kao da su nezavisni M/M/1 serveri.
  • Vreme odziva pojedinačnog servera dobijamo kao: $R_i = \frac{1}{\mu_i - X_i}$ (primena Litlove formule za M/M/1 sistem)
  • Verovatnoće stanja ukupnog sistema se dobijaju kao proizvodi pojedinačnih stanja sistema.
  • Za M/M/1 važi: $p_0 = 1 - \rho$, $p_i = \rho^i p_0$, $J = \frac{\rho}{1 - \rho}$
• 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}$
  • Sabirci su redom jednaki: $p_1, p_2, ..., p_k, p_0$
  • $V_0, V_1, ..., V_k$: prosečan broj poseta svakom od servisnih centara ($V_0$ je centralni server, u zadacima, uzeti da je $V_0 = 1$)

Interaktivni sistemi

• $\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}$: vreme odziva procesora
  • $\overline{r} = \overline{w} + \overline{s}$
• $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^*$: kritičan broj terminala (koliko maksimalno terminala možemo da imamo u sistemu tako da ostane $\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}$
  • 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 (važi samo za sistem sa jednim procesorom): $\frac{1}{p_0(n)} = 1 + n\rho \frac{1}{p_0(n-1)}$

MVA analiza

• Ulazni parametri:
  • $n$: ukupan broj poslova u sistemu
  • $Z$: srednje vreme razmišljanja terminala, ako sistem nije interaktivan onda je 0
  • $S_j$: vreme opsluživanja jednog posla na servisnom centru $j$
  • $V_j$: prosečan broj poseta servisnom centru $j$
  • $D_j$: potražnja servisnog centra $j$
    • Koristi se u drugoj varijanti algoritma, i dobija se kao $S_j \cdot V_j$.
• Promenljive:
  • $Q_j(n)$: broj poslova u servisnom centru $j$
  • $r_j(n)$: zadržavanje u servisnom centru $j$
  • $R(i)$: vreme zadržavanja posla u sistemu (vreme odziva)
  • $R_j(i)$: vreme zadržavanja posla u servisnom centru $j$
  • $X(i)$: protok kroz sistem
  • $X_j(i)$: protok kroz servisni centar $j$
  • $U_j(i)$: iskorišćenje servisnog centra $j$