Introduction 5

Chapitre 1. Analyse des méthodes et machines d'inférence logique et des systèmes de traitement des connaissances 14

1.1 Méthodes et machines d'inférence logique 14

1.1.1 Classification des types d'inférence logique 14

1.1.2 Classification des méthodes d'inférence 16

1.1.3 Mode de division des articles 19

1.1.4 Machines à inférence 23

1.2 Systèmes de traitement des connaissances (KPS) 25

1.2.1 Définition et structure 25

1.2.2 Classement 29

1.2.3 Modes de fonctionnement 31

1.2.4 Évaluation des performances 33

1.3 Conclusions du chapitre 1 35

Chapitre 2. Développement d'une méthode d'inférence logique de conclusions modifiées 36

2.1 Systèmes formels 36

2.2 Énoncé du problème d'inférence logique 37

2.3 Expansion de la formule de conclusion

2.3.1 Unification des littéraux 39

2.3.2 Coordination des décisions 40

2.3.3 Accord sur les valeurs des variables communes dans les conjonctions de disjointes 43

2.3.4 Division partielle des articles 45

2.3.5 Division complète des articles 47

2.3.6 Procédure de sortie 49

2.3.7 Construire des explications abductives

2.3.8 Méthode d'inférence parallèle avec expansion de la formule d'inférence

2.4 Minimisation de la formule de conclusion 65

2.4.1 Procédure de minimisation des conclusions 65

2.4.2 Méthode de minimisation des conclusions

2.5 Sélection des options de modification 69

2.6 Caractéristiques de l'inférence dans le calcul propositionnel 72

2.7 Exemple de sortie 73

2.8 Conclusions du chapitre 2 77

Chapitre 3. Développement d'un système d'inférence logique pour des conclusions modifiées 80

3.1 Structure du système d'inférence 80

3.1.1 Structure du système généralisé 80

3.1.2 Structure détaillée du système 82

3.2 Modes de fonctionnement du système d'inférence logique 85

3.2.1 Mode de sortie des conclusions modifiées 86

3.2.2 Mode d'inférence déductive 88

3.2.3 Mode d'inférence abductive 88

3.2.4 Mode de réglage 88

3.2.5 Mode d'accès direct aux bases de connaissances 89

3.2.6 Création d'une base de connaissances

3.3 Machine d'inférence logique pour des conclusions modifiées 90

3.4 Langage de programmation de logique déclarative

3.4.1 Structure du programme logique 96

3.4.2 Identifiants et constantes 99

3.4.3 Commentaires 100

3.4.4 Exemple de programme logique 101

3.5 Évaluation de l'efficacité des systèmes d'inférence 102

3.5.1 Critères d'évaluation des performances 102

3.5.2 Calcul du temps d'attente 103

3.5.3 Calcul du degré de modification de la conclusion 108

3.6 Conclusions du chapitre 3 110

Chapitre 4. Application des systèmes d'inférence logique pour les conclusions IZ modifiées

4.1 Demandes 113

4.2 Systèmes d'enseignement intelligents 114

4.3 Systèmes experts 119

4.4 Contrôle intelligent des processus informatiques 121

4.5 Module de sortie logique des conclusions modifiées 1

4.5.1 Caractéristiques générales du logiciel en cours de développement 127

4.5.2 Structure du module de sortie 128

4.5.3 Langage de description de la base de connaissances et des conclusions 129

4.5.4 Implémentation des blocs du module 130

4.6 Programme d'inférence logique « Logika-V » 134

4.6.1 Structure du programme 134

4.6.2 Langage de description des données sources 135

4.6.3 Interface utilisateur 136

4.6.4 Exemple d'utilisation du programme 141

4.7 Conclusions du chapitre 4 149

Conclusion 152

Liste des abréviations 155

Bibliographie 156

Candidatures 1

Introduction au travail

Cette thèse est consacrée au développement d'une nouvelle méthode d'inférence logique de conclusions modifiables sur des connaissances présentées sous forme de formules de calcul propositionnel et de calcul des prédicats de premier ordre, ainsi qu'un système d'inférence logique de conclusions modifiables. Les problèmes liés à la construction de systèmes de traitement des connaissances et de machines d'inférence logique utilisant cette méthode sont examinés, y compris les caractéristiques de leur mise en œuvre logicielle sur des plates-formes informatiques parallèles modernes. Les domaines d'application possibles de cette méthode d'inférence logique sont donnés, l'utilisation de l'inférence logique de conclusions modifiées pour le contrôle intelligent des processus informatiques, dans les systèmes de formation et dans les systèmes experts est envisagée.

Pertinence du sujet de recherche. L’un des domaines prometteurs des systèmes informatiques aujourd’hui est celui des systèmes de traitement des connaissances (KPS). Ils sont déjà répandus (cela est particulièrement vrai pour les systèmes experts (ES)), et à l'avenir ils pourront être utilisés presque partout, augmentant le niveau intellectuel des systèmes informatiques de presque tous types. Cependant, malgré les succès existants, les POP modernes présentent un certain nombre d'inconvénients. En particulier, ils ne sont pas capables de résoudre des problèmes qui nécessitent la présence d’une conclusion fiable alors qu’il existe une conclusion peu fiable. De plus, les POP modernes ne fonctionnent pas efficacement sur des plateformes parallèles.

Contrairement aux données, qui sont des opérandes de tout traitement formalisé et n'ont pas de contenu sémantique du point de vue du système de traitement, les connaissances reflètent certains aspects du monde réel et ont initialement un contenu sémantique. Le meilleur système de traitement des connaissances connu aujourd’hui est le cerveau humain. Cependant, cela présente également certains inconvénients. En particulier, il a de faibles performances dans la résolution de nombreux problèmes, le fonctionnement du cerveau est influencé par de nombreux facteurs et il est sujet aux erreurs. De plus, les conditions environnementales ne permettent souvent pas d'utiliser une personne comme système de traitement des connaissances et de prise de décision. Il est nécessaire de modéliser le comportement humain.

Il existe deux approches principales pour modéliser le comportement de l’intelligence naturelle. Le premier d'entre eux consiste à modéliser le travail d'éléments individuels de la structure cérébrale - les neurones et leurs connexions (approche par réseau neuronal). Son inconvénient caractéristique est la difficulté (souvent impossibilité) de construire une image sémantique du déroulement du raisonnement. La deuxième approche consiste à modéliser les aspects intellectuels du fonctionnement cérébral : le système de concepts (réseau sémantique), le raisonnement, etc. Dans le même temps, la modélisation du raisonnement humain est désormais la plus souvent utilisée, car elle simule des processus de pensée de haut niveau selon certaines règles (par exemple, selon les règles de la logique) et permet de décrire tout simplement les données source et d'interpréter le résultat, ainsi que de suivre la progression de la simulation.

La modélisation du raisonnement à l'aide de la logique est l'un des domaines prioritaires de la science qui étudie les méthodes et moyens de l'intelligence artificielle. Le raisonnement écrit sous la forme de formules de logique des prédicats du premier ordre ou de logique propositionnelle semble tout à fait naturel à l’homme. L'interprétation de la formule est simple et consiste à remplacer les littéraux par des expressions prédéfinies, et les connecteurs par des mots correspondant à leur sens.

La logique propositionnelle est un appareil mathématique assez simple qui n'a pas de très grandes capacités d'expression. Cependant, en raison de la facilité de traitement des formules, la logique propositionnelle est largement utilisée. La logique des prédicats du premier ordre a des capacités d'expression bien plus grandes. Mais le traitement des formules dans le calcul des prédicats est beaucoup plus compliqué, car il nécessite de prendre en compte la dépendance des valeurs des constantes de prédicat sur des ensembles de termes, de coordonner les valeurs des variables sujet et de prendre en compte la possibilité de la présence de constantes fonctionnelles.

La modélisation du raisonnement lui-même s'effectue par inférence logique (LI). Les données initiales pour l'inférence logique sont les formules de prémisses et de conclusion. Les prémisses sont un ensemble de faits et de règles d’inférence et constituent ensemble une base de connaissances. La conclusion est rédigée sous la forme d’une formule logique et vient (en règle générale) de l’extérieur dans le système d’inférence logique. Les procédures d'inférence traitent la conclusion et les prémisses initiales, et le résultat du travail peut être un message sur l'exactitude de la conclusion ou une modification des prémisses initiales.

On distingue généralement les principaux types d'inférence logique suivants : déductive, abductive et inductive. L'inférence déductive est utilisée pour répondre à la question de savoir si une conclusion spécifiée est une conséquence logique des prémisses initiales. L'inférence abductive, si la conclusion ne peut être dérivée des prémisses initiales, permet de compléter l'ensemble des prémisses initiales avec des faits afin que la conclusion devienne déductible. L'inférence inductive, contrairement à l'inférence abductive, permet de compléter l'ensemble des prémisses initiales par des règles générales.

Ces types d’inférence sont connus depuis longtemps et peuvent être utilisés pour résoudre un large éventail de problèmes. Cependant, il existe une classe de problèmes impossibles ou difficiles à résoudre à l’aide de ces types d’inférence. Cette classe de problèmes suppose la présence d'une base de connaissances correcte et complète pour un certain domaine et une conclusion peu fiable qui nécessite une transformation. Par conséquent, une formulation fondamentalement nouvelle du problème de l'inférence logique apparaît : modifier une conclusion initialement non dérivable afin d'en faire une conséquence des prémisses initiales. Ce problème est résolu en utilisant un nouveau type de LP – inférence logique de conclusions modifiées. On peut noter les domaines d'application suivants pour ce type de sortie : - les systèmes de contrôle automatique. L'état de l'objet de contrôle dans un tel système est décrit par une formule de conclusion logique et la plage d'états autorisée est spécifiée sous la forme de formules de prémisses initiales. Si l'état d'un objet est en dehors des limites acceptables, une modification de la conclusion est apportée pour ramener l'objet dans un état acceptable ;

Systèmes de formation corrective. La base des hypothèses initiales contient des connaissances dans un certain domaine. L'étudiant saisit une affirmation dont la véracité est vérifiée (déductibilité des prémisses initiales), et si elle est incorrecte, elle est corrigée ;

Analyse grammaticale des phrases. L'inférence logique de conclusions modifiées peut être utilisée pour restaurer des phrases et construire de nouvelles phrases ;

Systèmes informatiques à architecture dynamique. L'inférence logique de conclusions modifiées peut être utilisée pour répartir des processus informatiques dans des systèmes dont la composition et les connexions de moyens informatiques changent dynamiquement ;

Systèmes experts. Si la conclusion initiale de l'utilisateur est incomplète ou incorrecte, la conclusion logique des conclusions modifiées permettra de clarifier (corriger) la conclusion, et dans certains cas d'indiquer la nécessité d'étudier des signes supplémentaires.

Il existe un assez grand nombre de méthodes d’inférence logique. Le principal inconvénient d'une partie importante d'entre eux est le principe cohérent du traitement des connaissances. Cela réduit considérablement les performances des systèmes d’inférence utilisant ces méthodes. À cet égard, les méthodes d'inférence logique parallèle basées sur la procédure de division des propositions méritent attention. Chaque étape d’une telle production peut impliquer un certain nombre d’opérations, dont la plupart peuvent être effectuées en parallèle. Ceci est particulièrement pertinent à l'heure actuelle, car désormais, dans la plupart des cas, les performances des ordinateurs sont augmentées non seulement et non pas tant en améliorant l'architecture et la microarchitecture des processeurs, en augmentant les fréquences d'horloge, mais en augmentant le nombre d'éléments de processeur (processeurs et cœurs). .

Ainsi, la tâche urgente est de développer une méthode et un système d'inférence logique parallèle de conclusions modifiées sur les connaissances présentées sous la forme de formules de calcul propositionnel et de calcul des prédicats de premier ordre, qui élargiront la classe de problèmes résolus par SOZ, construits sur la base d'un système d'inférence logique, et augmenter leur vitesse de travail.

Des contributions significatives au développement et à la recherche de méthodes et de moyens d'inférence logique ont été apportées par M. L. Tsetlin, M. M. Bongard, Ya. Z. Tsypkin, D. A. Pospelov, V. K. Finn, G. S. Osipov, V. N. Vagin, T. A. Gavrilova, V. F. Khoroshevsky, P. Gaek, T. Gavranek, S. Osuga, U. Saeki, A. Samuel, E. Hunt, J. Marin, P. Stone, R. Michalski, J. Carbonell, T. Mitchell, T. Mitchell), D. Quinlan. Abductive LE a été étudié dans les travaux de C. S. Pierce, V. K. Finn, V. N. Vagin, E. Yu. Strabykin, M. L. Dolzhenkova, D. D. Gabbay, P. Smets, C. Boutilier, P. Flach, A. Kakas. , K. Inoue ), C. Sakama, J. Josephson, S. Mcllraith, G. Paul et autres.

Le but de l'étude est de développer une méthode d'inférence logique parallèle de conclusions modifiées pour le calcul des énoncés et le calcul des prédicats de premier ordre et de construire sur sa base un système et une machine LP de conclusions modifiées. Pour atteindre l'objectif, il est nécessaire de résoudre les tâches suivantes.

1. Développer une méthode de dérivation logique parallèle de conclusions modifiées pour le calcul des énoncés et le calcul des prédicats de premier ordre, qui permet de modifier une conclusion non dérivable et d'en faire une conséquence des prémisses initiales.

2. Développer une machine pour l'inférence logique parallèle de conclusions modifiées.

3. Développer un système d'inférence logique parallèle basé sur une machine d'inférence logique pour des conclusions modifiées.

4. Développer des critères pour évaluer l'efficacité du système et de la machine pour l'inférence logique parallèle de conclusions modifiées.

Méthodes de recherche. Pour atteindre l'objectif de recherche fixé dans le travail, des méthodes d'analyse algorithmique, de théorie des ensembles, de théorie des graphes, de logique mathématique, de théorie de l'inférence, de programmation logique et orientée objet ont été utilisées.

La nouveauté scientifique de l’étude est la suivante.

1. Une méthode a été développée pour l'inférence logique parallèle de conclusions modifiées pour la logique propositionnelle et la logique des prédicats du premier ordre, qui diffère des méthodes connues en ce que les prémisses supplémentaires suivantes sont appliquées aux prémisses supplémentaires obtenues à la suite de l'inférence abductive : procédure de transformation spéciale qui permet de construire à partir d'elles les ajouts des disjointes de la conclusion, une méthode de minimisation de la conclusion, ainsi qu'un algorithme parallèle pour évaluer les options de modification de la conclusion. Cela permet de transformer une conclusion non déductible afin d'en faire une conséquence des prémisses initiales.

2. Une méthode de minimisation de l'inférence a été développée pour le calcul propositionnel et le calcul des prédicats de premier ordre, qui diffère des méthodes d'inférence connues en ce qu'elle utilise une recherche parallèle dans un arbre de décision en coupant une partie des branches pour trouver des solutions. Dans le même temps, les littéraux qui ne sont pas impliqués dans le processus d'inférence sont supprimés des clauses de conclusion, augmentant ainsi l'efficacité du système d'inférence logique pour les conclusions modifiées.

3. Un algorithme parallèle a été développé pour évaluer et sélectionner des options de modification des clauses de la conclusion, caractérisé en ce que chaque clause se voit attribuer une certaine valeur numérique obtenue en appliquant une fonction d'évaluation spéciale à la clause. Cela vous permet de sélectionner les meilleures parmi l'ensemble des options permettant de modifier les disjonctions d'origine conformément à la fonction d'évaluation des disjonctions sélectionnée.

4. Des critères et des méthodes ont été développés pour évaluer l'efficacité du système et de la machine d'inférence logique de conclusions modifiées, en tenant compte des caractéristiques de l'inférence logique en divisant les clauses, du degré de parallélisme sélectionné, de l'architecture de l'ordinateur, des types de modification de la conclusion, qui permet d'estimer le temps passé sur l'inférence logique et le degré de modification de la conclusion.

La valeur pratique de l'étude est la suivante :

1. Un système d'inférence parallèle et logique de conclusions modifiées a été développé, dont les caractéristiques distinctives sont : l'utilisation de méthodes et de machines LP parallèles, l'utilisation d'une base de connaissances à deux niveaux, la présence d'un bloc d'interprétation de formule, ce qui permet de construire des POP hautes performances à diverses fins sur la base du système d'inférence logique développé. Le processus d'inférence peut être parallélisé jusqu'au niveau des opérations d'unification littérale, ce qui augmente la vitesse d'inférence logique sur les plates-formes informatiques parallèles.

2. Un langage de programmation logique déclaratif a été développé qui permet de décrire des connaissances à l'aide de formules de calcul propositionnel et de calcul de prédicats de premier ordre, d'utiliser des foncteurs et d'assumer la capacité d'interpréter des formules logiques en langage naturel.

3. Un programme de formation à l'inférence logique a été développé dont les particularités sont : la mise en œuvre de plusieurs types d'inférence logique en divisant les clauses de calcul des énoncés, y compris l'inférence logique de conclusions modifiées, la présence d'un mécanisme de conversion de formules en plusieurs clauses, interprétation des formules en langage naturel, sortie d'un rapport d'avancement détaillé. Les caractéristiques du système permettent de l'utiliser pour étudier les types et les méthodes d'inférence logique.

4. Des recommandations ont été élaborées pour l'utilisation de la méthode et du système d'inférence logique parallèle de conclusions modifiées pour le contrôle intelligent des processus informatiques, dans les systèmes d'enseignement intelligents et dans les systèmes experts.

Sont soumis à la défense :

1. Une méthode d'inférence logique parallèle de conclusions modifiées pour la logique propositionnelle et la logique des prédicats de premier ordre, qui permet de transformer une conclusion non dérivable afin d'en faire une conséquence des prémisses initiales.

2. Une méthode de minimisation d'inférence pour le calcul propositionnel et le calcul des prédicats de premier ordre, qui vous permet de supprimer les littéraux qui ne sont pas impliqués dans le processus d'inférence, augmentant ainsi l'efficacité du système d'inférence.

3. Un algorithme parallèle d'évaluation et de sélection des options de modification des clauses de la conclusion, qui vous permet de sélectionner les meilleures parmi l'ensemble des options de modification des clauses d'origine conformément à la règle sélectionnée pour trouver des solutions optimales.

4. Critères et méthodes d'évaluation de l'efficacité du système et de la machine d'inférence logique de conclusions modifiées, en tenant compte des caractéristiques de l'inférence logique par division de clauses, du degré de parallélisme sélectionné, de l'architecture informatique, des types de modification de la conclusion.

5. Un système parallèle d'inférence logique de conclusions modifiées basé sur une machine d'inférence logique parallèle, capable d'effectuer des types d'inférence logique de base, ainsi que l'inférence logique de conclusions modifiées. Mise en œuvre des résultats de la recherche. Les résultats théoriques et pratiques obtenus ont été utilisés dans le travail de recherche « Théorie et application de l'inférence logique avec modification des conclusions » (subvention du ministère de l'Éducation de la Fédération de Russie E02-2.0-93), dans le travail de recherche « Développement d'un environnement de programmation logique déclarative pour un système informatique en cluster » (Vyatka State University, travail de recherche n° 412) . Le programme d'études sur l'inférence logique a été introduit dans le processus éducatif des universités humanitaires de l'État de Viatka et de l'État de Viatka.

Approbation des travaux. Les principales dispositions et résultats de l'étude ont été rapportés et discutés lors de la 5ème conférence internationale « Les systèmes interactifs : les problèmes de l'interaction homme-machine », Oulianovsk, Université technique d'État d'Oulianovsk, 2003 ; 9e « Conférence nationale sur l'intelligence artificielle KII-2004 », Tver, 2004 ; Conférence scientifique et technique annuelle panrusse de l'Université d'État de Viatka « Science-production-technologie-écologie », Kirov (2004,2007,2008)

Méthodes d'inférence et de recherche de solutions dans les systèmes de production.

Méthodes d'inférence basées sur le chaînage avant et arrière.

Dans la représentation de la production, un domaine de connaissances est représenté par un ensemble de règles de production si-alors, et les données sont représentées par un ensemble de faits sur la situation actuelle.

Le moteur d'inférence compare chaque règle stockée dans la base de données avec les faits contenus dans la base de données. Lorsque la partie if de la règle (condition) correspond au fait, la règle est déclenchée et sa partie then (action) effectué. Une règle déclenchée peut modifier de nombreux faits en ajoutant un nouveau fait, comme le montre la figure 6.1. Les lettres en DB et KB sont utilisées pour représenter des situations et des concepts.

Figure 6.1. Cycle du mécanisme d'inférence à travers la procédure de tir d'allumette

La comparaison des parties si les règles avec les faits crée chaîne de sortie. La chaîne d'inférence montre comment l'ES applique les règles pour obtenir une conclusion. Pour illustrer la méthode d’inférence basée sur la chaîne, considérons un exemple simple.

Disons que la base de données comprend initialement les faits A, B, C, D et E, et que la base de connaissances ne contient que trois règles :

Règle 1. Y&D → Z

Règle 2. X&B&E→Y

Règle 3. A → X

La chaîne de sortie de la Fig. 6.2. montre comment l'ES applique des règles pour dériver le fait Z.

Figure 6.2. Exemple de chaîne de sortie.

Premièrement, la règle 3 est exécutée pour dériver un nouveau fait X à partir du fait publié A. Ensuite, la règle 2 est exécutée pour dériver le fait Y à partir des faits initialement connus B et E, ainsi que du fait X déjà connu. Enfin, la règle 1 s'applique le fait initialement connu D et le fait nouvellement obtenu Y pour l'arrivée et la conclusion Z.

Le SE peut refléter sa chaîne d’inférence pour expliquer comment une décision particulière a été prise ; c'est une partie importante de ses pouvoirs explicatifs.

Le moteur d'inférence doit décider quand les règles doivent se déclencher. Il existe deux manières principales de mettre en œuvre les règles. L’une est appelée chaîne directe (déduite conditionnellement) et l’autre est appelée chaîne inverse (déduite par cible).

Cet exemple utilise le chaînage de sortie directe.

Les systèmes de production dans lesquels la partie antécédente (les conditions) sont d'abord analysées ont une architecture dite inférentielle conditionnelle. Un exemple de système expert d'une telle architecture est META-DENDRAL.

Un autre type d'architecture qui est assez souvent utilisé dans les systèmes experts est celui des systèmes de production à inférence de but (inférence d'action ou d'inférence conséquente). Par exemple, une règle comme

peut être interprété comme

"La conjonction logique de A, B et C implique D" ou

« Pour prouver D, il faut établir A, B, C. »

Dans ce dernier cas, l’objectif doit être atteint par inférence déductive. Pour ce faire, les conséquences des règles sont examinées pour trouver une règle qui permettrait d’atteindre l’objectif. Lorsqu’une telle règle est trouvée, toutes ses conditions sont vérifiées. Si les conditions sont vraies, la sortie est activée. Sinon, la recherche de produits adaptés se poursuit.

Regardons un exemple simplifié d'un système de production avec une architecture inférentielle conséquente. Les lettres ici indiquent les éléments de la base de données et elles sont considérées comme vraies si elles y sont contenues.

Règle 1 : A&B&C→D

Règle 2 : D&F→G

Règle 3 : A&J→G

Règle 4 : B→C

Règle 5 : F→B

Règle 6 : L → J

Règle 7 : G→H

Supposons que le but soit de déduire la vérité de H. La première étape consiste à vérifier si H est dans la base de données ? Puisque ce n’est pas le cas dans ce cas, le système tente de déduire la vérité de H en utilisant des règles qui ont H du côté droit. C'est la règle 7. Maintenant le système essaie de déduire la vérité de G, puisque la vérité de cette dernière entraîne la vérité de H. La base de données est à nouveau vérifiée : il n'y a pas de G dans la base de données, donc un pôle de la règle contenant G sur le côté droit est organisé. Il existe plusieurs règles de ce type (deux ou trois). En tant que stratégie de « résolution de conflits », nous supposerons que les règles sont classées par priorité, la règle avec le numéro le plus bas correspondant à la priorité la plus élevée.

Dans ce cas, la règle 2 est choisie, le but devient donc maintenant de déduire la vérité de D et F. Pour cela, il suffit de montrer que A est vrai (puisqu'il est dans la base de données), B est vrai (selon à la règle 5), C est vrai (selon la règle 4 ). Puisque la vérité de D et F est prouvée, alors la vérité de G découle de la règle 2, et la vérité de H découle de la vérité de G (règle 7). L'objectif a donc été atteint. Les éléments avérés sont ajoutés à la base de données. Dans ce cas, il s'agit des éléments H, G, D, C.V. Des exemples d'architecture d'inférence cible sont MYCIN.

Inférence sur les frames et les réseaux sémantiques.

Sortie sur images.

Structure de données de trame.

Avant de discuter de la sortie dans un système de trames, examinons de plus près la structure des données de trame.

Un système de trames est une structure hiérarchique dont les nœuds sont des trames avec une certaine structure de données.

1. Nom du cadre. Il s'agit de l'identifiant attribué à la trame. Le cadre doit avoir un nom unique dans un système de cadres donné (nom unique). Chaque trame se compose d'un nombre arbitraire d'emplacements, dont quelques-uns sont généralement définis par le système lui-même pour exécuter des fonctions spécifiques, et le reste est défini par l'utilisateur. Ceux-ci incluent un emplacement affichant le cadre - le parent de ce cadre ; un emplacement de pointeur de trame enfant, qui est une liste de pointeurs de trame enfant ; emplacement pour saisir le nom d'utilisateur, la date de définition, la date de modification, le taux de commentaires et d'autres emplacements. Chaque emplacement, à son tour, est également représenté par une structure de données spécifique.

2. Nom de l'emplacement. Il s'agit de l'identifiant attribué au slot ; un slot doit avoir un nom unique dans le frame auquel il appartient. Habituellement, le nom de l'emplacement n'a aucune signification et n'est qu'un identifiant pour cet emplacement, mais dans certains cas, il peut avoir une signification spécifique. Ces noms incluent : l'attitude ; pointeur de cadre enfant direct ; date de définition du cadre ; date de modification du cadre, etc.

3. Pointeurs d'héritage. Ces pointeurs concernent uniquement les systèmes de cadres de types hiérarchiques basés sur des relations de types hiérarchiques basées sur des relations abstraites-concrètes. Ils montrent quelles informations d'attribut sur les emplacements dans un cadre de niveau supérieur sont héritées par les emplacements portant les mêmes noms dans un cadre de niveau inférieur.

4. Indicateur du type de données (attributs du slot). Indique que l'emplacement a une valeur numérique, une valeur numérique ou sert de pointeur vers une autre image (c'est-à-dire qu'il affiche le nom de l'image). Les types de données incluent un pointeur, un entier, un réel, un booléen, une procédure jointe, un texte, une liste, un tableau, une expression, etc.

5. Valeur de l'emplacement. La valeur de l'emplacement est saisie ici. La valeur d'un emplacement doit correspondre au type de données spécifié de cet emplacement et la condition d'héritage doit également être remplie.

6. Procédure - démon. Il existe les types de procédures suivants - démons : si nécessaire, si modifié, si ajouté, si supprimé.

Un démon spécifie une procédure qui est automatiquement lancée lorsqu'une certaine condition est remplie. Ceux. lorsque l'attribut dans la partie conditionnelle de l'instruction if concernant l'état du démon change de valeur. Procédures - Les démons sont activés chaque fois qu'une tentative est faite pour ajouter ou supprimer des données d'un emplacement (par défaut). Les démons sont démarrés lors de l'accès à l'emplacement correspondant. Par exemple, le démon if-necessary est lancé si sa valeur n'était pas définie au moment de l'accès à l'emplacement ; if-added est déclenché lorsqu'une valeur est remplacée dans l'emplacement ; if-remote est exécuté lorsque la valeur de l'emplacement est effacée. De plus, un démon est un type de procédure attachée.

7. Procédure ci-jointe (procédure – préposé). Vous pouvez utiliser un programme de type procédural appelé valeur d'emplacement comme officiel(en langage LISP) et méthode(en langage Smalltalk). Dans ce cas, la procédure attachée est déclenchée par un message transmis depuis une autre trame, ou lorsque les conditions spécifiées par l'utilisateur lors de la création de la trame sont remplies.

Lorsque nous disons que les modèles de représentation des connaissances par frames combinent connaissances procédurales et déclaratives, nous considérons également les procédures qui y sont attachées comme des valeurs procédurales. De plus, le langage de représentation des connaissances avec frames ne dispose pas de mécanisme spécial de contrôle de sortie, l'utilisateur doit donc implémenter ce mécanisme à l'aide d'une procédure jointe.

Sortie dans un système de trame.

Dans le cadre de l'approche cadre, on suppose que les connaissances dans le système sont présentées sous la forme de groupes de connaissances distincts, ou sous-structures, contenant des informations sur les stéréotypes (c'est-à-dire sur certaines caractéristiques générales d'une classe donnée d'objets ou de situations. Selon Selon cette hypothèse, comprendre la situation du système signifie rechercher dans la liste les structures accumulées qui décrivent le mieux la situation considérée. Dans ce cas, les emplacements sont remplis avec certaines informations et la trame remplie est vérifiée pour son adéquation à la situation donnée. . En cas de non-concordance, une nouvelle trame est recherchée et le processus continue.

Ainsi, nous pouvons distinguer trois processus principaux se produisant dans les systèmes de trame :

1. Créez une instance de frame. Pour créer une instance d'un cadre, vous devez trouver un cadre approprié et remplir ses emplacements avec des informations décrivant les spécificités de la situation considérée. Afin de remplir les créneaux, des informations spéciales sont utilisées sur la façon de trouver des « remplisseurs » potentiels des créneaux. Ces informations sont souvent stockées sous forme procédurale.

2. Activation des cadres. Lorsqu’un cadre est jugé approprié pour décrire une situation donnée, il est activé par un processus global. Si trop de différences entre le contenu des trames et les spécificités de la situation considérée sont détectées ou si elles sont d'un caractère suffisamment grave, une recherche d'une autre trame plus adaptée est organisée. Dans ce cas, la trame « rejetée » peut contenir des indications sur les trames à étudier à la place de celle-ci (par exemple, des trames plus générales ou, à l'inverse, des trames plus spécialisées). Certaines des données utilisées pour remplir les cases de la catégorie « rejetés » peuvent être utilisées lors de l'examen de nouveaux candidats.

3. Organisation de l'inférence, qui consiste en une recherche séquentielle d'activation dans le réseau de trames jusqu'à ce que la plus appropriée soit trouvée et qu'une instance de trame soit construite sur sa base.

T. Winograd a proposé de combiner les avantages de la représentation déclarative et procédurale dans des frames. L'essence de sa proposition est que les connaissances concernant les fonctions de représentation directe à l'aide de cadres devraient être stockées sous forme déclarative, et les connaissances sur l'utilisation des cadres - sous forme procédurale.

Les procédures peuvent notamment stocker des connaissances qui leur permettent de répondre aux questions suivantes :

1. Quand activer le cadre ? Comme les « démons », les cadres peuvent s'activer si la situation appropriée est reconnue.

3. Quand les créneaux horaires doivent-ils être pourvus : au moment de l'appel ou plus tard, selon les besoins ?

La mise en œuvre de ces fonctions peut être affectée aux procédures annexées. Les procédures peuvent également mettre en œuvre des heuristiques visant à trouver les informations nécessaires pour remplir les créneaux.

Incertitude.

L’une des caractéristiques communes de l’information dont dispose le décideur est son imperfection. Les informations peuvent être incomplètes, incohérentes, incertaines, peu fiables, peu claires, aléatoires ou diverses combinaisons de ces descriptions. En d’autres termes, les informations ne sont souvent pas entièrement adaptées à la résolution du problème. Cependant, l’expert surmonte ces lacunes et peut généralement prendre de bonnes décisions et prendre de bonnes décisions. Un DSS intelligent doit également être capable de faire face à l’incertitude et de parvenir à des conclusions raisonnables.

Fondamentalement, quatre sources de connaissances incertaines en matière de DSS intelligent sont identifiées : les données inconnues, le langage imprécis, le contenu sémantique implicite et les difficultés liées à la combinaison des points de vue de différents experts.

Bien que l’incertitude soit répandue dans le monde réel, sa prise en compte dans les systèmes d’IA pratiques est assez limitée.

L'incertitude est un problème sérieux. Tenter d'éviter d'en tenir compte et de réaliser les possibilités de travailler avec lui ne peut pas être la meilleure stratégie lors du développement de DSS intelligents.

Il est donc nécessaire d’améliorer les méthodes permettant de gérer l’incertitude.

Les DSS et ES intelligents doivent être capables de gérer l'incertitude, car Tout domaine du monde réel contient des connaissances inexactes et vous devez faire face à des données incomplètes, contradictoires ou même manquantes. Diverses méthodes ont été développées pour gérer l'incertitude dans les systèmes intelligents et experts. Nous considérerons les approches les plus connues de la gestion de l'incertitude : le raisonnement probabiliste bayésien et ses extensions, la théorie de la certitude, la logique floue.

Inférence probabiliste.

Approche probabiliste.

L'incertitude aléatoire (ou probabiliste) peut être associée au caractère aléatoire d'événements, par exemple aux situations économiques, aux conditions des objets, à la nature aléatoire des pannes d'équipement et à d'autres facteurs. Lors de la conception de DSS intelligents et de l'organisation du travail avec des bases de connaissances, le niveau de fiabilité et de fiabilité de nombreuses connaissances, faits, événements et données varie. Pour formaliser le raisonnement dans des conditions d'incertitude stochastique, la théorie des probabilités et des solutions statiques sont utilisées. Lors de la mise en œuvre d'un raisonnement prenant en compte l'incertitude pour calculer la probabilité d'une certaine hypothèse pour une option de solution, il est possible d'utiliser Approche bayésienne.

Considérons les principales dispositions de la méthode bayésienne et de la règle de Bayes.

Laisser UN est un événement dans la réalité, et DANS- un autre événement. Supposons que les événements UN Et DANS ne s’excluent pas mutuellement, mais surviennent de manière conditionnelle lorsque l’autre se manifeste. La probabilité que l'événement UN se produira si l'événement se produit DANS, appelé probabilité conditionnelle.

La probabilité conditionnelle est mathématiquement notée PENNSYLVANIE|B), dans lequel la barre verticale représente « s'est produit » et l'expression de probabilité complète est interprétée comme « La probabilité conditionnelle que l'événement se produise UN DANS».

Pennsylvanie|B)=(6.1)

Nombre de manifestations articulaires possibles UN Et DANS, ou la probabilité que UN Et DANS se passera ensemble, appelé probabilité conjointe A Et DANS.

Mathématiquement, cela apparaît P(ACB).

Nombre de manifestations possibles DANS est la probabilité DANS, P(B), et puis

(6.2)

En outre, la probabilité conditionnelle qu'un événement se produise DANSà condition que l'événement ait eu lieu UN déterminé

(6.3)

p(BÇA) =p(B|A)´p(A)(6.4)

La probabilité conjointe est commutative, donc

p(AÇB)= p(BÇA)

Ainsi

p(AÇB) =p(B|A)´P(A)(6.5)

La substitution de (6.5) dans (6.2) conduit à l’équation suivante :

(6.6)

p(UNE|B) UNà condition que l'événement ait eu lieu DANS;

p(B|UNE)– probabilité conditionnelle qu’un événement se produise DANSà condition que l'événement ait eu lieu UN;

Pennsylvanie) UN;

p(B)- la probabilité qu'un événement se produise DANS.

L'équation (6.6) est connue sous le nom de règle (ou formule) de Bayes, qui doit son nom à Thomas Bayes, le mathématicien britannique du XVIIIe siècle qui a proposé cette règle.

La notion de probabilité conditionnelle est proposée lorsqu'on estime qu'un événement UN dépendait de l'événement DANS. Ce principe peut être étendu au cas où l'événement UN dépend d'un certain nombre d'événements incompatibles B 1, B 2, ..., Bn.

L’ensemble d’équations suivant peut être dérivé de (6.2) :

p(AÇB 1) =p(A|B 1)´p(B 1)

p(AÇB 2) =p(A|B 2)´p(B 2)

p(АÇВ n) =p(А|В n)´p(В n)

Ou après la fusion.

(6.7)

Si (6.7) est additionné sur toute la liste complète des événements B i , nous obtenons

(6.8)

Cela conduit à l’équation de probabilité conditionnelle suivante, c’est-à-dire PENNSYLVANIE) exprimé à l'aide de la formule de probabilité totale :

(6.9)

Si la manifestation d'un événement UN ne dépend que de deux événements mutuellement exclusifs, par exemple DANS Et PAS DANS, alors (6.9) ressemblera à ceci :

p(A)=p(A|B)´p(B)+p(A\ØB)´p(ØB) (6.10)

Où Ø est NON logique.

p(B)=p(B|A)´p(A)+p(B\ØA)´p(ØA) (6.11)

Remplaçons maintenant (6.11) dans la formule de Bayes (6.6), ce qui conduit à

L'équation (6.12) fournit la base de l'utilisation de la théorie des probabilités pour gérer l'incertitude dans les systèmes intelligents.

Inférence bayésienne.

En utilisant l’équation (6.12), nous pouvons maintenant détourner notre attention de la théorie des probabilités vers les systèmes intelligents. Supposons que toutes les règles de la base de connaissances soient présentées sous la forme suivante :

Si N vrai

Alors AVEC vrai (avec probabilité r}.

Cette règle implique que si un événement N se produit, alors la probabilité que l'événement AVEC cela arrivera r.

Que se passe-t-il si l'événement AVEC s'est produit, mais nous ne savons pas si l'événement s'est produit N? Considérons la possibilité de calculer la probabilité qu'un événement N s'est également produit.

L’équation (6.12) nous permet de le faire. Nous utilisons simplement N Et AVEC au lieu de UN Et DANS. Dans les systèmes intelligents N désigne généralement des hypothèses, et AVEC– des preuves pour étayer ces hypothèses.

Ainsi, l’équation (6.12), exprimée en termes d’hypothèses et de preuves, ressemble à ceci

p(H) – probabilité a priori (inconditionnelle) que l'hypothèse N est vrai ;

p(C|H)– la probabilité que l'hypothèse N est vrai, ce sera le résultat de preuves AVEC;

p(ØН)- probabilité a priori (inconditionnelle) que l'hypothèse N est faux ;

p(С|ØН)– probabilité de trouver des preuves AVEC même lorsque l'hypothèse N FAUX.

L'équation (6.13) suggère que la probabilité d'une hypothèse N, p(H) doit être déterminé avant l’examen de toute preuve.

Dans le DSS intelligent, des probabilités sont nécessaires pour résoudre les problèmes posés par les experts. L'expert détermine les probabilités a priori d'une hypothèse possible p(H) Et p(ØН), ainsi que les probabilités conditionnelles pour les preuves observées AVEC, si l'hypothèse N vrai, p(C|H), et si l'hypothèse N FAUX p(С|ØН). Les utilisateurs fournissent des informations sur les preuves observées et le système intelligent calcule p(C|H) pour une hypothèse N au vu des éléments de preuve fournis par l'utilisateur AVEC. Probabilité p(C|H) appelé probabilité a posteriori hypothèses N avec des preuves observables AVEC.

Considérons des situations où un expert, sur la base de preuves simples AVEC, ne peut pas sélectionner une hypothèse simple, mais propose plutôt plusieurs hypothèses N 1, N 2,…, Nt. Ou quand il existe de nombreuses preuves C 1, C 2, …, C n et l'expert génère également de nombreuses hypothèses.

On peut généraliser l'équation (6.13) en tenant compte de nombreuses hypothèses N 1, N 2, …, Nt et de nombreux témoignages C 1, C 2, …, C n. Mais les hypothèses, tout comme les preuves, doivent s’exclure mutuellement.

Pour des preuves simples C et des hypothèses multiples N 1, N 2, …, Nt suit :

(6.14)

Pour de nombreuses preuves C 1, C 2, …, C n et de nombreuses hypothèses N 1, N 2, …, Nt suit :

(6.15)

L'application de l'équation (6.15) nécessite d'obtenir les probabilités conditionnelles de toutes les combinaisons possibles de preuves pour toutes les hypothèses. Cette exigence impose une charge énorme à l'expert et rend sa tâche presque impossible.

Par conséquent, dans les DSS et ES intelligents, les subtilités de l’influence conjointe de plusieurs preuves ne doivent pas être prises en compte, mais une indépendance conditionnelle entre diverses preuves doit être autorisée.

Par conséquent, au lieu de l’équation irréalisable (6.15), nous obtenons

Pour clarifier comment un système intelligent calcule toutes les probabilités a posteriori et classe finalement une hypothèse potentiellement vraie, prenons un exemple simple.

Supposons qu'un expert, disposant de trois éléments de preuve conditionnellement indépendants C1, C2 Et C3, crée trois hypothèses mutuellement exclusives N 1, N 2 Et N 3 et fournit des probabilités a priori pour ces hypothèses – p(H1), p(H2) Et p(H 3) respectivement. L'expert détermine également les probabilités conditionnelles de chaque élément de preuve noté pour toutes les hypothèses possibles.

Dans le tableau 6.1. Les probabilités a priori et conditionnelles fournies par l'expert sont présentées.

Tableau 6.1.

Probabilités a priori et conditionnelles.

Disons que nous observons d'abord la preuve C 3 . Le système intelligent calcule les probabilités a posteriori pour toutes les hypothèses à l'aide de l'équation (6.14) :

Ainsi

Comme on peut le constater, après avoir observé les preuves C3, confiance dans l'hypothèse H2 et devient égal à la confiance dans l'hypothèse H1. La confiance dans l'hypothèse H 3 augmente également et atteint même approximativement la confiance dans les hypothèses H1 Et H2.

Supposons maintenant que nous observions des preuves C1. Les probabilités a posteriori sont calculées à l'aide de l'équation (6.16) :

Ainsi

Hypothèse H2 est désormais considérée comme la plus probable, car la confiance dans l’hypothèse diminue fortement.

Après avoir vu les preuves C2 Smart DSS calcule également les dernières probabilités a posteriori pour toutes les hypothèses :

Ainsi

Même si le classement initial proposé par l'expert était H1, H2 et H3, seulement des hypothèses H1 Et N 3 restait à examiner après toutes les preuves ( C1, C2 Et C3) qui ont été observés. Hypothèse H2 peut maintenant être complètement éliminé.

Notez que l'hypothèse N 3 désormais considéré comme préférable à l'hypothèse H1.

Lors de l'utilisation de méthodes basées sur la logique bayésienne, des difficultés surviennent pour obtenir le grand nombre de données nécessaires pour déterminer les probabilités conditionnelles.

En pratique, on fait une hypothèse sur l’indépendance des observations, ce qui semble affecter la rigueur du modèle statique. Des hypothèses similaires sont présentes dans la méthode basée sur l’approche bayésienne proposée dans.

Duda, Hart et Nielson ont modifié les formules de Bayes pour l'inférence d'ingénierie des connaissances et ont proposé une méthode d'inférence appelée sujet Bayes.

Les principaux objectifs de cette méthode ont été mis en œuvre avec succès par eux dans le système expert PROSPECTOR.

Raisonnement approximatif.

Dans la théorie classique du calcul propositionnel, l'expression « Si UN, Alors DANS", Où UN Et DANS– variables propositionnelles (une variable propositionnelle est une variable pour des phrases considérées uniquement en fonction de leur vérité ou de leur fausseté), écrites sous la forme A®B, où l'implication (®) est considérée comme un connecteur dont le sens est déterminé par la table de vérité.

Ainsi А®ВºØАВ (6.17)

Dans le sens où A®B(A implique B) et ØÀÚВ(pas A ou B) ont des tables de vérité identiques. Le plus important dans notre cas est déclaration vague"Si UN, Alors DANS", brièvement A®B, dans lequel UN(antécédent) et DANS(conséquent) – ensembles flous, pas de variables propositionnelles (« proposition » signifie phrase, expression, énoncé).

Exemples typiques de déclarations :

Si "grand" Alors "petit"

Si « glissant », alors « dangereux » ;

Ce sont des abréviations de phrases :

Si x est « grand », alors y est « petit » ;

Si la route est « glissante », alors la conduite est « dangereuse ».

Essentiellement, les phrases de ce type décrivent une relation entre deux variables non définies. Cela signifie qu'un énoncé indéfini doit être défini comme une relation floue au sens de (5.25), plutôt que comme un connecteur au sens de (6.17).

Ici, il est conseillé de déterminer d'abord produit cartésien deux ensembles flous.

Laisser UN-sous-ensemble flou du domaine du raisonnement U et laisse DANS est un sous-ensemble flou d'un autre domaine de raisonnement V. Alors le produit cartésien UN Et DANS, noté А´В, est défini comme suit

(6.18)

Où UV signifie produit cartésien d'ensembles U Et V, c'est-à-dire

Notez que lorsque UN Et DANS– non flou, (6.18) se transforme en la définition habituelle d’un produit cartésien d’ensembles.

En d’autres termes, (6.18) signifie que А´В ensemble flou de paires ordonnées ( toi, v), , avec degré d'appartenance (u,v)À (A'B), donné par la formule. En ce sens А´В il y a une relation peu claire U Et V.

Exemple 6.1. Laisser

U=1+2(6.19)

V=1+2+3 (6.20)

A=1/1+0,8/2 (6.21)

B=0,6/1+0,9/2+1/3 (6.22)

A´B=0,6/(1,1)+0,9/(1,2)+1/(1,3)+0,6/(2,1)+0,8/(2,2 )+0,8/(2,3) (6.23)

La relation définie en (6.17) peut être représentée par la matrice de relation

La signification d'une déclaration floue de la forme « Si UN, Alors DANS" devient clair si on le considère comme un cas particulier de l'énoncé conditionnel " Si UN, Alors DANS, Sinon AVEC", Où UN, DANS Et AVEC– sous-ensembles flous, éventuellement de zones différentes U Et V, respectivement.

En termes de produit cartésien, la dernière phrase est définie comme suit :

Si UN, Alors DANS, Sinon AVEC (6.25)

Où + signifie l'union d'ensembles flous А´В Et (ØА´С).

Pour généraliser le concept d'implication matérielle aux ensembles flous, supposons que U Et V– deux ensembles universels éventuellement différents, et A, B Et AVEC– sous-ensembles flous d’ensembles U, V Et V respectivement.

Tout d'abord, déterminons le sens de la déclaration

Si UN, Alors DANS, Sinon AVEC, puis nous définissons

Si UN, Alors DANS comme cas particulier de l'énoncé Si UN, Alors DANS, Sinon AVEC.

Définition. Déclaration si UN, Alors DANS, Sinon AVEC il existe une relation floue binaire dans UV, défini comme suit :

Si A, alors B, sinon C=A´B+ØA´C (6.26)

Autrement dit, si A, B Et AVEC– relations floues unaires dans U, V Et V, alors si UN, Alors DANS, Sinon AVEC– relation floue binaire dans UV, qui est l'union du produit cartésien UN Et DANS(voir (5.23)) et le produit cartésien de négation UN Et AVEC.

Instruction suivante Si UN, Alors DANS peut être considéré comme un cas particulier de l'énoncé Si UN, Alors DANS, Sinon Avec l'hypothèse Quoi AVEC– ensemble complet V.

Que. Si UN, Alors DANS Si UN, Alors DANS, Sinon V=А´В+ØА´V(6.27)

En substance, cela équivaut à l’interprétation de l’énoncé Si UN, Alors DANS déclaration Si UN, Alors DANS, Sinon indifférent.

Exemple 6.2. Illustrations (6.26) et (6.27)

Supposons que

A=petit=1/1+0,4/2

B=grand=0,4/2+1/3

C=pas grand=1/1+0,6/2

Alors si UN, Alors DANS, Sinon С=(1/1+0,4/2)´(0,4/2+1/3)+(0,6/2+1/3)´ (1/1+0,6/2)= 0,4/(1,2)+1/ (1,3)+0,6/(2,1)+0,6/(2,2)+0,4/(2,3)+1/ (3,1)+0,6/(3,2)

Que peut-on représenter comme une matrice de relation

Si UN, Alors DANS, Sinon C=

De même

Si UN, Alors В=(1/1+0,4/2)´(0,4/2+1/3)+(0,6/2+1/3)´(1/1+1/2+1/3 ) =0,4/(1,2 )+1/(1,3)+0,6/(2,1)+0,6/(2,2)+0,6/(2,3)+ 1/(3,1)+1/(3,2)+1/(3,3)

Ou équivalent

Si UN, Alors B=

Inférence dans les réseaux de neurones.

Réseau Hopfield.

Hopfield a utilisé la fonction énergétique comme outil pour construire des réseaux récurrents et comprendre leur dynamique. La formalisation de Hopfield a précisé le principe du stockage des informations sous forme d'attracteurs dynamiquement stables et a popularisé l'utilisation de réseaux récurrents pour la mémoire associative et pour résoudre des problèmes d'optimisation combinatoire.

La modification dynamique des états du réseau peut être effectuée d'au moins deux manières : de manière synchrone et asynchrone. Dans le premier cas, tous les éléments sont modifiés simultanément à chaque pas de temps, dans le second, à chaque instant un élément est sélectionné et traité. Cet élément peut être choisi aléatoirement. La propriété principale de la fonction énergétique est qu'au cours de l'évolution des états du réseau, selon l'équation, elle diminue et atteint un minimum local (attracteur), dans lequel elle maintient une énergie constante.

Mémoire associative

Si les motifs stockés dans le réseau sont des attracteurs, celui-ci peut être utilisé comme mémoire associative. Tout exemplaire situé dans la zone d'attraction d'un échantillon stocké peut servir de pointeur pour le restaurer.

La mémoire associative fonctionne généralement selon deux modes : le stockage et la récupération. En mode stockage, les poids des connexions dans le réseau sont déterminés de manière à ce que les attracteurs mémorisent l'ensemble pn-échantillons dimensionnels ( x 1 , x 2 ,..., xp), qui doit être sauvegardé. Dans le deuxième mode, l'exemple d'entrée est utilisé comme état initial du réseau, puis le réseau évolue en fonction de sa dynamique. Le modèle de sortie est établi lorsque le réseau atteint l’équilibre.

Combien d'exemples peuvent être stockés en ligne avec n des éléments binaires ? Autrement dit, quelle est la capacité de stockage du réseau ? Il est fini, puisque le réseau avec n les éléments binaires ont un maximum 2n différents états, et tous ne sont pas des attracteurs. De plus, tous les attracteurs ne peuvent pas stocker des modèles utiles. Les faux attracteurs peuvent également stocker des échantillons, mais ils sont différents des exemples de l'ensemble d'apprentissage.

Minimisation de l'énergie. Le réseau Hopfield évolue dans le sens d'une réduction de son énergie. Cela permet de résoudre des problèmes d'optimisation combinatoire s'ils peuvent être formulés comme des problèmes de minimisation d'énergie. En particulier, le problème du voyageur de commerce peut être formulé de manière similaire.

Certains autres algorithmes d'entraînement du tableau 6.3 sont décrits dans les ouvrages suivants : Adaline et Madaline, analyse discriminante linéaire, projections de Sammon, analyse en composantes principales.

Processus de développement d'ANN.

Bien que le processus ANN soit similaire aux méthodologies de conception structurelle des circuits intégrés informatiques traditionnels, certaines étapes sont propres aux applications de réseaux neuronaux ou comportent des facteurs supplémentaires. Dans le processus décrit ci-dessous, nous supposons que les étapes préliminaires du développement du système, telles que l'identification des besoins en informations et la réalisation d'une étude de faisabilité, sont entièrement achevées. De telles étapes sont communes à tout système d’information.

Comme le montre la fig. 6.8., le processus de développement d’applications ANN comporte neuf étapes.

Sur étape 1 Les données sont collectées pour être utilisées pour la formation et le test du réseau.

Il est important de prendre en compte que la tâche à accomplir est accessible pour obtenir une solution ANN et que des données adéquates existent et peuvent être obtenues à cette fin.

Sur étape 2 les données de formation doivent être établies et un plan doit être créé pour tester les performances du réseau.

Sur étapes 3-4 L'architecture du réseau et la méthode de formation sont sélectionnées. La disponibilité d'outils de développement ANN spéciaux peut déterminer le type de réseau neuronal à construire. Le nombre spécifique de neurones et le nombre de couches sont des considérations importantes.

Les modèles de réseaux neuronaux existants comportent des paramètres qui ajustent le réseau au niveau d'exécution souhaité. Une partie du processus de l'étape 5 consiste en l'initialisation des pondérations et des paramètres du réseau, qui suit également la réception de la réponse d'exécution. Souvent, les valeurs initiales sont importantes pour déterminer l'efficacité et la durée de la formation. La procédure suivante à l'étape 6 convertit les données utilisées dans le type et le format requis par le réseau neuronal. Cela peut impliquer d'utiliser des programmes pour prétraitement données. Le stockage et la manipulation des données doivent être organisés pour un recyclage pratique et efficace du réseau neuronal lorsque cela est nécessaire. En outre, la manière dont les données utilisées sont présentées et organisées détermine souvent l'efficacité et éventuellement l'exactitude des résultats obtenus par l'ANN.

Sur étapes 7 à 8 la formation et les tests sont effectués sous la forme d'un processus d'intervalle de présentation des entrées et des sorties souhaitées au réseau.

Le réseau neuronal calcule les sorties réelles et ajuste les poids jusqu'à ce que les sorties réelles correspondent à l'état souhaité. Les sorties souhaitées et leurs relations avec les entrées sont obtenues à partir des données historiques (une partie des données collectées à l'étape 1).

Sur étape 9 processus, un ensemble stable de poids est obtenu. Le réseau peut désormais reproduire les résultats souhaités des entrées publiées ainsi que sur l'ensemble de formation. Le réseau neuronal est prêt à être utilisé en tant que système indépendant ou dans le cadre d'un autre système logiciel.

Figure 6.8. Séquence du processus de développement et de configuration d'un réseau de neurones artificiels.

« Thème 4 : Cours 9 : Méthodes d'inférence et de recherche de solutions dans les systèmes de production. Méthodes d'inférence basées sur le chaînage avant et arrière. Pendant la production..."

Sakhnyuk P.A.

Thème 4 :

Cours 9 : Méthodes d'inférence et de recherche de solutions dans les systèmes de production.

Méthodes d'inférence basées sur le chaînage avant et arrière.

Dans la représentation de la production, un domaine de connaissance est représenté par un ensemble

les règles et les données de production sont représentées par une variété de faits sur

SI ALORS

situation actuelle.

Le mécanisme d'inférence compare chaque règle stockée dans la base de connaissances avec des faits,

Figure 1. Cycle du mécanisme d'inférence à travers la procédure de tir d'allumette

Faire correspondre les parties if des règles avec les faits crée une chaîne d'inférence. La chaîne d'inférence montre comment l'ES applique les règles pour obtenir une conclusion. Pour illustrer la méthode d’inférence basée sur la chaîne, considérons un exemple simple.

Disons que la base de données comprend initialement les faits A, B, C, D et E, et que la base de connaissances ne contient que trois règles :

Règle 1. Y&D Z Règle 2.

Règle X&B&EY 3. Chaîne de sortie AX sur la Fig. 2. montre comment l'ES applique des règles pour dériver le fait Z.

Sakhnyuk P.A.

Fig.2. Exemple de chaîne de sortie.

Premièrement, la règle 3 est déclenchée pour générer un nouveau fait X du fait publié A.

Ensuite, la règle 2 est exécutée pour déduire le fait Y des faits initialement connus B et E, ainsi que du fait X déjà connu. Enfin, la règle 1 applique le fait initialement connu D et le fait nouvellement obtenu Y pour arriver à la conclusion Z.

Le SE peut refléter sa chaîne d’inférence pour expliquer comment une décision particulière a été prise ; c'est une partie importante de ses pouvoirs explicatifs.

Le moteur d'inférence doit décider quand les règles doivent se déclencher. Il existe deux manières principales de mettre en œuvre les règles. L’une est appelée chaîne directe (déduite conditionnellement) et l’autre est appelée chaîne inverse (déduite par cible).

Cet exemple utilise le chaînage de sortie directe.

Les systèmes de production dans lesquels la partie antécédente (les conditions) sont d'abord analysées ont une architecture dite inférentielle conditionnelle. Un exemple de système expert d'une telle architecture est META-DENDRAL.

Un autre type d'architecture, qui est assez souvent utilisé dans les systèmes experts, est celui des systèmes de production par inférence de but (action-inférence ou conséquentielle). Par exemple, une règle de la forme A&B&CD peut être interprétée comme « La conjonction logique de A, B et C implique D » ou « Pour prouver D, il faut établir A, B, C ».

Dans ce dernier cas, l’objectif doit être atteint par inférence déductive. Pour ce faire, les conséquences des règles sont examinées pour trouver une règle qui permettrait d'atteindre l'objectif. Lorsqu’une telle règle est trouvée, toutes ses conditions sont vérifiées.

Si les conditions sont vraies, la sortie est activée. Sinon, la recherche de produits adaptés se poursuit.

Sakhnyuk P.A.

Regardons un exemple simplifié d'un système de production avec une architecture inférentielle conséquente. Les lettres ici indiquent les éléments de la base de données et elles sont considérées comme vraies si elles y sont contenues.

BD : AF Règle 1 : A&B&CD Règle 2 : D&FG Règle 3 : A&JG Règle 4 : BC Règle 5 : FB Règle 6 : LJ Règle 7 : GH Supposons que le but soit de déduire la vérité de H.

Tout d'abord, on vérifie si H est dans la base de données ? Puisque ce n’est pas le cas dans ce cas, le système tente de déduire la vérité de H en utilisant des règles qui ont H du côté droit. C'est la règle 7. Maintenant le système essaie de déduire la vérité de G, puisque la vérité de cette dernière entraîne la vérité de H. La base de données est à nouveau vérifiée : il n'y a pas de G dans la base de données, donc un pôle de la règle contenant G sur le côté droit est organisé. Il existe plusieurs règles de ce type (deux ou trois). En tant que stratégie de « résolution de conflits », nous supposerons que les règles sont classées par priorité, la règle avec le numéro le plus bas correspondant à la priorité la plus élevée.

Dans ce cas, la règle 2 est choisie, le but devient donc maintenant de déduire la vérité de D et F. Pour cela, il suffit de montrer que A est vrai (puisqu'il est dans la base de données), B est vrai (selon à la règle 5), C est vrai (selon la règle 4 ). Puisque la vérité de D et F a été prouvée, alors de la règle 2 découle la vérité de G, et de la vérité de G découle la vérité de H (règle 7). L'objectif a donc été atteint. Les éléments avérés sont ajoutés à la base de données. Dans ce cas, ce sont les éléments H, G, D, S.V.

Des exemples d'architectures d'inférence cible incluent MYCIN.

Méthodes générales pour trouver des solutions dans l'espace d'état.

Méthodes de dénombrement. La solution à de nombreux problèmes dans les systèmes intelligents peut être définie comme un problème de recherche, où la solution recherchée est l'objectif de la recherche, et l'ensemble des chemins possibles pour atteindre l'objectif représente l'espace de recherche (ou espace d'état). Trouver des solutions dans l'espace consiste à déterminer une séquence d'opérateurs qui transforment l'état initial en état cible.

Sakhnyuk P.A.

Le problème de la recherche dans l’espace d’état peut être formulé sous la forme générale suivante :

Soit le problème initial décrit par un triplet (S, F, T), où S est l'ensemble des états initiaux ; F – un ensemble d'opérateurs mappant un état à un autre ; T – ensemble d’états cibles. La solution du problème consiste à trouver (fi F), qui transforment les séquences initiales d'opérateurs f1,f2,…,fk en états finaux. Le problème de recherche dans l'espace d'états est décrit à l'aide de concepts issus de la théorie des graphes. Un sommet initial (état initial) et un ensemble de sommets cibles T sont spécifiés. Les opérateurs F sont utilisés pour construire l'espace d'états. Les opérateurs liés à ce niveau sont utilisés séquentiellement de la racine aux sommets de l'arbre pour construire les sommets successeurs de l'arbre. niveau suivant (ouverture du sommet). Les arcs sont identifiés comme opérateurs de transformation.

Les sommets successeurs résultants sont vérifiés pour voir s'ils sont ceux cibles. Puis ils passent au niveau suivant. Les sommets terminaux sont ceux sur lesquels aucun opérateur ne peut être appliqué. L'expansion se poursuit jusqu'à ce que la cible ou le sommet terminal soit atteint. La recherche de graphe d'état est le processus de construction d'un graphe G contenant un sommet cible. Ce graphique est appelé graphique de recherche. La différence entre plusieurs options d'implémentation de la méthode d'énumération, qui diffèrent par l'ordre spécifié dans lequel les sommets seront énumérés.

Recherche en profondeur d'abord. Lors d’une recherche en profondeur, le sommet le plus profond est d’abord révélé. Parmi les sommets situés à la même profondeur, le choix du sommet d'ouverture est déterminé arbitrairement. Pour limiter la possibilité de suivre un non-chemin, une limite de profondeur est introduite. Les sommets situés à la profondeur limite ne sont pas ouverts.

Première recherche en largeur. Les sommets sont révélés dans la séquence de leur génération.

La recherche s'effectue sur la largeur de l'arbre, puisque l'ouverture du sommet se fait le long d'un niveau.

Le sommet cible est sélectionné immédiatement après la génération. Lors de la recherche en largeur, il est possible de trouver le chemin le plus court vers le sommet cible, si un tel chemin existe. Sur la fig. La figure 3 montre des graphiques de recherche, une construction pour les recherches en profondeur et en largeur.

Sakhnyuk P.A.

a) b) Fig. 3. Graphiques de recherche construits à l'aide d'une recherche en profondeur d'abord (a) et d'une recherche en largeur d'abord (b) Recherche basée sur le coût des arcs. Dans de nombreux cas, les arcs se voient attribuer une certaine valeur afin de fournir une estimation pour l'utilisation de la règle correspondante. Lors de la recherche d’un sommet cible, on s’efforce de trouver le chemin du coût minimum.

Les sommets sont révélés par ordre croissant de leur valeur. Pour chaque sommet, vous devez vous rappeler le coût minimum du chemin construit depuis le sommet initial jusqu'à celui-ci.

Recherche avec retour (backtracking). Lors de la mise en œuvre d'une telle recherche, lors du choix d'une règle, un point de retour est déterminé, c'est-à-dire que si une recherche ultérieure dans la direction choisie entraîne des difficultés ou n'est pas prometteuse, une transition est alors effectuée vers le point de retour passé au début de la recherche. . Ensuite, une autre règle est appliquée et le processus de recherche se poursuit. Ici, toutes les itérations infructueuses ayant conduit à une impasse sont oubliées dès que la nouvelle règle est appliquée, et la recherche passe dans une autre direction. Cette méthode de backtracking est appelée backtracking chronologique. Il est souvent inefficace car il ne mémorise pas les états infructueux et les étapes de recherche rencontrées le long d'un certain chemin. Beaucoup d’entre eux rendront par la suite leurs services à Sakhnyuk P.A.

impact négatif lors de la mise en œuvre d’autres voies. Que. de nombreuses informations utiles sont rejetées et ne sont pas utilisées lors de l'analyse de directions de recherche ultérieures.

Il est nécessaire d’analyser les étapes d’inférence qui conduisent à des blocages et des erreurs.

Pour ce faire, vous devez vous rappeler les étapes de retrait. De plus, il ne faut pas revenir au point de retour précédant l'état donné, mais à l'état qui a provoqué l'échec de la recherche.

Il est caractéristique des méthodes de recherche de solution lors de la représentation de l'espace d'états sous forme de graphe qu'elles consistent principalement à stocker les résultats de l'application de plusieurs séquences de règles. Une autre particularité est qu'ils fonctionnent en mode essai, c'est-à-dire que lors de la sélection et de l'utilisation d'une règle applicable à n'importe quelle situation, il est possible de revenir à cette situation pour appliquer une autre règle. Les avantages des méthodes par force brute sont leur mise en œuvre assez simple et la possibilité, en principe, de trouver une solution si elle existe. Cependant, dans la pratique, le processus de mise en œuvre de la recherche présente toujours des limites de temps et de mémoire. Pour les grands espaces et les ensembles complexes de problèmes, les méthodes de force brute sont inacceptables - la réalité d'une explosion combinatoire. Pour affiner la recherche, des informations appelées heuristiques sont nécessaires.

Méthodes de recherche heuristique. Ces méthodes de recherche peuvent être utilisées lorsque vous disposez de quelques règles empiriques qui vous permettent de réduire le nombre de solutions que vous recherchez. Les informations heuristiques sont basées sur l'expérience, le bon sens et les hypothèses du développeur.

Lors de l’utilisation de méthodes de recherche heuristiques, les sommets ouverts ont tendance à être ordonnés de telle manière que le processus de recherche se propage dans les directions les plus prometteuses. Pour déterminer la direction de recherche, on utilise une certaine mesure qui caractérise les perspectives du sommet ou le chemin où se trouve ce sommet. Cette mesure est appelée fonction d'évaluation f(n). Cette fonction est une estimation du coût du chemin le plus court du sommet initial au sommet cible, à condition qu'il passe par le sommet n. Lors de l'expansion d'un sommet ou de la détermination d'un chemin, le sommet avec la valeur minimale de la fonction d'évaluation est sélectionné. La fonction d'évaluation doit caractériser adéquatement l'espace de recherche, c'est-à-dire une quantité suffisamment grande de connaissances sur le domaine du problème et une analyse approfondie de l’espace d’état sont nécessaires. En pratique, l'utilisation de caractéristiques quantitatives et de coefficients de pondération pour représenter ces connaissances n'est pas justifiée, car l'application ne permet pas une recherche efficace de solutions (de gros volumes de calculs peuvent être nécessaires).

De plus, une recherche heuristique utilisant la fonction d'évaluation est suggérée par Sakhnyuk P.A.

connaissance fiable de l’espace d’état. Cependant, dans la pratique, lorsqu'ils prennent des décisions, ils sont confrontés à des faits et à des connaissances insuffisamment complets et précis.

De plus, le processus de recherche est souvent affecté par la pression du temps. Dans ces conditions, les gens utilisent des méthodes autres que le raisonnement mathématique formel.

Le raisonnement mathématique formel est monotone, c'est-à-dire chaque conclusion découle de la précédente. (La monotonie est une propriété de certaines opérations (fonctions) logiques et mathématiques, qui, d'une manière générale, consiste dans le fait que la direction d'un changement possible dans le résultat des opérations ne dépend que de la direction du changement dans ce sur quoi ces opérations sont effectuées. .) Les décideurs utilisent un raisonnement non monotone, ou un raisonnement de bon sens (basé sur des connaissances élémentaires générales).

Même si le raisonnement de bon sens est assez courant chez les humains, il est très difficile d’atteindre le niveau requis de mise en œuvre d’un tel raisonnement dans l’IA. (Cependant, dans certains ES classiques, tels que MYCIN, PROSPECTOR, cette méthode est implémentée avec succès pour réduire l'espace de recherche.

Dans le raisonnement de bon sens, la procédure de recherche repose sur certaines hypothèses en l’absence d’informations contredisant ces hypothèses.

Les hypothèses peuvent changer à mesure que des informations de clarification supplémentaires deviennent disponibles, c'est-à-dire dans les systèmes de recherche basés sur des hypothèses, il est nécessaire de revoir les hypothèses sur la nature de la situation et l'orientation de la recherche lors de l'obtention de nouveaux faits et connaissances. Il est également nécessaire de revoir les conclusions obtenues sur la base de ces hypothèses. (Combinaison avec procédures de retour) Méthode de réduction. Trouver l'ensemble de données nécessaire pour résoudre un problème revient à résoudre les sous-tâches qui le constituent. Les tâches sont décrites de différentes manières : listes, arbres, tableaux. Considérons la forme de description du problème comme une recherche dans l’espace d’états. Dans cette représentation, les sous-tâches sont considérées comme des problèmes consistant à trouver des connexions entre certains états dans l'espace de recherche. Pour représenter le problème d'origine sous la forme d'un ensemble de sous-tâches, l'opérateur de transition vers une nouvelle description est utilisé. Cet opérateur transforme le problème d'origine de telle manière que lorsque tous les sous-problèmes successeurs sont résolus, une solution au problème d'origine est fournie.

Pour chaque représentation du problème d'origine, il peut y avoir un certain ensemble de tels opérateurs, dont chacun génère son propre ensemble de sous-tâches. Certaines de ces sous-tâches peuvent s’avérer insolubles. Pour les autres sous-tâches, le processus est répété, c'est-à-dire

eux, à leur tour, sont également réduits à des sous-tâches. Cela continue jusqu'à ce que chaque sous-problème ait une solution évidente.

Sakhnyuk P.A.

Le processus de transformation est également commodément décrit à l’aide de structures graphiques.

Le processus de recherche d'une solution au problème d'origine avec cette description est un graphique de réduction de problème orienté. Ce graphe est appelé graphe ET/OU. Les sommets de ce graphique représentent des descriptions de tâches et de sous-tâches. Le graphe AND/OR contient deux types de sommets. Type « I » – correspond à un problème qui peut être résolu à condition que toutes ses sous-tâches soient implémentées dans les sommets successeurs correspondants. Type « OU » – correspond à un problème dont la solution peut être obtenue en résolvant l’un des sous-problèmes alternatifs aux sommets successeurs correspondants. Sur la fig. 4. Des fragments de graphiques de type ET/OU sont présentés.

b) Fig. 4. Représentation de la division du problème initial en sous-tâches sous la forme d'un graphe ET/OU (a) et transformation du graphe ET/OU (b).

La tâche initiale S0 est divisée en groupes de sous-tâches. Il peut être résolu en résolvant les sous-problèmes S1 et S2 ; ou S3 ; S4 et S5. Les pics N, S3, M, S5 sont des sommets de type « I ». La ligne pointillée montre une version du graphique de solution du problème d'origine. Les solutions aux sous-tâches S2, S7, S9, S10, S11 sont supposées connues. Les solutions aux autres sous-problèmes sont inconnues. Des sommets supplémentaires sont généralement introduits dans la structure afin que chaque ensemble de sous-tâches soit formé sous son propre sommet parent.

Sakhnyuk P.A.

Un sommet d'un graphe AND/OR peut être de type AND ou OR. Par conséquent, le graphe original est transformé et des sommets supplémentaires N et M sont introduits, qui servent de sommets parents distincts pour les sous-problèmes (S1, S2) et (S4, S5. Ainsi, le sommet S0 est transformé en sommet OU.

L’implémentation du graphe de réduction est similaire à l’implémentation du graphe de recherche de solution dans l’espace d’état. Dans le cas particulier, s’il n’y a pas de sommets AND, le résultat est un graphe d’espace d’état ordinaire. Par conséquent, la méthode de réduction est dans une certaine mesure une généralisation de l’approche de l’espace d’états.

Le processus de recherche sur un graphe ET/OU consiste à construire un graphe de décision (ou arbre de décision), qui est un sous-graphe du graphe de réduction.

Méthodes pour trouver des solutions dans de grands espaces d'états.

Il existe différentes méthodes pour organiser la recherche et l’inférence de solutions dans de grands espaces d’états. L'utilisation d'une méthode particulière est associée à la nature de l'espace d'états, à sa structurabilité, à la capacité de décrire la zone de solution à différents niveaux d'abstraction, à la capacité d'évaluer les chemins de recherche prometteurs et à d'autres facteurs.

Un domaine problématique réel est souvent caractérisé par un espace d’états si vaste qu’il peut être très difficile d’organiser pratiquement une recherche à l’aide de méthodes de force brute. Cependant, il est souvent nécessaire de trouver toutes les solutions possibles dans un domaine problématique. La solution dans de tels cas consiste à utiliser la méthode de génération et de vérification. Cette méthode peut être utilisée si l'espace est factorisable, c'est-à-dire

il est possible de le partitionner en sous-espaces assez indépendants avec des solutions incomplètes caractéristiques. Une solution incomplète caractéristique permet de juger des perspectives de recherche de solutions complètes dans ce sous-espace.

L'essence de la méthode est qu'un générateur adapté au domaine du problème génère un certain nombre de solutions incomplètes caractéristiques correspondant aux descriptions de divers sous-espaces. Les solutions incomplètes sont vérifiées à l'aide de procédures d'évaluation spéciales, et si la solution s'avère inacceptable, alors toute la classe de solutions complètes d'un sous-espace donné générée par celle-ci est exclue d'un examen plus approfondi. En raison de la suppression de certaines branches de recherche à un stade précoce de la recherche sans générer ni vérifier les nœuds d'état, le nombre d'états à analyser est considérablement réduit. Si une solution incomplète est reconnue comme prometteuse, alors sur sa base dans le sous-espace correspondant, des solutions complètes sont développées à des niveaux plus profonds de la hiérarchie de description de l'espace et il est déterminé si les solutions résultantes sont des solutions cibles.

Sakhnyuk P.A.

La procédure hiérarchique de mise en œuvre du procédé de génération et de vérification permet d'appliquer les règles de coupure des variantes dès les premières étapes de génération. L'utilisation de la méthode de génération et de vérification dans un espace factorisé peut être difficile en raison du fait qu'il n'existe souvent pas de méthodes fiables pour évaluer des solutions incomplètes caractéristiques, c'est-à-dire qu'il n'est pas possible de tirer des conclusions sur la faisabilité de solutions complètes basées sur des solutions incomplètes. . Ici, il est impossible de couper les branches peu prometteuses avec un degré de confiance élevé au stade initial de la recherche. Il existe toujours un risque d'exclure une partie de l'espace d'état qui semble peu prometteuse, mais qui est tout à fait capable de fournir une solution lors d'un traitement ultérieur lorsque des informations supplémentaires apparaissent.

De telles situations sont typiques des problèmes de planification et de conception à long terme.

De plus, il n’est pas toujours nécessaire de rechercher toutes les solutions possibles, mais il suffit d’en avoir une acceptable.

Dans ces cas, l’espace des solutions est abstrait. La solution au problème s'effectue à différents niveaux d'abstraction en le clarifiant séquentiellement à ces niveaux de description de l'espace. L'abstraction révèle en outre des détails importants qui caractérisent le problème. La tâche principale est réduite à un ensemble fixe de descriptions de sous-tâches. Dans les cas simples de l'espace abstrait, une seule partition suffit, utilisée pour différentes tâches d'un domaine problématique donné.

Si la zone problématique contient un grand nombre de problèmes, il n'est alors pas possible de résoudre tous les problèmes en utilisant une certaine version de la réduction de l'espace de recherche. Un exemple est le problème de la planification des actions d’un robot pour se déplacer dans l’espace et manipuler des objets. Dans ces cas, l'abstraction doit refléter la structure variable du plan d'action.

Il est possible d'utiliser la méthode de raffinement séquentiel par le haut. Cette méthode se caractérise par le fait qu'elle crée une abstraction adéquate à chaque tâche. De plus, pour simplifier le processus de résolution d'un problème, ils obtiennent d'abord une description généralisée de l'espace et résolvent le problème dans cet espace, puis passent à une description plus spécifique de l'espace. Ainsi, la solution au problème est mise en œuvre de haut en bas, depuis la recherche et la définition d'une solution dans l'espace abstrait jusqu'à la transformation de cette solution et sa concrétisation à des niveaux de description inférieurs (c'est-à-dire plus détaillés).

Le passage à un niveau plus spécifique s'effectue seulement une fois la solution au niveau d'abstraction en question terminée.

Lors de la recherche de solutions dans de grands espaces d’états, des méthodes et procédures heuristiques sont également utilisées. Il est souvent difficile d'identifier un P.A. Sakhnyuk purement heuristique.

procédure, car elle peut être plus ou moins intégrée à l’une des méthodes nommées. Par exemple, des évaluations heuristiques sont présentes dans la méthode de génération et de test, où le générateur construit des hypothèses concernant des solutions incomplètes caractéristiques, qui sont ensuite testées. Lors de l'utilisation de la méthode de raffinement séquentiel par le haut, il est supposé et admis que la résolution du problème aux niveaux d'abstraction supérieurs permettra de spécifier la solution à des niveaux plus détaillés de la description du problème.

La nécessité de formuler des hypothèses lors de la recherche de solutions peut être causée par de nombreuses raisons : l'incapacité de faire un choix de direction de recherche à un certain stade de la décision lors de la mise en œuvre d'une méthode, des faits et des connaissances insuffisants ; manque de temps pour étudier diverses solutions ;

d’autres ressources limitées. Dans ces cas, une hypothèse raisonnable est avancée quant à l'orientation ultérieure de la recherche, qui reste valable jusqu'à ce que, sur la base de nouvelles informations obtenues lors de la décision, le contraire devienne évident. En pratique, ils s’efforcent de mettre en œuvre un raisonnement fondé sur le bon sens, c’est-à-dire un raisonnement non monotone, ce qui est assez difficile dans les systèmes d’IA pratiques, comme indiqué ci-dessus.

Classement des erreurs

Ressources Internet

Plan de la conférence

Débogage de logiciels

Conférence n°8.

Tambov 2011

Cours, groupes BIS-11, BIS-12

Sujet 6. Débogage de logiciels

Conférence 8

Technologie de programmation disciplinaire

Direction 230400 « Systèmes et technologies de l'information »

Professeur : Minine Youri Viktorovitch

Objectif de la conférence

Le but de la conférence est de fournir une compréhension du processus et des techniques de débogage logiciel.

1. Classification des erreurs

2. Techniques de débogage de logiciels

3. Méthodes et moyens d'obtenir des informations complémentaires sur l'erreur

4. Technique de débogage du logiciel

Références

Littérature de base

1. Ivanova G.S. Technologie de programmation M. : Maison d'édition MSTU im. N.E. Bauman, 2002. - 320 p.

2. Jogolev E.A. Technologie de programmation M. : Monde scientifique, 2004. - 216 p.

3. Gagarina L.G., Kokoreva E.V., Visnadul B.D. Technologie de développement de logiciels. M. : Maison d'édition "FORUM" - INFRA-M, 2008. - 400 p.

Lectures complémentaires

1. Kaner S., Folk D., Nguyen E. Tests de logiciels. M. : DiaSoft, 2001. - 544 p.

2. Braude E. Technologie de développement de logiciels. Saint-Pétersbourg : Peter, 2004. - 655 p.

3. Baranov S.N., Domaratsky A.N., Lastochkin N.K., Morozov V.P. Processus de développement de produits logiciels. M. : FIZMATLIT, Nauka, 2000. - 176 p.

1. www.intuit.ru - Université Internet des technologies de l'information.

2. http://citforum.ru/ - Centre de technologie de l'information.

3. http://www.tstu.ru/r.php?r=education - Bibliothèque électronique TSTU.

4. http://www.edu.ru/ - Bibliothèque du portail fédéral « Éducation russe »

Le débogage d'un programme est l'une des étapes les plus difficiles du développement logiciel, nécessitant une connaissance approfondie de :

Des spécificités de gestion des moyens techniques utilisés,

Système opérateur

Environnement et langage de programmation,

Processus mis en œuvre,

La nature et les spécificités des diverses erreurs,

Techniques de débogage et logiciels associés.

Cette conférence est consacrée à la discussion des deux dernières questions.

Débogage- est le processus de localisation et de correction des erreurs trouvées lors des tests logiciels. Localisation appelé le processus de détermination d'une instruction de programme dont l'exécution a provoqué une perturbation du processus de calcul normal. Pour corriger l'erreur, vous devez l'identifier raison, c'est-à-dire identifier l'instruction ou le fragment qui contient l'erreur. Les causes des erreurs peuvent être à la fois évidentes et très profondément cachées.

En général, la difficulté du débogage est due aux raisons suivantes :

Nécessite que le programmeur ait une connaissance approfondie des spécificités de la gestion du matériel utilisé, du système d'exploitation, de l'environnement et du langage de programmation, des processus mis en œuvre, de la nature et des spécificités des diverses erreurs, des techniques de débogage et des logiciels pertinents ;

Psychologiquement inconfortable, car vous devez rechercher vos propres erreurs et, en règle générale, dans un temps limité ;

Il est possible que des erreurs dans différentes parties du programme interagissent, par exemple en raison de l'effacement de la zone mémoire d'un module par un autre en raison d'erreurs d'adressage ;

Il n'existe pas de techniques de débogage clairement définies.

Selon l'étape de traitement à laquelle les erreurs apparaissent, on les distingue (Fig. 1) :

- erreurs de syntaxe - erreurs enregistrées par le compilateur (traducteur, interprète) lors de l'analyse syntaxique et partiellement sémantique du programme ;

- erreurs de mise en page - erreurs détectées par l'éditeur de liens (éditeur de liens) lors de la combinaison des modules du programme ;

- erreurs d'exécution - erreurs rencontrées par le système d’exploitation, le matériel ou l’utilisateur lors de l’exécution d’un programme.

Figure 1 - Classification des erreurs par étape de traitement du programme

Erreurs de syntaxe. Les erreurs de syntaxe sont classées parmi les plus simples, car la syntaxe du langage est généralement strictement formalisée et les erreurs sont accompagnées d'un commentaire détaillé indiquant son emplacement. En règle générale, déterminer les causes de telles erreurs n'est pas difficile, et même avec une connaissance peu claire des règles du langage, il est possible en plusieurs exécutions de supprimer toutes les erreurs de ce type.

Il convient de garder à l'esprit que plus les règles de syntaxe du langage sont formalisées, plus le compilateur peut détecter d'erreurs par rapport au nombre total et, par conséquent, moins d'erreurs seront détectées aux étapes suivantes. À cet égard, ils parlent de langages de programmation avec une syntaxe protégée et une syntaxe non protégée. Le premier, bien sûr, inclut Pascal, qui a une syntaxe très simple et clairement définie, qui est bien vérifiée lors de la compilation d'un programme, et le second - C/C++ avec toutes ses modifications. Que vaut au moins pouvoir effectuer une affectation dans un opérateur conditionnel en C/C+, par exemple :

Dans ce cas, l'égalité de c et oui n'est pas vérifiée, mais une affectation à partir de la valeur n est effectuée, après quoi le résultat de l'opération est comparé à zéro. Si le programmeur voulait effectuer non pas une affectation, mais une comparaison, alors cette erreur ne sera détectée qu'au stade de l'exécution lors de l'obtention de résultats différents de ceux attendus.

Erreurs de mise en page. Les erreurs de mise en page, comme leur nom l'indique, sont liées à des problèmes rencontrés lors de la résolution des liens externes. Par exemple, un appel à un sous-programme d'un autre module est fourni, mais lors de la fusion de modules, ce sous-programme n'est pas trouvé ou les listes de paramètres ne sont pas jointes. Dans la plupart des cas, les erreurs de ce type peuvent également être rapidement localisées et éliminées.

Erreurs d'exécution. Le groupe le plus imprévisible comprend les erreurs d’exécution. Tout d’abord, ils peuvent avoir des natures différentes et, par conséquent, se manifester différemment. Certaines erreurs sont détectées et documentées par le système d'exploitation. De telles erreurs peuvent se manifester de quatre manières :

L'apparition d'un message d'erreur enregistré par les circuits de contrôle d'exécution des commandes machine, par exemple débordement de grille de bits, situation de division par zéro, violation d'adressage, etc. ;

Un message apparaît concernant une erreur détectée par le système d'exploitation, par exemple une violation de la protection de la mémoire, une tentative d'écriture sur des périphériques protégés en écriture, l'absence d'un fichier portant le nom spécifié, etc.

- le « gel » de l'ordinateur, à la fois simple, lorsqu'il est possible de terminer le programme sans redémarrer le système d'exploitation, et « grave », lorsqu'un redémarrage est nécessaire pour continuer à travailler ;

Écart entre les résultats obtenus et ceux attendus.

A noter que si des erreurs au stade de l'exécution sont détectées par l'utilisateur, alors dans les deux premiers cas, après avoir reçu le message correspondant, l'utilisateur, en fonction de son caractère, de son degré de besoin et de son expérience avec l'ordinateur, tentera soit de comprendre quoi s'est produit, cherche sa faute, ou demande de l'aide, ou essaiera de ne plus jamais s'occuper de ce produit. Lorsque l'ordinateur se bloque, l'utilisateur peut même ne pas comprendre immédiatement que quelque chose ne va pas, même si sa triste expérience l'inquiète à chaque fois que l'ordinateur ne répond pas rapidement à la commande saisie, qu'il est également conseillé de garder à l'esprit. Les situations dans lesquelles l'utilisateur reçoit des résultats incorrects et les utilise dans son travail peuvent également être dangereuses.

Les causes des erreurs d'exécution sont très variées et la localisation peut donc être extrêmement difficile. Toutes les causes possibles d'erreurs peuvent être divisées dans les groupes suivants :

Définition incorrecte des données sources,

Erreurs logiques

Accumulation d'erreurs dans les résultats de calcul (Fig. 2).

Une mauvaise identification des données sources se produit lorsqu'une erreur se produit lors des opérations d'E/S : erreurs de transfert, erreurs de conversion, erreurs de réécriture et erreurs de données. De plus, l'utilisation de moyens techniques particuliers et une programmation sans erreurs permettent de détecter et de prévenir seulement certaines de ces erreurs.

Les erreurs logiques ont des natures différentes. Ainsi, ils peuvent résulter d'erreurs commises lors de la conception, par exemple lors du choix des méthodes, du développement des algorithmes, ou de la définition de la structure des classes, ou bien ils peuvent être directement introduits lors du codage du module. Le dernier groupe comprend :

Erreurs d'utilisation incorrecte des variables, par exemple, choix infructueux des types de données, utilisation de variables avant leur initialisation, utilisation d'index allant au-delà de la définition des tableaux, violations de la correspondance des types de données lors de l'utilisation d'une redéfinition explicite ou implicite du type de données localisé en mémoire lors de l'utilisation de variables non typées, de tableaux ouverts, d'unions, de mémoire dynamique, d'arithmétique d'adresse, etc. ;

Erreurs de calcul, par exemple, calculs incorrects sur des variables non arithmétiques, utilisation incorrecte de l'arithmétique entière, conversion incorrecte des types de données lors des calculs, erreurs liées à la méconnaissance des priorités des opérations pour les expressions arithmétiques et logiques, etc.

Erreurs dans l'interface intermodule, par exemple, ignorer les conventions du système, violation des types et de la séquence lors du passage des paramètres, non-respect de l'unité des unités de mesure des paramètres formels et réels, violation de la portée des variables locales et globales ;

Autres erreurs de codage, par exemple, mise en œuvre incorrecte de la logique du programme lors du codage, ignorant les caractéristiques ou les limitations d'un langage de programmation particulier.

L'accumulation d'erreurs dans les résultats des calculs numériques se produit, par exemple, lorsque les chiffres fractionnaires des nombres sont incorrectement ignorés, que les méthodes de calcul approximatives sont utilisées de manière incorrecte, que les restrictions sur la grille de chiffres pour représenter les nombres réels dans un ordinateur sont ignorées, etc.

Toutes les raisons d’erreurs ci-dessus doivent être gardées à l’esprit pendant le processus de débogage. De plus, la complexité du débogage augmente également en raison de l'influence des facteurs suivants :

Manifestation indirecte d'erreurs ;

Possibilité d'influence mutuelle des erreurs ;

Possibilité d'obtenir des manifestations extérieurement identiques d'erreurs différentes ;

Manque de répétabilité des manifestations de certaines erreurs d'un lancement à l'autre (erreurs stochastiques) ;

La capacité d'éliminer les manifestations externes d'erreurs dans la situation étudiée lors de certaines modifications du programme, par exemple, lorsque des fragments de diagnostic sont inclus dans le programme, la manifestation externe d'erreurs peut être annulée ou modifiée ;

Écriture de parties distinctes du programme par différents programmeurs.

Dans tous les cas, le débogage d'un programme nécessite une réflexion et une compréhension logique de toutes les informations disponibles sur l'erreur. La plupart des erreurs peuvent être détectées par des preuves indirectes grâce à une analyse approfondie des textes du programme et des résultats des tests sans obtenir d'informations supplémentaires. Différentes méthodes sont utilisées :

Tests manuels ;

Induction;

Déduction;

Rétrolien.

Méthode de test manuelle. C'est la méthode la plus simple et la plus naturelle de ce groupe. Si une erreur est détectée, vous devez exécuter le programme testé manuellement, en utilisant la suite de tests au cours de laquelle l'erreur a été détectée.

La méthode est très efficace, mais n'est pas applicable aux programmes volumineux, aux programmes avec des calculs complexes et dans les cas où l'erreur est due à une mauvaise compréhension du programmeur sur la façon d'effectuer certaines opérations.

Cette méthode est souvent utilisée dans le cadre d’autres méthodes de débogage.

Méthode d'induction. La méthode est basée sur une analyse minutieuse des symptômes d’erreur, qui peuvent apparaître sous la forme de résultats de calcul incorrects ou d’un message d’erreur. Si l'ordinateur « se fige » simplement, un fragment de la manifestation de l'erreur est calculé sur la base des derniers résultats reçus et des actions de l'utilisateur. Les informations ainsi obtenues sont organisées et soigneusement étudiées en visualisant le fragment correspondant du programme. À la suite de ces actions, des hypothèses d'erreurs sont avancées, dont chacune est testée. Si l’hypothèse est correcte, alors les informations sur l’erreur sont détaillées, sinon une autre hypothèse est avancée. La séquence de débogage utilisant la méthode d'induction est illustrée à la Fig. 3 sous la forme d'un diagramme algorithmique.

Figure 3 - Schéma du processus de débogage par induction

L'étape la plus critique consiste à identifier les symptômes de l'erreur. Lors de l'organisation des données sur une erreur, il est conseillé d'écrire tout ce qui est connu sur ses manifestations et d'enregistrer à la fois les situations dans lesquelles un fragment avec une erreur est exécuté normalement et les situations dans lesquelles l'erreur se manifeste. Si, à la suite de l’étude des données, aucune hypothèse n’émerge, des informations supplémentaires sur l’erreur sont alors nécessaires. Des informations supplémentaires peuvent être obtenues, par exemple, en effectuant des tests similaires.

Dans le processus de preuve, ils essaient de savoir si toutes les manifestations d'une erreur sont expliquées par une hypothèse donnée, sinon toutes, alors soit l'hypothèse est incorrecte, soit il y a plusieurs erreurs ;

Méthode de déduction. En utilisant la méthode de déduction, diverses raisons sont d'abord formées qui pourraient provoquer cette manifestation d'erreur. Ensuite, en analysant les raisons, excluez celles qui contredisent les données disponibles. Si toutes les causes sont exclues, des tests supplémentaires sur le fragment étudié doivent être effectués. Sinon, ils tentent de prouver l’hypothèse la plus probable. Si l'hypothèse explique les symptômes reçus d'une erreur, alors l'erreur est trouvée, sinon la raison suivante est vérifiée (Fig. 4).

Figure 4 - Schéma du processus de débogage utilisant la méthode de déduction

Méthode de rétrolien. Pour les petits programmes, la méthode du backtracking est efficace. Ils partent du point où ils produisent un mauvais résultat. Pour ce point, une hypothèse est construite sur les valeurs des principales variables qui pourraient conduire à l'obtention du résultat existant. Ensuite, sur la base de cette hypothèse, des propositions sont faites sur les valeurs des variables au point précédent. Le processus se poursuit jusqu'à ce que la cause de l'erreur soit découverte.

Conférence 9.Contrôle E/S

9.1 Principes du matériel d'E/S

Les deux niveaux inférieurs du système de contrôle des E/S sont le matériel : les appareils eux-mêmes, qui effectuent directement les opérations, et leurs contrôleurs, qui servent à organiser la collaboration des appareils et du reste du système informatique. Le niveau suivant est Pilotes de périphérique d'E/S , cachant les fonctionnalités du système d'exploitation de périphériques spécifiques aux développeurs de systèmes d'exploitation et fournissant une interface clairement définie entre le matériel et le niveau supérieur - le niveau , qui, à son tour, fournit un mécanisme d'interaction entre les pilotes et la partie logicielle du système informatique dans son ensemble.

Riz. 1. Structure du système d'E/S

Dans tout système d'exploitation, il existe un sous-système spécial qui contrôle l'équipement d'entrée/sortie. Les principales tâches résolues à l'aide de ce sous-système sont les suivantes :

- le sous-système doit fournir aux utilisateurs une interface pratique et compréhensible pour accéder au panneau de commande dans les modes de fonctionnement de l'ordinateur mono-utilisateur et multi-utilisateur ; dans le même temps, il est souvent nécessaire de réaliser une interface unifiée pour l'accès aux appareils de contrôle présentant des caractéristiques physiques différentes, pour laquelle le principe d'indépendance des appareils est mis en œuvre ;

- dans le mode de fonctionnement multiprogramme des systèmes à temps partagé, le sous-système doit assurer une telle planification du processus d'entrée-sortie de données afin d'obtenir un chevauchement maximal du temps de fonctionnement de l'unité centrale (CPU) et de l'équipement d'entrée-sortie.

- La composition du sous-système du système d'exploitation pour les périphériques d'entrée-sortie et les équipements d'entrée-sortie diffère considérablement selon les ordinateurs, mais un principe conceptuel unique peut être identifié, caractéristique de tous les sous-systèmes. Le matériel d’E/S peut être considéré comme un ensemble de processeurs matériels capables de fonctionner en parallèle les uns avec les autres, ainsi qu’avec le CPU. Ces processeurs exécutent des processus dits externes. Par exemple, pour un périphérique d'impression, le processus peut consister en un ensemble d'actions qui assurent le retour chariot, l'avance du papier d'une ligne et l'impression d'un nombre donné de caractères sur une ligne.

Les processus externes interagissent avec les processus logiciels exécutés par le processeur et la mémoire vive (RAM). Il est important que la vitesse d'exécution d'un processus logiciel puisse dépasser la vitesse d'un processus externe de plusieurs ordres de grandeur.

Le sous-système OS pour le contrôle des E/S du point de vue des processus logiciels est une interface avec le panneau de commande. Il existe trois types d'actions avec PU :

1. opérations de lecture-écriture de données ;

2. Opérations de contrôle des PU ;

3. opérations de vérification de l'état de la centrale.

9.1.1 Périphériques d'E/S

Les appareils sont divisés en deux catégories (certains n’appartiennent à aucune des deux) :

• périphériques de bloc - les informations sont lues et écrites en blocs, les blocs ont leur propre adresse (disques)
• périphériques de caractères - les informations sont lues et écrites caractère par caractère (imprimante, cartes réseau, souris)

9.1.2 Contrôleurs d'appareils

Les périphériques d'E/S se composent généralement de deux parties :

• mécanique (ne doit pas être pris au pied de la lettre) - disque, imprimante, moniteur
• électronique - contrôleur ou adaptateur

Si l'interface entre le contrôleur et l'appareil est standardisée (ANSI, IEEE ou ISO), alors les fabricants indépendants peuvent produire des contrôleurs et des appareils compatibles. Par exemple : lecteurs IDE ou SCSI.

Le système d'exploitation ne s'occupe généralement pas de l'appareil, mais du contrôleur. En règle générale, le contrôleur exécute des fonctions simples, par exemple, lors de la lecture à partir d'un disque, il convertit le flux binaire en blocs constitués d'octets, surveille et corrige les erreurs, la somme de contrôle du bloc est vérifiée si elle correspond à celle spécifiée. dans l'en-tête du secteur, alors le bloc est lu sans erreur, sinon il est relu.

9.1.3 E/S mappées par adresse mémoire

Chaque contrôleur dispose de plusieurs registres utilisés pour communiquer avec le processeur central. À l'aide de ces registres, le système d'exploitation contrôle (lit, écrit, allume, etc.) et détermine l'état (préparation) de l'appareil.

De nombreux appareils disposent d'un tampon de données (par exemple : mémoire vidéo).

Implémentations d'accès aux registres de contrôle et aux tampons :

• Numéro de port d'E/S - attribue un entier de 8 ou 16 bits à chaque registre de contrôle. Les espaces d'adressage de la RAM et des périphériques d'E/S ne se chevauchent pas dans ce schéma.
  Défauts
  - des commandes spéciales sont utilisées pour la lecture et l'écriture, par exemple IN et OUT
  - un mécanisme spécial de protection des processus est requis
  - vous devez d'abord lire le registre de l'appareil dans le registre du processeur

• E/S mappées dans l'espace d'adresse mémoire - les registres sont mappés sur l'espace d'adressage de la mémoire.
  Défauts
  - lors de la mise en cache de la mémoire, les registres des appareils peuvent également être mis en cache
  - Tous les appareils doivent examiner tous les accès à la mémoire pour déterminer ceux auxquels répondre. Sur un bus commun, cela peut être facilement mis en œuvre, mais sur plusieurs bus, des problèmes se poseront.

• mise en œuvre mixte - utilisé dans x86 et Pentium,
  de 0 à 64K est alloué aux ports,
  de 640 à 1M est réservé aux tampons de données.

Méthodes de mise en œuvre de l'accès aux registres de contrôle et aux tampons

9.1.4 Direct accéder À mémoire (DMA - Accès direct à la mémoire)

L'accès direct à la mémoire est implémenté à l'aide de Contrôleur DMA.

Le contrôleur contient plusieurs registres :

• registre d'adresses mémoire
• compteur d'octets
• les registres de contrôle peuvent contenir :
  -Port E/S
  - lire ou écrire
  - porter des unités (octet par octet ou mot par mot)

Sans contrôleur, voici ce qui se produit :

1. Le processeur demande au contrôleur de disque de lire les données dans le tampon,
2. Les données sont lues dans le tampon, le contrôleur vérifie la somme de contrôle des données lues (vérification des erreurs). Le processeur, avant interruption, passe à d'autres tâches.
3. Le contrôleur de disque lance une interruption
4. Le système d'exploitation commence à fonctionner et peut lire les données du tampon dans la mémoire

Fonctionnement du contrôleur DMA

Ce qui suit arrive au contrôleur :

1. Le processeur programme le contrôleur (quelles données déplacer et où)
2. Le processeur demande au contrôleur de disque de lire les données dans le tampon
3. Les données sont lues dans le tampon, le contrôleur de disque vérifie la somme de contrôle des données lues (le processeur, avant interruption, passe à d'autres tâches).
4. Le contrôleur DMA envoie une requête de lecture au contrôleur de disque
5. Le contrôleur de disque fournit des données au bus, l'adresse mémoire est déjà sur le bus, les données sont écrites en mémoire
6. Une fois l'écriture terminée, le contrôleur de disque envoie un accusé de réception au contrôleur DMA.
7. Le contrôleur DMA augmente l'adresse utilisée et diminue la valeur du compteur d'octets
8. Tout est répété à partir de l'étape 4 jusqu'à ce que la valeur du compteur devienne nulle.
9. Le contrôleur DMA lance une interruption

Le système d'exploitation n'a pas besoin de copier les données en mémoire, elles y sont déjà.

9.1.5 Interruptions

Une fois que le périphérique d'E/S a commencé à fonctionner, le processeur passe à d'autres tâches.

Pour signaler au processeur que le travail est terminé, l'appareil lance une interruption en plaçant un signal sur la ligne de bus dédiée de l'appareil (plutôt que sur un fil dédié).

Contrôleur d'interruption - gère les interruptions entrantes des appareils.

1. S'il n'y a aucune interruption en attente, l'interruption est exécutée immédiatement.
2. S'il y a des interruptions non gérées, le contrôleur ignore l'interruption. Mais l'appareil continue de maintenir le signal d'interruption sur le bus jusqu'à ce qu'il soit traité.

Interruption du fonctionnement

Algorithme de travail :

• L'appareil définit un signal d'interruption
• Le contrôleur d'interruption lance une interruption en indiquant le numéro de périphérique
• Le processeur commence à effectuer le traitement des interruptions en appelant la procédure
• Cette procédure accuse réception d'une interruption au contrôleur d'interruption.

9.2 Principes du logiciel d'E/S

9.2.1 Tâches logicielles d'E/S

Les principales tâches que le logiciel d'E/S doit résoudre :

• Indépendance vis-à-vis des appareils - par exemple, un programme lisant les données d'un fichier n'a pas à penser à ce qu'il lit (CD, disque dur, etc.). Tous les problèmes doivent être résolus par le système d'exploitation.
• Dénomination uniforme : le nom du fichier ou du périphérique ne doit pas différer. (Sur les systèmes UNIX, cela est fait textuellement).
• Gestion des erreurs : les erreurs peuvent être détectées au niveau du contrôleur, du pilote, etc.
• Transfert de données - synchrone et asynchrone(dans ce dernier cas, le processeur démarre le transfert de données et passe à d'autres tâches jusqu'à son interruption).
• Mise en mémoire tampon
• Le problème des périphériques dédiés (imprimante) et non dédiés (disque) - l'imprimante ne doit être fournie qu'à un seul utilisateur et le disque à plusieurs. Le système d'exploitation doit résoudre tous les problèmes qui surviennent.

Les trois principales manières d'effectuer des opérations d'E/S sont :

• E/S logicielles
• E/S pilotées par interruption
• E/S utilisant DMA

Regardons-les de plus près.

9.2.2 E/S logicielles

Dans ce cas, le processeur central fait tout le travail.

Examinons le processus d'impression de la chaîne ABCDEFGH à l'aide de cette méthode.

Étapes pour imprimer la chaîne ABCDEFGH

Algorithme d'impression :

1. La chaîne d'impression est collectée dans l'espace utilisateur.
2. En appelant un appel système, le processus obtient une imprimante.
3. Lors de l'appel d'un appel système, un processus demande qu'une chaîne soit imprimée sur une imprimante.
4. Le système d'exploitation copie la chaîne dans un tableau situé en mode noyau.
5. Le système d'exploitation copie le premier caractère dans le registre de données de l'imprimante, qui est mappé en mémoire.
6. Le symbole est imprimé sur papier.
7. Le pointeur est placé sur le caractère suivant.
8. Le processeur attend que le bit prêt de l'imprimante soit défini sur prêt.
9. Tout se répète.

Lorsque vous utilisez un tampon d'imprimante, la ligne entière est d'abord copiée dans le tampon, puis l'impression commence.

9.2.3 E/S déclenchées par interruption

Si dans l'exemple précédent le tampon n'est pas utilisé et que l'imprimante imprime 100 caractères par seconde, alors chaque caractère prendra 10 ms, pendant lequel le processeur sera inactif, attendant que l'imprimante soit prête.

Regardons le même exemple, mais avec une légère amélioration.

Algorithme d'impression :

1. Il en va de même pour le point 8.
2. Le processeur n'attend pas que l'imprimante soit prête, mais appelle le planificateur et passe à une autre tâche. Le processus d'impression est bloqué.
3. Lorsque l'imprimante est prête, elle envoie une interruption au processeur.
4. Le processeur passe au processus d'impression.

9.2.4 E/S utilisant DMA

L'inconvénient de la méthode précédente est qu'une interruption se produit à chaque fois qu'un caractère est imprimé.

L'algorithme n'est pas différent, mais le contrôleur DMA fait tout le travail.

9.3 Niveaux de logiciel et fonctions E/S

Quatre niveaux d'E/S :

Niveaux d'E/S

9.3.1 Gestionnaires d'interruptions

Les interruptions doivent être cachées aussi profondément que possible dans les profondeurs du système d'exploitation, afin que le moins de parties possible du système d'exploitation aient à les gérer. Il est préférable de bloquer le pilote qui a démarré les E/S.

Algorithme:

1. Le pilote commence une opération d'E/S.
2. Le conducteur se bloque
   - en exécutant la procédure down sur le sémaphore
   - en exécutant la procédure d'attente sur la variable d'état
   - en exécutant la procédure de réception sur le message
3. Une interruption se produit
4. Le gestionnaire d'interruption commence à fonctionner
5. Le gestionnaire d'interruption peut débloquer le pilote (par exemple, en exécutant la procédure up sur le sémaphore)

9.3.2 Pilotes de périphérique

Pilote de périphérique - requis pour chaque périphérique. Différents systèmes d'exploitation nécessitent différents pilotes.

Les pilotes doivent faire partie du noyau (dans un système monolithique) pour accéder aux registres du contrôleur.

C’est l’une des principales raisons pour lesquelles les systèmes d’exploitation tombent en panne. Parce que les pilotes sont généralement écrits par les fabricants de périphériques et insérés dans le système d'exploitation.

Emplacement logique des pilotes de périphériques. En fait, l'échange de données entre les contrôleurs et les pilotes s'effectue via le bus.

Les pilotes doivent interagir avec le système d'exploitation via des interfaces standard.

Interfaces standard que les pilotes doivent prendre en charge :

• Pour les appareils bloqués
• Pour les appareils de caractères

Auparavant, pour installer le noyau, il fallait recompiler les noyaux système.

De nos jours, les systèmes d’exploitation chargent principalement des pilotes. Certains pilotes peuvent être chargés à chaud.

Fonctions exécutées par les pilotes :

• traiter les demandes de lecture ou d'écriture
• initialisation de l'appareil
• gestion de l'énergie des appareils
• réchauffer l'appareil (scanner)
• allumer l'appareil ou démarrer le moteur

9.3.3 Logiciel d'E/S indépendant de l'appareil

Caractéristiques du logiciel d'E/S indépendantes du périphérique :

• Interface uniforme pour les pilotes de périphériques,
• Mise en mémoire tampon
• Messages d'erreur
• Saisir et libérer les appareils attribués (verrouillage)
• Taille de bloc indépendante du périphérique

Interface cohérente pour les pilotes de périphériques

En plus de l'interface, cela inclut également des problèmes

• dénomination de l'appareil
• protection de l'appareil

Mise en mémoire tampon

Examinons quelques exemples de mise en mémoire tampon.

a) Entrée sans tampon - une interruption se produit après la saisie de chaque caractère

b) Mise en mémoire tampon dans l'espace utilisateur - les pages de mémoire nécessaires doivent être conservées chargées dans la mémoire physique.

c) Mise en mémoire tampon dans le noyau avec copie dans l'espace utilisateur - la page n'est chargée que lorsque le tampon du noyau est plein, les données du tampon du noyau vers le tampon utilisateur sont copiées en une seule opération. Le problème peut survenir lorsque le tampon du noyau est plein et que la page du tampon utilisateur n'a pas encore été chargée.

d) Double tampon dans le noyau - si un tampon est plein et pendant qu'il est en cours de pagination, les caractères sont écrits dans le deuxième tampon.

Messages d'erreur

Le plus grand nombre d'erreurs proviennent des opérations d'E/S, elles doivent donc être identifiées le plus tôt possible. Les erreurs peuvent être très différentes selon les appareils.

Capturer et libérer les appareils alloués

Pour les appareils (une imprimante) avec lesquels un seul processus doit fonctionner à la fois, la possibilité d'acquérir et de libérer des appareils est nécessaire. Lorsqu'un processus a occupé l'appareil, les autres font la queue.

Taille de bloc indépendante du périphérique

La taille des blocs doit être la même pour les niveaux supérieurs et ne pas dépendre des périphériques (taille des secteurs sur le disque).

9.4. Logiciel d'E/S de l'espace utilisateur

Fonctions de ce logiciel :

• Accéder aux appels système d'E/S (via les procédures de la bibliothèque).
• Formater l'entrée/la sortie (changer le format, par exemple, en ASCII)
• Spooling (pour les appareils dédiés) - un processus (par exemple, un démon d'impression) et un répertoire spooler sont créés.

Résumé des niveaux et fonctions d'E/S

Niveaux et principales fonctions du système d'entrées/sorties

Sous-système d'E/S de base sert d'intermédiaire entre les processus du système informatique et un ensemble de pilotes. Les appels système pour effectuer des opérations d'E/S sont transformés par celui-ci en appels aux fonctions du pilote de périphérique requis. Cependant, les responsabilités sous-système de base ne se limitent pas à effectuer uniquement les actions de traduction d'un appel système général en un appel à une fonction de pilote privé. Sous-système de base fournit au système informatique des services tels que le support blocage, non bloquant Et appels système asynchrones, mise en mémoire tampon Et mise en cache données d'entrée et de sortie, mise en œuvre du spooling et capture exclusive des périphériques externes, gestion des erreurs et interrompt survenant lors des opérations d'E/S, planifier la séquence de requêtes pour effectuer ces opérations. Examinons de plus près ces services.

Appels système bloquants, non bloquants et asynchrones

Tous les appels système associés à la mise en œuvre des opérations d'E/S peuvent être divisés en trois groupes selon les méthodes de mise en œuvre de l'interaction entre le processus et le périphérique d'E/S.

· Le premier groupe, le plus familier à la plupart des programmeurs, comprend bloquer les appels système. Comme son nom l'indique, l'utilisation d'un tel appel conduit au blocage du processus qui l'a initié, c'est-à-dire que le processus est transféré par le système d'exploitation depuis l'état exécution dans un état attente. Une fois que toutes les opérations d'E/S spécifiées par l'appel système sont terminées, le système d'exploitation fait passer le processus hors d'état. attente dans un état préparation. Une fois le processus sélectionné à nouveau pour exécution, ce sera l'endroit où se produira le retour final de l'appel système. Un cas typique d'utilisation d'un tel appel système est lorsqu'un processus doit recevoir une quantité strictement définie de données d'un appareil, sans laquelle il ne peut pas effectuer de travail supplémentaire.

· Le deuxième groupe comprend appels système non bloquants. Leur nom ne reflète pas exactement l’essence du problème. Dans le cas le plus simple, le processus appliqué appel non bloquant, n'est pas transféré à l'État attente du tout. L'appel système revient immédiatement, après avoir terminé complètement, partiellement ou pas du tout les opérations d'E/S qui lui sont assignées, selon la situation actuelle (état de l'appareil, disponibilité des données, etc.). Dans des situations plus complexes, le processus peut être bloqué, mais la condition pour le débloquer est l'achèvement de toutes les opérations nécessaires ou la fin d'un certain laps de temps. Application typique peut être une vérification périodique de la réception des informations du clavier lors de l'exécution de calculs à forte intensité de main-d'œuvre.

· Le troisième groupe comprend appels système asynchrones. Le procédé utilisé appel système asynchrone, n'y est jamais bloqué. L'appel système lance les opérations d'E/S nécessaires et revient immédiatement, après quoi le processus poursuit ses activités normales. Le système d'exploitation informe ensuite le processus que l'opération d'E/S est terminée en modifiant les valeurs de certaines variables, en lui envoyant un signal ou un message, ou d'une autre manière. Il est nécessaire de bien comprendre la différence entre non bloquant Et appels asynchrones. Appel système non bloquant pour effectuer l'opération lire reviendra immédiatement, mais peut lire le nombre d'octets demandé, un nombre plus petit ou aucun. Appel système asynchrone car cette opération reviendra également immédiatement, mais le nombre d'octets requis sera tôt ou tard lu dans son intégralité.

Mise en mémoire tampon et mise en cache

Sous tampon fait généralement référence à une certaine zone de mémoire pour stocker des informations lors de l'échange de données entre deux appareils, deux processus ou un processus et un appareil. L'échange d'informations entre deux processus appartient au domaine de la coopération de processus et nous avons examiné son organisation en détail dans le cours correspondant. Nous nous intéresserons ici à l'utilisation de buffers dans le cas où l'un des participants à l'échange est un appareil externe. Il y a trois raisons qui conduisent à l'utilisation de tampons dans .

· Première raison mise en mémoire tampon– ce sont les différentes vitesses de réception et de transmission des informations dont disposent les participants à l’échange. Prenons par exemple le cas de la transmission d'un flux de données d'un clavier vers un modem. La vitesse à laquelle le clavier fournit des informations est déterminée par la vitesse de frappe humaine et est généralement nettement inférieure à la vitesse de transmission des données du modem. Afin de ne pas occuper le modem pendant tout le temps de frappe, le rendant inaccessible aux autres processus et appareils, il est conseillé d'accumuler les informations saisies dans un tampon ou plusieurs tampons de taille suffisante et de les envoyer via le modem une fois les tampons remplis. .

· Deuxième raison mise en mémoire tampon– il s’agit de différentes quantités de données qui peuvent être acceptées ou reçues par les participants à l’échange à la fois. Prenons un autre exemple. Laissez les informations être fournies par le modem et enregistrées sur le disque dur. En plus d'avoir des vitesses de transaction différentes, un modem et un disque dur sont des types d'appareils différents. Le modem est dispositif de caractères et génère des données octet par octet pendant que le disque est bloquer l'appareil et pour effectuer une opération d'écriture pour celui-ci, il est nécessaire d'accumuler le bloc de données nécessaire dans le tampon. Plusieurs tampons peuvent également être utilisés ici. Après avoir rempli le premier tampon, le modem commence à remplir le second, simultanément à l'écriture du premier sur le disque dur. Étant donné que la vitesse du disque dur est des milliers de fois supérieure à la vitesse du modem, au moment où le deuxième tampon sera plein, l'opération d'écriture du premier sera terminée et le modem pourra à nouveau remplir le premier tampon. en même temps que l'écriture du second sur le disque.

· Troisième raison mise en mémoire tampon est associé à la nécessité de copier les informations des applications qui effectuent des E/S vers le tampon du noyau du système d'exploitation et inversement. Disons qu'un processus utilisateur souhaite afficher des informations de son espace d'adressage sur un périphérique externe. Pour ce faire, il doit exécuter un appel système avec le nom générique write, en passant en paramètres l'adresse de la zone mémoire où se trouvent les données et sa taille. Si un périphérique externe est temporairement occupé, il est possible qu'au moment où il est libéré, le contenu de la zone requise soit corrompu (par exemple, lors de l'utilisation d'une forme asynchrone d'appel système). Pour éviter de telles situations, le moyen le plus simple consiste à copier les données nécessaires au début de l'appel système dans le tampon du noyau du système d'exploitation, situé en permanence dans la RAM, et à les envoyer au périphérique à partir de ce tampon.

Sous le mot cache(cash - "cash"), dont nous ne considérerons pas ici l'étymologie, est généralement compris comme une zone de mémoire rapide contenant une copie de données située quelque part dans une mémoire plus lente, destinée à accélérer le fonctionnement du système informatique. Nous sommes tombés sur ce concept en considérant la hiérarchie de la mémoire. DANS sous-système d'E/S de base Il ne faut pas confondre les deux notions mise en mémoire tampon Et mise en cache, bien que souvent la même zone mémoire soit allouée pour exécuter ces fonctions. Un tampon contient souvent le seul ensemble de données existant sur le système, tandis qu'un cache contient par définition une copie de données qui existent ailleurs. Par exemple, un tampon utilisé par le sous-système sous-jacent pour copier les données de l'espace utilisateur d'un processus vers le disque peut à son tour être utilisé comme cache pour ces données si les opérations de modification et de relecture sur le bloc sont effectuées suffisamment fréquemment.

Fonctions mise en mémoire tampon Et mise en cache n'ont pas besoin d'être localisés dans sous-système d'E/S de base. Ils peuvent être partiellement implémentés dans les pilotes et même dans contrôleurs de périphériques, secret envers sous-système de base.

Mise en file d'attente et détournement d'appareils

À propos du concept mise en file d'attente nous avons parlé dans le premier cours de notre cours d'un mécanisme qui permettait pour la première fois de combiner des opérations d'E/S réelles d'une tâche avec l'exécution d'une autre tâche. Nous pouvons maintenant définir ce concept plus précisément. Par spool, nous entendons un tampon contenant des données d'entrée ou de sortie vers un périphérique qui doivent être évitées entre différents processus entrelaçant son utilisation. Certes, dans les systèmes informatiques modernes, le spool n'est pratiquement pas utilisé pour la saisie de données, mais est principalement destiné à accumuler des informations de sortie.

Considérons une imprimante comme un périphérique externe. Bien qu'une imprimante ne puisse pas imprimer simultanément des informations provenant de plusieurs processus, il peut être souhaitable de permettre aux processus de sortir vers l'imprimante en parallèle. Pour ce faire, le système d'exploitation, au lieu d'envoyer des informations directement à l'imprimante, accumule les données de sortie dans des tampons sur disque, organisés sous forme de fichier spool distinct pour chaque processus. Une fois le processus terminé, le fichier spool correspondant est mis en file d'attente pour l'impression réelle. Le mécanisme qui garantit de telles actions est appelé spooling.

Certains systèmes d'exploitation, au lieu d'utiliser le spooling pour éliminer les conditions de concurrence, utilisent un mécanisme d'acquisition exclusive de périphériques par processus. Si l'appareil est libre, alors l'un des processus peut en prendre possession exclusive. Dans ce cas, tous les autres processus tentant d'effectuer des opérations sur cet appareil seront soit bloqués (transférés vers le attente), ou recevra des informations sur l'impossibilité d'effectuer l'opération jusqu'à ce que le processus qui a capturé l'appareil se termine ou informe explicitement le système d'exploitation qu'il refuse de l'utiliser.

Fournir un mécanisme de mise en file d'attente et de capture de périphérique est la prérogative sous-système d'entrée/sortie de base.

Gestion des interruptions et des erreurs

Si, lorsque vous travaillez avec un périphérique externe, le système informatique n'utilise pas la méthode d'interrogation de son état, mais utilise le mécanisme interrompt, puis quand interrompt, comme nous l'avons dit plus tôt, le processeur, ayant partiellement conservé son état, transfère le contrôle à un programme de traitement spécial interrompt.

Même procédure de traitement interrompt peut être utilisé pour plusieurs périphériques d'E/S (par exemple, si ces périphériques partagent la même ligne interrompt, allant d'eux à contrôleur d'interruption), donc la première action du programme de traitement lui-même est de déterminer quel appareil a émis interrompre. Connaissant l'appareil, nous pouvons identifier le processus qui a initié l'opération correspondante. Parce que interrompre se produit à la fois lors d'une exécution réussie et infructueuse, la prochaine chose que nous devons faire est de déterminer si l'opération s'est terminée avec succès en vérifiant la valeur bit d'erreur V registre de statut appareils. Dans certains cas, le système d'exploitation peut prendre certaines mesures pour compenser l'erreur survenue. Par exemple, si une erreur de lecture de disquette se produit, vous pouvez essayer d'exécuter la commande plusieurs fois. Si la compensation d'erreur n'est pas possible, le système d'exploitation informera ensuite le processus qui a demandé l'opération (par exemple, avec un code retour spécial provenant d'un appel système). Si ce processus a été bloqué avant de terminer l'opération terminée, alors le système d'exploitation le met dans l'état préparation. S'il existe d'autres requêtes non satisfaites adressées au périphérique libéré, le système d'exploitation peut lancer l'exécution de la requête suivante, tout en informant simultanément le périphérique que interrompre traité. C'est en fait le traitement interrompt se termine et le système peut commencer à planifier l’utilisation du processeur.

Actions de traitement interrompt et la compensation des erreurs survenues peut être partiellement transférée sur les épaules du conducteur correspondant. Pour ce faire, l'interface entre conducteur Et sous-système d'entrée/sortie de base ajouter une fonction supplémentaire - la fonction de traitement interrompt intr.

Planification des requêtes

Lors de l'utilisation appel système non bloquant Il se peut que l'appareil souhaité soit déjà occupé à effectuer certaines opérations. Dans ce cas appel non bloquant peut revenir immédiatement sans terminer les commandes demandées. Lors de l'organisation d'une demande d'exécution d'opérations d'E/S à l'aide de blocage ou appel asynchrone Si un appareil est occupé, il devient nécessaire de mettre en file d'attente une requête vers cet appareil. De ce fait, chaque appareil est associé à une liste de requêtes non satisfaites provenant des processus de l'état attentes et les requêtes s'exécutant de manière asynchrone. État attente est divisé en un ensemble de files d'attente de processus attendant divers périphériques d'E/S (ou attendant des changements dans les états de divers objets - sémaphores, files d'attente de messages, variables de condition dans les moniteurs, etc. - voir leçon 6).

Après avoir terminé la requête en cours, le système d'exploitation (lors du traitement de la demande émergente) interrompt) doit décider laquelle des demandes de la liste doit être ensuite satisfaite et lancer son exécution. Tout comme pour sélectionner le prochain processus à exécuter parmi une liste de processus prêts, nous avons dû effectuer une planification de processus à court terme, nous devons ici planifier l'utilisation des appareils, en utilisant une sorte d'algorithme de planification. Les critères et les objectifs d'une telle planification diffèrent peu des critères et des objectifs de la planification des processus.

La tâche de planifier l'utilisation de l'appareil est généralement confiée à sous-système d'entrée/sortie de base Cependant, pour certains appareils, les meilleurs algorithmes de planification peuvent être étroitement liés aux détails de leur fonctionnement interne. Dans de tels cas, l'opération de planification est déplacée dans le pilote de périphérique correspondant, car ces détails sont masqués au sous-système sous-jacent. Pour ce faire, une autre fonction spéciale est ajoutée à l'interface du pilote, qui sélectionne la requête suivante - la fonction stratégie

9. 5 . Les principes qui sous-tendent le sous-système de contrôle d'E/S sous UNIX

1. Ce sous-système est construit de manière uniforme avec le sous-système de gestion des données (système de fichiers). L'utilisateur dispose d'une méthode d'accès unifiée à la fois à l'interface utilisateur et aux fichiers. Un fichier sous UNIX OS est compris comme un ensemble de données sur un disque, un terminal vidéo, etc. tout PU est considéré comme un fichier spécial. Lorsqu'un processus logiciel demande de sortir des données vers un fichier spécial, le système d'exploitation intercepte la demande et transmet les données au périphérique approprié. La lecture des données d'un fichier spécial est organisée de la même manière : il s'agit de la réception de données du panneau de commande. Ainsi, l'accès, par exemple, à un fichier disque et à un fichier d'affichage spécial est assuré par le même ensemble d'appels système.

2. Une autre caractéristique du sous-système d'E/S sous UNIX est qu'il fonctionne comme un système synchrone. Tout processus logiciel nécessitant une saisie est suspendu au point où il a émis la demande jusqu'à ce que l'opération de saisie à partir du fichier spécial spécifié soit terminée. Lors de la sortie, le processus s'arrête au point où la sortie est demandée jusqu'à ce que la sortie soit acceptée par le système dans le tampon de l'utilisateur. Cette organisation des entrées-sorties conduit à une augmentation de l'efficacité d'utilisation du temps CPU dans un mode de fonctionnement d'un ordinateur multi-programmes grâce à une réduction des temps d'arrêt du CPU. A noter que dans les systèmes temps réel (RTS), le principe de fonctionnement asynchrone du sous-système d'entrée-sortie est plus souvent utilisé, car dans ce cas le temps de réponse du RTS aux événements nécessitant un traitement immédiat est réduit.

3. Pour contrôler les PU dans le système d'exploitation UNIX, 2 types d'interfaces avec ces PU sont utilisés : orientées octets et orientées bloc. L'interface orientée blocs permet la communication avec les PU, qui peuvent être adressées sous la forme d'une séquence de blocs de 512 octets. Ces PU sont principalement des VZU. La base pour organiser une telle interface est le système de mise en mémoire tampon pris en charge dans l'OP. L'interface orientée octet est utilisée pour accéder au périphérique d'impression, au clavier d'affichage et à certains autres périphériques, et n'utilise pas de mise en mémoire tampon.

4. Le système de contrôle d'E/S comprend également des pilotes et un ensemble de tables spéciales pour la connexion logique du noyau du système d'exploitation aux pilotes de divers périphériques. Chaque driver contient 2 parties et peut desservir plusieurs appareils du même type.

La première partie du pilote contient un ensemble de modules logiciels permettant d'effectuer des opérations d'ouverture, de fermeture, de lecture et d'écriture de fichiers spéciaux, ainsi que de contrôler les modes de fonctionnement spéciaux de l'unité de contrôle. Pour commencer à travailler avec un certain appareil, vous devez ouvrir ou créer un fichier spécial associé à cet appareil. L'ouverture d'un fichier est le processus d'établissement d'une association entre le nom du fichier et une variable stockée dans la zone mémoire du processus qui ouvre le fichier. Cette variable, appelée numéro de descripteur de fichier, est utilisée ultérieurement dans les opérations sur le fichier ouvert. Une fois le fichier ouvert, le processus qui l'a ouvert est autorisé à accéder à l'appareil. L'opération de fermeture est à l'opposé de son objectif prévu et entraîne une rupture de la connexion entre le processus logiciel et la PU spécifiée.

La deuxième partie du pilote est le module de traitement des interruptions. Lors du contrôle de la plupart des unités de contrôle sous UNIX OS, la méthode d'interruption est utilisée. Pour un PU orienté octet, une interruption se produit après la transmission d'un octet, pour un PU orienté bloc - après la transmission d'un bloc. Le module de traitement des interruptions, qui fait partie du pilote, soit cesse de fonctionner avec l'unité de contrôle, soit continue de travailler avec elle, lui confiant une nouvelle tâche.

Certains des principes énoncés pour la construction du système d'entrée-sortie du système d'exploitation UNIX ont été implémentés dans des systèmes d'exploitation créés plus tard, par exemple sous MS DOS, fonctionnant sur un ordinateur IBM PC avec un 80x86 MP.

Considérons une autre caractéristique de la construction d'un système d'entrées-sorties. Dans le mode de fonctionnement de l'ordinateur multiprogramme utilisé dans les systèmes RTOS ou à temps partagé, une file de requêtes provenant de différents programmes peut apparaître pour une même unité de contrôle. Pour organiser l'exécution séquentielle par ce centre de contrôle des demandes de service reçues par lui, un tableau spécial doit être organisé dans l'OP, dont le contenu affiche sans ambiguïté à chaque instant l'ordre et le contenu des demandes reçues ; après l'exécution de la prochaine application, les données la concernant sont exclues du tableau considéré. De tels tableaux doivent être organisés pour la plupart des unités de contrôle interagissant avec un ordinateur.