NobrSorbanállási rendszerek összehasonlítása/nobr

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

<style> img { margin: 5px 0px; } </style>

Teljesítményjellemzők

• Stabilitás: egy puffer stabil, ha a benne lévő igények számának várható értéke véges.
  • A véges méretű puffer mindig stabil.
  • A végtelen méretű akkor, ha az érkezési intenzitás kisebb, mint a kiszolgálási intenzitás.
  • Egy rendszer akkor stabil, ha az összes puffere stabil.
• ρ = kihasználtság: 0 és 1 közötti mennyiség
  • Kiszolgálóra: átlagosan az idő hány százalékában dolgozik a kiszolgáló.
  • Rendszerre: a kiszolgálók átlagosan hány százaléka dolgozik.
• _S_ = átvitel: távozási intenzitás.
• _T_, E[T] = (átlagos) válaszidő: mennyi idő telik el egy igény rendszerbe való belépésétől a kiszolgálása végéig.
• _W_, E[W] = (átlagos) várakozási idő: mennyi időt tölt egy igény a pufferben.
• _x_, E[x] = (átlagos) kiszolgálási idő: meddig tart egy igény kiszolgálása, miután sorra került.
• _X_, E[X] = rendszerben lévő igények (átlagos) száma.

Kendall jelölésrendszer

A/B/c/d/e − x

• A:   az érkezési időközök eloszlásának típusa.
  

Lehetőségek:

• • M : emlékezetmentes eloszlás (folytonos időben markovi) exponenciális eloszlás
  • Geom: emlékezetmentes eloszlás (diszkrét időben markovi) geometriai eloszlás
  • D: determinisztikus eloszlás
  • G: általános eloszlás (egyes -főleg régebbi - irodalmakban egyúttal független és azonos általános eloszlás)
  • GI: (egyes újabb irodalmakban ezt használják a független, azonos, általános eloszlás jelölésére)

• B:   a kiszolgálási idő eloszlásának típusa.
  • Lehetőségek: ld. A

• c:   a kiszolgáló egységek száma
  • Véges vagy végtelen is lehet.

• d:   a rendszer kapacitása
  • Beleértve a kiszolgáló egységet is!

• e:   az igényforrások száma
  • Véges vagy végtelen is lehet.

• x:   kiszolgálási elv
  • FIFO (FCFS) – First In First Out (First Come First Served)
  • LIFO (LCFS) – Last In First Out (Last Come First Served)
  • RO – Random Order
  • RR – Round Robin
  • PS – Processor Sharing
  • Priority

-- Zoz - 2007.11.18.

M/M/1

• állapotgráf:
  

Ezen a helyen volt linkelve a MM1_allapotgraf.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• stabil, ha λ<μ
• $p_{i}=p_{0}({\frac {\lambda }{\mu }})^{i},p_{0}=1-{\frac {\lambda }{\mu }}$
  $1-{\frac {\lambda }{\mu }}$ paraméterű geometriai eloszlás eggyel elcsúsztatott indexszel
• kihasználtság: $\rho =1-p_{0}={\frac {\lambda }{\mu }}$
• átvitel: $S=\lambda$
• rendszerbeli igények átlagos száma: $E[X]=\sum _{k=1}^{\infty }k(1-\rho )\rho ^{k}=\rho \sum _{k=1}^{\infty }k(1-\rho )\rho ^{k-1}=$
  $\rho (1-\rho )$ paraméterű geometriai eloszlás várható értéke$={\frac {\rho }{1-\rho }}={\frac {\lambda }{\mu -\lambda }}$
• átlagos válaszidő (rendszerbe belépéstől kiszolgálás befejezéséig):
  Little-formula alapján $E[T]={\frac {E[X]}{E[\lambda ]}}={\frac {1}{\mu -\lambda }}$

M/M/1 teljesítményjellemzőinek számolása az M/G/1 speciális eseteként

M/M/m

• állapotgráf:
  

Ezen a helyen volt linkelve a MMm_allapotgraf.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• stabil, ha λ<mμ
• átvitel: A Little-formula szerint a dolgozó kiszolgálók számának várható értéke (E[X_S]) egyenlő az átlagos érkezési intenzitás (λ) és az átlagos kiszolgálási idő $({\frac {1}{\mu }})$ szorzatával. $\rho ={\frac {E[X_{S}]}{m}}={\frac {\lambda }{m\mu }}$
• átlagos várakozási idő: $E[W]=\sum _{i=m}^{\infty }E[W|i]p_{i}=\sum _{i=m}^{\infty }{\frac {i-m+1}{m\mu }}p_{i}$
• várakozás valószínűsége: ErlangC formula (nem kell tudni)
• kihasználtság:
  • $\rho _{k}=E[\rho |k]=$
    • ${\frac {k}{m}}$, ha k < m
    • 1, ha k >= m
  • $\rho ={\frac {\lambda }{m\mu }}$

M/M/∞

• állapotgráf:
  

Ezen a helyen volt linkelve a MMv_allapotgraf.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• mindig stabil
• $p_{k}=({\frac {\lambda }{\mu }})^{k}{\frac {\mathrm {e} ^{-({\frac {\lambda }{\mu }})}}{k!}}$ — Poisson-eloszlás
• várakozási idő: $E[W]=0$, mert végtelen sok kiszolgáló van
• kiszolgálási idő: $E[x]={\frac {1}{\mu }}$
• válaszidő: $E[T]={\frac {1}{\mu }}$
• rendszerbeli igények átlagos száma: $E[X]=E[T]E[\lambda ]={\frac {\lambda }{\mu }}$
• kihasználtság: $\rho =1-p_{0}=1-\mathrm {e} ^{-{\frac {\lambda }{\mu }}}$
• átvitel: $S=\lambda$

M/M/m/m

• állapotgráf:
  

Ezen a helyen volt linkelve a MMmm_allapotgraf.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• stabil, mert véges a pufferméret
• veszteség valószínűség: $p_{l}oss=p_{m}$, mert egy konkrét igény szempontjából nézve a rendszert az igény akkor veszik el, ha minden kiszolgáló foglalt, aminek $p_{m}$ a valószínűsége. $p_{m}$ értékét az ErlangB formulával lehet kiszámolni.
• átvitel: $\lambda =S_{light}<S_{altalanos}<S_{heavy}=m\mu$
• kiszolgálási idő: $E[x]={\frac {1}{\mu }}$
• várakozási idő: $E[W]=0$
• válaszidő: $E[T]=E[x]+E[W]={\frac {1}{\mu }}$

M/M/1//N

• jelölés: egy igényforrás $\alpha$ intenzitással generál igényeket
• állapotgráf _K_ igényforrás esetén:
  

Ezen a helyen volt linkelve a MM1vN_allapotgraf.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• stabil, mert véges az igényforrások száma
• light load válaszidő ($\alpha K\ll \mu$): $E[T]={\frac {1}{\mu }}$
• heavy load válaszidő ($\alpha K\gg \mu$):
  • hivatalos megoldás: $E[T]={\frac {K}{\mu }}-{\frac {1}{\alpha }}$
  • szerintem: $E[T]={\frac {K}{\mu }}$, mert egy igénynek meg kell várnia a sorban előtte lévő K-1 igény, majd a saját kiszolgálását. Mindegyik átlagosan ${\frac {1}{\mu }}$ ideig tart, ez összesen ${\frac {K}{\mu }}$.
  • $\alpha K\gg \mu$-t átrendezve ${\frac {K}{\mu }}\gg {\frac {1}{\alpha }}$-t kapunk, ezért az ${\frac {1}{\alpha }}$ tag elhanyagolható, és így egyezik a hivatalos megoldás az enyémmel.
• light load átvitel: veszteségmentes a rendszer $\Rightarrow S=E[\lambda ]$. Az érkezési intenzitás pedig $E[\lambda ]=K\alpha$, mert _K_ független, kicsi $\alpha$ intenzitású igényforrás termeli az igényeket, és a kiszolgálási idő elhanyagolható az igény keletkezések között eltelt időhöz képest.
• heavy load átvitel: $S=\mu$, mert a kiszolgáló folyamatosan kap kéréseket

M/M/m/K/N

• állapotgráf: TODO
• stabil, mert véges a pufferméret

M/G/1

• Tegyük fel, hogy ismert a kiszolgálási idő várható értéke (E[x]) és relatív szórása (C_s).
• Várakozási idő: $\mathrm {E} [W]={\frac {\rho }{1-\rho }}\mathrm {E} [x]{\frac {1+C_{S}^{2}}{2}}$ (Pollaczek—Hincsin-féle várható érték formula)
• Teljes rendszerben töltött idő: E[T] = E[x] + E[W]
• A kihasználtság a Little-formulából számolható: ρ = λE[x]. Akkor stabil, ha λE[x] < 1.
• Rendszerben lévő igények száma: E[X] = λE[T]

Speciális esetek

M/M/1

• $E[x]={\frac {1}{\mu }}$
• $C_{S}=1$
• $\rho =\lambda E[x]={\frac {\lambda }{\mu }}$
• $\mathrm {E} [W]={\frac {\lambda /\mu }{1-\lambda /\mu }}{\frac {1}{\mu }}{\frac {1+1^{2}}{2}}={\frac {\lambda }{\mu (\mu -\lambda )}}$
• $\mathrm {E} [T]={\frac {1}{\mu }}+{\frac {\lambda }{\mu (\mu -\lambda )}}={\frac {1}{\mu -\lambda }}$
• $\mathrm {E} [X]=\lambda \mathrm {E} [T]={\frac {\lambda }{\mu -\lambda }}$

M/D/1

• E[x] = _x_ = _D_
• C_S = 0
• ρ = λE[x] = λD
• $\mathrm {E} [W]={\frac {\lambda D}{1-\lambda D}}D{\frac {1+0^{2}}{2}}={\frac {1}{2}}{\frac {\lambda D^{2}}{1-\lambda D}}$
• $\mathrm {E} [T]=D+{\frac {1}{2}}{\frac {\lambda D^{2}}{1-\lambda D}}$
• $\mathrm {E} [X]=\lambda \mathrm {E} [T]=\lambda D+{\frac {1}{2}}{\frac {(\lambda D)^{2}}{1-\lambda D}}$

Ld. még: elméleti és gyakorlati M/G/1 kidolgozások

M/G/1/1

• Kihasználtság: E[x] ideig tart a kiszolgálás, utána ${\frac {1}{\lambda }}$ ideig kell várakozni a következő kérésre $\Rightarrow \rho ={\frac {E[x]}{E[x]+{\frac {1}{\lambda }}}}$. A Little-formula nem használható, mert veszteséges a rendszer.
• Igényvesztés valószínűsége: a rendszer ρ valószínűséggel foglalt, azaz egy újonnan érkező igény ekkora valószínűséggel veszik el.

-- Peti - 2006.12.12.