Problématiques de l'ordonnancement dans les systèmes distribués

L'ordonnancement est la question de la répartition dans le temps et l'espace de « tâches » (aussi appelées unités d'ordonnancement) au sein d'un système de traitement de l'information. C'est un des problèmes les plus étudiés en informatique et il recouvre de nombreuses situations très variées. Nous allons étudier ici 5 cas de systèmes distribués soumis à des contraintes diverses.

Cas d'étude

Gérer les tâches lors de la construction d'un index inversé pour un moteur de recherche sur le web

• Quelle est l'unité d'ordonnancement pertinente ?

• on pourrait parler des instances de fonctions sur les différentes données

• Quel est ou quels sont les objectifs principaux d'un ordonnancement dans ce cas ?

• exécution de toutes les instances de fonctions

• gestion de la tolérance aux pannes

• répartition pour les performances

• Quelles sont les contraintes pesant sur les ordonnancements valides ?

• vitesse de l'ordonnancement

• tout calculer en respectant les contraintes de précédences

• gérer la tolérance aux pannes

• Quels sont les critères de qualité d'un bon ordonnancement ?

• la vitesse d'execution

• l'efficacité énergétique

• outils ou algos pertinents

• Hadoop, Spark, etc

Ordonnancer les traitements dans un processeur multi-cœur

Quelle est l'unité d'ordonnancement pertinente ?

Les fils d'exécution (threads)

Le processus est plutôt l'unité d'allocation de ressources

• Quel est ou quels sont les objectifs principaux d'un ordonnancement dans ce cas ?

• Améliorer la vitesse de traitement

• maximiser l'utilisation du processeur

• répartition équitable des tâches

• recouvrir les temps d'entrées-sorties (y compris les accès mémoires)

• L'ordonnanceur à également pour but de répartir de le temps d'exécution sur le processeur de manière équitable pour que chaque traitement puisse avancée. Un autre aspect que l'ordonnanceur doit prendre en compte est la distribution équitable des caches mémoire. Puisque si les caches du processeur sont souvent remis à zéro pour démarrer une nouvelle exécution, cela peut engendrer un temps d'exécution plus long.

• Quelles sont les contraintes pesant sur les ordonnancements valides ?

• Partage de la mémoire et des ressources au sein du processeur

• Conservation de l'intégrité des données

• Temps d'attente de ressources faible

• Répartition correcte des données pour maximiser la capacité des caches et éviter des appelles mémoire inutiles

-Quels sont les critères de qualité d'un bon ordonnancement ?

• L'équilibrage de charge

• la gestion des priorités (avec la commande nice par exemple)

• minimiser le surcoût de l'ordonnancement

Outils :

• BubbleSched, ordonnanceur de linux

Gérer l'utilisation d'un supercalculateur

• Quelle est l'unité d'ordonnancement pertinente ?

• "in a massively parallel system, the job management system needs to manage the allocation of both computational and communication resources, as well as gracefully dealing with inevitable hardware failures when tens of thousands of processors are present." // le « job » = ensemble de processus sur une partition de la machine

• Quel est ou quels sont les objectifs principaux d'un ordonnancement dans ce cas ?

• Minimiser le temps d'exécution

• Minimiser l'overhead lié à l'utilisation d'un supercalculateur

• Maximiser l'utilisation du supercalculateur

• Quelles sont les contraintes pesant sur les ordonnancements valides ?

• Il faut proposer une manière de distribuer les jobs "justement" : "firstcome, first served" (FCFS) achieves good job fairness but results in poor response times and resource fragmentation. On the other hand, using "short-job first" (SJF) achieves best response time in theory but violates job fairness and causes job starvation."

• Tolérance aux pannes

• Délais de communication

• Architecture de la machine (hétérogénéité des cœurs, accélérateurs, entrées-sorties asymétriques, etc)

• Quels sont les critères de qualité d'un bon ordonnancement ?

• équité entre jobs

• Rapidité et égalité sur les entrées/sorties

• Waiting time [1]

• Depth [1]

• Fairness ( fair start time) [1]

• System utilization rate [1]

• Loss of capacity [1]

Outils :

SLURM

Ordonnancer les traitements dans un système multi-processeurs temps-réel (par exemple l'aide à la conduite dans une voiture)

Quelle est l'unité d'ordonnancement pertinente ?

Un thread.

• Quel est ou quels sont les objectifs principaux d'un ordonnancement dans ce cas ?

  • La prise en compte de contraintes temporelles dont le respect est aussi important que l'exactitude du résultat

  • Répartition des traitements sur les ressources de calcul tout en respectant les contraintes temporelles

  • Quelles sont les contraintes pesant sur les ordonnancements valides ?

• Criticité mixte

1. Contraintes de temps

2. Contraintes de précédences

3. Contraintes d'exclusions mutuelles (mutex)

4. respect du pire temps d'exécution de chaque tâche (WCET)

• Quels sont les critères de qualité d'un bon ordonnancement ?

• Répartir équitablement les charges de travail

• Bien réagir à la variabilité des traitements

• Ne pas gaspiller trop de ressource

Ordonnancer les traitements dans une caméra HD professionnelle (retransmission télévisuelle)

Quelle est l'unité d'ordonnancement pertinente ?

tâche = un morceau du traitement

• Quel est ou quels sont les objectifs principaux d'un ordonnancement dans ce cas ?

• optimiser les ressources

• conception conjointe logiciel - matériel

• Minimiser les coûts d'exécution de l'algorithme avec un ordonnancement statique par exemple

• stocker efficacement le flux visuel enregistré

• Quelles sont les contraintes pesant sur les ordonnancements valides ?

• contraintes fonctionnelles = précédences entre tâches

• contraintes non fonctionnelles = architecture matérielle + temps réel

• Respect des temps d'exécution (système temps réel)

• Ne pas dépasser un certain temps de calcul

• Quels sont les critères de qualité d'un bon ordonnancement ?

• La meilleure adéquation application/architecture

• Faire en sorte que les images soient calculées assez vite

• Si le traitement est trop long, abandonner le traitement actuel pour ne pas prendre de retard(perte d'image)

• Si le traitement se finit plus tôt, attendre avant de traiter l'image suivante

Sources caméra HD :

https://arxiv.org/pdf/1212.4455.pdf

https://docplayer.fr/8571381-Caracteristiques-camera-cinealta-hd-avec-2-2-millions-de-pixels-par-couleur-enregistrement-hdcam-commutable-50i-24p-et-25p-www-pro-sony.html

https://www.hdr.fr/Broadcast-Television/Serveurs-diffusion/WinMedia.html

https://fr.wikipedia.org/wiki/Syst%C3%A8me_d%27exploitation_embarqu%C3%A9

Source système multi-processeurs temps-réel :

https://www.usenix.org/legacy/event/hotos07/tech/full_papers/rajagopalan/rajagopalan_html/index.html

https://www.scribd.com/doc/4838281/Operating-System-Scheduling-on-multi-core-architectures

https://www.lri.fr/~falcou/teaching/sys/session1/processus

https://fr.wikipedia.org/wiki/Syst%C3%A8me_temps_r%C3%A9el

https://perso.telecom-paristech.fr/pautet/inf342/supports/rt-sched.pdf

http://www.in2p3.fr/actions/formation/InfoTempsReel/Ordonnancement_TR.pdf

Sources supercalculateur :

https://ieeexplore.ieee.org/document/6337469

http://datasys.cs.iit.edu/events/MTAGS10/paper10.pdf

https://en.wikipedia.org/wiki/Supercomputer_operating_systems