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.
|
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.
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.
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.
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.
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.

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.
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.
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
Outre les problèmes « fondamentaux », il existe certains problèmes pratiques qui doivent être explicitement traités
lors de la conception de logiciels concurrents.
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.
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.
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.
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 :
-
Les tâches d'application peuvent être interrompues à tout moment par le système d'exploitation (fonctionnement
multitâche préventif).
-
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.
-
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).
-
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é.
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.
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.
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.

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.
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.
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.
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.
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.
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).
|