Planification du processeur Algorithms in OperaSystèmes de montage

Qu’est-ce que la planification du processeur ?

Planification du processeur L'ordonnancement du processeur consiste à déterminer quel processus utilisera le CPU pour son exécution lorsqu'un autre processus est en attente. Sa principale fonction est de garantir que, lorsque le CPU est inactif, le système d'exploitation sélectionne au moins un processus disponible dans la file d'attente des processus prêts à être exécutés. Cette sélection est effectuée par l'ordonnanceur du processeur, qui choisit un processus en mémoire prêt à être exécuté.

Types de planification du processeur

Voici deux types de méthodes de planification :

Planification préventive

Dans la planification préemptive, les tâches se voient généralement attribuer une priorité. Il est parfois important d'exécuter une tâche prioritaire avant une autre, même si cette dernière est encore en cours d'exécution. La tâche prioritaire est alors mise en attente pendant un certain temps, puis reprend son exécution une fois la tâche prioritaire terminée.

Planification non préemptive

Dans ce type de méthode d'ordonnancement, le processeur est alloué à un processus spécifique. Ce processus libère le processeur soit en changeant de contexte, soit en se terminant. C'est la seule méthode utilisable sur différentes plateformes matérielles, car elle ne nécessite pas de matériel particulier (par exemple, un minuteur), contrairement à l'ordonnancement préemptif.

Quand la planification est-elle préemptive ou non préemptive ?

Pour déterminer si la planification est préemptive ou non préemptive, considérez ces quatre paramètres :

1. Un processus passe de l’état en cours d’exécution à l’état d’attente.
2. Un processus spécifique passe de l'état d'exécution à l'état prêt.
3. Un processus spécifique passe de l'état d'attente à l'état prêt.
4. Un processus achève son exécution et se termine.

Si seules les conditions 1 et 4 sont remplies, l'ordonnancement est dit non préemptif. Toutes les autres situations d'ordonnancement sont préemptives.

Terminologies importantes de planification des processeurs

• Temps de rafale/temps d’exécution : Le temps nécessaire à un processus pour s'exécuter complètement. On l'appelle aussi temps d'exécution.
• Heure d'arrivée: Le moment où un processus passe à l'état prêt.
• Heure de fin : Le moment où un processus s'achève et quitte le système.
• Multiprogrammation : Plusieurs programmes peuvent être présents en mémoire simultanément.
• Travaux: Un type de programme sans aucune interaction avec l'utilisateur.
• Utilisateur: Un type de programme qui permet l'interaction avec l'utilisateur.
• Processus: La référence utilisée à la fois pour un poste et un utilisateur.
• Cycle de rafale CPU/E/S : Caractérise l'exécution du processus, qui alterne entre l'activité du processeur et les opérations d'entrée/sortie. Les temps d'utilisation du processeur sont généralement plus courts que les temps d'entrée/sortie.

Critères de planification du processeur

Un algorithme de planification du processeur tente de maximiser et de minimiser les éléments suivants :

Maximisez

Utilisation du processeur: L'utilisation du processeur est la principale tâche pour laquelle le système d'exploitation doit veiller à ce que le processeur reste aussi occupé que possible. Elle peut varier de 0 à 100 %. Cependant, pour un système d'exploitation temps réel (RTOS), elle peut varier de 40 % pour un système bas niveau à 90 % pour un système haut niveau.

Débit: Le débit correspond au nombre de processus qui terminent leur exécution par unité de temps. Ainsi, lorsque le processeur exécute un processus, un travail est effectué, et le travail accompli par unité de temps est appelé débit.

Minimiser

Temps d'attente: Le temps d'attente correspond à la durée pendant laquelle un processus spécifique doit attendre dans la file d'attente des processus prêts.

Temps de réponse: Il s'agit du délai entre la soumission de la demande et l'obtention de la première réponse.

Délai d'exécution: Le temps d'exécution correspond au temps nécessaire pour exécuter un processus. Il s'agit du temps total passé à attendre l'accès à la mémoire, à patienter dans la file d'attente et à s'exécuter sur le processeur. La période entre la soumission du processus et sa fin est donc le temps d'exécution.

Minuterie d'intervalle

L'interruption de la minuterie est une méthode étroitement liée à la préemption. Lorsqu'un certain processus obtient l'allocation de CPU, une minuterie peut être réglée sur un intervalle spécifié. L'interruption du temporisateur et la préemption forcent un processus à renvoyer le processeur avant que sa rafale de processeur ne soit terminée.

La plupart des systèmes d'exploitation multiprocessus utilisent une forme de minuterie pour empêcher un processus de monopoliser le système indéfiniment.

Qu’est-ce que Dispatcher ?

Le répartiteur est un module qui permet aux processus de contrôler le processeur. Il doit être rapide afin de pouvoir s'exécuter à chaque changement de contexte. La latence de répartition correspond au temps nécessaire au planificateur du processeur pour arrêter un processus et en démarrer un autre.

Fonctions assurées par le répartiteur :

• Changement de contexte.
• Passage en mode utilisateur.
• Déplacement vers le bon emplacement dans le programme nouvellement chargé.

Types de planification du processeur Algorithms

Il existe principalement six types de algorithmes de planification de processus:

1. Premier arrivé, premier servi (FCFS)
2. Planification du travail le plus court en premier (SJF)
3. Temps restant le plus court
4. Planification prioritaire
5. Planification du tournoi à la ronde
6. Planification de files d'attente à plusieurs niveaux

Planification Algorithms

Premier arrivé premier servi

FCFS signifie Premier arrivé premier serviIl s'agit de l'algorithme d'ordonnancement du processeur le plus simple. Dans ce type d'algorithme, le processus qui demande l'accès au processeur l'obtient en premier. Cette méthode d'ordonnancement peut être gérée par une file d'attente FIFO.

Lorsqu'un processus entre dans la file d'attente des processus prêts, son bloc de contrôle (PCB) est associé à la fin de la file. Ainsi, lorsque le processeur se libère, il doit être affecté au processus situé en début de file.

Caractéristiques de la méthode FCFS

• Il s'agit d'un algorithme d'ordonnancement non préemptif.
• Les travaux sont toujours exécutés selon le principe du premier arrivé, premier servi.
• Il est facile à mettre en œuvre et à utiliser.
• Cependant, cette méthode est peu performante et le temps d’attente général est assez élevé.

Temps restant le plus court

L'abréviation SRT signifie « Temps restant le plus court ». On parle également d'ordonnancement préemptif SJF. Cette méthode consiste à affecter un processus à la tâche la plus proche de son achèvement. Elle empêche ainsi un processus plus récent, prêt à l'exécution, de retarder la finalisation d'un processus plus ancien.

Caractéristiques de la méthode de planification SRT

• Cette méthode est principalement appliquée dans les environnements de traitement par lots où il est nécessaire de privilégier les tâches courtes.
• Cette méthode n'est pas idéale à mettre en œuvre dans un système partagé où le temps processeur requis est inconnu.
• Chaque processus est associé à la durée de sa prochaine rafale d'utilisation du processeur ; le système d'exploitation utilise donc ces durées pour planifier le processus dans les plus brefs délais.

Planification basée sur les priorités

Planification prioritaire Il s'agit d'une méthode d'ordonnancement des processus basée sur la priorité. Dans cette méthode, le planificateur sélectionne les tâches à exécuter en fonction de leur priorité.

L'ordonnancement par priorité permet également au système d'exploitation d'attribuer des priorités aux processus. Les processus les plus prioritaires sont exécutés en premier, tandis que les tâches de priorité égale sont traitées selon un algorithme de type « tourniquet » ou « premier arrivé, premier servi ». La priorité peut être déterminée en fonction des besoins en mémoire, en temps et d'autres facteurs.

Planification à tour de rôle

Round robin L'algorithme d'ordonnancement par rotation est l'un des plus anciens et des plus simples. Son nom provient du principe de la rotation, où chaque personne reçoit une part égale d'une ressource à tour de rôle. Il est principalement utilisé pour l'ordonnancement dans les systèmes multitâches. Cette méthode permet d'assurer l'exécution des processus sans risque de famine.

Caractéristiques de la planification à tour de rôle

• Le modèle Round Robin est un modèle hybride piloté par une horloge.
• Le temps alloué au traitement d'une tâche spécifique doit être minimal. Cependant, il peut varier d'un processus à l'autre.
• Il fonctionne comme un système à temps partagé qui répond à chaque processus dans un délai imparti.

Le travail le plus court en premier

SJF (Shortest Job First) est un algorithme d'ordonnancement qui sélectionne le processus ayant le temps d'exécution le plus court pour être exécuté ensuite. Cette méthode d'ordonnancement peut être préemptive ou non préemptive. Elle réduit considérablement le temps d'attente moyen des autres processus en attente d'exécution.

Caractéristiques de la planification SJF

• Chaque tâche est associée à une unité de temps à accomplir.
• Dans cette méthode, lorsque le processeur est disponible, le processus ou la tâche suivante ayant le temps d'exécution le plus court est exécuté en premier.
• Elle est mise en œuvre selon une politique non préemptive.
• Cet algorithme est utile pour le traitement par lots, où l'attente de la fin des tâches n'est pas critique.
• Cela améliore la productivité en exécutant d'abord les tâches plus courtes, qui ont généralement un temps d'exécution plus court.

Planification de files d'attente à plusieurs niveaux

Cet algorithme divise la file d'attente des processus prêts en plusieurs files d'attente distinctes. Dans cette méthode, les processus sont affectés à une file d'attente en fonction d'une propriété spécifique, telle que leur priorité, la taille de leur mémoire, etc.

Cependant, il ne s'agit pas d'un algorithme d'ordonnancement indépendant, car il doit utiliser d'autres types d'algorithmes pour planifier les tâches.

Caractéristiques de la planification des files d'attente à plusieurs niveaux

• Il convient de maintenir plusieurs files d'attente pour les processus présentant des caractéristiques communes.
• Chaque file d'attente peut avoir son propre algorithme d'ordonnancement.
• Des priorités sont attribuées à chaque file d'attente.

Objectif d'un algorithme d'ordonnancement

Voici les raisons d’utiliser un algorithme de planification :

• Le processeur utilise la planification pour améliorer son efficacité.
• Cela vous aide à répartir les ressources entre les processus concurrents.
• L'utilisation maximale du processeur peut être obtenue grâce à la multiprogrammation.
• Les processus à exécuter sont conservés dans la file d'attente des processus prêts.

FAQ