La contrainte TEMPS

                         Revenons sur le controle des deux chariots. lorsque le chariot A arrive en B et ferme le contact b, et à supposer qu'il n'y a pas de commande reflèxe (arret  automatique sans  intervention  de l'UC ), L'unité de controle qui recoit l'information logique b ne dispose que d'une fraction de  seconde  pour  commander l'arret du moteur. Ce temps est évidemment critique et demande à ce que le système réagisse dans  les  meilleurs  délais  à  l'évènement fin de course b fermé. On dit qu'il y a réaction de l'unité centrale en temps réel.
 

TEMPS DE REPONSE

               Le laps de temps écoulé entre l'instant de l'évènement et l'instant de la commande d'arret du moteur  caractérise  le temps de réponse du système. La diversité des éléments sous controle fait que cet évènement peut se manifester sans qu'il y ait pour autant prise en  compte immédiate de la part de l'U.C. Celui-ci  peut  ètre en cours d'exécution d'un travail (pour le compte par exemple de la console opérateur) qu'il ne peut pas pour de bonnes raisons "interrompre" dans les quelques microsecondes qui suivent l'occurence de b .

               Examinons, et en nous situant dans le cas le plus défavorable, la chronologie  des  actions  élémentaires  qui  suivent l'occurence de  b.

         L'évènement ne sera porté à la  connaissance  de l'unité centrale qu'à l'instant t1. Ce n'est seulement qu'une  prise en compte. Il peut encore y avoir des exécutions plus prioritaires.  A partir de cet instant l'UC sait seulement qu'il y a  lieu de faire quelque chose dans les meilleurs délais .
 

         Ce ne sera qu'à l'instant t3 qu'il y aura exécution du  segment  de programme associé. Nous verrons plus loin que  cette  exécution peut elle-mème subir encore des interruptions momentanées (IT) au  profit de taches de priorités plus élevées.
 

         Enfin, il y a génération de la commande d'arret à l'instant   t4  avec une fin d'exécution de la routine à l'instant  t5.
 

         Autant de contretemps qu'il faut prendre en compte dans la phase de  conception du système de controle tant au  plan  logiciel  qu'au  plan matériel.
 

         Conscient de ces aspects, le concepteur devra  vérifier le fonctionnement "pire cas". Il s'assure  que mème dans les situations les plus défavorables, la somme des temps de latence et de traitement ne saurait  excéder  la  durée  d'une demie seconde qui a été arretée comme contrainte à respecter. Une analyse fine voire une simulation pire cas peuvent s'imposer. Avec un chiffrage aussi précis  que  possible  des  différents  temps  en  se   placant naturellement dans le cas le plus défavorable.
 

      ORDRES de GRANDEURS
 
 

         Si le système a réagit en moins d'une seconde, notons tout de mème que ce temps représente quelques centaines  de  millisecondes  ou encore des centaines de milliers de microsecondes. Si nous  estimons que le microprocesseur en place  effectue  en  moyenne une  opération élémentaire en un millionième de seconde, il faut  se  rendre  compte qu'il  peut  effectuer de   l'ordre   de   500.000   opérations élémentaires dans le temps dt qui sépare l'instant de l'évènement  et celui de la commande "arret moteur" .
 

         Toujours dans le mème ordre d'idée, notons que le temps mis par la palette  d'un relais  pour  commuter  est  de  l'ordre de quelques millisecondes. Dans ce mème temps le  microprocesseur  exécute  plus d'un millier d'instructions .

         En d'autres termes, les échelles de temps du processus commandé  et du processeur sont ici dans un rapport un million . D'un coté c'est la seconde qui est la référence de temps, de l'autre, la microseconde, voire la nanoseconde si nous situons au coeur mème du microprocesseur.
 

         Ce sont la des ordres de grandeurs qu'il nous faut conserver présents à l'esprit dans l'étape de conception d'un système programmé ou microprogrammé.
 

Notion d'EVENEMENT
 

         Un  évènement est  la  manifestation  d'un  fait  nouveau appelant de la part de l'unité centrale une réaction. l'UC doit prendre des décisions et exécuter  un certain travail (tache) pour le compte très précisément de cet évènement. Cette manifestation a  dans  le  temps  un  caractère aléatoire. On dit encore de ce type d'evènement qu'il est asynchrone, au sens ou l'unité centrale ne peut prévoir l'instant  de son occurence. Il est imprévisible et ne présente généralement pas de caractère de périodicité. C'est bien le cas de la fermeture du contact B.
 

         Un évènement peut  ètre  de  nature  externe  autant  qu'interne.  L'évènement a=1 est externe. C'est le procédé controlé qui a émis le signal à destination de l'unité de controle.

         Un segment de programme (ou une tache logicielle) peut aussi produire un  évènement. C'est alors un évènement interne. Il est  généralement destiné à un autre segment de programme.  Ainsi  une  fois  le  buffer  image rempli il y aura demande d'exécution du programme de  traitement de cette image. Il y a création d'un évènement interne sous forme  généralement du positionnement d'un sémaphore booléen.
 

      LE TEMPS REEL

              Un micro-ordinateur de controle est considéré travailler  en  temps réel si la décision et la commande en réponse à un  évènement  externe sont  respectivement  prise et  générée  dans  un   laps   de   temps suffisamment court eu égard à la "constante de temps" associé à  cet évènenememt.
 
 

        Le temps  réel  peut  ètre  ainsi  caractérisé  par  l'aptitude  d'un micro-ordinateur à gérer des contraintes de temps qui sont de deux ordres :

        1- Il doit ètre  apte  à  prendre  en  compte  certains  évènements externes dans un laps de temps suffisament court.

     2- Il est susceptible de traiter et de  décider  de  la réponse  à accorder à ces évènements  dans  des temps qui  restent  eux  aussi compatibles avec le comportement évolutif du procédé controlé.

L'aptitude du système de controle à  remplir  sa mission dans le cas de systèmes complèxes dépendra  des  caractéristiques  ci-après :

        1) Vélocité  intrinsèque  du  microprocesseur  et  nous  savons qu'elle est fonction :

             - De la fréquence horloge
             - De sa capacité à traiter des mots machines aussi longs que possibles ( 16, 32 bits ,... )
             - De la puissance et de l'adaptation de son jeu d'instructions
             - De sa souplesse au changement de contexte (Interruptions)

        2) Structure  de  prise  en  compte  et  d'identification  des interruptions. C'est la structure matérielle, associée  ou  intégrée au microprocesseur, qui aura ici son importance. Cette  structure sera  évidemment  programmable, laissant  une  certaine marge  de configuration à l'initiative de l'utilisateur. Suppose tout de mème la mise en oeuvre de composants périphériques performants et bien adaptés en plus du ou des controleurs d'interruptions eux-mèmes.
 

         3) Organisation et structure du  logiciel.

      Le temps  réel  ne  désigne  donc pas  forcément  une  méthodologie particulière  de  conception. La notion de temps réel est toute relative. Ce  n'est  pas une  implémentation matérielle ou logicielle spécifique. C'est seulement mettre en place un système de controle  parfaitement adapté au procédé auquel il  est  connecté. Pour  cela, le rythme des activités du monde extérieur ne  doit  en  aucune circonstance  ètre  incommodé  par  le   rythme   de   traitement   du  microprocesseur. Ce  qui  équivaut  à  assurer  la  disponibilité  du  système en garantissant des  temps  de  réponse  acceptables  à  toute sollicitation externe.

              Si  n  processus  sont  placés  sous  le  controle  d'un  mème processeur, celui-ci doit donner l'impression à chacun des processus de lui ètre totalement dévoué pour  estimer  que  l'on  fait déja du temps réel .

              Toutes les solutions tant matérielles que logicielles adoptées dans la phase de conception sont autorisées dés lors que ces  critères  sont respectées .
 
 

              Ce  ne  sera  que  lorsque  les  contraintes  vont  devenir draconniennes avec l'augmentation en complexité des procédés pilotés que le recours à des architectures  spécifiques  tant matérielles  que logicielles vont s'avérer nécessaires. Alors le choix des  composants et leur agencement ainsi que la méthodologie  d'écriture  du  logiciel auront une importance capitale et  retiendront  toute  l'attention  du concepteur .
 
 

              La  structure  matérielle  devra  faciliter  les  interactions partie opérative - partie controle ce qui conditionnera pour une  part le temps de reponse de l'U.C . Le logiciel quant à lui  sera  organisé en fonctions , routines , modules ou  taches  structurés  de  facon  à répondre aussi rapidement que nécessaire aux sollicitations externes .
 

Les  solutions sont, en  partant  du  trivial   au  sophistiqué:

                   - le traitement en séquence
                   - La scrutation
                   - l'enchainement implicite
                   - Les activations sur interruptions
                   - L'écriture d'un moniteur spécifique
 

L'organisation en SEQUENCE

              Cette solution consiste essentiellement à  écrire  en  mémoire centrale les fonctions les unes après les autres dans un ordre préetablit. On  contraint le microprocesseur à les  balayer  toutes  en  séquence  en  recommencant indéfiniment.
 

              Cette  organisation  se  caractérise  par  le  fait  qu'on  ne rencontre nulle part dans le programme de rebouclages. Tout organigramme partiel du type de celui de la figure (   ) est interdit. Par contre,  on  pourra  fréquemment  rencontrer  des structures se rapprochant de celles des figures (    ) et (   ) . La structure  (    )   n'étant qu'un cas particulier de la structure (   ) .

      Ainsi, toute "attente active" est prohibée. Le seul  rebouclage  est celui de l'intégralité du programme sur lui méme ( fig      ).

             Signalons que cette  technique  est  utilisée  dans  certaines  applications bas de gamme des automates programmables (transposition  des schémas dits "à relais" ou "en échelle" ).

             Le traitement en  séquence ne doit  pas empécher l'utilisation des interruptions  lorsque le besoin s'en fait sentir. Les routines d'IT et le programme principal auront alors à communiquer  par l'intermédiaire de sémaphores.

TEMPS DE CYCLE

              A chaque fonction Fi est associée une durée d'exécution . Cette durée varie  selon  les  tests  et  débranchements  exécutés à l'intérieur de la fonction. On pourra retenir comme valeur de  la  durée la plus élevée. C'est celle  qui  correspond  au  cas  le  plus défavorable ( pire cas ) .

              La durée totale d'éxécution d'une boucle est le "TEMPS de CYCLE". Ce temps de réponse dans le cas le plus  défavorable  sera celui que nous confronterons chaque fois aux exigences temps  réel  du procédé. Il arrivera que l'on se base aussi sur un temps moyen.

              Nous accorderons  désormais  une  attention  particulière  aux divers temps d'exécution. Chaque fois que nous écrirons une procédure ou une fonction, nous évaluerons sa durée d'exécution .
 

La SCRUTATION

             C'est l'organisation précédente mais  dans  laquelle  on  fait nettement apparaitre le test des variables qui doivent décider ou  non de l'execution de telle ou telle fonction (organigramme type   ). C'est toujours  une  structure  sans  bouclage  hormis  le  rebouclage général
 
 

             On doit pouvoir entrer dans un  bloc  fonction  et  en  sortir aussi rapidement que possible afin de réduire au maximum le  temps  de cycle. A la limite le temps de cycle minimum est celui ou le micro-processeur ne fait que scruter les variables sans avoir à exécuter  de  fonctions .

            Ce principe de consultation en séquence de variables  booléennes pour décider d'exécuter  ou  non  telle fonction  Fi  annonce  le  principe des services attendus d'un moniteur.

            Encore une fois cela  n'empèche  pas  la  mise  en  oeuvre  de  demandes d'interruption pour le compte d'évènements spécifiques .

     ENCHAINEMENT IMPLICITE

             C'st  un  peu  une  combinaison  des  deux  modes  d'écriture précédents . Il consiste à écrire un certain nombre  de  fonctions  Fi interconnectées logiquement dans le respect d'une  chronologie  dictée par le cahier des charges .

              L'organigramme (   ) est un exemple de représentation. On  ne passe de la fonction  F1  aux fonctions avals ( F2,  F3,...)  qu'après qu'elle se soit totalement exécutée.

             Les éxécutions de  F3 ou F4 dépendent soit  des  résultats  de traitement des fonctions  amonts   F1   ou   F2  ou  de  l'etat  d'une variable externe etc ....

             Le RdP associé rappelle que nous avons affaire à une structure logicielle modélisée par un  graphe  d'état.  Le  microprocesseur  est sensé employer un  peu plus utilement son temps e  doit  en  tout  cas ètre en mesure de repondre plus rapidement aux sollicitations externes
 

ACTIVATIONS sur INTERRUPTIONS
.....

                    Dans ce cas de figure , ce sont  les  interruptions  qui  vont assurer l'essentiel du role  d'activation  des  fonctions.  Alors, plutot que d'obliger le microprocesseur  à  tester  tour  à  tour  les variables d'états des différents périphériques, on peut le  cantonner à  ne  rien  faire  ou  presque,  tant  qu'il  n'y  a  pas   demande d'interruption.

              La demande d'interruption ITi doit déclencher de  la  part  du microprocesseur un travail  bien  précis.  Il  exécute  en  fait  un sous-programme ou routine d'interruption RITi .  Au  sortir  de  cette routine , il s'en retourne en  situation  d'attente  de  la  prochaine interruption .

Tache d'arrière plan:

        Cantonner le microprocesseur à  ne  rien  faire  ,  c'est  par exemple écrire :

                  .......
                  .......
         ICI     JMP ICI  ;  boucle d'attente
                  .......

      L'interruption ITi déroute le microprocesseur dans la routine  RITi  . Le RET de cette routine le renvoyant dans la boucle à l'adresse ICI . On vérifiera , en détaillant le mécanisme de débranchement  consécutif à la demande d'IT que le retour s'effectue  bien  à  l'adresse  ICI  . Cette dernière adresse est bien celle qui a été empilée dans la  phase de sauvegarde automatique à l'occasion du débranchement.

              En fait, en dehors de toute activité  pour  le  compte  d'une interruption , on peut toujours charger le microprocesseur d'un petit travail de routine qui ne  revet aucun  caractère  d'urgence. Nous l'appelerons la tache d'arrière plan (BACKGROUND). Elle pourra  par exemple  procéder  à  des  controles  ,  tests  ou   vérifications   (  maintenance ) .
 

    ......      Il pourra aussi ètre demandé  à  cette  tache  d'arrière  plan d'éxécuter certains travaux pour le compte  d'interruptions. Alors cette  tache  prend les allures d'un  programme   principal comprenant un certain nombre de travaux éxécutés en différé.
 

Imbrications des interruptions

              Nous savons que le  débranchement  consécutif  à  une  demande d'interruption a automatiquement comme conséquence un masquage général ...... des interruptions.  Masquage  équivalent  à  l'exécution  de  l'instruction  DI  ( desable interrupt ). Dés lors , la routine d'IT est ininterruptible . Il faut par contre prendre soin de  démasquer  à  nouveau les IT juste avant exécution du RET  de  renvoi  au  programme principal ou à la tache d'arrière plan .

              Si la routine d'IT est longue, et si on ne veut pas pénaliser les autres demandes d'interruption, il faut rendre la routine  d'IT interruptible à  partir  d'un  certain  stade  de  son  exécution. L'organigramme général de la routine peut alors se présenter selon  la structure (    ) .

              Après les sauvegardes d'usage, il y a  exécution d'un  premier segment de programme jugé critique au sens ou on  considère  qu'il  ne doit pas ètre interrompu. Puis il y a exécution d'un  EI   démasquant l'ensemble des interruptions.  Dés  lors,  la  routine  peut  ètre interrompue par n'importe laquelle des demandes  d'interruption voire mème par  ITi . Il y a imbrication des demandes d'interruption.

              A  noter  cependant  qu'une  routine  d'IT  est ......  souvent   un sous-programme de durée d'exécution brève. Une routine d'IT se charge souvent d'un échange avec le monde  exterieur  (octet  à  envoyer  à destination d'une imprimante, lecture du contenu d'un port d'entrée, etc ....), opérations de très courte durée.
 

              Quand une fonction de traitement associée à  une  interruption doit prendre un certain temps, son exécution peut ètre différée. La routine d'IT se contente seulement d'alerter  le  programme  principal (en arière plan) de ce qu'il y a lieu d'exécuter telle fonction   Fi associée. Elle le fait en positionnant un  drapeau. Celui-ci est périodiquement testé par la  tache d'arrière plan qui se charge de la fonction  Fi .
 

IMPORTANCE DES INTERRUPTIONS

         Selon le degré d'urgence de l'évènement il peut s'avérer nécessaire d'obliger l'U.C à abandonner provisoirement le traitement en cours pour desservir en "priorité" la demande  externe qui  vient de se manifester. Cela ne peut se  faire que sous forme d'une demande  d'interruption . Mais si les  interruptions  jouent  un  role privilégié dans la grande majorité des systèmes temps réel,  il  faut se garder d'associer de facon systématique temps réel et interruptions.

         Si dans la majorité des cas on ne  peut  garantir  un  comportement temps réel sans recourir aux interruptons il peut s'en trouver qui se passent des interruptions tout en garantissant des réactions  de  type "temps réel " .
 
 

Une étude précise de la "charge" du microprocesseur peut suffire à apprécier les risques de non respect du temps réel .

TACHE

              La tache est le concept de base de tout système temps réel  c'est une entité  logicielle  placée  sous  controle d'un gestionnaire de taches ou "moniteur". On dit souvent de ce moniteur, que c'est un "moniteur temps réel". Un moniteur gère les allocations du processeur au niveau tache. Une tache est reconnue et parfaitement identifiée par son NOM, mais aussi par son point d'entrée  (adresse de la première instruction exécutable).

       Une tache est un module logiciel auquel on a assigné une fonction bien précise . Elle est autonome, indépendante. Elle a une signification logique. On lui affecte un niveau de priorité.

         Elle se présente comme un programme à  part  entière  et  peut  ètre  constituée d'un programme principal et de sous-programmes. Elle se décompose en une succession de travaux élémentaires.

         Une tache peut faire appel aux sous-programmes qui lui sont propres autant qu'à des sous-programmes externes. Elle peut  opérer  sur  des données qu'elle est seule à traiter (variables locales) ou sur des données mises en commun pour un ensemble de taches distinctes  (variables globales).

         La commande d'un processus va nécéssiter l'écriture de n taches qui devront coopérer pour satisfaire les objectifs assignés au système  de controle. Cette coopération de taches selon une logique donnée pour le controle d'un procédé constitue une "APPLICATION". Cet  ensemble de taches concourant à assumer les fonctions élémentaires pour le compte d'une mème application est une  "tribu".
 

Transition interne de fonctionnement.

              Chaque fois que le moniteur retire le processeur à  une  tache pour l'attribuer à une autre, il y a transition   interne   de fonctionnement .  Une  transition  de  fonctionnement  va  exiger  du moniteur  qu'il  prenne  un  certain  nombre  de  précautions .   sur lesquelles nous reviendrons en détail plus loin (sauvegarde "contexte").

         Bien sur, le  moniteur  ne  peut  exécuter  une  transition   de fonctionnement que si  il  est  justement  en  train  de  disposer  du processeur. Aussi s'agirat'il  d'examiner  attentivement  toutes  les circonstances qui amènent le moniteur  à  reprendre  le  controle, donc à disposer du processeur afin d'exécuter son propre code  lui permettant de prendre ce type de décision.

COMMUNICATION

         Les taches sont le plus souvent  conditionnées  les  unes  aux  autres,  elles  doivent  s'échanger  des  messages, se synchroniser etc...  c'est  la   "COMMUNICATION".

      Si nous nous référons à  la tache de sortie buffer sur imprimante, nous notons que:

         1 - la tache est activée sur demande d'une autre tache

      2 - Elle ne peut s'exécuter de facon satisfaisante que  si  on  lui  fournit un certain nombre d'indications (adresse de la première cellule du buffer, taille du buffer,....). C'est le  passage  de paramètres.

      Il y a eu communication entre taches. Une tache Ti  a demandé la mise en service d'une tache  Tj  en lui fournissant les informations essentielles à son bon déroulement.
 

Tache matérielle / tache logicielle

         Une tache matérielle ou tache immédiate est une tache  activée  par l'ordonnanceur  consécutivement a une demande  d'interruption. C'est  l'implication de cette interruption  qui  confère  à  la  tache  son caractère matériel.

         Une tache matérielle s'exécute à partir de son point d'entrée et se termine par un retour au moniteur.

         Elle ne peut se mettre en attente sur sémaphore  et  ne  peut ètre interrompue  que  par  une  tache  elle  mème  matérielle  mais  plus prioritaire.

        Les  caractérisiques  d'une  tache  matérielle  sont  relativement restrictives,  sa fonction  est  le  plus  souvent  rudimentaire  et n'assure généralement que le stricte minimum  pour  redonner aussi tot que possible la main au moniteur. Sa durée d'exécution est donc généralement très courte.

       Une tache logicielle ou tache différée est activée par le  moniteur consécutivement à une décision  de  l'ordonnanceur.  Elle  est  dite différée dans la mesure ou son activation  est  généralement  demandée  par une autre tache (souvent matérielle).

         Nous avons précisé qu'une tache matérielle était  le  plus  souvent une tache de durée d'exécution brève ce qui justifie déja qu'on puisse lui accorder un niveau de priorité elevé.  Une  tache  logicielle  en cours d'exécution se verra  inévitablement  retirer  l'utilisation  du processeur au profit de la tache matérielle, le temps  pour  celle-ci d'effectuer un minimum de  choses  (  strictement  essentielles  à  ce  niveau ) entre  autres  celle  de  demander  l'activation  d'une  tache  logicielle donnée qui elle prendra le temps nécessaire pour poursuivre  le travail. ( retour au moniteur ).
 

ETATS D'UNE TACHE

              Le graphe (   ) rappele les differents etats d'une tache. Les arcs signalent les possibilités de transitions d'état. Ce sont :
                   - état exécution
                   - état bloqué
                   - état éligible
                   - état endormi
                   - état inexistant

Etat EXECUTION

              Une tache est dite en exécution si son code est effectivement exécuté  par  le  processeur .  Celui-ci  lui  a   été   alloué   par  l'ordonnanceur.

Etat BLOQUE

              En cours d'exécution, une tache peut ètre amenée  à  demander l'utilisation d'une ressource qui n'est pas libre. Si la poursuite du programme de cette tache dépend essentiellement de cette libération, elle sera  mise  en  attente.  Elle  passe  alors  sur      décision du moniteur à  l'état bloqué.  C'est  une  tache  empéchée ,  empéchée au sens ou la non disponibilité de la ressource l'empèche  de poursuivre son travail.
 

         Un cas fréquent de passage  à  L'état  bloqué  est  celui  ou  pour poursuivre son exécution, une tache doit  attendre  l'occurence  d'un évènement. Celui se manifeste souvent  d'ailleurs  sous  forme  d'une interruption.  Pendant  ce  temps  d'attente  le  processeur  a  été attribué à  une autre tache.
 
 

              Dés qu'une tache Ti est passée à   l'état bloqué par le moniteur,  celui-ci alloue le processeur à   la tache la plus prioritaire en attente  ( état éligible ).

Etat éligible

              La libération du processeur autorise le moniteur à l'allouer à une autre tache. Celle-ci en avait préalablement fait  la  demande. Elle était en état éligible. Une tache en état éligible est  prète  à utiliser le processeur aussitot  que  possible  tandis  que  rien  par       ailleurs ne s'oppose à   l'exécution de son code.

Etat ENDORMI

              C'est la tache qui n'a rien à faire. Pour l'instant on ne lui  demande rien. elle est endormie.  Notons ce qui distingue cet état de l'état éligible. Une  tache en  état éligible a quelque chose à faire, il lui  manque  seulement  de  pouvoir disposer du C.P.U.

         Le réveil d'une tache  Tj  endormie  peut  ètre  illustrée  par  le réseau partiel (    ). La tache  Ti  décide d'activer  Tj   afin  que celle-ci exécute un certain travail. Elle  le  fera  en  marquant  la  place  ( sémaphore booléen ). Tj passera alors de  l'état  endormi  à  l'état éligible.

Notons enfin qu'une tache  T  peut demander son propre endormissement pour un certain temps. C'est une délicatesse de la part de  T  vis à vis des autres taches en attente. L'exécution du code de  T  n'ayant pas de caractère d'urgence c'est un mécanisme qui permet au processeur de n'exécuter que du code efficace.
 

Etat INEXISTANT

      Cet état est la pour rappeler seulement que les autres  taches se trouvant dans l'un des quatre etats examines  jusqu'ici  ont  ete portes a la connaissance du moniteur. Pour celui-ci, elles  sont  parfaitement identifiees.

         La tache non crée peut ètre une  tache  dont  le  code  d'exécution existe déja et peut mème ètre présent en mémoire centrale  du  système mais reste pour le moment totalement ignorée du moniteur. Celui-ci n'a pour l'instant aucune responsabilité de gestion à son égard.
 

PRIORITES

              A  l'instant  ou  le  moniteur  s'apprète   à   attribuer   le   processeur, il peut y avoir plusieurs taches en attente d'utilisation   de ce processeur. Le moniteur ne peut faire son  choix  qu'en  tenant   compte d'une hiérarchie qui a été préalablement  établie en attribuant  à   chaque tache un niveau de priorité. Après éxamen des priorités,  le   moniteur  alloue  le  processeur  à  la  tache  la  plus   prioritaire   (franchissement de la transition t1).

              La transition  t2  signale la possibilité  pour une  tache  de passer directement de l'état exécution a l'état éligible sur  décision du moniteur. Dans quelles conditions cela peut-il se  produire  alors que la tache en exécution est justement la plus prioritaire ?

      Deux possibilités :

              Une   tache   bloquée   de  plus   haute  priorité  vient d'ètre  débloquée la condition d'empèchement de poursuite de son  code venant  de disparaitre.

              Une  tache  endormie  de  plus  forte  priorité  vient  d'ètre réveillée.

SEMAPHORE

              Dans son acception la plus étendue, et c'est DIJKSTRA  qui  a  proposé cette formulation, un sémaphore s est constitué :

              - d'une variable entière  S(s)
              - d'une file d'attente F(s)

Nous reviendrons ultèrieurement sur cette notion à propos des primitives de  DIJKSTRA.
 
 

Sémaphore BOOLEEN

         Un sémaphore  s  est dit binaire ou booléen si sa valeur S(s) est bornée à 1. La modélisation d'un sémaphore booléen prendra la  forme  d'une  place ordinaire. C'est un drapeau ( flag ).
 

Primitives  P  et  V  de DIJKSTRA

        La valeur S(s) ne peut ètre que supèrieure ou égale à zéro. Elle est parfaitement modélisable  par une place ( figure  ) .  Le  nombre  de jetons dans la place est égal à  S.

      Deux primitives notées P(S) et V(S) peuvent opérer sur la valeur de S.
 

         La primitive  P(s) a pour effet l'exécution de l'opération

              S = S - 1   ( si  S > 0 )
 

         C'est le franchissement de la transition notée aussi P(s)  donc  le retrait d'un jeton de la place S. Cette opération n'est exécut[e que si S est supèrieure à  0.

         La primitive  V(s) a l'effet dual soit l'exécution de l'opération :

              S = S + 1

         C'est un rajout de jeton en place S par  le  franchissement  de  la transition V(s).

NOTA.BENE :

         Si l'exécution  de  la  primitive   P   ramène  une  valeur  de   S  négative (et ce ne peut ètre que -1),  il  faut  conserver  à  S  sa  valeur avant exécution de la primitive soit S = 0.

         Toute opération P(s) ou V(s) doit ètre une opération indivisible. Nous en donnerons plus loin la justification.

Si on veut se donner des repères mnémotechniques on pourra associer à

     P(S)  : Puis-je ?
     V(S)  : Vas-y
 

FILE D'ATTENTE

         La tache qui tente sans succés une opération P(s) ne  doit pas poursuivre l'exécution de son code mais rester sur le test de P(s) tant que ce test n'est pas exécuté avec succés. Elle est mise en attente sur le sémaphore  s.

Nom d'un sémaphore

         Une  opération  P(sj)  ou  V(sj)  est  appliquée  à  un sémaphore parfaitement identifié de nom sj . Chaque fois que  l'on  manipule  un sémaphore, il faut le désigner clairement dans la mesure ou  en  crée généralement plusieurs.

         (A l'usage, le terme de sémaphore tend à désigner uniquement la variable  S  seule. )

REPRESENTATION MACHINE

         A la place  S  on associe  une cellule mémoire. La taille de cette cellule pourra recouvrir un ou plusieurs  mots mémoire  selon la borne supèrieure de  S.

                          A un sémaphore ordinaire peut ètre associé un seul bit dans un mot mémoire (une simple bascule dans un système logique). Il pourra s'avérer  plus  pratique  cependant de  réserver   plutot la  totalité  d'un  mot. Cela  dépendra  du  jeu  d'instruction  du microprocesseur et tout particulièrement de la disponibilité d'instructions  d'accés  direct  au  bit ( Z80, 68000,... ). L'instruction TEST AND SET du 68000 est par exemple tout à fait indiquée.

Le DESCRIPTEUR  de  TACHE:

Le moniteur temps réel ne peut assurer convenablement sa fonction de gestion des taches matérielles et logicielles que dans la mesure ou il dispose à tout instant d'un certain nombre d'indications ou d'informations sur les taches sous sa dépendance et qui peuvent ètre pour une tache:

    - Le point d'entrée        (adresse de début de son code)
    - Le niveau de priorité
    - L'état de la tache       (empéchée, endormie, eligible,....)
    - L'adresse de retour    (pour une tache précédemment interrompue)
    - L'adresse du segment de mémoire ou à été sauvegardé son contexte
    - Etc .......

Ces informations peuvent ètre rassemblées dans un DESCRIPTEUR de tache. C'est une table de données à un emplacement mémoire qui lui aura été spécialement réservé.
 

SYNCHRONISATION

         Le RDP (      )  modélise une synchronisation entre deux taches T1 et T2. T2 ne doit pas poursuivre l'exécution de son code au dela de la transition  T8  tant que  T1  n'a pas franchi de son coté la transition  T3. Pour cela, un sémaphore booléen est mis en place. Il est sous le controle des primitives  P  et  V  exécutées respectivement par les taches  T2  et  T1.

    Deux cas de figures :

- La tache  T2  est en avance et elle doit attendre en  P7 le marquage de  S  pour poursuivre
- La tache  T2  est en retard ( S marquée avant p  ), rendue au stade du marquage de  P7, elle poursuit exécution en séquence  en place  8.

    Remarques :

- Le franchissement de  T8  provoque bien une remise à zéro de S  ( S = S - 1 ). Caractéristique de la primitive  P.

- Ce réseau partiel n'est pas SAUF. La place S  n'est pas bornée. Il peut y avoir accumulation de jetons en  S  si T2 prend  trop de retard par rapport à  T1.
 

SECTIONS CRITIQUES

Dans le cas du  lecteur  de  ruban,  les  fonctions  "sortie imprimante" IMPRUB et "impression message" IMPMESS ne doivent  jamais s'exécuter simultanément pour des raisons évidentes  de  cohérence  du  texte. Nous dirons de ces deux segments de programme  qu'ils  sont  " critiques ".

             L'imprimante est déclarée " ressource non  partageable ".

      Généralisons :

      Deux segments de code A et B, représentés par les places P1 et P2  du RdP (   ) sont déclarés sections critiques si il apparait ou  qu'il a été décidé que leur exécution ne pouvait ou ne devait en  aucun  cas s'effectuer simultanément. Cette notion se généralise à n segments . Nous dirons encore de ces segments qu'ils s'excluent mutuellement. Si il y en a un en cours d'exécution il doit ètre le seul.

Exclusion mutuelle

              Mettons en place dans le cas de la figure (     )  le  mécanisme qui assurera cette exclusion  mutuelle .  Il  suffit  (  figure     ) d'associer à la ressource  non  partageable  imprimante  un  sémaphore booléen de nom IMP. C'est un sémaphore d'occupation rappelant que  la ressource n'est disponible que si S(IMP) > 0.
 
 

      Le marquage simultané des places P  et P   est désormais impossible.

              Chacune des taches doit maintenant exécuter la primitive  P(S) avant son entrée en section critique. Si la  valeur  ramenée  par  ce test est "1" la tache peut  poursuivre  après  avoir  pris  soin  de décrémenter  S ( retrait du jeton ).

              Au  sortir  de  la  section  critique ,  elle  effectuera  la  primitive duale  V(S) par une incrémentation de  S  soit  le  marquage à nouveau de la place  P.

      Discussion :

              Au plan logiciel nous réservons en mémoire le sémaphore  IMP  Pour la tache  T1, le principe du test de ce sémaphore  avant  entrée en section critique peut s'écrire, sans précautions  particulières  et de  facon intentionnellement maladroite.

-
 
 

              IMPRUB                                       IMPMESS
             .......                                                     .......
             .......                                                      .......
      BOUCL1  LD A,(IMP)      ; (IMP)--->A                    .......
              DCR A                   ;  A = A - 1
              JN BOUCL1            ;  saut si non zéro                P(IMP)
              XRA A                    ;  0--->A
              LD S,A                   ;  0--->IMP                     .......
 

 début section critique T1                       <section

             .......                                       critique>
             .......                                     .......
 

 fin section critique T1                          .......

              LD A,(IMP)
              INC A                                         V(IMP)
              LD (IMP),A   ;  1--->IMP

              On écrira sensiblement la mème chose pour  T2, il  suffit  de remplacer dans ce segment de programme  T1   par   T2  et  BOUCL1  par  BOUCL2.

      Rappelons seulement     que nous nous situons dans le cas de figure ou  nous estimons ne pas  savoir  dans  l'ensemble  du  logiciel  implante quelle peut ètre l'instruction qui va ètre  executée  apres  celle  en cours d'execution.

         Une imbrication particulière de  demandes  d'interruptions ou  tout simplement un mode de fonctionnement en temps partage  peut  engendrer  le scénario  suivant :

         IMPRUB s'apprète à entrer  dans  sa  section  critique .  Elle  va chercher le contenu de la cellule d'adresse  IMP  que  nous  supposons pour l'heure égale à   "1" .  Elle  décrémente  le  contenu  de  A, n'effectue pas le saut  en  BOUCL1  et  en  arrive  à  l'exécution  de l'instruction  XRA A.
......

        Survient une demande d'interruption,  qui  peut  d'ailleurs  ètre celle de l'horloge temps partagé. Il y a changement  de  contexte  et  c'est maintenant la  tache  IMPMESS  qui  dispose   du  CPU  pendant  20 ms par exemple. Si cette tache  s'apprète  elle  aussi  à entrer dans sa section critique elle exécute de son coté la  primitive  P( IMP ) alors que  IMP vaut toujours  "1".  IMPMESS  entre  donc  sans encombres  dans  sa  section  critique  et  le  mécanisme d'exclusion mutuelle mis en place n'a pas joué son role (marquage équivalent  ).
 

        C'est la raison qui veut que l'exécution de toute primitive P(   )  ou V(   ) soit indivisible. Une fois dans  la primitive ,  celle-ci  doit s'exécuter jusqu'au bout sans qu'il soit possibe de  l'interrompre . On satisfait cette contrainte  en  vérouillant les  interruptions  le  temps d'execution de la primitive.
 

         Mais la encore on ne peut pas considérer que toutes les précautions sont bien prises.

        Imaginons que l'on insère dans IMPRUB l'instruction DI juste avant l'étiquette  BOUCL1  et  EI  aussitot  aprés l'istruction  LD  (IMP),A  encadrant  ainsi le segment  de  code  par  les deux instructions  de verouillage  et deverouillage des IT. L'illustration  (    )  met  en evidence un  risque de  blocage  irreversible    IMPRUB  est  dans  sa  primitive P() tandis que IMP = 0 .  La  tentative  de  sortie  de  la  primitive est désespérée puisque les IT étant vérouillées aucune autre tache ne peut venir a la rescousse en se chargeant de ramener IMP égal

      à "1".
 
 

         C'est le blocage de l'ensemble  du  système  (  cauchemar  de  tout informaticien ) dont  on  ne  sortira  que  par  une  réinitialisation  générale  ( RESET ??? )
 

PRIMITIVE

         L'écriture du segment qui teste la valeur du sémaphore dans le corps mème de la tache est maladroite. Le sémaphore est une entité  partagée. Elle est variable commune à un ensemble de taches mais n'appartient à aucune d'entre elles. Elle doit avoir sa propre autonomie.

         Lorsqu'on crée un sémaphore, il semble préférable de lui associer sa propre procédure de gestion. Ainsi, toute tache désirant accéder à ce sémaphore ne pourra le faire qu'en s'adressant qu'à sa procédure  de gestion. Cela pourra ètre sous forme d'un appel à sous-programme avec passage de paramètres pour indiquer par exemple s'il s'agit d'une demande de type  P  ou de type  V .

         En retour, le gestionnaire de sémaphores indique, par une convention qui reste à définir (positionnement d'un indicateur) si la demande a été satisfaite.
 

Sécurité

         Le gestionnaire pourra procéder à certaines vérifications. Ainsi, un sémaphore que l'on sait borné à  "1" pourra ètre la cause d'une procédure d'urgence (déroutement - trap) si il y a tentative de la part d'un tache d'incrémentation au dela de  1. La tache fautive court le risque d'un ABORT.

     Ce  n'est  que  maintenant  que  cette  notion   de  "PRIMITIVE" prend réellement tout son sens. C'est un segment de  code qui a toute son autonomie et à la limite, tous  les  attributs  d'une  tache.

        Les taches IMPRU et IMPMESS pourront maintenant se presenter  sous les formes ci-aprés :

    Ressource non partageable

         RdP (        ), la disponibilité  d'une ressource non partageable est modélisée par la place  P7. Si T1, aprés une primitive  P(S) obtient la  réservation  de la  ressource, T2  sera  mise en attente lorsqu'elle effectuera de son coté une demande de réservation. Elle attendra la restitution  du jeton  dans  p7 ( primitive  V(S) exécutée par T1 ) avant d'accéder à son tour à la ressource.

         Ce mécanisme d'exclusion mutuelle sur une ressource non partageable peut évidemment s'éttendre à n taches parallèles.

         Au plan logiciel il  faudra  veiller à ce que les segments de codes  d'exécution  des  primitives  P  et  V  soient indivisibles (peut nécessiter le masquage général des  IT par exemple pour les microcontroleurs qui ne disposeraient pas d'instructions spécifiques du type TEST and SET    -  68000).
 

Schéma    PRODUCTEUR - CONSOMMATEUR

         Figure (    ), une tache T1 calcule une valeur ou une suite de valeurs ou encore produit un message qui doit ètre transmis au monde extérieur. Cette transmission est placée sous la responsabilité  de la tache  T2.

         Les deux taches doivent communiquer. Cette communication se fera par l'intermédiaire

         - d'un tampon  C  servant de contenant intermédiaire de stockage.
         - d'un mécanisme de synchronisations.

    Le tampon  C  est une ressource commune aux taches  T1  et  T2. Nous lui associons un sémaphore de disponobilité  c (c=1 équivaut à tampon vide).

    Après que  T1  ait déposé la valeur ou le message dans C, il lui faut demander l'activation de  T2. Elle le fera en exécutant la primitive  V(a) sur le sémaphore d'activation  a.

    Le RdP  (    ) résume le protocole de synchronisation entre ces deux taches. La place  p7  symbolise une activité complémentaire de  t2 (exemple: réinitialisation des périphériques, etc....). La place p2 symbolise la phase d'attente sur le sémaphore  c de t1.

    En effet le temps de production peut ètre beaucoup plus bref que le temps de transmission. On observe bien que le rythme de production ne peut ètre supérieure au rythme de la consommation et vice versa. Par contre, les temps de production et de consommation sont tout à fait quelconques.
 
 

    Ce schéma de base PRODUCTEUR - CONSOMMATEUR est, on s'en doute, courant dans tout système informatique mais aussi partout ou il  y a nécéssité de synchroniser production et consommation (atelier de fabrication, chaines de montage, etc....... ).

    Réservations mémoire :

         Les réservations sont :

              - Un tampon de  n  cellules mémoire
              - Un mot mémoire pour le sémaphore  c
              - Un mot mémoire pour le sémaphore  a

    Ces derniers peuvent si nécéssaire se liniter à des bits.
    On aura remarqué au préalable que le réseau est SAUF.

         La modélisation de base du schéma producteur - consommateur est  donnée figure (   ).

         La tache  T1  produit un message dans le buffer  B. La tache T2 consomme ce message ( lecture de B ). Le consommateur T2 ne peut consommer que si le producteur T1 a produit. Le producteur ne peut déposer un nouveau message dans  B  que si il ya bien eu consommation  du message précédent.

         Cette synchronisation est assurée par la gestion des sémaphores booléens des places  4  et  5. La synchronisation des deux taches et le marquage initial précisé sur la figure fait qu'il n'est pas nécessaire de prévoir un sémaphore d'exclusion mutuelle sur  B.

         p1 : place de synchronisation. T1 attend la libération de B.
         p2 : représentation de la phase de génération du message.
         p3 : phase de dépot du message dans  B.

    Réseau 13, producteur et consommateur communiquent par l'intermédiaire d'un TAMPON constitué de trois buffers B1, B2, B3. Les contraintes sont maintenant les suivantes :

         - Le producteur ne peut écrire que si il y a au moins un buffer de libre.
         - Ecriture et lecture dans le tampon s'excluent mutuellement.
         - Le consommateur doit étre prévenu de la présence du ou des messages dans  T.

    Seul le sémaphore d'exclusion mutuelle  S  est booléen. On vérifiera que les places  5  et  6  sont bornées (bornes = 3).

    Noter le marquage initial :  M( p5 ) = 3 ;   M( p6 ) = 0 ;    M( p11 ) = 1

    A hauteur de la transition 1 a été rappelée la primitive de réservation d'un buffer exécutée par t1 . La primitive  de restitution du buffer aprés lecture est exécutée par t2 à hauteur de la transition   t6 soit  V(s1).

BLOCAGE ( deadlock )

         RdP (   ), deux taches  T1  et T2 procédent périodiquement à la réservation de deux ressources R1 et R2 non partageables. Elles les réservent toutefois en séquence dans un ordre différent. T1 réserve d'abord  R1 tandis que T2 réserve en premier R2.

            Si nous nous intéressons exclusivement à l'une ou l'autre des deux taches, Nous vérifions qu'il n'y a pas d'entrave aux exécutions séparées de  T1 ou T2. Par contre, si T1 en est rendue à l'étape  3 et  que  dans  ce  mème laps de temps T2 exécute sa primitive P(s2) à partir de la place marquée p7, il y a interblocage.  Ni l'une ni l'autre des deux taches ne peut alors progresser.

Solution :

         Le RdP (      ) ne présente pas, dans la procédure de réservation modélisée, de risque de blocage.
 

Problème des PHILOSOPHES

         Une table de quatre couverts est dréssée. Quatre philosophes sont attendus. Ils ont choisi de se goinfrer de spaghettis.

         Un philosophe en présence de spaghettis insaisissables à l'aide d'une seule fourchette ne s'énerve pas inutilement, il emprunte tout simplement la fourchette du voisin si celle-ci n'est pas déja utilisée. Par ailleurs, il mange pendant 10 mn, redépose les deux fourchettes et se met à révasser pendant 5 mn. Au bout de ce temps, il se remet en attente de la libération des deux fourchettes immédiatement accessibles.

         Ce mécanisme, pour un philosophe est modélisé par le réseau  partiel (   ).

         p3 :       philosophe en train de manger  (durée 10 mn)
         p4 :       temps de rèverie (durée  5 mn)
         p5 :       philosophe en attente de libération des fourchettes
         p1, p2 : disponibilité des ressources
 

    Le réseau  (       )  modélise l'activité des quatre philosophes. On peut montrer alors qu'en fonction des ordres et des instants d'arrivée de chacun des convives à la table, il y a risque pour deux d'entre eux de rester sur leur faim.
 

Une implémentation partielle du réseau est proposé figure (      ). Une fois de plus, cette matérialisation est une transposition directe du RdP en logique cellulaire.
 

Traitement PIPE-LINE

         Considérons la chaine de traitement (    ). Chaque module  Mi est constitué :

              - d'un tampon d'entrée  Ei
              - d'un tampon de sortie Si
              - d'un module de traitement  Ti
              - d'un module de transfert &i

         La fonction du logiciel qui supervise l'ensemble de la chaine de traitement est modélisée par le réseau  (    ).

         On voit que  Ti  ne doit ètre activée que si il y a bien une donnée à traiter dans  Ei  "ET"  que le tampon de sortie  Si est vide.

         &i ne doit exécuter son transfert du contenu du tampon de sortie Si dans le tampon d'entrée du module suivant que si le traitement  Ti  est bien terminé "ET" que Ei+1 est bien vide.

         Les places  Eip  sont des places de demande d'activation de taches, les places  Sip des demandes d'activation de transfert.
 

         On pourra vérifier que les temps de traitements et de transfert peuvent ètre tout à fait quelconques, il n'y a pas de risque de recouvrement. Par contre à un instant donné  t , plusieurs fonctions peuvent ètre simultanément en activité.