Planeacion

PROGRAMACIÓN DE n TAREAS EN m PROCESADORES

Los problemas de programación se tornan complejos rápidamente. En esta sección, el problema se complica al considerarse varios procesadores .Primero se examinara el problema de m procesadores en paralelo; en este caso, cada tarea debe entrar a uno solo de los procesadores. Subsecuentemente, se presentará el problema de m procesadores enserie; en este caso, cada tarea debe entrar a cada proceso en el mismo orden. Estas dos situaciones se ilustran en la figura 9.5. Como se vera incluso estos sencillos incrementos de la complejidad hacen que el problema sea considerablemente más difícil.

.

Figura 9.5 Problemas de programación en procesadores en paralelo y serie.

Considere primero el caso en que existan m procesadoresidénticos. El problema es seleccionar dos procesadores para usarlos y la secuencia para las tareas en cada procesador. Si el objetivo es minimizar el tiempo medio de flujo, se puede usar una sencilla variación de la regla de programación de SPT. A continuación se proporciona el algoritmo.

Algoritmo 9.3 Minimizar el tiempo medio de flujo en m procesadores paralelo.

• Paso 1: Ordenar en secuenciatodas las áreas conforme al SPT.
• Paso 2: Tome las tareas de la lista, una a la vez, y prográmelas en el procesador con la menor cantidad de tiempo ya asignada. Romper arbitrariamente los enlaces.

Para ilustrar este procedimiento, considere la programación de las siguientes 10 tareas en tres procesadores idénticos.

| |Tiempo de procesamiento |
|Tarea i |ti(horas)|
|1 |5 |
|2 |6 |
|3 |3 |
|4 |8 |
|5 |7 |
|6 |2 |
|7 |3 |
|8 |5 |
|9 |4|
|10 |2 |

La secuencia de SPT es 6-10-3-7-9-1-8-2-5-4. . En la figura 9.6 se ilustra el programa resultante.
El tiempo medio de flujo de este programa es de 8.1 horas y el lapso de trabajo 18 horas. La primera lección que se aprende de este algoritmo es que el propósito de reducir el tiempo medio de flujo se logra mejor programandosiempre la tarea más corita en el siguiente procesador disponible. La segunda lección es como manejar casos de programación con dos o más procesadores idénticos en paralelo. Generalmente estos problemas de programación se manejan primero ordenando todas las tareas mediante alguna regla apropiada de procesador único y luego se asignan las tareas a los procesadores sobre la base de situar primeroel menor tiempo programado.

[pic]

Figura 9.6 Programa ilustrado para el algoritmo 9.3

Unas vez superadas el problema de un solo procesador, el lapso de trabajo del programa no se puede considerar ya independiente de la secuencia elegida. De este modo, si el objetivo es el lapso de trabajo y sus correspondientes connotaciones de eficiencia del procesador, se debe considerar una regla deprogramación apropiada. No existen reglas o algoritmos que garanticen un programa mínimo de lapso de trabajo. Sin embargo, se ha mostrado que un procedimiento sencillo se desempeña consistentemente bien.
Básicamente es el reverso de la regla de SPT que se uso en el algoritmo 9.3; es decir, el algoritmo se basa en la regla de situar primero el Tiempo Más Largo de Procesamiento Longest Processingtime (LPT) como se indica a continuación. Una vez aplicada la regla del LPT para determinar en que procesador se programa cada tarea, entonces las tareas en cada procesador se colocan en orden de SPT de modo que se minimice el tiempo medio de flujo para el esquema de asignación del procesador en particular.

Algoritmo 9.4. Reducir el lapso de trabajo, así como los tiempos medios de...