Grupo de subprocesos para ejecutar tareas arbitrarias con diferentes prioridades

Question

Estoy intentando idear un diseño para un grupo de subprocesos con muchos requisitos de diseño para mi trabajo.Este es un problema real para el software en funcionamiento y es una tarea difícil.Tengo una implementación funcional, pero me gustaría enviarla a SO y ver qué ideas interesantes se le ocurren a la gente, para poder compararla con mi implementación y ver cómo se compara.He tratado de ser lo más específico posible con los requisitos.

El grupo de subprocesos necesita ejecutar una serie de tareas.Las tareas pueden ser de corta duración (<1 segundo) o de larga duración (horas o días).Cada tarea tiene una prioridad asociada (desde 1 = muy baja hasta 5 = muy alta).Las tareas pueden llegar en cualquier momento mientras las otras tareas se están ejecutando, por lo que cuando llegan, el grupo de subprocesos debe seleccionarlas y programarlas a medida que los subprocesos estén disponibles.

La prioridad de la tarea es completamente independiente de la duración de la tarea.De hecho, es imposible saber cuánto tiempo podría tardar en ejecutarse una tarea sin simplemente ejecutarla.

Algunas tareas están vinculadas a la CPU, mientras que otras están vinculadas en gran medida a IO.Es imposible saber de antemano cuál sería una tarea determinada (aunque supongo que podría ser posible detectarla mientras se ejecutan las tareas).

El objetivo principal del grupo de subprocesos es maximizar el rendimiento.El grupo de subprocesos debería utilizar eficazmente los recursos de la computadora.Idealmente, para tareas vinculadas a la CPU, la cantidad de subprocesos activos sería igual a la cantidad de CPU.Para las tareas vinculadas a IO, se deben asignar más subprocesos que CPU para que el bloqueo no afecte demasiado el rendimiento.Es importante minimizar el uso de cerraduras y utilizar contenedores rápidos y seguros para subprocesos.

En general, debes ejecutar tareas de mayor prioridad con una mayor prioridad de CPU (ref:Establecer prioridad de hilo).Las tareas de menor prioridad no deben "bloquear" la ejecución de las tareas de mayor prioridad, por lo que si aparece una tarea de mayor prioridad mientras se ejecutan todas las tareas de baja prioridad, la tarea de mayor prioridad se ejecutará.

Las tareas tienen asociado un parámetro de "tareas en ejecución máxima".Cada tipo de tarea solo puede ejecutar como máximo esta cantidad de instancias simultáneas de la tarea a la vez.Por ejemplo, podríamos tener las siguientes tareas en la cola:

• A - 1000 instancias - prioridad baja - tareas máximas 1
• B - 1000 instancias - prioridad baja - tareas máximas 1
• C - 1000 instancias - prioridad baja - tareas máximas 1

Una implementación funcional solo podría ejecutar (como máximo) 1 A, 1 B y 1 C al mismo tiempo.

Debe ejecutarse en Windows XP, Server 2003, Vista y Server 2008 (los últimos service packs).

---

Como referencia, podríamos usar la siguiente interfaz:

namespace ThreadPool
{
    class Task
    {
    public:
        Task();     
        void run();
    };

    class ThreadPool
    {    
    public:
        ThreadPool();
        ~ThreadPool();

        void run(Task *inst);
        void stop();
    };
}

Answer 1

Entonces, ¿qué vamos a elegir como elemento básico para esto?Windows tiene dos bloques de construcción que parecen prometedores: puertos de finalización de E/S (IOCP) y llamadas a procedimientos asíncronos (APC).Ambos nos brindan colas FIFO sin tener que realizar un bloqueo explícito y con una cierta cantidad de soporte integrado del sistema operativo en lugares como el programador (por ejemplo, los IOCP pueden evitar algunos cambios de contexto).

Los APC quizás encajen un poco mejor, pero tendremos que tener un poco de cuidado con ellos, porque no son del todo "transparentes".Si el elemento de trabajo realiza una espera que genera alertas (::SleepEx, ::WaitForXxxObjectEx, etc.) y accidentalmente enviamos un APC al subproceso, entonces el APC recién enviado se hará cargo del subproceso, suspendiendo el APC que se estaba ejecutando previamente hasta que se ejecute el nuevo APC. finalizado.Esto es malo para nuestros requisitos de concurrencia y puede aumentar la probabilidad de que se produzcan desbordamientos de pila.

Answer 2

Debe ejecutarse en Windows XP, Server 2003, Vista y Server 2008 (los últimos service packs).

¿Qué característica de los grupos de subprocesos integrados del sistema los hace inadecuados para su tarea?Si desea apuntar a XP y 2003, no puede usar los nuevos y brillantes grupos de Vista/2008, pero aún puede usar QueueUserWorkItem y amigos.

Answer 3

@DrPizza: esta es una muy buena pregunta y va directo al meollo del problema.Hay algunas razones por las que se descartaron QueueUserWorkItem y el grupo de subprocesos de Windows NT (aunque el de Vista parece interesante, tal vez dentro de unos años).

En primer lugar, queríamos tener un mayor control sobre cuándo inicia y detiene los subprocesos.Hemos oído que el grupo de subprocesos de NT se muestra reacio a iniciar un nuevo subproceso si cree que las tareas se están ejecutando poco tiempo.Podríamos usar WT_EXECUTELONGFUNCTION, pero realmente no tenemos idea si la tarea es larga o corta.

En segundo lugar, si el grupo de subprocesos ya estuviera lleno de tareas de baja prioridad y de larga duración, no habría posibilidad de que una tarea de alta prioridad se ejecutara de manera oportuna.El grupo de subprocesos de NT no tiene un concepto real de prioridades de tareas, por lo que no podemos hacer un QueueUserWorkItem y decir "por cierto, ejecuta este ahora mismo".

En tercer lugar, (según MSDN) el grupo de subprocesos NT no es compatible con el modelo de apartamento STA.No estoy seguro de qué significaría esto, pero todos nuestros subprocesos de trabajo se ejecutan en STA.

Answer 4

@DrPizza: esta es una muy buena pregunta y va directo al meollo del problema.Hay algunas razones por las que se descartaron QueueUserWorkItem y el grupo de subprocesos de Windows NT (aunque el de Vista parece interesante, tal vez dentro de unos años).

Sí, parece que se reforzó bastante en Vista, ahora es bastante versátil.

Bien, todavía no tengo claro cómo desea que funcionen las prioridades.Si el grupo está ejecutando actualmente una tarea de tipo A con concurrencia máxima de 1 y baja prioridad, y se le asigna una nueva tarea también de tipo A (y concurrencia máxima de 1), pero esta vez con una prioridad alta, ¿qué debería hacer? ?

Suspender el A que se está ejecutando actualmente es complicado (podría mantener un bloqueo que la nueva tarea debe tomar, bloqueando el sistema).No puede generar un segundo hilo y simplemente dejar que se ejecute al mismo tiempo (la simultaneidad permitida es solo 1).Pero no puede esperar hasta que se complete la tarea de baja prioridad, porque el tiempo de ejecución no tiene límites y hacerlo permitiría que una tarea de baja prioridad bloquee una tarea de alta prioridad.

Mi presunción es que lo que busca es este último comportamiento.

Answer 5

@DrPizza:

Ok, todavía no estoy claro sobre cómo desea que funcionen las prioridades.Si el grupo actualmente ejecuta una tarea de tipo A con una concurrencia máxima de 1 y baja prioridad, y se le da una nueva tarea también de Tipo A (y la concurrencia máxima 1), pero esta vez con una alta prioridad, ¿qué debe hacer? ?

Esta es un poco complicada, aunque en este caso creo que estaría contento con simplemente permitir que la tarea de baja prioridad se ejecute hasta su finalización.Por lo general, no veríamos muchos tipos de tareas iguales con diferentes prioridades de subprocesos.En nuestro modelo, en realidad es posible detener y luego reiniciar tareas de manera segura en ciertos puntos bien definidos (por razones diferentes a ésta), aunque las complicaciones que esto introduciría probablemente no valga la pena correr el riesgo.

Normalmente, sólo diferentes tipos de tareas tendrían diferentes prioridades.Por ejemplo:

• Una tarea - 1000 instancias - prioridad baja
• Tarea B - 1000 instancias - alta prioridad

Suponiendo que las tareas A llegaron y se estaban ejecutando, luego llegaron las tareas B, quisiéramos que las tareas B pudieran ejecutarse más o menos de inmediato.