Il existe deux structures de données qui sont connues de tout programmeur et qui sont tellement considérées comme des axiomes que personne n'essaie même d'analyser si elles sont nécessaires, si elles en retirent des avantages et si ce préjudice ne les dépasse pas.
File d'attente
Tout d'abord, nous allons discuter de la file d'attente. Quelle est la signification de la file d'attente? Une file d'attente est un tampon. Et quand avons-nous besoin d'un tampon? Lorsque nous n'avons pas le temps de traiter les événements entrants au rythme de leur arrivée.
En relation avec ce qui précède, une seule question se pose: pourquoi? La réponse est que nous espérons que quelque chose se produira et que le système nous permettra soudain de traiter les événements.
Voyons d'abord le premier paragraphe. Que devrait-il arriver au système, qu'il arrête soudainement de freiner et commence à digérer les données plus rapidement? Très probablement, certains processus gourmands en ressources mettront tout simplement fin et libéreront des ressources. Mais que se passe-t-il si cela ne se produit pas? Que faire des données? On sait que: soit nous les réinitialisons, soit le système entier se bloque simplement par manque de ressources.
Canard, il y a deux questions:
- Et pourquoi ne pouvez-vous pas supprimer les données immédiatement si nous savons que nous n'avons pas les ressources pour les traiter? C'est pourquoi il est impossible de faire une file d'attente à partir d'un élément?
- Ou la question inverse. Pourquoi avons-nous des illusions et ne fournissons-nous pas au système les ressources nécessaires pour traiter les données au rythme de la réception?
Les réponses à ces questions sont, en fait, évidentes. Nous ne savons tout simplement pas comment concevoir des systèmes logiciels et matériels. Parce que si nous savions comment les concevoir, nous saurions alors combien de données d'entrée nous avons, le taux de leur réception, combien nous avons besoin de les traiter et, en conséquence, nous pourrions calculer le besoin réel de ressources. Mais l'état actuel des outils et méthodologies de développement des TIC, à l'exception d'une partie des systèmes technologiques (et en aucun cas tous), ne nous permet pas de faire des calculs objectifs des besoins en ressources.
Et nous comblons ces lacunes avec toutes sortes de tampons, notamment sous forme de files d'attente. En conséquence, nous avons une bombe posée dans les fondations du bâtiment même au niveau de la fosse de fondation, car ces béquilles servent de source à divers problèmes méprisables et difficiles à saisir avec la fiabilité, la sécurité et simplement la qualité du travail.
Mais continuons, devant nous se trouve ma structure la plus «préférée» - la pile!
Pile
C'est sûr, comme l'a dit Hoar à propos de Null, qu'il s'agit d'une erreur d'un milliard de dollars, donc on peut en dire autant de la pile.
Il s'agit de l'une des structures les plus problématiques utilisées dans les TIC et son évitement maximal dans la pratique de création de matériel et de logiciels, jusqu'à l'éradication complète, est hautement souhaitable.
Alors, quel est exactement le problème de pile? Oui, exactement comme pour la file d'attente. Les piles sont fondamentalement impossibles à organiser. Dès qu'il y a une personne qui prédit avec précision la quantité de mémoire dont la pile de tout programme arbitraire a besoin, je m'excuse personnellement et j'écris un énorme article que j'avais tort et je demande pardon.
Mais quelque chose me dit qu'il est peu probable que cela se produise dans un avenir prévisible.
Analysons pourquoi nous avons besoin de piles? Oui, exactement pour le même, pour lequel la file d'attente. Ceci est un tampon. Autrement dit, ce sont des béquilles pour un esprit paresseux qui ne veut pas concevoir correctement les systèmes logiciels et matériels.
La leçon est donc la suivante: les récursions doivent être évitées lorsqu'il existe une solution itérative évidente. Cependant, cela ne signifie pas que les récursions doivent être éliminées à tout prix. Il existe de nombreux bons exemples d'utilisation de la récursivité, que nous allons démontrer dans les sections et chapitres suivants. Le fait qu'il existe des implémentations de procédures récursives sur des machines pratiquement non récursives prouve qu'à des fins pratiques tout programme récursif peut être transformé en un programme purement itératif. Cependant, cela nécessite un travail explicite avec la pile de récursivité, et ces actions obscurcissent souvent l'essence du programme de sorte qu'il peut être difficile à comprendre. Conclusion: les algorithmes de nature récursive et non itérative doivent être formulés comme des procédures récursives.
Nicklaus Wirth. Algorithmes et structures de données
D'accord avec le maître sur les options de conversion, je ne suis pas d'accord avec ses approches douces pour utiliser la pile.
J'ai proposé un théorème: tout algorithme de pile peut être converti en boucle, et ceux qui ne peuvent pas être convertis sont mauvais.
La pratique d'appeler des sous-programmes avec passage de paramètres à travers la pile doit être arrêtée, et la récursivité qui ne se développe pas dans la boucle et d'autres pratiques largement utilisées doivent également y aller.
Nous pouvons remplacer la pile pour les cas suivants:
- Récursivité, implémentée sous la forme de l'extension de l'algorithme de pile dans une boucle avec un bloc de données qui est modifié lors de l'exécution de la boucle.
- Si vous devez transférer des paramètres, vous organiserez un système de micrologiciel avec messagerie. Et à propos de la messagerie, nous allons aux lignes qui ont été décrites dans la première partie de l'article. Si vous voulez vraiment une pile, vous ne devez évidemment pas y pousser des dizaines et des centaines de kilo-octets d'objets, mais vous devez allouer de la mémoire pour cela normalement, sur le tas.
Dans le même temps, au niveau supérieur, les programmeurs peuvent utiliser n'importe quelle structure de données, et c'est aux compilateurs de les transformer de manière à exclure l'utilisation de la pile.
Bien sûr, certaines opportunités seront probablement perdues, mais cela, si on l'examine en détail, n'est pas un fait.
Blocage
En 1995, avec mon camarade de classe, j'ai formulé les principes de la construction d'un système d'exploitation qui excluait ces deux paradigmes.
Les principes étaient les suivants:
- Logiciel - réseaux de processus en interaction.
- L'interaction des processus se fait par l'échange de messages.
- Le réseau de processus en interaction est organisé comme suit: les sources de messages primaires dans un tel réseau ne sont que des événements du monde extérieur fournis par des équipements, les consommateurs finaux de messages ne sont que des appareils qui effectuent des actions dans le monde extérieur. C'est-à-dire que le réseau commence dans le monde réel et s'y termine.
- Les processus ne peuvent pas avoir de priorités. Les priorités ne peuvent avoir qu'un réseau de processus.
- Le réseau ne met jamais les messages en mémoire tampon. Le complexe matériel-logiciel devrait être organisé de manière à pouvoir traiter les messages au rythme de leur réception du monde extérieur.
- Le complexe matériel est un réseau de nœuds informatiques reliés par des canaux de communication.
- Chaque nœud a un «coût», en fonction de sa puissance de traitement, de la taille de la mémoire, de la charge et du facteur de poids, en tenant compte des coûts de sa création et de sa maintenance.
- Chaque canal de communication a un «coût», en fonction de sa bande passante, de son encombrement et de son coefficient de pondération, en tenant compte des coûts de sa création et de sa maintenance.
- Le système d'exploitation permet le lancement de processus en réponse aux messages entrants et au routage des messages.
- Le système d'exploitation assure la distribution des processus et des messages entre les nœuds de calcul, optimisant la fonction f (cpu, mem) sur la topologie du réseau, en tenant compte du coût de transmission du code de processus et des messages au nœud.
- Compte tenu de la construction du système, vous pouvez toujours calculer avec précision la quantité de mémoire requise pour le processus. Le temps de comptage requis peut être calculé avec précision sur la base de l'analyse de l'algorithme.
Processeur BIND
Dans le cadre de sa carrière d'enseignant, avec des étudiants, il a déjà participé au concours d'émulateur de processeur IEEE. Un processeur sans pile polyvalent de l'architecture Harvard a été développé à l'aide d'un système de commande similaire aux ARM précédents. En outre, l'idée oubliée des transporteurs a été intégrée dans le CPU et le processeur était équipé de 16 canaux de réception-transmission de 8 bits.
En conséquence, il n'y a eu aucune opération d'appel / retour dans le processeur. Seule une transition conditionnelle / inconditionnelle était possible. Étant donné que presque personne n'écrit dans l'assembleur en ce moment, toutes les questions sur la génération d'un programme en code machine étaient censées être attribuées au compilateur.
L'objectif principal de ce processeur était de prendre en charge de manière transparente les principes du Blockout OS au niveau matériel en créant un réseau de processeurs dans le nœud informatique local connectés par des canaux de communication sur lesquels les processus seront déjà distribués.
Conclusions
Le texte montre les failles fatales des structures de données de file d'attente et de pile. Les principes de conception de systèmes logiciels et matériels permettant d'exclure ces structures de la pratique de l'application sont donnés.
Ce texte est plutôt une compilation de réflexions qui ont eu lieu tout au long de la carrière en informatique, pour ainsi dire, pour tout ramener en un seul endroit.