Derivaremos la fórmula discreta para el algoritmo de priorización

Question

Para la planificación prioritaria de trabajos impulsados por eventos en un sistema de software, se me ocurrió el siguiente algoritmo:

Sean $k$ clases de prioridad, representadas por los primeros $k$ números naturales, un conjunto finito de clases de trabajos $J$ y para cada $j \in J$ existe un conjunto infinito de posibles instancias de trabajo $I(j)=\{j_1,j_2,\dots\}$.

Definir la función $prio$, que mapea las clases de trabajo a las clases de prioridad y las instancias de trabajo a los valores de prioridad:

• $prio: J\to \{1,\dots ,k\}$
• $prio: I(j)\to \mathbb{N}$

Para cada clase de prioridad $p$, sea $c_p$ el contador de prioridad asociado con esa clase. Estos contadores se inicializan con $c_p:=0$

Cuando la instancia de trabajo $j_i$ entra en el sistema, establecer:

• $c_{prio(j)}:=c_{prio(j)}+prio\left(j\right)$
• $prio(j_i) := c_{prio(j)}$

Las instancias de trabajo se programan en el orden relativo de sus respectivos valores de prioridad. Si los valores de prioridad de dos trabajos de diferentes clases son iguales, el trabajo con la clase de prioridad más baja se programa primero.

En mi intuición, esto debería producir un algoritmo en el que, bajo carga de trabajo constante en todas las clases de prioridad, los trabajos de la clase 1 se ejecuten aproximadamente el doble de veces que los trabajos de la clase 2 y tres veces más que los trabajos de la clase 3, etc.

Intenté con un ejemplo breve de 3 clases de prioridad y 3 inserciones de instancias para cada clase.

_____|_____ejecuciones por clase_____
tiempo | clase 1 | clase 2 | clase 3 |
-----|------------------------------
  0  |  0      |  0      |  0      |
-----|------------------------------
  1  |  1      |  0      |  0      |
-----|------------------------------
  2  |  2      |  0      |  0      |
-----|------------------------------
  3  |  2      |  1      |  0      |
-----|------------------------------
  4  |  3      |  1      |  0      |
-----|------------------------------
  5  |  3      |  1      |  1      |
-----|------------------------------
  6  |  3      |  2      |  1      |

Quería derivar una fórmula discreta para esto, para poder generar programáticamente una tabla como la anterior sin simulación. Esto sería una función de los 3 parámetros $k$ (número de clases de prioridad), $i$ (clase de prioridad que estamos analizando) y $n$ (número de pasos temporales).

Intenté por un tiempo y jugué con esos parámetros pero no pude llegar a un resultado. También descubrí que me falta metodología para buscar la solución correcta, por lo que decidí finalmente registrarme en stackoverflow después de haber vivido de las preguntas y respuestas de otros durante bastante tiempo.

No necesariamente estoy buscando respuestas con la fórmula correcta, me encantaría si alguien pudiera dar una pista o dos sobre cómo los verdaderos matemáticos abordarían este problema, tal vez alguna literatura para principiantes. Sinceramente, ni siquiera sé a qué campo de las matemáticas recurriría este procedimiento (encontrar fórmulas para algoritmos), o por dónde empezar a buscar. Cada esfuerzo es muy apreciado.

Answer 1

Usted parece estar describiendo un programador por lotes: recibe el (posiblemente infinito) lista de instancias de trabajo en el tiempo cero y, a continuación, de forma instantánea asigna el horario de las instancias. Pero la tabla no está de acuerdo. Parece que el trabajo de las instancias de llegar a indefinido de veces en indefinidos de los números y de que el programador puede programar una instancia hasta que llega. Tampoco hay información acerca de un descheduler (un objeto que se borra una instancia de una prioridad (cola) para que el siguiente en la cola de espera ejemplo de la prioridad que se pueda realizar). Con estas carencias, he procedido con el sistema como se describe (secuencia infinita de casos instantánea y simultánea programación en el tiempo cero).

Hay $k$ clases de prioridad y el número de instancias de trabajo de cada clase de prioridad que entra en el sistema es inicialmente cero y, a continuación, en cada paso aumenta por $0$ o $1$. Podemos, por tanto, el modelo de los números de cada clase de prioridad que han entrado en el sistema como un punto en $\mathbb{N}^k$, $x = (x_1, \dots, x_k)$. El sistema es impulsado por una especie de paseo aleatorio en este espacio.

Una vez que el $s^\text{th}$ instancia de trabajo entra en el sistema, tenemos la relación $\sum_{n=1}^k x_n = s$, por lo que en el $s^\text{th}$ "paso", el punto de $x$ se encuentra en el hyperplane la satisfacción de esta relación. Este hyperplane avanza por la misma cantidad en cada paso, por lo que podemos eliminar esta "deriva", y descubrir que el sistema es realmente sólo participa en dos dimensiones de paseo aleatorio con una constante deriva.

El $k$ da prioridad a los contadores son independientes, en el sentido de que el $c_k$ sólo se incrementa cuando un trabajo de clase de prioridad $k$ entra en el sistema y la entrada de un trabajo de otra clase de prioridad no tiene ningún efecto sobre el contador. Esto significa que los valores de la clase de prioridad de los contadores son independientes de la ruta tomada a través de $\mathbb{N}^k$ -- una vez que el pie llega a $x$, los valores de la clase de prioridad de los mostradores de $c_i = i x_i$.

(Se preguntó cómo un "matemático real" abordar este problema. Yo no soy técnicamente un matemático real todavía (para algunas definiciones, pero la básica es el método de inducción. Observar que antes de que las instancias de trabajo de entrar, los contadores están en $(0,0,\dots,0)$, por lo que la fórmula es un principio verdadero. Desde cualquier punto de $(x_1, x_2, \dots, x_j)$, la entrada de una instancia de trabajo aumenta una coordenada por exactamente la cantidad de la fórmula dice que lo hará. Así que por la inducción, la fórmula sostiene. Este es el tipo de argumento general que uno usa para este tipo de situación. Somos capaces de hacer el más simple, más global, el argumento que he escrito anteriormente, ya que el sistema se separa en pequeños sistemas que no interactúan.

Este es también el lugar donde la diferencia entre la línea de programador y el pre-programador de diferentes -- una línea de programador puede causar una entrada instancia de trabajo para viajar en el tiempo y ser programadas antes de "ahora". I. e., la cola de espera de puestos de trabajo en cada clase de prioridad no puede contener números negativos de puestos de trabajo. En consecuencia, también tenemos el modelo de la profundidad de estas colas, así como el número de puestos de trabajo de cada uno de los tipos que se encuentran tan lejos. También, la profundidad de una cola es superior limitada por el número de casos de este tipo que han llegado tan lejos. En consecuencia, no todos los de la $2k$-dimensiones del espacio de la cuenta y la profundidad es accesible, y esta falta de accesibilidad es donde la inducción se hace duro. Si desea acercarse a esta versión del problema, necesitamos saber un poco más que la que se suministra en la pregunta original.

También, si no había preguntado sobre la manera en que los matemáticos enfoque de este, le habría recomendado de enrutamiento de esta pregunta cs.stackexchange.com)

En consecuencia, suponiendo una fuente infinita de trabajo de las instancias de cada clase de prioridad de entrar en el sistema, los de prioridad clase $1$ será asignado a los sucesivos números enteros, los de prioridad clase $2$ será asignado a los números enteros, ... las de la clase de prioridad $i$ será asignado a múltiplos de $i$. Esto significa que su intuición de que la $1$ trabajos están programados dos veces tan a menudo como $2$ puestos de trabajo y tres veces más con frecuencia como $3$ puestos de trabajo es la correcta.

Respondiendo a la pregunta de manera más genérica requiere más información que la proporcionada en el problema: Supongamos que el $1$ trabajos de entrar en el sistema de un tercio tan a menudo como $2$ empleos, es decir, $x_1 = (1/3) x_2$. Luego hay $x_2$ $2$ puestos de trabajo programada de forma homogénea hasta la ranura $2 x_2$ y $x_2/3$ $1$ trabajos programados hasta el $(1/3) x_2$. Es decir, la cola de $1$ puestos de trabajo ha sido severamente muerto de hambre. A continuación, su intuición (temporalmente) incorrecta, pero sólo porque todo el proceso aleatorio causas puestos de trabajo para entrar en el sistema ha tenido una persistente fluctuación que conduce a la entrada de $1$ puestos de trabajo. Si la Ley de los Grandes Números sostiene y la entrada de trabajo de las instancias de cada clase de prioridad es equiprobables, entonces esta fluctuación va a pasar y, finalmente, la cola de $1$ puestos de trabajo "ponerse al día"...

Pero no puede alcanzar. Supongamos equi-probabilidad contiene de hecho en algún momento para que $x_1 = x_2 = \cdots = x_k$, entonces no se $x_1$ prioridad $1$ trabajos programados a la ranura $x_1$, $x_1$ prioridad $2$ trabajos programados a la ranura $2 x_1$, $x_1$ prioridad $3$ trabajos programados a la ranura $3 x_1$, ... $x_k$ prioridad $k$ trabajos programados a tiempo $k x_1$. En otras palabras, la prioridad de la última $1$ trabajo será programada para que comience cuando sólo la mitad de la $2$ puestos de trabajo, un tercio de la $3$ puestos de trabajo, et c. se han iniciado. Después de este tiempo, la prioridad $2$ y posterior colas lentamente vacío, llevando la relación de puestos de trabajo programado (de nuevo) a $1$ para cualquier par de prioridades.

Sin embargo, volviendo a tu pregunta acerca de las fórmulas... Asumiendo que la probabilidad de entrada de un puesto de trabajo de cada clase de prioridad es el mismo, $p_1 = p_2 = \cdots = p_k$, entonces la expectativa de coordenadas son todos de la misma y el escenario donde la prioridad $1$s están previstas en la mitad del tiempo de la prioridad $2$s y así se mantiene. La distribución de las ubicaciones se espera que sea aproximadamente una distribución normal con desviación estándar de la raíz cuadrada del número de puestos de trabajo introducidos hasta el momento de veces el tamaño del paso. El tamaño de paso es $\sqrt{1^2 - (\sqrt{3}/3)^2} = \sqrt{2/3}$ (Tenemos un triángulo rectángulo con hipotenusa que es uno de los lados de un cubo unitario y con una pierna y un tercio de la longitud de la diagonal larga.) Con 90% de probabilidad, esperamos que el punto en el espacio dentro de $1.644...$ desviaciones estándar de la expectativa de valor. Supongamos entonces hemos suministrado $kN$ instancias de trabajo; somos un 90% de probabilidades de encontrar que el punto está dentro de $\sqrt{2kN/3}$ de el punto de $(N,N,\dots, N)$. Supongamos para mayor claridad, la discrepancia está enteramente en la clase de prioridad $1$, de modo que las coordenadas del punto a son (en el 90% de los posibles simulaciones) entre $(N - (k-1)/k \sqrt{2kN/3}, N + (1/k)\sqrt{2kN/3}, N + (1/k) \sqrt{2kN/3}, \dots , N + (1/k) \sqrt{2kN/3})$$(N + (k-1)/k \sqrt{2kN/3}, N - (1/k)\sqrt{2kN/3}, N - (1/k) \sqrt{2kN/3}, \dots , N - (1/k) \sqrt{2kN/3})$. Para la gran $N$, el principal término domina y el resultado está muy cerca (en un radiométrica sentido) a la equiprobables caso. Para las pequeñas $N$, $\sqrt{N}$- tamaño plazo puede ser muy notable. Tenga en cuenta también que el aumento de $k$ disminuye la discrepancia en el segundo y siguientes coordenadas. Pero esto es sólo una única estimación para tener una idea de lo mal que una simulación puede desviarse de la conducta esperada. Para obtener la fórmula que estás pensando, nos acercamos a ella en dos pasos...

En primer lugar, hemos de reconocer que las distribuciones marginales multivariante de las distribuciones normales son distribuidos normalmente (con el "obvio" que la media y desviación estándar), por lo que en virtud de la aproximación normal, con $k$ el número de clases de prioridad, $i$ una particular clase de prioridad, y $N$ el número de timesteps, el valor en la tabla es una variable aleatoria $$ T(k,i,N) = NormalDistribution(N/k, \sqrt{2N/3})/i $$ where the $N/k$ represents equidistribution and each variable contributes $\sqrt{2N/3}$ standard devation, the rms of which is $\sqrt{2kN/3}$. Finally the "$/i$" reminds us that the entries in column $i$ only increment on rows divisible by $i$.

Pero entonces volvemos a lo que conocíamos anteriormente. Suponiendo instantánea programación por lotes en el tiempo cero y una promesa de que cada clase de trabajo parece infinitamente a menudo en la secuencia de entrar en instancias de trabajo, a continuación, cada entrada de la tabla es de sólo us $$ T(k,i,N) = \left\lfloor \frac{N}{ik} \right\rfloor $$ where $\lfloor \cdot \rfloor$ is the "floor function" or "the greatest integer not greater than" function. For instance, $\lfloor 0 \rfloor = \lfloor 1/k \rfloor = \cdots \lfloor (k-1)/k \rfloor$ and $\lfloor 1 \rfloor = 1$.