Ejercicio resuelto: reparto de trabajo entre hilos en Java

Ejercicio de examen resuelto en Java: repartir un vector entre K hilos, acumular con synchronized y esperar con join, con código probado y errores típicos.

Actualizado el 16 de octubre de 2026

Código de Examen Java Sistemas operativos Nivel examen Código probado

Sistemas Operativos · Examen parcialEjercicio 3 · 2,5 puntos · 30 min

Una subestación eléctrica registra N lecturas de consumo, en kilovatios, y hay que analizarlas en paralelo con K hilos de Java. Llamamos pico a toda lectura estrictamente mayor que un umbral U. Se pide la suma de todas las lecturas y el número total de picos, además del resultado parcial que ha obtenido cada hilo.

Reparto del trabajo. Las lecturas se dividen en K bloques contiguos, tan equilibrados como sea posible. Si base = N / K y resto = N % K, el hilo h (numerados desde 0) recibe base + 1 lecturas si h < resto y base en caso contrario. Los bloques se asignan en orden: el hilo 0 empieza en el índice 0 y cada hilo empieza donde terminó el anterior. Un hilo puede recibir un bloque vacío.

Sincronización. Cada hilo recorre solo su bloque y calcula su suma y su número de picos en variables locales. Al terminar aporta ambos valores una única vez a un objeto Acumulador compartido, cuyos métodos deben ser synchronized. El hilo principal arranca los K hilos y espera a todos con join() antes de escribir nada. No se permite usar java.util.concurrent.

Entrada (por la entrada estándar): una primera línea con tres enteros N K U, con 0 ≤ N ≤ 100000, 1 ≤ K ≤ 16 y 0 ≤ U ≤ 109. A continuación vienen N enteros, separados por espacios, con valores entre 0 y 109. Si N es 0, no hay más datos.

Salida (por la salida estándar): K líneas, una por hilo y en orden de identificador, con el formato Hilo h: [ini, fin) suma=S picos=P, donde [ini, fin) es el intervalo semiabierto de índices del bloque. A continuación, una última línea Total: suma=S picos=P con los valores leídos del acumulador. La salida debe ser idéntica en todas las ejecuciones, sea cual sea el orden en que el planificador ejecute los hilos.

Entrada de ejemplo

10 3 50
12 70 55 3 90 41 50 51 8 100

Salida esperada

Hilo 0: [0, 4) suma=140 picos=2
Hilo 1: [4, 7) suma=181 picos=1
Hilo 2: [7, 10) suma=159 picos=2
Total: suma=480 picos=5

Reparto equilibrado de los N datos en K bloques contiguos: los N mod K primeros hilos reciben un elemento más y no se pierde ni se repite ningún índice

0,75

Creación de los K hilos, arranque de todos con start() antes de esperar a ninguno y espera correcta con join() antes de leer los resultados

0,75

Acumulador compartido protegido con métodos synchronized, con una sola aportación por hilo y no una por elemento

0,5

Formato de salida exacto, uso de long para las sumas y casos límite (N = 0, K > N)

0,5

Pistas

Pista 1 · ¿Cómo calculo los límites de cada bloque sin huecos?

Lleva una variable pos que empiece en 0. Para cada hilo h, su bloque empieza en pos y mide base + (h < resto ? 1 : 0). Después avanza pos esa cantidad. Al acabar el bucle, pos tiene que valer exactamente N. Comprueba a mano con N = 10 y K = 3: los tamaños deben ser 4, 3 y 3.

Pista 2 · ¿Qué tiene que estar protegido y qué no?

Solo hay estado compartido en el acumulador: la suma y la cuenta de picos totales. El recorrido del bloque usa variables locales del método run(), que viven en la pila de cada hilo y no necesitan cerrojo. Si el hilo llama al método synchronized una sola vez, al final, la contención es mínima. Llamarlo dentro del bucle sería correcto, pero desperdicia casi todo el paralelismo.

Pista 3 · ¿Dónde coloco los join() para no serializar los hilos?

Usa dos bucles separados: uno que llame a start() en todos los hilos y, después, otro que llame a join() en todos. Si haces start() y join() en la misma iteración, cada hilo termina antes de que nazca el siguiente. Para que la salida sea determinista, imprime solo después del segundo bucle, en el orden del array de hilos y no en el orden en que terminan.

Solución

Solución explicada

La solución separa tres responsabilidades. La clase Acumulador guarda el estado compartido. La clase Trabajador, que extiende Thread, procesa un bloque. El método main reparte el trabajo, lanza los hilos, espera con join() y escribe la salida. Cada hilo guarda también su resultado parcial en sus propios campos, de modo que el hilo principal pueda imprimirlo después sin depender del orden de ejecución.

Si quieres repasar el modelo clásico de hilos que comparten un búfer con wait() y notify(), puedes compararlo con el programa en C que genera 6 hilos y los identifica. Aquí el patrón es otro: dividir el trabajo, lanzar los hilos, esperarlos y combinar los resultados.

import java.io.IOException;

public class Main {

    // Estado compartido: solo se toca a través de métodos synchronized.
    static class Acumulador {
        private long suma;
        private int picos;

        synchronized void aportar(long s, int p) {
            suma += s;
            picos += p;
        }

        synchronized long suma() {
            return suma;
        }

        synchronized int picos() {
            return picos;
        }
    }

    // Cada trabajador procesa el intervalo [ini, fin) del vector.
    static class Trabajador extends Thread {
        private final int[] datos;
        private final int ini;
        private final int fin;
        private final int umbral;
        private final Acumulador acumulador;
        private long sumaLocal;
        private int picosLocal;

        Trabajador(int[] datos, int ini, int fin, int umbral, Acumulador acumulador) {
            this.datos = datos;
            this.ini = ini;
            this.fin = fin;
            this.umbral = umbral;
            this.acumulador = acumulador;
        }

        @Override
        public void run() {
            long s = 0;
            int p = 0;
            for (int i = ini; i < fin; i++) {
                s += datos[i];
                if (datos[i] > umbral) {
                    p++;
                }
            }
            sumaLocal = s;
            picosLocal = p;
            acumulador.aportar(s, p); // una sola sección crítica por hilo
        }
    }

    public static void main(String[] args) throws IOException, InterruptedException {
        String[] tok = new String(System.in.readAllBytes()).trim().split("\\s+");
        int n = Integer.parseInt(tok[0]);
        int k = Integer.parseInt(tok[1]);
        int umbral = Integer.parseInt(tok[2]);
        int[] datos = new int[n];
        for (int i = 0; i < n; i++) {
            datos[i] = Integer.parseInt(tok[3 + i]);
        }

        Acumulador acumulador = new Acumulador();
        Trabajador[] hilos = new Trabajador[k];
        int base = n / k;
        int resto = n % k;
        int pos = 0;
        for (int h = 0; h < k; h++) {
            int tam = base + (h < resto ? 1 : 0);
            hilos[h] = new Trabajador(datos, pos, pos + tam, umbral, acumulador);
            pos += tam;
        }

        for (Trabajador t : hilos) {
            t.start();
        }
        for (Trabajador t : hilos) {
            t.join();
        }

        StringBuilder sb = new StringBuilder();
        for (int h = 0; h < k; h++) {
            Trabajador t = hilos[h];
            sb.append("Hilo ").append(h).append(": [").append(t.ini).append(", ").append(t.fin)
              .append(") suma=").append(t.sumaLocal).append(" picos=").append(t.picosLocal).append('\n');
        }
        sb.append("Total: suma=").append(acumulador.suma())
          .append(" picos=").append(acumulador.picos()).append('\n');
        System.out.print(sb);
    }
}

Lectura. El programa lee toda la entrada de una vez con readAllBytes() y la parte en tokens. Así el caso N = 0 no necesita tratamiento especial: después de trim() quedan exactamente tres tokens y el bucle que rellena datos no se ejecuta. En el test «sin lecturas» se ve que el programa escribe dos bloques vacíos [0, 0) y un total de cero.

Reparto. El bucle sobre h calcula tam = base + (h < resto ? 1 : 0) y crea cada Trabajador con el intervalo [pos, pos + tam). En el ejemplo, N = 10 y K = 3, así que base = 3 y resto = 1. El hilo 0 recibe 4 lecturas y los otros dos, 3. Los intervalos resultantes son [0, 4), [4, 7) y [7, 10). Con K mayor que N, como en el test de 2 lecturas y 4 hilos, base vale 0 y los dos últimos hilos reciben bloques vacíos.

Trabajo de cada hilo. En run(), las variables s y p son locales y no las comparte nadie. Por eso el bucle no necesita ningún cerrojo. Al terminar, el hilo copia sus resultados en sumaLocal y picosLocal y llama una única vez a acumulador.aportar(s, p). Como aportar es synchronized, las dos sumas suma += s y picos += p se ejecutan en exclusión mutua sobre el monitor del acumulador. Ninguna actualización se pierde aunque dos hilos terminen a la vez.

Arranque y espera. Los dos bucles separados son la clave del paralelismo. Primero se llama a start() en todos los hilos, de modo que todos quedan listos para el planificador. Después, el bucle de join() bloquea al hilo principal hasta que cada trabajador termina. Si un hilo ya ha acabado, su join() vuelve en el acto. El orden en que terminan no importa, porque la salida se construye recorriendo hilos por índice.

Visibilidad. El hilo principal lee t.sumaLocal sin synchronized y la lectura es correcta. El modelo de memoria de Java establece que todo lo que hace un hilo ocurre antes de que otro hilo vuelva de un join() sobre él. Las lecturas del total pasan por acumulador.suma() y acumulador.picos(), que también son synchronized. Así el acceso al estado compartido es uniforme y no depende de ese razonamiento sutil.

Tipos. La suma es long. En el test «suma que desborda int», el primer bloque ya suma 2000000000 y el total llega a 3999999999. Ese valor no cabe en un int, cuyo máximo es 2147483647. La cuenta de picos sí cabe en un int, porque nunca supera N.

Casos de prueba

Caso	Entrada	Salida esperada	Salida real	Resultado
Ejemplo del enunciado	10 3 50 12 70 55 3 90 41 50 51 8 100	Hilo 0: [0, 4) suma=140 picos=2 Hilo 1: [4, 7) suma=181 picos=1 Hilo 2: [7, 10) suma=159 picos=2 Total: suma=480 picos=5	Hilo 0: [0, 4) suma=140 picos=2 Hilo 1: [4, 7) suma=181 picos=1 Hilo 2: [7, 10) suma=159 picos=2 Total: suma=480 picos=5	OK
Un solo hilo	5 1 0 0 1 2 3 0	Hilo 0: [0, 5) suma=6 picos=3 Total: suma=6 picos=3	Hilo 0: [0, 5) suma=6 picos=3 Total: suma=6 picos=3	OK
Más hilos que lecturas	2 4 5 7 5	Hilo 0: [0, 1) suma=7 picos=1 Hilo 1: [1, 2) suma=5 picos=0 Hilo 2: [2, 2) suma=0 picos=0 Hilo 3: [2, 2) suma=0 picos=0 Total: suma=12 picos=1	Hilo 0: [0, 1) suma=7 picos=1 Hilo 1: [1, 2) suma=5 picos=0 Hilo 2: [2, 2) suma=0 picos=0 Hilo 3: [2, 2) suma=0 picos=0 Total: suma=12 picos=1	OK
Sin lecturas	0 2 10	Hilo 0: [0, 0) suma=0 picos=0 Hilo 1: [0, 0) suma=0 picos=0 Total: suma=0 picos=0	Hilo 0: [0, 0) suma=0 picos=0 Hilo 1: [0, 0) suma=0 picos=0 Total: suma=0 picos=0	OK
Suma que desborda int	4 2 999999999 1000000000 1000000000 1000000000 999999999	Hilo 0: [0, 2) suma=2000000000 picos=2 Hilo 1: [2, 4) suma=1999999999 picos=1 Total: suma=3999999999 picos=3	Hilo 0: [0, 2) suma=2000000000 picos=2 Hilo 1: [2, 4) suma=1999999999 picos=1 Total: suma=3999999999 picos=3	OK
División exacta	6 2 3 1 2 3 4 5 6	Hilo 0: [0, 3) suma=6 picos=0 Hilo 1: [3, 6) suma=15 picos=3 Total: suma=21 picos=3	Hilo 0: [0, 3) suma=6 picos=0 Hilo 1: [3, 6) suma=15 picos=3 Total: suma=21 picos=3	OK

Salidas reales: código compilado con Java 21.0.12.1 (Temurin) y ejecutado en un contenedor aislado el 16 de octubre de 2026.

Complejidad

Tiempo. Cada lectura la recorre exactamente un hilo, así que el trabajo total es O(N) más O(K) por crear, arrancar y esperar los hilos. Con P procesadores, el tiempo de pared ideal es O(N/K + K) si K ≤ P. En el entorno de corrección hay una sola CPU: los hilos se intercalan y no hay aceleración real, pero el resultado es el mismo. Las secciones críticas son K, una por hilo, y cada una cuesta O(1).

Memoria. El vector datos ocupa O(N) y se comparte por referencia: ningún hilo copia su bloque. Cada Trabajador añade O(1) campos más su pila, de modo que la memoria extra es O(K). Para N = 100000 enteros esto supone unos 400 KB, muy por debajo de cualquier límite razonable.

Errores típicos

• Llamar a join() justo después de start() en el mismo bucle. El programa da el resultado correcto, pero los hilos se ejecutan uno detrás de otro y desaparece el paralelismo que pedía el enunciado.
• Sumar directamente sobre un campo static long total desde run() sin synchronized. La operación total += x se compone de leer, sumar y escribir, y dos hilos pueden pisarse y perder aportaciones. Además, la escritura de un long no volátil ni siquiera está garantizada como atómica.
• Calcular el tamaño del bloque como N / K para todos los hilos. Se pierden las N % K últimas lecturas. Otro error frecuente es asignar todo el resto al último hilo, lo que no respeta el reparto que exige el enunciado.
• Llamar a run() en vez de start(). El código se ejecuta en el hilo principal, de forma secuencial, y no se crea ningún hilo nuevo.
• Imprimir desde dentro de run(). El orden de las líneas depende del planificador y la salida deja de ser determinista.
• Usar int para la suma. Con lecturas de hasta 109, basta con tres valores para desbordar.

Variantes

Sin objeto compartido: cada hilo escribe en su casilla

Si cada hilo escribe solo en la posición id de dos arrays sumas y picos, no hay ninguna variable escrita por dos hilos y no hace falta synchronized. El hilo principal combina los resultados después de los join(), que garantizan la visibilidad. Es la forma más eficiente, pero el profesor puede exigir el acumulador precisamente para evaluar la exclusión mutua. Los límites ini y fin se escriben antes de start(), que también establece una relación ocurre antes.

public class Main {
    public static void main(String[] args) throws Exception {
        String[] tok = new String(System.in.readAllBytes()).trim().split("\\s+");
        int n = Integer.parseInt(tok[0]);
        int k = Integer.parseInt(tok[1]);
        int umbral = Integer.parseInt(tok[2]);
        int[] datos = new int[n];
        for (int i = 0; i < n; i++) {
            datos[i] = Integer.parseInt(tok[3 + i]);
        }
        long[] sumas = new long[k];
        int[] picos = new int[k];
        int[] ini = new int[k];
        int[] fin = new int[k];
        Thread[] hilos = new Thread[k];
        int base = n / k, resto = n % k, pos = 0;
        for (int h = 0; h < k; h++) {
            ini[h] = pos;
            pos += base + (h < resto ? 1 : 0);
            fin[h] = pos;
            final int id = h;
            hilos[h] = new Thread(() -> {
                long s = 0;
                int p = 0;
                for (int i = ini[id]; i < fin[id]; i++) {
                    s += datos[i];
                    if (datos[i] > umbral) p++;
                }
                sumas[id] = s;
                picos[id] = p;
            });
        }
        for (Thread t : hilos) t.start();
        for (Thread t : hilos) t.join();
        long total = 0;
        int totalPicos = 0;
        StringBuilder sb = new StringBuilder();
        for (int h = 0; h < k; h++) {
            total += sumas[h];
            totalPicos += picos[h];
            sb.append("Hilo ").append(h).append(": [").append(ini[h]).append(", ").append(fin[h])
              .append(") suma=").append(sumas[h]).append(" picos=").append(picos[h]).append('\n');
        }
        sb.append("Total: suma=").append(total).append(" picos=").append(totalPicos).append('\n');
        System.out.print(sb);
    }
}

Productor y consumidor con búfer acotado

Otra pregunta clásica cambia el reparto estático por uno dinámico. Un hilo productor deposita lecturas en un búfer de capacidad C y K consumidores las retiran y acumulan. El búfer necesita dos métodos synchronized: poner espera con while (lleno) wait(); y quitar espera con while (vacío) wait();. Ambos llaman a notifyAll() tras modificar el búfer. Usar while y no if protege frente a despertares espurios. Para terminar, el productor inserta K marcas de fin, una por consumidor, y el principal hace join() sobre todos.

Lo que preguntará el profesor

«Si el hilo principal lee t.sumaLocal sin synchronized ni volatile, ¿qué te garantiza que no lee un valor antiguo, por ejemplo 0?»

La garantía la da el join(). El modelo de memoria de Java define que todas las acciones de un hilo ocurren antes de que otro hilo vuelva con éxito de un join() sobre él. Por eso, una vez que t.join() ha devuelto el control, las escrituras de sumaLocal y picosLocal son visibles para el hilo principal. Si leyéramos esos campos antes del join(), por ejemplo en un bucle que comprobara si ya son distintos de cero, no habría ninguna garantía. Podríamos ver 0 o un valor a medio escribir, y además sería una espera activa.

En los temarios

La planificación de hilos y la sincronización entre procesos figuran en el programa de Sistemas Operativos de la Universidad Tecnológica Nacional (FRBA), que incluye «Planificación e hilos en Procesos» y «Comunicación y Sincronización entre Procesos». En Chile, el programa de IIC2333 Sistemas Operativos y Redes de la Pontificia Universidad Católica de Chile recoge la sincronización y la comunicación entre procesos dentro de su bloque de procesos. Este ejercicio practica justo esos contenidos: lanzar hilos, esperar su fin y proteger un recurso compartido.

También tratan la gestión de procesos el programa de ELO321 Teoría de Sistemas Operativos de la Universidad Técnica Federico Santa María, que incluye administración de procesos y bloqueo mutuo, y el de CC3301 Programación de Software de Sistemas de la Universidad de Chile, centrado en procesos pesados con fork, exec y pipes. Este último es un buen contraste: allí los procesos no comparten memoria y se comunican por tuberías, mientras que aquí los hilos comparten el vector y hay que sincronizar el acceso.

Opinión · Qué haría yo si fuera…

Qué haría yo si fuera el estudiante que se enfrenta a este ejercicio: antes de escribir una línea de código, dibujaría los intervalos de los bloques para el ejemplo de 10 lecturas y 3 hilos y comprobaría que no hay huecos. Después decidiría qué dato es realmente compartido, que aquí es solo el acumulador. Por último, probaría a propósito el caso de más hilos que lecturas y el de ninguna lectura, porque ahí es donde se cae un reparto mal hecho. La sincronización bien puesta es la mínima: una sección crítica por hilo, no una por elemento.

Artículos relacionados de LaRebelión

Ejercicio resuelto: pila con vector y paréntesis equilibrados en CEjercicio resuelto: traspuesta, diagonales y sumas de matrices en Python

• Ejercicio resuelto: serialización con transient en Java
• Ejercicio resuelto: interfaces, default y múltiples implementaciones en Java
• Ejercicio resuelto: polimorfismo y enlace dinámico en Java

Historial de cambios

1. 16 oct 2026Reescrito con la plantilla de Código de Examen: enunciado de examen, pistas, solución explicada, casos de prueba y código compilado y ejecutado; versión en inglés enlazada.
2. 1 mar 2021Publicación original.

Artículo generado mediante AI.larebelion · Revisado por Jose Santamaria

Kernel · Dirección de tecnología · España

«Un hilo que entra en el cerrojo por cada elemento no es paralelismo, es una cola con más pasos.»