Siguiente: Problemas Un nivel arriba: Problemas con varios procesadores Anterior: Problemas con varios procesadores

Nociones básicas

En un proceso de asignación de tareas con varios procesadores, utilizaremos los conceptos y la notación siguientes:

• Un conjunto finito de tareas: $A=\{a_1,\ldots,a_n\}$.
• Duración (de ejecución) de cada tarea, $\forall a\in A: d(a)\in \mbox{\bf Z}^+$.
• Un conjunto finito de procesadores: $P=\{p_1,\ldots,p_m\}$.
• Un punto de saturación (deadline): $S\in \mbox{\bf Z}^+$. Usualmente S es una cota para la ``carga'' que puede recibir cada procesador.
• Una asignación factible es una partición ${\cal A}=\left\{A_i\right\}_{1\leq i\leq m}$ del conjunto de tareas A tal que
  
  $$\mathop{\rm Max}_{1\leq i\leq m}\left\{\sum_{a\in A_i}d(a)\right\}\leq S.$$
  
  

• Sea ``$\preceq$'' una relación de orden en A. Una asignación con restricción en las precedencias es una función $\sigma:A\rightarrow [0,S]$ tal que
  • $\sigma$ es monótona, i.e.: $a\preceq b\Rightarrow \sigma(a)\leq \sigma(b)$,
  • en ningún momento se excede la capacidad de proceso:
    
    $$\forall i\leq S:\ \mbox{\rm card}\{a\in A\vert\sigma(a)\leq i < \sigma(a)+d(a)\}\leq m.$$