|
Les systèmes d'exploitation emploient diverses stratégies pour éviter la famine dans les processus d'allocation des ressources. La famine se produit lorsqu'un processus se voit refuser à plusieurs reprises l'accès à une ressource, même s'il est capable d'effectuer son travail. Voici un aperçu des techniques courantes :
1. Planification basée sur les priorités avec vieillissement :
* Le problème : Les processus hautement prioritaires peuvent monopoliser continuellement les ressources, empêchant les processus moins prioritaires d'avoir une chance de s'exécuter et pouvant potentiellement provoquer une famine.
* La solution - Vieillissement :
* Concept : Au fil du temps, augmentez la priorité des processus qui attendent depuis longtemps pour acquérir une ressource.
* Mise en œuvre : Le système d'exploitation incrémente périodiquement la priorité des processus en attente. Cela garantit que même les processus peu prioritaires deviendront éventuellement éligibles à l'exécution.
* Exemple : Un processus en attente de temps CPU peut voir sa priorité augmentée tous les quelques ticks d'horloge. Finalement, cela deviendra le processus le plus prioritaire et sera planifié.
2. File d'attente équitable et file d'attente équitable pondérée :
* Le problème : Les processus demandant la même ressource peuvent recevoir des allocations imprévisibles, favorisant potentiellement certains par rapport à d'autres à plusieurs reprises.
* La solution - File d'attente équitable :
* Concept : Garantir à chaque processus une part équitable d’une ressource dans le temps.
* Mise en œuvre :
* Les processus en attente d'une ressource sont placés dans une file d'attente.
* La ressource est allouée aux processus de manière équitable, souvent à l'aide d'algorithmes de planification circulaire ou similaires.
* Chaque processus se voit attribuer une tranche de temps (ou un autre quota de ressources) avant qu'un autre processus n'obtienne son tour.
* Mise en file d'attente équitable pondérée (WFQ) :
* Concept : Une variante de la file d'attente équitable où chaque processus se voit attribuer un poids qui détermine sa part relative de la ressource.
* Mise en œuvre :
* Les processus avec des poids plus élevés reçoivent des tranches de ressource proportionnellement plus grandes.
* Cela permet de prioriser les processus importants tout en garantissant que les autres processus reçoivent un certain accès.
3. Allocation de ressources avec prévention/évitement des blocages :
* Le problème : Une impasse peut conduire à la famine. Si les processus restent bloqués dans l'attente des ressources des autres, certains peuvent être bloqués indéfiniment. Même si l’on sort de l’impasse, les mêmes processus pourraient être choisis à plusieurs reprises comme victimes, conduisant à la famine.
* La solution :
* Prévention des blocages : Concevoir structurellement le système d'allocation des ressources pour éliminer les conditions qui provoquent une impasse. Cela pourrait impliquer :
* Élimination des exclusions mutuelles (généralement impossible) : Permettez que les ressources soient utilisées simultanément par plusieurs processus.
* Prévention des mises en attente et des attentes : Exiger qu'un processus demande toutes ses ressources en même temps, ou libérer toutes les ressources détenues avant d'en demander davantage.
* Aucune préemption : Autoriser le système d'exploitation à retirer de force des ressources à un processus (si le processus détient une ressource dont un autre processus a besoin et attend une autre ressource).
* Prévention de l'attente circulaire : Imposer un ordre total sur les types de ressources et exiger que les processus demandent des ressources par ordre croissant.
* Évitement des impasses : Surveillez dynamiquement l’état d’allocation des ressources et évitez d’allouer des ressources si cela pourrait conduire à une impasse. L'algorithme du banquier en est un exemple courant.
* Pourquoi cela aide-t-il à mourir de faim : En évitant les blocages, le système d'exploitation garantit que les ressources seront finalement libérées et mises à la disposition des processus en attente, réduisant ainsi le risque de blocage indéfini.
4. Systèmes basés sur les réservations :
* Le problème : Les processus peuvent être continuellement surenchéris par d'autres pour l'accès aux ressources.
* La solution :
* Concept : Autorisez les processus à réserver des ressources à l’avance.
* Mise en œuvre :
* Un processus peut demander une allocation garantie d'une ressource pour une période déterminée.
* Le système d'exploitation garantit que la ressource est disponible lorsque le processus en a besoin.
* Pourquoi cela aide-t-il à mourir de faim : La réservation empêche qu'un processus se voie refuser l'accès à plusieurs reprises parce qu'il ne peut pas rivaliser avec les demandes immédiates d'autres processus. Il garantit un certain niveau de service minimum.
5. Planification de la loterie :
* Le problème : Les processus peuvent être systématiquement malchanceux dans les schémas d’allocation aléatoire.
* La solution :
* Concept : Donner aux processus des « tickets de loterie » pour une ressource. Le système d'exploitation sélectionne un ticket au hasard et le processus détenant ce ticket obtient la ressource.
* Mise en œuvre :
* Chaque processus se voit attribuer un nombre de tickets proportionnel à son importance ou à son besoin.
* Le système d'exploitation organise une loterie pour déterminer quel processus obtient la ressource.
* Pourquoi cela aide-t-il à mourir de faim : Même s'il est toujours possible qu'un processus soit malchanceux dans une seule loterie, au fil du temps, les processus avec plus de tickets recevront statistiquement une plus grande part de la ressource, évitant ainsi un déni de service permanent. Plus un processus possède de tickets, plus ses chances de gagner sont élevées. Même les processus avec peu de tickets ont une chance non nulle de gagner, évitant ainsi une famine complète.
6. Mécanismes de rétroaction :
* Le problème : Les algorithmes de planification statique peuvent ne pas s'adapter correctement aux conditions changeantes du système.
* La solution :
* Concept : Surveiller les performances des processus et ajuster l’allocation des ressources en conséquence.
* Mise en œuvre :
* Le système d'exploitation suit la durée pendant laquelle les processus attendent des ressources.
* Si un processus attend depuis trop longtemps, le système d'exploitation peut augmenter sa priorité, allouer plus de ressources ou passer à un algorithme de planification différent.
* Pourquoi cela aide-t-il à mourir de faim : Les mécanismes de rétroaction permettent au système d'exploitation de répondre dynamiquement aux situations de famine et de prendre des mesures correctives.
Considérations clés :
* Frais généraux : Toutes ces solutions s’accompagnent de frais généraux. La complexité de l'algorithme a un impact sur l'utilisation du processeur et le suivi des temps d'attente nécessite de la mémoire.
* Équité versus efficacité : Il faut souvent trouver un compromis entre l'équité (éviter la famine) et l'efficacité globale du système. Un système parfaitement équitable n’est peut-être pas le plus efficace en termes de débit.
* Spécifique au contexte : La meilleure approche pour prévenir la famine dépend de la ressource spécifique allouée, de la nature des processus et des objectifs globaux du système. Un système d'exploitation en temps réel (RTOS) a des exigences plus strictes qu'un système d'exploitation à usage général.
En résumé, les systèmes d'exploitation emploient diverses techniques, souvent combinées, pour éviter la famine et garantir que tous les processus reçoivent finalement les ressources dont ils ont besoin pour accomplir leurs tâches. La clé est d’équilibrer l’équité, l’efficacité et les exigences spécifiques du système.
|
