Brevet FR2830162A1 — publié le 20030328

Dispositif de gestion partagée L'invention concerne une attribution de ressource informatique ou de télécommunication partagée entre plusieurs utilisateurs. De façon particulière, elle concerne un dispositif de gestion permettant d'attribuer une ressource à chaque utilisateur. A chaque instant déterminé, ce dispositif sélectionne un utilisateur parmi l'ensemble des utilisateurs demandant une attribution de ressource. Cette sélection s'effectue suivant notamment la valeur d'une échéance (ou attente) associée à chaque utilisateur. En pratique, à chaque utilisateur sélectionné, la ressource est attribuée suivant une quantité de services prédéterminée. Chaque quantité de services prédéterminée est comprise dans une tranche de services limités (temps de traitement partagé ou transmission par paquets). Dans la technique antérieure de EP 98 955 731.9, le dispositif est apte à regrouper les utilisateurs par classes comprenant chacune une mémoire du type FIFO (First In First Out). Ainsi, chaque classe est déterminée suivant un critère de classe correspondant à une valeur de couple standard "paramètre-part, quantité de services maximale". Chaque utilisateur a une priorité sur la ressource qui est représentée par le"paramètre part", aussi qualifiée de"quotepart". Dans une autre technique plus évoluée, la classe attribuée à chaque utilisateur correspond à un couple "paramètre-part, quantité de services maximale"correspon- dant à une valeur prédéterminée. Seuls les premiers utilisateurs en tête de FIFO sont susceptibles d'être sélectionnés par le dispositif. Les utilisateurs en tête de FIFO correspondent aux utilisateurs dont l'échéance est la moins avancée. Dans ces solutions, le temps de traitement de sélection reste indépendant du nombre de connexions. Toutefois, ces solutions ne proposent pas à l'utilisateur ni d'obtenir une quantité de services variable suivant ses besoins, ni de pouvoir faire varier le"paramètre-part". L'invention vise notamment à améliorer la situation. Elle propose à cet effet une structure de mémoires FIFO regroupées en différentes classes de telle sorte que l'utilisateur peut faire varier, suivant certaines conditions, sa quantité de services et son"paramètre-part". L'invention propose un ordonnanceur pour le partage d'une ressource, du type comprenant : - une mémoire capable de stocker, pour des utilisateurs, des quantités d'ordre respectives, dites échéances, - des mémoires de type FIFO, associées chacune à une valeur, dite première valeur d'incrément, pour stocker des identifiants-utilisateur, et - un organe de gestion, capable : * de désigner l'une des mémoires FIFO, dont l'identifiant-utilisateur premier sortant est le "prochain à servir"par la ressource, cette désignation s'effectuant en fonction de premières conditions qui comprennent l'ordre des échéances des utilisateurs premiers sortants, * de recycler l'identifiant-utilisateur dans l'une des FIFO, et * d'augmenter l'échéance d'un utilisateur recyclé de la première valeur d'incrément de la FIFO où se trouve cet utilisateur. De façon à répondre au mieux aux besoins de services des utilisateurs, - l'une au moins des mémoires FIFO est associée en outre à une seconde valeur d'incrément, et - l'organe de gestion comprend un organe de décision de recyclage, capable, après service d'un utilisateur, de réorienter l'identifiant de cet utilisateur vers l'une des FIFO, en fonction de secondes conditions, qui comprennent une comparaison entre la seconde valeur d'incrément de la FIFO où va l'utilisateur et la première valeur d'incrément de la FIFO d'où provient l'utilisateur. L'invention propose un procédé d'ordonnancement pour le partage d'une ressource comprenant les étapes suivantes : a. stocker des identifiants-utilisateur dans des mémoires FIFO associées chacune à une valeur, dite première valeur d'incrément, l'une au moins des mémoires FIFO étant associée en outre à une seconde valeur d'incrément, b. désigner, parmi lesdites mémoires FIFO, une mémoire FIFO dont l'identifiant-utilisateur premier sortant est le "prochain à servir"par la ressource, cette désignation s'effectuant en fonction de premières conditions qui comprennent l'ordre des échéances des utilisateurs premiers sortants, c. recycler l'identifiant-utilisateur en ré-orientant cet identifiant-utilisateur dans l'une des FIFO, en fonction de secondes conditions, qui comprennent une comparaison entre la seconde valeur d'incrément de la FIFO où va l'utilisateur et la première valeur d'incrément de la FIFO d'où provient l'utilisateur, et d. augmenter l'échéance d'un utilisateur recyclé de la première valeur d'incrément de la FIFO où se trouve cet utilisateur. L'invention couvre un module logiciel, qui peut être défini comme comprenant les fonctions pour exécuter les étapes du procédé a. à d. ci-dessus, et/ou comme comprenant les fonctions de l'ordonnanceur défini ci-dessus. L'invention couvre également un système informatique qui peut être défini comme comprenant l'ordonnanceur défini cidessus. Le système informatique comprend en outre un équipement de télécommunication. - la figure 1 illustre schématiquement des interactions entre la ressource, le dispositif-gestionnaire de la ressource et N utilisateurs Ui, u2.... UN (entités utilisatrices), - la figure 2 illustre schématiquement les interactions entre différents éléments que comporte le dispositif et les N entités utilisatrices, - la figure 3 représente schématiquement les attributs d'un utilisateur u quelconque, - la figure 4 représente schématiquement la mémoire de travail du dispositif, - la figure 5 représente un ordinogramme de l'initialisation du gestionnaire selon l'invention, - la figure 6 représente un ordinogramme définissant, pour une valeur donnée de "paramètre-part" d'un utilisateur, les quantités de services attribuables à cet utilisateur, et les classes de délai associées, - la figure 7 représente un ordinogramme d'activation d'un utilisateur selon l'invention, - la figure 8 représente un ordinogramme de sélection du prochain utilisateur selon l'invention, - la figure 9 représente un ordinogramme complétant la figure 8. En annexe 1 sont définies des formules du domaine de l'invention. Les dessins et annexe contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la description, mais aussi contribuer à la définition de l'invention, le cas échéant. Le présent document peut contenir des éléments susceptibles d'une protection par droit d'auteur ou copyright. Le titulaire des droits n'a pas d'objection à la reproduction à l'identique par quiconque de ce document de brevet, tel qu'il apparaît dans les dossiers et/ou publications des offices de brevet. Par contre, il réserve pour le reste l'intégralité de ses droits d'auteur et/ou de copyright. On se réfère tout d'abord à la figure 1 comprenant une ressource 1 telle qu'une liaison de transmission de données ou une unité centrale de traitement, et partagée entre un nombre N d'entités utilisatrices, us,,... Un, par exemple entre N applications d'ordinateurs ou N communications dans des noeuds de réseaux. Un dispositif 2 pour gérer la ressource 1, affecte celle-ci par quantité de services à des entités utilisatrices successivement sélectionnées. Chaque attribution de service à une entité utilisatrice Ux est faite pour une quantité de services choisie : le quantum Qx de cette attribution. L'entité utilisatrice peut consommer ou non la totalité de ce quantum. Sur la figure 2, le dispositif de gestion de la ressource 2 de la figure 1 comprend une liaison entrée/sortie 4, par exemple un bus de communication avec les N entités utilisa- trices. Il comprend également une mémoire de travail 3, où sont enregistrées notamment des données relatives aux entités utilisatrices ul... un, ainsi qu'un moyen de liaison mémoire 5, par exemple une interface mémoire entre la liaison entrée/sortie 4 et la mémoire 3. Enfin, le dispositif décrit comprend un moyen de décision 6 (faisant partie, par exemple, d'une unité centrale de traitement) comprenant, selon l'invention, un organe de décision de pré-sélection 62 entre utilisateurs capable notamment de sélectionner l'une des entités pour que la ressource lui soit affectée et un organe de décision de recyclage 61 capable notamment de réorienter en mémoire, selon certaines conditions, une entité ayant été servie, comme décrit plus loin. L'ensemble constitué de la ressource 1, interface mémoire entre la liaison entrée/sortie 4, le moyen de liaison mémoire 5, et le moyen de décision 6 est appelé organe de gestion 21 travaillant en liaison avec la mémoire 3. L'ensemble formé par l'organe de gestion travaillant en liaison avec la mémoire 3 est désigné comme l'ordonnanceur 22. Le dispositif propose une gestion partagée d'une ressource entre plusieurs utilisateurs. Pour ce faire, la ressource est attribuée successivement à chaque utilisateur suivant, par exemple, des quantités de services Q (u). Chaque quantité de services Q (u) (appelée aussi quantum) peut désigner une durée de services attribuée à un utilisateur. Ainsi, à une entité utilisatrice sélectionnée us, on attribue la durée de services Qs relative à l'exécution d'une tâche par la ressource. D'autre part, un autre paramètre est associé à chaque utilisateur, appelé"paramètre-part", enregistré dans la mémoire de travail 3. Ce "paramètre-part" est associé à chaque entité utilisatrice selon des critères externes au dispositif-gestionnaire de ressource 2. Dans le cas d'une gestion en temps partagé, ces"paramètres- parts" (appelés aussi"charges") sont proportionnels à des vitesses moyennes d'exécution désirées pour chaque entité utilisatrice. Ainsi, afin de respecter une équité de partage entre les entités utilisatrices et de respecter au mieux les besoins de vitesse d'exécution désirés par chaque entité utilisatrice, le gestionnaire de ressource 2 doit attribuer à chaque entité utilisatrice u. des quantités de services Qx, afin que, cumulées sur des durées quelconques, ces quantités de services Qx soient au mieux proportionnelles à la charge Wx de l'entité utilisatrice ux. Ainsi, la charge de la ressource y (t) en fonction du temps t et pour N entités utilisatrices Il... UN, est définie par la relation (1), donnée en annexe 1 de la présente demande. La technique antérieure est présentée dans le document suivant : [1]-' ; Algorithme d'allocation d'une unité centrale pour calculateurs exploités en temps partagé" (R. Després et A. Bache, Annales des communications, p. 19, 1972). La Demanderesse propose un modèle pour la gestion de ressource en temps partagé qui s'applique sur un traitement en parallèle des entités utilisatrices. La ressource est allouée alternativement pour des tâches en cours d'exécution, réclamant un traitement équivalent à la possession complète de la ressource pendant un temps-quantum Q. Chaque tâche est ainsi exécutée d'autant moins vite que le nombre d'entités utilisatrices demanderesses est important. Pour chaque entité utilisatrice nouvellement demanderesse ux, la date d (t) de sa dernière demande de quantum Qx (t) à l'instant t est connue. A partir du quantum Qx (t), la date future fx (t) à laquelle le quantum Qx (t) sera totalement exécutée, peut être évaluée à condition de connaître la charge y (t) de la ressource évoluant dans le temps, tel que défini par la relation (2) de l'annexe 1. Arbitrairement, il est défini une échelle de temps virtuel tel qu'à l'instant tO (t), la charge y (t) de la ressource est nulle à cet instant. Le quantum q (t) est défini dans la relation (3) de l'annexe 1 suivant le temps virtuel to (t). Ainsi, une échéance de fin d'exécution du quantum Qx (t) est estimée suivant la relation (4) ou (5) de l'annexe 1. Pour chaque entité utilisatrice ut, cette échéance Ex (t) progresse d'une valeur Q./W,, à chaque exécution de demande de services de l'entité utilisatrice. D'autre part, le gestionnaire de ressource 2 entretient une heure virtuelle V incrémentée, à chaque exécution de demande de services d'une entité utilisatrice sélectionnée Ug, d'une quantité pV (us) telle que définie dans la relation (6) de l'annexe 1. Afin d'établir un ordre de priorité de satisfaction des demandes des entités utilisatrices, à chaque entité utilisatrice est associé un état d'éligibilité défini dans le document [1]. En plus de cet état d'éligibilité, une comparaison de l'échéance virtuelle de l'entité utilisatrice à l'heure virtuelle V du gestionnaire de ressources doit répondre à certains critères. Le gestionnaire de ressources attribue alors un quantum Qx à l'entité utilisatrice u., éligible et d'échéance virtuelle la plus petite. Cette technique présente un inconvénient majeur : le temps de traitement nécessaire au gestionnaire de ressources pour la sélection d'une entité utilisatrice est dépendant du nombre N d'entités utilisatrices. La Demanderesse a alors proposé des solutions dans les documents suivants : [2]"A packet switching network with graceful saturated operation" (R. Després, International Conference and Computer Communications, P. 345,1972), [3]-EP 98 955 731. 9,"Dispositif d'une gestion de ressource entre plusieurs utilisateurs". Ces documents proposent des solutions complémentaires s'appuyant sur une gestion d'un nombre limité de files d'entités utilisatrices. Ces files sont de type FIFO. Dans le document en référence [2], le gestionnaire de ressources impose aux entités utilisatrices des valeurs de couple standard"charge-quantum". Chaque FIFO correspond également à une valeur de couple standard"charge-quantum". A chaque FIFO correspond une échéance virtuelle et une progression d'échéance virtuelle ainsi qu'un état d'éligibilité. A un instant donné, pour la FIFO éligible dont l'échéance virtuelle est la plus petite, le gestionnaire de ressources attribue un quantum à l'entité en tête de FIFO. Ainsi, le temps de traitement est indépendant du nombre d'entités utilisatrices et seulement dépendant du nombre de FIFO. Toutefois, les valeurs de couple standard"charge-quantum" ne permettent pas d'assurer une équité de partage entre les entités utilisatrices. Ainsi le document en référence [3] définit pour chaque FIFO une classe c associée à un délai d (c). Chaque entité utilisatrice est affectée à une classe telle que le quantum Q (u) maximal (ou attente maximale) désiré par cette entité utilisatrice corresponde au délai d (c) de cette classe telle que Qmax (u) = d (c) xw (u). Ainsi, lorsque le gestionnaire de ressource sélectionne une entité utilisatrice u en tête d'une FIFO de délai d (c) et dont l'échéance virtuelle E (u) est la plus petite parmi celles des entités utilisatrices apparaissant en tête de leur FIFO, le gestionnaire de ressource attribue un quantum Q (u) =d (c) xW (u) à l'entité utilisatrice u sélectionnée. L'échéance virtuelle de chaque entité utilisatrice progresse, après attribution du quantum Q (u) associé à la charge W (u), d'une quantité égale au délai de la classe dans laquelle se trouve l'entité utilisatrice u. Le document en référence [3] propose également un mode de réalisation dans le cas d'un nombre variable d'entités utilisatrices. Dans ce cas, le gestionnaire de ressources distingue deux types de classes : une classe d'entités utilisatrices nouvellement demanderesses et une classe d'entités utilisatrices qui étaient déjà demanderesses avant la demande actuelle. Les échéances des entités utilisatrices nouvellement demanderesses sont alors déterminées à partir d'une variable interne du gestionnaire de ressources, de préférence à partir de l'heure virtuelle V. Toutefois, la technique proposée dans le document en référence [3] ne satisfait pas une entité utilisatrice désirant changer de quantité de services Q et/ou de paramètre-part W au cours du temps. En pratique, dans le cas d'une gestion de transmission par paquet par exemple, un paquet de petite taille peut attendre aussi longtemps qu'un paquet de grande taille pour une même entité utilisatrice. Pour des temps de traitement constants, le but de l'invention est d'atteindre les objectifs d'indépendance à la fois des charges des entités utilisatrices et des quanta des entités utilisatrices. De plus, chaque entité utilisatrice u peut demander un quantum Q et une charge W variables au cours du temps. Le gestionnaire de ressources selon l'invention s'appuie sur une mémoire de travail 3 telle que représentée dans la figure 4. Ainsi, la mémoire de travail 3 est partagée en plusieurs classes i, indexées de 1 à m, notées c (i). Les classes c (i) sont de délais respectifs d (i), ces classes c (i) sont également appelées classes de délai. Chaque entité utilisatrice u est affectée à la classe de délai c (i) telle que, pour une charge W (u) choisie par l'entité utilisatrice, le quantum Q (u), choisi selon des conditions déterminées, réponde à l'inégalité : d (i) L'entité utilisatrice est alors affectée à la classe de délai c (i). Dans le cas d'une nouvelle entité utilisatrice u, celle-ci est affectée à la file FIFO 0 de la classe c (i) (soit la file représentée par c (i, 0)) correspondant à la file des nouveaux utilisateurs. L'échéance virtuelle E (u) de l'entité utilisatrice est incrémentée du délai d (i) de la classe c (i) dans laquelle se trouve l'entité utilisatrice. Après une première attribution de la ressource selon la charge W (u) et le quantum Q (u) choisis par l'entité utilisatrice, cette dernière peut effectuer une nouvelle demande d'attribution de la ressource suivant un nouveau quantum, appelé quantum actuel Qa (u), et/ou une nouvelle charge appelée charge actuelle Wa (u). L'entité utilisatrice u est alors affectée à une nouvelle classe de délai c (j) telle que d (j) Qa (u)/Wa (u) Ainsi, une file c (j, i) dépend du délai d (j), appelé également première valeur d'incrément de la classe c (j) et du délai d (i), appelé également deuxième valeur d'incrément de la classe c (i). On comprendra que chaque classe, indexée de 1 à m, est constituée de m+1 files de type FIFO indexées de 0 à m. La file 0 (également notée c (j, O) dans la classe c (j)) correspond à la file des nouvelles entités utilisatrices et les files indexées de 1 à m correspondent aux files des anciennes entités utilisatrices des classes 1 à m. Dans une réalisation possible, une entité utilisatrice est enregistrée dans une mémoire FIFO sous forme d'un identifiant-utilisateur pouvant être constitué d'attributs de l'entité utilisatrice. Ainsi, pour chaque entité utilisatrice u, sont définis les attributs de la figure 3 comprenant des attributs variables dans le temps : - Q (u, c (i)) la liste des quanta attribuables à l'utilisateur associés aux classes c (i), pour la charge du moment, - Wp (u), la charge précédente choisie de l'entité utilisatrice, - Wa (u), la charge actuelle choisie de l'entité utilisatrice, - Qp (u), le quantum précédent de l'entité utilisatrice - Qa (u) le quantum actuel de l'entité utilisatrice - Cp (u), la classe précédente correspondant à Wp (u) et Qp (u), - ca (u), la classe actuelle correspondant à Wa (u) et Qa (u), - E (u), l'échéance virtuelle de l'entité utilisatrice. De même, dans la mémoire 3 de la figure 4, pour chaque classe c (j) est défini un certain nombre d'attributs comprenant : un attribut fixe dans le temps : - d (j), son délai, des attributs variables dans le temps : - e (j), son état d'éligibilité, - E (j), son échéance virtuelle, - E. (j), l'échéance minimale parmi les échéances d'anciens utilisateurs en tête de FIFO. De même, le gestionnaire de ressource 2 définit plusieurs attributs dans la mémoire 3 de la figure 4 : des attributs fixes dans le temps : - Wm, la charge maximale attribuable à une entité utilisatrice, - Qmaxp le quantum maximal attribuable à une entité utilisatrice, - nbQ, le nombre des divers quanta possibles attribuables à une entité utilisatrice après chaque affectation de la ressource, - RQ, la progression géométrique des suites de quanta, attribuables à une entité utilisatrice, des attributs variables dans le temps : - V, l'heure virtuelle du dispositif, - WS, la charge totale du dispositif correspondant à la somme des charges attribuées à chaque entité utilisatrice. Dans la suite de la description, chaque paramètre est décrit dans son utilisation selon l'invention. La figure 5 présente l'initialisation du gestionnaire de ressource selon l'invention. Ainsi, selon l'étape 102, le quantum minimal attribuable à une entité utilisatrice est calculé suivant le quantum maximal Qmax attribuable à une entité utilisatrice, la raison géométrique RQ des suites géométriques des quanta attribuables, et le nombre de quanta attribuables nbQ. A l'étape 104, le nombre de classes m, déterminant également le nombre m+1 de FIFO par classe, est un entier calculé en fonction du nombre de quanta attribuables nbQ et de l'entier correspondant au rapport Wmax/Wmin. A l'étape 106, le gestionnaire de ressource initialise l'heure virtuelle V et la charge totale du gestionnaire WS à zéro. D'autre part, pour chacune des m classes c (i), le gestionnaire de ressource initialise à"vide"la file des nouveaux utilisateurs c (i, O) et les m files d'anciens utilisateurs c (j, i), j variant de 1 à m. La figure 6 représente un ordinogramme illustrant la définition des quanta attribuables à un utilisateur donné pour une charge choisie de cet utilisateur. A l'étape 112, il est recherché la classe c (i) de délai d (i) qui permet de ne pas dépasser le quantum maximal théoriquement attribuable Qmax pour la charge W (u) choisie. Ce délai d (i) est mémorisé en tant que délai maximal d (u) de l'utilisateur donné u. A l'étape 114, le quantum maximal réellement attribuable à l'entité utilisatrice est calculé en fonction du délai maximal trouvé d (u) telle que Qmax (u) =W (u) xdmax (u). L'étape 116 définit les quanta que l'utilisateur pourra demander suivant ses besoins. Ces quanta attribuables Q (u) prennent différentes valeurs possibles telles Q (u) =Qmax (u)/RQk avec k nbQ. Ainsi, pour une charge W (u) fixée et associée à un quantum attribuable Q (u) correspond une classe c (i) de délai d (i) =Q (u) /W (u). Une liste Q (u, c (i)) de ces quanta attribua- bles est établie pour les différentes classes c (i). D'autre part, la figure 7 présente l'ordinogramme illustrant l'activation d'un nouvel utilisateur uac de charge choisie W (uac). Ainsi, à l'étape 122, la charge totale du gestionnaire de ressource est incrémentée de la charge choisie de l'utilisateur activé. L'utilisateur activé demande un des quanta Q (ubac) attribuables tels que définis à l'étape 116 de la figure 6. D'autre part, à l'étape 124, la classe c (i) est déduite de la recherche du délai d (i) vérifiant la relation d (i) A l'étape 128, l'utilisateur activé uac est inséré en fin de file c (i, O) des nouveaux utilisateurs de la classe c (i). D'autre part, à l'étape 130, si la file de nouveaux utilisateurs de la classe c (i) est dite"vide" (ou encore sans utilisateur) et si l'utilisateur ancien d'échéance minimale de la classe (s'il en existe un) n'était pas déjà éligible, la classe devient éligible à l'étape 131. e (c (i)) prend la valeur"vraie"et l'échéance de l'utilisateur activé E (uac) devient l'échéance de la classe E (c (i)). Les ordinogrammes des figures 8 et 9 représentent les algorithmes utilisés par le gestionnaire de ressources pour sélectionner un utilisateur. Ainsi, lors d'un appel de la ressource à l'étape 140, le gestionnaire de ressource vérifie si sa charge globale WS est nulle à l'étape 142. Dans le cas d'une charge globale nulle, l'appel de la ressource est sans effet pour un utilisateur. Sinon, le gestionnaire de ressource sélectionne l'utilisateur à qui il va attribuer la ressource à l'étape 143. Cette sélection s'effectue tout d'abord sur les m classes dont seule la classe dite"éligible"et d'échéance de classe E (c (i)) minimale et retenue. Ainsi, parmi les entités utilisatrices des files de cette classe sélectionnée, l'entité utilisatrice éligible et d'échéance E (u) minimale est sélectionnée, appelée entité utilisatrice Ug, et ceci pour un quantum Qp (uns, c (i)). L'heure virtuelle du gestionnaire de ressource progresse d'une quantité égale au quantum servi divisé par la charge totale Qp (Ug, c (i))/WS, à l'étape 144. A l'étape la charge totale Qp (u. 146, l'utilisateur est informé de sa sélection et est invité à demander, s'il le désire, une nouvelle valeur de charge actuelle Wa (u) (pour laquelle il devra réaliser un nouveau calcul des quanta attribuables et des classes de délai correspondant aux étapes 112 à 116 de la figure 6) ; et une nouvelle valeur de quantum Qa (u) choisi parmi ceux attribuables. L'utilisateur est alors sorti de sa FIFO c (j, i) à l'étape 147. A l'étape 148, dans le cas d'un quantum nul demandé par l'utilisateur, le gestionnaire de ressource diminue sa charge totale WS de la charge de l'utilisateur Wp (u), à l'étape 152. Le gestionnaire de ressource vérifie qu'aucun utilisateur ne reste dans sa mémoire, à savoir que sa charge totale est nulle, à l'étape 154, et ainsi arrête l'attribution de la ressource à l'utilisateur. Si, au contraire, des utilisateurs restent dans la mémoire du gestionnaire de ressource, à l'étape 154, l'ordinogramme continue à l'étape 160 désignant la figure 9. Si, à l'étape 148, le quantum demandé par l'utilisateur pour sa prochaine sélection n'est pas nul, la charge totale WS est alors éventuellement modifiée à l'étape 149 pour prendre en compte une modification de la charge individuelle de l'utilisateur sélectionné : WS = WS-Wp (u) +Wa (u). A l'étape 150, l'utilisateur servi est inséré en fin d'une nouvelle FIFO d'anciens dans la classe de délai correspondant d'une part au quantum demandé pour sa prochaine sélection et d'autre part à sa charge fixée. Dans cette classe, l'utilisateur servi est inséré dans la FIFO d'anciens c (j, i), correspondant à la classe précédente c (i) dont il vient de sortir et à la classe actuelle c (j). Les étapes suivantes correspondent à des mises à jour des paramètres d'échéances des classes et des variables d'états d'éligibilité. A l'étape 156, si, à l'intérieur de sa nouvelle classe, l'utilisateur réinséré devient celui dont l'échéance d'anciens est minimale, l'échéance minimale d'anciens de la classe Emin-an (c (j)) est mise à jour à l'étape 158. Sinon, l'étape 160 désignant la figure 9 est effectuée. La figure 9 décrit les étapes précédant l'étape 162 de la figure 8. A l'étape 200, si l'utilisateur u faisait partie de l'ensemble A désignant les utilisateurs anciens de la classe précédente c (i) et s'il existe, en tête de la FIFO des utilisateurs anciens, un utilisateur u1 d'échéance minimale E (u1), tel que E (ul) L'échéance de l'utilisateur u1 est incrémentée du délai d (i) de la classe c (i) et le paramètre d'état d'éligibilité de cet utilisateur e (ul) est passé à"vrai". Ainsi, dans l'ancienne classe de l'utilisateur servi, un autre utilisateur est rendu éligible avec une nouvelle échéance. D'autre part, dans l'ancienne classe c (i) de l'utilisateur servi, si la file de nouveaux utilisateurs de la classe n'est pas vide et/ou si l'utilisateur ancien d'échéance minimale u1 est devenu éligible, à l'étape 204, la classe c (i) devient éligible et l'échéance de cette classe E (c (i)) prend la valeur de la plus petite échéance trouvée, à l'étape 206. L'échéance minimale d'ancien utilisateur de la classe est mis à jour si nécessaire. Si les critères de l'étapes 204 ne sont pas remplis, la classe c (i) est inéligible à l'étape 208. La variable f est un entier variant de 1 à m. A l'étape 212, le gestionnaire de ressource parcourt les m classes afin de rendre éligibles les classes inéligibles c (f) dont l'échéance minimale E (c (f)) est dépassée par l'heure virtuelle V. Si aucune classe n'est éligible, à l'étape 214, le gestionnaire de ressource trouve parmi les m classes, la classe dont l'échéance d'anciens est minimale à l'étape 218 et l'heure virtuelle V est avancée à l'échéance minimale d'anciens du gestionnaire de ressource à l'étape 220. Après l'étape 220 ou si une classe est éligible à l'étape 214, l'étape 162 de la figure 8 vérifie si le quantum demandé par l'utilisateur est nul : - dans le cas d'une réponse positive, l'algorithme reprend à l'étape 142, - dans le cas d'une réponse négative, l'algorithme finit sur un état de non attribution de la ressource. La présente invention vise entre autre le code logiciel qu'elle fait intervenir, tout particulièrement lorsqu'il est mis à disposition sur tout support lisible sur un ordina- teur. L'expression"support lisible par ordinateur"couvre un support de stockage, par exemple magnétique ou optique, aussi bien qu'un moyen de transmission, tel qu'un signal numérique ou analogique. L'invention vise également un système informatique compre- nant l'ordonnanceur. Par système informatique, on entend un ou plusieurs ordinateurs, et/ou tout système numérique capable d'effectuer des télécommunications et/ou de la transmission de données. Bien entendu l'invention n'est pas limitée à la forme de réalisation décrite précédemment à titre d'exemple, elle s'étend à d'autres variantes. Ainsi, on comprendra que la présente invention peut s'appliquer à des dispositifs informatiques dont le système d'exploitation partage une unité centrale de traitement entre plusieurs tâches. Elle peut aussi concerner des noeuds de réseaux à commutation par paquets (noeuds de réseaux type"internet"etc) qui partagent au moins une liaison de transmission de données entre plusieurs courants d'informations. Dans l'exemple décrit ci-avant, l'allocation de la ressource se fait par temps de traitement fini (la gestion en temps partagé) adapté suivant la demande de chaque utilisateur. Cependant, l'invention s'applique aussi bien à une allocation par transmission par paquets (liaison de transmission) suivant également les besoins de chaque utilisateur, les quanta demandés étant définis alors comme des quantités d'informations à transmettre. De manière générale, l'invention s'applique à des allocations par tranches de services pouvant varier au cours du temps selon les besoins des utilisateurs. Chaque allocation par tranche de services pour un utilisateur est associée à une file d'utilisateurs ayant eu l'allocation de la même tranche de services précédente. Dans une même classe, quelle que soit la file dans laquelle l'utilisateur se trouve en fonction de l'allocation de la tranche de services précédente, un incrément est défini pour la classe afin de compte un cumul pour chaque utilisateur représentatif des services rendus à cet utilisateur dans le temps. D'autre part, le nombre de classes proposées selon l'invention peut être défini différemment. L'invention peut s'exprimer sous la forme de produits industriels nouveaux que constituent les dispositifs de gestion d'une ressource de type précité. Elle peut aussi bien s'exprimer sous la forme du traitement appliqué à un ordinateur ou à un noeud de réseaux, pour gérer le partage de cette ressource. La série de quanta successifs d'un même utilisateur qui reste actif peut être implicite. Par exemple, le premier quantum a la valeur minimale pour l'utilisateur et les suivants sont en progression géométrique de raison QR jusqu'à une stabilisation à la valeur maximale. Le nombre de classes et le nombre des FIFO dans chaque classe étant limité, un matériel spécialisé pour exécuter les boucles les plus critiques est envisageable sans que sa dimension introduise une limite contraignante du nombre d'utilisateurs. Les boucles les plus critiques, exécutables à chaque sélection, concernent l'examen des classes inéligibles pour déterminer si leur échéance a été atteinte ou dépassée par l'heure virtuelle, la recherche d'une classe éligible d'échéance la moins avancée, et, pour le recalage éventuel de l'heure virtuel, la recherche de la classe inéligible d'échéance précédente la moins avancée. Dans une réalisation particulière de l'invention, le nombre d'utilisateurs est fixé au départ, la gestion de nouveaux utilisateurs n'existe pas, les FIFO des nouveaux utilisateurs sont alors supprimées. Dans une autre réalisation particulière de l'invention, la modification de la charge d'un utilisateur est limitée à un ensemble de valeurs en progression géométrique de même raison (RQ) que la suite des valeurs de quanta, de sorte que la liste des valeurs de quanta possibles pour cette nouvelle charge reste inchangée, seules les classes associées définissant des délais étant modifiées. Ceci minimise la quantité de calcul nécessaire. Dans une réalisation possible de l'invention, les mémoires FIFO sont toutes associées à une première valeur d'incrément et une seule de ces mémoires FIFO est associée à une seconde valeur d'incrément correspondant à une première valeur d'incrément d'une des mémoires FIFO. Annexe 1 k=N (1) : y (t) = I., W (k) k=l fx (t) (2) : Q, (t) = f dT/y (i) ax (t) t (3) : q (t) = f dT/y (ï) to (t) (4) Ex (t) = q (fx (t)) (5) Ex (t) = q (0 (t) + Qx/Wx k=N (6) : pV (uJ = Q (u,)/W (k) k=l Revendications 1. Ordonnanceur pour le partage d'une ressource, du type comprenant : - une mémoire capable de stocker, pour des utilisateurs, des quantités d'ordre respectives, dites échéances (E (u)), - des mémoires de type FIFO, associées chacune à une valeur, dite première valeur d'incrément (d (j)), pour stocker des identifiants-utilisateur, et - un organe de gestion (21), capable : * de désigner l'une des mémoires FIFO, dont l'identifiant-utilisateur premier sortant est le "prochain à servir"par la ressource, cette désignation s'effectuant en fonction de premières conditions qui comprennent l'ordre des échéances des utilisateurs premiers sortants, * de recycler l'identifiant-utilisateur dans l'une des FIFO, et * d'augmenter l'échéance d'un utilisateur recyclé de la première valeur d'incrément de la FIFO où se trouve cet utilisateur, caractérisé : - en ce que l'une au moins des mémoires FIFO (c (j, i)) est associée en outre à une seconde valeur d'incrément (d (i)), et - en ce que l'organe de gestion (21) comprend un organe de décision de recyclage (61), capable, après service d'un utilisateur, de ré-orienter l'identifiant de cet utilisateur vers l'une des FIFO, en fonction de secondes conditions, qui comprennent une comparaison entre la seconde valeur d'incré- ment de la FIFO où va l'utilisateur et la première valeur d'incrément de la FIFO d'où provient l'utilisateur. 2. Ordonnanceur selon la revendication 1, caractérisé en ce qu'il comprend au moins deux FIFO (c (j, l), c (j, i)) ayant la même première valeur d'incrément (d (j)) et en ce que l'organe de gestion (21) comprend un organe de pré-sélection (62) entre les utilisateurs premiers sortants de ces FIFO ayant la même première valeur d'incrément. 3. Ordonnanceur selon la revendication 2, caractérisé en ce que au moins deux des FIFO (c (j, l), c (j, i)) ayant la même première valeur d'incrément ont des secondes valeurs d'incrément (d (l), d (i)) différentes. 4. Ordonnanceur selon l'une des revendications 1 à 4, caractérisé en ce que les première conditions prédéterminées comprennent le fait de déterminer, pour chaque groupe de mémoires FIFO ayant la même première valeur d'incrément, une échéance minimale parmi les échéances (E (u)) des utilisateurs premiers sortants des mémoires FIFO ayant la même première valeur d'incrément et de désigner une mémoire FIFO correspondant d'une part à une échéance inférieure à une valeur globale (V) attribuée à l'ordonnanceur et d'autre part à l'échéance minimale parmi les échéances minimales des groupes de mémoires FIFO ayant la même première valeur d'incrément. 5. Ordonnanceur selon l'une des revendications 1 à 4, caractérisé en ce que les deuxième conditions prédéterminées comprennent la vérification de l'égalité entre la seconde valeur d'incrément de la FIFO où va l'utilisateur et la première valeur d'incrément de la FIFO d'où provient l'utilisateur. 6. Ordonnanceur selon l'une des revendications précédentes, caractérisé en ce qu'il comprend une FIFO spécifique (c (j, 0)) pour stocker un identifiant utilisateur entrant. 7. Ordonnanceur selon la revendication 6, caractérisé en ce qu'il comprend en outre un organe de décision d'entrée, capable de placer un identifiant utilisateur dans une mémoire FIFO, possédant une première valeur d'incrément qui correspond à un paramètre lié au besoin relatif de ressource par l'utilisateur entrant. 8. Procédé d'ordonnancement pour le partage d'une ressource, caractérisé en ce qu'il comprend les étapes suivantes : a. stocker des identifiants-utilisateur dans des mémoires FIFO associées chacune à une valeur, dite première valeur d'incrément (d (j)), l'une au moins des mémoires FIFO (c (j, i)) étant associée en outre à une seconde valeur d'incrément (d (i)), b. désigner, parmi lesdites mémoires FIFO, une mémoire FIFO dont l'identifiant-utilisateur premier sortant est le "prochain à servir" par la ressource, cette désignation s'effectuant en fonction de premières conditions qui comprennent l'ordre des échéances des utilisateurs premiers sortants, c. recycler l'identifiant-utilisateur en ré-orientant cet identifiant-utilisateur dans l'une des FIFO, en fonction de secondes conditions, qui comprennent une comparaison entre la seconde valeur d'incrément de la FIFO où va l'utilisateur et la première valeur d'incrément de la FIFO d'où provient l'utilisateur, et d. augmenter l'échéance d'un utilisateur recyclé de la première valeur d'incrément de la FIFO où se trouve cet utilisateur. 9. Procédé d'ordonnancement selon la revendication 8, caractérisé en ce que l'étape b. comprend une pré-sélection entre les utilisateurs premiers sortants de deux FIFO, au moins ces deux FIFO ayant la même première valeur d'incrément. 10. Procédé d'ordonnancement selon les revendications 8 et 9, caractérisé en ce que au moins deux des FIFO de l'étape b. ayant la même première valeur d'incrément ont des secondes valeurs d'incrément différentes. 11. Procédé d'ordonnancement selon les revendications 8 à 10, caractérisé en ce que les première conditions de l'étape b. comprennent le fait de déterminer, pour chaque groupe de mémoires FIFO ayant la même première valeur d'incrément, une échéance minimale parmi les échéances (E (u) ) des utilisateu- rs premiers sortants des mémoires FIFO ayant la même première valeur d'incrément et de désigner une mémoire FIFO correspondant d'une part à une échéance inférieure à une valeur globale (V) attribuée à l'ordonnanceur et d'autre part à l'échéance minimale parmi les échéances minimales des groupes de mémoires FIFO ayant la même première valeur d'incrément. 12. Procédé d'ordonnancement selon les revendications 8 et 11, caractérisé en ce que les secondes conditions de l'étape c. comprennent la vérification de l'égalité entre la seconde valeur d'incrément de la FIFO où va l'utilisateur et la première valeur d'incrément de la FIFO d'où provient l'utilisateur. 13. Procédé d'ordonnancement selon l'une des revendications 8 à 12, caractérisé en ce que l'étape a. comprend une FIFO spécifique pour stocker un identifiant utilisateur entrant. 14. Procédé d'ordonnancement selon la revendication 13, caractérisé en ce que l'étape a. comprend en outre lors de l'entrée d'un utilisateur, de placer l'identifiant utilisateur correspondant dans une mémoire FIFO, possédant une première valeur d'incrément qui correspond à un paramètre lié au besoin relatif de ressource par l'utilisateur entrant. 15. Système informatique comprenant un ordonnanceur selon l'une des revendications 1 à 7. 16. Système informatique selon la revendication 15, caractérisé en ce qu'il comprend un équipement de télécommunication. 17. Module logiciel réalisant les fonctions utilisées dans l'ordonnanceur selon l'une des revendications 1 à 7. 18. Module logiciel réalisant les étapes du procédé selon l'une des revendications 8 à 14.