5.6: Round-robin y uso compartido de procesadores
- Page ID
- 86209
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Los sistemas de colas típicos tienen uno o más servidores, cada uno de los cuales atiende a los clientes en orden FCFS, sirviendo a un cliente completamente mientras otros clientes esperan. Estos sistemas típicos tienen un retardo promedio mayor de lo necesario. Por ejemplo, si dos clientes con requisitos de servicio de 10 y 1 unidades respectivamente están esperando cuando un solo servidor se vacíe, entonces servir el primero antes del segundo da como resultado salidas en los tiempos 10 y 11, para un retraso promedio de 10.5. Servir a los clientes en el orden opuesto da como resultado salidas en los tiempos 1 y 11, para un retraso promedio de 6. Los supermercados lo han reconocido desde hace años y tienen líneas especiales de pago exprés para clientes con pequeños requisitos de servicio.
Dar prioridad a clientes con requisitos de servicio pequeños, sin embargo, tiene algunas desventajas; primero, los clientes con altos requisitos de servicio pueden sentirse discriminados, y segundo, no siempre es posible determinar los requisitos de servicio de los clientes antes de que sean atendidos. La siguiente alternativa a las prioridades es popular tanto en las industrias de computadoras como de redes de datos. Cuando un procesador en un sistema informático tiene muchos trabajos que cumplir, a menudo atiende estos trabajos en una base de tiempo compartido, gastando un pequeño incremento de tiempo en uno, luego en el siguiente, y así sucesivamente. En las redes de datos, particularmente las redes de alta velocidad, los mensajes se rompen en pequeños paquetes de longitud fija, y luego los paquetes de diferentes mensajes pueden transmitirse de manera alterna entre mensajes.
Un sistema de servicio round-robin es un sistema en el que, si hay m clientes en el sistema\(c_{1}, c_{2}, \ldots, c_{m}\), digamos,\(c_{1}\) se sirve por un intervalo incremental\(\delta\), seguido de\(c_{2}\) ser atendido por un intervalo\(\delta\), y así sucesivamente hasta\(c_{m}\). Después de\(c_{m}\) que se sirve por un intervalo\(\delta\), el servidor regresa y comienza a servir\(c_{1}\) por un intervalo de\(\delta\) nuevo. Así, los clientes son atendidos en un orden cíclico, o “round-robin”, cada uno obteniendo un pequeño incremento de servicio en cada visita desde el servidor. Cuando se completa el servicio de un cliente, el cliente abandona el sistema,\(m\) se reduce y el servidor continúa rotando a través del ciclo ahora reducido como antes. Cuando llega un nuevo cliente,\(m\) se incrementa y el nuevo cliente debe insertarse en el ciclo de clientes existentes de una manera que se discutirá más adelante.
El uso compartido del procesador es el límite del servicio round-robin ya que el incremento\(\delta\) va a cero. Así, con el procesador compartido, si m clientes están en el sistema, todos están siendo atendidos simultáneamente, pero cada uno está siendo atendido a\(1 / m\) veces la tarifa básica del servidor. Para el ejemplo de dos clientes con requerimiento de servicio 1 y 10, cada cliente es atendido inicialmente a tarifa 1/2, por lo que un cliente sale al tiempo 2. En ese momento, el cliente restante es atendido a la tarifa 1 y sale en el momento 11. Para el servicio round robin con un incremento de 1, el cliente con requerimiento de servicio de unidad sale en cualquier momento 1 o 2, dependiendo del orden inicial del servicio. Con otros incrementos de servicio, los resultados son ligeramente diferentes.
Primero analizamos el servicio round-robin y luego pasamos al límite de compartición del procesador como\(\delta \rightarrow 0\). Como sugiere el ejemplo anterior, los resultados son algo más limpios en el caso limitante, pero más realistas en el caso de todos contra todos. Round robin proporciona un buen ejemplo del uso de probabilidades de transición hacia atrás para encontrar la distribución en estado estacionario de una cadena de Markov. Las técnicas utilizadas aquí son bastante similares a las utilizadas en el siguiente capítulo para analizar las redes de cola.
Asumir un proceso de llegada a Bernoulli en el que se\(\delta\) encuentra la probabilidad de una llegada en un intervalo\(\lambda \delta\). Supongamos que el cliente que\(i^{t h}\) llega tiene un requisito de servicio\(W_{i}\). Las variables aleatorias\(W_{i}, i \geq 1\), son IID e independientes de las épocas de llegada. Así, en términos del proceso de llegada y los requisitos de servicio, esto es lo mismo que una cola M/G/1 (ver Sección 4.5.5), pero con las colas M/G/1, el servidor atiende completamente a cada cliente antes de pasar al siguiente cliente. Encontraremos que el servicio round robin aquí evita el “efecto camión lento” identificado con la cola M/G/1.
Por simplicidad, supongamos que\(W_{i}\) es aritmética con span\(\delta\), tomando solo valores que son múltiplos enteros positivos de\(\delta\). Dejar\(f(j)=\operatorname{Pr}\left\{W_{i}=j \delta\right\}, j \geq 1\) y dejar\(\overline{F}(j)=\operatorname{Pr}\left\{W_{i}>j \delta\right\}\). Tenga en cuenta que si un cliente ya ha recibido j incrementos de servicio, entonces la probabilidad de que ese cliente salga después de 1 incremento más es\(f(j+1) / \overline{F}(j)\). Esta probabilidad de salida en el siguiente incremento de servicio después de la\(j^{t h}\) se denota por
\[g(j)=f(j+1) / \overline{F}(j) ; j \geq 1\label{5.47} \]
El estado\(\mathcal{s}\) de un sistema round-robin se puede expresar como el número,\(m\), de clientes en el sistema, junto con una lista ordenada de cuántos incrementos de servicio ha recibido cada uno de esos\(m\) clientes, es decir,
\[\boldsymbol{s}=\left(m, z_{1}, z_{2}, \ldots, z_{m}\right)\label{5.48} \]
donde\(z_{1} \delta\) esta la cantidad de servicio ya recibida por el cliente al frente de la cola,\(z_{2} \delta\) es el servicio ya recibido por el siguiente cliente en orden, etc. en el caso especial de una cola inactiva,\(\boldsymbol{s}=(0)\), que denotamos como\(\phi\).
Dado que el estado\(X_{n}\) en el momento\(n \delta\) es\(s \neq \phi\), el estado\(X_{n+1}\) en el momento\(n \delta+\delta\) evoluciona de la siguiente manera:
- Una nueva llegada entra con probabilidad\(\lambda \delta\) y se coloca al frente de la cola;
- El cliente al frente de la cola recibe un incremento\(\delta\) de servicio;
- El cliente sale si el servicio está completo.
- De lo contrario, el cliente va al fondo de la cola
Se puede observar que la transición de estado depende, primero, de si se produce una nueva llegada (un evento de probabilidad\(\lambda \delta\)), y, segundo, de si se produce una salida. Si no se produce llegada y no hay salida, entonces la cola simplemente gira. El nuevo estado es\(\boldsymbol{s}^{\prime}=r(\boldsymbol{s})\), donde el operador de rotación\(r(s)\) está definido por\(r(s)=\left(m, z_{2}, \ldots, z_{m}, z_{1}+1\right)\). Si se produce una salida pero no llega, entonces el cliente al frente de la cola recibe su última unidad de servicio y sale. El nuevo estado es\(\boldsymbol{s}^{\prime}=\delta(\boldsymbol{s})\), donde el operador de salida\(\delta(\boldsymbol{s})\) está definido por\(\delta(s)=\left(m-1, z_{2}, \ldots, z_{m}\right)\).
Si se produce una llegada, el nuevo cliente recibe una unidad de servicio y va al fondo de la cola si se requiere más de una unidad de servicio. En este caso, el nuevo estado es\(\boldsymbol{s}^{\prime}=a(\boldsymbol{s})\) donde\(a(s)\) se define al operador de llegada\(a(\boldsymbol{s})=\left(m+1, z_{1}, z_{2}, \ldots, z_{m}, 1\right)\). Si solo se requiere una unidad de servicio por una nueva llegada, la llegada sale y\(\boldsymbol{s}^{\prime}=\boldsymbol{s}\). En el caso especial de una cola vacía,\(s=\phi\), el estado no cambia si o bien no se produce llegada o llega una llegada que requiera un incremento de servicio. De lo contrario, el nuevo estado es\(s=(1,1)\), es decir, que el único cliente en el sistema haya recibido un incremento de servicio.
A continuación encontramos la probabilidad de cada transición para\(s \neq \phi\). La probabilidad de no llegada es\(1-\lambda \delta\). Dado que no hay llegada, y dado un sistema no vacío\(s \neq \phi\),, la probabilidad de una salida es\(g\left(z_{1}\right)=f\left(z_{1}+1\right) / \overline{F}\left(z_{1}\right)\), es decir, la probabilidad de que un incremento más de servicio permita al cliente al frente de la cola salir. Así la probabilidad de una salida es\((1-\lambda \delta) g\left(z_{1}\right)\) y la probabilidad de una rotación es\((1-\lambda \delta)\left[1-g\left(z_{1}\right)\right]\). Finalmente, la probabilidad de una llegada es\(\lambda \delta\), y dada una llegada, la nueva llegada saldrá del sistema después de una unidad de servicio con probabilidad\(g(0)=f(1)\). Así es la probabilidad de una llegada y no salida\(\lambda \delta[1-f(1)]\) y la probabilidad de un sistema sin cambios es\(\lambda \delta f(1)\). Resumir, para\(s \neq \phi\),
\ [\ begin {array} {ll}
P_ {s, r (s)} =( 1-\ lambda\ delta)\ left [1-g\ left (z_ {1}\ right)\ right]; & r (s) =\ left (m, z_ {2},\ ldots, z_ {m}, z_ {1} +1\ right)\\
P_ {s, d (s)} =( 1-\ lambda\ delta) g\ izquierda (z_ {1}\ derecha); & d (s) =\ izquierda (m-1, z_ {2},\ ldots, z_ {m}\ derecha)\\
P_ {s, a (s)} =\ lambda\ delta [1-f (1)]; & a (s) =\ izquierda (m+1, z_ {1}, z_ {2},\ ldots, z_ {m}, 1\ derecha)\\
P_ {s, s} =\ lambda\ delta f (1). &
\ end {array}\ label {5.49}\]
Para el caso especial del estado inactivo,\(P_{\phi, \phi}=(1-\lambda \delta)+\lambda \delta f(1)\) y\(P_{\phi,(1,1)}=\lambda \delta(1-f(1))\).
Ahora encontramos la distribución en estado estacionario para esta cadena de Markov al observar la cadena atrasada de Markov. Haremos la hipótesis de probabilidades de transición hacia atrás, y luego usaremos el Teorema 5.3.3 para verificar que la hipótesis es correcta. Considere las transiciones hacia atrás correspondientes a cada una de las transiciones hacia adelante en (5.49). Una rotación en el tiempo de avance hace que los elementos\(z_{1}, \ldots, z_{m}\) en el estado giren\(\boldsymbol{s}=\left(m, z_{1}, \ldots, z_{m}\right)\) a la izquierda, y el elemento más a la izquierda (correspondiente al frente de la cola) se incrementa mientras gira hacia el extremo derecho. La transición hacia atrás de\(r(s)\) a\(s\) corresponde a los elementos que\(z_{2}, \ldots, z_{m}, z_{1}+1\) giran hacia la derecha, con el elemento más derecho decrementado mientras gira hacia el extremo izquierdo. Si vemos las transiciones en el tiempo hacia atrás como una especie de sistema round-robin, vemos que la rotación es en la dirección opuesta al sistema de tiempo hacia adelante.
En el sistema de tiempo atrás, vemos los números\(z_{1}, \ldots, z_{m}\) en el estado como el servicio restante requerido antes de que los clientes correspondientes puedan partir. De esta manera, estos números disminuyen en el sistema de movimiento hacia atrás. También, dado que la rotación del cliente en el sistema de movimiento hacia atrás es opuesta a la del sistema de avance,\(z_{m}\) es el servicio restante del cliente al frente de la cola, y\(z_{1}\) es el servicio restante del cliente al final de la cola. También vemos las salidas en tiempo de avance como llegadas en tiempo atrasado. Así, la transición hacia atrás de\(d(\boldsymbol{s})=\left(m-1, z_{2}, \ldots, z_{m}\right)\) a\(\boldsymbol{s}=\left(m, z_{1}, \ldots, z_{m}\right)\) corresponde a una llegada que requiere\(z_{1}+1\) unidades de servicio; la llegada va al frente de la cola, recibe un incremento de servicio, y luego va a la parte posterior de la cola con\(z_{1}\) incrementos de servicio restante.
Lo más bonito que podríamos esperar ahora es que las llegadas en tiempos atrasados son Bernoulli. Esta es una hipótesis razonable de hacer, en parte porque es plausible, y en parte porque es fácil de verificar a través del Teorema 5.3.3. Afortunadamente, encontraremos que es válido. Según esta hipótesis, la probabilidad\(P_{r(s), s}^{*}\) de transición hacia atrás viene dada por\(1-\lambda \delta\); es decir, dada r (s), s\(X_{n+1}\) es decir\(r(s)=\left(m, z_{2}, \ldots, z_{m}, z_{1}+1\right)\), y dado que no hay llegada al sistema hacia atrás en el momento\((n+1) \delta\), entonces el único estado posible en el momento\(n\) es\(\boldsymbol{s}=\left(m, z_{1}, \ldots, z_{n}\right)\). A continuación considere una transición hacia atrás de\(d(\boldsymbol{s})=\left(m-1, z_{2}, \ldots, z_{n}\right)\) a\(\boldsymbol{s}=\left(m, z_{1}, z_{2}, \ldots, z_{m}\right)\). Esto corresponde a una llegada al sistema de movimiento hacia atrás; la llegada requiere\(z_{1}+1\) incrementos de servicio, uno de los cuales se proporciona inmediatamente, dejando la llegada al fondo de la cola con los incrementos\(z_{1}\) requeridos de servicio restantes. La probabilidad de esta transición es\(P_{d(s), s}^{*}=\lambda \delta f\left(z_{1}+1\right)\). Calculando las otras transiciones hacia atrás de la misma manera, las probabilidades de transición hacia atrás hipotéticas vienen dadas por
\ [\ begin {array} {ll}
P_ {r (s), s} ^ {*} =1-\ lambda\ delta & P_ {d (s), s} ^ {*} =\ lambda\ delta f\ izquierda (z_ {1} +1\ derecha)\\
P_ {a (s), s} ^ {*} =\ lambda\ delta y P_ {s, s} {*} =\ lambda\ delta f (1)
\ end {array}\ label {5.50}\]
Uno debería ver\ ref {5.50} como una hipótesis para las probabilidades de transición hacia atrás. Los argumentos que conducen a\ ref {5.50} son simplemente motivación para esta hipótesis. Si la hipótesis es correcta, podemos combinar\ ref {5.49} y\ ref {5.50} para expresar las ecuaciones de estado estacionario del Teorema 5.3.3 (for\(s \neq f\)) como
\ (\ begin {alineado}
\ pi_ {s} P_ {s, r (s)} &=\ pi_ {r (s)} P_ {r (s), s} ^ {*}; & & (1-\ lambda\ delta)\ izquierda [1-g\ izquierda (z_ {1}\ derecha)\ derecha]\ pi_ {s} =( 1-\ lambda\ delta)\ pi_ {r (s)} &\ quad (5.51)\
\\ pi_ {s} P_ {s, d (s)} &=\ pi_ {d (s)} P_ {d (s), s} ^ {*}; & (1-\ lambda\ delta) g\ izquierda (z_ {1}\ derecha)\ pi_ {s} =\ lambda\ delta f\ izquierda (z_ {1} +1\ derecha)\ pi_ {d (s)} &\ quad (5.52)\
\ pi_ {s} P_ {s} P_ {s, a (s)} &=\ pi_ {a (s)} P_ {a (s), s} ^ {*}; & &\ lambda\ delta [1-f (1)]\ pi_ {s} =( 1-\ lambda\ delta)\ pi_ {a (s)} &\ quad (5.53)\
\\ pi_ {s} P_ {s, s} &=\ pi_ {s} P_ {s, s} ^ {*} ; & &\ lambda\ delta f (1)\ pi_ {s} =\ lambda\ delta f (1)\ pi_ {s}. &\ quad (5.54)
\ final {alineado}\)
A continuación mostramos que (5.52), aplicado repetidamente, nos permitirá resolver para\(\pi_{s}\) (si\(\lambda\) es lo suficientemente pequeño para que los estados sean positivos recurrentes). Verificar que la solución también satisface\ ref {5.51} y (5.53), luego verificará la hipótesis. \(f\left(z_{1}+1\right) / g\left(z_{1}\right) \text { is } \overline{F}\left(z_{1}\right)\)Desde (5.47), tenemos
\[\pi_{s}=\frac{\lambda \delta}{1-\lambda \delta} \bar{F}\left(z_{1}\right) \pi_{d(s)}\label{5.55} \]
Para\(m>1, d(\boldsymbol{s})=\left(m-1, z_{2}, \ldots, z_{m}\right)\), así podemos aplicar\ ref {5.55} a\(\pi_{d(s)}\), y sustituir el resultado de nuevo en (5.55), cediendo
\[\left.\pi_{s}=\frac{\lambda \delta}{1-\lambda \delta}\right)^{2} \overline{F}\left(z_{1}\right) \overline{F}\left(z_{2}\right) \pi_{d(d(s))}\label{5.56} \]
donde\(d(d(\boldsymbol{s}))=\left(m-2, z_{3}, \ldots, z_{m}\right)\). Aplicando\ ref {5.55} repetidamente a\(\pi_{d(d(s))}, \pi_{d(d(d(s)))}\), y así sucesivamente, finalmente obtenemos
\[\left.\pi_{s}=\frac{\lambda \delta}{1-\lambda \delta}\right)^{m}\left(\prod_{j=1}^{m} \overline{F}\left(z_{j}\right)\right) \pi_{\phi}\label{5.57} \]
Antes de que esto pueda ser aceptado como una distribución en estado estacionario, debemos verificar que satisface\ ref {5.51} y (5.53). El lado izquierdo de\ ref {5.51} es\((1-\lambda \delta)\left[1-g\left(z_{1}\right)\right] \pi_{s}\), y, de (5.47),\(1-g\left(z_{1}\right)=\left[\overline{F}\left(z_{1}\right)-f\left(z_{1}+1\right)\right] / \overline{F}\left(z_{1}\right)=\overline{F}\left(z_{1}+1\right) /\left(z_{1}\right)\). Por lo tanto, usando (5.57), el lado izquierdo de\ ref {5.51} es
\(\left.\left.\left.(1-\lambda \delta) \frac{\overline{F}\left(z_{1}+1\right)}{\overline{F}\left(z_{1}\right)} \quad \frac{\lambda \delta}{1-\lambda \delta}\right)^{m}\left(\prod_{j=1}^{m} \overline{F}\left(z_{j}\right)\right) \pi_{\phi}=(1-\lambda \delta) \quad \frac{\lambda \delta}{1-\lambda \delta}\right)^{m}\left(\prod_{j=2}^{m}\right\} \overline{F}\left(z_{j}\right)\right) \overline{F}\left(z_{1}+1\right) \pi_{\phi}\)
Esto es igual a\((1-\lambda \delta) \pi_{r(s)}\), verificando (5.51). La ecuación\ ref {5.53} se verifica de la misma manera. Ahora tenemos que encontrar si existe una solución para pf tal que estas probabilidades sumen a 1. Primero definir\(P_{m}=\sum z_{1}, \ldots, z_{m} \pi\left(m, z_{1}, \ldots, z_{m}\right)\). Esta es la probabilidad de m clientes en el sistema. Siempre que un nuevo cliente ingresa al sistema, recibe un incremento de servicio inmediatamente, así que cada uno\(z_{i} \geq 1\). Usando la solución hipotética en (5.57),
\[\left.P_{m}=\frac{\lambda \delta}{1-\lambda \delta}\right)^{m}\left(\prod_{j=1}^{m} \sum_{i=1}^{\infty} \overline{F}(i)\right) \pi_{\phi}\label{5.58} \]
Dado que\(\overline{F}(i)=\operatorname{Pr}\{W>i \delta\}\), dado que W es aritmética con span\(\delta\), y dado que la media de una variable aleatoria no negativa es la integral de su función de distribución complementaria, tenemos
\[\left.\delta \sum_{i=1}^{\infty}\right\} \overline{F}(i)=\mathrm{E}[W]-\delta\label{5.59} \]
\[\left.P_{m}=\frac{\lambda}{1-\lambda \delta}\right)^{m}(\mathrm{E}[W]-\delta)^{m} \pi_{\phi}\label{5.60} \]
Definir\(\rho=[\lambda /(1-\lambda \delta)]\{\mathrm{E}[W]-\delta\}\), vemos\(P_{m}=\rho^{m} \pi_{\phi}\). Si\(\rho<1\), entonces\(\pi_{\phi}=1-\rho\), y
\[P_{m}=(1-\rho) \rho^{m} ; \quad m \geq 0\label{5.61} \]
El padecimiento\(r<1\) se requiere para que los estados sean positivo-recurrentes. El número esperado de clientes en el sistema para una cola round-robin es\(\sum_{m} m P_{m}=\rho /(1-\rho)\), y usando el teorema de Little, Teorema 4.5.3, el retraso esperado es\(\rho /[\lambda(1-\rho)]\). Al usar aquí el teorema de Little, sin embargo, estamos viendo el tiempo que un cliente pasa en el sistema como comenzando cuando aumenta el número m en el estado; es decir, si un cliente llega a tiempo\(n \delta\), va al frente de la cola y recibe un incremento de servicio, y luego, asumiendo que necesita más de un incremento, el número m en el estado aumenta a la vez\((n+1) \delta\). Por lo tanto, el retraso real esperado, incluyendo el d original cuando el cliente está siendo atendido pero no contado en el estado, es\(\delta+\rho /[\lambda(1-\rho)]\).
La relación entre\(\rho\) y\(\lambda \mathrm{E}[W]\) se muestra en la Figura 5.8, y se ve que\(\rho<1\) para\(\lambda E[W]<1\). El caso extremo donde\(\lambda \delta=\lambda \mathrm{E}[W]\) es el caso para el cual cada cliente requiere exactamente una unidad de servicio. Dado que a lo sumo un cliente puede llegar por incremento de tiempo, el estado siempre permanece en\(s=\phi\), y el retraso es\(\delta\), es decir, el incremento original del servicio recibido cuando llega un cliente.
Tenga en cuenta que\ ref {5.61} es lo mismo que la distribución de clientes en el sistema para la cadena M/M/1 Markov en (5.40), a excepción de la anomalía en la definición de\(\rho\) aquí. Entonces tenemos el resultado sorprendente de que si se usa la cola de round-robin en lugar de FCFS, entonces la distribución del número de clientes en el sistema es aproximadamente la misma que para una cola M/M/1. Es decir, se ha eliminado el efecto de camión lento asociado a la cola M/G/1.
Otra característica notable de los sistemas round-robin es que también se puede calcular el retraso esperado para un cliente en función del servicio requerido de ese cliente. Esto se hace en el Ejercicio 5.16, y se encuentra que el retraso esperado es lineal en el servicio requerido.
A continuación nos fijamos en el uso compartido de procesadores yendo al límite como\(\delta \rightarrow 0\). Primero eliminamos la suposición de que la distribución de requisitos de servicio es aritmética con span\(\delta\). Supongamos que el servidor siempre pasa un incremento de tiempo en el cliente al frente de la cola, y si el servicio finaliza antes de que termine el intervalo de duración, el servidor estará inactivo hasta el siguiente tiempo de muestra. El análisis de la distribución en estado estacionario anterior sigue siendo válido si definimos\(\overline{F}(j)=\operatorname{Pr}\{W>j \delta\}\), y\(f(j)=\overline{F}(j)-\overline{F}(j+1)\). En este caso\(\delta \sum_{i=1}^{\infty} \overline{F}(i)\) se encuentra entre\(\mathrm{E}[W]-\delta\). As\(\delta \rightarrow 0\),\(\rho=\lambda \mathrm{E}[W]\), y la distribución del tiempo en el sistema se vuelve idéntica a la del sistema M/M/1.