Planification du processeur Algorithms in OperaSystèmes de montage

Types de planification du processeur

Voici deux types de méthodes de planification :

Planification préventive

Dans la planification préemptive, les tâches sont pour la plupart assignées avec leurs priorités. Parfois, il est important d'exécuter une tâche ayant une priorité plus élevée avant une autre tâche de priorité inférieure, même si la tâche de priorité inférieure est toujours en cours d'exécution. La tâche de priorité inférieure est conservée pendant un certain temps et reprend lorsque la tâche de priorité supérieure termine son exécution.

Planification non préemptive

Dans ce type de méthode de planification, le CPU a été alloué à un processus spécifique. Le processus qui maintient le processeur occupé libérera le processeur soit en changeant de contexte, soit en se terminant. C'est la seule méthode qui peut être utilisée pour diverses plates-formes matérielles. En effet, il ne nécessite pas de matériel spécial (par exemple, une minuterie) comme la planification préemptive.

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

Pour déterminer si la planification est préemptive ou non préemptive, tenez compte de 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 en cours d’exécution à l’état prêt.
3. Un processus spécifique passe de l’état d’attente à l’état prêt.
4. Le processus a terminé son exécution et s'est terminé.

Seules les conditions 1 et 4 s'appliquent, l'ordonnancement est dit non préemptif.

Toutes les autres planifications sont préventives.

Terminologies importantes de planification du processeur

• Temps de rafale/temps d’exécution : C'est le temps requis par le processus pour terminer son exécution. On l'appelle aussi temps d'exécution.
• Heure d'arrivée: lorsqu'un processus entre dans un état prêt
• Heure de fin : lorsque le processus est terminé et quitte un système
• Multiprogrammation : Un certain nombre de programmes pouvant être présents en mémoire en même temps.
• Travaux: Il s’agit d’un type de programme sans aucune interaction de l’utilisateur.
• Utilisateur: C'est une sorte de programme ayant une interaction avec l'utilisateur.
• Processus: C'est la référence qui est utilisée à la fois pour le travail et pour l'utilisateur.
• Cycle de rafale CPU/E/S : Caractérise l’exécution du processus, qui alterne entre l’activité du processeur et celle des E/S. Les temps CPU sont généralement plus courts que le temps des E/S.

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 tâche principale dans laquelle le système d'exploitation doit s'assurer que le processeur reste aussi occupé que possible. Cela peut aller de 0 à 100 pour cent. Cependant, pour le RTOS, cela peut aller de 40 % pour le système de bas niveau à 90 % pour le système de haut niveau.

Débit: Le nombre de processus qui terminent leur exécution par unité de temps est appelé Débit. Ainsi, lorsque le processeur est occupé à exécuter le processus, le travail est en cours à ce moment-là et le travail effectué par unité de temps est appelé débit.

Minimiser

Temps d'attente: Le temps d'attente est la durée qu'un processus spécifique doit attendre dans la file d'attente prête.

Temps de réponse: Il s'agit du temps pendant lequel la demande a été soumise jusqu'à ce que la première réponse soit produite.

Délai d'exécution: Le délai d’exécution est le temps nécessaire pour exécuter un processus spécifique. Il s'agit du calcul du temps total passé à attendre d'entrer dans la mémoire, à attendre dans la file d'attente et à s'exécuter sur le CPU. La période entre le moment de la soumission du processus et l’heure d’achèvement est le délai 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 multiprogrammés utilisent une forme de minuterie pour empêcher un processus de bloquer le système pour toujours.

Qu’est-ce que Dispatcher ?

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

Fonctions assurées par Dispatcher :

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

Types d’algorithme de planification du processeur

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

Premier arrivé premier servi

Le premier arrivé, premier servi est la forme complète du FCFS. Il s’agit de l’algorithme de planification CPU le plus simple et le plus simple. Dans ce type d'algorithme, le processus qui demande le CPU obtient en premier l'allocation de CPU. Cette méthode de planification peut être gérée avec une file d'attente FIFO.

Lorsque le processus entre dans la file d'attente prête, son PCB (Process Control Block) est lié à la queue de la file d'attente. Ainsi, lorsque le processeur devient libre, il doit être affecté au processus au début de la file d'attente.

Caractéristiques de la méthode FCFS

• Il propose un algorithme de planification non préemptif et 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

La forme complète de SRT est le temps restant le plus court. Elle est également connue sous le nom de planification préemptive SJF. Dans cette méthode, le processus sera affecté à la tâche la plus proche de son achèvement. Cette méthode empêche un processus prêt plus récent de retarder l’achèvement d’un processus plus ancien.

Caractéristiques de la méthode de planification SRT

• Cette méthode est principalement appliquée dans les environnements par lots où les tâches courtes doivent être privilégiées.
• Ce n'est pas une méthode idéale pour l'implémenter dans un système partagé où le temps CPU requis est inconnu.
• Associez à chaque processus la durée de sa prochaine rafale de processeur. Ainsi, le système d'exploitation utilise ces longueurs, ce qui permet de planifier le processus dans les plus brefs délais.

Planification basée sur les priorités

Planification prioritaire est une méthode de planification des processus basée sur la priorité. Dans cette méthode, le planificateur sélectionne les tâches à travailler selon la priorité.

La planification des priorités aide également le système d'exploitation à impliquer les affectations de priorités. Les processus ayant une priorité plus élevée doivent être exécutés en premier, tandis que les tâches ayant des priorités égales sont exécutées sur une base circulaire ou FCFS. La priorité peut être décidée en fonction des besoins en mémoire, des exigences de temps, etc.

Planification à tour de rôle

Le round robin est l’algorithme de planification le plus ancien et le plus simple. Le nom de cet algorithme vient du principe du round-robin, selon lequel chaque personne reçoit à son tour une part égale de quelque chose. Il est principalement utilisé pour planifier des algorithmes en multitâche. Cette méthode algorithmique permet une exécution des processus sans famine.

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

• Le round robin est un modèle hybride piloté par une horloge
• La tranche de temps doit être minimale et attribuée à une tâche spécifique à traiter. Cependant, cela peut varier selon les processus.
• Il s'agit d'un système en temps réel qui répond à l'événement dans un délai précis.

Le travail le plus court en premier

SJF est une forme complète de (le travail le plus court en premier) est un algorithme de planification dans lequel le processus avec le temps d'exécution le plus court doit être sélectionné pour l'exécution suivante. Cette méthode de planification peut être préemptive ou non préemptive. Cela réduit considérablement le temps d’attente moyen des autres processus en attente d’exécution.

Caractéristiques de la planification SJF

• Il est associé à chaque tâche comme unité de temps à accomplir.
• Dans cette méthode, lorsque le processeur est disponible, le processus ou la tâche suivante avec le temps d'exécution le plus court sera exécuté en premier.
• Il est implémenté avec une politique non préemptive.
• Cette méthode d'algorithme est utile pour le traitement par lots, où l'attente de la fin des tâches n'est pas critique.
• Il améliore le rendement des travaux en proposant des travaux plus courts, qui doivent être exécutés en premier, et qui ont généralement un délai d'exécution plus court.

Planification de files d'attente à plusieurs niveaux

Cet algorithme sépare la file d'attente prête 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 du processus, comme la priorité du processus, la taille de la mémoire, etc.

Cependant, il ne s’agit pas d’un algorithme de planification indépendant du système d’exploitation, 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

• Plusieurs files d'attente doivent être conservées pour les processus présentant certaines caractéristiques.
• Chaque file d'attente peut avoir ses algorithmes de planification distincts.
• Des priorités sont données pour chaque file d'attente.

Le but d'un algorithme de planification

Voici les raisons d’utiliser un algorithme de planification :

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

Résumé

• La planification du processeur est un processus permettant de déterminer quel processus possédera le processeur pour l'exécution pendant qu'un autre processus est en attente.
• Dans la planification préemptive, les tâches sont pour la plupart assignées avec leurs priorités.
• Dans la méthode de planification non préemptive, le processeur a été alloué à un processus spécifique.
• Le temps de rafale est le temps nécessaire au processus pour terminer son exécution. On l'appelle aussi temps d'exécution.
• L'utilisation du processeur est la tâche principale dans laquelle le système d'exploitation doit garantir que le processeur reste aussi occupé que possible.
• Le nombre de processus qui terminent leur exécution par unité de temps est appelé Débit.
• Le temps d'attente est la durée qu'un processus spécifique doit attendre dans la file d'attente prête.
• Il s'agit du délai pendant lequel la demande a été soumise jusqu'à ce que la première réponse soit produite.
• Le temps d’exécution est le temps nécessaire pour exécuter un processus spécifique.
• L'interruption de la minuterie est une méthode étroitement liée à la préemption.
• Un répartiteur est un module qui permet de contrôler le processeur du processus.
• Six types d'algorithmes de planification de processus sont les suivants : 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 à tour de rôle, 6) planification de files d'attente à plusieurs niveaux .
• Dans le Méthode du premier arrivé, premier servi, le processus qui demande le CPU obtient l'allocation de CPU en premier.
• Dans le temps restant le plus court, le processus sera alloué à la tâche la plus proche de son achèvement.
• Dans la planification prioritaire, le planificateur sélectionne les tâches à travailler selon la priorité.
• Ordonnancement à tour de rôle fonctionne sur le principe selon lequel chaque personne reçoit à son tour une part égale de quelque chose.
• Dans le travail le plus court, le temps d'exécution le plus court doit être sélectionné pour l'exécution suivante.
• La méthode de planification à plusieurs niveaux sépare la file d'attente prête 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.
• Le processeur utilise la planification pour améliorer son efficacité.