programmation (suite)
Une des multiples méthodes permettant de construire la fonction d’adressage est la méthode dite « par changement de base » : la configuration binaire de la clef est considérée comme étant un nombre binaire. On découpe ce nombre en tranches successives de n bits et l’on construit ainsi un nombre en base 2n = p. Comme on veut, finalement, obtenir une adresse comprise entre 0 et N, il suffit d’exprimer le nombre en base p en un nombre décimal modulo N + 1.
Une telle fonction une fois construite, une clef de recherche étant donnée, l’adresse de la cellule associée à cette clef étant calculée, il faut, pour rendre la méthode complètement opérationnelle, savoir si cette cellule est vide, si elle contient l’élément cherché et, au cas où elle contient un autre élément (collision), quelle politique il convient d’appliquer pour placer (ou retrouver) l’élément associé à la clef de recherche.
Pour savoir si une cellule est vide, on utilise la méthode suivante : préalablement à la création de la table, on a chargé dans chacune des cellules de la zone réservée un caractère spécial (flag) qui ne peut pas être confondu avec un quelconque caractère de la table ; dans ces conditions, l’existence de ce flag dans une cellule prouve que l’état initial de cette dernière n’a pas été modifié et qu’elle peut être considérée comme vide.
Pour résoudre les cas de collision, il existe de nombreuses méthodes.
• La résolution linéaire. Si l’entrée a de la table est occupée, on essaie les entrées a + 1, a + 2, ..., jusqu’à la découverte d’une entrée libre. L’inconvénient de ce procédé est de créer artificiellement des « bouchons », car, si une série de collisions se produit au voisinage de a, les cellules a + 1, ..., seront occupées.
• La résolution linéaire modifiée. Pour pallier cet inconvénient tout en conservant la même idée, on peut procéder ainsi : si N désigne le nombre de cellules de la zone d’implantation de la table, on choisit une fois pour toutes un entier i ne divisant pas N et l’on essaie successivement les entrées a + i, a + 2i, ... (modulo N). [La restriction sur i provient de ce que l’algorithme doit pouvoir permettre de parcourir toutes les cellules.]
• La résolution par quotient linéaire. Cette méthode est analogue à la précédente, à la différence que l’entier i est construit comme quotient de la division de la clef de recherche (considérée comme entier binaire à transcrire sous forme décimale) par N : « clef » = Ni + reste. Compte tenu du caractère aléatoire de i, si l’on désire pouvoir parcourir l’ensemble de la table, il faut choisir N premier. D’autre part, le cas i = 0 est à proscrire (en cette occurrence, on posera par exemple i = 1).
Finalement et quelle que soit la méthode qui a été adoptée pour résoudre les cas de collision, il y a avantage, pour faciliter la recherche, à chaîner les éléments associés à une même entrée lors de leur implémentation.
La préparation du passage en machine
Les ordinateurs modernes sont toujours utilisés sous le contrôle de systèmes d’exploitation, ensembles de programmes destinés à la fois à faciliter le travail du programmeur et à améliorer le rendement de la machine. Or, pour permettre au système d’exploitation de savoir quelle aide le programmeur attend de sa part, il est nécessaire que ce dernier puisse lui fournir des directives et dispose d’un moyen de dialogue avec le système, moyen qui sera en général un langage spécial : le langage de commande des travaux.
Par suite, l’existence de cette supervision des travaux par le système d’exploitation impose au programmeur la rédaction d’un nouveau programme : le programme de commande des travaux qu’il désire confier au système, programme dont les données sont les textes composant le programme initial.
Dans ce programme de commande de travaux, le programmeur doit préciser :
— le traitement à faire subir au programme initial (compilation, exécution, etc.) ;
— les ressources hardware dont ce dernier programme a besoin (place en mémoire centrale, type de mémoires auxiliaires utilisé, place à réserver respectivement sur ces mémoires, etc.) ;
— les fichiers privés qui lui sont nécessaires (bandes magnétiques, disk-packs, etc., réservés à son seul usage et sur lesquels il a préservé des informations).
Les tests et le contrôle de qualité du programme
Aussi soigneux qu’ait été le programmeur, aussi logiques et précis qu’aient été les analystes, il subsiste toujours des possibilités d’erreurs dans le texte d’un programme. En pratique, ces erreurs ne pourront être détectées qu’au cours des passages en machine, et leur recherche en vue de correction fait l’objet de ce que l’on appelle les tests. Elles sont de deux sortes :
— celles que le système ou les traducteurs de langage sont en mesure de diagnostiquer, donc de signaler explicitement, comme les fautes commises dans la rédaction du programme de commande des travaux ainsi que les erreurs de syntaxe faites au cours de l’écriture du programme ;
— celles qui ne pourront être détectées qu’au vu des résultats du programme.
Si la correction des erreurs du premier type est très facile, il est loin d’en être de même des autres, qui, heureusement, sont moins fréquentes ; la recherche de celles-ci s’avère toujours être un travail impossible à automatiser et, comme tel, délicat, pénible et coûteux. En pratique, pour tester un programme, on combine les deux techniques suivantes :
— la méthode statique, qui consiste à des moments choisis par le programmeur à faire imprimer tout ou partie du contenu de la mémoire centrale (dump) ;
— la méthode dynamique, dans laquelle, au cours de certaines étapes de traitement on fait imprimer les valeurs que prennent certaines quantités, puis, on exécute le traitement manuellement et l’on vérifie la concordance des résultats obtenus.
Néanmoins, si l’ensemble des programmes de tests a été bien conçu, on doit pouvoir trouver :
— au niveau des programmes de tests internes, les erreurs de codage acceptables du point de vue de la syntaxe, les oublis d’initialisations locales ;
— au niveau des tests externes de modules, les erreurs de « dimensionnement » des tables, les fautes commises lors de la transmission des arguments ;
— au niveau des tests de phases, les erreurs de chaînage ;
— au niveau des tests globaux du programme, les incohérences de spécifications externes et les oublis d’initialisations globales.