• Accueil LIP6
  • Page : 'rapport_recherche' inconnue (menus.php)

LIP6 1999/013

  • Rapports de recherche
    Sur la borne de Graham pour l'ordonnancement cyclique
  • Ph. Chrétienne
  • 15 pages - 19/05/1999- document en - http://www.lip6.fr/lip6/reports/1999/lip6.1999.013.ps.gz - 66 Ko
  • Contact : Philippe.Chretienne (at) nulllip6.fr
  • Ancien Thème : SYSDEF
  • Ce papier concerne la performance des algorithmes de liste pour l'ordonnancement d'un système répétitif de N tâches génériques non préemptives sur m processeurs identiques. Le graphe réduit est supposé fortement connexe mais le nombre d'instances simultanément actives d'une même tâche générique n'est pas restreint. Quelques propriétés des ordonnacements sont d'abord montrées. On se restreint ensuite à la classe des ordonnancements réguliers pour lesquels on montre que le nombre de tâches prêtes ou actives à un instant quelconque est au moins égale à la hauteur minimale H* d'un circuit du graphe réduit. On montre ensuite que le rapport entre temps de cycle moyen d'un ordonnancement de liste régulier et le temps de cycle minimum est au plus égal à 2-(min{H^*,m}/m). Ce résultat qui est similaire à la garantie bien connue 2-1/m due à Graham pour les ordonnancements de liste dans le cas non-cyclique montre jusqu'à quel point les algorithmes de liste prennent en compte le parallélisme des systèmes cycliques de tâches.
  • Mots clés : Ordonnancement cyclique, Algorithme de liste, garantie
    de performance
  • Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
Mentions légales
Carte du site