Algoritmo de distribución de tareas / equilibrio de carga de trabajo

7

Estoy buscando un algoritmo para usar o como un punto de salto para el equilibrio de carga.

Ambiente: Tenemos ~ 7 tipos de trabajos que nuestros usuarios pueden programar en cualquier momento. Algunos trabajos son rápidos, otros son lentos (gran cantidad de procesamiento de datos). Tenemos una instancia única de un "procesador de trabajos" que descubrirá los trabajos que se han programado y luego los ejecutará. El "procesador de trabajos" ejecutará hasta 5 trabajos a la vez, "hilos".

El problema es que un trabajo puede consumir tantos recursos que los otros 4 trabajos no se procesan y, lo que es peor, los otros trabajos programados se retrasan durante largos períodos de tiempo.

Algunos trabajos pueden programarse como "ejecutarse inmediatamente", lo que los convierte en los siguientes en la línea.

Solución: Agregue más instancias del "procesador de trabajo". Tenemos un gran servidor de máquinas virtuales que está implementando 3 máquinas virtuales para cada una de las instancias de este "procesador de trabajos".

De forma predeterminada, va a ayudar, pero creo que debería haber más reflexión detrás.

Mi solución: Además de hacer que los "procesadores de trabajo" se amplíen horizontalmente, creo que debe haber una manera de determinar qué trabajos tomará una instancia en función de la carga actual de la instancia y también permitirá un sesgo.

Sugiero que determinemos las estadísticas para cada tipo de trabajo (promedio de tiempo de ejecución, etc.) y le asignemos una puntuación de 1 a 5 (5 son de larga duración). Cada instancia determinará cuál es su carga actual en función de la puntuación total de los trabajos que se están ejecutando actualmente y luego se toma en cuenta su sesgo. Por ejemplo, creo que deberíamos poder establecer una instancia para que esté orientada hacia trabajos pequeños, de modo que evite trabajos más grandes, mientras que otra instancia esté orientada hacia trabajos medianos, etc.

Estoy buscando consejos sobre cómo hacer esto. Los trabajos pueden consumir grandes cantidades de tiempo, CPU y / o memoria. Mi objetivo es asegurarme de que cada instancia solo esté reduciendo el trabajo que es capaz de hacer mientras mantiene la cola de trabajos programados avanzando lo más rápido posible.

Uno de los otros desarrolladores sugirió que dejemos a los "procesadores de trabajo" solos para simplemente jalar lo que está en la cola siguiente o "round robin". Yo digo que esto podría llevar a un problema potencial en el que una sola instancia ha derribado demasiados trabajos grandes y está luchando por terminarlos mientras que las otras instancias están inactivas.

    
pregunta DustinDavis 27.12.2011 - 17:51

3 respuestas

2

Parte de lo que está buscando es una " cola de prioridad ". En empleadores anteriores, hicimos una versión muy primitiva de esto, pero mi heurística fue permitir que solo algunos procesadores manejaran trabajos de corta duración (los trabajos cortos podían tomar minutos), mientras que otros manejaban trabajos de mayor duración (el informe trimestral podría tomar casi 2 días a procesar). Esto garantizaba que los trabajos cortos siempre tuvieran tiempo de procesamiento disponible. También utilicé un cuadro de indicadores que enumeraba los trabajos listos para ejecutarse, y el primer procesador capaz de manejar la tarea lo tomaría y ejecutaría con una sola hebra (eran computadoras baratas que no se habían depreciado y, por lo tanto, no se podían descartar). Muchas personas usan lo contrario: un programador que le dice a los procesadores qué unidad de trabajo deben hacer a continuación. Mi consejo sería que cada instancia ejecute una sola tarea, esto simplifica drásticamente la programación.

La programación de trabajos arbitrarios de longitudes arbitrarias es un problema difícil en el procesamiento distribuido. Casi todas las decisiones implicarán simular muchas carreras. Cuál es una de las peculiaridades de la teoría de la cola, en la que se basará este material.

  

Uno de los otros desarrolladores sugirió que dejemos a los "procesadores de trabajo" solos para simplemente jalar lo que haya en la cola siguiente o "round robin". Yo digo que esto podría llevar a un problema potencial en el que una sola instancia ha derribado demasiados trabajos grandes y está luchando por terminarlos mientras que las otras instancias están inactivas.

Esto necesita simulación para responder. Mi esquema anterior usaba algo muy similar. Si tiene estadísticas sobre ejecuciones de trabajos anteriores, puede modelarlas en Excel. He recogido este libro de otra publicación que lo recomiendo y busco aprender algunas técnicas para poder responde problemas como lo que estas describiendo Los números reales superan todo, así que reúna datos y haga simulaciones basadas en ellos.

    
respondido por el Tangurena 27.12.2011 - 21:00
2

Creo que tu razonamiento es sólido y que tu idea es buena y la idea de un amigo es lo suficientemente buena.

¿Quizás también debería considerar un proceso de "Pre-Proceso"?

Si sus trabajos están demorando tanto tiempo que está causando un tiempo de espera innecesario en la cola, puede ser posible dividir un solo trabajo grande en una serie de trabajos más pequeños que están procesando previamente los datos en tablas de preparación para el proceso principal.

Reducir el costo de un trabajo individual para que la disparidad en el tiempo de procesamiento promedio sea mucho menor sería una alternativa considerable a un sistema de clasificación.

EDITAR: También me gustaría señalar que un sistema de clasificación derivado del Tiempo por Trabajo puede estar muy influenciado por variables específicas del entorno (por ejemplo, un trabajo clasificado bajo debido al acceso de E / S en un servidor con configuración RAID puede no tener un rango que tenga sentido en un servidor con un HDD de estado sólido.)

Esto puede ser un escollo en la degradación de rango en función del rendimiento de un solo entorno.

    
respondido por el maple_shaft 27.12.2011 - 18:05
2
  

Agregue más instancias del "procesador de trabajo". Tenemos un gran servidor de máquinas virtuales que TI está implementando 3 máquinas virtuales para cada una de las instancias de este "procesador de trabajo".

Correcto.

  

De forma predeterminada, va a ayudar, pero creo que debería haber más reflexión detrás.

Incorrecto.

Cualquier ingeniería adicional es una pérdida absoluta de tiempo.

Considere los casos de uso en detalle.

En una cola de un solo procesador, el trabajo de larga duración se coloca primero en el procesador de una sola vez. Otros trabajos esperan. No te gusta esto.

En las colas de varios procesadores, el trabajo de larga duración entra en uno de los procesadores, dejando los otros libres. Problema resuelto.

Digamos que tiene tres trabajos de larga duración que podrían iniciarse simultáneamente. Entonces, simplemente necesita 4 procesadores para manejar la carga de trabajo. Tres obtendrán trabajos de larga duración, el cuarto manejará los trabajos "instantáneos".

Múltiples procesadores que trabajan desde una única cola de solicitudes es la solución estándar, ampliamente adoptada, casi universal. No se necesita nada más.

Si realmente cree que las prioridades son importantes, use una cola de prioridad en lugar de una cola FIFO y asigne manualmente prioridades simples. No lo pienses demasiado. Pensar más será simplemente una pérdida de tiempo.

    
respondido por el S.Lott 27.12.2011 - 19:04

Lea otras preguntas en las etiquetas