[go: up one dir, main page]

WO2012038000A1 - Procede de gestion de taches dans un microprocesseur ou un ensemble de microprocesseurs - Google Patents

Procede de gestion de taches dans un microprocesseur ou un ensemble de microprocesseurs Download PDF

Info

Publication number
WO2012038000A1
WO2012038000A1 PCT/EP2011/003973 EP2011003973W WO2012038000A1 WO 2012038000 A1 WO2012038000 A1 WO 2012038000A1 EP 2011003973 W EP2011003973 W EP 2011003973W WO 2012038000 A1 WO2012038000 A1 WO 2012038000A1
Authority
WO
WIPO (PCT)
Prior art keywords
list
variable
value
task
tasks
Prior art date
Application number
PCT/EP2011/003973
Other languages
English (en)
Inventor
Olivier Huyard
Original Assignee
Continental Automotive France
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Continental Automotive France filed Critical Continental Automotive France
Priority to US13/819,182 priority Critical patent/US9135058B2/en
Priority to CN201180045180.XA priority patent/CN103154894B/zh
Publication of WO2012038000A1 publication Critical patent/WO2012038000A1/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Definitions

  • the present invention relates to a method for managing tasks in a microprocessor or in a set of microprocessors, and more particularly a method managing the interruption of tasks in a microprocessor.
  • a microprocessor is an electronic device that can perform various tasks, each task being a sequence of several instructions. Means are associated with the microprocessor to form with it a microcontroller. These additional means allow the management of the tasks entrusted to the microprocessor.
  • a microprocessor usually only performs one task at a time. It is then necessary to manage the situations in which several tasks are to be executed simultaneously or even the case where one or more tasks are to be executed while a previous task is being executed.
  • microprocessors it is for example provided for some microprocessors to be able to interrupt a task in order to execute another one and to finish the interrupted task once the new task has been completed.
  • Such management is problematic especially when the execution of the tasks by the microprocessor uses access to a memory.
  • the realization of the new task may then disturb the stored values for the task being executed, which of course disturbs the task in progress and can lead to inconsistencies due to the unstable state of the intermediate data.
  • JobRow a software for storing pending tasks.
  • Such software then manages a list of tasks which will be called later "JobRow". With such software, the task being executed is momentarily stopped while the software is waiting for the list of tasks. Thus, during the execution of a task, the arriving tasks are stored via the software in the JobRow list and will be performed once the running task is completed.
  • This task interrupt management works but has the disadvantage of slowing the speed of execution of the tasks. Indeed, these stops and restarting of tasks consume time. In addition, allowing these shutdowns and restarting also increases the risk of making a human error when writing the software managing the "JobRow". Such an error can even lead to a system crash.
  • the object of the present invention is therefore to provide a process for managing tasks in a microprocessor, in particular for managing work interruptions, which allows the system to function properly with the fastest possible execution of the tasks. In particular, it is necessary to avoid wasting time due to stopping and restarting of a task execution.
  • one resource is common to several microprocessors.
  • several microprocessors are likely to access this resource, called shared resource, for the execution of the tasks entrusted to them.
  • This shared resource can however only be used by one microprocessor at a time. It is then known to use mutual exclusion algorithms (or “mutual exclusion”), also called “mutex”, to manage access to shared resources.
  • the present invention will also manage the successive access to a shared resource shared by several microprocessors.
  • the present invention proposes a process for managing the processing of tasks in a microprocessor, characterized in that it comprises steps for the parallel management of a first list and a second list,
  • the first list corresponds to a list of tasks to be performed
  • the second list corresponds to a list of variables reflecting the presence or absence of tasks to be performed
  • the task list is managed in a "FIFO", “First In, First Out” manner; or first inbound, first outgoing, that is, the first task entered in the list is the first task executed, and
  • the present invention also provides a detailed algorithm for implementing such a method. It also proposes a method for managing the processing of tasks in a microprocessor, characterized in that it comprises steps for managing a first list and a second list,
  • the first list is a list containing elements giving an indication of a task to be performed by the microprocessor
  • the second list is a list of variables representative of a state, each variable of the second list being associated with one and only one element of the first list and having a first value representative of a first state and a first second representative value of a second state,
  • a global variable is defined, this global variable being able to take as many distinct values as there are elements in the second list, said global variable making it possible to point to a variable in the first list as well as in the second list,
  • said global variable is a variable intended to be incremented so as to point in a given order the elements of the first list and the second list, the first list and the second list being considered circular lists, that is to say that in said given order, the first element of the list is considered as the next element of the last element of the list and vice versa, the last element of the list is considered as the preceding element of the first element of the list.
  • the first step of the method when a task, called the current task, is entrusted to the microprocessor, consists in performing a reading of the value of the second list pointed to by the global variable, in copying the value read in a first local variable and to write in the second list, instead of the value read, the representative value of the second state, this first step forming a single operation, called "Test And Set" and can not be interrupted, in that said method implements a first sub-method in the case where the first local variable has taken the value representative of the first state and a second sub-method in the case where the first local variable has taken the value representative of the second state,
  • the first sub process comprises the following steps:
  • variable of the second list preceding the variable corresponding to the global variable is set to the value representative of the first state
  • step 6a the first sub-method returns to step 4a) if the value of the second list corresponding to the global variable, incremented, is representative of the second state, and the process is terminated otherwise,
  • the second sub process comprises the following steps:
  • step 6b) testing the third local variable and executing a step 6b) of updating the first list so that the variable corresponding to the incremented global variable of the second local variable gives an indication corresponding to the current task then end of the task management process insofar as the result of the test on the third local variable indicates that it has a value representative of the first state, in a contrary case, an incrementation of the second local variable is performed followed by 'a return to step 4b) as long as the value of the second local variable is strictly less than a limit value corresponding to the number of elements of the second list decreased by 1, and end of the process with loss of the current task if this limit value is exceeded by the second local variable.
  • Such a process contains no part that is not interruptible. It can be interrupted at any moment of its execution and restart another execution.
  • the "Test And Set” function can not be interrupted.
  • the algorithm of the above method has two branches, one for the execution of the tasks, the other for storing the new tasks to be executed. It makes it possible to ensure the consistency of the values produced by the tasks being executed without blocking the execution of the other tasks that arrive, this process being able to be interrupted at any time.
  • the third local variable is advantageously confused with the first local variable. This avoids multiplying the number of variables to manage.
  • variables of the second list are preferably Boolean variables.
  • the present invention also relates to a method for managing the task processing at a set of at least two microprocessors.
  • each microprocessor uses a task management method as described above.
  • Such management at the level of a set of microprocessors allows consistent management of common resources (memory). Tasks can run one after another according to their order of arrival in the list. However, with this management, when a task must be executed, it is not possible to know in advance which microprocessor of the set of microprocessors using the shared resource this task will be executed.
  • the present invention also relates to a computer program stored on an information medium, said program comprising instructions for implementing a task management method as described above, when this program is loaded and executed by a computer system, such as a microprocessor.
  • the present invention also relates to a microprocessor, characterized in that it comprises instructions of a program for implementing a task management method as described above.
  • FIG. 1 is an algorithm illustrating a task management method according to the present invention
  • FIG. 2 schematically illustrates a memory shared by several microprocessors
  • FIG. 3 illustrates an algorithm for microprocessor task management and access to the shared memory diagrammatically shown in FIG. 2.
  • FIG. 1 represents an algorithm allowing the implementation of a preferred embodiment of a task management method according to the present invention. Different elements are used in this algorithm. Among these, we have in particular:
  • RowSize this is a variable that is an integer greater than two.
  • JobRow This is a list of items that are in RowSize. These elements can be directly tasks or a pointer indicating the location of a task, or any other element that allows to define tasks, including tasks to be performed.
  • TasRow This is a list of variables, preferably Boolean variables. There are as many variables in this list as in JobRow. This list is a reflection of JobRow and allows to know the positions of the tasks stored in JobRow.
  • rjndex is set to zero as are all the elements of the TasRow list.
  • Step 1 implements a function called thereafter "Test And Set". This is a function that can not be interrupted. It will be applied here to Boolean variables.
  • This function Test And Set performs a reading of the Boolean variable, stores the value of this variable in a buffer, a local memory, then gives the Boolean variable read a predetermined value, here the value 1.
  • the Test And Set function is applied to the item in the rjndex index's TasRow list. The value, 0 or 1, of this element of the list TasRow is then placed in the local memory Get then the element of rank rjndex in TasRow takes the value 1.
  • step 2 the value of Get is analyzed and depending on the response obtained, the program executes the left branch of the algorithm or the right branch of this algorithm.
  • the left branch of the algorithm allows tasks to be executed while the right branch is used to store the new tasks to be performed.
  • step 3a if the value of Get is therefore 0, the task "Job" is put in the JobRow list at rank rjndex. Then, in step 4a, the rank value preceding rank r_index is then set to 0 in the TasRow list.
  • step 5a Job, which corresponds to the item in the JobRow list at rank rjndex, is executed. Only when the task is fully executed is the rjndex variable incremented by one unit (step 6a).
  • step 7a we look in the list TasRow the rank element rjndex, this rank being the new rank incremented. If the value of this element is 1, it means that a task is to be executed. The algorithm then returns in this case to step 4a. On the other hand, if there is no more task to execute, the program is completed.
  • the bottom point of Figure 1 represents the output of the program corresponding to the algorithm.
  • step 3b the local variable N is initialized to the value 1.
  • step 4b a Test And Set function is performed on the item of the ranged TasRow list. rjndex + N, of course modulo RowSize.
  • a third local variable could be used here as a buffer. In fact, it is useless to use here a third variable, the local variable Get being available to stack the tasks entrusted to the microprocessor and can not be executed immediately. The result of the Test and Set function at step 4b is then recorded in the local variable Get.
  • step 5b the place of rank rjndex + N is then free in the JobRow list and the task Job, which is the current task that triggered the program, is then stored in JobRow at rank rjndex + N (modulo RowSize of course). The job is in the waiting list, so the program is finished.
  • step 5b if the value of Get is not 0, that is to say that it is 1, it is necessary to increment N by one unit to see if the next place in JobRow job list is free. We continue to look at all the places in the JobRow list until we find a free place (loop 4b, 5b, 6c, 7c, 4b). If the task list is completely filled (step 7c), the current job "Job" is lost. The program is then also finished.
  • the task management method just described here has the advantage that it contains no part that is not interruptive. However, it is recalled here that the Test And Set function can not be interrupted.
  • the method described above and illustrated in Figure 1 can be interrupted at any time of its execution to restart another run. In the case of the interruption of this process by itself, its execution is suspended until the next execution is finished.
  • the algorithm proposed here allows tasks to be saved in the task list as soon as a running job is completed. Tasks are stored and read by their order of arrival. So here we have a management "FIFO” (English First In First Out, or French first-in first-out).
  • This algorithm ensures consistency of the values produced by the running tasks without blocking the execution of other tasks that arrive, since the corresponding process is interruptible at any time. This consistency is achieved in particular because the algorithm used to execute and store tasks is based on a function, the function Test And Set which is not interruptive and can not be interrupted.
  • the present invention also provides for managing tasks of a set of microprocessors, this set having a shared memory to which each of the microprocessors in the set can access.
  • FIG. 2 represents four microprocessors, called CPU A, CPU B, CPU C and CPU D.
  • CPU A central processing unit
  • CPU B central processing unit
  • CPU C central processing unit
  • CPU D central processing unit
  • a memory in the center of Figure 2 contains data accessible and modifiable by the four microprocessors of all microprocessors.
  • each microprocessor has four levels (“Level") of interruption.
  • each of the microprocessors manages its tasks according to a method such as that described above with reference to FIG. 1.
  • the method of FIG. 3 concerns a task management at the assembly level. microprocessors, that is to say here microprocessors CPU A, CPU B, CPU V and CPU D.
  • the present invention proposes here to use a common list of tasks, here also called JobRow.
  • JobRow a common list of tasks
  • the elements relate to all the microprocessors and the shared memory.
  • JobRow already mentioned above. This is a list of tasks for all microprocessors
  • RowSize this is the number of items that can be in JobRow
  • r_index this is an integer variable that can take RowSize value. It will be assumed here that rjndex can take values from 0 to RowSize - 1. As will be seen later, the method provides for reading the tasks to execute them on one side and on the other hand to place tasks to be executed. in the task list. The rjndex index is used for reading (r of "read” in English or read in French),
  • mutex this variable indicates the status of the shared memory. It serves in particular to block access to this memory.
  • mutex a Boolean variable taking either the value 0 when the memory is accessible, or the value 1 to indicate that the memory is blocked,
  • RowSize is considered here to be at least 3.
  • the job list, JobRow is managed in a "FIFO" manner.
  • the JobRow list is, as already mentioned before, managed as a cyclic list. In this cyclic list, all the tasks to be performed are grouped together. There can be no "free place (s)" between two jobs in the JobRow list.
  • the method described below simply provides for the execution of the first task to be executed (followed by the index r_index) and to stack in the JobRow list of tasks the tasks that arrive using the list w_index. Access to shared memory, especially for the management of indices rjndex and w_index implements a mutex mechanism using the variable of the same name and the function Test And Set.
  • step a1 of FIG. 3 provides for the execution of a Test And Set function on the mutex variable.
  • This variable is representative of the state of the memory shared by all the microprocessors of the set of microprocessors.
  • the result of the Test And Set function is placed in the Get local variable.
  • the mutex variable takes the value 1 and the value Get is equal to either 0 or 1.
  • step a2 if the value Get is not 0, we go back to step a1, this is done until the shared memory is accessible and so the value Get is at O.
  • step a3 the value Get is reset to 0 (optional) and the variable rjndex is compared to the variable wj ' ndex. Indeed, if these two variables are equal, it means that the task list is empty. If this is the case, the method then follows the left branch of the algorithm shown in FIG. 3 which corresponds to the execution of the tasks. The branch on the right (separation at step a4) concerns the stacking of tasks in the task list.
  • step b1 of the left branch the current task
  • Job is copied into the JobRow job list at wj ' ndex.
  • variable wj ' ndex is incremented by one. As already mentioned, this incrementation is modulo RowSize. Because of this, when wj ' ndex is set to RowSize, it is set to 0.
  • step b3 The index wj ' ndex now being modified, the memory can be released and the value mutex is set to 0 in step b2.
  • the task in the JobRow job list at rank rjndex is then executed (step b3).
  • Step b4 then performs a Test And Set function on the mutex variable.
  • the variable Get As long as this variable Get is 1, that is, as long as the shared variable is used by another resource, we return to step b4. However, when the memory becomes accessible, then Get takes the value 0 and it is possible to proceed to step b6 which provides for the incrementation of a unit of the index rjndex.
  • step a5 to release access to the shared memory by setting the mutex variable to 0.
  • step b7 we return to step b2 to perform the next task.
  • variable (wj ' ndex + 1) is then compared to the value of the variable rjndex (modulo RowSize of course). If these values are equal, we assign the value 1 to the local variable Get in step d1; this shows that the task list is filled.
  • step c1 if the JobRow task list is not full, the current task
  • Job is then entered in the JobRow list at rank wj ' ndex. Once the registration is completed, the index wj ' ndex can be incremented by one unit.
  • step a5 resetting the mutex variable to 0 is performed.
  • the method corresponding to the algorithm shown in FIG. 3 is not blocking. It never leads to a potentially infinite hold of a microprocessor. One is sure to avoid such a block if all the processors use the mutex variable concerning the shared memory only with this algorithm (figure 3).
  • the algorithm described has this feature that if multiple microprocessors share the same resource, and therefore the same task list, then when task execution is required, it is not possible to know which microprocessor will execute it. However, this algorithm ensures that the task will be executed by one of the microprocessors sharing the resource, as soon as possible, with management type "FIFO".
  • the present invention is not limited to the methods described above by way of non-limiting examples. It relates to all variants of such methods within the scope of the claims below. This invention also relates to a microprocessor for implementing a method as described above.

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Debugging And Monitoring (AREA)

Abstract

Ce procédé comporte des étapes pour la gestion parallèle d'une première liste et d'une seconde liste. La première liste correspond à une liste de tâches à effectuer. La seconde liste correspond à une liste de variables reflétant la présence ou non de tâches à effectuer. La liste de tâches est gérée de manière "FIFO" c'est-à-dire que la première tâche rentrée dans la liste est la première tâche exécutée. Une interruption de tâche est gérée à l'aide d'une fonction "Test And Set" exécutée sur les éléments de la seconde liste, la fonction "Test And Set" étant une fonction ne pouvant pas être interrompue et comportant les étapes suivantes : - lecture de la valeur de l'élément considéré, - stockage de la valeur lue dans une mémoire locale, - affectation d'une valeur prédéterminée à l'élément qui vient d'être lu.

Description

Procédé de gestion de tâches dans un microprocesseur ou un ensemble
de microprocesseurs
La présente invention concerne un procédé de gestion de tâches dans un microprocesseur ou dans un ensemble de microprocesseurs, et plus particulièrement un procédé gérant l'interruption de tâches dans un microprocesseur.
Un microprocesseur est un dispositif électronique qui peut réaliser diverses tâches, chaque tâche étant une suite de plusieurs instructions. Des moyens sont associés au microprocesseur pour former avec lui un microcontrôleur. Ces moyens supplémentaires permettent la gestion des tâches confiées au microprocesseur.
Un microprocesseur n'effectue habituellement qu'une seule tâche à la fois. Il convient alors de gérer les situations dans lesquelles plusieurs tâches sont à exécuter simultanément ou bien encore le cas où une ou plusieurs tâches sont à exécuter alors qu'une tâche précédente est en cours d'exécution.
Il est par exemple prévu pour certains microprocesseurs de pouvoir interrompre une tâche afin d'en exécuter une autre et de terminer la tâche interrompue une fois la nouvelle tâche achevée.
Une telle gestion est problématique notamment lorsque l'exécution des tâches par le microprocesseur utilise des accès à une mémoire. La réalisation de la nouvelle tâche risque alors de perturber les valeurs mémorisées pour la tâche en cours d'exécution, ce qui bien entendu vient perturber la tâche en cours et peut aboutir à des incohérences dues à l'état instable des données intermédiaires.
Pour remédier à ces problèmes, on peut simplement proscrire toute interruption. Le risque est alors que des tâches soient perdues. On peut également utiliser un logiciel de stockage des tâches en attente. Un tel logiciel gère alors une liste de tâches qui sera appelée par la suite "JobRow". Avec un tel logiciel, la tâche en cours d'exécution est stoppée momentanément, le temps que le logiciel liste des tâches en attente. Ainsi, pendant l'exécution d'une tâche, les tâches arrivant sont stockées par l'intermédiaire du logiciel dans la liste JobRow et seront effectuées une fois la tâche en cours d'exécution terminée.
Cette alternative pose toutefois des problèmes. Si l'interruption d'exécution d'un logiciel est autorisée, l'interruption du logiciel gérant la liste JobRow est également autorisée. Ainsi, une tâche de type "gestion de JobRow" pourra être interrompue par une nouvelle tâche de même type. Le logiciel gérant une liste JobRow peut ainsi être interrompu par lui-même. Pour éviter cet inconvénient, il convient alors de prévoir d'empêcher toute interruption de tâches pendant le fonctionnement de ce logiciel.
Cette gestion d'interruption de tâches fonctionne mais présente l'inconvénient de ralentir la vitesse d'exécution des tâches. En effet, ces arrêts et remises en marche de tâches consomment du temps. En outre, autoriser ces arrêts et remises en marche augmente également le risque de faire une erreur humaine lors de l'écriture du logiciel gérant la « JobRow ». Une telle erreur peut même conduire à un blocage du système.
La présente invention a alors pour but de fournir un procédé de gestion de tâches dans un microprocesseur, permettant notamment de gérer aussi des interruptions de tâches, qui permette un bon fonctionnement du système avec une exécution aussi rapide que possible des tâches. Il convient notamment d'éviter des pertes de temps dues à des arrêts et remises en marche d'une exécution de tâche.
Dans certains systèmes, une ressource est commune à plusieurs microprocesseurs. Ainsi, plusieurs microprocesseurs sont susceptibles d'accéder à cette ressource, dite ressource partagée, pour l'exécution des tâches qui leur sont confiées. Cette ressource partagée ne peut toutefois être utilisée que par un seul microprocesseur à la fois. Il est alors connu d'utiliser des algorithmes d'exclusion mutuelle (ou en anglais "mutual exclusion"), appelés également "mutex", pour gérer l'accès aux ressources partagées.
Avantageusement, la présente invention permettra de gérer également l'accès successif à une ressource partagée commune à plusieurs microprocesseurs.
À cet effet, la présente invention propose un procédé de gestion du traitement de tâches dans un microprocesseur, caractérisé en ce qu'il comporte des étapes pour la gestion parallèle d'une première liste et d'une seconde liste,
• en ce que la première liste correspond à une liste de tâches à effectuer,
• en ce que la seconde liste correspond à une liste de variables reflétant la présence ou non de tâches à effectuer,
• en ce que la liste de tâches est gérée de manière "FIFO", « First In, First Out », en anglais ; ou premier entrant, premier sortant, c'est-à-dire que la première tâche rentrée dans la liste est la première tâche exécutée, et
• en ce qu'une interruption de tâche est gérée à l'aide d'une fonction "Test And Set" exécutée sur les éléments de la seconde liste, la fonction "Test And Set" étant une fonction ne pouvant pas être interrompue et comportant les étapes suivantes :
- lecture de la valeur de l'élément considéré,
- stockage de la valeur lue dans une mémoire locale,
- affectation d'une valeur prédéterminée à l'élément qui vient d'être lu. L'utilisation originale d'une fonction de type "Test And Set" qui ne peut pas être interrompue au niveau justement d'une interruption de tâche permet de conserver des données cohérentes et ainsi un bon déroulement des tâches.
Quand il s'agit d'une liste de tâches, il faut comprendre que les tâches ne sont pas forcément listées mais que des pointeurs associés à des tâches sont les éléments contenus dans la liste. On peut étendre les éléments de la liste à tout type d'élément qui permettrait d'identifier clairement une tâche à exécuter (adresse, etc.).
La présente invention propose également un algorithme détaillé pour mettre en œuvre un tel procédé. Elle propose ainsi également un procédé de gestion du traitement de tâches dans un microprocesseur, caractérisé en ce qu'il comporte des étapes pour la gestion d'une première liste et d'une seconde liste,
• en ce que la première liste est une liste contenant des éléments donnant une indication sur une tâche à effectuer par le microprocesseur,
• en ce que la seconde liste est une liste de variables représentatives d'un état, chaque variable de la seconde liste étant associée à un et un seul élément de la première liste et pouvant prendre une première valeur représentative d'un premier état et une seconde valeur représentative d'un second état,
• en ce qu'une variable globale est définie, cette variable globale pouvant prendre autant de valeurs distinctes qu'il y a d'éléments dans la seconde liste, ladite variable globale permettant de pointer sur une variable dans la première liste ainsi que dans la seconde liste,
• en ce que ladite variable globale est une variable destinée à être incrémentée de manière à pointer dans un ordre donné les éléments de la première liste et de la seconde liste, la première liste et la seconde liste étant considérée comme des listes circulaires, c'est-à-dire que dans ledit ordre donné, le premier élément de la liste est considéré comme l'élément suivant du dernier élément de la liste et inversement, le dernier élément de la liste est considéré comme l'élément précédent du premier élément de la liste,
• en ce que la première étape du procédé, lorsqu'une tâche, dite tâche courante, est confiée au microprocesseur, consiste à effectuer une lecture de la valeur de la seconde liste pointée par la variable globale, à recopier la valeur lue dans une première variable locale et à écrire dans la seconde liste, à la place de la valeur lue, la valeur représentative du second état, cette première étape formant une seule opération, appelée "Test And Set" et ne pouvant être interrompue, en ce que ledit procédé met en œuvre un premier sous procédé dans le cas où la première variable locale a pris la valeur représentative du premier état et un second sous procédé dans le cas où la première variable locale a pris la valeur représentative du second état,
en ce que le premier sous procédé comporte les étapes suivantes :
- 3a) mise à jour de la première liste de telle sorte que l'élément correspondant à la variable locale donne une indication correspondant à la tâche courante,
- 4a) la variable de la seconde liste précédent la variable correspondant à la variable globale est mise à la valeur représentative du premier état,
- 5a) exécution de la tâche courante,
- 6a) incrémentation de la variable globale,
en ce qu'après l'étape 6a), le premier sous procédé retourne à l'étape 4a) si la valeur de la seconde liste correspondant à la variable globale, incrémentée, est représentative du second état, et le procédé est terminé sinon,
en ce que le second sous procédé comporte les étapes suivantes :
- 3b) initialisation d'une seconde variable locale à la valeur 1 , cette seconde variable locale étant destinée à être utilisée pour l'incrémentation de la variable globale,
- 4b) exécution d'une opération "Test And Set" sur la variable de la seconde liste correspondant à la variable globale incrémentée de la valeur de la seconde variable locale, la valeur lue étant recopiée dans une troisième variable locale et la valeur représentative du second état étant prise par l'élément de la seconde liste correspondant à la variable globale incrémentée de la valeur de la seconde variable locale,
- 5b) test sur la troisième variable locale et exécution d'une étape 6b) consistant à mettre à jour la première liste de telle sorte que la variable correspondant à la variable globale incrémentée de la seconde variable locale donne une indication correspondant à la tâche courante puis fin du procédé de gestion des tâches dans la mesure où le résultat du test sur la troisième variable locale indique que celle-ci a une valeur représentative du premier état, dans un cas contraire, une incrémentation de la seconde variable locale est réalisée suivie d'un retour à l'étape 4b) tant que la valeur de la seconde variable locale est strictement inférieure à une valeur limite correspondant au nombre d'éléments de la seconde liste diminué de 1 , et fin du procédé avec perte de la tâche courante si cette valeur limite est dépassée par la seconde variable locale.
Un tel procédé ne contient aucune partie qui ne soit pas interruptible. Il peut donc être interrompu à n'importe quel moment de son exécution et redémarrer une autre exécution. Bien entendu, comme mentionné, la fonction "Test And Set" ne peut pas être interrompue. On peut aussi prévoir une interruption de cet algorithme par lui-même.
L'algorithme du procédé ci-dessus a deux branches, l'une pour l'exécution des tâches, l'autre pour le stockage des nouvelles tâches à exécuter. Il permet d'assurer une cohérence des valeurs produites par les tâches en cours d'exécution sans bloquer l'exécution des autres tâches qui arrivent, ce procédé pouvant être interrompu à tout moment.
Dans ce procédé détaillé, la troisième variable locale est avantageusement confondue avec la première variable locale. Ceci permet d'éviter de multiplier le nombre de variables à gérer.
En outre, pour favoriser une rapidité d'exécution d'un procédé selon la présente invention, les variables de la seconde liste sont de préférence des variables booléennes.
La présente invention concerne également un procédé de gestion du traitement de tâches au niveau d'un ensemble d'au moins deux microprocesseurs. Dans ce procédé, chaque microprocesseur utilise un procédé de gestion de tâches tel que décrit plus haut.
Lorsqu'en outre une mémoire partagée est accessible par chaque microprocesseur de l'ensemble considéré, il est proposé :
• qu'une liste de tâches commune à l'ensemble des microprocesseurs soit définie,
• que cette liste de tâches soit gérée de manière "FIFO" c'est-à-dire que la première tâche rentrée dans la liste est la première tâche exécutée,
• que deux index soient définis en commun pour l'ensemble des microprocesseurs, un premier index indiquant quelle tâche est la prochaine tâche à exécuter et un second index indiquant l'emplacement dans lequel la liste de tâches sera à occuper par la prochaine tâche entrant dans la liste des tâches à effectuer, la gestion de la liste de tâches étant effectuée de manière cyclique, • que l'accès à la mémoire partagée soit géré par un mécanisme "mutex" définissant une variable dont la valeur est représentative de l'état de la mémoire partagée et à l'aide d'une fonction "Test And Set" exécutée sur cette dernière variable, la fonction "Test And Set" étant une fonction ne pouvant pas être interrompue et comportant les étapes suivantes :
- lecture de la valeur de la variable,
- stockage de la valeur lue dans une mémoire locale,
- affectation d'une valeur prédéterminée à la variable qui vient d'être lue.
Une telle gestion au niveau d'un ensemble de microprocesseurs permet une gestion cohérente des ressources (mémoire) communes. Les tâches peuvent s'exécuter les unes après les autres en fonction de leur ordre d'arrivée dans la liste. Toutefois, avec cette gestion, lorsqu'une tâche doit être exécutée, il n'est pas possible de savoir d'avance par quel microprocesseur de l'ensemble de microprocesseurs utilisant la ressource partagée cette tâche sera exécutée.
La présente invention concerne également un programme d'ordinateur stocké sur un support d'informations, ledit programme comportant des instructions permettant la mise en œuvre d'un procédé de gestion de tâches tel que décrit plus haut, lorsque ce programme est chargé et exécuté par un système informatique, tel un microprocesseur.
Enfin, la présente invention concerne aussi un microprocesseur, caractérisé en ce qu'il comporte des instructions d'un programme permettant la mise en œuvre d'un procédé de gestion de tâches tel que décrit plus haut.
Des détails et avantages de la présente invention ressortiront mieux de la description qui suit, faite en référence aux dessins schématiques annexés sur lesquels :
· La figure 1 est un algorithme illustrant un procédé de gestion de tâches selon la présente invention,
• La figure 2 illustre schématiquement une mémoire partagée par plusieurs microprocesseurs, et
• La figure 3 illustre un algorithme pour la gestion de tâches des microprocesseurs et de l'accès à la mémoire partagée représentés schématiquement sur la figure 2.
La figure 1 représente un algorithme permettant la mise en œuvre d'une forme de réalisation préférée d'un procédé de gestion de tâches selon la présente invention. Différents éléments sont utilisés dans cet algorithme. Parmi ceux-ci, on a notamment :
· RowSize, il s'agit d'une variable qui est un nombre entier supérieur à deux.
Il correspond au nombre de tâches pouvant être mises en attente dans le microprocesseur. • rjndex : il s'agit d'un nombre entier pouvant prendre toutes les valeurs de 0 à (RowSize-1 ).
• JobRow : il s'agit d'une liste d'éléments qui sont au nombre de RowSize. Ces éléments peuvent être directement des tâches ou bien un pointeur indiquant l'emplacement d'une tâche, ou tout autre élément qui permet de définir des tâches, notamment des tâches à exécuter.
• TasRow : il s'agit ici d'une liste de variables, de préférence des variables booléennes. Il y a autant de variables dans cette liste que dans JobRow. Cette liste est le reflet de JobRow et permet de connaître les positions des tâches stockées dans JobRow.
• Get : il s'agit d'une variable locale, disponible uniquement au niveau du microprocesseur et dont un nouvel exemplaire est créé à chaque fois que le procédé est interrompu dans son exécution pour être exécuté de nouveau depuis le début. Il s'agit de préférence d'une variable booléenne. · N : il s'agit ici aussi d'une variable locale. On supposera par la suite qu'il s'agit d'un nombre entier. Comme indiqué par la suite, cette variable locale est utilisée pour la lecture des éléments de TasRow.
Lorsque le programme correspondant à l'algorithme représenté sur la figure 1 est initialisé, rjndex est mis à zéro ainsi que tous les éléments de la liste TasRow.
Le point noir en haut de la figure 1 correspond au point d'entrée du programme qui va être décrit ci-après.
L'étape 1 met en œuvre une fonction appelée par la suite "Test And Set". Il s'agit d'une fonction qui ne peut être interrompue. Elle sera appliquée ici à des variables booléennes. Cette fonction Test And Set effectue une lecture de la variable booléenne, stocke la valeur de cette variable dans une mémoire tampon, une mémoire locale, puis donne à la variable booléenne lue une valeur prédéterminée, ici la valeur 1. À l'étape 1 , la fonction Test And Set est appliquée à l'élément de la liste TasRow d'indice rjndex. La valeur, 0 ou 1 , de cet élément de la liste TasRow est alors placée dans la mémoire locale Get puis l'élément de rang rjndex dans TasRow prend la valeur 1.
À l'étape 2, la valeur de Get est analysée et en fonction de la réponse obtenue, le programme exécute la branche de gauche de l'algorithme ou la branche de droite de cet algorithme. La branche de gauche de l'algorithme permet d'exécuter les tâches tandis que la branche de droite est utilisée pour stocker les nouvelles tâches à exécuter.
À l'étape 3a, si la valeur de Get est donc 0, la tâche "Job" est mise dans la liste JobRow au rang rjndex. Ensuite, à l'étape 4a, la valeur de rang précédent au rang r_index est alors mise à 0 dans la liste TasRow.
Il est à remarquer ici que la gestion de toutes les listes est une gestion circulaire (également dans le procédé par la suite concernant plusieurs microprocesseurs). Ainsi par exemple, si RowSize vaut 10, rjndex peut varier entre 0 et 9. Lorsque rjndex vaut alors 9 et qu'il est incrémenté d'une unité, sa valeur devient 0. Une telle gestion cyclique d'une liste est tout à fait habituelle pour l'homme du métier.
À l'étape suivante, étape 5a, Job, qui correspond à l'élément rangé dans la liste JobRow au rang rjndex, est exécuté. Ce n'est que lorsque la tâche est entièrement exécutée que la variable rjndex est incrémentée d'une unité (étape 6a).
À l'étape 7a, on regarde dans la liste TasRow l'élément de rang rjndex, ce rang étant le nouveau rang incrémenté. Si la valeur de cet élément vaut 1 , cela signifie qu'une tâche est à exécuter. L'algorithme renvoie alors dans ce cas à l'étape 4a. Par contre, s'il n'y a plus de tâche à exécuter, le programme est achevé. Le point en bas de la figure 1 représente la sortie du programme correspondant à l'algorithme.
La branche de gauche de l'algorithme ayant maintenant été décrite, intéressons-nous à la branche de droite. Cette branche concerne le stockage de tâches dans la liste de tâches JobRow.
À l'entrée de la branche de droite, à l'étape 3b, la variable locale N est initialisée à la valeur 1. On réalise ensuite à l'étape 4b une fonction Test And Set sur l'élément de la liste TasRow de rang rjndex + N, bien entendu modulo RowSize. Une troisième variable locale pourrait être utilisée ici comme mémoire tampon. En fait, il est inutile d'utiliser ici une troisième variable, la variable locale Get étant disponible pour empiler les tâches confiées au microprocesseur et ne pouvant être de suite exécutées. Le résultat de la fonction Test and Set au niveau de l'étape 4b est alors enregistré dans la variable locale Get. Si celle-ci vaut alors 0 (étape 5b), la place de rang rjndex + N est alors libre dans la liste JobRow et la tâche Job, qui est la tâche courante ayant déclenché le programme, est alors stockée dans JobRow au rang rjndex + N (modulo RowSize bien entendu). La tâche étant dans la liste d'attente, le programme est alors terminé.
Par contre, à l'étape 5b, si la valeur de Get n'est pas 0, c'est-à-dire qu'elle vaut 1 , il convient d'incrémenter N d'une unité pour regarder si la place suivante dans la liste des tâches JobRow est libre. On continue alors à regarder toutes les places dans la liste JobRow jusqu'à trouver une place libre (boucle 4b, 5b, 6c, 7c, 4b). Si la liste des tâches est entièrement remplie (étape 7c), la tâche courante "Job" est alors perdue. Le programme est alors également terminé.
Le procédé de gestion des tâches qui vient d'être décrit ici présente l'avantage qu'il ne contient aucune partie qui ne soit pas interruptive. Il est toutefois rappelé ici que la fonction Test And Set ne peut pas être interrompue. Le procédé décrit ci-dessus et illustré sur la figure 1 peut être interrompu à n'importe quel moment de son exécution pour redémarrer une autre exécution. Dans le cas de l'interruption de ce procédé par lui-même, son exécution est suspendue jusqu'à ce que la prochaine exécution soit finie.
L'algorithme proposé ici permet d'enregistrer des tâches dans la liste des tâches dès qu'une tâche en cours d'exécution est terminée. Les tâches sont stockées et lues par leur ordre d'arrivée. On a donc ici une gestion "FIFO" (de l'anglais First In First Out, ou en français, premier entré premier sorti).
La mise en oeuvre de cet algorithme permet d'assurer une cohérence des valeurs produites par les tâches en cours d'exécution sans bloquer l'exécution des autres tâches qui arrivent, puisque le procédé correspondant est à tout moment interruptible. Cette cohérence est notamment obtenue grâce au fait que l'algorithme servant à l'exécution et au stockage des tâches est basé sur une fonction, la fonction Test And Set qui n'est pas interruptive et ne peut donc être interrompue.
La présente invention prévoit également de gérer des tâches d'un ensemble de microprocesseurs, cet ensemble présentant une mémoire partagée à laquelle chacun des microprocesseurs de l'ensemble peut accéder.
À titre d'exemple non-limitatif et simplement illustratif, la figure 2 représente quatre microprocesseurs, appelés CPU A, CPU B, CPU C et CPU D. On suppose ici par exemple que ces quatre microprocesseurs sont tous les quatre identiques mais bien entendu l'invention fonctionne également avec des microprocesseurs qui ne seraient pas semblables. Une mémoire au centre de la figure 2 contient des données accessibles et modifiables par les quatre microprocesseurs de l'ensemble des microprocesseurs. On suppose ici, toujours à titre d'exemple non-limitatif, que chaque microprocesseur possède quatre niveaux ("Level") d'interruption.
Pour la cohérence du système, il convient de prévoir un mécanisme de sécurité qui permette de mettre en attente une tâche qui devrait être exécutée lorsqu'une autre tâche utilisant des données communes est déjà en cours d'exécution. Il convient ici de gérer plusieurs microprocesseurs avec chacun plusieurs niveaux d'interruption. Il convient ainsi de trouver un mécanisme de verrouillage qui permette d'assurer une cohérence des données pour l'exécution de chaque programme. On souhaite ainsi s'assurer qu'il soit accédé à la mémoire partagée séquentiellement par toutes les tâches, c'est-à-dire que chaque tâche soit entièrement réalisée avant qu'une autre ne soit démarrée. Comme illustré à titre d'exemple sur la figure 2, on souhaite gérer par exemple une situation où le niveau 3 du CPU A, le niveau 1 du CPU A, le niveau 4 du CPU B, le niveau 2 du CPU B, le niveau 3 du CPU C et le niveau 1 du CPU D nécessitent un accès à une même mémoire en même temps. L'algorithme de la figure 3 est destiné à la gestion de tâches pour plusieurs microprocesseurs ainsi qu'à la gestion d'une mémoire partagée entre ces microprocesseurs.
Il est proposé ici tout d'abord que chacun des microprocesseurs gère ses tâches selon un procédé tel celui décrit plus haut en référence à la figure 1. Le procédé de la figure 3 concerne quant à lui une gestion de tâches au niveau de l'ensemble des microprocesseurs, c'est-à-dire ici les microprocesseurs CPU A, CPU B, CPU V et CPU D.
La présente invention propose ici d'utiliser une liste commune de tâches, appelée ici également JobRow. On reprendra ici les mêmes noms que précédemment pour des éléments semblables. Toutefois, dans la description qui suit, les éléments concernent l'ensemble des microprocesseurs et la mémoire partagée.
Le procédé représenté sur l'algorithme de la figure 3 met ainsi notamment en œuvre les éléments suivants :
• JobRow, déjà évoqué plus haut. Il s'agit d'une liste de tâches concernant l'ensemble des microprocesseurs,
• RowSize, il s'agit du nombre d'éléments pouvant se trouver dans JobRow,
• r_index, il s'agit d'une variable entière pouvant prendre RowSize valeur. On supposera ici que rjndex peut prendre les valeurs allant de 0 à RowSize - 1. Comme on le verra plus loin, le procédé prévoit de lire les tâches pour les exécuter d'un côté et d'un autre côté de placer des tâches à exécuter dans la liste de tâches. L'indice rjndex est utilisé pour la lecture (r de "read" en anglais ou lire en français),
• wj'ndex, de même que rjndex, il s'agit d'une variable entière pouvant prendre RowSize valeur. Dans la pratique, elle prendra les valeurs de 0 à RowSize -1. Cet indice wj'ndex est utilisé pour empiler des tâches dans la liste de tâches JobRow (w de "write" en anglais ou écrire en français),
• mutex, cette variable indique l'état de la mémoire partagée. Elle sert notamment à bloquer l'accès à cette mémoire. Dans la pratique, on choisira pour mutex une variable booléenne prenant soit la valeur 0 lorsque la mémoire est accessible, soit la valeur 1 pour indiquer que la mémoire est bloquée,
• Get, il s'agit ici d'une variable locale qui est ici également choisie, de préférence, comme étant une variable booléenne.
Au départ, les variables sont initialisées en mettant à 0 les valeurs de rjndex, wj'ndex et mutex. On considère ici que RowSize est au moins égal à 3.
Dans le procédé qui suit, la liste des tâches, JobRow, est gérée de manière "FIFO". La liste JobRow est, comme déjà mentionné précédemment, gérée comme une liste cyclique. Dans cette liste cyclique, toutes les tâches à exécuter sont regroupées. Il ne peut pas y avoir de "place(s) libre(s)" entre deux tâches de la liste JobRow. Le procédé décrit ci-après prévoit simplement l'exécution de la première tâche à exécuter (suivi avec l'index r_index) et d'empiler dans la liste de tâches JobRow les tâches qui arrivent à l'aide de la liste w_index. L'accès à la mémoire partagée, notamment pour la gestion des indices rjndex et w_index met en œuvre un mécanisme mutex utilisant la variable du même nom et la fonction Test And Set.
Ainsi, la première étape, l'étape a1 de la figure 3, prévoit l'exécution d'une fonction Test And Set sur la variable mutex. Cette variable est représentative de l'état de la mémoire partagée par tous les microprocesseurs de l'ensemble de microprocesseurs. Le résultat de la fonction Test And Set est placé dans la variable locale Get. Comme il est habituel pour la fonction Test And Set, la variable mutex prend donc la valeur 1 et la valeur Get est égale soit à 0, soit à 1.
À l'étape a2, si la valeur Get ne vaut pas 0, on retourne à l'étape a1 , ceci est réalisé jusqu'à ce que la mémoire partagée soit accessible et que donc la valeur Get soit à O.
À l'étape a3, la valeur Get est réinitialisée à 0 (facultatif) et la variable rjndex est comparée à la variable wj'ndex. En effet, si ces deux variables sont égales, cela signifie que la liste des tâches est vide. Si c'est le cas, le procédé suit alors la branche de gauche de l'algorithme représenté sur la figure 3 qui correspond à l'exécution des tâches. La branche de droite (séparation au niveau de l'étape a4) concerne quant à elle l'empilage de tâches dans la liste de tâches.
La description ci-après commente tout d'abord la branche de gauche (étapes b1 à b7) puis ensuite la branche de droite de l'algorithme de la figure 1.
Dans la première étape (étape b1) de la branche de gauche, la tâche courante
Job est recopiée dans la liste de tâches JobRow au rang wj'ndex. En outre, la variable wj'ndex est incrémentée d'une unité. Comme déjà mentionné, cette incrémentation se fait modulo RowSize. De ce fait, lorsque wj'ndex doit prendre la valeur RowSize, elle prend la valeur 0.
L'indice wj'ndex étant maintenant modifiée, la mémoire peut être libérée et la valeur mutex est mise à 0 à l'étape b2. La tâche se trouvant dans la liste de tâches JobRow au rang rjndex est alors exécutée (étape b3).
De même que précédemment, pour le procédé décrit en référence à la figure 1 , une fois la tâche réalisée, l'indice de rang rjndex peut être incrémenté. Toutefois, il faut ici s'assurer que l'accès à la mémoire partagée est disponible. On réalise alors à l'étape b4 une fonction Test And Set sur la variable mutex. Comme déjà suggéré précédemment pour le procédé illustré sur la figure 1 , il est inutile de choisir une variable locale supplémentaire. On reprend ici la variable Get. Tant que cette variable Get vaut 1 , c'est-à-dire tant que la variable partagée est utilisée par une autre ressource, on revient à l'étape b4. Toutefois, quand la mémoire devient accessible, Get prend alors la valeur 0 et on peut passer à l'étape b6 qui prévoit l'incrémentation d'une unité de l'indice rjndex.
Une fois l'indice rjndex incrémenté, il est à nouveau comparé à l'indice wj'ndex. Si ces deux indices sont égaux, c'est-à-dire si la liste des tâches est vide, le programme peut être achevé. Toutefois, avant de sortir du programme, il est prévu, à l'étape a5, de libérer l'accès à la mémoire partagée en donnant à la variable mutex la valeur 0.
Dans le cas contraire (rjndex différent de wj'ndex, à l'étape b7), on retourne à l'étape b2 pour effectuer la tâche suivante.
La branche de gauche de l'algorithme de la figure 3 étant maintenant décrite, la suite de la description va porter sur la branche de droite de cet algorithme.
La valeur de la variable (wj'ndex + 1) est alors comparée à la valeur de la variable rjndex (modulo RowSize bien entendu). Si ces valeurs sont égales, on affecte la valeur 1 à la variable locale Get à l'étape d1 ; cela permet de voir que la liste de tâches est remplie. On peut ici aussi utiliser la variable locale Get, et non pas définir une variable locale particulière car cette variable Get sera remise à 0 après exécution d'une tâche par le procédé (ou quand une nouvelle tâche est ajoutée à la liste de tâches).
À l'étape c1 , si la liste de tâches JobRow n'est pas pleine, la tâche courante
Job est alors inscrite dans la liste JobRow au rang wj'ndex. Une fois l'inscription réalisée, l'indice wj'ndex peut être incrémenté d'une unité.
La tâche étant correctement empilée, les indices étant mis à jour, le programme peut être terminé. Toutefois, pour libérer l'accès à la mémoire partagée, l'étape a5 réinitialisant la variable mutex à la valeur 0 est réalisée.
Le procédé correspondant à l'algorithme représenté sur la figure 3 n'est pas bloquant. Il ne conduit jamais à une mise en attente potentiellement infinie d'un microprocesseur. On est sûr d'éviter un tel blocage si tous les processeurs utilisent la variable mutex concernant la mémoire partagée uniquement avec cet algorithme (figure 3).
De cette manière, si un microprocesseur a une tâche à effectuer en accédant à des données partagées, il va mettre cette tâche dans la liste de tâches et lui-même ou un autre microprocesseur exécutera cette tâche ultérieurement lorsque la ressource partagée sera disponible.
L'algorithme décrit présente cette caractéristique que si plusieurs microprocesseurs partagent une même ressource, et de ce fait une même liste de tâches, alors lorsqu'une exécution de tâche est requise, il n'est pas possible de savoir quel microprocesseur va l'exécuter. Toutefois, cet algorithme garantit que la tâche va être exécutée par l'un des microprocesseurs partageant la ressource, aussitôt que possible, avec une gestion de type "FIFO".
La présente invention ne se limite pas aux procédés décrits ci-dessus à titre d'exemples non-limitatifs. Elle concerne toutes les variantes de réalisation de tels procédés dans le cadre des revendications ci-après. Cette invention concerne également un microprocesseur permettant la mise en œuvre d'un procédé tel que décrit plus haut.

Claims

REVENDICATIONS
1. Procédé de gestion du traitement de tâches dans un microprocesseur, caractérisé en ce qu'il comporte des étapes pour la gestion d'une première liste et d'une seconde liste :
• en ce que la première liste est une liste contenant des éléments donnant une indication sur une tâche à effectuer par le microprocesseur,
• en ce que la seconde liste est une liste de variables représentatives d'un état, chaque variable de la seconde liste étant associée à un et un seul élément de la première liste et pouvant prendre une première valeur représentative d'un premier état et une seconde valeur représentative d'un second état,
• en ce qu'une variable globale est définie, cette variable globale pouvant prendre autant de valeurs distinctes qu'il y a d'éléments dans la seconde liste, ladite variable globale permettant de pointer sur une variable dans la première liste ainsi que dans la seconde liste,
· en ce que ladite variable globale est une variable destinée à être incrémentée de manière à pointer dans un ordre donné les éléments de la première liste et de la seconde liste, la première liste et la seconde liste étant considérées comme des listes circulaires, c'est-à-dire que dans ledit ordre donné, le premier élément de la liste est considéré comme l'élément suivant du dernier élément de la liste et inversement, le dernier élément de la liste est considéré comme l'élément précédent du premier élément de la liste,
• en ce que la première étape du procédé, lorsqu'une tâche, dite tâche courante, est confiée au microprocesseur, consiste à effectuer une lecture de la valeur de la seconde liste pointée par la variable globale, à recopier la valeur lue dans une première variable locale et à écrire dans la seconde liste, à la place de la valeur lue, la valeur représentative du second état, cette première étape formant une seule opération, appelée "Test And Set" et ne pouvant être interrompue et comportant les étapes suivantes :
- lecture de la valeur de l'élément considéré,
- stockage de la valeur lue dans une mémoire locale,
- affectation d'une valeur prédéterminée à l'élément qui vient d'être lu,
• en ce que ledit procédé met en œuvre un premier sous procédé dans le cas où la première variable locale a pris la valeur représentative du premier état et un second sous procédé dans le cas où la première variable locale a pris la valeur représentative du second état,
• en ce que le premier sous procédé comporte les étapes suivantes :
- 3a) mise à jour de la première liste de telle sorte que l'élément correspondant à la variable locale donne une indication correspondant à la tâche courante,
- 4a) la variable de la seconde liste précédent la variable correspondant à la variable globale est mise à la valeur représentative du premier état,
- 5a) exécution de la tâche courante,
- 6a) incrémentation de la variable globale,
• en ce qu'après l'étape 6a), le premier sous procédé retourne à l'étape 4a) si la valeur de la seconde liste correspondant à la variable globale, incrémentée, est représentative du second état, et le procédé est terminé sinon,
• en ce que le second sous procédé comporte les étapes suivantes :
- 3b) initialisation d'une seconde variable locale à la valeur 1 , cette seconde variable locale étant destinée à être utilisée pour l'incrémentation de la variable globale,
- 4b) exécution d'une opération "Test And Set" sur la variable de la seconde liste correspondant à la variable globale incrémentée de la valeur de la seconde variable locale, la valeur lue étant recopiée dans une troisième variable locale et la valeur représentative du second état étant prise par l'élément de la seconde liste correspondant à la variable globale incrémentée de la valeur de la seconde variable locale,
- 5b) test sur la troisième variable locale et exécution d'une étape 6b) consistant à mettre à jour la première liste de telle sorte que la variable correspondant à la variable globale incrémentée de la seconde variable locale donne une indication correspondant à la tâche courante puis fin du procédé de gestion des tâches dans la mesure où le résultat du test sur la troisième variable locale indique que celle-ci a une valeur représentative du premier état, dans un cas contraire, une incrémentation de la seconde variable locale est réalisée suivie d'un retour à l'étape 4b) tant que la valeur de la seconde variable locale est strictement inférieure à une valeur limite correspondant au nombre d'éléments de la seconde liste diminué de 1 , et fin du procédé avec perte de la tâche courante si cette valeur limite est dépassée par la seconde variable locale.
2. Procédé selon la revendication 1T caractérisé en ce que la troisième variable locale est confondue avec la première variable locale.
3. Procédé selon l'une des revendications 1 à 2, caractérisé en ce que les variables de la seconde liste sont des variables booléennes.
4. Procédé de gestion du traitement de tâches au niveau d'un ensemble d'au moins deux microprocesseurs, caractérisé en ce que chaque microprocesseur utilise un procédé de gestion de tâches selon l'une des revendications 1 à 3.
5. Procédé selon la revendication 4, caractérisé en ce qu'une mémoire partagée est accessible par chaque microprocesseur de l'ensemble considéré,
• en ce qu'une liste de tâches communes à l'ensemble des microprocesseurs est définie,
· en ce que cette liste de tâches est gérée de manière "FIFO" c'est-à-dire que la première tâche rentrée dans la liste est la première tâche exécutée,
• en ce que deux index sont définis en commun pour l'ensemble des microprocesseurs, un premier index indiquant quelle tâche est la prochaine tâche à exécuter et un second index indiquant l'emplacement dans lequel la liste de tâches sera à occuper par la prochaine tâche entrant dans la liste des tâches à effectuer, la gestion de la liste de tâches étant effectuée de manière cyclique,
• en ce que l'accès à la mémoire partagée est géré par un mécanisme "mutex" définissant une variable dont la valeur est représentative de l'état de la mémoire partagée et à l'aide d'une fonction "Test And Set" exécutée sur cette dernière variable, la fonction "Test And Set" étant une fonction ne pouvant pas être interrompue et comportant les étapes suivantes :
- lecture de la valeur de la variable,
- stockage de la valeur lue dans une mémoire locale,
- affectation d'une valeur prédéterminée à la variable qui vient d'être lue.
6. Programme d'ordinateur stocké sur un support d'informations, ledit programme comportant des instructions permettant la mise en œuvre d'un procédé de gestion de tâches selon l'une quelconque des revendications 1 à 5, lorsque ce programme est chargé et exécuté par un système informatique, tel un microprocesseur.
7. Microprocesseur, caractérisé en ce qu'il comporte des instructions d'un programme permettant la mise en œuvre d'un procédé de gestion de tâches selon l'une quelconque des revendications 1 à 5.
PCT/EP2011/003973 2010-09-21 2011-08-09 Procede de gestion de taches dans un microprocesseur ou un ensemble de microprocesseurs WO2012038000A1 (fr)

Priority Applications (2)

Application Number Priority Date Filing Date Title
US13/819,182 US9135058B2 (en) 2010-09-21 2011-08-09 Method for managing tasks in a microprocessor or in a microprocessor assembly
CN201180045180.XA CN103154894B (zh) 2010-09-21 2011-08-09 用于管理微处理器中的或微处理器组件中的任务的方法

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR1003747A FR2965077B1 (fr) 2010-09-21 2010-09-21 Procede de gestion de taches dans un microprocesseur ou un ensemble de microprocesseurs
FR10/03747 2010-09-21

Publications (1)

Publication Number Publication Date
WO2012038000A1 true WO2012038000A1 (fr) 2012-03-29

Family

ID=43927848

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2011/003973 WO2012038000A1 (fr) 2010-09-21 2011-08-09 Procede de gestion de taches dans un microprocesseur ou un ensemble de microprocesseurs

Country Status (4)

Country Link
US (1) US9135058B2 (fr)
CN (1) CN103154894B (fr)
FR (1) FR2965077B1 (fr)
WO (1) WO2012038000A1 (fr)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8904451B2 (en) * 2012-04-13 2014-12-02 Theplatform, Llc Systems for prioritizing video processing events based on availability of media file and agent to process the event type
CN106021100B (zh) * 2016-05-12 2018-12-04 中国电子科技集团公司第四十一研究所 一种支持并行测试的测试任务运行调度方法
JP6859922B2 (ja) * 2017-10-24 2021-04-14 オムロン株式会社 制御装置、制御装置の制御方法、情報処理プログラム、および記録媒体

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6009454A (en) * 1994-09-30 1999-12-28 Allen-Bradley Company, Llc Multi-tasking operation system for industrial controller

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN1714340A (zh) * 2002-10-15 2005-12-28 皇家飞利浦电子股份有限公司 使数据处理设备中的至少两个处理装置同步化的数据处理设备和方法
JP2005005909A (ja) * 2003-06-10 2005-01-06 Sony Ericsson Mobilecommunications Japan Inc 競合管理プログラム，競合管理プログラムが記憶された記憶媒体，競合管理方法及び電子機器
CN101425024A (zh) * 2008-10-24 2009-05-06 中国移动通信集团山东有限公司 一种多任务处理方法及装置
US9063779B2 (en) * 2010-01-06 2015-06-23 Mindspeed Technologies, Inc. Task list generation, parallelism templates, and memory management for multi-core systems

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6009454A (en) * 1994-09-30 1999-12-28 Allen-Bradley Company, Llc Multi-tasking operation system for industrial controller

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
MICHAEL SCHOBEL AND ANDREAS POLZE: "Kernel-mode scheduling server for CPU partitioning: a case study using the Windows research kernel", SAC '08 PROCEEDINGS OF THE 2008 ACM SYMPOSIUM ON APPLIED COMPUTING, 2008, New York, NY, USA, pages 1700 - 1704, XP002636316, Retrieved from the Internet <URL:http://delivery.acm.org/10.1145/1370000/1364091/p1700-schobel.pdf?key1=1364091&key2=5793015031&coll=DL&dl=ACM&ip=145.64.134.241&CFID=20511403&CFTOKEN=22492694> [retrieved on 20110510] *
YINGLONG XIA ET AL: "Hierarchical Scheduling of DAG Structured Computations on Manycore Processors with Dynamic Thread Grouping", 23 April 2010, JOB SCHEDULING STRATEGIES FOR PARALLEL PROCESSING, SPRINGER BERLIN HEIDELBERG, BERLIN, HEIDELBERG, PAGE(S) 154 - 174, ISBN: 978-3-642-16504-7, XP019154641 *

Also Published As

Publication number Publication date
FR2965077A1 (fr) 2012-03-23
CN103154894A (zh) 2013-06-12
CN103154894B (zh) 2016-08-31
FR2965077B1 (fr) 2016-12-09
US20130185727A1 (en) 2013-07-18
US9135058B2 (en) 2015-09-15

Similar Documents

Publication Publication Date Title
EP3129874B1 (fr) Systeme de calcul distribue mettant en oeuvre une memoire transactionnelle materielle de type non-speculatif et son procede d&#39;utilisation pour le calcul distribue
EP2480969B1 (fr) Système et procédé de gestion de l&#39;execution entrelacée de fils d&#39;instructions
FR3025908A1 (fr) Mecanisme et procede pour acceder a des donnees dans une memoire partagee
EP1043658A1 (fr) Procédé d&#39;amélioration des performances d&#39;un système multiprocesseur comprenant une file d&#39;attente de travaux et architecture de système pour la mise en oeuvre du procédé
FR3025907A1 (fr) Mecanisme et procede pour permettre une communication entre un client et un serveur en accedant a des donnees de messages en memoire partagee.
EP2870535B1 (fr) Procede d&#39;execution, au sein d&#39;un systeme embarque multitaches, d&#39;une application cadencee par plusieurs domaines de temps differents incluant une gestion d&#39;interruptions
FR2997774A1 (fr) Procede, dispositif et programme d&#39;ordinateur de placement de taches dans un systeme multi-cœurs
WO2012038000A1 (fr) Procede de gestion de taches dans un microprocesseur ou un ensemble de microprocesseurs
EP0540383B1 (fr) Système multiprocesseur avec moyens microprogrammés pour la répartition des processus aux processeurs
EP2726985B1 (fr) Dispositif et procede de synchronisation de taches executees en parallele sur une plateforme comprenant plusieurs unites de calcul
CA2352420A1 (fr) Dispositif de gestion de memoire permettant l&#39;inscription de blocs de donnees par substitution
FR2980611A1 (fr) Circuit pour planifier le deroulement d&#39;un traitement de donnees
WO2021156308A2 (fr) Procede de gestion de donnees echantillonnees partagees entre plusieurs unites de traitement
FR2503900A1 (fr) Dispositif de reprise pour installation de traitement de donnees
FR2829847A1 (fr) Procede de controle d&#39;acces a des ressources partagees dans un systeme embarque et systeme embarque pour la mise en oeuvre d&#39;un tel procede
WO1998034171A1 (fr) Procede et dispositif de traitement de plusieurs applications techniques avec pour chacune d&#39;elles la surete qui lui est propre
FR3087982A1 (fr) Procede et circuit de multiplexage temporel d&#39;acces concurrents a une ressource informatique
EP3131005A1 (fr) Equipement électronique ferroviaire comprenant un programme de démarrage comportant une ou plusieurs partitions de démarrage, véhicule ferroviaire et système ferroviaire associés
EP2860630A1 (fr) Procédé de transfert de données dans un environnement dynamique
EP4113297A1 (fr) Procédé de gestion des travaux dans un système informatique et système associé
EP4206907A1 (fr) Procédé et système de supervision de mise à jour de logiciel de support dans une infrastructure de fourniture de services
FR2829848A1 (fr) Procede de gestion d&#39;acces a des ressources partagees dans un systeme embarque et systeme embarque pour la mise en oeuvre d&#39;un tel procede
WO2025003099A1 (fr) Procédé d&#39;adaptation du dimensionnement d&#39;une infrastructure de virtualisation à une charge de service
FR3139639A1 (fr) Procédé et dispositif de transmission répétée de données définies
WO2019115907A1 (fr) Dispositif, chaine de traitement de données et procédé de commutation de contexte

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201180045180.X

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 11743780

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 13819182

Country of ref document: US

122 Ep: pct application non-entry in european phase

Ref document number: 11743780

Country of ref document: EP

Kind code of ref document: A1