Arrière-plan de rinvention

L'invention se rapporte au domaine général des systèmes informatiques, et plus particulièrement des systèmes informatiques s'appuyant sur des clusters de machines (désignées également plus couramment par « serveurs »).

De façon connue, un cluster (ou grappe) de serveurs regroupe plusieurs ordinateurs (ou nœuds) indépendants placés en réseau, de sorte à permettre une gestion globale et optimisée des ressources informatiques (ex. mémoire, CPU (Central Processing Unit), espace disque, accès réseau, etc.) offertes par ces ordinateurs. Un tel cluster de serveurs permet typiquement la distribution et le lancement en parallèle, sur plusieurs serveurs distincts du cluster, de différentes tâches informatiques associées à un même programme ou à une même application informatique (aussi désigné par « travail » ou encore « job » en anglais). Dans le contexte des traitements de données actuels, qui peuvent impliquer des volumes de données très importants (ex. traitements dits « Big Data »), il n'est pas rare de rencontrer des clusters de serveurs comprenant des milliers voire des dizaines de milliers de machines qu'il est nécessaire d'administrer de façon efficace.

La distribution des tâches sur les différentes machines d'un cluster est généralement administrée par un système de gestion du cluster. Des systèmes de gestion de clusters connus sont par exemple le système Borg proposé par Google ou encore le système Hadoop Yarn proposé par The Apache Software Foundation. Ces systèmes sont capables d'administrer des clusters regroupant un nombre très important de machines, et de lancer en parallèle sur ces machines des centaines de milliers de tâches appartenant à plusieurs milliers d'applications logicielles différentes.

Dans ce contexte, les systèmes de gestion des clusters sont très souvent confrontés à des tâches qui doivent être lancées en rafales sur les clusters. Il leur est donc nécessaire pour traiter efficacement ces tâches de prendre une décision très rapidement quant à leur distribution sur les différentes machines des clusters. A cet effet, les systèmes de gestion de clusters de l'état de la technique allouent les ressources d'un cluster aux différentes tâches d'un programme (autrement dit, associent à ces différentes tâches différents serveurs du cluster capables de fournir les ressources nécessaires à leur exécution et réservent sur ces serveurs les ressources requises) sur la base des ressources réservées par l'utilisateur du cluster qui demande l'exécution de son programme.

Ainsi à titre d'exemple, le système de gestion de cluster Hadoop Yarn définit, pour chaque serveur S d'un cluster Hadoop et chaque ressource informatique R offerte par le serveur, une capacité limite CL_R. On considère ici par souci de simplification que tous les serveurs S ont la même capacité limite pour la ressource R. La ressource informatique R peut être de nature diverse comme par exemple de la mémoire, du CPU (Central Processing Unit), de l'espace disque, un accès réseau, etc. Pour décider quelle ressource allouer sur quel serveur du cluster à une tâche j d'un programme (ou job), le système de gestion de cluster Hadoop Yarn détermine rapidement quels sont les serveurs capables d'exécuter cette tâche j, autrement dit, quels sont les serveurs qui disposent des ressources nécessaires à son exécution au vu des besoins en ressource R déclarés par l'utilisateur du programme. Il utilise à cet effet la capacité limite CL_R de chaque serveur, les besoins R_RJ de la tâche j en ressource R déclarés par l'utilisateur du programme, et la quantité totale T_R de ressource R déjà réservées sur chaque serveur. Un serveur est alors considéré comme apte à exécuter une tâche j seulement si pour ce serveur :

R_RJ+T_R < CL_R.

Un serveur est alors sélectionné par le système de gestion Hadoop Yarn parmi les serveurs aptes à exécuter la tâche j, en fonction de critères prédéterminés, non détaillés ici.

Ce mode de fonctionnement n'est pas sans contrainte pour les utilisateurs du cluster. En effet, cela impose aux utilisateurs de spécifier les besoins en ressources des différentes tâches de leurs programmes de façon suffisamment précise pour ne pas bloquer inutilement des ressources au niveau du cluster ni, au contraire, risquer de voir leurs tâches ne pas être traitées ou être traitées de façon moins performante parce qu'elles requièrent plus de ressources que celles déclarées par l'utilisateur. Une telle estimation des besoins des tâches de leurs programmes est particulièrement difficile pour les utilisateurs, d'autant plus que ces besoins sont susceptibles d'évoluer dans le temps. Dans ce contexte, il est classique que les utilisateurs surestiment les besoins en ressources des tâches de leurs programmes, ce qui conduit à une sous-utilisation des ressources du cluster. Objet et résumé de l'invention

L'invention permet notamment de pallier les inconvénients précités en proposant un procédé de mise à jour, pour au moins un serveur d'un cluster de serveurs d'au moins une valeur courante d'une variable notée V choisie parmi une estimation d'une quantité déjà utilisée d'une ressource informatique sur le serveur ou une capacité maximale du serveur pour ladite ressource informatique, ladite au moins une valeur courante étant destinée à être prise en compte par un dispositif de gestion du cluster de serveurs pour sélectionner, sur réception d'une requête d'exécution d'une tâche informatique associée à une quantité prédéterminée de ladite ressource informatique requise initialement pour son exécution, un serveur dit cible du cluster pour exécuter cette tâche informatique, ledit procédé étant tel que ladite mise à jour est réalisée à chaque détection d'un événement parmi un ensemble prédéfini d'événements et :

— si l'événement détecté est une obtention d'une mesure d'une utilisation réelle courante de la ressource informatique sur le serveur, ladite mise à jour de la valeur courante de la variable V utilise ladite mesure de l'utilisation réelle courante de la ressource informatique sur le serveur ;

— si l'événement détecté est une réservation par le dispositif de gestion pour une tâche informatique d'une quantité de la ressource informatique sur le serveur, ladite mise à jour de la valeur courante de la variable V utilise ladite quantité de la ressource informatique réservée ; et — si l'événement détecté est une libération par une tâche informatique d'une quantité de la ressource informatique sur le serveur, ladite mise à jour de la valeur courante de la variable V utilise ladite quantité de la ressource informatique libérée.

L'invention vise aussi un procédé de gestion de tâches informatiques comprenant, sur réception par un dispositif de gestion d'un cluster de serveurs d'une requête d'exécution d'une tâche informatique, cette tâche informatique étant associée à une quantité prédéterminée d'une ressource informatique requise initialement pour son exécution :

— une étape de détermination, par le dispositif de gestion du cluster, d'au moins un serveur du cluster apte à exécuter la tâche informatique, cette étape de détermination utilisant la quantité prédéterminée de la ressource informatique requise initialement pour l'exécution de la tâche informatique, une capacité maximale du serveur pour la ressource informatique et une estimation d'une quantité déjà utilisée de la ressource informatique sur le serveur ;

— une étape de sélection, par le dispositif de gestion du cluster, d'un serveur pour exécuter la tâche informatique parmi ledit au moins un serveur du cluster déterminé.

Ce procédé est remarquable en ce que, pour au moins un serveur du cluster, au moins une valeur courante d'une variable notée V choisie parmi l'estimation de la quantité déjà utilisée de la ressource informatique sur le serveur et la capacité maximale du serveur pour la ressource informatique est mise à jour conformément à un procédé de mise à jour selon l'invention.

Aucune limitation n'est attachée à la nature des ressources informatiques des serveurs du cluster gérées par le dispositif de gestion du cluster et requises pour l'exécution des tâches informatiques dans le contexte de l'invention. Il peut s'agir de tout type de ressources (i.e. composants matériels ou logiciels) informatiques et/ou réseaux comme par exemple de la mémoire, du CPU, des accès réseaux, de l'espace disque, etc.

En outre, l'invention est décrite en référence à une unique ressource ; toutefois le même procédé peut être utilisé pour prendre en compte plusieurs ressources, en l'appliquant à chaque ressource individuellement. C'est lors de la sélection à proprement parler du serveur sur lequel exécuter la tâche que la pluralité des ressources sera prise en compte en choisissant un serveur disposant de chacun des ressources nécessaires pour l'exécution de la tâche.

L'invention propose donc une solution qui permet de tenir compte de l'utilisation courante et réelle (i.e. effective) des ressources au niveau des serveurs d'un cluster pour gérer l'attribution des ressources au sein de ce cluster.

Cette solution s'appuie avantageusement sur le mécanisme actuel d'allocation de ressources appliqué par les systèmes de gestion de clusters de l'état de la technique, ce qui permet d'assurer une réponse rapide du dispositif de gestion notamment lorsque des tâches en rafales doivent être lancées par celui-ci sur le cluster. En effet, sans connaissance a priori sur l'utilisation réelle des ressources par une tâche informatique, le dispositif de gestion réserve pour cette tâche au niveau du serveur sur lequel il la lance, une quantité de ressource égale au besoin déclaré par l'utilisateur à l'origine de la tâche informatique (quantité prédéterminée de la ressource informatique requise initialement pour l'exécution de la tâche informatique au sens de l'invention).

Le mécanisme de l'état de la technique est toutefois adapté de sorte à prendre en compte, après le lancement d'une tâche par le dispositif de gestion sur un serveur du cluster, l'utilisation réelle des ressources par cette tâche sur le serveur.

Ceci offre la possibilité au dispositif de gestion, si cette utilisation réelle est inférieure aux besoins de la tâche déclarés par son utilisateur, d'attribuer les ressources non utilisées par la tâche à d'autres tâches informatiques présentées ultérieurement au dispositif de gestion. Cette prise en compte est réalisée via la mise à jour, à partir de mesures effectuées directement sur les serveurs, des quantités utilisées par le dispositif de gestion pour décider de l'attribution des ressources, à savoir de l'estimation de la quantité déjà utilisée de la ressource informatique requise par la tâche sur le serveur et/ou de la capacité maximale du serveur pour cette ressource. Dans un mode particulier de réalisation, l'obtention des mesures d'utilisation courante de la ressource peut être périodique.

En outre, conformément à l'invention, d'autres événements affectant les ressources disponibles sur le serveur déclenchent une mise à jour de la valeur courante de la variable V considérée. Ces événements sont la réservation sur le serveur, par le dispositif de gestion, d'une quantité de la ressource considérée pour d'autres tâches, ainsi que la libération d'une quantité de cette ressource sur le serveur par des tâches qui ont fini de s'exécuter sur celui-ci.

Ceci permet de prendre en compte les tâches informatiques qui sont positionnées de façon asynchrone sur le serveur par le dispositif de gestion entre deux remontées de mesures d'utilisation réelle de la ressource sur le serveur (ces remontées n'étant généralement pas continues mais périodiques ou à des instants prédéterminés), ainsi que celles qui se terminent sur le serveur. La prise en compte des tâches achevées a un intérêt privilégié lorsqu'une tâche informatique lancée sur un serveur se termine très rapidement, typiquement en un temps inférieur à la période de remontée des mesures d'utilisation réelle faites sur le serveur le cas échéant. Cela permet d'éliminer le reliquat de ressource réservé pour cette tâche sur le serveur et qui n'est plus utilisé par ce serveur sans pour autant être répercuté dans la mesure.

L'invention rend donc possible la répercussion en temps réel des différentes variations susceptibles d'affecter la quantité de ressource disponible sur le serveur dans la quantité prise en compte par le dispositif de gestion pour répondre à une requête d'exécution d'une tâche informatique. Le dispositif de gestion du cluster dispose en effet d'une représentation plus précise de la quantité de ressource réellement utilisée sur le serveur à chaque instant, ou tout du moins au moment où il reçoit une requête d'exécution d'une tâche.

Le dispositif de gestion du cluster peut ainsi simultanément, grâce à l'invention, apprendre comment les ressources sont effectivement utilisées sur les serveurs tout en étant capable de prendre des décisions rapidement pour allouer des ressources aux tâches informatiques qui lui sont présentées. Cette prise de décision rapide est réalisée instantanément sur la base des ressources qui sont réservées par les utilisateurs pour ces tâches sans attendre de savoir comment ces tâches vont se comporter effectivement. L'invention résout ainsi le double problème d'adresser des rafales de tâches sans avoir de connaissance de leur utilisation future des ressources du cluster tout en permettant d'allouer à d'autres tâches des ressources non utilisées du cluster.

L'invention propose donc une solution compatible avec des clusters de grande dimension et des applications logicielles comprenant un nombre volumineux de tâches informatiques à exécuter sur ces clusters, et qui permet de corriger progressivement une estimation erronée ou peu précise des besoins en ressources de ces tâches par leurs utilisateurs. Les contraintes imposées aux utilisateurs des clusters peuvent être ainsi relâchées.

Par ailleurs, les ressources des clusters sont mieux utilisées tout en tentant d'assurer la bonne exécution des tâches sur ces clusters : on limite en effet, grâce à l'invention, les temps d'attente prolongés pour l'exécution d'une tâche informatique ou l'éviction d'une tâche informatique notamment en cas de ressources insuffisantes attribuées à cette tâche en tenant compte de l'utilisation réelle des ressources sur les serveurs du cluster. Il convient de noter qu'un temps d'attente prolongé ou l'éviction d'une tâche est toujours possible, toutefois il ou elle est contrebalancé(e) par le fait qu'un plus grand nombre de tâches peut être lancé simultanément sur le cluster du fait d'une meilleure gestion des ressources de ce dernier. Les performances du cluster sont ainsi globalement améliorées.

En outre, l'invention permet de s'adapter à une éventuelle variation dans le temps des besoins en ressources des tâches lancées sur les serveurs des clusters.

On note que la mise à jour de la capacité maximale du serveur pour la ressource plutôt que de l'estimation de la quantité déjà utilisée de la ressource informatique requise par la tâche sur le serveur permet avantageusement d'utiliser comme dispositif de gestion du cluster l'un des systèmes de gestion de l'état de la technique. En effet, la capacité maximale de chaque serveur est une information qui est remontée aujourd'hui périodiquement par ce serveur au système de gestion du cluster dans l'état de la technique. En mettant à jour cette capacité au niveau du serveur pour qu'elle reflète l'utilisation réelle de la ressource, on s'assure que le système de gestion du cluster prend en compte cette utilisation réelle pour l'attribution des ressources du cluster de façon totalement transparente pour lui. Autrement dit, ceci permet d'envisager une implémentation dans laquelle le fonctionnement du système de gestion centralisé du cluster reste le même (et donc dans laquelle il est possible d'utiliser des systèmes de gestion de l'état de la technique, tels que les systèmes Borg ou Hadoop Yarn mentionnés précédemment), et où seuls les serveurs du cluster doivent être adaptés pour prendre en compte dans la capacité maximale qu'ils remontent au système de gestion du cluster, l'utilisation réelle de leurs ressources. Une telle implémentation est particulièrement intéressante car elle permet une installation progressive de l'invention sur l'ensemble des serveurs du cluster tout en gardant inchangé le système de gestion du cluster. Or la mise à jour des serveurs s'avère en pratique une tâche bien plus simple qu'une mise à jour du système de gestion du cluster qui en soi est souvent un module déjà très complexe. En outre, dans cette variante, l'invention peut s'appuyer sur la signalisation (i.e. protocole de communication) déjà définie entre les serveurs du cluster et le système de gestion du cluster.

Dans un mode particulier de réalisation, si l'événement détecté est l'obtention de la mesure de l'utilisation réelle courante de la ressource informatique sur le serveur, la mise à jour de la valeur courante de la variable V utilise en outre au moins une valeur de la variable V notée Vpast mise à jour à un instant précédent.

Dans ce mode de réalisation, lors de la mise à jour la mesure de l'utilisation réelle courante de la ressource informatique peut être notamment pondérée par un facteur réel a compris entre 0 et 1, et ladite au moins une valeur Vpast être pondérée par un facteur égal à (1-a).

Ce mode de réalisation, qui met en œuvre une moyenne mobile de type exponentielle, permet de lisser dans le temps la prise en compte de l'utilisation réelle au niveau du serveur de la ressource par rapport à la quantité de ressource initialement réservée. Ce lissage donne la possibilité d'une prise en compte progressive de l'utilisation réelle des ressources au niveau de chaque serveur tout en évitant des fluctuations transitoires brusques qui pourraient entraîner une allocation moins efficace des ressources par le dispositif de gestion du cluster. En effet, plus le facteur a est choisi proche de 0, plus on tient compte longtemps de la quantité de ressources réservées et on retarde l'utilisation des ressources disponibles dans le cluster par le dispositif de gestion. Au contraire, en choisissant un facteur a proche de 1, le dispositif de gestion peut utiliser les ressources disponibles plus tôt dans le temps. On note que le facteur a peut varier dans le temps.

Bien entendu, d'autres manières de prendre en compte la mesure de l'utilisation réelle de la ressource informatique et le cas échéant ladite au moins une valeur mise à jour à un instant précédent peuvent être envisagées. On peut s'appuyer par exemple sur le principe d'une moyenne mobile arithmétique ou pondérée de mesures obtenues à différents instants et évaluée sur une fenêtre glissante de dimension prédéterminée dont l'extrémité est positionnée sur l'instant courant, etc. Dans le cas d'une moyenne pondérée, on peut envisager d'appliquer des poids décroissants au fur et à mesure que l'ancienneté des mesures augmente.

A titre d'exemple, dans une variante de réalisation de l'invention dans laquelle la variable V mise à jour est l'estimation EU_R de la quantité déjà utilisée de la ressource informatique sur le serveur, si l'événement détecté est l'obtention de la mesure de l'utilisation réelle courante de la ressource informatique sur le serveur, ladite valeur courante notée EU_R(n) de la variable V est mise à jour selon l'équation :

EU_R(n) = max((l - a)EU_R(n - 1) + aU _R(n), U _R(n)) où n désigne un entier supérieur à 1, EU_R(n - 1) est la valeur de l'estimation de la quantité déjà utilisée de la ressource informatique sur le serveur mise à jour à un instant précédent, et U_R(n) désigne la mesure obtenue de l'utilisation réelle courante de la ressource informatique sur le serveur. Cette variante a une application privilégiée lorsque la ressource informatique en question est de la mémoire. En effet, les contraintes en terme de ressource mémoire sont des contraintes relativement fortes dans le sens où une tâche peut être évincée d'une machine sur laquelle elle est exécutée si elle requiert à un instant donné plus de mémoire que la machine en dispose à cet instant. En forçant la mise à jour de la valeur EU_R(n) à une valeur supérieure ou égale à la ressource mémoire U_R(n) effectivement utilisée sur le serveur lorsque la valeur de (l - a)EU_R (n - 1) + U_R(n) ne reflète de façon insuffisante l'occupation réelle de la mémoire sur le serveur, on s'assure que le dispositif de gestion n'alloue pas indûment à de nouvelles tâches de la mémoire sur le serveur qui pourrait manquer ensuite aux tâches informatiques s'exécutant déjà sur le serveur et s'avérer préjudiciable pour le traitement de celles-ci.

Dans un autre mode de réalisation de l'invention, si l'événement détecté est l'obtention de la mesure de l'utilisation réelle courante de la ressource informatique sur le serveur, cette mesure correspond à une utilisation de la ressource informatique sur le serveur par une ou plusieurs tâches informatiques s'exécutant sur le serveur et toutes gérées par le dispositif de gestion du cluster.

Sur un serveur peuvent en effet s'exécuter en plus des tâches informatiques lancées sur ce serveur par le dispositif de gestion du cluster, d'autres processus tels que typiquement des processus internes au serveur lancés par exemple par son système d'exploitation. Dans ce mode de réalisation, on s'assure que seules les tâches gérées et positionnées à proprement parler par le dispositif de gestion du cluster sont prises en compte par celui-ci lors de l'allocation des ressources aux tâches qui lui sont présentées. Autrement dit, ce mode de réalisation permet une intervention en force du dispositif de gestion par rapport aux droits (i.e. quantités de ressource) qui lui sont réservés sur le serveur.

Une façon de mettre en œuvre ce mode de réalisation est par exemple la suivante :

— la mesure de l'utilisation réelle courante de la ressource informatique sur le serveur comprend une pluralité de valeurs notées U_R(n,fi, j=l,...J, associées respectivement à une pluralité de tâches informatiques Tj, j=l,...J, positionnées par le dispositif de gestion du cluster sur le serveur, J et n désignant des entiers supérieurs ou égaux à 1, chaque valeur U_R(n,fi correspondant à une mesure de l'utilisation réelle de la ressource informatique sur le serveur par la tâche Tj ;

— ladite mise à jour (F30) comprend :

o une première étape d'évaluation pour chaque tâche Tj, d'une valeur courante EU_R(n,j) d'une estimation d'une quantité déjà utilisée de la ressource informatique sur le serveur par la tâche informatique Tj selon l'équation :

EU_R(n,j) = max((l - a)EU_R ( - 1, ;) + U_R(n,j), U_R(n,j)) ou selon l'équation : EU_R(n,j) = (1 - a)EU_R (n - 1, ;) + U_R(n,j)

où :

EU_R (n - lj) désigne une valeur évaluée à un instant précédent de l'estimation de la quantité déjà utilisée de la ressource informatique sur le serveur par cette tâche informatique Tj ; et

■ est un facteur réel compris entre 0 et 1 ;

o une deuxième étape d'évaluation de la valeur courante notée EU_R(n) de l'estimation de la quantité déjà utilisée de la ressource informatique sur le serveur selon l'équation :

ou selon l'équ où J désigne le nombre de tâches informatiques positionnées sur le serveur par le dispositif de gestion du cluster au moment de la deuxième étape d'évaluation.

Dans cette variante, on a donc accès à des informations plus précises sur l'utilisation réelle du serveur, puisque ce sont des mesures de l'utilisation réelle du serveur pour chaque tâche informatique positionnée sur le serveur (c'est-à-dire s'exécutant effectivement sur celui-ci ou pour laquelle une quantité de la ressource a été réservée par le dispositif de gestion sur le serveur) qui sont disponibles et utilisées lors de la mise à jour de la valeur EU_R(n). De cette sorte, lorsqu'une tâche disparaît et libère de la ressource sur le serveur, cela est pris en compte instantanément dans sa contribution à la quantité EU_R(n) (la somme réalisée pour évaluer EU_R(n) ne tient en effet compte que des tâches positionnées sur le serveur à cet instant, c'est-à-dire au moment de l'évaluation de EU_R(n)).

On note toutefois que cette variante requiert des calculs supplémentaires pour mettre à jour la quantité EU_R(n), liés à la gestion individuelle des tâches Tj, j=l,...,J. Ces calculs peuvent être mis en œuvre préférentiel lement localement au niveau de chaque serveur puis être remontés au dispositif de gestion du cluster par les nœuds.

Dans un autre mode de réalisation de l'invention dans lequel la variable V mise à jour est l'estimation EU_R de la quantité déjà utilisée de la ressource informatique sur le serveur, et si l'événement détecté est l'obtention de la mesure de l'utilisation réelle courante de la ressource informatique sur le serveur, ladite valeur courante notée EU_R(n) de la variable V est mise à jour selon l'équation :

EU_R(n) = U_R(n) + DR_R(ri) où U_R(n) désigne une mesure courante de l'utilisation réelle de la ressource informatique sur le serveur, et DR_R(n) désigne une valeur courante d'une quantité de la ressource informatique réservée pour au moins une tâche informatique par le dispositif de gestion sur le serveur.

En outre, dans ce mode de réalisation, le procédé peut comprendre en outre :

— une étape de mise à jour de la valeur courante DR_R(n) de la quantité de la ressource informatique réservée pour au moins une tâche informatique par le dispositif de gestion sur le serveur est obtenue selon l'équation :

DR_R(n) = (1 - )DR_R(n - 1)

où β désigne un facteur réel compris entre 0 et 1 et DR_R(n - 1) désigne une quantité de la ressource informatique réservée par le dispositif de gestion sur le serveur obtenue à un instant précédent ;

— une étape de détection de la mise à jour de la valeur courante DR_R(n) ; et

— une étape de mise à jour de la valeur courante de la variable EU_R selon l'équation :

EU_R(n) = U_R(n) + DR_R(n).

Dans ce mode de réalisation, la pondération (par un facteur (l - β) ici) est appliquée non plus sur la mesure de l'utilisation réelle des ressources sur le serveur mais sur les ressources qui sont réservées par le dispositif de gestion du cluster sur ce serveur. Autrement dit, on effectue un lissage des quantités de ressource réservées et non plus de l'utilisation réelle de la ressource. Ce mode de réalisation assure que le dispositif de gestion du cluster prend en compte, lors de l'allocation de ressource à une nouvelle tâche, une quantité de cette ressource utilisée sur le serveur toujours au moins égale à son utilisation réelle (autrement dit, on s'affranchit dans ce mode de réalisation de recourir à une fonction « max » comme dans les exemples précédemment décrits).

Dans un autre mode de réalisation, le procédé de mise à jour comprend en outre :

— si l'événement détecté est une réservation par le dispositif de gestion pour une tâche informatique d'une quantité R_R_Tnew de la ressource informatique sur le serveur, une étape de mise à jour de la valeur courante DR_R(n) de la quantité de la ressource informatique réservée pour au moins une tâche informatique par le dispositif de gestion sur le serveur utilisant ladite quantité R_R_Tnew et

une quantité DR_R(n - 1) de la ressource informatique réservée par le dispositif de gestion sur le serveur obtenue à un instant précédent,

— si l'événement détecté est une libération par une tâche informatique d'une quantité R_R_Told de la ressource informatique sur le serveur, une étape de mise à jour de la valeur courante DR_R(n) de la quantité de la ressource informatique réservée pour au moins une tâche informatique par le dispositif de gestion sur le serveur utilisant ladite quantité R_R_Told et la quantité DR_R(n - 1) ;

et dans lequel ladite mise à jour de la valeur courante de la variable EU_R utilise ladite quantité de la ressource informatique réservée selon l'équation : EU_R(n) = U_R(n) + DR_R(ri) .

Le choix de l'un ou l'autre des modes de réalisation précédemment décrits peut dépendre de différents paramètres, comme notamment du contexte dans lequel est mise en œuvre l'invention ou encore d'un compromis entre complexité d'implémentation et performance de l'allocation de ressources réalisée par le dispositif de gestion.

Dans un mode particulier de réalisation, le procédé de mise à jour est mis en œuvre par le dispositif de gestion du cluster.

Corrélativement, dans ce mode de réalisation, l'invention vise également un dispositif de gestion d'un cluster de serveurs comprenant :

— un module de réception ;

— un module de détermination, activé sur réception par le module de réception d'une requête d'exécution d'une tâche informatique, ladite tâche informatique étant associée à une quantité prédéterminée d'une ressource informatique requise initialement pour son exécution, le module de détermination étant configuré pour déterminer au moins un serveur du cluster apte à exécuter la tâche informatique en utilisant la quantité prédéterminée de la ressource informatique requise initialement pour l'exécution de la tâche informatique, une capacité maximale du serveur pour la ressource informatique et une estimation d'une quantité déjà utilisée de la ressource informatique sur le serveur ;

— un module de sélection configuré pour sélectionner un serveur pour exécuter la tâche informatique parmi ledit au moins un serveur du cluster déterminé par le module de détermination ;

Le dispositif de gestion selon l'invention est remarquable en ce qu'il comprend en outre :

— un module de détection configuré pour détecter un ensemble prédéfini d'événements ; et

— un module de mise à jour activé pour au moins un serveur du cluster, et configuré pour mettre à jour au moins une valeur courante d'une variable notée V choisie parmi l'estimation de la quantité déjà utilisée de la ressource informatique sur le serveur et la capacité maximale du serveur pour la ressource informatique, ledit module de mise à jour étant activé sur chaque détection d'un événement parmi l'ensemble prédéfini d'événements par le module de détection, et configuré pour :

o si l'événement détecté est une obtention d'une mesure (U_R(n)) d'une utilisation réelle courante de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite mesure de l'utilisation réelle courante de la ressource informatique sur le serveur ;

o si l'événement détecté est une réservation par le dispositif de gestion pour une tâche informatique d'une quantité de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite quantité de la ressource informatique réservée ; et o si l'événement détecté est une libération par une tâche informatique d'une quantité de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite quantité de la ressource informatique libérée.

Dans un autre mode de réalisation, le procédé de mise à jour est mise en œuvre par le serveur. Le procédé de gestion comprend alors en outre une étape de transmission de ladite au moins une valeur mise à jour par le serveur au dispositif de gestion du cluster.

Corrélativement, dans ce mode de réalisation, l'invention vise aussi un serveur appartenant à un cluster de serveurs géré par un dispositif de gestion, ledit serveur étant apte à exécuter au moins une tâche informatique gérée par ledit dispositif de gestion, ladite au moins une tâche informatique utilisant lors de son exécution au moins une ressource informatique du serveur, ce serveur comprenant des modules activés pour au moins un intervalle de temps et comprenant :

— un module de mesure configuré pour mesurer une utilisation réelle de la ressource informatique sur le serveur ;

— un module de détection configuré pour détecter un ensemble prédéfini d'événements ; et — un module de mise à jour configuré pour mettre à jour au moins une valeur courante d'une variable notée V choisie parmi une estimation d'une quantité déjà utilisée de la ressource informatique sur le serveur et une capacité maximale du serveur pour la ressource informatique, ledit module de mise à jour étant activé sur chaque détection par le module de détection d'un événement parmi l'ensemble prédéfini d'événements et configuré pour :

o si l'événement détecté est une obtention d'une mesure d'une utilisation réelle courante de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite mesure de l'utilisation réelle courante de la ressource informatique sur le serveur ;

o si l'événement détecté est une réservation par le dispositif de gestion pour une tâche informatique d'une quantité de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite quantité de la ressource informatique réservée ; et

o si l'événement détecté est une libération par une tâche informatique d'une quantité de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite quantité de la ressource informatique libérée ; et

— un module de transmission, configuré pour transmettre au dispositif de gestion ladite valeur courante de la variable V mise à jour.

Comme mentionné précédemment, ce mode de réalisation peut permettre de faciliter l'implémentation progressive de l'invention en limitant les développements nécessaires à sa mise en œuvre réalisés sur le dispositif de gestion du cluster.

Dans un mode particulier de réalisation, les différentes étapes du procédé de mise à jour et/ou les différentes étapes du procédé de gestion sont déterminées par des instructions de programmes d'ordinateurs. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre dans un dispositif de gestion, dans un serveur ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé de mise à jour tel que décrit ci- dessus.

L'invention vise également un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre dans un dispositif de gestion ou plus généralement dans un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre des étapes d'un procédé de gestion tel que décrit ci-dessus.

Chacun de ces programmes peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.

L'invention vise aussi un support d'informations ou d'enregistrement lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci- dessus.

Le support d'informations ou d'enregistrement peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur.

D'autre part, le support d'informations ou d'enregistrement peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type Internet.

Alternativement, le support d'informations ou d'enregistrement peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question.

L'invention vise également un système informatique comprenant :

— un cluster de serveurs comprenant une pluralité de serveurs, chaque serveur comprenant au moins une ressource informatique permettant l'exécution de tâches informatiques ;

— un dispositif de gestion du cluster de serveurs ;

dans lequel le dispositif de gestion du cluster est conforme à l'invention et/ou au moins un serveur du cluster est conforme à l'invention.

On peut également envisager, dans d'autres modes de réalisation, que le procédé de mise à jour, le procédé de gestion, le dispositif de gestion, le serveur et le système informatique selon l'invention présentent en combinaison tout ou partie des caractéristiques précitées. Brève description des dessins

D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures :

— la figure 1 représente, de façon schématique, un système informatique conforme à l'invention, dans un mode particulier de réalisation, le système informatique comprenant un cluster de serveurs et un dispositif de gestion du cluster ;

— la figure 2 représente l'architecture matérielle du dispositif de gestion du cluster de la figure 1 ;

— la figure 3A représente, sous forme d'ordinogramme, les différentes étapes d'un procédé de gestion tel qu'il est mis en œuvre dans un mode particulier de réalisation par le dispositif de gestion de la figure 1 ;

— la figure 3B représente, sous forme d'ordinogramme les différentes étapes d'un procédé de mise à jour tel qu'il est mis en œuvre dans un mode particulier de réalisation par le dispositif de gestion de la figure 1 ; et

— la figure 3C représente, sous forme d'ordinogramme les différentes étapes d'un procédé de mise à jour dans une variante de réalisation.

Description détaillée de l'invention

La figure 1 représente, dans son environnement, un système informatique 1, conforme à l'invention, dans un premier mode de réalisation.

Conformément à l'invention, le système informatique 1 comprend

— un cluster 2 de serveurs comprenant une pluralité de serveurs SI, S2,..., SK, K désignant un entier supérieur à 1, reliés en réseau. Chaque serveur Sk, k=l,...,K comprend diverses ressources informatiques (matérielles et/ou logicielles) permettant l'exécution de tâches informatiques. Ces ressources sont par exemple de la mémoire, de l'espace disque, du CPU, des accès réseaux, etc. Aucune limitation n'est attachée à la nature des ressources informatiques proposées par les serveurs S1,...,SK du cluster 2. Toutefois, pour mieux illustrer l'invention, on s'attache ici à une ressource informatique particulière R qui consiste en de la mémoire ; et

— un dispositif 3 de gestion du cluster 2 de serveurs, conforme à l'invention.

Le dispositif 3 de gestion du cluster 2 est configuré pour, sur réception d'une requête REQ en provenance d'un dispositif client 4 (ex. ordinateur) d'un utilisateur du cluster 2 demandant l'exécution d'au moins une tâche informatique T, allouer des ressources du cluster 2 à ce client pour l'exécution de cette tâche. Plus spécifiquement, sur réception de la requête REQ, le dispositif 3 de gestion du cluster 2 identifie un serveur Sk du cluster 2 apte à exécuter la tâche informatique T, c'est-à-dire un serveur Sk disposant des ressources nécessaires à son exécution (mémoire, CPU, etc.), puis lance la tâche informatique T sur ce serveur Sk pour qu'elle y soit exécutée. Aucune limitation n'est attachée à la nature de la tâche informatique T à exécuter sur le cluster 2. Il peut s'agir de tout type de tâche associée à une application logicielle APP installée sur le dispositif client 4 ou à n'importe quel programme informatique de manière générale. De façon connue un tel programme informatique comprend une pluralité de tâches informatiques à exécuter, et qui peuvent être soumises en rafales au dispositif 3 de gestion du cluster 2 pour être exécutées en parallèle sur différents serveurs du cluster 2. On s'intéresse ici plus particulièrement au traitement réalisé par le dispositif 3 de gestion sur l'une de ces tâches, à savoir sur la tâche T. Un traitement similaire est appliqué sur l'ensemble des tâches contenues dans la requête REQ.

Chacune des tâches envoyées par l'application logicielle APP au dispositif 3 de gestion du cluster 2 a des besoins en ressources informatiques pour permettre son exécution sur le cluster 2. Ces besoins sont spécifiés ici par l'utilisateur du dispositif client 4 pour chacune des tâches et pour chacune des ressources. Pour la ressource informatique R et la tâche T, l'utilisateur du dispositif client 4 spécifie une quantité R_R_T de mémoire requise « initialement » pour l'exécution de la tâche T. La quantité R_R_T peut être déterminée de manière grossière par l'utilisateur du dispositif client 4, sur la base de ses connaissances des opérations mises en œuvre par la tâche informatique T et la consommation en terme de mémoire requise par ces opérations. On note que bien que l'utilisateur du dispositif client 4 tente dans la mesure du possible de fournir une quantité R_R_T proche de l'utilisation réelle de la ressource R par la tâche informatique T, cette quantité R_R_T est difficile en pratique à estimer précisément pour l'utilisateur : elle est généralement surestimée par l'utilisateur de sorte à s'assurer que la tâche informatique T se voit allouer une quantité suffisante de mémoire par le dispositif 3 de gestion du cluster 2 pour pouvoir être exécutée dans de bonnes conditions. La quantité R_R_T ainsi prédéterminée est transmise ici dans la requête REQ d'exécution de la tâche informatique T adressée au dispositif 3 de gestion du cluster 2.

Dans le mode de réalisation décrit ici, le dispositif 3 de gestion du cluster 2 a l'architecture matérielle d'un ordinateur, telle qu'illustrée à la figure 2. Il comprend notamment un processeur 5, une mémoire vive 6, une mémoire morte 7, une mémoire flash non volatile 8 ainsi que des moyens de communication 9 lui permettant de communiquer notamment d'une part avec le dispositif client 4 et d'autre part avec les serveurs Sk, k=l,...,K du cluster 2. Ces moyens de communication 9 comprennent par exemple une carte réseau, bien connue en soi.

La mémoire morte 7 du dispositif 3 de gestion du cluster 2 constitue un support d'enregistrement conforme à l'invention, lisible par le processeur 8 et sur lequel est enregistré ici un programme d'ordinateur PROG conforme à l'invention.

Le programme d'ordinateur PROG définit des modules fonctionnels (et logiciels ici), configurés pour mettre en œuvre les étapes du procédé de mise à jour et les étapes du procédé de gestion de tâches informatiques selon l'invention. Ces modules fonctionnels s'appuient sur et/ou commandent les éléments matériels 5-9 du dispositif 3 de gestion cités précédemment. Ils comprennent notamment ici, comme illustré sur la figure 1 : — un module 3A de réception de requêtes en provenance de dispositifs clients comme le dispositif client 4, ce module 3A s'appuyant sur les moyens de communication 9 ;

— un module 3B de détermination, activé sur réception par le module 3A de réception d'une requête d'exécution d'une tâche informatique, le module de détermination étant configuré pour déterminer au moins un serveur du cluster 2 apte à exécuter la tâche informatique ;

— un module 3C de sélection configuré pour sélectionner un serveur pour exécuter la tâche informatique parmi les serveurs du cluster déterminés par le module 3B de détermination ;

— un module 3D de détection, configuré pour détecter un ensemble prédéfini d'événements relatifs à la ressource R et détaillés ultérieurement ; et

— un module 3E de mise à jour, configuré pour mettre à jour à chaque détection d'événement par le module 3D de détection, une ou plusieurs valeurs utilisées par le module 3B de détermination pour déterminer les serveurs susceptibles d'exécuter la tâche informatique en utilisant les mesures d'utilisation réelle de la ressource informatique R obtenues par le module 3D d'obtention.

Les fonctions de ces différents modules sont décrites plus en détail maintenant, en référence à la figure 3 (constituée des figures 3A et 3B) et aux étapes du procédé de mise à jour et du procédé de gestion de tâches informatiques selon l'invention, telles qu'elles sont mises en œuvre, dans le premier mode particulier de réalisation, par le dispositif 3 de gestion du cluster 2.

Comme illustré sur la figure 3, le procédé de gestion de tâches informatiques selon l'invention s'appuie, dans le premier mode de réalisation décrit ici, sur deux processus qui se déroulent en parallèle :

— un processus PI de traitement asynchrone, illustré sur la figure 3A, qui est déclenché par le dispositif 3 de gestion du cluster 2 sur réception par son module 3A de réception de chaque requête d'exécution de tâche(s) informatique(s) sur le cluster 2. Ce processus PI vise à attribuer à chaque tâche informatique des ressources informatiques sur un serveur du cluster 2 afin de permettre son exécution ; et

— un processus P2 de mise à jour, illustré sur la figure 3B, qui est mis en œuvre ici en continu par le dispositif 3 de gestion du cluster 2. Plus particulièrement ici, les mises à jour visent des valeurs utilisées par le dispositif 3 de gestion du cluster 2 pour sélectionner un serveur apte à exécuter une tâche informatique qui lui est confiée. Ces mises à jour sont effectuées dans le premier mode de réalisation sur détection de différents événements appartenant à un ensemble prédéterminé d'événements. Cet ensemble comprend ici trois événements, à savoir, la remontée (périodique) par les serveurs du cluster 2 de mesures d'utilisation de leurs ressources, le positionnement de tâches et la réservation de ressources en découlant sur des serveurs, et la libération de ressources sur les serveurs. Les valeurs mises à jour lors du processus P2 sont prises en compte préférentiellement dès leurs disponibilités par le processus PI pour le traitement des requêtes reçues après chaque mise à jour.

Nous allons maintenant décrire plus en détail chacun de ces processus. En référence à la figure 3A, on suppose que le dispositif 3 de gestion du cluster 2 reçoit, par l'intermédiaire de ses moyens de communication 9 et de son module de réception 3A, une requête REQ d'exécution d'une tâche informatique T du dispositif client 4 (étape E10). Cette requête REQ comprend, comme mentionné précédemment, une quantité R_R_T de ressource R requise initialement pour que la tâche informatique T puisse s'exécuter convenablement, cette quantité R_R_T ayant été prédéterminée par l'utilisateur du dispositif client 4.

Sur réception de la requête REQ(T,R_R_T), le dispositif 3 de gestion du cluster 2, par l'intermédiaire de son module 3B de détermination, détermine ici parmi les serveurs S1,...,SK du cluster 2 quels sont ceux qui sont aptes à exécuter la tâche T, compte tenu des besoins R_R_T en ressource R spécifiés par l'utilisateur. Autrement dit, le module 3B de détermination détermine quel(s) serveur(s) dispose d'une quantité de ressource R suffisante pour exécuter la tâche informatique T. On note que cette détermination n'a pas besoin d'être exhaustive, et une liste de serveurs réduite à un unique serveur peut être suffisante.

A cet effet, pour chaque serveur Sk du cluster 2, k=l,...,K (étape d'initialisation E20, étape test E50 puis étape d'incrémentation E60), le module 3B de détermination détermine si le serveur Sk vérifie l'inégalité (eql) suivante (étape test E30) :

R_R_T + EU_R(Sk) < CL_R(Sk) (eql)

dans laquelle :

— CL_R(Sk) désigne la capacité maximale du serveur Sk pour la ressource informatique R (i.e. quantité maximale de ressource R disponible sur le serveur Sk). Cette capacité maximale est remontée ici périodiquement au dispositif 3 de gestion par chaque serveur Sk ; et

— EU_R(Sk) désigne une estimation d'une quantité déjà utilisée de la ressource informatique R sur le serveur Sk.

Si le serveur Sk vérifie l'inégalité (eql) (réponse oui à l'étape test E30), il est identifié par le module 3B de détermination comme un serveur susceptible d'exécuter la tâche T (étape E40).

Sinon (réponse non à l'étape test E30 et étape test E50), le module 3B de détermination teste un nouveau serveur parmi les serveurs non encore testés du cluster 2 (réponse non à étape test E50 et étape d'incrémentation E60).

Dans le premier mode de réalisation décrit ici, une fois que tous les serveurs Sk, k=l,..,K du cluster 2 ont été testés (réponse oui à l'étape test E50), le module 3C de sélection sélectionne un serveur SkO parmi les serveurs identifiés comme étant aptes à exécuter la tâche informatique T compte-tenu de ses besoins R_R_T en ressource R initialement fournis par l'utilisateur (étape E70). Aucune limitation n'est attachée aux critères utilisés par le dispositif 3 de gestion du cluster 2 pour sélectionner le serveur SkO. Ce choix peut être fait par exemple par rapport aux autres ressources requises pour l'exécution de la tâche et disponibles sur le serveur SkO, par rapport à des contraintes géographiques, etc. Suite à cette sélection, le dispositif 3 de gestion du cluster 2 ordonne (ou déclenche) le lancement de la tâche T sur le serveur SkO sélectionné (étape E80). En d'autres mots, il positionne la tâche T sur le serveur SkO et réserve sur ce serveur la quantité R_R_T de ressource R en vue de son exécution.

Le dispositif 3 de gestion du cluster 2 procède ainsi pour chaque tâche informatique qui lui est soumise.

On note que le processus asynchrone PI qui vient d'être décrit en référence à la figure 3A et qui est mis en œuvre par le dispositif 3 de gestion du cluster 2 se rapproche des traitements mis en œuvre par les systèmes de gestion de cluster de l'état de la technique, et notamment par les systèmes Borg et Hadoop Yarn cités précédemment. Dans les traitements mis en œuvre par ces systèmes de l'état de la technique, l'estimation EU_R(Sk) de la quantité de ressource R déjà utilisée sur le serveur Sk est prise égale, dans l'équation (eq l), à la quantité Q_R(Sk) de ressource R initialement réservée (i.e. allouée) par le système de gestion sur le serveur Sk pour l'exécution des tâches reçues antérieurement et toujours en cours de traitement par le serveur Sk, c'est-à-dire toujours positionnées sur le serveur Sk (ce nombre de tâches positionnées est supposé égal à JO, JO désignant un entier supérieur à 0). Cette quantité Q_R(Sk) se base sur les déclarations des besoins R_R_Tj en ressource R fournis par les utilisateurs pour ces tâches antérieures Tj, j= l,...,J0, autrement dit, elle est égale à la somme des besoins R_R_Tj, j= l,...,J0 en ressource R déclarés par les utilisateurs à l'origine de ces J0 tâches Tj, j = l,...,J0, soit encore :

Q_R(Sk) =∑ ^J ° ₌₁ R_R_Tj .

En d'autres mots encore, les systèmes de gestion de l'état de la technique tels que ceux précités appliquent, pour l'attribution d'une ressource R à une tâche informatique T entrante qui leur est soumise, l'inégalité suivante (eq l :

R_R_T + Q_R(Sk) < CL_R (Sk) (eql')

Conformément à l'invention, le dispositif 3 de gestion du cluster 2 se distingue des systèmes de gestion de l'état de la technique en ce que certaines valeurs utilisées dans l'équation (eq l), et en particulier la valeur EU_R(Sk) et/ou la valeur de capacité limite CL_R(Sk), sont mises à jour sur détection de trois événements prédéterminés (définissant un ensemble prédéterminé d'événements au sens de l'invention) (étape F10). Ces trois événements comprennent :

— l'obtention de mesures d'utilisation réelle (courante) de la ressource informatique R sur les serveurs Sk, k= l,...,K du cluster 2 serveur ;

— la réservation par le dispositif 3 de gestion du cluster pour une tâche informatique d'une quantité de la ressource informatique R sur un serveur Sk, k= l,...,K du cluster 2 ; et

— la libération par une tâche informatique d'une quantité de la ressource informatique R sur un serveur Sk, k= l,...,K du cluster 2.

Cette mise à jour est illustrée à la figure 3B décrite maintenant (processus continu P2) pour la quantité EU_R(Sk) (variable V au sens de l'invention). La prise en compte des trois événements précités permet au dispositif 3 de gestion du cluster 2 d'avoir une information plus précise sur la quantité de ressource R disponible sur chaque serveur lors de l'attribution des tâches informatiques via le processus Pl. Chaque événement désigné par EV détecté parmi ces trois événements entraine une mise à jour de la valeur courante de la variable V considérée (ici EU_R(Sk)). On note dans la suite de la description V(n) la valeur courante mise à jour de la variable V, n désignant un entier supérieur ou égal à 0 indexant la mise à jour (en d'autres mots, chaque événement détecté incrémente l'entier n (étapes d'initialisation F00 puis d'incrémentation F20)). Ainsi, lorsque cette variable est EU_R(Sk), la valeur courante de cette variable est notée EU_R(n,Sk). Il en est de même pour les autres variables considérées dans la description. On note qu'une valeur dite courante désigne une valeur disponible ou que l'on modifie à un instant considéré dit courant (c'est-à-dire à un instant en cours de réalisation). Dans le cas d'une mesure, celle-ci peut avoir été réalisée à un instant précédent (notamment en cas de périodicité de la mesure) ; si tel est le cas, la mesure courante désigne la mesure qui est disponible au moment courant où on l'utilise.

Conformément à l'invention, suivant l'événement détecté, une mise à jour différente de la valeur courante de la variable V est envisagée. Nous allons détailler maintenant ces trois mises à jour.

Comme indiqué précédemment, dans le premier mode de réalisation décrit ici, on suppose que la remontée des mesures effectuées sur les serveurs Sk, k=l,...,K vers le dispositif 3 de gestion du cluster 2 est réalisée de façon périodique, selon une période Tupd. Par souci de simplification, on considère ici une même période Tupd pour tous les serveurs du cluster toutefois l'invention s'applique également à des périodes distinctes d'un serveur à l'autre. En outre, l'invention s'applique également lorsque les mesures sont remontées à des instants prédéterminés, pas nécessairement espacés de façon régulière, ou de façon totalement asynchrone.

Cette obtention périodique des mesures d'utilisation réelle de la ressource R par le dispositif 3 de gestion est détectée par le dispositif 3 de gestion du cluster (réponse oui à l'étape F10 avec EV=UPD-U). Une telle mesure peut être réalisée par chaque serveur Sk au moyen d'outils connus en soi, comme par exemple au moyen d'une commande « top » lancée par le système d'exploitation de chaque serveur Sk périodiquement. On note U_R(n,Sk) la mesure de l'utilisation réelle de la ressource informatique R réalisée sur le serveur Sk et disponible à l'instant courant au niveau du dispositif 3 de gestion du cluster 2.

Chacune des mesures U_R(n,Sk), k=l,...,K obtenue par le dispositif 3 de gestion du cluster 2 est utilisée par le dispositif 3 de gestion du cluster comme une mesure de l'utilisation réelle courante de la ressource informatique R sur le serveur Sk.

A partir de cette mesure, le dispositif 3 de gestion du cluster 2, via son module 3E de mise à jour, met à jour, dans le premier mode de réalisation décrit ici, la valeur courante de l'estimation EU_R(Sk) de la quantité déjà utilisée de la ressource informatique R sur le serveur Sk destinée à être prise en compte par le dispositif 3 de gestion au cours de l'étape E30 du processus PI (étape F30).

Dans le premier mode de réalisation décrit ici, le module 3E de mise à jour calcule la valeur courante EU_R(n,Sk) selon l'équation (eq2) suivante (étape F30) :

EU_R(n, Sk) = (1 - a)EU_R(n - l. Sk) + ai/_i?(n,5fe)(eq2) où a désigne un facteur de pondération réel compris entre 0 et 1. On note que dans cette équation, EU_R(0,Sk) est initialisé à la quantité de le ressource R réservée sur le serveur Sk à un instant t=0 pour l'ensemble des tâches positionnées sur ce serveur par le dispositif 3 de gestion du cluster 2.

On note que l'équation (eq2) permet de mettre à jour l'estimation de la quantité déjà utilisée de la ressource informatique R sur le serveur Sk en calculant la valeur EU_R(n,Sk) à l'instant courant à partir d'une valeur Vpast(n) = EU_R(n - l,Sk) calculée (mise à jour) à un instant précédent (en l'espèce ici, lors de sa précédente mise à jour). Elle comprend une moyenne mobile exponentielle paramétrée par le facteur . Plus le facteur est choisi proche de 0, plus longtemps le dispositif 3 de gestion du cluster tient compte de la quantité de ressources réservée et retarde le moment où il utilise des ressources libres des serveurs qui semblent « indûment » réservées. Au contraire, plus le facteur est choisi proche de 1, plus le dispositif 3 de gestion du cluster oublie rapidement ces ressources réservées par les tâches, prenant le risque que ces ressources soient en fait nécessaires aux tâches pour lesquelles elles avaient été réservées mais utilisées ultérieurement. Le choix du facteur résulte donc d'un compromis entre ces différentes considérations.

L'équation (eq2) permet avantageusement d'ajuster (i.e. de mettre à jour) le niveau EU_R(n,Sk) d'utilisation de la ressource R utilisé par le dispositif 3 de gestion du cluster 2 pour l'allocation des ressources aux tâches informatiques qui lui sont confiées en tenant compte de l'utilisation réelle des ressources sur les serveurs du cluster 2. Ceci permet, si une tâche s'exécutant sur un serveur Sk du cluster 2 requiert moins de ressource R pour s'exécuter que les besoins en cette ressource annoncés initialement par l'utilisateur dans la requête d'exécution de cette tâche, d'allouer à d'autres tâches de la ressource R non utilisée sur le serveur Sk, ou inversement de stopper l'allocation de ressource R à des tâches entrantes si le serveurs Sk n'a plus de ressource R disponible. On obtient donc une meilleure allocation par le dispositif 3 de gestion des ressources du cluster 2, tout en s'assurant d'une bonne exécution des tâches sur le cluster.

Dans le premier mode de réalisation décrit ici, la mise à jour de la valeur courante de la variable EU_R(Sk) au moyen de l'équation (eq2) est réalisée de façon périodique, à chaque remontée de mesures reçue par le dispositif 3 de gestion du cluster 2. En d'autres mots, l'événement d'obtention de mesures (EV=UPD-U) par le dispositif 3 de gestion se reproduit de façon périodique.

En plus de cette mise à jour périodique, conformément à l'invention, d'autres événements (EV=RESA et EV=FREE sur la figure 3B) sont susceptibles de déclencher des mises à jour asynchrones de la valeur courante de la variable V=EU_R(Sk) pour les différents serveurs Sk, k=l,...,K. Plus précisément, ces mises à jour asynchrones sont déclenchées par le module 3E de mise à jour à chaque fois que celui-ci détecte l'un et/ou l'autre des deux événements suivants pour l'un des serveurs Sk :

— la réservation par le dispositif 3 de gestion d'une quantité de la ressource R sur le serveur Sk, pour l'exécution d'une tâche informatique Tnew (suite à l'application du processus PI représenté sur la figure 3A par le dispositif 3 de gestion sur la tâche Tnew) (branche EV=RESA sur la figure 3B). La quantité de ressource réservée pour cette tâche Tnew par le dispositif 3 de gestion sur le serveur Sk correspond aux besoins R_R_Tnew en ressource R requis initialement par l'utilisateur dans la requête d'exécution de cette tâche transmise au dispositif 3 de gestion. Dans la suite de la description, on désigne cet événement par EV=RESA ;

— la libération par une tâche informatique Told d'une quantité de la ressource R sur le serveur Sk, du fait notamment de l'achèvement de cette tâche Told ou de son interruption branche EV=FREE sur la figure 3B). Dans la suite de la description, on désigne par EV=FREE cet événement.

Pour chaque serveur Sk concerné pour lequel un événement EV=RESA est détecté par le dispositif 3 de gestion (via son module de détection 3D) en association avec une tâche Tnew (réponse oui à l'étape de détection F10, branche EV=RESA), la valeur courante de la variable EU_R(Sk) est mise à jour par le module 3E de mise à jour selon l'équation (eq3-RESA) suivante (étape F40) :

EU_R(n,Sk) = EU_R(n - l.Sk) + R_R_Tnew (eq3-RESA) Le dispositif 3 de gestion du cluster 2 étant à l'origine du positionnement (attribution) des tâches sur les différents serveurs Sk du cluster, il peut informer sans délai via son module de sélection 3C, le module de détection 3D de la réservation de nouvelles ressources sur un serveur Sk.

Pour chaque serveur Sk concerné pour lequel un événement EV=FREE est détecté par le dispositif 3 de gestion en association avec une tâche Told (réponse oui à l'étape de détection F10, branche EV=FREE), la valeur courante de la variable EU_R(Sk) est mise à jour par le module 3E de mise à jour selon l'équation (eq3-FREE) suivante (étape F50) :

EU_R(n,Sk) = EU_R(n - l. Sk) - (1 - a) ^nold R_R_Told (eq3-FREE) où nold indexe le nombre de mises à jour de EU_R réalisées sur détection de l'événement UPD-U (nouvelle mesure remontée au dispositif 3 de gestion de l'utilisation réelle de la ressource) depuis l'instant où la quantité de ressource R_R_Told a été réservée pour la tâche Told sur le serveur Sk jusqu'à sa libération, la quantité R_R_Told correspondant aux besoins initialement requis en ressource R déclarés par l'utilisateur dans la requête d'exécution de la tâche Told adressée au dispositif 3 de gestion.

Dans l'équation (eq3)-FREE, le facteur (1 - ) ^nold R_R_Told permet de tenir compte du reliquat de ressource R qui est libérée par la tâche Told au niveau du serveur Sk du fait de la fin de son exécution par le serveur Sk. On note que la prise en compte de ce reliquat présente un intérêt privilégié pour des tâches dont l'exécution est de courte durée (par exemple inférieure à la période de mise à jour Tupd).

Les mises à jour asynchrones de la variable EU_R(Sk) ainsi effectuées à chaque détection d'un événement EV=RESA et/ou EV=FREE visent à tenir compte des tâches allouées à chaque serveur Sk par le dispositif 3 de gestion du cluster 2 et des tâches qui se sont achevées sur chaque serveur Sk entre deux remontées de mesures du serveur Sk (et donc entre deux mises à jour périodiques de la variable EU_R(Sk)).

On note que, comme mentionné précédemment, les événements EV=RESA peuvent être détectés aisément par le dispositif 3 de gestion du cluster 2, celui-ci étant en charge de l'allocation des ressources aux tâches informatiques qui lui sont confiées. Les événements EV=FREE sont détectés ici par les serveurs Sk sur lesquelles les tâches Told avaient été distribuées (positionnées) et remontées par ces serveurs au dispositif 3 de gestion du cluster 2 (accompagnées des indices nold correspondant). La réception par le dispositif 3 de gestion d'une notification d'un serveur Sk de l'achèvement d'une tâche Told constitue une détection d'un événement EV=FREE pour ce serveur Sk au sens de l'invention. Le dispositif 3 de gestion dispose alors des informations nécessaires pour évaluer le facteur (1 - a) ^nold R_R_Told.

La valeur courante EU_R(n,Sk) mise à jour de la variable EU_R(Sk) est utilisée dès qu'elle est disponible (i.e. dès sa mise à jour terminée) par le module de détermination 3B du dispositif 3 de gestion du cluster 2 dans le cadre du processus PI, et plus précisément dans l'inégalité (eql) pour sélectionner un serveur du cluster 2 apte à exécuter une nouvelle tâche entrante reçue à compter de cette mise à jour.

Les étapes F10 à F50 du processus P2 sont ensuite réitérées à chaque détection d'un événement EV=UPD-U, RESA ou FREE par le module de détection 3D.

Dans une première variante de ce premier mode de réalisation, le module 3E de mise à jour utilise lors de l'étape F30 pour calculer la valeur courante EU_R(n,Sk) l'équation (eq2 suivante à la place de l'équation (eq2) :

EU_R(n, Sk) = max((l - a)EU_R (n - l. Sfc) + aU_R(n, Sk ^~ ), U_R(n, Sk)) (eq2') où max(x,y) désigne la fonction qui fournit la valeur maximale parmi les valeurs x et y. Les processus de mise à jour décrits aux étapes F40 et F50 restent par ailleurs identiques à celui décrit précédemment.

Cette première variante de réalisation permet de tenir compte plus rapidement de l'utilisation réelle des ressources sur le serveur Sk.

Dans une deuxième variante du premier mode de réalisation illustrée à la figure 3C, le module 3E de mise à jour utilise pour calculer la valeur courante EU_R(n,Sk) l'équation (eq2") suivante à la place de l'équation (eq2) (étape G30) :

EU_R(n, Sk) = DR_R(n, Sk) + U_R(n, Sk) (eq2") où DR_R(n, Sk) désigne une valeur courante lissée de la quantité de la ressource informatique réservée pour au moins une tâche informatique par le dispositif 3 de gestion sur le serveur Sk à l'instant courant. La valeur lissée DR_R(n, Sk) est calculée ici par le module 3E de mise à jour lors de l'étape G30, dans la deuxième variante, selon l'équation (eq4) suivante :

DR_R(n, Sk) = (1 - )DR_R(n - l, Sk) (eq4)

où β est un facteur de pondération réel compris entre 0 et 1. On note que le choix du facteur de pondération /? répond à un compromis similaire à celui évoqué précédemment pour le choix du facteur de pondération a (Le. rapidité d'oubli des ressources réservées versus utilisation réelle constatée de ces ressources). Dans cette équation, DR_R(0,Sk) est initialisé à la quantité de le ressource R réservée sur le serveur Sk à l'instant t=0 pour l'ensemble des tâches positionnées sur ce serveur.

On suppose ici que la valeur de la variable DR_R est mise à jour périodiquement selon la même période Tupd que la remontée des mesures vers le dispositif 3 de gestion.

Toutefois cette hypothèse n'est pas limitative en soi, et la mise à jour de la valeur de DR_R selon l'équation (eq4) peut être réalisée selon une autre période, asynchrone par rapport à la remontée de U_R(n,Sk). Chaque mise à jour de la valeur de DR_R(Sk) entraîne alors une mise à jour de la valeur de EU-R(Sk). Il s'agit donc d'un autre événement (événement EV=UPD-D représenté en pointillés sur la figure 3C), au même titre que les événements EV=UPD-U, EV=RESA et EV=FREE décrits précédemment, susceptible dans la deuxième variante décrite ici d'être détecté par le module de détection 3D et de déclencher une mise à jour de la valeur courante de la variable V(=EU-R(Sk) ici) (étape G40).

En outre, dans cette deuxième variante, lors de la détection d'un événement EV=RESA ou EV=FREE, la valeur de DR_R est mise à jour suivant les équations (eq5-RESA) pour la détection d'un événement EV=RESA (étape G50) et (eq5-FREE) pour la détection d'un événement EV=FREE (étape G60) suivantes :

D_R(n,Sk) = D_R(n - l,Sk) + R_R_Tnew (eq5-RESA) et

D_R n, Sk) = D_R(n - l,Sk) - (1 - ) ^nold R_R_Told (eq5-FREE) où nold indexe le nombre de mises à jour de D_R réalisées sur détection de l'événement UPD-U (nouvelle mesure remontée au dispositif 3 de gestion de l'utilisation réelle de la ressource) depuis l'instant où la quantité de ressource R_R_Told a été réservée pour la tâche Told sur le serveur Sk jusqu'à sa libération, la quantité R_R_Told correspondant aux besoins initialement requis en ressource R déclarés par l'utilisateur dans la requête d'exécution de la tâche Told adressée au dispositif 3 de gestion.

La valeur courante de EU-R est ensuite mise à jour durant les étapes G50 et G60 suivant l'équation (eq2") où U_R(n,Sk) désigne la valeur courante disponible au niveau du dispositif 3 de gestion de la mesure d'utilisation réelle de la ressource R. Dans une troisième variante du premier mode de réalisation, chaque mesure de l'utilisation réelle de la ressource informatique R est réalisée sur chaque serveur Sk du cluster 2, k= l,...,K, pour chaque tâche distincte Tj exécutée par ce serveur Sk utilisant la ressource informatique R, j=0,...,Jl, J l désignant un entier supérieur à 0 dénombrant les tâches positionnées sur le serveur Sk lors de la mesure. On se limite ici aux seules tâches Tj exécutées par le serveur Sk et gérées par le dispositif 3 de gestion du cluster 2 (c'est-à-dire qui ont été lancées sur le serveur Sk sur instruction du dispositif 3 de gestion du cluster 2 après exécution du processus PI).

On désigne par U_R(n,Sk,j) la mesure de l'utilisation réelle de la ressource informatique R réalisée sur le serveur Sk pour la tâche Tj à l'issue de l'intervalle de temps t(n-l). Chaque mesure U_R(n,Sk,j) réalisée sur un serveur Sk est envoyée à l'issue de l'intervalle de temps t(n) au dispositif 3 de gestion du cluster 2, et obtenue au cours de l'étape F20 par le module 3D d'obtention du dispositif 3 de gestion du cluster 2. Chaque mesure U_R(n,Sk,j) est utilisée par le dispositif 3 de gestion du cluster comme une mesure de l'utilisation réelle de la ressource informatique R sur le serveur Sk par la tâche Tj pour l'intervalle de temps t(n).

A partir de ces mesures, le dispositif 3 de gestion du cluster 2, via son module 3E de mise à jour, évalue dans la troisième variante, au cours de l'étape F30, une estimation EU_R(n,Sk,j) de la quantité déjà utilisée de la ressource informatique R sur chaque serveur Sk par chaque tâche informatique Tj gérée par le dispositif 3 de gestion du cluster 2 et exécutée sur le serveur Sk en utilisant l'équation (eq6) suivante :

EU_R(n,Sk,j) = (1 - a)EU_R (n - l. Sk.j) + U_R(n,Sk,j) (eq 6) ou l'équation (eqô suivante :

EU_R(n, Sk,j) = max((l - a)EU_R (n - l.Sk.j) + aU_R(n,Sk,j), U_R(n,Sk,jj) (eq 6') dans lesquelles est un facteur de pondération réel compris entre 0 et 1, choisi comme décrit précédemment dans les autres variantes de réalisation. On note que dans cette troisième variante, EU_R(n0j,j) est initialisé à la quantité R_R_Tj de ressource informatique R requise initialement pour l'exécution de la tâche Tj, nOj désignant l'indice de mise à jour correspondant à l'attribution de la tâche informatique Tj au serveur Sk par le dispositif 3 de gestion.

Puis, dans la troisième variante décrite ici, au cours de l'étape F30, le module 3E de mise à jour évalue à partir des valeurs EU_R(n,Sk,fi obtenues pour chacune des tâches Tj la quantité EU_R(n, Sk) selon l'équation (eq2'") suivante :

Jlact

EU_R(n, Sk) = ^ EU_R(n,Sk,j) (eq2"')

7 = 0

ou selon l'équation (eq2 ⁽⁴⁾ ) suivante :

EU_R(n, Sk) = max(∑ ^J _j= ^1a ₀ ^ct EU_R(n,Sk,j) ,Σ^' U_R(n,Sk,j)) (eq2 ⁽⁴⁾ ) dans lesquelles Jlact désigne le nombre de tâches positionnées sur le serveur Sk (c'est-à-dire attribuées au serveur Sk par le dispositif 3 de gestion) parmi les Jl tâches pour lesquelles des mesures ont été remontées au dispositif 3 de gestion. Dans le premier mode de réalisation et dans ses trois variantes précédemment décrites, c'est le dispositif 3 de gestion du cluster 2 qui, à partir des mesures remontées par les serveurs Sk, k=l,...,K du cluster 2, met à jour la valeur de la quantité EU_R(Sk) utilisée par le module 3B de détermination du dispositif 3 de gestion du cluster 2 pour sélectionner un serveur du cluster pour exécuter une tâche entrante.

Dans un second mode de réalisation, chaque serveur Sk du cluster 2 est un serveur conforme à l'invention. Il comprend :

— un module de mesure, configuré pour mesurer, périodiquement ici, l'utilisation réelle de sa ressource informatique R ;

— un module de détection configuré pour détecter un ensemble prédéfini d'événements (UPD-U, RESA et FREE) ; et

— un module de mise à jour configuré pour mettre à jour au moins une valeur courante d'une variable notée V choisie parmi une estimation d'une quantité déjà utilisée de la ressource informatique sur le serveur et une capacité maximale du serveur pour la ressource informatique, ledit module de mise à jour étant activé sur chaque détection par le module de détection d'un événement parmi l'ensemble prédéfini d'événements et configuré pour :

o si l'événement détecté est une obtention d'une mesure (U_R(n)) d'une utilisation réelle courante de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite mesure de l'utilisation réelle courante de la ressource informatique sur le serveur ;

o si l'événement détecté est une réservation par le dispositif de gestion pour une tâche informatique d'une quantité de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite quantité de la ressource informatique réservée ; et

o si l'événement détecté est une libération par une tâche informatique d'une quantité de la ressource informatique sur le serveur, mettre à jour la valeur courante de la variable V en utilisant ladite quantité de la ressource informatique libérée ; et

— un module de transmission, configuré pour transmettre au dispositif de gestion ladite valeur courante de la variable V mise à jour.

Plus précisément, dans le second mode de réalisation, sur chaque détection d'un événement EV (EV=UPD-U, RESA, FREE ou UPD-D comme dans le premier mode de réalisation) chaque serveur Sk estime via son module de mise à jour la quantité courante EU_R(n,Sk) déjà utilisée de sa ressource informatique R. Il peut procéder à cet effet par exemple de façon similaire ou identique à ce qui a été décrit précédemment dans le premier mode de réalisation et mis en œuvre par le dispositif 3 de gestion en référence aux figures 3B et 3C.

Puis, à partir de la quantité EU_R(n,Sk) ainsi estimée par le serveur Sk, le module de mise à jour du serveur Sk met à jour la valeur de sa capacité maximale CL_R(Sk) pour la ressource R et pour l'intervalle de temps t(n) selon l'équation (eq7) suivante : CL_R (n, Sk) = CL_R (Sk) + Q_R (n, Sk) - EU(n, Sk) (eq7) où Q_R(n,Sk) désigne la quantité de ressource R réservée initialement par le dispositif 3 de gestion sur le serveur Sk pour l'exécution des tâches positionnées sur le serveur Sk à l'instant courant de mise à jour. Cette quantité Q_R(n,Sk) est donnée par, compte-tenu des besoins R_R_Tj, en ressource R déclarés par les utilisateurs à l'origine de ces tâches :

Q_R(n. Sk) = R_R_Tj .

où J2(n) désigne le nombre de tâches Tl,...,TJ2(n) positionnées sur le serveur Sk à l'instant courant de mise à jour.

La valeur courante de la capacité maximale CL_R(n,Sk) du serveur Sk pour la ressource R est alors remontée (périodiquement par exemple ici) par le serveur Sk au dispositif 3 de gestion du cluster 2, par exemple en utilisant le protocole de communication déjà utilisé dans les systèmes informatiques s'appuyant sur un système de gestion Hadoop Yarn.

Le dispositif 3 de gestion du cluster 2 utilise alors la valeur mise à jour CL_R(n,Sk) de la capacité maximale CL_R(Sk) du serveur Sk dans l'équation (eql') mentionnée précédemment pour déterminer, pour une tâche entrante T qui lui est soumise les serveurs Sk, k=l,...,K du cluster 2 aptes à exécuter cette tâche.

Il convient de noter que ce second mode de réalisation ne requiert aucune modification du traitement réalisé aujourd'hui par les systèmes de gestion de l'état de la technique (i.e. ils utilisent l'équation (eql ). Ainsi, dans ce second mode de réalisation, le dispositif 3 de gestion du cluster 2 peut être un système de gestion Hadoop Yarn ou un système de gestion Borg déjà connus. Seuls les serveurs Sk du cluster 2 doivent être modifiés pour implémenter l'invention. Ces modifications peuvent toucher tout ou partie des serveurs du cluster 2.

Dans les deux modes de réalisation décrits ici, ainsi que dans leurs variantes, on a considéré pour mettre à jour la quantité EU_R(n,Sk) une moyenne mobile exponentielle. Toutefois cette hypothèse n'est pas limitative en soi, et d'autres types de lissage ou de moyennes glissantes peuvent être envisagés pour calculer la quantité EU_R(n,Sk). Ainsi par exemple, dans une variante de réalisation, on peut considérer une moyenne arithmétique des mesures d'utilisation réelle remontées sur une fenêtre glissante comprenant N intervalles de temps précédents l'intervalle de temps t(n).

Dans une autre variante encore, on peut considérer une moyenne MMP(n, Sk) mobile pondérée des mesures d'utilisation réelle remontées sur une fenêtre glissante comprenant N intervalles de temps précédant l'instant courant de mise à jour, telle que par exemple :

N'u R(n,Sk)+(N'-l)u R(n-l,Sk)+---+U R(n-N'+l,Sk)

MMP(n, Sk) =— ^J —^- ,— — —

J N'+QV'-1)+---+1

où N' est le maximum du nombre de mesures U_R(n,Sk) disponibles précédant la mesure U_R(n,Sk) et de N. Cette moyenne MMP(n, Sk) s'écrit de façon équivalente, après avoir obtenu N mesures U_R(m,Sk), sous la forme : MMP(n, Sk) = MMP (n - 1, 57c) + ;— —

J ^J QV+l)/2

On note que dans cette moyenne pondérée, les mesures U_R(n,Sk) ont d'autant plus de poids qu'elles sont récentes.

La valeur EU_R(n, Sk) peut alors être calculée selon l'équation suivante, à la réception d'une nouvelle mesure U_R(n,Sk) (détection d'un événement EV=UPD-U) :

„ (k + N - n) * R_R_Tj

EU_R(n, Sk) = MMP(n,Sk) + > > - ' _T

^—' , N

k=n-N +1 ^a l- ^k

dj>n

où aj indexe le début de la tâche Tj et dj la fin de la tâche Tj sur le serveur Sk.

La valeur EU_R(n,Sk) peut en outre être mise à jour de la façon suivante lors de la détection d'un événement EV=RESA :

EU_R(n, Sk) = EU_R(n, Sk) + R_R_Tnew

Ces exemples ne sont donnés qu'à titre illustratif et d'autres exemples encore peuvent être envisagés pour mettre à jour la valeur EU_R(n,Sk).