7.3: Agregar un algoritmo

Última actualización
Guardar como PDF

Page ID: 110805

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$ \newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$

( \newcommand{\kernel}{\mathrm{null}\,}\) $ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\id}{\mathrm{id}}$

$ \newcommand{\Span}{\mathrm{span}}$

$ \newcommand{\kernel}{\mathrm{null}\,}$

$ \newcommand{\range}{\mathrm{range}\,}$

$ \newcommand{\RealPart}{\mathrm{Re}}$

$ \newcommand{\ImaginaryPart}{\mathrm{Im}}$

$ \newcommand{\Argument}{\mathrm{Arg}}$

$ \newcommand{\norm}[1]{\| #1 \|}$

$ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\AA}{\unicode[.8,0]{x212B}}$

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

Hasta ahora, hemos estado creando horarios por conjetura y verificación, lo que funciona lo suficientemente bien para horarios pequeños, pero no funcionaría bien con docenas o cientos de tareas. Para crear un enfoque más procesal, podríamos comenzar por crear de alguna manera una lista de prioridades. Una vez que tenemos una lista de prioridades, podemos comenzar a programar usando esa lista y el algoritmo de procesamiento de listas.

Lista de Prioridad

Una lista prioritaria es una lista de tareas dadas en el orden en que deseamos que se completen.

El algoritmo de procesamiento de listas convierte una lista de prioridades en un horario.

Algoritmo de procesamiento

En el dígrafo o lista de prioridades, encierra en un círculo todas las tareas que están listas, lo que significa que todas las tareas prerrequisitos se han completado.
Asigne a cada procesador disponible, en orden, la primera tarea lista. Marcar la tarea como en progreso, tal vez poniendo una sola línea a través de la tarea.
Avanzar en el tiempo hasta que se complete una tarea. Marcar la tarea como completada, quizás tachando la tarea. Si alguna nueva tarea está lista, márquelas como tales.
Repita hasta que se hayan programado todas las tareas.

Ejemplo 2

Usando nuestro dígrafo de arriba, progrémalo usando la lista de prioridades a continuación:

$\mathrm{T}_{1}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Solución

Tiempo 0: Marcar tareas listas

Lista de prioridades:$({\mathrm{T}_{1}}), (\mathrm{T}_{3}), (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Asignamos la primera tarea,$\mathrm{T}_{1}$ al primer procesador$\mathrm{P}_{1}$, y la segunda tarea lista,$\mathrm{T}_{3}$, al segundo procesador. Al realizar esas asignaciones, marcamos esas tareas como en progreso:

Lista de prioridades:$\cancel{(\mathrm{T}_{1})}, \cancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}$

Agenda hasta aquí:

$clipboard_e77fb190a3f596755cb0ed99767471a80.png$

Saltamos al momento en que se completa la siguiente tarea, que es en el momento 2.

Tiempo 2: Ambos procesadores completan sus tareas. Marcamos esas tareas como completas. Con la Tarea 1 completada, la Tarea 2 estará lista:

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

Asignamos la siguiente tarea lista en la lista,$\mathrm{T}_{4}$ a$\mathrm{P}_{1}$, y$\mathrm{T}_{5}$ a$\mathrm{P}_{2}$.

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \cancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

$clipboard_ed931c39742cb3d6bfcc67592f093b557.png$

Tiempo 3: El procesador 1 ha finalizado$\mathrm{T}_{4}$. Completar$\mathrm{T}_{4}$ no hace que ninguna otra tarea esté lista (tenga en cuenta que todo el resto requiere que$\mathrm{T}_{2}$ se complete primero).

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}$

Como las siguientes tres tareas aún no están listas, asignamos la siguiente tarea lista,$\mathrm{T}_{2}$ a$\mathrm{P}_{1}$

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \cancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e5f8d7915ae037b71ff7e5fa3c51f66de.png$

Tiempo 3.5: El procesador 1 ha finalizado$\mathrm{T}_{2}$. Completar$\mathrm{T}_{2}$ causas$\mathrm{T}_{6}$ y$\mathrm{T}_{7}$ estar listos. Nos asignamos$\mathrm{T}_{6}$ a$\mathrm{P}_{1}$.

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \cancel{(\mathrm{T}_{6})}, (\mathrm{T}_{7}), \mathrm{T}_{8}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e5d65817f8fa5dc929322c44dbfb1f85a.png$

Tiempo 4: Ambos procesadores completan sus tareas. La finalización de$\mathrm{T}_{5}$$\mathrm{T}_{8}$ permite estar listo. Asignamos$\mathrm{T}_{7}$ a$\mathrm{P}_{1}$ y$\mathrm{T}_{8}$ a$\mathrm{P}_{2}$.

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \cancel{(\mathrm{T}_{7})}, \cancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}$

$clipboard_e00d40539291882f1466b3b9ba4fc17fc.png$

Tiempo 4.5: Ambos procesadores completan sus tareas. $\mathrm{T}_{9}$se prepara, y se asigna a$\mathrm{P}_{1}$. No hay tarea lista para$\mathrm{P}_{2}$ trabajar, así que$\mathrm{P}_{2}$ ociosa.

Lista de prioridades:$\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \xcancel{(\mathrm{T}_{7})}, \xcancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \cancel{(\mathrm{T}_{9})}$

$clipboard_e7bc0f4b15e2eb217727706f983d188af.png$

Con la última tarea concluida, tenemos un cronograma terminado, con tiempo de finalización 5.5 días.

Pruébalo ahora 1

Usando el dígrafo a continuación, cree un horario usando la lista de prioridades:

$\mathrm{T}_{1}, \mathrm{T}_{2}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{9}$

$sc3.svg$

Contestar

Tiempo 0: Las tareas 1, 4 y 7 están listas. Asignar tareas 1 y 4

Tiempo 9: Se completa la Tarea 4. Solo la tarea 7 está lista; asignar tarea 7

Tiempo 10: Se completa la Tarea 1. Tarea 2 ya lista. Asignar tarea 2

Tiempo 17: Se completa la Tarea 2. Nada está listo. Procesador 1 ralentí

Tiempo 22: Se completa la Tarea 7. Las tareas 5 y 8 están listas. Asignar tareas 5 y 8

Tiempo 26: Se completa la Tarea 8. La tarea 9 está lista. Asignar tarea 9

Tiempo 27: Se completa la Tarea 5. Las tareas 3 y 6 están listas. Asignar tarea 3

Tiempo 31: Se completa la Tarea 3. Asignar tarea 6

Tiempo 35: Todo está hecho. El tiempo de finalización es de 35 para este horario.

$clipboard_eeee2de77e15748630b6197c99fed34fc.png$

Es importante señalar que el algoritmo de procesamiento de listas en sí mismo no influye en el horario resultante; el horario está completamente determinado por la lista de prioridades seguida. El procesamiento de listas, aunque se puede hacer a mano, podría ser ejecutado con la misma facilidad por una computadora. La parte interesante de la programación, entonces, es cómo elegir una lista de prioridades que creará el mejor horario posible.