Agregar recursivamente subprocesos a un grupo de subprocesos de Java

Question

Estoy trabajando en un tutorial para mi curso de concurrencia de Java. El objetivo es usar grupos de hilos para calcular los números primos en paralelo.

El diseño se basa en el Tamiz de Eratóstenes. Tiene una matriz de n bools, donde n es el entero más grande que está comprobando, y cada elemento en la matriz representa un número entero. True es primo, falso no es primo, y la matriz es inicialmente cierta.

Un grupo de subprocesos se utiliza con un número fijo de subprocesos (se supone que debemos experimentar con el número de subprocesos en el grupo y observar el rendimiento).

Un subproceso tiene un número entero múltiple para procesar. Luego, el hilo encuentra el primer elemento verdadero en la matriz que no es un múltiplo del número entero del hilo. El subproceso crea un nuevo subproceso en el grupo de subprocesos al que se asigna el número encontrado.

Después de formar un nuevo subproceso, el subproceso existente continúa estableciendo todos los múltiplos de su entero en el conjunto en falso.

El subproceso principal del programa inicia el primer subproceso con el entero '2', y luego espera a que finalicen todos los subprocesos generados. Luego escupe los números primos y el tiempo necesario para calcular.

El problema que tengo es que cuantos más subprocesos hay en el grupo de subprocesos, más lento se hace con 1 subproceso que es el más rápido. ¡Debería ser más rápido, no más lento!

Todo lo que se publica en Internet acerca de los grupos de subprocesos de Java crea n subprocesos de trabajo el subproceso principal y luego espera a que finalicen todos los subprocesos. El método que uso es recursivo ya que un trabajador puede engendrar más hilos de trabajo.

Me gustaría saber qué está pasando mal, y si los grupos de subprocesos de Java se pueden utilizar recursivamente.

Answer 1

Su solución puede funcionar más lentamente a medida que se añaden temas para algunos de los problemas siguientes:

• gastos generales de la creación del hilo: la creación de un hilo es caro.

• Conflicto de procesador: si hay más subprocesos que procesadores para ejecutarlos, algunos de los subprocesos se suspenderán en espera de un procesador libre. El resultado es que la tasa de procesamiento promedio para cada hilo disminuye. Además, el sistema operativo necesita cortar el tiempo de los hilos, y eso le quita tiempo que de otro modo se utilizaría para el trabajo "real".

• Conflicto de memoria virtual: cada hilo necesita memoria para su pila. Si su máquina no tiene suficiente memoria física para la carga de trabajo, cada nueva pila de subprocesos aumenta la contención de la memoria virtual que da como resultado paginación que desacelera las cosas

• Conflicto de caché: cada subproceso (presumiblemente) explorará una sección diferente de la matriz, lo que da como resultado falta de memoria caché. Esto ralentiza los accesos a la memoria.

• bloqueo de contención: si los hilos están leyendo y actualizar un conjunto compartido y el uso de objetos synchronized y una cerradura para controlar el acceso a la matriz, usted podría estar sufriendo de contención de bloqueo. Si se usa un único objeto de bloqueo, cada hilo pasará la mayor parte del tiempo esperando adquirir el bloqueo. El resultado neto es que el cálculo se serializa efectivamente, y la tasa de procesamiento general cae a la velocidad de un solo procesador/subproceso.

Los primeros cuatro problemas son inherentes a múltiples hilos, y no hay soluciones reales ... aparte de no crear demasiados hilos y reutilizar los que ya haya creado. Sin embargo, hay varias formas de atacar el problema de contención de bloqueo. Por ejemplo,

• Recodifique la aplicación para que cada subproceso explore por enteros múltiples, pero en su propia sección de la matriz. Esto eliminará la contención de bloqueo en las matrices, aunque necesitará una forma de decirle a cada hilo qué hacer, y eso debe diseñarse con contención en mente.
• Crea una matriz de bloqueos para diferentes regiones de la matriz y haz que los subprocesos seleccionen la cerradura para usarla según la región de la matriz en la que están operando. Todavía tendrías problemas, pero en promedio deberías tener menos contienda.
• Diseñe e implemente una solución sin cerraduras. Esto implicaría un ENTENDIMIENTO PROFUNDO del modelo de memoria de Java. Y sería muy difícil demostrar/demostrar que una solución sin cerraduras no contiene fallas sutiles de concurrencia.

Por último, recursiva creación de hilos es probablemente un error, ya que hará que sea más difícil para poner en práctica la reutilización hilo y las medidas anti-bloqueo de contención.

Answer 2

¿Cuántos procesadores hay disponibles en su sistema? Si #threads> #processors, agregar más hilos ralentizará las cosas para una tarea de cálculo como esta.

Recuerde que no importa cuántos subprocesos inicie, todavía comparten la misma CPU (s). Cuanto más tiempo pasa la CPU cambiando entre hilos, menos tiempo puede estar haciendo el trabajo real.

También tenga en cuenta que el costo de iniciar un hilo es significativo en comparación con el costo de comprobar un primo - probablemente puede hacer cientos o miles de multiplicaciones en el tiempo que lleva disparar 1 hilo.

Answer 3

El punto clave de un grupo de subprocesos es mantener un conjunto de subprocesos activo y volver a utilizarlos para procesar las tareas. Por lo general, el patrón consiste en tener una cola de tareas y seleccionar aleatoriamente un hilo del grupo para procesarlo. Si no hay un hilo libre y el grupo está lleno, simplemente espere.

El problema que ha diseñado no es bueno para ser resuelto por un grupo de subprocesos, porque necesita que los subprocesos se ejecuten en orden. Corrígeme si me equivoco aquí.

hilo # 1: Conjunto múltiple de 2 a falso

hilo # 2: encontrar 3, conjunto múltiple de 3 a falso

hilo # 3: encontrar 5, conjunto múltiple de 5 a falso

hilo # 4: encontrar 7, conjunto múltiple de 7 a falso

....

Estos temas necesitan ser ejecutados en orden y que está entrelazado (como el tiempo de ejecución t horarios hem) importa.

Por ejemplo, si el hilo # 3 comienza a ejecutarse antes de que el hilo # 1 establezca "4" en falso, encontrará "4" y continuará restableciendo los múltiplos de 4. Esto termina haciendo mucho trabajo extra, aunque el resultado final será correcto.

Answer 4

Reestructura tu programa para crear un ThreadPoolExecutor fijo por adelantado. Asegúrese de llamar a ThreadPoolExecutor # prestartAllCoreThreads(). Haga que su método principal envíe una tarea para el entero 2. Cada tarea presentará otra tarea. Como está utilizando un grupo de subprocesos, no creará y terminará un grupo de subprocesos, sino que permitirá que los mismos subprocesos realicen nuevas tareas a medida que estén disponibles. Esto reducirá la sobrecarga general de la ejecución.

usted debe conocer que en este caso el número óptimo de hilos es igual al número de procesadores (P) en la máquina. A menudo ocurre que la cantidad óptima de hilos es P + 1. Esto se debe a que P + 1 minimiza la sobrecarga del cambio de contexto al mismo tiempo que minimiza la pérdida del tiempo de inactividad/bloqueo.