Introduction détaillée à la planification du processeur

Planification du processeur

Balises (séparées par des espaces) : Algorithme de planification de processus Système d'exploitation

---

Concepts de base

Définition
 : Gestion du système d'exploitation Ressources limitées du système. Lorsque plusieurs processus (ou requêtes émises par plusieurs processus) veulent utiliser ces ressources, en raison de la nature limitée des ressources, les processus (demandes) doivent être sélectionnés selon certains principes pour occuper les ressources. .

Le but est de contrôler le nombre d'utilisateurs de ressources et de sélectionner l'autorisation des utilisateurs de ressources pour occuper des ressources ou occuper des ressources. Trois niveaux de planification du processeur :

• Planification avancée : planification des tâches, l'objet de planification est le travail.

• Planification intermédiaire : planification de la mémoire (essentiellement C'est la fonction d'échange de mémoire)

• Planification de bas niveau : planification de processus, l'objet de planification est un processus ou un thread au niveau du noyau

Planification des tâches L'algorithme est également applicable à la planification des processus

Temps de service(T_s) : Le temps nécessaire au système pour fournir des services pour un travail ou un processus
Délai d'exécution(T_i) : L'intervalle de temps entre le moment où une tâche ou un processus est soumis au système et celui où la tâche ou le processus est terminé
Comprend généralement :

. Le temps pendant lequel le travail attend la planification dans la file d'attente de sauvegarde du stockage externe.
Le processus est dans Le temps passé à attendre la planification du processus dans la file d'attente prête.
Le temps pendant lequel le processus est exécuté sur le processeur.
Le temps d'attente pour la planification du processus sur la file d'attente de sauvegarde du stockage externe. temps pendant lequel le processus attend la fin de l'opération d'E/S.

Délai d'exécution moyen :
[T = frac{sum_{i=1}^n T_i}{n} ]
Délai d'exécution pondéré : rapport entre le délai d'exécution d'un travail et le temps nécessaire pour le réparer
[W_i = frac{T_i}{T_s}]
Délai d'exécution moyen pondéré :
[W = frac{sum_{i=1}^n frac{T_i}{T_s} }{n}]

Calendrier de planification, commutation et processus

Le programme de planification et de commutation des processus est le programme du noyau du système d'exploitation. Lorsque l'événement demandant la planification se produit, le planificateur de processus peut être exécuté lorsqu'un nouveau processus prêt est planifié, la commutation entre les processus sera effectuée. En théorie, ces trois choses devraient être exécutées séquentiellement, mais dans la conception réelle, lorsque le programme du noyau du système d'exploitation est en cours d'exécution, si des facteurs provoquant la planification du processus surviennent à un moment donné, la planification et la commutation peuvent ne pas être possibles immédiatement.

Dans les systèmes d'exploitation modernes, la planification et la commutation des processus ne peuvent pas être effectuées dans les situations suivantes :

1. Dans le processus de gestion des interruptions : le processus de traitement des interruptions est compliqué, il Il est difficile de changer de processus lors de la mise en œuvre, et le traitement des interruptions fait partie du travail du système. Il n'appartient logiquement pas à un certain processus et ne doit pas être privé des ressources du processeur.

2. Le processus se trouve dans la section critique du programme du noyau du système d'exploitation : après être entré dans la section critique, il doit accéder exclusivement aux données partagées. En théorie, il doit être verrouillé pour empêcher d'autres. programmes parallèles d'entrer. Après le déverrouillage, vous ne devez pas passer à d'autres processus avant de les exécuter pour accélérer la libération des données partagées.

3. Lors d'autres opérations atomiques nécessitant une protection complète contre les interruptions : telles que le verrouillage, le déverrouillage, l'interruption de la protection du site, la récupération et d'autres opérations atomiques. Dans un processus atomique, même les interruptions doivent être masquées et la planification et la commutation du processus ne doivent pas être effectuées.

Si les conditions qui provoquent la planification se produisent pendant le processus ci-dessus et que la planification et la commutation ne peuvent pas être effectuées immédiatement, l'indicateur de planification de demande du système doit être défini et la planification correspondante ne sera effectuée que lorsque le processus ci-dessus est terminé avec le commutateur.

Les situations dans lesquelles la planification et la commutation du processus doivent être effectuées sont :

1. Lorsqu'une condition de planification se produit et que le processus en cours ne peut pas continuer à s'exécuter, la planification et la commutation peuvent être effectuées immédiatement. Si le système d'exploitation effectue uniquement la planification des processus dans cette situation, il s'agit d'une planification sans privation.

2. Lorsque le traitement d'interruption ou le traitement d'interruption est terminé, avant de revenir au site d'exécution de programme en mode utilisateur du processus interrompu, si l'indicateur de planification de demande est défini, la planification et la commutation du processus peuvent être effectué immédiatement. Si le système d'exploitation prend en charge un planificateur d'exécution dans ce cas, la planification en mode de privation est implémentée.

La commutation de processus se produit souvent immédiatement après la fin de la planification. Elle nécessite la sauvegarde des informations de scène du point de commutation actuel du processus d'origine et la restauration des informations de scène du processus planifié. Lors du changement de contexte, le noyau du système d'exploitation pousse les informations contextuelles du processus d'origine dans la pile du noyau du processus actuel pour les enregistrer et met à jour le pointeur de pile. Une fois que le noyau a terminé de charger les informations locales du nouveau processus à partir de la pile du noyau du nouveau processus, de mettre à jour le pointeur d'espace de processus en cours d'exécution, de réinitialiser le registre du PC et d'autres travaux connexes, il commence à exécuter le nouveau processus.

Méthode de planification

• Méthode non préemptive
  Une fois le processeur affecté à un processus, il continuera à s'exécuter et ne sera jamais interrompu en raison d'une interruption de l'horloge ou Pour toute autre raison, le processeur du processus en cours d'exécution est préempté. Le processeur ne sera pas alloué à d'autres processus jusqu'à ce que le processus soit terminé ou bloqué en raison d'un événement

• Préemption.
  Le système permet au planificateur de suspendre un processus en cours d'exécution et de réaffecter le processeur affecté au processus à un autre processus en fonction de certains principes
  Certains principes doivent être suivis lors de la "préemption" :

<.>
• Principe de priorité

• Principe de priorité des processus courts

• Principe des tranches de temps

Algorithme de planification typique

Algorithme de planification premier arrivé, premier servi) :

est l'algorithme de planification FCFS, qui peut être utilisé à la fois pour la planification des tâches et pour la planification des processus. Le système suit l'ordre de arrivée des tâches (priorité au temps d'attente le plus long dans la file d'attente des tâches prêtes).
Inconvénients : L'urgence du travail n'est pas prise en compte et ne peut être exécuté que de manière séquentielle

Algorithme de planification prioritaire des travaux courts (processus) (travail court en premier) :

Il est configuré pour les tâches courtes, car la plupart des systèmes d'exploitation sont des tâches courtes Lorsque le travail est en cours d'exécution, le système sélectionne le tâche avec la durée d'exécution la plus courte et le transfère dans la mémoire.

1. SJF (non préemptif) : l'algorithme calcule la priorité en fonction de la durée du travail (le temps dont le travail a besoin pour s'exécuter). Plus le travail est court, plus sa priorité est élevée.

2. SPF (préemptif) : comme ci-dessus, mais lorsqu'il y a un travail avec une priorité plus élevée, il peut préempter les ressources et les exécuter en premier.

Inconvénients :

• La durée du travail doit être prévue à l'avance

• Ce n'est pas bon pour le processus de travail

• L'interaction homme-machine ne peut pas être réalisée

• Ne tient pas compte de l'urgence du travail

Algorithme de planification des priorités :

L'algorithme PSA est basé sur l'urgence du travail, la priorité correspondante est donnée au travail de l'extérieur et est planifiée en fonction de la priorité du travail.

Algorithme de planification à priorité fermée de réponse la plus élevée (taux de requêtes le plus élevé ensuite) :

L'algorithme HRRN prend en compte à la fois le temps d'attente du travail et le temps d'exécution du travail. Il introduit une priorité dynamique pour. aucun travail :

Priorité = (temps d'attente + temps de service requis) / temps de service requis

peut être abrégé en :

R = temps de réponse / temps de service requis

Caractéristiques :

1. Si le temps d'attente du travail est le même, plus le temps de service requis est court, plus la priorité est élevée . Semblable à l'algorithme SJF, il est avantageux pour les travaux courts

2. Lorsque le travail nécessite le même temps de service, plus le temps d'attente du travail est long, plus la priorité est élevée, similaire. à l'algorithme FCFS, qui est bénéfique pour les travaux longs

3. Pour les travaux longs (nécessitant un temps de service long), comme le temps d'attente est suffisamment long, vous pouvez également obtenir une priorité plus élevée. n'attendra pas éternellement.

Algorithme de planification de rotation des tranches de temps (RR)

Principe : le système attribuera toutes les demandes en fonction de la politique FCFS. Le processus prêt est organisé. dans une file d'attente prête et est configuré pour générer des interruptions séquentielles à intervalles réguliers, activer le planificateur de processus dans le système, terminer la planification séquentielle et allouer le processeur au nouveau processus leader de la file d'attente (ou au processus urgent nouvellement arrivé).

Changement de processus

1. Si une tranche de temps n'a pas été utilisée et que le processus en cours est terminé, le planificateur sera immédiatement activé et supprimé de la file d'attente d'exécution. de la file d'attente prête s'exécute et démarre une nouvelle tranche de temps

2. Lorsqu'une tranche de temps est écoulée, le gestionnaire d'interruption de synchronisation est activé. Si le processus n'a pas terminé son exécution, le planificateur envoie. jusqu'à la fin de la file d'attente prête, planifie l'exécution du processus principal de la file d'attente prête et démarre une nouvelle tranche de temps

Remarque : La tranche de temps. a été sélectionné S'il est petit, la planification fréquente du processus d'exécution et le changement de contexte long du processus augmenteront la surcharge du système si la tranche de temps est sélectionnée trop longue, l'algorithme RR dégénérera en l'algorithme FCFS, qui ne pourra pas répondre aux besoins des tâches courtes et ; utilisateurs interactifs. La tranche de temps doit être sélectionnée légèrement plus grande que la séquence. Le temps requis pour une interaction typique est que la plupart des processus sont terminés dans une tranche de temps

Algorithme de planification de file d'attente de commentaires à plusieurs niveaux (file d'attente de commentaires à plusieurs niveaux) :

1. Paramètres Plusieurs files d'attente prêtes et attribuez des priorités différentes à chaque file d'attente. Plus la priorité est élevée, plus la tranche de temps est petite. La file d'attente avec la priorité la plus élevée entre en premier dans la file d'attente à planifier.

2. L'algorithme de planification FCFS est utilisé entre les files d'attente Ce n'est que lorsque tous les processus de la file d'attente haute priorité sont terminés que la file d'attente suivante sera planifiée

3. Les processus dans la file d'attente sont planifiés selon l'algorithme de rotation. Les nouveaux processus entrent Après la mémoire, ils entrent d'abord dans la file d'attente avec la priorité la plus élevée

4. Lorsqu'une file d'attente de faible priorité est en cours d'exécution. , si un nouveau processus arrive, alors après avoir exécuté cette tranche de temps, le CPU est immédiatement alloué aux nouveaux travaux arrivant (préemptif).

Algorithme de planification des processus dans le système en temps réel

Le système en temps réel signifie que le système peut répondre aux demandes d'événements externes en temps opportun et traiter ces demandes en temps opportun . Sur la base de cette caractéristique, les systèmes en temps réel sont largement utilisés dans l'industrie (courant dans les systèmes de contrôle des armes), multimédia et autres
Dans les systèmes en temps réel, il existe généralement des tâches en temps réel difficiles (HRT). exigent qu'elles soient exécutées avant la date limite de début et qu'elles se terminent avant la date limite de fin. Tâches souples en temps réel Identique à ci-dessus, mais pas strictes
Il existe deux types d'algorithmes à noter dans les systèmes en temps réel : Echéance la plus précoce. Premier algorithme (Earliest Deadline First) et Least Laxity First (Least Laxity First). Les deux types d'algorithmes peuvent utiliser des méthodes préemptives et une planification non préemptive, mais cette dernière est souvent utilisée pour la planification préemptive.
En m réel périodique. planification temporelle, le temps de traitement de chaque tâche temps réel(C_i), temps de cycle (P_i), dans le cas d'un seul processeur, la condition doit être remplie : $sum_{ i=1}^mfrac{C_i}{P_i} (inférieur à 1 ; dans le cas d'un multiprocesseur, la condition doit être remplie )sum_{i=1}^mfrac{C_i}{P_i } $ est inférieur à N, N est le nombre de processeurs.

Earliest Deadline First Algorithm (EDF)

Cet algorithme hiérarchise les tâches en fonction de leurs délais dans les systèmes en temps réel

.

1. Non préemptif

2. Préemptif

Algorithme du moindre jeu en premier (LLF)

Dans cette méthode, les tâches sont prioritaires en fonction de leur urgence (slack), et plus la tâche est urgente, plus la priorité est élevée.

Le degré de slack de la tâche = le temps où elle doit être accomplie - son propre temps d'exécution - l'heure actuelle

Les tâches du système sont disposées dans une file d'attente prête en fonction du degré de marge, et les tâches avec une faible marge sont placées dans la file d'attente. c'est-à-dire que le planificateur s'exécute en premier.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!