Ordonnancement
I. L'ordonnancement⚓︎
Ordonnancement
Afin de choisir quel processus va repasser en mode exécution, l'ordonnanceur applique un algorithme prédéfini lors de la conception de l'OS. Le choix que va réaliser cet algorithme va impacter directement la réactivité du système et les usages qui pourront en être fait. C'est un élément critique du système d'exploitation.
Nous allons maintenant voir le principe de fonctionnement de l'ordonnancement
Les différents algorithmes d'ordonnancement
- Le modèle FIFO : on affecte les processus dans l'ordre de leur apparition dans la file d'attente.
- Le modèle SJF (Shortest Job First) : on affecte en premier le « plus court processus en premier » de la file d'attente à l'unité de calcul.
- Le modèle Round Robin : (ou méthode du tourniquet) on effectue un bloc de chaque processus présent dans la file d'attente à tour de rôle, pendant un quantum de temps d'en général 20 à 30 ms. Si le processus n'est pas terminé, il repart en fin de liste d'attente.
D'autres algorithmes
Il existe d'autres algorithmes d'ordonnancement, comme par exemple le modèle Priorité, où chaque processus dispose d’une valeur de priorité et on choisit le processus de plus forte priorité à chaque fois. Actuellement, la plupart des systèmes d’exploitation utilise une évolution du modèle priorité, reposant sur les principes suivants :
Chaque processus possède une priorité de base.
Cette priorité augmente quand le processus est inactif et diminue quand il est actif (le taux de changement dépend de la priorité de base).
Le système choisit parmi les processus de plus forte priorité.
Le quantum
Le quantum est une unité arbitraire de temps
Eléments pour l'ordonnancement
- Durée du processus ou durée d'exécution sur le coeur : à la durée en quantum P nécessaire à l'execution du processus.
- Date d'arrivée ou date de soumission : date où le processus arrive dans la file d'attente.
- Date de terminaison: pour un processus P : durée écoulée entre le temps 0 et le temps où le processus est terminée P
- Temps d'exécution ou temps de séjour : différence entre le temps d'arrivée de P et le temps de terminaison de P.
- Temps d'attente d'un processus P : différence entre le temps d'execution et la durée du processus.
- Temps moyen d'attente : moyenne des temps d'attente de tous les processus
Nous allons voir ceci dans différents ordonnancements
II. L'ordonnancement SJF⚓︎
En exemple, nous allons traiter un ordonnancement avec le modèle SJF
| Processus | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Durée en quantum | 3 | 6 | 4 | 2 | 1 |
| Date d'arrivée | 0 | 1 | 4 | 6 | 7 |
👉 Etape 1 : classons les processus selon l'ordre croissant de leur durée : P5 (1 qt) < P4 (2qt) < P1 (3 qt) < P3 (3 qt) < P2 (6qt)
👉 Etape 2 :
- Au début du traitement des processus l'horloge mesurant les quantums est à 0.
- P1 arrive en 0 , il n'y a pas d'autre processus en attente. L'OS execute P1 pendant 3 quantums
- A la fin de P1, l'horloge indique 3 quantums. Pendant le traitement de P1 seul P2 est arrivé. L'OS traite P2 et son traitement dure 6 quantums.
- A la fin du traitement de P2, l'horloge indique 9 quantums. Pendant le temps de traitement de P2, sont arrivés P3, P4 et P5. L'OS va traiter le plus court donc P5, puis il va traiter P4 en enfin il traite P3.
- A la fin du traitement des 5 processus, l'horloge indique 16 quantums
✏️ Nous obtenons le schéma suivant :
Comment compléter le tableau suivant ?
| Processus | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Durée en quantum | 3 | 6 | 4 | 2 | 1 |
| Date d'arrivée | 0 | 1 | 4 | 6 | 7 |
| Date de terminaison | |||||
| Temps d'exécution | |||||
| temps d'attente |
Aides
- La date de terminaison (optionnelle) est la date de démarrage de l'exécution plus la durée en quantums
- Le temps d'exécution est la date de terminaison moins la date d'arrivée
- Le temps d'attente est le temps d'exécution moins la durée du processus
Réponse
| Processus | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Durée en quantum | 3 | 6 | 4 | 2 | 1 |
| Date d'arrivée | 0 | 1 | 4 | 6 | 7 |
| Date de terminaison | 3 | 9 | 16 | 12 | 10 |
| Temps d'exécution | 3 | 8 | 12 | 6 | 3 |
| temps d'attente | 0 | 2 | 8 | 4 | 2 |
III. Les ordonnancements FIFO et Round Robin (tourniquet)⚓︎
IV. Exercices⚓︎
Exercice 1 :⚓︎
FIFO
| Processus | P1 | P2 | P3 |
|---|---|---|---|
| Durée en quantum | 8 | 3 | 9 |
| Date d'arrivée | 8 | 5 | 0 |
Représenter l'ordonnancement des processus ci-dessus à l'aide du modèle FIFO.
Réponse
Exercice 2 :⚓︎
SJF
| Processus | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 | 2 |
| Date d'arrivée | 4 | 0 | 3 | 7 |
Représenter l'ordonnancement des processus ci-dessus à l'aide du modèle SJF.
Réponse
Exercice 3 :⚓︎
Round Robin
| Processus | P1 | P2 | P3 |
|---|---|---|---|
| Durée en quantum | 8 | 5 | 9 |
| Date d'arrivée | 1 | 0 | 3 |
Représenter l'ordonnancement des processus ci-dessus à l'aide du modèle Round Robin (tourniquet)
Réponse
Exercice 4 :⚓︎
SJF et Round Robin
Les trois processus suivants doivent être exécutés simultanément sur un ordinateur à un seul microprocesseur. Chaque instruction dure 1 quantum. Nous les noterons P1, P2 et P3.
- L’ordonnanceur du système d’exploitation utilise la méthode SJF « plus court d’abord ». Schématiser l’ordre de traitement des instructions des 3 processus.
- L’ordonnanceur du système d’exploitation utilise la méthode du tourniquet. Schématiser l’ordre de traitement des instructions des 3 processus. Au départ, on supposera que P1 est exécuté, puis P2, puis P3.
Réponse
Exercice 5 :⚓︎
comparaison des algorithmes
5 processus, P1, P2, P3, P4, P5 sont dans une file d'attente dans cet ordre (P1 est le premier, P5 est le dernier). Ils arrivent tous en même temps pour être traité. Leur exécution demande un temps total de service exprimé en unités arbitraires (quantum).
| Processus | P1 | P2 | P3 | P4 | P5 |
|---|---|---|---|---|---|
| Durée en quantum | 10 | 1 | 2 | 1 | 5 |
- Décrire l'exécution des processus (schéma + tableau) dans le cadre des politiques d'ordonnancement FIFO, SJF, RR (avec un quantum de 1).
- Quelle est de ces trois politiques, celle qui correspond à un temps minimal d'attente moyen par processus?
Réponse
Temps d'attente moyen :
- RR : \(\dfrac{9+1+5+3+9}{5} = 5,4\)
- FIFO : \(\dfrac{0+10+11+13+14}{5} = 9,6\)
- SJF : \(\dfrac{9+0+2+1+4}{5} = 3,2\)
Détails :
QCM⚓︎
Comment s'appelle la gestion du partage du processeur entre différents processus?
- l'interblocage
- l'ordonnancement
- la planification
- la priorisation
l'ordonnancement
L'ordonnanceur :
- donne des instructions pour réparer des processus cassés
- transforme un programme en processus
- planifie l'exécution des processus
- planifie l'exécution des processus
Un processus
- ne s'exécute jamais en même temps qu'un autre processus sur le même processeur.
- peut être mis en attente par l'ordonnancement du système d'exploitation
- réalise l'ensemble des ses instructions avant de rendre la main
- ne s'exécute jamais en même temps qu'un autre processus sur le même processeur.
- peut être mis en attente par l'ordonnancement du système d'exploitation
TP ordonnancement⚓︎
Le TP
Vous lirez le fichier à partir de Basthon
👉 Vous devrez télécharger dans le même dossier les deux fichiers suivants
🌐 TD à télécharger : Fichier TP_ordonnanceur_sujet_2023.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"
👉 Vous devez charger le module suivant : test_tp_ordonn_sjf.py dans le document : icone ouvrir fichier puis choisir Installer le module
🌐 module à télécharger : "Clic droit", puis "Enregistrer la cible du lien sous"
Réponse
🌐 Fichier TP_ordonnanceur_corr_2023.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"
Crédits⚓︎
Auteurs Mireille Coilhac, Valérie Mousseaux, Jean-Louis Thirot , sur la base du travail de :
- Olivier Lécluse
- monlycéenumerique.fr
- courstechinfo.be