Concept: Simultanéité
Le terme d'accès concurrent désigne la tendance qu'ont les événements à se produire au même moment sur un système. Traiter les problèmes d'accès concurrent au sein des systèmes logiciels implique généralement de considérer deux aspects importants : être en mesure de détecter et de réagir aux événements externes se produisant de manière aléatoire et s'assurer qu'une réponse est apportée à ces événements dans un intervalle de temps requis minimal.
Relations
Description principale
Remarque : le présent document traite de la question de l'accès concurrent de manière générale, ce problème pouvant s'appliquer à n'importe quel système. Toutefois, l'accès concurrent revêt une importance particulière pour les systèmes devant réagir aux événements extérieurs en temps réel et qui doivent souvent respecter des échéances très serrées. Afin de répondre aux contraintes particulières de cette classe de système, le processus Rational Unified Process (RUP) dispose d'extensions système en temps réel (réactives). Pour plus d'informations sur ce sujet, voir Systèmes en temps réel.

Qu'est-ce que l'accès concurrent ?

Le terme d'accès concurrent désigne la tendance qu'ont les événements à se produire au même moment sur un système. L'accès concurrent est bien entendu un phénomène naturel. Dans le monde réel, de nombreux événements surviennent simultanément, ceci à tout moment. Lorsque nous concevons des logiciels de surveillance et de contrôle des systèmes physiques, nous devons composer naturellement avec ces accès concurrents.

Traiter les problèmes d'accès concurrent au sein des systèmes logiciels implique généralement de considérer deux aspects importants : être en mesure de détecter et de réagir aux événements externes se produisant de manière aléatoire et s'assurer qu'une réponse est apportée à ces événements dans un intervalle de temps requis minimal.

Si chaque activité concurrente évoluait de manière indépendante, vraiment parallèle, ceci s'avérerait relativement simple : il suffirait simplement de créer des programmes distincts pour traiter chaque activité. Concevoir des systèmes concurrents soulève de nombreux défis, qui découlent principalement des interactions entre des activités concurrentes. Un certain degré de coordination est nécessaire lorsque des activités concurrentes interagissent.

Diagramme détaillé dans le contenu.

Figure 1 :  exemple de concurrence : les activités parallèles n'interagissant pas rencontrent des problèmes de concurrence simples. C'est lorsque les activités parallèles interagissent ou partagent les mêmes ressources que les problèmes de concurrence prennent de l'ampleur.

La circulation automobile fournit une analogie pratique. Les flux parallèles de véhicules circulant sur des routes différentes et ayant peu d'interactions entraînent peu de problèmes. Les flux parallèles circulant sur des voies adjacentes requièrent un certain niveau de coordination pour que les interactions soient sûres, mais les interactions deviennent beaucoup plus problématiques au niveau des intersections, qui nécessitent une coordination soigneuse.

Pourquoi nous penchons-nous sur la question des accès concurrents ?

Certaines des forces qui président à l'apparition d'accès concurrents sont externes. Cela signifie qu'elles sont imposées par les exigences de l'environnement. Sur les systèmes physiques, de nombreux événements se produisent simultanément et doivent être traités en « temps réel » par le logiciel. Pour ce faire, de nombreux logiciels en temps réel doivent être « réactifs ». Ils doivent répondre aux événements générés en externe pouvant survenir de manière aléatoire, dans n'importe quel ordre, ou les deux.

Concevoir un programme procédural classique permettant de gérer ces situations est extrêmement complexe. Il peut s'avérer beaucoup plus simple de partitionner le système en différents éléments logiciels concurrents destinés à traiter chacun de ces événements. Notez bien ici la formule « il peut s'avérer », car la complexité varie également en fonction du niveau d'interaction entre les événements.

Les accès concurrents peuvent également avoir une origine interne [LEA97]. Effectuer des tâches en parallèle peut accélérer de manière significative le travail de calcul d'un système dans les cas où plusieurs UC sont disponibles. Même dans le cas d'un processeur unique, le fonctionnement multitâche peut accélérer considérablement le traitement en empêchant une activité d'en bloquer une autre en attendant des E/S, par exemple. L'initialisation d'un système est un exemple type de situation dans laquelle survient ce type de problème. Un système compte souvent de nombreux composants, qui nécessitent tous un certain délai pour être opérationnels. Effectuer ces opérations de manière séquentielle peut s'avérer d'une lenteur exaspérante.

Le contrôle du système peut également être facilité par l'accès concurrent. Une fonction peut par exemple être démarrée, arrêtée, ou même influencée au milieu du flux par d'autres fonctions concurrentes, résultat extrêmement difficile à obtenir sans composants concurrents.

Pourquoi les logiciels concurrents sont-ils si difficiles à appréhender ?

Considérant tous les avantages offerts, pourquoi ne recourons-nous pas de manière systématique à la programmation concurrente ?

La plupart des ordinateurs et des langages de programmation sont par essence séquentiels. Une procédure ou un processeur exécute une instruction à la fois. Dans un processeur séquentiel unique, l'illusion d'accès concurrent doit être créée en entrelaçant l'exécution des différentes tâches. La difficulté ne réside pas tant dans les manières d'y parvenir que dans le fait de déterminer quand et comment entrelacer des segments de programme susceptibles d'interagir les uns avec les autres.

Bien que parvenir à un accès concurrent soit aisé avec plusieurs processeurs, les interactions n'en sont que plus complexes. Se pose dans un premier temps la question de la communication entre des tâches s'exécutant sur différents processeurs. En règle générale, plusieurs couches logicielles sont concernées, ce qui accroît la complexité ainsi que le temps système de synchronisation. Le déterminisme est réduit dans les systèmes multi-processeurs, les horloges et les rythmes pouvant différer et les composants étant susceptibles de tomber en panne de manière indépendante.

Pour finir, les systèmes concurrents peuvent être plus difficiles à comprendre car ils ne disposent pas d'un état système global explicite. L'état d'un système concurrent correspond à l'agrégat des états de ses composants.

Exemple de système concurrent en temps réel : un système d'ascenseur

En guise d'exemple pour illustrer les concepts qui seront abordés, nous utiliserons un système d'ascenseur. Il s'agit plus précisément d'un système informatique destiné à commander un groupe d'ascenseurs installés dans un bâtiment. Il peut bien évidemment se produire de nombreux événements concurrents au sein d'un groupe d'ascenseurs ou même aucun événement du tout ! A n'importe quel moment, une personne se trouvant à n'importe quel étage peut appeler un ascenseur, tandis que d'autres demandes sont en attente. Certains des ascenseurs peuvent être inutilisés tandis que d'autres transportent des personnes ou s'apprêtent à répondre à un appel, ou les deux. Les portes doivent s'ouvrir et se refermer au bon moment. Des personnes peuvent être en train de bloquer les portes, ou d'appuyer sur les boutons d'ouverture et de fermeture des portes, ou de sélectionner des étages, puis changer d'avis. Les affichages doivent être mis à jour, les moteurs contrôlés, etc., tout ceci sous la surveillance du système de commande de l'ascenseur. Dans l'ensemble, ce système constitue un bon modèle d'étude des concepts liés à l'accès concurrent, et un domaine avec lequel nous partageons, dans une certaine mesure, une compréhension et un vocabulaire de travail communs.


Diagramme détaillé dans le contenu.
Figure 2 :   scénario portant sur deux ascenseurs et cinq passagers potentiels répartis sur un espace de 11 étages.

Lorsque les passagers potentiels transmettent des requêtes au système à des moments différents, ce dernier essaie de fournir le meilleur service global en choisissant les ascenseurs qui vont répondre aux appels en fonction de leur état actuel et de leur temps de réponse prévu. Par exemple, lorsque le premier passager potentiel, Andy, appelle un ascenseur afin de descendre et que les deux ascenseurs sont inutilisés, c'est l'ascenseur le plus proche, l'ascenseur 2, qui répond, bien qu'il doive d'abord remonter pour rejoindre Andy. D'un autre côté, lorsque Bob, le second passager potentiel, appelle un ascenseur quelques instants plus tard afin de monter, c'est l'ascenseur 1, plus éloigné, qui répond, car il est établi que l'ascenseur 2 devra descendre jusqu'à un étage qui n'est pas pas encore déterminé avant de pouvoir répondre à une demande de montée venant d'en-dessous.

L'accès concurrent en tant que stratégie de simplification

Si le système d'ascenseur ne comptait qu'un ascenseur et que ce dernier ne devait prendre en charge qu'une personne à la fois, on pourrait penser qu'il serait gérable à l'aide d'un programme séquentiel ordinaire. Même dans ce cas « simple », le programme nécessiterait de nombreuses branches pour pouvoir accepter différentes conditions. Par exemple, si la personne n'emprunte pas l'ascenseur et ne sélectionne pas d'étage, il conviendrait de réinitialiser cet ascenseur afin de lui permettre de répondre à un autre appel.

L'exigence normale qui consiste à gérer des appels provenant de plusieurs passagers potentiels et des requêtes émanant de plusieurs passagers illustre les forces externes présidant à l'apparition d'appels concurrents précédemment évoquées. Etant donné que les passagers potentiels eux-mêmes mènent des vies concurrentes, ils effectuent des demandes auprès de l'ascenseur à des moments apparemment aléatoires, quel que soit l'état de l'ascenseur. Il est extrêmement difficile de concevoir un programme séquentiel en mesure de répondre n'importe quand à n'importe lequel de ces événements externes tout en continuant à guider l'ascenseur sur la base des décisions antérieures.

Abstraction de l'accès concurrent

Pour concevoir des systèmes concurrents de manière efficace, il convient de s'interroger sur le rôle des accès concurrents dans le système, et pour ce faire nous avons besoin d'abstractions de l'accès concurrent lui-même.

Les blocs de génération fondamentaux des systèmes concurrents sont des « activités », qui fonctionnent de manière plus ou moins indépendante les unes des autres. Les « timethreads » de Buhr constituent une abstraction graphique pratique pour visualiser mentalement ces activités. [BUH96] Le scénario d'ascenseur de la Figure 3 a justement recours à une forme de timethread. Chaque activité est représentée sous la forme d'une ligne le long de laquelle l'activité se déplace. Les gros points représentent les points où une activité démarre ou attend qu'un événement se produise avant de continuer sa route. Une activité peut déclencher la reprise d'une autre, ce qui est représenté dans la notation du timethread par un point de contact au niveau de l'emplacement d'attente de l'autre timethread.

Diagramme détaillé dans le contenu.

Figure 3 :   visualisation d'unités d'exécution

Les blocs de génération élémentaires des logiciels sont les procédures et les structures de données, mais ces dernières ne suffisent pas à elles-seules à réfléchir à l'accès concurrent. Lorsqu'un processeur exécute une procédure, il suit un chemin précis qui dépend des conditions à cet instant. Ce chemin peut être appelé « chemin d'exécution » ou « chemin de commande ». Ce chemin de commande peut emprunter différentes branches ou boucles en fonction des conditions existant à cet instant et, dans les systèmes en temps réel, peut se mettre en pause pendant une durée déterminée ou attendre une heure planifiée pour reprendre.

Du point de vue du concepteur du programme, l'unité d'exécution est contrôlée par la logique du programme et planifiée par le système d'exploitation. Lorsque le concepteur du logiciel décide qu'une procédure en appelle d'autres, l'unité d'exécution saute d'une procédure à une autre, puis revient directement à son point de départ et reprend là où elle s'était arrêtée dès qu'elle rencontre une instruction return.

Du point de vue de l'UC, il n'existe qu'une seule unité d'exécution principale qui parcourt tout le logiciel, complétée par de courtes unités distinctes qui sont exécutées suite à des interruptions matérielles. Etant donné que tout le reste est généré sur ce modèle, il est important que les concepteurs connaissent le sujet. Les concepteurs de systèmes en temps réel, dans une plus grande mesure que les concepteurs d'autres types de logiciels, doivent comprendre le fonctionnement d'un système dans ses moindres détails. Ce modèle, toutefois, se situe à un niveau si faible d'abstraction qu'il ne peut représenter l'accès concurrent qu'avec une granularité très grossière (celle de l'UC). Pour concevoir des systèmes complexes, il est utile de pouvoir travailler à des niveaux divers d'abstraction. L'abstraction, bien entendu, est le produit d'une vue ou d'un modèle qui supprime les détails inutiles afin que nous puissions nous concentrer sur les aspects importants du problème considéré.

Pour monter d'un niveau, on envisage souvent les logiciels en termes de couches. Au niveau le plus élémentaire, le système d'exploitation (SE) est une couche qui s'intercale entre le matériel et le logiciel applicatif. Il fournit à l'application des services matériels, tels que la mémoire, la synchronisation et les E/S, mais il analyse l'UC afin de créer une machine virtuelle indépendante de la configuration matérielle réelle.

Réalisation de l'accès concurrent : mécanismes

Gestion des fils de contrôle

Pour prendre en charge l'accès concurrent, un système doit prévoir plusieurs fils de contrôle. L'abstraction d'une unité d'exécution peut être implémentée de multiples façons par le matériel et les logiciels. Les mécanismes les plus courants sont des variations de l'un des éléments suivants [DEI84], [TAN86] :

  • Multitraitement - exécution concurrente de plusieurs UC
  • Fonctionnement multitâche - les systèmes d'exploitation simulent un accès concurrent sur une unique UC en
    entrelaçant l'exécution de différentes tâches
  • Solutions reposant sur l'application - le logiciel applicatif se charge de
    la commutation d'une branche de code à une autre au moment opportun

Fonctionnement multitâche

Lorsque le système d'exploitation assure un fonctionnement multitâche, les processus constituent un exemple courant d'accès concurrent. Un processus est une entité fournie, prise en charge et gérée par le système d'exploitation, dont la seule finalité est de fournir un environnement dans lequel un programme peut être exécuté. Le processus fournit un espace mémoire exclusivement réservé à son programme applicatif, une unité d'exécution destinée à l'exécuter et éventuellement un moyen d'envoyer des messages à d'autres processus et d'en recevoir de ces derniers. Un processus est en fait une UC virtuelle destinée à exécuter une partie concurrente d'une application.

Chaque processus peut avoir trois états différents :

  • bloqué - le processus est en attente de réception d'une entrée ou de prise de contrôle d'une ressource ;
  • prêt - le processus attend que le système d'exploitation lui donne l'autorisation de s'exécuter ;
  • en cours de fonctionnement - le processus utilise l'UC à cet instant.

En outre, les processus se voient souvent affecter des priorités relatives. Le noyau du système d'exploitation détermine quel(s) processus exécuter à tout moment sur la base de l'état et des priorités de ce(s) processus et d'après une certaine règle de planification. Les systèmes d'exploitation multitâche partagent en réalité une unique unité d'exécution entre tous leurs processus.

Remarque : les termes « tâche » et « processus » sont souvent employés de manière interchangeable. Malheureusement, l'expression « fonctionnement multitâche » est généralement employée pour faire référence à la capacité à gérer simultanément plusieurs processus, tandis que « multitraitement » fait référence à un système doté de plusieurs processeurs (UC). Nous adhérons à cette convention car c'est celle qui est la plus répandue. Toutefois, nous utilisons rarement le terme « tâche », et le cas échéant, uniquement pour faire une subtile différence entre l'unité de travail en cours d'exécution (la tâche) et l'entité fournissant les ressources et l'environnement nécessaires (le processus).

Comme nous l'avons déjà évoqué, du point de vue de l'UC, il n'existe qu'une seule unité d'exécution. Exactement comme un programme d'application peut sauter d'une procédure à une autre en appelant des sous-programmes, le système d'exploitation peut transférer le contrôle d'un processus à un autre à l'occasion d'une interruption, de la fin d'une procédure ou d'un autre événement. Du fait de la protection de mémoire permise par un processus, cette « commutation de tâches » peut avoir pour corollaire un temps système considérable. De plus, la règle de planification et les états des processus n'ayant que peu de relations avec le point de vue de l'application, l'entrelacement des processus constitue généralement un niveau d'abstraction trop faible pour envisager le type d'accès concurrent important pour l'application.

Pour pouvoir penser clairement la question de l'accès concurrent, il est important de distinguer nettement le concept d'unité d'exécution de celui de commutation de tâche. Chaque processus peut être envisagé comme gérant sa propre unité d'exécution. Lorsque le système d'exploitation bascule d'un processus à un autre, une unité d'exécution est temporairement suspendue et une autre démarre ou reprend là où elle s'était arrêtée.

Traitement multitâche

De nombreux systèmes d'exploitation, particulièrement ceux utilisés pour les applications en temps réel, offrent une alternative « légère » aux processus, appelée « unités d'exécution » ou « unités d'exécution légères ».

Les unités d'exécution permettent d'obtenir une granularité d'accès concurrent légèrement plus fine au sein d'un processus. Chaque unité d'exécution appartient à un unique processus, et toutes les unités d'exécution d'un processus partagent le même espace mémoire et les autres ressources contrôlées par ce processus.

En général, chaque unité d'exécution se voit affecter une procédure à exécuter.

Remarque : il est regrettable que le terme « unité d'exécution » soit employé à tort et à travers. Lorsque nous employons le terme « unité d'exécution » seul, comme c'est le cas ici, nous faisons référence à une « unité d'exécution physique » fournie et gérée par le système d'exploitation. Lorsque nous parlons d'une « unité d'exécution », d'une « unité de contrôle » ou d'une « timethread » comme dans ce qui suit, nous parlons d'une abstraction qui n'est pas nécessairement associée à une unité d'exécution physique.

Multitraitement

Bien entendu, l'existence de plusieurs processeurs offre la possibilité d'une exécution véritablement concurrente. La plupart du temps, chaque tâche est affectée de manière permanente à un processus dans un processeur donné, mais dans certains cas les tâches peuvent être affectées de manière dynamique au prochain processeur disponible. La manière la plus facile d'y parvenir est peut-être d'utiliser un « multiprocesseur symétrique ». Dans ce type de configuration matérielle, plusieurs UC peuvent accéder à la mémoire via un bus commun.

Les systèmes d'exploitation prenant en charge les multiprocesseurs symétriques peuvent affecter de manière dynamique les unités d'exécution à n'importe quelle UC disponible. Solaris de SUN et Windows NT de Microsoft sont deux exemples de systèmes d'exploitation prenant en charge les multiprocesseurs symétriques.

Problèmes fondamentaux liés aux logiciels concurrents

Bien que cela puisse sembler paradoxal, nous avons précédemment affirmé que l'accès concurrent rend les logiciels à la fois plus simples et plus complexes. Les logiciels concurrents offrent des solutions plus simples aux problèmes complexes principalement parce qu'ils permettent une « séparation des problèmes » entre les activités concurrentes. A cet égard, l'accès concurrent n'est qu'un outil de plus pour accroître la modularité du logiciel. Lorsqu'un système doit effectuer des activités qui sont principalement indépendantes ou doit réagir face à des événements principalement indépendants, affecter ces derniers à des composants concurrents donnés simplifie naturellement la conception.

Les autres complexités liées aux logiciels concurrents découlent presque exclusivement des situations dans lesquelles ces activités concurrentes sont quasiment indépendantes, mais pas totalement. En d'autres termes, les complexités découlent de leurs interactions.  Du point de vue pratique, les interactions entre les activités asynchrones impliquent invariablement l'échange d'une forme de signaux ou d'informations. Les interactions entre unités de commande concurrentes entraînent un ensemble de problèmes qui sont propres aux systèmes concurrents, et qui doivent être traités afin de garantir le bon fonctionnement du système.

Comparaison entre l'interaction asynchrone et l'interaction synchrone

Bien qu'il existe de nombreuses réalisations spécifiques différentes de la communication interprocessus ou de nombreux mécanismes de communication interprocessus, il est au final possible de tous les répartir en deux grandes catégories :

Dans la communication asynchrone, l'activité émettrice réachemine ses informations, que le destinataire soit prêt à les réceptionner ou pas. Après avoir lancé les informations, l'expéditeur passe à l'activité suivante. Si le destinataire n'est pas prêt à réceptionner ces informations, ces dernières sont placées dans une file d'attente, dans laquelle il pourra les récupérer ultérieurement. L'expéditeur et le destinataire fonctionnent tous deux de manière asynchrone l'un par rapport à l'autre et ne peuvent donc aucunement présumer de leur état respectif. Le communication asynchrone est souvent appelée transmission de messages.

Outre l'échange d'informations, la communication synchrone prévoit une synchronisation entre l'expéditeur et le destinataire. Lors de l'échange d'informations, les deux activités concurrentes fusionnent en exécutant, en fait, un segment de code partagé, puis se séparent de nouveau une fois la communication achevée. Elles sont donc, durant cet intervalle, synchronisées et protégées contre tout conflit d'accès concurrent susceptible de se produire entre elles. Si une activité (expéditeur ou destinataire) est prête à communiquer avant l'autre, elle est mise en attente jusqu'à ce que l'autre activité soit également prête. C'est la raison pour laquelle ce mode de communication est parfois appelé rendez-vous.

L'un des problèmes potentiels de la communication synchrone réside dans le fait qu'une activité qui attend que son homologue soit prête n'est pas en mesure de réagir à d'autres événements. Pour de nombreux systèmes en temps réel, ce problème n'est pas toujours tolérable car il peut empêcher de garantir une réponse rapide à une situation importante. Un autre inconvénient réside dans la propension au blocage dont souffre la communication synchrone. Un blocage se produit lorsque deux activités ou plus sont impliquées dans un cercle vicieux où elles s'attendent mutuellement.

Lorsque des interactions sont nécessaires entre des activités concurrentes, le concepteur doit choisir entre un style synchrone ou asynchrone. Par synchrone, nous entendons que deux unités de commande concurrentes ou plus doivent se retrouver à un point unique dans le temps. Cela signifie généralement qu'une unité de commande doit en attendre une autre pour répondre à une requête. La forme la plus simple et la plus courante d'interaction synchrone se produit lorsque une activité concurrente A sollicite des informations auprès d'une activité concurrente B pour pouvoir poursuivre son propre travail.

Les interactions synchrones constituent, bien entendu, la norme pour les composants de logiciels non concurrents. Les appels de procédure ordinaires sont un exemple de choix d'interaction synchrone : lorsqu'une procédure en appelle une autre, l'appelant transfère instantanément le contrôle à la procédure appelée et « attend » véritablement que le contrôle lui soit restitué. Dans un contexte concurrent, des appareils complémentaires sont toutefois nécessaires afin de synchroniser des unités de commande qui seraient naturellement indépendantes.

Les interactions asynchrones ne nécessitent pas de rendez-vous dans le temps, mais requièrent cependant des appareils complémentaires pour prendre en charge les communications entre les deux unités de commande. Ces appareils prennent souvent la forme de canaux de communication pourvus de files d'attente de messages afin que les messages puissent être envoyés et reçus de manière asynchrone.

Il est à noter qu'une unique application peut mélanger communications synchrones et communications asynchrones, selon qu'elle doive attendre une réponse ou peut effectuer d'autres travaux pendant que l'expéditeur du message traite ce dernier.

Gardez à l'esprit qu'un véritable accès concurrent au niveau des processus ou des unités d'exécution n'est possible que sur les multiprocesseurs caractérisés par une exécution concurrente des processus ou des unités d'exécution. Sur un monoprocesseur, l'illusion d'exécution simultanée des unités d'exécution ou des processus est créée par le planificateur du système d'exploitation, qui segmente les ressources de traitement disponibles en petits tronçons afin de donner l'impression que plusieurs unités d'exécution ou processus s'exécutent de manière concurrente. Une mauvaise conception contournera ce découpage temporel en créant plusieurs processus ou unités d'exécution qui communiquent fréquemment et de manière synchrone, avec pour effet de voir les processus ou les unités d'exécution passer la majeure partie de leur « tranche de temps » bloqués et en attente d'une réponse d'un autre processus ou d'une autre unité d'exécution.

Conflits autour des ressources partagées

Des activités concurrentes peuvent dépendre de ressources rares qu'elles doivent partager. Les périphériques d'entrée-sorties constituent un exemple type. Si une activité requiert une ressource déjà utilisée par une autre activité, elle doit attendre son tour.

Conditions d'indétermination : la question de l'état cohérent

Le problème le plus fondamental dans la conception de systèmes concurrents est probablement celui des « conditions d'indétermination », qui doivent être évitées. Lorsqu'une partie d'un système doit effectuer des fonctions liées à l'état (c'est-à-dire des fonctions dont le résultat dépend de l'état du système à cet instant), elle doit avoir la garantie que cet état restera stable au cours de l'opération. En d'autres termes, certaines opérations doivent être « atomiques ». A chaque fois que deux unités de commande ou plus ont accès aux mêmes informations d'état, une certaine forme de « contrôle d'accès concurrent » est nécessaire afin de garantir qu'une unité ne modifie pas l'état pendant que l'autre effectue une opération atomique liée à l'état. On appelle « conditions d'indétermination » les tentatives d'accès simultané aux mêmes informations d'état susceptibles de rendre l'état intérieurement incohérent.

Un exemple type de condition d'indétermination peut facilement se produire dans un système d'ascenseur lorsqu'un passager sélectionne un étage. Notre ascenseur fonctionne à partir de listes d'étages à visiter lorsqu'il se déplace dans chaque direction, ascendante ou descendante. A chaque fois que l'ascenseur atteint un étage, une unité de commande supprime cet étage de la liste correspondante et identifie la destination suivante à partir de cette liste. Si la liste est vide, l'ascenseur change de direction si des étages figurent dans l'autre liste ou reste inactif si les deux listes sont vides. Une autre unité de commande est responsable d'affecter les requêtes d'étage aux listes qui conviennent lorsque les passagers sélectionnent un étage. Chaque unité d'exécution effectue sur la liste des combinaisons d'opérations qui ne sont pas intrinsèquement atomiques : par exemple, vérifier quel est le prochain emplacement disponible et le remplir. S'il s'avère que les unités d'exécution entrelacent leurs opérations, ces dernières peuvent aisément écraser le même emplacement de la liste.

Blocage

Le blocage est une condition dans laquelle deux unités de commande sont toutes deux bloquées et attendent chacune que l'autre effectue une action. Assez ironiquement, les blocages se produisent souvent du fait de notre recours à des dispositifs de synchronisation destinés à éviter les conditions d'indétermination.

L'exemple de condition d'indétermination rencontré avec l'ascenseur pourrait facilement entraîner un cas assez bénin de blocage. L'unité de commande de l'ascenseur pense que la liste est vide et ne se déplace donc vers aucun autre étage. L'unité d'exécution de la requête d'étage pense que l'ascenseur est occupé à vider la liste et qu'elle n'est donc pas tenue d'informer l'ascenseur qu'il doit quitter l'état inactif.

Autres problèmes pratiques

Outre les problèmes « fondamentaux », il existe certains problèmes pratiques qui doivent être explicitement traités lors de la conception de logiciels concurrents.

Compromis sur les performances

Au sein d'un monoprocesseur, les dispositifs nécessaires à la simulation d'accès concurrent par commutation des tâches utilisent les cycles d'UC qui seraient en temps normal consacrés à l'application elle-même. D'un autre côté, si le logiciel doit attendre des périphériques d'entrée-sortie, par exemple, les améliorations des performances offertes par l'accès concurrent peuvent largement compenser tout temps système supplémentaire.

Compensations de la complexité

Les logiciels concurrents nécessitent des dispositifs de coordination et de contrôle qui ne sont pas nécessaires dans les applications de programmation séquentielle. Ceci rend les logiciels concurrents plus complexes et augmente le risque d'erreurs. Les problèmes survenant dans les systèmes concurrents sont également intrinsèquement plus difficiles à diagnostiquer du fait de la multiplicité des unités de commande. D'un autre côté, comme nous l'avons déjà évoqué, lorsque les forces contraignantes externes sont elles-mêmes concurrentes, le logiciel concurrent qui gère les différents événements indépendamment peut être considérablement plus simple qu'un programme séquentiel tenu de gérer les événements dans un ordre arbitraire.

Le non-déterminisme

Etant donné que de nombreux facteurs déterminent l'entrelacement d'exécution de composants concurrents, le même logiciel peut répondre à la même séquence d'événements dans un ordre différent. En fonction de la conception, ces changements d'ordre peuvent produire des résultats différents.

Le rôle des logiciels d'applications dans le contrôle des accès concurrents

Les logiciels d'applications peuvent être impliqués ou non dans la mise en oeuvre du contrôle des accès concurrents. Il existe un large éventail de possibilités, dont les suivantes, présentées dans l'ordre croissant d'implication :

  1. Les tâches d'application peuvent être interrompues à tout moment par le système d'exploitation (fonctionnement multitâche préventif).
  2. Les tâches d'application peuvent définir des unités atomiques de traitement (sections critiques) ne devant pas être interrompues et informer le système d'exploitation lorsqu'elles sont accédées ou quittées.
  3. Les tâches d'application peuvent décider quand transférer le contrôle de l'UC à d'autres tâches (fonctionnement multitâche coopératif).
  4. Les logiciels d'application peuvent assumer l'entière responsabilité de la planification et du contrôle de l'exécution de diverses tâches.

Les possibilités mentionnées ci-dessus ne constituent nullement un ensemble exhaustif et ne s'excluent pas mutuellement. Certaines d'entre elles peuvent très bien être utilisées conjointement dans un système donné.

Abstraction de l'accès concurrent

Une erreur fréquemment commise lors de la conception de systèmes concurrents consiste à sélectionner trop tôt dans le processus de conception les mécanismes précis à utiliser pour l'accès concurrent. Chaque mécanisme se caractérise par certains avantages et inconvénients et choisir le « meilleur » mécanisme pour une situation donnée est souvent le fruit de subtils compromis et compensations. Plus un mécanisme est choisi tôt, moins les informations dont on dispose pour effectuer son choix sont nombreuses. Fixer un mécanisme a également tendance à réduire la souplesse et l'adaptabilité de la conception à d'autres situations.

Comme c'est le cas pour la plupart des tâches de conception complexes, le recours à plusieurs couches d'abstraction rend l'accès concurrent plus intelligible. Tout d'abord, les exigences fonctionnelles du système doivent être bien comprises en termes de comportement souhaité. Ensuite, les rôles possibles de l'accès concurrent doivent être étudiés. La meilleure manière d'y parvenir est de recourir à l'abstraction des unités d'exécution sans se fixer sur une implémentation en particulier. Dans la mesure du possible, le choix final des mécanismes de réalisation de l'accès concurrent doit demeurer ouvert afin de permettre d'ajuster les performances avec précision et de distribuer les composants différemment pour les diverses configurations de produit.

La « distance conceptuelle » entre le domaine du problème (un système d'ascenseur, par ex.) et le domaine de la solution (les constructions logicielles) demeure l'un des plus gros problèmes de la conception de systèmes. Les « formalismes visuels » sont d'une grande utilité quand il s'agit de comprendre et de communiquer des idées complexes telles que le comportement concurrent et, dans la pratique, de combler ce fossé conceptuel. Parmi les outils qui se sont montrés utiles pour ce type de problèmes, on trouve :

  • diagrammes de modules permettant de prévoir les composants agissant de manière concurrente ;
  • timethreads permettant de prévoir les activités concurrentes et ayant des interactions (qui peuvent être orthogonales par rapport aux composants) ;
  • diagrammes de séquence permettant de visualiser les interactions entre composants ;
  • tableaux de diagrammes de transition d'état permettant de définir l'état et le comportement lié à l'état des composants.

Les objets en tant que composants concurrents

Pour concevoir un système logiciel concurrent, nous devons associer les blocs de génération logiciels (procédures et structures de données) aux blocs de génération d'accès concurrent (unités de commande). Le concept d'activité concurrente a déjà été abordé, mais les systèmes ne sont pas développés à partir d'activités. Ils le sont à partir de composants, et il est logique de développer des systèmes concurrents à partir de composants concurrents. Pris individuellement, ni les procédures, ni les structures de données, ni les unités de commande ne constituent des modèles très naturels pour les composants concurrents, contrairement aux objets, qui apparaissent comme une manière très naturelle d'associer tous les éléments nécessaires en un package bien fini.

Un objet regroupe les procédures et les structures de données au sein d'un composant cohérent doté de son propre état et de son propre comportement. Il encapsule l'implémentation précise de cet état et de ce comportement et définit une interface au travers de laquelle d'autres objets ou logiciels peuvent interagir avec lui. Les objets modélisent généralement les entités réelles ou les concepts et interagissent avec les autres objets en échangeant des messages. Ils sont aujourd'hui considérés par beaucoup comme la meilleure manière de construire des systèmes complexes.

Diagramme détaillé dans le contenu.

Figure 4 :   un ensemble simple d'objets pour le système d'ascenseur.


Imaginez un modèle d'objet pour notre système d'ascenseur. Un objet de poste d'appel positionné à chaque étage surveille les boutons d'appels ascendant et descendant de cet étage. Lorsqu'un passager potentiel appuie sur un bouton, l'objet de station d'appel répond en envoyant un message à un objet répartiteur d'ascenseur, qui sélectionne l'ascenseur susceptible de fournir le service le plus rapide, affecte cet ascenseur pour exécution et accuse réception de l'appel. Chaque objet d'ascenseur contrôle de manière indépendante et concurrente son homologue physique d'ascenseur, et répond aux sélections d'étage effectuées par les passagers et aux appels du répartiteur.

L'accès concurrent peut prendre deux formes dans ce type de modèle d'objet. L'accès concurrent entre objets se produit lorsque deux objets ou plus effectuent des activités de manière indépendante via des unités de commande distinctes. L'accès concurrent interne aux objets se produit lorsque plusieurs unités de commande sont actives dans un unique objet. Dans la plupart des langages à objets d'aujourd'hui, les objets sont « passifs » et ne disposent pas d'unité de commande propre. La ou les unité(s) de commande doit(doivent) être fournie(s) par un environnement externe. La plupart du temps, l'environnement est un processus standard de système d'exploitation créé pour exécuter un « programme » à objets écrit dans un langage tel que C++ ou Smalltalk. Si le système d'exploitation prend en charge le traitement multitâche, plusieurs unités d'exécution peuvent être actives dans le même objet ou dans des objets différents.

Dans la figure ci-dessous, les objets passifs sont représentés par les éléments circulaires. La zone intérieure grisée de chaque objet correspond à ses informations d'état et l'anneau extérieur segmenté correspond à l'ensemble de procédures (méthodes) qui définissent son comportement.

Diagramme détaillé dans le contenu.
Figure 5 :   exemple d'interaction d'objets.

L'accès concurrent interne aux objets a pour corollaire tous les défis posés par les logiciels concurrents, tels que le risque de conditions d'indétermination lorsque plusieurs unités de commande ont accès au même espace mémoire (dans le cas présent, les données encapsulées dans l'objet). On aurait pu penser que l'encapsulation des données aurait fourni une solution à cette question. Le problème, bien entendu, est que l'objet n'encapsule pas l'unité de commande. Bien que l'accès concurrent entre objets évite en majeure partie ces problèmes, il subsiste un problème de taille. Pour que deux objets concurrents puissent interagir en échangeant des messages, au moins deux unités de commande doivent gérer ce message et accéder au même espace mémoire afin de pouvoir le transmettre. Un problème annexe (mais tout aussi épineux) réside dans la répartition des objets entre différents processus ou même entre différents processeurs. Les messages entre objets de différents processus requièrent une assistance pour la communication interprocessus et exigent généralement que le message soit encodé et décodé en données pouvant être transmises au-delà des limites des processus.

Aucun de ces problèmes n'est bien entendu insurmontable. En fait, comme nous l'avons souligné dans la section précédente, chaque système concurrent doit composer avec eux, c'est pourquoi il existe des solutions éprouvées. En réalité, le problème se résume au fait que le « contrôle de l'accès concurrent » induit une charge de travail supplémentaire et augmente le risque d'erreurs. En outre, il masque l'essence même de la question de l'application. Pour toutes ces raisons, nous souhaitons, autant que possible, éviter aux programmeurs d'applications d'y être confrontés directement. L'une des façons d'y parvenir consiste à générer un environnement orienté objet comportant une prise en charge de la transmission de messages entre objets concurrents (y compris un contrôle de l'accès concurrent), et de réduire, voire de supprimer, le recours à plusieurs unités de commande au sein d'un objet unique. En réalité, ceci a pour effet d'encapsuler l'unité de commande ainsi que les données.

Le modèle d'objet actif

On appelle « objets actifs » les objets dotés de leurs propres unités de commande. Afin de prendre en charge la communication asynchrone avec d'autres objets actifs, chaque objet actif est fourni avec une file d'attente de messages, ou « boîte aux lettres ». Lors de la création d'un objet, l'environnement lui confère sa propre unité de commande, que l'objet encapsule jusqu'à sa disparition. A l'instar d'un objet passif, un objet actif reste en veille jusqu'à l'arrivée d'un message de l'extérieur. L'objet exécute le code qui convient pour traiter le message. Tout message entrant alors que l'objet est occupé est placé en file d'attente dans la boîte aux lettres. Lorsque l'objet achève de traiter un message, il va récupérer le message en attente suivant dans la boîte aux lettres ou attend qu'un nouveau message lui parvienne. Comme bons exemples d'objets actifs dans le système d'ascenseur, on trouve les ascenseurs à proprement parler, les stations d'appel de chaque étage et le répartiteur.

En fonction de leur implémentation, il est possible de rendre les objets actifs assez efficaces. Ils occasionnent toutefois plus de temps système qu'un objet passif. Dès lors, chaque opération n'étant pas tenue d'être concurrente, il est fréquent de panacher objets actifs et objets passifs au sein d'un même système. Du fait de leurs styles de communication différents, il est difficile d'en faire des homologues, mais un objet actif constitue un environnement idéal pour les objets passifs, en remplaçant le processus du système d'exploitation utilisé précédemment. En effet, si l'objet actif délègue tout le travail aux objets passifs, il devient de fait l'équivalent d'un processus de système d'exploitation ou d'une unité d'exécution dotée de fonctions de communication interprocessus. Les objets actifs les plus intéressants, toutefois, ont un comportement qui leur est propre et qui leur permet d'effectuer une partie du travail, en déléguant le reste aux objets passifs.

Diagramme détaillé dans le contenu.

Figure 6 :   un objet "actif" fournit un environnement aux classes passives

Comme bons exemples d'objets passifs au sein d'un objet d'ascenseur actif, on trouve une liste d'étages auxquels l'ascenseur doit s'arrêter lorsqu'il monte et une autre liste du même type pour les déplacements descendants. L'ascenseur doit être en mesure de demander à la liste quel est le prochain arrêt, d'ajouter de nouveaux arrêts à cette liste et de supprimer les arrêts qui ont été desservis.

Les systèmes complexes étant quasiment toujours composés de sous-systèmes comportant plusieurs niveaux avant d'arriver aux composants de niveau de feuille, autoriser les objets actifs à contenir d'autres objets actifs est une extension logique du modèle d'objet actif.

Bien qu'un objet actif à unité d'exécution unique ne prenne pas en charge le véritable accès concurrent interne aux objets, le fait de déléguer une partie du travail aux objets actifs contenus constitue un substitut acceptable pour de nombreuses applications. Il conserve l'avantage important d'une encapsulation complète de l'état, du comportement et de l'unité de commande de manière individuelle pour chaque objet, ce qui simplifie les problèmes de contrôle de l'accès concurrent.

Diagramme détaillé dans le contenu.

Figure 7 :   le système d'ascenseur, comportant des objets actifs imbriqués

Prenons, par exemple, le système partiel d'ascenseur représenté ci-dessus. Chaque ascenseur est doté de portes, d'un palan et d'un panneau de contrôle. Chacun de ces composants est correctement modélisé par un objet actif concurrent, dans lequel l'objet de porte commande l'ouverture et la fermeture des portes de l'ascenseur, l'objet de palan commande la position de l'ascenseur dans la cage et l'objet panneau de contrôle surveille les boutons de sélection d'étage et les boutons d'ouverture/fermeture des portes. Le fait d'encapsuler les unités de commande concurrentes en tant qu'objets actifs produit des logiciels beaucoup plus simples que ceux qui auraient été produits si tous ces comportements étaient gérés par une unique unité de commande.

Le problème de « l'état cohérent » chez les objets

Comme nous l'avons expliqué en évoquant les conditions d'indétermination, pour qu'un système se comporte correctement et de manière prévisible, certaines opérations liées à l'état doivent être atomiques.

Pour qu'un objet se comporte correctement, il est assurément nécessaire que son état interne soit cohérent avant et après le traitement de tout message. Lors du traitement d'un message, l'état de l'objet peut se trouver dans une condition transitoire et peut s'avérer indéterminé si les opérations ne sont que partiellement réalisées.

Si un objet fournit toujours une réponse complète à un message avant de répondre à un autre, cette condition temporaire ne constitue pas un problème. Interrompre un objet pour en exécuter un autre ne pose pas de problème non plus car chaque objet effectue une encapsulation stricte de son état (à strictement parler, cette affirmation n'est pas totalement vraie, comme nous l'expliquerons plus loin).

Toute situation dans laquelle un objet interrompt le traitement d'un message pour en traiter un autre rend possible des conditions d'indétermination et nécessite dès lors de recourir à un contrôle de l'accès concurrent. Ceci rend alors possible un éventuel blocage.

La conception concurrente est généralement plus simple, par conséquent, si les objets traitent chaque message intégralement avant d'en accepter un autre. Ce comportement est implicite dans la forme particulière de modèle d'objet actif que nous avons présenté.

La question de l'état cohérent peut se manifester sous deux formes différentes dans les systèmes concurrents et ces formes sont peut-être plus faciles à comprendre en termes de systèmes concurrents orientés objet. La première forme est celle dont nous avons déjà parlé. Si l'état d'un objet unique (passif ou actif) est accessible à plusieurs unités de commande, les opérations atomiques doivent être protégées soit par l'atomicité naturelle des opérations UC élémentaires, soit par un dispositif de contrôle des accès concurrents.

La seconde forme du problème d'état cohérent est peut-être plus subtile. Si plusieurs objets (actifs ou passifs) contiennent les mêmes informations d'état, ces objets seront inéluctablement en désaccord sur l'état, au moins pendant de très brefs intervalles de temps. En cas de mauvaise conception, ils peuvent être en désaccord pour des périodes plus prolongées, peut-être même de manière définitive. Cette manifestation d'état incohérent peut être considérée comme un « double » mathématique de l'autre forme.

Par exemple, le système de contrôle des déplacements de l'ascenseur (le palan) doit s'assurer que les portes sont fermées et ne peuvent s'ouvrir pour que l'ascenseur puisse se déplacer. Une conception dépourvue de systèmes de sécurité adaptés pourrait autoriser l'ouverture des portes suite à une requête d'ouverture qu'effectuerait un passager alors que l'ascenseur commence à se déplacer.

On pourrait penser qu'une solution simple à ce problème serait d'autoriser les informations d'état à ne résider que dans un seul objet. Bien que cette solution puisse avoir une certaine utilité, elle peut également avoir une incidence néfaste sur les performances, particulièrement dans les systèmes répartis. De plus, il ne s'agit pas d'une solution indéréglable. Même si un seul objet contient certaines informations d'état, tant que d'autres objets concurrents prennent des décisions basées sur cet état à un moment donné dans le temps, les changements d'état peuvent invalider les décisions d'autres objets.

Il n'existe pas de solution magique au problème de l'état cohérent. Toutes les solutions pratiques nous imposent d'identifier les opérations atomiques et de les protéger au moyen d'un quelconque dispositif de synchronisation qui bloque l'accès concurrent pendant des périodes d'une durée acceptable. Le concept de « durée acceptable » dépend en grande partie du contexte. Il peut s'agir du temps nécessaire à l'UC pour stocker tous les octets dans un nombre à virgule flottante, ou il peut s'agir du temps nécessaire à l'ascenseur pour atteindre l'étage suivant.

Systèmes en temps réel

Dans les systèmes en temps réel, le processus RUP recommande d'utiliser des Capsules pour représenter les objets actifs. Les capsules comportent une sémantique robuste afin de simplifier la modélisation de l'accès concurrent :
  • elles utilisent la communication asynchrone basée sur les messages via des ports en recourant à des protocoles bien définis ;
  • elles utilisent une sémantique RTC pour le traitement des messages ;
  • elles encapsulent les objets passifs (prévenant ainsi tout risque d'interférence entre les unités d'exécution).