Tout d'abord, notez que les "threads" mentionnés dans les diapositives ne sont pas comme les threads OS comme on peut le penser. Leur définition d'un fil est donnée à la diapositive 10: "a maximal sequence of instructions not containing parallel control (spawn, sync, return)". Pour éviter toute confusion, laissez-moi appeler une tâche à la place.
Sur les diapositives 32 à 35, un cercle représente une tâche ("fil") et les bords représentent des dépendances entre les tâches. Et les phrases que vous posez sont en fait des définitions: quand P ou plusieurs tâches sont prêtes à être exécutées (et donc tous les processeurs P peuvent être occupés), la situation est appelée une étape complète, tandis que si moins de P sont prêts, la situation est appelée une étape incomplète. Pour simplifier l'analyse, il est (implicitement) supposé que toutes les tâches contiennent un travail égal (de taille 1). Ensuite, le théorème sur la diapositive 35 fournit une limite supérieure de temps nécessaire pour qu'un planificateur glouton exécute un programme. Comme toute l'exécution est une suite d'étapes complètes et incomplètes, le temps d'exécution est la somme de toutes les étapes. Puisque chaque étape complète effectue exactement P travaux, le nombre d'étapes complètes ne peut pas être supérieur à T1 (travail total) divisé par P. Ensuite, chaque étape incomplète doit exécuter une tâche appartenant au chemin critique (car à chaque étape au moins une étape critique la tâche de chemin doit être prête et les étapes incomplètes exécutent toutes les tâches prêtes); le nombre total d'étapes incomplètes ne dépasse donc pas l'intervalle T_inf (longueur du chemin critique). Ainsi, la somme de T1/P et T_inf donne une limite supérieure au temps d'exécution.
Le reste des diapositives de la section "Programmation" est plutôt simple.
@Alexey Kukanov Désolé, j'ai malheureusement lié la mauvaise diapositive, il devrait être ok maintenant, j'ai mis à jour le lien ... merci –