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 :

sjf

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

exo_1

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

exo_2

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

exo_3

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.

exo_2

Réponse

exo_4

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

exo_5

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 :

exo_5 détails

QCM⚓︎

Comment s'appelle la gestion du partage du processeur entre différents processus?

L'ordonnanceur :

Cocher la ou les affirmations correctesSolution

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

Cocher la ou les affirmations correctesSolution

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