Concepts multithreading Partie Famine

Bienvenue dans la deuxième partie de notre série multithreading ! Dans la première partie, nous avons exploré l'Atomicité et l'Immuabilité.

Dans cette partie, nous approfondirons la compréhension de la famine car elle est essentielle pour les ingénieurs, car elle garantit l'équité et les performances du système. En reconnaissant les risques de famine, les ingénieurs peuvent concevoir des systèmes qui donnent la priorité à l'équité, empêchent la monopolisation des ressources et garantissent que tous les threads disposent du temps CPU et des ressources nécessaires pour fonctionner de manière optimale.

L'attente interminable dans les lobbys de jeux

Imaginez que vous jouez à un jeu multijoueur en ligne et que vous essayez de rejoindre un lobby pour un mode de jeu populaire, comme une bataille en équipe. Vous attendez dans le hall depuis un moment, mais chaque fois qu'un match commence, un nouveau groupe de joueurs disposant d'une connexion Internet plus rapide ou d'un classement de compétences plus élevé est prioritaire et ajouté au jeu avant vous. Vous voyez des matchs recommencer encore et encore, mais vous ne semblez jamais y entrer !

Vous êtes techniquement dans la file d'attente, mais comme d'autres joueurs avec des temps de réponse plus rapides ou des classements plus élevés continuent de participer aux jeux en premier, vous restez indéfiniment dans le lobby. Malgré un système parfaitement fonctionnel, vous n'avez pas la possibilité de jouer en raison de la façon dont l'algorithme de matchmaking donne injustement la priorité aux autres.

1. La famine

La famine est une situation dans laquelle un processus se voit continuellement refuser l'accès aux ressources dont il a besoin pour se dérouler, même si ces ressources sont disponibles. Le processus reste dans un état d'attente car des processus plus prioritaires ou d'autres politiques d'allocation de ressources l'empêchent d'acquérir les ressources nécessaires. Contrairement à l'impasse, les ressources ne sont pas totalement indisponibles, mais le processus ne peut pas y accéder en raison d'une planification injuste.

2. Causes

• Inversion de priorité : lorsqu'un processus de priorité plus élevée attend une ressource détenue par un processus de priorité inférieure, le processus de priorité inférieure peut être privé de temps CPU si d'autres processus de priorité plus élevée les processus continuent d'arriver.

• Politiques d'allocation des ressources : certains algorithmes de planification peuvent favoriser certains processus (généralement ceux avec des priorités plus élevées), conduisant à une situation où les processus moins prioritaires se voient rarement attribuer des ressources.

• Algorithmes mal conçus : Si l'algorithme d'allocation des ressources n'est pas équilibré ou équitable, cela peut conduire à la négligence continue de certains processus.

• Demande élevée de ressources : Si quelques processus exigent une quantité excessive de ressources, ils peuvent affamer d'autres processus en monopolisant ces ressources.

• Longs délais d'attente : Les processus qui sont fréquemment préemptés ou qui se retrouvent en concurrence pour des ressources limitées peuvent connaître la famine.

3. Prévenir la famine

• Utiliser ReentrantLock avec équité

Le ReentrantLock de Java fournit une option pour faire respecter l'équité. En utilisant le constructeur ReentrantLock avec l'argument vrai, nous pouvons garantir que les threads acquièrent le verrou selon le principe du premier arrivé, premier servi (FCFS), évitant ainsi la famine.

private final Lock lock = new ReentrantLock(true); // Fair lock

• Utiliser le sémaphore pour un partage équitable des ressources

Un Sémaphore permet de contrôler l'accès à un nombre limité de ressources. En utilisant un sémaphore avec l'équité activée, nous pouvons garantir que les threads acquièrent les permis dans un ordre équitable, évitant ainsi la famine.

private final Semaphore sp = new Semaphore(1, true); // Fair semaphore

Le Sémaphore(1, true) est un sémaphore avec un seul permis et une équité activée.

• Éviter la famine dans le problème producteur-consommateur (en utilisant BlockingQueue)

Dans les problèmes traditionnels entre producteur et consommateur, la famine peut survenir si le producteur submerge le consommateur ou si les consommateurs se voient refuser l'accès à la ressource partagée. BlockingQueue empêche cela car il gère automatiquement la synchronisation entre les producteurs et les consommateurs. Le producteur et le consommateur sont bloqués lorsque la file d'attente est respectivement pleine ou vide. Cela garantit un juste équilibre entre les deux et évite que l’un n’écrase l’autre, évitant ainsi la famine.

• Utiliser ForkJoinPool de Java pour une planification équitable des tâches

Dans les scénarios où plusieurs tâches sont bifurquées et jointes, ForkJoinPool en Java fournit un moyen d'équilibrer équitablement le travail entre les threads. Il garantit le vol de travail, évitant ainsi la famine des threads les moins actifs. ForkJoinPool de Java gère efficacement le fractionnement et l'équilibrage des tâches, garantissant qu'aucun thread ne manque de travail. Ceci est réalisé à l'aide d'un algorithme de vol de travail, dans lequel les threads inactifs volent les tâches des threads occupés pour que tout se déroule sans problème

4. Comment le système d'exploitation empêche la famine

Les systèmes d'exploitation (OS) utilisent diverses techniques pour éviter la famine, une situation dans laquelle certains processus ou threads se voient refuser les ressources nécessaires (telles que le temps CPU, la mémoire ou l'accès aux E/S) pendant des périodes prolongées parce que les tâches les plus prioritaires dominent. Voici quelques-unes des méthodes courantes utilisées par un système d'exploitation pour prévenir la famine :

No.	Method	Description	Prevents Starvation By
1	Aging	Gradually increases priority of waiting processes.	Prevents long waits by adjusting priority based on wait time.
2	Round-Robin Scheduling	Allocates CPU time in a fixed cyclic order.	Ensures all processes get CPU time, avoiding starvation.
3	Completely Fair Scheduler	Allocates CPU based on fairness, independent of priority.	Ensures fair distribution of CPU time.
4	Priority Boosting	Temporarily raises the priority of starved processes holding important resources.	Prevents priority inversion and ensures high-priority tasks get needed resources.
5	Multilevel Feedback Queues	Dynamically adjusts process priorities based on behavior.	Promotes long-waiting processes to higher-priority queues.
6	Semaphores with Fairness	Ensures fair access to resources through FIFO queues.	Prevents low-priority tasks from being perpetually blocked by higher-priority tasks.
7	Fair Resource Allocation	Distributes system resources like CPU and memory based on process demand and need.	Prevents resource-hogging processes from starving others.
8	Fair I/O Scheduling	Prioritizes I/O requests to ensure timely completion for all processes.	Prevents disk I/O starvation for processes making low-priority requests.

En mettant en œuvre ces stratégies, les systèmes d'exploitation peuvent garantir qu'aucun processus ou thread ne soit indéfiniment privé de ressources, favorisant ainsi une utilisation plus juste et efficace des ressources système.

Points clés à retenir pour les ingénieurs logiciels

• La Famine est un problème de progrès dans lequel un processus continue de se voir refuser l'accès à une ressource, mais n'implique pas nécessairement que d'autres processus la bloquent dans un cycle de blocage. Cela est souvent causé par une planification ou une allocation de ressources injuste.
• La Famine survient même si la ressource dont elle a besoin est disponible, mais elle n'a jamais la chance de l'acquérir.
• La Famine se produit également même lorsqu'il n'y a pas de blocage du système.
• La famine peut être un effet secondaire de la prévention des impasses (par exemple, donner la priorité à certains processus pour éviter les impasses), il est donc crucial d'équilibrer l'équité avec les stratégies pour éviter les impasses.

Référence

Un immense merci à la documentation en ligne, à la communauté et à toutes les ressources disponibles qui ont rendu cet article possible.

1. Concepts multithreading Partie 1 : Atomicité et immuabilité
2. Stackoverflow
3. Info-graphiques

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!