Brevet FR2691557A1 — publié le 19931126

La présente invention concerne le domaine des systèmes d'exploitation pour ordinateurs numériques, plus particulièrement pour ordinateurs numériques dans lesquels de multiples tâches sont programmées en vue d'une exécution par un ou plusieurs processeurs. Il est classique dans les ordinateurs numériques de disposer de plus d'une tâche dans un état prêt à exécution en même temps Dans les ordinateurs d'unité centrale ainsi que dans les mini-ordinateurs, ces tâches peuvent être constituées par des tâches de traitement par lot, par des utilisateurs agissant sur un système en temps partagé et par des tâches systèmes utilisées pour produire des sorties pour des imprimantes Le traitement multitâche se rencontre présentement dans les micro- ordinateurs et même dans des systèmes basés sur des ordinateurs portables en réseau Bien que l'utilisateur d'un micro-ordinateur ou d'un système d'ordinateur portable puisse avoir seulement besoin de la tâche primaire qui est dirigée par ses actions, d'autres tâches peuvent être des fonctions de traitement telles qu'un courrier électronique, un calendrier, une reconnaissance d'écriture manuscrite et autre. Dans des environnements multitâches, lorsqu'il y a plus d'une tâche qui est prête pour l'exécution, le système d'exploitation doit programmer l'ordre selon lequel les tâches seront exécutées par un ou plusieurs processeurs. Un procédé de programmation connu associe des priorités à chaque tâche; à chaque intervalle de programmation, la tâche présentant la priorité la plus élevée est sélectionnée en vue de son exécution Un problème rencontré avec la programmation basée sur une règle de priorité est que des tâches à priorité inférieure ne sont pas exécutées tant qu'une tâche à priorité plus élevée est disponible pour être exécutée; ce problème est connu en tant que "problème d'exclusion" Bien qu'il existe des modifications apportées à la programmation par priorité (telle qu'une programmation préemptive et que l'on puisse appliquer des petits incréments de priorités pendant une période temporelle courte sur la base de certains évènements, ces deux modifications étant expliquées ci-après), ces procédés ne résolvent pas le problème d'exclusion et ajoutent de la complexité au processus de programmation. Un mode de réalisation préféré de la présente invention propose un nouveau processus de programmation basé sur une priorité qui ne permet pas la survenue d'une exclusion Les tâches sont sélectionnées pour une exécution de façon stochastique sur la base d'un nombre aléatoire pondéré par une priorité de tâche Du fait que chaque tâche a une probabilité finie non nulle d'être sélectionnée, la probabilité étant proportionnelle à la priorité de la tâche, la présente invention a pour avantage que toutes les tâches, même celles à priorité faible, ont une chance d'être sélectionnées, ce qui élimine le problème d'exclusion. D'autres objets, caractéristiques et avantages de la présente invention apparaîtront à l'évidence à la lumière de la description détaillée d'un mode de réalisation particulier qui va suivre, que l'on lira en relation avec les dessins annexés parmi lesquels: la figure 1 est un schéma fonctionnel d'un système d'ordinateur typique; la figure 2 représente les structures de données pour un système de programmation basé sur la priorité (art antérieur); la figure 3 représente les structures de données pour un système de programmation basé sur la priorité modifiée (art antérieur); la figure 4 représente la structure de données selon la présente invention; la figure 5 est une représentation différente de la présente invention; la figure 6 est un mode de réalisation de la présente invention; la figure 7 représente les performances du mode de réalisation de la figure 6; et la figure 8 représente un second mode de réalisation de la présente invention. La figure 1 est un schéma fonctionnel d'un dispositif ou système à base d'ordinateur typique Le système comprend une unité centrale de traitement (CPU) 10 interconnectée à des dispositifs d'entrée 12, une hiérarchie de mémoire 14, des dispositifs de sortie 16 et une horloge- minuterie 18 La CPU 10 est responsable de l'exécution d'instructions recherchées dans la mémoire 14 Un système peut comporter une ou plusieurs CPU Lors d'une utilisation typique, la mémoire 14 est agencée de façon hiérarchique Des systèmes plus grands comportent typiquement une mémoire morte (ROM), une mémoire vive (RAM) et une mémoire de stockage de sauvegarde qui se présente habituellement sous la forme d'un dispositif de commande de disque. Les ordinateurs plus petits peuvent comporter seulement une ROM et une RAM et peuvent utiliser des cartes enfichables contenant une ROM ou une RAM supplémentaire en vue d'une expansion L'horloge-minuterie 18 constitue une source d'interruption de la CPU. En fonctionnement, la CPU 10 recherche des instructions dans la mémoire 14 Au moyen des instructions recherchées dans la mémoire, la CPU 14 commande les dispositifs d'entrée 12, les dispositifs de sortie 16 et manipule les données contenues dans la mémoire 14 Le système d'exploitation est un ensemble d'instructions et de structures de données qui commande le fonctionnement du système d'ordinateur L'objet du système d'exploitation consiste à exécuter des tâches utilisateurs sélectionnées La partie du système d'exploitation qui sélectionne la tâche qui doit être exécutée est connue en tant que programmateur. Dans un système d'exploitation multitâches, une tâche est une collection d'instructions et de données. Le processus de programmation traite la manipulation et la sélection des tâches Dans un mode de réalisation simplifié, une tâche peut être dans l'un de deux états c'est-à-dire soit active soit bloquée La transition d'une tâche d'un état à l'autre est commandée par des événements Une tâche active est prête à être exécutée par la CPU Une tâche bloquée n'est pas prête à être exécutée et elle est en attente de la survenue d'un quelconque événement pour retourner à l'état actif En tant qu'exemple, supposons qu'une première tâche est en train de s'exécuter et qu'elle traite des données La tâche réalise une requête d'entrée par rapport au système d'exploitation pour rechercher une information nécessaire pour continuer son traitement Le système d'exploitation initialise l'opération d'entrée et appelle le programmateur pour changer l'état de la tâche afin de le faire passe de l'état actif à l'état bloqué Le programmateur sélectionne une seconde tâche à dérouler Lorsque l'opération d'entrée de la première tâche est terminée, le programmateur ramène l'état de la première tâche de l'état bloqué à l'état actif à nouveau. Un programmateur simple connu est le programmateur cyclique Ce type de programmateur sélectionne simplement chaque tâche active tour à tour en conférant à chaque tâche un poids égal L'exclusion ne se produit pas avec le programmateur cyclique La programmation peut être initialisée soit en tant que résultat de la tâche qui s'exécute et qui effectue des requêtes au système d'exploitation ou peut être initialisée sur la base d'interruption de minuterie selon une fréquence régulière. La programmation basée sur la priorité est un procédé connu qui reconnaît que certaines tâches sont plus importantes que d'autres Par exemple, dans un système de guichet automatique, une tâche manipulant une ligne de communication de données jusqu'à un terminal de guichet automatique est plus importante et d'une priorité plus élevée qu'une tâche par lot traitant des vérifications; le client situé au niveau du terminal de guichet automatique souhaite une réponse rapide tandis que le traitement de vérification d'arrière plan n'est pas soumis à une contrainte temporelle similaire Dans un système à temps partagé traditionnel comportant des tâches représentant de multiples utilisateurs en temps partagé, des tâches par lot d'arrière-plan et des transferts de données à des imprimantes, une priorité élevée est assignée aux utilisateurs en temps partagé dont chacun souhaite une réponse rapide aux requêtes entrées, une priorité inférieure étant assignée à la tâche d'imprimante qui prend peu de temps et une priorité inférieure étant assignée aux tâches par lot d'arrière-plan qui peuvent utiliser le temps CPU disponible restant dans un système d'ordinateur personnel comportant des tâches représentant une activité d'utilisateur principale telle qu'un traitement de mots et des tâches d'arrière- plan telles qu'une commande d'imprimante, qu'un transfert de données à distance et qu'un courrier électronique, la priorité la plus élevée est donnée à l'activité de traitement de mots et des priorités plus faibles sont données aux tâches d'arrière-plan Le programme du programmateur garde trace des tâches et sélectionne la tâche suivante en vue de son exécution. Typiquement, le programmateur maintient une file d'attente de tâches actives et une file d'attente de tâches bloquées la figure 2 est une représentation d'une file d'attente de tâches actives pour un programmateur basé sur la priorité Les structures de données représentées de manière schématique sont bien connues de l'art En fonction de l'architecture du processeur utilisé, ces structures de données peuvent être organisées en tant que blocs de commande (comme cela est représenté) ou peuvent être organisées en tant que tables La file d'attente des tâches actives de la figure 2 est représentée au moyen de l'utilisation de listes chaînées doubles Une en-tête de file d'attente active 20 contient une chaîne arrière 21 vis-à-vis du dernier élément de la file d'attente et une chaîne avant 22 vis-à-vis du premier bloc de file d'attente de tâches 24 Chaque bloc de file d'attente de tâches 24 contient également une chaîne arrière 21 vis-à-vis de l'élément précédent et une chaîne avant 22 vis-à-vis de l'élément suivant de la file d'attente Par souci de clarté, les chaînes avant 22 sont représentées et les chaînes arrière sont omises Chaque bloc de file d'attente de tâches 24 contient également un unique identifiant de tâches 25 utilisé pour identifier la tâche vis-à-vis du système d'exploitation Chaque bloc de file d'attente de tâches 24 contient également un ordre de priorité des tâches 26 Le bloc de file d'attente de tâches 24 contient également des données de contexte de tâches supplémentaires 27 nécessaires pour suspendre l'exécution de la tâche, pour effectuer une commutation sur une tâche différente et pour ultérieurement restaurer l'exécution de la tâche quand nécessaire au moyen du système d'exploitation et de la CPU Les listes chaînées doublement permettent l'utilisation de techniques bien connues pour une utilisation efficace lors d'une insertion, d'un enlèvement et d'un repositionnement des entrées dans la file d'attente. Moyennant la programmation basée sur la priorité et moyennant une file d'attente de tâches actives non tenues selon l'ordre des priorités, le programmateur sélectionne simplement la première tâche dans la file d'attente de tâches actives lors de son exécution En fonctionnement, un programmateur basé sur la priorité qui utilise l'information présentée sur la figure 2 placerait une tâche 24 a présentant un indentifiant égal à 1 et une priorité égale à 14 en exécution Cette tâche poursuivrait son exécution jusqu'à ce qu'un quelconque évènement se produise qui, soit augmente la priorité d'une autre tâche au-dessus de son niveau, soit abaisse sa priorité au-dessous de la priorité d'une autre tâche, soit laisse passer la tâche de l'état actif à l'état bloqué Des tâches 24 b, 24 c et 24 d sont exclues et elles ne sont pas exécutées tant qu'un quelconque évènement de ce type ne se produit pas. Il y a deux phases dans le processus de programmation Une phase met en jeu le report d'évènements et l'autre met en jeu une sélection d'une tâche en vue de son exécution Le report des évènements conduit à changer les priorités les états des tâches. Puisque ces évènements peuvent résulter d'une modification des priorités d'une tâche, la sélection de la tâche en vue de son exécution suit habituellement un report d'évènements Le processus de programmation peut donc être considéré comme étant initialisé par des évènements Une classe d'évènements invoquant le processus de programmation est constituée par des appels effectués au système d'exploitation. Par exemple, lorsqu'une tâche effectue une requête d'entrée spécifiant qu'une exécution de tâche est suspendue jusqu'à ce que la requête d'entrée soit terminée, la programmation est invoquée pour modifier l'état de la tâche et le faire passer de l'état actif à l'état bloqué puis pour sélectionner une tâche active en vue de son exécution. Une autre classe d'évènements qui met en jeu le processus de programmation est constituée par des évènements d'entrée/sortie tels que la fin d'opérations d'entrée/sortie et que l'arrivée à l'état vide ou plein de tampons Par exemple, si une tâche est en train de générer des données très rapidement et qu'elle émet ses données au travers d'un tampon de sortie à un dispositif de sortie relativement lent, une fois que le tampon de sortie est devenu plein, la tâche est bloquée jusqu'à ce que la place soit disponible dans le tampon de sortie, instant auquel la tâche peut être rendue active à nouveau. Un autre évènement utilisé pour invoquer la programmation est une interruption de minuterie Le système d'exploitation permet à une minuterie connectée à la CPU de générer une interruption dans une certaine période temporelle (par exemple 1/60 ième de secondes) connue en tant que tranche temporelle Lorsque l'interruption se produit, la CPU arrête l'exécution de sa tâche courante et dessert l'interruption en tant que partie de cette desserte d'interruption, le système d'exploitation invoque le processus de programmation, ce qui peut aboutir à la sélection d'une tâche différente en vue de son exécution Ce type de programmation est appelé programmation préemptive à tranche temporelle du fait que l'exécution de la tâche courante est préemptée et que le temps CPU est alloué en tranches A l'opposé, un programmateur qui permet la poursuite de l'exécution de la tâche en cours d'exécution jusqu'à ce que cette tâche déclenche un quelconque évènement aboutissant à la programmation d'une autre tâche est connu en tant que programmateur non préemptif. Plusieurs modifications ont été apportées au procédé de programmation de base par priorité afin de traiter le problème d'exclusion La programmation préemptive à tranche temporelle constitue l'une de ces modifications. Afin d'empêcher une exclusion dans un groupe de tâches présentant la même priorité, une programmation cyclique est également utilisée Les règles de ce procédé sont très simples: 1) lorsqu'une tâche est ajoutée, elle est ajoutée à la tête son groupe de priorités et 2) lorsqu'une tâche termine une tranche temporelle, elle est déplacée jusqu'à la fin de son groupe de priorités Par exemple, dans le cas représenté sur la figure 2, la tâche 24 a munie de l'identifiant à 1 serait la première tâche à être exécutée A la fin d'une tranche temporelle donnée, le procédé cyclique déplace la tâche 24 a à la fin du groupe de priorités 14 dans la file d'attente Sur la figure 2, la tâche 24 a serait replacée dans la liste après la tâche 24 b, en laissant la tâche 24 b à l'avant de la file d'attente en vue de son exécution A la fin de la tranche temporelle suivante, ces positions seraient commutées et l'exécution de la tâche 24 a reprendrait Sur des tranches temporelles successives, les tâches 24 a et 24 b sont exécutées tour à tour Cette approche ne résout pas le problème d'exclusion; les tâches 24 c et 24 d sont toujours exclues de fait de leurs priorités plus faibles et ne sont pas exécutées. Une autre approche au problème d'exclusion consiste à appliquer des petits incréments aux priorités des tâches pendant de courts intervalles, sur la base de certains évènements Ceci est représenté sur la figure 3 Dans un tel système, chaque bloc de tâches 24 contient une priorité courante 32 et une priorité de base 34 Comme représenté sur la figure 3, un programmateur préemptif cyclique tel que précédemment décrit programme en alternance l'exécution des tâches 24 a et 24 b L'approche par incrément ajoute les règles suivantes au processus de programmation: 1) à la fin d'une tranche temporelle, la priorité 32 de la tâche courante est décrémentée mais elle n'est pas autorisée à tomber au-dessous de la priorité de base des tâches courantes 34 Après décrémentation de la priorité courante, la tâche est alors à la queue du groupe de priorités approprié et 2) chaque évènement rapporté au programmateur a une incrément de priorité qui lui est associé, lequel peut être égal à zéro Lorsqu'un évènement est rapporté, cet incrément est additionné à la priorité courante de la tâche et cette tâche est repositionnée dans la file d'attente à la tête du groupe de priorités appropriées. Supposons qu'un évènement est rapporté pour la tâche 24 c moyennant un identifiant égal à 3 et que cet évènement est porteur d'un incrément de priorité de 3. Ceci augmenterait la priorité courante 32 de la tâche 24 c de 12 à 15, ce qui ferait que la tâche 24 c présenterait la priorité la plus élevée La file d'attente de tâches actives 20 se verrait positionner la tâche 24 c à l'avant, laquelle serait suivie par l'étage 24 a et 24 b de telle sorte que la tâche 24 c serait programmée en vue de son exécution La fin d'une tâche temporelle, la priorité courante 32 de la tâche 24 c serait décrémentée de 15 à 14 et cette tâche serait replacée dans la file d'attente après les tâches 24 a et 24 b qui présentent également une priorité courante de 14 La tâche 24 a serait alors exécutée pendant une tranche temporelle A la fin de cette tranche temporelle, la priorité de la tâche 24 a ne pourrait pas être décrémentée du fait que cette priorité tomberait alors au-dessous de sa priorité de base 34; la tâche 24 a est replacée derrière les tâches 24 b et 24 c et la tâche 24 b est déroulée A la fin de la tranche temporelle suivante, la tâche 24 b est repositionnée derrière les tâches 24 c et 24 a et la tâche 24 c est maintenant déroulée A la fin de la tranche temporelle suivante, la priorité courante 32 de la tâche 24 c est décrémentée de 14 à 13 et cette tâche est repositionnée ll après les tâches 24 a et 24 b Si l'on suppose qu'aucun autre évènement (autre que les évènements de minuterie préemptifs) n'est rapporté, alors les tâches 24 a et 24 b poursuivent leurs exécutions, les tâches 24 c et 24 d étant une fois de plus exclues du fait de leurs priorités courantes plus faibles. Le processus d'incrémentation de priorité ajoute de la complexité au processus de programmation Les incréments de priorités doivent être assignés à chaque évènement et de faibles variations de ces incréments peuvent affecter de façon dramatique le comportement du système ainsi que sa performance En outre, le programme d'exclusion n'est pas résolu au moyen du processus d'incrémentation de priorités. La figure 4 représente de manière schématique les structures de données utilisées par le premier mode de réalisation de la présente invention La présente invention résout le problème d'exclusion tout en préservant un schéma basé sur la priorité en sélectionnant des tâches d'une façon stochastique sur la base des priorités des tâches Une en- tête de file d'attente active 20 est l'en-tête d'une liste chaînée doublement de blocs de file d'attente de tâche 24. Chaque bloc de file d'attente de tâche 24 contient un identifiant de tâche 25, une priorité de tâches 26 et des données de tâches 27 Une variable Eprio 40 contient la somme des priorités de tâches 25 de toutes les tâches contenues dans la file d'attente de tâches actives Lorsque la file d'attente de tâches actives est modifiée au moyen de l'insertion ou l'enlèvement de tâches, la variable Eprio 40 est mise à jour afin de refléter la somme des priorités de tâches 25 de toutes les tâches présentes dans la file d'attente de tâches actives Pour les structures représentées sur la figure 4, cette valeur vaut 43 Le processus de programmation de l'invention présente généré un entier aléatoire dans la plage définie par 1 à Eprio, y compris ces deux valeurs, soit ici la plage qui va de 1 à 43, et utilise cet entier pour sélectionner la tâche suivante en vue de son exécution. Un entier aléatoire peut être généré de façon commode et déficiente en utilisant des procédés et des appareils bien connus tels qu'un générateur de séquence pseudo aléatoire à congruence linéaire Soit rn la valeur entière courante de la séquence, la valeur entière suivante de la séquence soit rn+l est calculée comme étant rn+l = (a*rn) modulo k La constante a et la valeur origine initiale pour la séquence doivent être sélectionnées avec soin comme il est connu de l'art La multiplication est effectuée d'une façon modulaire par rapport à la base k, en étant habituellement rapportée à une puissance de 2 afin de faciliter le calcul Par exemple, rn+l = ( 16807 * rn) modulo 231 _l produit une séquence uniforme. Etant donné un entier aléatoire situé dans la plage appropriée, la file d'attente de tâches actives est traversée en sommant des priorités des tâches jusqu'à ce que la priorité sommée soit supérieure ou égale à la valeur générée La tâche qui satisfait cette condition pendant le processus de traversée est celle qui doit être exécutée La valeur Eprio peut être maintenue lorsque des tâches sont ajoutées et ôtées de la file d'attente de tâches ou elle peut être régénérée pendant le processus de programmation en effectuant un passage supplémentaire au travers d'attente et en sommant les priorités des tâches. Dans l'exemple représenté sur la figure 4, on suppose que l'entier aléatoire généré pour la sélection de tâches est 33 La traversée de la file d'attente de tâches commence avec sa tâche 24 a La somme des priorités des tâches à ce point est de 14 et puisque 14 est inférieur à 33, la tâche 24 a n'est pas sélectionnée Si l'on se déplace à la tâche suivante soit la tâche 24 b, la somme des priorités est 28 ( 14 + 14), ce qui est inférieur à 33 de telle sorte que la tâche 24 b n'est pas sélectionnée Si l'on se déplace à la tâche suivante soit la tâche 24 c, la somme des priorités vaut 40 ( 14 + 14 + 12), ce qui est supérieur à 33 et ainsi, la tâche 24 c est sélectionnée en vue de son exécution. Selon une variante, plutôt que de traverser la file d'attente de tâche et d'ajouter les priorités des tâches, la file d'attente de tâches peut être traversée en décrémentant l'entier aléatoire de la priorité de la tâche courante et en effectuant un test par rapport à zéro Sur bon nombre d'ordinateurs, il est plus efficace de tester une valeur pour voir si elle est inférieure ou égale à zéro Selon ce procédé de traversée, tel que représenté sur la figure 4, on suppose que l'entier aléatoire généré pour la sélection de tâches est 33 La traversée de la file d'attente de tâches commence par la tâche 24 a La priorité de la tâche, soit 14, est soustraite de la valeur de sélection de tâches soit 33 Le reste est 19, lequel reste est stocké en tant que valeur de sélection de tâches Puisque cette valeur est supérieure à zéro, la traversée se poursuit avec la tâche 24 b la priorité de la tâche 24 b vaut 14, laquelle valeur est soustraite de 19, ce qui donne un reste de 5 Puisque 5 est supérieur à zéro, la traversée se poursuit avec la tâche 24 c La priorité de la tâche 24 c vaut 12, laquelle valeur est soustraite de 5, ce qui donne un reste de 7 Puisque -7 est inférieur à zéro, la tâche 24 c est sélectionnée en vue de son exécution. La figure 5 représente le comportement de la présente invention selon une forme graphique Du fait que la sortie d'un générateur de séquence pseudo aléatoire conçu en puits est statistiquement uniforme, au fil du temps, toutes les valeurs entières de 1 à 43 apparaissent avec une fréquence similaire et toutes les tâches données sont par conséquent choisies en vue d'être exécutées La probabilité qu'une quelconque tâche donnée soit choisie est proportionnelle à la priorité des tâches Sur la figure 5, une ligne de nombres 50 représente les entiers de zéro à Eprio (la somme des priorités des tâches actives) soit ici la plage zéro à 43 Sont également représentés les empattements de chaque tâche, chaque empattement étant égal à la priorité des tâches La tâche 24 a qui présente la priorité 14 se voit associer à un empattement 52 a qui va de 1 à 14 La tâche 24 b présentant la priorité 14 se voit associer l'empattement 52 b qui va de 15 à 28 La tâche 24 c qui présente la priorité 12 se voit associer à un empattement 52 c qui va de 29 à 40 La tâche 24 d présentant une priorité de 3 se voit associer à un empattement 52 d qui va de 41 à 43 Un entier aléatoire généré dans la plage 1 à 14 sélectionne la tâche 24 a, dans la plage 25 à 28 la tâche 24 b, dans la plage 29 à la tâche 24 c et dans la plage 41 à 43 la tâche 24 d. Au fil du temps, la quantité de temps CPU d'exécution d'une tâche est proportionnelle à sa priorité, aucune tâche n'étant exclue Dans la limite du temps qui croît, la valeur du temps CPU pendant laquelle une tâche s'exécute s'approche de la priorité de tâches divisée par Sprio Sur la figure 5, Eprio a pour valeur 43 La valeur de temps CPU pendant laquelle la tâche 24 a munie de la priorité 14 s'exécute s'approche de 14/43, soit approximativement 32,6 % La valeur de temps CPU pendant lequel la tâche 24 b présentant la priorité 14 s'exécute se rapproche de 14/43 soit approximativement 32,6 % La valeur de temps CPU pendant lequel la tâche 24 c munie de la priorité 12 s'exécute s'approche de 12/43, soit approximativement 27,9 % La valeur de temps CPU pendant lequel la tâche 24 d munie de la priorité 3 s'exécute s'approche de 3/43 soit approximativement 7 %. La figure 6 est un modèle de la présente invention qui utilise les paramètres de la figure 5 Le modèle est écrit dans le langage Mathematica publié par Wolfram Research, Inc, lequel langage est disponible sur bon nombre de systèmes d'ordinateurs y compris le Macintosh, et Apple La figure 7 représente la sortie de ce modèle obtenu sur un Macintosh de Apple II et cette figure démontre sa performance. Si l'on se reporte tout d'abord à la figure 6, les numéros de lignes situés à la gauche de la barre verticale sont présentés à titre de références seulement et ne font pas partie du modèle Les lignes 1 à 5 définissent une fonction graphique lplot Cette fonction prend en tant qu'arguments une liste des points à tracer, le titre du graphique et la valeur de la ligne asymptote au tracé La ligne 6 définit une variable N comme étant le nombre de points d'échantillonnages à accumuler soit ici 1000 Une ligne 7 définit des variables tl, t 2, t 3 et t 4 et les initialise à zéro La variable tl contient le nombre de fois o la tâche 1 est sélectionnée La variable t 2 contient le nombre de fois o la tâche 2 est sélectionnée La variable t 3 contient le nombre de fois o la tâche 3est sélectionnée La variable t 4 contient le nombre de fois o la tâche 4 est sélectionnée Une ligne 8 initialise 4 lignes pl, p 2, p 3 et p 4 utilisées pour maintenir les données du tracé Une ligne 9 commence une boucle qui est répétée pour chaque point d'échantillonnage Une ligne 10 assigne à une variable j un entier aléatoire compris dans la plage 1 à 43, bornes comprises Les lignes Il à 14 comptent le nombre de fois que chaque tâche est sélectionné sur la base de l'entier aléatoire contenu dans la variable j. Reportons-nous également à la figure 5 sur laquelle35 l'entier aléatoire j s'inscrit dans la plage qui va de 1 à 14 et la tâche 1 repérée 24 a sur la figure 5 est sélectionnée, la variable tl est incrémentée pour refléter cette sélection Les lignes 15 et 16 calculent le pourcentage de temps pendant lequel chaque tâche a été exécutée en vue d'une utilisation pour les graphiques de la figure 7 Le pourcentage de temps pour chaque point de données est égal au nombre de fois o la tâche a été sélectionnée, maintenue dans les variables tl, t 2, t 3 et t 4, divisée par le nombre d'échantillons, soit i Des lignes 18 à 21 produisent les graphiques représentés sur la figure 7. Les graphiques de la figure 7 représentent la performance de la présente invention telle que modélisée au moyen de la figure 6, le pourcentage de temps CPU utilisé par chaque tâche au fil du temps. Comme représenté sur les graphiques, pour la tâche 1 présentant une priorité de 14, le temps CPU s'approche rapidement de la valeur calculée de 32,7 %, laquelle valeur est représentée en tant que ligne horizontale en traits pleins sur le graphique De façon similaire, la tâche 2 présentant également une priorité de 14 s'approche rapidement de 32,7 %, la tâche 3 munie d'une priorité de 12 s'approche rapidement de 27,9 % et la tâche 4 munie d'une priorité de 3 s'approche rapidement de 7 % quant au temps CPU Ces graphiques montrent que la présente invention programme des tâches sur une base de priorités et n'exclut pas des tâches à priorités faibles. Le mode de réalisation de la figure 5 nécessite une recherche linéaire de la file d'attente de tâches actives afin d'effectuer une sélection Cette rechercher linéaire peut devenir consommatrice de temps si un nombre important de tâches sont présentes dans la file d'attente La figure 8 représente un second mode de réalisation de la présente invention qui réduit le temps requis pour une traversée de file d'attente lorsqu'il y a beaucoup de tâches dans la file d'attente Plutôt que de disposer de toutes les tâches actives positionnées ensemble afin d'activer l'en-tête de file d'attente dans une liste linéaire, les tâches sont groupées en sous-file d'attente dont chacune comporte une en-tête sous-file d'attente 62 Chaque en- tête de sous-file 62 contient une cellule Elist 64 qui est la somme des priorités pour toutes les tâches contenues dans cette sous-file d'attente L'en-tête de sous-file d'attente 64 contient également une en- tête de file d'attente de tâches 65 contenant des chaînes avant et arrière vis-à-vis de chacun des blocs de file d'attente de tâches 66 Par souci de clarté du schéma, seulement les chaînes avant sont représentées La somme de l'ensemble des cellules Elist 64 est maintenue en tant que Zprio 60 soit la somme de toutes les priorités des tâches Les tâches ne doivent pas nécessairement se trouver selon un quelconque ordre particulier dans les files d'attente. Dans le mode de réalisation de la figure 8, le processus de traversée est plus rapide que dans le mode de réalisation de la figure 5 du fait que sur la figure 8, les en-têtes de files d'attente 62 sont traversées pour tout d'abord sélectionner une sous-file d'attente répondant aux critères de programmation puis cette sous-file d'attente est traversée pour sélectionner le bloc de files d'attentes de tâches particulier 66 plutôt que de traverser tous les blocs de files d'attente de tâches 24 de la figure 5 afin d'atteindre la tâche sélectionnée. Supposons par exemple que sur la figure 8 l'anti aléatoire généré pour la sélection de tâches est 81 La traversée commence par l'en-tête de sous-file d'attente 62 a la somme des priorités à ce point vaut 40 et du fait que 40 est inférieur à 81, la tâche qui doit être sélectionnée ne se trouve pas dans la sous-file d'attente 62 a On se déplace à l'en- tête de sous-file d'attente suivante 62 b et la somme des priorités vaut 54 ( 40 + 14) ce qui est inférieur à 81 de telle sorte que la tâche qui doit être sélectionnée ne se trouve pas dans la sous-file d'attente 62 b On se déplace jusqu'à l'en-tête de sous-file d'attente suivante 62 c et la somme des priorités vaut 66 ( 40 + 14 + 12), ce qui est inférieur à 81 de telle sorte que la tâche qui doit être sélectionnée n'est pas dans la sous-file d'attente 62 c On se déplace jusqu'à l'en- tête de sous-file d'attente suivante 62 d et la somme des priorités vaut 92 ( 40 + 14 + 12 + 26), ce qui est supérieur à 81 et ainsi la tâche qui doit être sélectionnée ne se trouve pas dans la sous-file d'attente 62 d La traversée de l'en-tête de file d'attente de tâches 65 contenue dans le bloc d'en-tête de sous-file d'attente 62 d conduit au bloc de file d'attente de tâches 66 d La somme des priorités à ce point vaut 75 ( 40 + 14 + 12 + 9), ce qui est inférieur à 81 et ainsi, la tâche 66 d n'est pas sélectionnée en vue de son exécution On se déplace jusqu'au bloc de file d'attente de temps 66 e o la somme des priorités vaut 82 ( 40 + 14 + 12 + 9 + 8), ce qui est supérieur à 81 et ainsi, la tâche 66 e est sélectionnée en vue de son exécution. Une variante de la figure 8 consisterait à maintenir une valeur de comptage dans une en-tête de sous file d'attente 62 du nombre de tâches chaînées à cette en-tête de sous-file d'attente Ceci permet un codage spécifique afin de traiter le cas o il y a seulement un bloc de file d'attente de tâches 66 chaînées à l'en-tête de sous-file d'attente 62, comme représenté au moyen du bloc de file d'attente de tâches 66 c et du bloc d'en-tête de sous-file d'attente 62 c. Ceci simplifierait également le processus d'ajout de nouvelles tâches à la sous-file d'attente plus courte. L'invention telle que décrite propose un programmateur basé sur la priorité qui élimine le problème d'exclusion Les avantages supplémentaires de l'invention incluent la gestion de files d'attente simplifiées Les tâches n'ont pas à être ajoutées selon un ordre de priorité ou n'ont pas à être maintenues selon un ordre de priorité Du fait que les priorités des tâches ne changent pas, les tâches n'ont pas à être positionnées selon de nouvelles positions de priorités dans la file d'attente. Bien que l'invention ait été décrite par report à des systèmes d'ordinateurs, l'invention peut être appliquée à n'importe quel dispositif actionné par ordinateur dans lequel de multiples tâches doivent être programmées en vue de leur exécution Bien que l'invention ait été décrite par report à des modes de réalisation spécifiques, il est bien entendu par l'homme de l'art que diverses modifications peuvent être apportées et que des équivalents peuvent être substitués à des éléments de ces modes de réalisation sans que l'on s'écarte ni du cadre ni de l'esprit de l'invention En outre, bon nombre de modifications peuvent être effectuées sans que l'on s'écarte des techniques essentielles de la présente invention. REVENDICATIONS 1 Procédé de sélection de tâche dans un système d'ordinateur dans lequel une pluralité de tâches ( 24 a à 24 d) exécutables sont disponibles pour l'exécution, le procédé étant caractérisé en ce qu'il comprend les étapes de: le maintien d'une structure de données comprenant la pluralité de tâches exécutables; association d'une priorité à chacune des tâches exécutables; et sélection d'une tâche d'une façon aléatoire pondérée par une priorité de tâche en provenance de la structure de données de tâches exécutables. 2 Procédé de sélection de tâche selon la revendication 1, caractérisé en ce que l'étape de sélection d'une tâche de façon aléatoire pondérée par une priorité de tâche comprend en outre: le calcul de la somme des priorités pour toutes les tâches exécutables; la génération d'une valeur de sélection aléatoire entre 1 et la somme des priorités; l'initialisation d'une variable temporaire à zéro; la traversée de la structure de données de tâches exécutables en ajoutant la priorité de tâche à la variable temporaire, en comparant la variable temporaire à la valeur de sélection aléatoire et en se déplaçant jusqu'à la tâche suivante dans la structure de données si la variable temporaire est inférieure à la valeur de sélection; et la sélection de la tâche qui correspond au fait que la variable temporaire est égale ou supérieure à la valeur de sélection en tant que tâche exécutable. 3 Procédé de sélection de tâche selon la revendication 2, caractérisé en ce que la structure de données de tâches exécutables est maintenue dans une liste chaînée. 4 Procédé de sélection de tâche selon la revendication 2, caractérisé en ce que la structure de données de tâches exécutables est maintenue en tant que jeu de tables indexées. Procédé de sélection de tâche selon la revendication 1, caractérisé en ce que l'étape de sélection d'une tâche de façon aléatoire est pondérée par une priorité de tâche qui comprend en outre: le calcul de la somme des priorités pour toutes les tâches exécutables; la génération d'une valeur de sélection aléatoire entre 1 et la somme des priorités; le parcours de la structure de données de tâches exécutables en soustrayant la priorité de tâches de la valeur de sélection et en se déplaçant jusqu'à la tâche suivante dans la structure de données si la valeur de sélection est supérieure à zéro; et la sélection de la tâche qui correspond au fait que la valeur de sélection est inférieure ou égale à zéro. 6 Procédé de sélection de tâche selon la revendication 5, caractérisé en ce que la structure de données de tâches exécutables est maintenue en tant que liste chaînée. 7 Procédé de sélection de tâche selon la revendication 5, caractérisé en ce que la structure de données de tâches exécutables est maintenue en tant que jeu de tables indexées.