Ordonnancement dans les systèmes d'exploitation
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Dans les systèmes d'exploitation l’ordonnanceur désigne le module du noyau du système d'exploitation qui choisit les processus qui vont être exécutés par les processeurs d'un ordinateur.

En anglais, l'ordonnanceur est appelé scheduler.

Introduction

Un processus peut avoir besoin (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois grandes catégories :...) de la ressource processeur (Le processeur, ou CPU (de l'anglais Central Processing Unit, « Unité centrale de traitement »), est le composant de l'ordinateur qui exécute les programmes informatiques. Avec la...) pour, par exemple, effectuer des calculs, déclencher une interruption, etc. La plupart des composants matériel, et en particulier le processeur d'un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques...), n'est pas capable d'effectuer plusieurs traitements simultanément. Pour la très grande majorité des ordinateurs, avoir un seul processeur implique de ne pouvoir effectuer qu'un traitement à la fois.
Or, à un instant (L'instant désigne le plus petit élément constitutif du temps. L'instant n'est pas intervalle de temps. Il ne peut donc être considéré comme une...) donné, il est possible qu'il y ait plus de processus à exécuter qu'il n'y a de processeurs. Il est courant que de nombreux programmes soient exécutés en parallèle sur une machine mono processeur.

Un des rôles du système d'exploitation et plus précisément de l'ordonnanceur du noyau est de permettre à tous ces processus de s'exécuter et d'utiliser le processeur de manière optimale du point (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) de l'utilisateur. Pour arriver à donner l'illusion que plusieurs tâches sont traitées simultanément, l'ordonnanceur du noyau du système s'appuie sur les notions de commutation de contexte (Une commutation de contexte (context switch) en informatique consiste à sauvegarder l'état d'un processus ou d'un processus léger et à restaurer l'état d'un autre processus (léger) de façon à ce que des...) et d'ordonnancement.

Commutation de contexte (Le contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le contexte d'un mot, d'une phrase ou d'un texte inclut les mots qui l'entourent. Le concept de contexte issu...) et élection

Pour effectuer ces tâches, l'ordonnanceur procède de la manière suivante : à intervalle régulier, le système appelle une procédure d'ordonnancement qui élit le processus à exécuter. Si le nouveau processus est différent de l'ancien alors survient un changement de contexte, opération qui consiste à sauvegarder le contexte d'exécution de l'ancienne tâche, comme par exemple, les zones mémoires du processus, le pointeur de programme. Cette structure de données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) est généralement appelée PCB. Le système d'exploitation restaure le PCB de la nouvelle tâche.

Exemple

Si n tâches doivent être exécutées de manière simultanée et qu'il est physiquement impossible pour l'ordinateur de traiter plus d'une tâche simultanément, le noyau commute rapidement le contexte d'exécution des n tâches, de manière à ce que :

  • Une seule tâche soit exécutée à la fois,
  • globalement toutes les tâches soient exécutées.

Par exemple, avec 3 tâches cela peut se décomposer par

  1. Sauvegarde (En informatique, la sauvegarde (backup en anglais) est l'opération qui consiste à dupliquer et à mettre en sécurité les données contenues dans un système...) par le noyau des contextes d'exécutions de 3 tâches,
  2. commutation de contexte et élection de la nouvelle tâche n°1
    • Chargement (Le mot chargement peut désigner l'action de charger ou son résultat :) par le noyau du contexte de la tâche 1.
    • Exécution des instructions de la tâche 1 pendant x milli-secondes
    • Sauvegarde du contexte de la tâche 1
  3. commutation de contexte et élection de la nouvelle tâche n°2
    • Chargement par le noyau du contexte de la tâche 2.
    • Exécution des instructions de la tâche 2 pendant x milli-secondes
    • Sauvegarde du contexte de la tâche 2
  4. commutation de contexte et élection de la nouvelle tâche n°3
    • Chargement par le noyau du contexte de la tâche 3.
    • Exécution des instructions de la tâche 3 pendant x milli-secondes
    • Sauvegarde du contexte de la tâche 3
  5. commutation de contexte et élection de la nouvelle tâche n°1
    • Chargement par le noyau du contexte de la tâche 1.
    • Exécution des instructions de la tâche 1 pendant x milli-secondes
    • Sauvegarde du contexte de la tâche 1

...

(3 tâches ordonnancées avec l'algorithme Round-robin (L'anglicisme round-robin est utilisée dans plusieurs contextes.) (Chacun son tour)).

Types d'algorithmes

Du choix de l'algorithme d'ordonnancement dépend le comportement du système. Il existe deux grandes classes d'ordonnancement.

L'ordonnancement en temps partagé (Le temps partagé est une approche permettant de simuler le partage par plusieurs utilisateurs de temps processeur. Il ne faut pas le confondre avec le terme de multitâche : un système...)

Il est présent sur la plupart des ordinateurs " classiques ". Par exemple l'ordonnancement " decay " ; qui est celui par défaut sous Unix. Il consiste en un système de priorités adaptatives, par exemple il privilégie les tâches interactives pour que leur temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) de réponse soit bon. Une sous-classe de l'ordonnancement en temps partagé sont les ordonnanceurs dits " proportional share ", eux sont plus destinés aux stations de calcul et permettent une gestion rigoureuse des ressources. On peut citer notamment " lottery " et " stride ".

L'ordonnancement en temps réel

Il fournit la certitude qu'une certaine tâche sera terminée à un instant donné. Ceci est très recherché dans les systèmes embarqués.

Optimalité

Un ordonnanceur temps réel est dit optimal pour un système de tâches s'il trouve une solution d'ordonnancement du système si cette solution existe. S'il ne trouve pas de solution à ce système, alors aucun autre ordonnanceur ne peut en trouver une.

Algorithmes d'ordonnancement

  • Round-robin
  • Rate-monotonic scheduling (RMS)
  • Earliest deadline first scheduling (EDF)
  • FIFO
  • Shortest job first (SJF, ou SJN -Shortest Job Next-)
  • CFS

Stratégies d'ordonnancement

  • Ordonnancement sans réquisition
  • Ordonnancement avec réquisition
Page générée en 0.147 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique