Brevet FR2858074A1 — publié le 20050128

La présente invention concerne un procédé de gestion de l'exécution d'au moins un programme sur plusieurs calculateurs. Plus précisément l'invention concerne un procédé de gestion de l'exécution d'au moins un programme associé à une liste de données d'entrée nécessaires à l'exécution 5 de ce programme, le programme étant adapté pour une exécution distribuée par un gestionnaire de traitement sur plusieurs calculateurs grâce à la distribution de ses données d'entrée. Ce procédé comporte une étape de réception d'une requête d'exécution du programme. On sait que la taille et la complexité des programmes d'ordinateurs augmentent et 10 qu'il est donc nécessaire d'en optimiser le temps de calcul. Une solution pour augmenter la vitesse d'exécution de ces calculs consiste à répartir l'exécution d'un programme sur plusieurs calculateurs selon une méthode connue sous le nom de parallélisation. Chaque calculateur possède un ou plusieurs processeurs pour l'exécution du programme. Cette méthode suppose que les données d'entrées du 15 programme sont décorrélées, de façon à pouvoir les traiter séparément. Ainsi, il est possible de distribuer l'exécution de ce programme sur plusieurs calculateurs, chacun d'eux effectuant partiellement le calcul en ne tenant compte que d'une partie des données d'entrée. Ensuite les différents résultats donnés par chacun des calculateurs sont combinés pour former un résultat final. Le problème d'une telle distribution de l'exécution d'un programme consiste en ce qu'elle ne tient en général pas compte d'informations sur les capacités de calcul respectives des calculateurs. Ainsi, si l'un des calculateurs a une capacité de calcul inférieure aux autres, il risque d'être entièrement sollicité lorsqu'un calcul complexe est lancé, au point d'arriver à saturation et de retarder ainsi le résultat final de ce calcul, alors 25 que d'autres calculateurs de capacité plus grande ne sont que partiellement sollicités. L'invention a pour but de remédier à cet inconvénient en fournissant un procédé de gestion de l'exécution d'un programme, capable de réguler la distribution de l'exécution du programme sur les différents calculateurs en profitant au mieux des capacités des calculateurs disponibles. A cet effet, I'invention a pour objet un procédé de gestion de l'exécution d'au moins un programme associé à une liste de données d'entrée nécessaires à l'exécution de ce programme, le programme étant adapté pour une exécution distribuée par un gestionnaire de traitement sur plusieurs calculateurs grâce à la distribution de ses données d'entrée, comportant une étape de réception d'une requête d'exécution du programme, caractérisé 35 en ce qu'il comporte en outre les étapes suivantes: - On sélectionne un calculateur parmi une pluralité de calculateurs selon un critère de disponibilité, a priori, à exécuter cette requête; - On teste si le calculateur sélectionné a les ressources suffisantes pour exécuter la totalité de la requête; - Si non, on sélectionne une partie des données d'entrée sur laquelle on estime que le calculateur sélectionné a les ressources suffisantes pour exécuter le programme, et l'on génère à partir de la requête, une première sous-requête d'exécution du programme sur cette partie sélectionnée des données d'entrée et au moins une seconde sous-requête d'exécution du 10 programme sur le reste des données d'entrée. Le procédé selon l'invention propose, d'une part, le choix d'un calculateur pour exécuter un calcul partiel contributif du résultat final, et d'autre part, l'extraction, pour ce calculateur sélectionné, d'un sous-ensemble optimal des données d'entrée qui seront traitées par celuici afin qu'il ne soit pas mis en état de saturation. Ainsi, I'élection d'un 15 calculateur, combinée à un dimensionnement a priori du calcul qui sera effectué par ce calculateur permet un équilibrage de charge assurant de ne jamais dépasser les limites d'aucun des calculateurs sollicités. Un tel procédé élimine donc tout risque de saturation des calculateurs, quel que soit le nombre de requêtes à exécuter. Un procédé de gestion de l'exécution d'un programme selon l'invention peut en outre 20 comporter l'une ou plusieurs des caractéristiques suivantes: on exécute la première sous-requête sur le calculateur sélectionné; - le critère de disponibilité d'un calculateur à exécuter une requête est directement lié à la comparaison du nombre de processus, issus du gestionnaire de traitement, en cours d'exécution sur ce calculateur au 25 nombre de processus, issus du gestionnaire de traitement, exécutables simultanément sur ce calculateur; - le critère de disponibilité d'un calculateur à exécuter une requête est le rapport du nombre de processus issus du gestionnaire de traitement en cours d'exécution sur ce calculateur sur le nombre de processus issus du 30 gestionnaire de traitement exécutables simultanément sur ce calculateur, et le calculateur sélectionné est celui pour lequel ce rapport est le plus faible; - le critère de disponibilité d'un calculateur à exécuter une requête est pondéré par l'estimation d'un coefficient de charge dépendant des ressources du calculateur, notamment le nombre de processus en cours d'exécution sur le 35 calculateur au moment du test ou la mémoire vive utilisée; - lors de l'étape de test du calculateur sélectionné, on compare le nombre de données d'entrée de la requête à un nombre maximal estimé de données d'entrées que le calculateur sélectionné est a priori capable de traiter; - le nombre maximal de données d'entrées que le calculateur sélectionné est a 5 priori capable de traiter est estimé à partir des paramètres suivants: le nombre de données d'entrée de la requête, la somme sur tous les calculateurs du nombre de processus, issus du gestionnaire de traitement, exécutables simultanément sur chaque calculateur, un nombre de processus, issus du gestionnaire de traitement, exécutables simultanément 10 sur le calculateur sélectionné, et un coefficient d'étalement défini par le gestionnaire de traitement et permettant de diviser en un nombre plus ou moins grand de sous-requêtes l'exécution de la requête; - le nombre maximal de données d'entrées que le calculateur sélectionné est a priori capable de traiter est estimé à partir de la formule suivante: NP, NEe = E(NER. n e.CE + 1) NPi i=1 où: E() est la fonction Partie Entière, NEe est le nombre de données d'entrées que le calculateur sélectionné est a priori capable de traiter, NER est le nombre de données d'entrée de la requête, NPe est le nombre de processus issus du gestionnaire de traitement exécutables simultanément n sur le calculateur sélectionné, NPi est la somme sur tous les calculateurs i=1 du nombre de processus issus du gestionnaire de traitement exécutables simultanément sur chaque calculateur, et CE est le coefficient d'étalement. - les valeurs du coefficient d'étalement et du nombre de processus, issus du gestionnaire de traitement, exécutables simultanément sur un calculateur 25 sont modifiables par l'utilisateur, et/ou de façon dynamique; - la partie des données d'entrée sur laquelle est générée la première sousrequête correspond au nombre maximal de données d'entrées que le calculateur sélectionné est a priori capable de traiter; - on sélectionne la requête parmi une liste de requêtes classées par ordre de 30 priorité; - on renvoie dans la liste des requêtes la seconde sous-requête; et - on affecte à chaque requête de la liste un coefficient de priorité, et les requêtes de coefficients de priorité égaux sont classées par ordre d'arrivée dans la liste. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés dans lesquels: - la figure 1 représente un schéma structurel d'un système de gestion pour la mise en oeuvre d'un procédé selon l'invention; - la figure 2 illustre les étapes successives d'un procédé de gestion de l'exécution d'un programme selon l'invention; 10 la figure 3 représente un schéma fonctionnel de la combinaison des résultats partiels d'une requête exécutée selon le procédé de gestion de la figure 2; On a représenté sur la figure 1 un système comportant un terminal utilisateur 10, un gestionnaire de traitement 12 et des calculateurs 141, .... 14n. On entend ici par gestionnaire de traitement 12 un serveur de gestion de 15 traitement. Mais on pourrait aussi désigner par cette expression un logiciel installé sur un tel serveur. Le terminal utilisateur 10 est par exemple un micro-ordinateur de type classique adapté pour émettre des requêtes d'exécution de programmes vers le gestionnaire de traitement 12. Le gestionnaire de traitement 12 est lui aussi un micro-ordinateur de type classique, comportant des moyens de stockage, tels qu'une mémoire 15, pour le stockage au moins temporaire d'une liste d'attente 17 de requêtes en provenance d'un ou plusieurs terminaux utilisateurs tels que le terminal 10, et pour le stockage de résultats 50 au moins partiels provenant de l'exécution de requêtes issues de la liste 17. Chaque calculateur 14j est relié au gestionnaire de traitement 12 et est muni d'au moins un processeur. Ainsi, comme on le voit sur la figure 1, le calculateur 14, comporte un seul processeur 161, le calculateur 142 comporte quatre processeurs 162, 163, 164, 165 et le calculateur 14n comporte deux processeurs 16m1- et 16m. Les calculateurs ne sont donc pas tous identiques: certains sont monoprocesseurs, tandis que d'autres sont 30 biprocesseurs ou multiprocesseurs. Comme on le voit sur la figure 2, lors d'une première étape de saisie 18, un utilisateur rentre sur le terminal utilisateur 10 une requête R1(P, D) d'exécution d'un programme P associé à une liste D de données d'entrée. Cette requête R1(P, D) est ensuite envoyée au gestionnaire de traitement 12 et l'on 35 passe à une étape 22 de classement cette requête R1 dans la liste d'attente 17 de requêtes. La liste d'attente 17 comporte par exemple d'autres requêtes déjà reçues par le gestionnaire de traitement 12, soit du même terminal utilisateur 10, soit d'un autre terminal utilisateur quelconque. Ces requêtes peuvent être par exemple des requêtes d'exécution du même programme P associé à une autre liste de données, ou bien des requêtes d'exécution d'autres programmes associés à d'autres données d'entrée. Pour le bon fonctionnement du procédé selon l'invention, il est important de noter que les données d'entrée figurant dans la liste D de données d'entrée sont décorrélées. La décorrélation de ces données d'entrée signifie qu'il est possible d'effectuer des exécutions du programme P sur chacune d'entre elles de façon séparée. La liste D de 10 données d'entrée peut comporter plusieurs centaines de milliers de données d'entrée, celles-ci étant simples ou multivaluées. La décorrélation de ces données d'entrée est une condition sine qua non de la distribution de l'exécution du programme P sur plusieurs calculateurs 14j. Lors de l'étape 22 de classement, on classe les requêtes de la liste d'attente 17 par 15 ordre de priorité d'exécution. La priorité des requêtes de la liste d'attente 17 peut être définie de différentes façons, telles que par un système de définition a priori des priorités qui consisterait à rentrer un numéro de priorité lors de l'étape 18 de saisie de chaque requête, ou encore, telles que par un principe de traitement du type FIFO consistant à traiter les requêtes par ordre d'arrivée. Après l'étape 22 de classement de la liste d'attente 17, on passe à une étape 24 d'élection d'une requête prioritaire, correspondant à la première requête de la liste d'attente 17. Pour simplifier les notations dans la suite de la description, on suppose que la requête prioritaire est la requête précédemment reçue par le gestionnaire de traitement 12 25 lors de l'étape 18, c'est-à-dire la requête R1(P, D). La requête prioritaire aurait bien sûr pu être l'une des autres requêtes contenues dans la liste 17. Une fois que l'on connaît la requête prioritaire à exécuter, on passe à une étape 26 d'élection d'un calculateur parmi tous les calculateurs 14j, pour traiter au moins une partie de cette requête prioritaire. Le calculateur élu 14e correspond au calculateur le plus 30 disponible parmi tous les calculateurs 14. . Pour choisir le calculateur élu 14e lors de l'étape 26, le gestionnaire de traitement 12 calcule pour chacun des calculateurs 14j la valeur npi/NP1 où npj représente le nombre de processus en cours d'exécution sur le calculateur 141 et NPi le nombre de processus exécutables simultanément sur ce calculateur 14i. Un processus correspond à l'exécution 35 d'un programme par un calculateur sur des données d'entrées associée à ce programme. Le calculateur élu 14e est le calculateur 14j pour lequel la valeur npi/NP1 est la plus petite. Selon un autre mode de réalisation, il est possible de choisir le calculateur le plus disponible selon d'autres critères tels que l'estimation d'un coefficient de charge, calculé 5 dynamiquement sur chaque calculateur en tenant compte des ressources de chaque calculateur telles que le nombre de processus actifs sur le calculateur en cours d'exécution au moment du test ou la mémoire vive utilisée. Dans ce cas, I'étape 26 d'élection du calculateur consiste à toujours choisir le calculateur le moins chargé. Une fois que le calculateur élu 14e est déterminé, on passe à des étapes destinées 10 à déterminer la façon de distribuer l'exécution de la requête prioritaire R,(P, D). Ainsi, lors d'une étape 27, on compare les deux paramètres suivants: NEmin, représentant le nombre minimal de données d'entrées devant être traitées sur tout calculateur 14j lors de l'exécution d'un programme, ce paramètre permettant de ne pas distribuer la requête prioritaire sur plus d'un 15 calculateur si celle-ci est jugée petite a priori (c'est à dire acceptable en totalité par le calculateur le plus petit); - NER correspondant au nombre total de données d'entrée que la requête prioritaire R,(P, D) doit traiter, c'est à dire au nombre de données d'entrées figurant dans la liste D. Si NER L'étape 28 d'exécution de la requête prioritaire R1(P, D) est suivie éventuellement d'une étape 29 de traitement de résultats, comportant par exemple le stockage, le formatage et l'affichage des résultats sur l'interface du terminal utilisateur 10. Si NER> NEmin, on passe alors à une étape 30 de calcul du nombre NEe maximal de 30 données d'entrée que le calculateur élu 14e est a priori capable de traiter. Pour estimer NEe, le gestionnaire de traitement 12 prend en compte différents paramètres: n - -NP, représentant la somme, sur tous les calculateurs 14j, du nombre de processus, issus du gestionnaire de traitement 12, exécutables 35 simultanément sur chaque calculateur 14,; NPe correspondant au nombre de processus, issus du gestionnaire de traitement, exécutables simultanément sur le calculateur élu 14e, et dont la valeur peut être modifiée par l'utilisateur et/ou de façon dynamique; et - CE représentant un coefficient d'étalement défini par le gestionnaire de 5 traitement 12 et dont la valeur peut être modifiée par l'utilisateur, et/ou de façon dynamique, ce coefficient d'étalement permettant, pour l'ensemble des calculateurs, de regrouper en un nombre plus au moins grand de sousrequêtes l'exécution de la requête prioritaire R1(P, D). Le coefficient d'étalement CE est tel que: ZNP, 0 On passe ensuite à une étape de test 31 consistant à comparer le nombre NEe 15 calculé lors de l'étape 30 au nombre total NER de données d'entrée que la requête prioritaire R1(P, D) doit traiter. Cette étape permet de déterminer si le calculateur élu 14e est apte à exécuter la requête prioritaire R1(P, D) dans sa totalité. Si NER Si NER > NEe, c'est-à-dire si le calculateur élu 14e n'a pas les ressources suffisantes pour exécuter la requête prioritaire R1(P, D) dans sa totalité, on passe alors à deux étapes 32 et 34 de génération de sous-requêtes à partir de la requête prioritaire R1(P, D). En effet, la liste D des données d'entrée associée à la requête prioritaire Ri(P, D) ne comportant que des données d'entrée décorrélées, il est possible de diviser la requête en plusieurs sous-requêtes portant sur un sous-ensemble de l'ensemble de données d'entrée D. L'étape 32 consiste à générer une première sous-requête Rs1(P, D1) que l'un des 30 processeurs du calculateur élu 14e est capable de traiter. Cette première sous-requête Rs1(P, D1) est telle que la liste Dl comporte NEe données d'entrée, NEe ayant été estimé au cours de l'étape 30. L'étape 34 consiste à générer une seconde sous-requête Rs2(P, D2), destinée à être exécutée avec les données d'entrée qui ne sont pas comprises dans la liste Di de données d'entrées sur laquelle sera exécutée la sous-requête Rs1(P, D1). D2 est le complément de Dl dans D et comporte NER-NEe données d'entrée. Après l'étape 34, la seconde sous-requête Rs2(P, D2) générée est envoyée dans la liste d'attente 17 des requêtes. Le procédé est alors reporté à l'étape de classement 22 des requêtes de la liste d'attente 17. Après l'étape 32, la première sous-requête Rs1(P, D1) générée est envoyée au calculateur élu 14e qui l'exécute lors d'une étape d'exécution 40 et le procédé est en 10 même temps reporté à l'étape 24 d'élection d'une autre requête prioritaire à traiter. Ensuite, lors d'une étape 42, le calculateur 14e envoie les résultats issus de l'étape au gestionnaire de traitement 12. Cette étape 42 d'envoi des résultats est suivie par une étape 44 de stockage par le gestionnaire de traitement 12 des résultats de l'exécution de la première sous-requête 15 Rs1(P, D1) dans la mémoire 15. Comme on le voit sur la figure 3, I'exécution d'une requête telle que la requête R1(P, D) saisie lors de l'étape 18, peut aboutir, après l'application d'un procédé tel que celui décrit sur la figure 2, à plusieurs étapes 44, 461, 462, .... 46q de stockage de résultats intermédiaires. Les résultats stockés au cours des étapes 44, 46", 462, .. ., 46q sont les 20 résultats de l'exécution de toutes les sous-requêtes générées à partir de la requête RI(P, D) afin de distribuer l'exécution de cette requête RI(P, D) sur plusieurs calculateurs 14j. Après les étapes 44, 461, 462, ..., 46q de stockage des résultats par le gestionnaire de distribution 12, on passe à une étape 48 de combinaison de tous ces résultats en un résultat final 50 de la requête RI(P, D). Le résultat final 50 de la requête R,(P, D) est ensuite envoyé au terminal utilisateur qui traite ces résultats 50 sur son interface lors d'une étape 52 de traitement de résultats comportant notamment le formatage et l'affichage des résultats. Selon un autre mode de réalisation de l'invention, le système de gestion peut exécuter plusieurs programmes P1, P2, ..., Pz transmis sous forme de requêtes par 30 plusieurs terminaux utilisateurs. De façon optionnelle, il est possible de doter le système d'une fonction d'information de l'avancement de l'exécution des requêtes. Un système de messagerie peut rendre compte à chaque client utilisateur, dans le cas où le système comporte plusieurs terminaux utilisateurs 10, de l'état d'avancement de ses requêtes ou de manière globale, 35 de l'état d'avancement de toutes les requêtes à un client administrateur. Enfin, il est possible d'associer d'autres fonctions classiques à ce système de gestion telles qu'un démarrage de l'exécution des requêtes en différé, une gestion de pannes, des mécanismes de synchronisation de requêtes, ou encore une fonction d'arrêt automatique permettant d'arrêter une requête quel que soit son statut, en cours d'exécution ou en file d'attente. Il apparaît clairement qu'un procédé selon l'invention permet de distribuer l'exécution du programme P sur plusieurs calculateurs 14j, les étapes 26, 27, 30 et 31 de calcul du mode de distribution permettant de distribuer ces exécutions de façon optimale afin de réduire le temps global d'exécution. 10 REVENDICATIONS 1. Procédé de gestion de l'exécution d'au moins un programme (P) associé à une liste de données d'entrée (D) nécessaires à l'exécution de ce programme (P), le 5 programme étant adapté pour une exécution distribuée par un gestionnaire de traitement (12) sur plusieurs calculateurs (14f) grâce à la distribution de ses données d'entrée, comportant une étape (18) de réception d'une requête (R1(P, D)) d'exécution du programme (P), caractérisé en ce qu'il comporte en outre les étapes suivantes: - On sélectionne (26) un calculateur (14e) parmi une pluralité de 10 calculateurs (14,) selon un critère de disponibilité, a priori, à exécuter cette requête (R1(P, D)); - On teste (31) si le calculateur sélectionné (14e) a les ressources suffisantes pour exécuter la totalité de la requête (Ri(P, D)); - Si non, on sélectionne (30) une partie (D1) des données d'entrée sur 15 laquelle on estime que le calculateur sélectionné (14e) a les ressources suffisantes pour exécuter le programme (P), et l'on génère (32, 34) à partir de la requête (R,(P, D)), une première sousrequête (Rs1(P, D,)) d'exécution du programme (P) sur cette partie (D) sélectionnée des données d'entrée et au moins une seconde 20 sous- requête (Rs2(P, D2)) d'exécution du programme (P) sur le reste (D2) des données d'entrée. 2. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 1, caractérisé en ce que l'on exécute la première sousrequête (Rs1(P, D)) sur le calculateur sélectionné (14e). 3. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication I ou 2, caractérisé en ce que le critère de disponibilité d'un calculateur (14v) à exécuter une requete (R,(P, D)) est directement lié à la comparaison du nombre (npi) de processus, issus du gestionnaire de traitement (12), en cours d'exécution sur ce calculateur (14j) au nombre (NPj) de processus, issus du gestionnaire de traitement (12), 30 exécutables simultanément sur ce calculateur (14i). 4. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 3, caractérisé en ce que le critère de disponibilité d'un calculateur (14j) à exécuter une requête (RI(P, D)) est le rapport du nombre (npj) de processus, issus du gestionnaire de traitement (12), en cours d'exécution sur ce calculateur (14i) sur le 35 nombre (NPi) de processus, issus du gestionnaire de traitement (12), exécutables simultanément sur ce calculateur (140), et en ce que le calculateur sélectionné (14e) est celui pour lequel ce rapport est le plus faible. 5. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 3 ou 4, caractérisé en ce que le critère de disponibilité d'un calculateur (14) 5 à exécuter une requête (R,(P, D)) est pondéré par l'estimation d'un coefficient de charge dépendant des ressources du calculateur (140), notamment le nombre de processus en cours d'exécution sur le calculateur au moment du test ou la mémoire vive utilisée. 6. Procédé de gestion de l'exécution d'au moins un programme (P) selon l'une quelconque des revendications 1 à 5, caractérisé en ce que, lors de l'étape de test (26) du 10 calculateur sélectionné (14e), on compare le nombre (NER) de données d'entrée de la requête (R1(P, D)) à un nombre (NEe) maximal estimé de données d'entrées que le calculateur sélectionné (14e) est a priori capable de traiter. 7. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 6, caractérisé en ce que le nombre (NEe) maximal de données d'entrées 15 que le calculateur (14e) sélectionné est a priori capable de traiter est estimé à partir des paramètres suivants: - le nombre (NER) de données d'entrée de la requête (RI(P, D)); n - la somme (XNP, ) sur tous les calculateurs (14i) du nombre (NPi) de i=1 processus, issus du gestionnaire de traitement (12), exécutables 20 simultanément sur chaque calculateur (14i); - un nombre (NPe) de processus, issus du gestionnaire de traitement (12), exécutables simultanément sur le calculateur sélectionné (14e); et - un coefficient d'étalement (CE) défini par le gestionnaire de traitement (12) et permettant de diviser en un nombre plus ou moins grand de sous-requêtes 25 I'exécution de la requête (R1(P, D)). 8. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 7, caractérisé en ce que le nombre (NEe) maximal de données d'entrées que le calculateur (14e) sélectionné est a priori capable de traiter est estimé à partir de la formule suivante: NP, NEe = E(NER. " . CE + 1), où E() représente la fonction Partie Entière. Z Npi i=1 9. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 8, caractérisé en ce que les valeurs du coefficient d'étalement (CE) et du nombre (NPe) de processus, issus du gestionnaire de traitement (12), exécutables simultanément sur un calculateur (14f) sont modifiables par l'utilisateur, et/ou de façon dynamique. 10. Procédé de gestion de l'exécution d'au moins un programme (P) selon l'une quelconque des revendications 6 à 9, caractérisé en ce que la partie (Di) des données 5 d'entrée sur laquelle est générée la première sous-requête (Rs1(P, D1)) correspond au nombre (NEe) maximal de données d'entrées que le calculateur sélectionné (14e) est a priori capable de traiter. 11. Procédé de gestion de l'exécution d'au moins un programme (P) selon l'une quelconque des revendications 1 à 10, caractérisé en ce que l'on sélectionne (24) la 10 requête (RI(P, D)) parmi une liste de requêtes (17) classées (22) par ordre de priorité. 12. Procédé de gestion de l'exécution d'au moins un programme (P) selon la revendication 11, caractérisé en ce que l'on renvoie dans la liste des requêtes (17) la seconde sous-requête (Rs2(P, D2)). 13. Procédé de gestion de l'exécution d'au moins un programme (P) selon la 15 revendication 11 ou 12, caractérisé en ce que l'on affecte à chaque requête de la liste un coefficient de priorité, et en ce que les requêtes de coefficients de priorité égaux sont classées (22) par ordre d'arrivée dans la liste (17).