Manejo de tareas con diferentes prioridades en un grupo de subprocesos

Question

Tengo muchas tareas entrantes de prioridad A, B y C y quiero manejar las tareas con un grupo de subprocesos en una CPU multinúcleo. El 70% de la CPU se debe usar para procesar tareas de 'tipo A', el 20% de la CPU para tareas 'tipo B' y el 10% de la CPU para tareas 'tipo C'.

Si, sin embargo, solo llegan las tareas de 'tipo C', entonces debe dedicarse el 100% de la CPU a ellas. Si única tarea B y C arirve luego 66% se Proccess tarea B y el 33% C tarea, etc ...

¿Cómo le implementar esto en Java?

p.s: Una cola de prioridad no funcionará porque solo se escribirá una tarea. Además, la asignación de prioridades a los hilos no funcionará porque no es precisa.

Answer 1

Quizás debería usar 3 grupos de subprocesos a continuación. 1 grupo de 7 subprocesos para tareas A, 1 grupo de 2 subprocesos para tareas B y 1 grupo de 1 subproceso para tareas C.

EDITAR: para tener un paralelismo incluso si solo hay tareas C (o, si tiene muchos procesadores, si solo tiene tareas B y C), multiplique el número de subprocesos en cada grupo por el número de procesadores, o la cantidad de procesadores + 1, o cualquier otro factor más grande que desee.

Answer 2

Suponiendo que no se estén ejecutando otros procesos en la CPU, cree 3 grupos de subprocesos, uno para cada tipo de tarea, cada grupo con tantos subprocesos como núcleos en la CPU (para que la CPU pueda ser consumida por tareas de cualquier tipo si solo se están ejecutando tareas de ese tipo). Cada tarea nueva debe pasar por una sección de código que registra cuántos de cada tipo de tareas se están ejecutando. Si hay un núcleo libre en la CPU, inicie de inmediato la nueva tarea. Si no hay un espacio libre, comience con el grupo de prioridad más baja que tenga una prioridad menor que la nueva tarea, y pase al siguiente grupo de prioridad más alta si es necesario con este escaneo: interrumpa/pause un hilo en ejecución (esto supone que las tareas están diseñadas para ser interrumpible/en pausa) si el grupo actual está excediendo su límite de uso de núcleo proporcional, espere a que termine esa tarea (otra tarea puede terminar primero, lo cual es igual de bueno). Lanzar una nueva tarea en el grupo adecuado. Si la nueva tarea no se puede iniciar, espera en cola para que se complete otro, liberando un nuevo espacio. Cuando se libera una nueva ranura, una tarea del tipo que acaba de completarse obtiene la primera prioridad para la ranura liberada, si ninguna tarea está esperando, se inicia la tarea en espera con la prioridad más alta.

Answer 3

esto es en realidad un problema bastante difícil. Básicamente, necesitaría implementar una cola de bloqueo personalizada que rastrea no solo los trabajos pendientes, sino también los trabajos pendientes actualmente, . para los trabajos pendientes, mantendría listas separadas para los distintos niveles de prioridad. Además, debe realizar un seguimiento de los recuentos de ejecución para cada nivel de prioridad. cuando se solicita un nuevo trabajo de la cola, debe verificar la proporción de trabajos actualmente en ejecución y elegir el próximo trabajo disponible de la prioridad más alta aplicable (difiriendo a otras prioridades si no hay ninguna disponible con la prioridad deseada). Obviamente, necesitará retroalimentación en esta cola para sus trabajos en ejecución, por lo que probablemente desee ajustar los trabajos reales con un contenedor Runnable que ejecute el trabajo real y luego actualice su cola cuando se termine ese trabajo.

Answer 4

Escriba un motor de predicción que determine estadísticamente la probabilidad de que una determinada tarea se complete antes de que llegue una tarea de mayor prioridad. Parametrizar por umbral de valor de confianza que sea aceptable. Cuanto mayor sea la confianza requerida, más probabilidades hay de utilizar menos CPU.Cuanto menor sea el umbral, más probabilidades tendrá de dar demasiada CPU a tareas de menor prioridad.

Answer 5

Dado que esta es una pregunta de la entrevista, solo estoy sugiriendo un algoritmo para abordar el problema.

Supongamos que tenemos tres colas separadas para tres tipos de tareas, lo que significa que tenemos tres colas una para TypeA, otra para TypeB, otra para Typec.

Podemos tener una cola de proceso digamos que es Qp.

Hay un programador que controla el Qa, Qb, Qc y llena el Qp.

Digamos que cada Tarea en Qa, Qb, Qc tendrá un campo especial que indica el número de ciclos de CPU necesarios para completar la tarea.

Digamos que Qa tiene tres tareas en las que la primera tarea requiere 1 ciclo de reloj. La segunda tarea requiere tres ciclos de reloj y la tercera requiere 3 ciclos de reloj.

Digamos que Qb tiene una tarea que requiere 2 ciclos de reloj y Qc tiene una tarea que requiere 1 ciclo de reloj.

El planificador dividirá la tarea T en tareas pequeñas y enques en Qp.

Entonces Qp se verá como Tc, Tb, Ta1, Ta2, Ta2, Ta2, Ta3, Ta3, Ta3.

El procesador puede deque Qp y ejecutar la tarea.

Si alguien encuentra la manera de mejorar este algoritmo, corrija.

Answer 6

Lo que realmente necesita aquí es un planificador jerárquico que implementa acciones ... su jerarquía con este aspecto:

  CPU 
      | 
------------------------- 
|   |   | 
A (70)  B (20)  C (10) 
      | 
     --------------- 
     | | | | | | 
     T1 T2 T3 T4 T5 T6 

Tenga en cuenta que yo no mostrar una jerarquía completa de A y C, pero estoy seguro de que tengo la idea. Ahora el camino a seguir es implementar un planificador basado en tiempo virtual muy simple, digamos Start-Time Fair Queuing (SFQ) de Goyal para manejar la programación entre A, B y C.

Tal programador es conservador de trabajo lo que significa que si solo están presentes tareas de C, entonces C como un todo tomará todo.

Ahora, para lidiar con el segundo nivel de programación, tiene dos formas ... O implementa HSFQ que es una versión jerárquica de SFQ o realiza un simple round-robin entre el subproceso A, B y C para que cada hilo obtiene una parte "justa" de los ciclos disponibles para su grupo.

Sería cuidadoso con round-robin aunque la equidad no es buena si tienes una mezcla de población con hilo de ráfaga y un hilo muy codicioso ... Round-robin no se asegurará de que usen la misma cantidad de ciclo excepto si te metes en el ciclo de conteo que se reduce más o menos a SFQ.

También puede mirar a Stride Programación más concretamente su versión jerárquica ...

creo que sirve,