2.8. Exemple d'édition de liens

Il s'agit essentiellement de jouer le rôle de l'éditeur de liens pour calculer les implantations des modules et les valeurs des liens utilisables.
On dispose d'un ensemble de modules définis comme suit:
module PROGRAMME	taille:		332
				liens à satisfaire:	OUVRIR
									LIRE
									FERMER
									EDITER
				adresse lancement:		133
module ETIQUETTE	taille:		128
				liens utilisables:		NOM		  0
									SOCIETE	 32
									ADRESSE	 64
									CODEPOST	 96
									VILLE	101
module LECTURE		taille:		840
				liens utilisables:		OUVRIR	  0
									LIRE		 340
									FERMER	 732
				liens à satisfaire:	NOM
									SOCIETE
									ADRESSE
									CODEPOST
									VILLE
module IMPRESSION	taille:		212
				liens utilisables:		IMPRIMER	  0
module EDITION		taille:		642
				liens utilisables:		EDITER	  0
				liens à satisfaire:	NOM
									SOCIETE
									ADRESSE
									CODEPOST
									VILLE
									IMPRIMER
A- On effectue l'édition de liens des modules PROGRAMME, ETIQUETTE, LECTURE, IMPRESSION et EDITION. Donner, en justifiant brièvement votre réponse:
- les adresses d'implantations de ces modules,
- la taille totale du programme résultant,
- la table des liens après le premier passage,
- l'adresse de lancement du programme résultant.
B- On désire mettre les modules ETIQUETTE, LECTURE, IMPRESSION et EDITION dans une bibliothèque de nom UTIL. Dans quel ordre doit-on les mettre, pour obtenir l'édition de liens correcte, en fournissant le module PROGRAMME et la bibliothèque UTIL à l'éditeur de liens, sachant que ce dernier parcourt séquentiellement la bibliothèque, pour savoir s'il doit incorporer ou non les modules successifs qu'il rencontre. Expliquer le fonctionnement.
Solution de l’exercice 2.8

2.8.1. Question A

L'adresse d'implantation d'un module est 0 pour le premier, et pour les autres, le premier emplacement laissé libre par le module qui le précède, c'est-à-dire, la somme entre son adresse d'implantation et sa taille:
	PROGRAMME	 	   0
	ETIQUETTE		 332
	LECTURE		 460
	IMPRESSION	1300
	EDITION		1512
La taille totale du programme est la somme des tailles de tous les modules, ou encore l'adresse du premier emplacement laissé libre par le dernier module, c'est-à-dire, la somme entre son adresse d'implantation et sa taille, soit 2154.
La table des liens contient tous les identificateurs présents dans les modules, en tant que lien utilisable ou lien à satisfaire, ainsi que éventuellement les noms des modules. De plus, la table associe à tout identificateur rencontré comme lien utilisable dans un module, leur adresse dans le programme, obtenue en ajoutant à leur adresse dans ce module l'adresse d'implantation du module. Enfin aux noms de modules, la table associe l'adresse d'implantation du module.
  *  PROGRAMME	 	   0
     OUVRIR		 460
     LIRE			 800
     FERMER		1192
     EDITER		1512
  *  ETIQUETTE		 332
     NOM			 332
     SOCIETE		 364
     ADRESSE		 396
     CODEPOST		 428
     VILLE		 433
  *  LECTURE		 460
  *  IMPRESSION	1300
     IMPRIMER		1300
  *  EDITION		1512
Les lignes marquées par un “*” ne sont pas toujours dans la table, suivant que l'on utilise ou non la table pour mémoriser les adresses d'implantations des modules.
L'adresse de lancement est la valeur trouvée dans l'un des modules augmentée de l'adresse d'implantation de ce module: 133 + 0 = 133.

2.8.2. Question B

On a le graphe des références suivant:

L'éditeur de liens parcours séquentiellement la bibliothèque pour savoir s'il doit ou non incorporer les modules successifs. Au cours de ce parcours, pour chaque module en bibliothèque, il regarde donc si ce module, par ses liens utilisables, peut satisfaire un lien de la table, encore non satisfait. Si c'est le cas, il ajoute le module à la liste, et effectue le traitement du premier passage sur ce module, c'est-à-dire, définit son implantation, et ajoute ses liens à la table. Si ce module contient un lien à satisfaire qui n'était pas encore dans la table, il doit pouvoir être satisfait par un module qui le suit dans la bibliothèque. Le graphe de la figure montre alors que l'on doit respecter les ordres suivants:
	LECTURE	 précède	  ETIQUETTE
	EDITION	 précède	  ETIQUETTE
	EDITION	 précède	  IMPRESSION
Les ordres possibles sont donc:
	LECTURE EDITION ETIQUETTE IMPRESSION
	LECTURE EDITION IMPRESSION ETIQUETTE
	EDITION LECTURE ETIQUETTE IMPRESSION
	EDITION LECTURE IMPRESSION ETIQUETTE
	EDITION IMPRESSION LECTURE ETIQUETTE