GEF 435Principes des systèmes d’exploitation

Ordonnancement partie I(Tanenbaum 2.5)

Synopsis

• Arrière plan sur l’ordonnancement• Concepts d’ordonnancement• Catégories des algorithmes d’ordonnancement• Buts de l’ordonnancement• Ordonnancement dans les systèmes de lots (batch)

Arrière plan

• L’ordonnancement sur les systèmes d’exploitation initiaux était facile: exécute le prochain programme sur le ruban magnétique

• Les ordinateurs personnels ont changé cet environnement parce ce que nous mettons l’emphase sur le processus qui interagit avec l’utilisateurDe plus avec l’augmentation de la vitesse des CPU, la plupart

des programmes pour ordinateurs personnels sont limités par la capacité de l’utilisateur à fournir les entrées, pas par le CPU

Arrière plan

• Avec plusieurs processus qui sont en compétition pour les précieux cycles du CPU, une décision doit être faite pour savoir quel processus va exécuter

• L’ordonnanceur est la partie du système d’exploitation qui fait ce choix, basé sur un algorithme d’ordonnancement

• L’ordonnanceur peut faire une très grande différence dans la performance qui est perçu par l’utilisateur:Est-ce que l’ordonnanceur exécute la job de lots ou le processus

qui répond à une entrée de l’utilisateur?

Concepts d’ordonnancement (comportement)

• Comportement du processusLes processus alternent entre des salves de travail pour le CPU

et des salves de demandes d’E/S• Les E/S qui sont fait par le CPU (ie: sans DMA) compte comme du

travail de CPU

Processus qui passent la majorité de leurs temps à exécuter sont tributaires du traitement (compute-bound) (tributaire du CPU)

Processus qui passent la majorité de leurs temps à attendre pour les E/S sont tributaires des E/S (I/O bound)

• Note: ceci veut dire les périodes d’attente pour l’E/S, pas le temps passé à faire les E/S

Concepts d’ordonnancement (comportement)

• Comportement des processus

• Note: Avec l’augmentation de vitesse des CPU, plus de processus deviennent tributaires des E/S

Tributaire du CPU

Tributaire des E/S

Concepts d’ordonnancement (Quand)

• On doit faire des décisions d’ordonnancement quand: Un nouveau processus est crée

• Exécute le parent ou l’enfant?Un processus termine

• Un nouveau processus de la liste des processus qui sont prêt doit être choisit (même si c’est le processus inactif (idle))

Un processus bloque sur E/S ou sémaphore• Pourrait être bon de démarrer un processus sur lequel le

processus bloqué attend• N’importe quel processus qui est prêt peut être démarré

Concepts d’ordonnancement (Quand)

• On doit faire des décisions d’ordonnancement quand:Sur une interruption

• Si l’interruption est un périphérique d’E/S, un processus était bloqué pour l’E/S peut être prêt à exécuter

• L’ordonnanceur pourrait démarrer le processus interrompu, le nouveau processus qui est maintenant prêt, ou un autre candidat

• Si l’interruption vient d’une horloge matériel d’autres options sont possibles: un ordonnanceur préemptif peut décider de démarrer un autre processus et un ordonnanceur non préemptif retourne au processus courant et le laisse finir jusqu’à ce qu’il bloque ou laisse volontairement le CPU

Catégories d’algorithmes d’ordonnancement

• Différent algorithmes sont utilisés sur différents systèmes.

• Trois catégories majeurs pour algorithmes :Systèmes de lots

• Séries de programmes qui attendent pour exécutionSystèmes interactifs

• Utilisateurs aux terminaux qui attendent pour leurs réponsesSystèmes en temps réel

• Exécutent généralement dans un environnement non-hostile où les processus coopèrent pour finir une tâche

Buts des algorithmes d’ordonnancement

• Certains buts sont applicables à tout genre de systèmes Impartialité (Fairness)

• Les processus comparables devraient recevoir un service comparable

• Acceptable de traiter les différentes catégories de processus différemment, ie: le processus de fermeture d’un réacteur nucléaire a priorité sur un jeux

Application de la politique• Actuellement applique les buts de l’impartialité

Balance• Non désirable d’exécuter tout les processus qui sont tributaire du

CPU ensemble puis ensuite tout ceux qui sont tributaire des E/S

Buts des algorithmes d’ordonnancement

• Buts des systèmes de lots:Débit (Throughput)

• Maximise le nombre de jobs complétés par heureTemps de réponse (Turnaround time)

• Complète les jobs dans le plus petit lapse de temps possibleUtilisation du CPU

• Utilise le CPU le plus possible – c’est une ressource dispendieuse avec beaucoup de jobs qui attendent pour terminer

• Même si cette mesure est utilisé par certains, ce n’est pas un bon choix – Que préfèrerais GM: plus d’autos produits par heure ou que les robots soient utilisés 100% du temps?

Buts des algorithmes d’ordonnancement

• Systèmes interactifsTemps de réponse

• Le temps entre ce que l’utilisateur envoie sa commande et qu’il obtient un résultat

• Généralement la commande devrait prendre précédence sur le travail d’arrière plan

Proportionnalité• L’idée que ça ne dérange pas aux utilisateurs d’attendre si ils

pensent que la demande devrait prendre du temps

• Compiler un gros programme prend du temps, mais si ça prend 20 secondes à fermer un IDE on deviens furieux!

Buts des algorithmes d’ordonnancement

• Systèmes en temps réelRencontrer les échéanciers (deadlines)

• Ce but est évident quand on considère que les échéanciers sont une caractéristique marquante de ces systèmes

Prédictibilité• Être capable de prévoir combien de fois qu’un processus va

avoir le CPU aide à écrire un programme qui rencontre ses échéances

• Un processus qui est prédictible va exécuter avec moins de gigue “jitter” – Ceci est assez important pour les applications multimédia

Ordonnancement des systèmes de lots

• Les algorithmes pour les systèmes interactifs que nous allons voir le prochain cours; peuvent être aussi utilisés pour ordonnancer les systèmes de lots

• Cet examen couvre les algorithmes qui sont seulement utiles au systèmes de lots

• A moins d’être mentionné, l’ordonnancement réfère à ordonnancer les processus pour l’accès au CPU

Ordonnancement des systèmes de lots

• Premier-arrivé premier-servis - First-Come First-ServedL’algorithme le plus simpleNon-préemptifUne seule queue de processus prêtsChacun a le CPU et exécute jusqu’à ce qu’il bloqueAvantages:

• Facile à comprendre et implémenter

• Définitivement impartial (si on considère l’attente en ligne impartial)

Ordonnancement des systèmes de lots

• Premier-arrivé premier-servisDésavantages

• Potentiellement une grande perte de cycles de CPU

CPU (1s) I/O (1ms) I/O (1ms) I/O (1ms) I/O (1ms)

Chaque a besoin de faire 1000 lectures au disque, et bloque immédiatement (temps de CPU court: <1ms)

Plusieurs processus tributaire aux E/S

Si le processus d’E/S a le CPU une fois par seconde cela va prendre 1000 secondes pour que tout les processus complètent! Si le processus qui est tributaire au CPU donne le CPU tout les 10ms, tout les processus

qui font des E/S finissent en un petit 10 secondes!

Exécute pour 1s à la fois et

bloque

Ordonnancement des systèmes de lots

• La plus petite job en premier - Shortest Job First Non-préemptif Applicable pour les jobs de grandeur connue, ie: différent types de

réclamations dans une compagnie d’assurance Les processus mit dans cet ordre produisent le plus petit temps de

réponse (généralement)

Temps de réponse moyen= [8+(8+4)+(8+4+4)+(8+4+4+4)]/4= 14

Temps de réponse moyen= [4+(4+4)+(4+4+4)+(4+4+4+8)]/4= 11

Ordonnancement des systèmes de lots

• La plus petite job en premierNotez que le système est optimale quand tout les jobs

sont disponibles en même temps• Si une job qui est longue et encore en exécution quand un

nombre de petites jobs arrivent, le délais de la longue job est ajouté à tout les nouvelles jobs

Est-ce qu’il y a une solution à ce problème?Le temps du premier processus a plus d’impacte sur le

temps de réponse que tout les autres • (4a+3b+2c+d)/4

Ordonnancement des systèmes de lots

• Le plus petit temps qui reste est le Prochain -Shortest Remaining Time NextSimilaire à la plus petite job en premier, mais préemptifSi une job qui arrive a moins de temps pour compléter

que la job qui exécute, commence à exécuter la nouvelle job

Donne un bon service au nouvelles jobs qui sont courtes

Ordonnancement des systèmes de lots• Ordonnancement à trois niveaux

Jusqu’ici nous avons seulement considéré l’ordonnancement du CPU

Les systèmes de lots peuvent bénéficier de l’ordonnancement de trois façons:

• Admission (ie: processus est crée et a maintenant le potentiel d’embarquer sur le CPU au lieu d’attendre sur le disque)

• Mémoire (si on permute au disque ‘swapping’, combien de fois est-ce que le processus est amené en mémoire).

• CPU (les algorithmes que l’on viens de voir et ceux du prochain cours)

Ordonnancement des systèmes de lots• Ordonnancement à trois niveaux

Ordonnancement des systèmes de lots

• Considérations de l’ordonnancement à trois niveauxCritères potentiels pour l’ordonnanceur d’admission:

• Mix de processus tributaires du CPU et des E/S

• Admet les plus petites jobs en premier (similaire à la méthode pour le CPU)

• Peut tenir les jobs dans la queue d’admission pour exécuter les plus récentes

Ordonnancement des systèmes de lots

• Considérations de l’ordonnancement à trois niveauxCritères potentiels pour l’ordonnanceur de mémoire (par

processus):• Combien de temps depuis le dernier swap du processus?

• Combien de temps de CPU il a eu récemment?

• Comment gros est le processus?

• Comment important est le processus?

Problèmes pour l’ordonnanceur de mémoire “big picture”:• Pas swaper trop souvent très coûteux en temps

• Peut gérer le dégrée de multiprogrammation pour obtenir près de 100% d’utilisation du CPU (pas de changement de tâches inutiles)

Quiz Time!

Questions?