Approche de programmation concurrente sous Android
Approche de programmation concurrente sous Android modifier
Définition modifier
Une situation de compétition est le comportement d'un système électronique, logiciel ou autre, où la sortie dépend du séquencement d'autres événements incontrôlables. Elle devient un bug lorsque les événements ne se produisent pas dans l'ordre que le programmeur a prévu. Le terme provient de l'idée de deux signaux qui font la course les uns contre les autres pour influencer la sortie en premier.
Causes modifier
Cette section fournit différents types de concurrence qui peuvent survenir sur la plateforme Android.
Par exemple, une situation de concurrence peut se produire quand deux événements (générés à partir de sources variées) peuvent être exécutés dans un ordre arbitraire et accèdent à la même zone de mémoire et un des deux accès est un accès en écriture.
Ces situations de concurrence en Android[1] ont un comportement différent par rapport aux langages traditionnels qui proposent des structures très faibles. Par exemple avec le langage C, il est possible d'incrémenter une variable non-atomique, alors qu'Android possède une structure bien définie, c'est-à-dire que les événements sont exécutés par le même thread.
La partie suivante consiste en la mise en situation de différents types de concurrence sous Android, puis le comportement nuisible que ceux-ci peuvent engendrer et finalement la solution pour les éviter.
Réutilisation d'objets modifier
Situation modifier
Imaginons une ListView affichant une image par ligne, et que chaque ligne doit afficher une image différente (comme dans la figure ci-contre).
Chaque ligne est identifiée par un index et contient donc une ImageView qui, grâce à un adaptateur, charge son image respective à travers le système de fichiers ou du réseau.
Chaque fois qu'une nouvelle ligne devient visible sur l'écran, soit à la création de la liste ou quand l'utilisateur descend dans celle-ci, le framework d'implémentation de la ListView invoque la méthode getView pour remplir le contenu de sa ligne. Et même si la liste contient une centaine de lignes, seulement quelques-unes sont affichées à l'écran à n'importe quel instant. À cause de cela, pour des soucis de performances, le composant représentant la ligne est réutilisé et est fourni à la méthode getView en paramètre.
Pour assurer une réactivité de la vue, l'application créer un ImageLoader qui est une AsyncTask (un mécanisme de thread asynchrone présent nativement dans Android) afin de charger l'image. À la fin du chargement, cette tâche avertit le thread principal pour que celui-ci rafraîchisse la vue avec l'image téléchargée.
Comportement nuisible modifier
Malheureusement, vu que les composants de l'ImageView sont réutilisés par le framework, il est possible que 2 tâches asynchrones avec la même ImageView chargent des images différentes en parallèle. Le résultat dépend donc de la tâche asynchrone la plus lente qui va afficher son image en dernier.
Il est possible que l'image de la ligne n°1 se retrouve dans la ligne n°6.
Solution modifier
Pour éviter ce genre de situation, il faut pouvoir ignorer la réutilisation des composants de l'ImageView et en créer de nouveaux pour chaque ligne mais cela dégrade fortement les performances.
Une autre solution est d'appliquer un tag à l'ImageView avant de lancer la tâche asynchrone et de tester si ce tag est toujours le même en fin de tâche.
Invalidation modifier
Une invalidation désigne une opération qui peut utiliser un objet qui ne serait plus dans un état valide.
Situation modifier
Imaginons une activité qui à son lancement doit charger des données et donc lance une tâche asynchrone (AsyncTask) et affiche une pop-up (ProgressDialog en Android) pour avertir l'utilisateur de devoir patienter.
Comportement nuisible modifier
Si lorsque la tâche asynchrone est terminée et doit renvoyer ses résultats, l'activité n'est plus dans un état valide (cela peut se produire si l'utilisateur navigue autre part, comme en appuyant sur le bouton précédent alors que la pop-up est toujours présente), il est possible que l'activité crashe tout simplement en essayant d'invoquer des méthodes sur des objets invalides (comme, essayer de faire disparaître la pop-up qui n'existe plus et qui est donc null).
Dans cet exemple, l’événement qui détruit l'activité quand l'utilisateur navigue autre part et l’événement de la tâche asynchrone ne possèdent pas d'ordre.
Solution modifier
Une solution serait de vérifier si l'activité est toujours dans un état valide à la fin de la tâche asynchrone.
Callback modifier
Le framework Android possède une centaine de types d'événements qui peuvent être délivrés à une application de manière non-déterminée.
Même les développeurs maîtrisant Android peuvent ne pas savoir toutes les contraintes d'ordre.
Situation modifier
Imaginons une application utilisant la puce GPS et écrivant les positions en base de données.
Les opérations de base de données sont facilitées grâce à un SQLiteOpenHelper (fourni par le framework Android).
La méthode onResume du framework Android (qui est invoquée lorsque l'activité démarre ou en sortie de veille) est utilisée, ici, pour démarrer la mise à jour de la localisation.
La méthode onStop du framework Android (qui est invoquée lorsque l'utilisateur navigue autre part par exemple) est utilisée pour supprimer ces mises à jour et pour fermer la connexion à la base de données.
Comportement nuisible modifier
Si la puce GPS demande une mise à jour de la position alors que la méthode onStop est en train d'être invoquée, la position peut arriver lorsque l'activité a déjà été arrêtée, la connexion à la base de données va être réouverte par le SQLiteOpenHelper et consommer des ressources alors que l'utilisateur n’interagit plus avec cette activité.
Solution modifier
Pour assurer que la mise à jour de la position n'est pas traitée alors que l'activité est stoppée, il faudrait ajouter un flag pour tester si celle-ci est toujours active.
Android et son fonctionnement modifier
Cette partie va balayer la manière dont Android fonctionne et plus particulièrement comment Android gère la délégation d’événements, celle-ci étant différente par rapport à un système classique et utilisant des mécanismes développés par le framework.
Délégation d’événements modifier
La délégation d'événements sous Android est facilitée par la classe Looper.
Quand l'application démarre, le framework Android démarre le thread principal et lance le Looper sur celui-ci. Il s'occupe de dispatcher les événements (appelés messages) et chaque message définit une routine qui peut être exécutée.
Quand une routine est démarrée, aucun autre message de routine ne peut être démarré tant que la première n'est pas terminée. Additionnellement le Looper permet pour un message d'être mis en file d'attente soit par le framework directement soit par l'application et il supporte la suppression de message qui serait obsolète avant qu'il soit dispatché.
Message modifier
Un message est donc un événement qui définit une routine et est dispatché par le Looper.
Il possède plusieurs attributs :
- Delayed(delay) : le message doit être dispatché après le délai fourni en paramètre. Si celui-ci est égal à 0, le message doit être dispatché directement après que l'événement courant soit terminé.
- AtTime(when) : le message devrait être dispatché à un temps précis fourni en paramètre.
- Front : le message devrait être dispatché directement après l’événement courant (avant les autres messages dans la file d'attente).
- Idle : le message peut être dispatché à n'importe quel instant quand le Looper ne doit rien traiter.
Il y a aussi des messages différents :
- Barriers : Les messages marqués comme des barrières par le framework sont autorisés à outrepasser la file d'attente et doivent être exécutés avant un temps critique. Ces messages sont par exemple des animations ou des manipulations de l'interface utilisateur qui doivent être exécutés à une cadence d'image fixe élevée.
- Messages natifs : Le Looper contient des mécanismes supplémentaires de bas niveau pour mettre en file d'attente et dispatcher les messages venant du code natif du framework. Ces messages sont utilisés seulement par le framework dans le but d'améliorer les résultats de livraison des interactions avec l'utilisateur (Input et Display messages).
Communication inter-processus modifier
Les communications entre les processus (par exemple avec des services comme le manager Audio ou Wifi) sont facilitées grâce à un mécanisme appelé Binder.
Similairement au Looper, on peut voir le Binder comme un type spécial de dispatcheur, où les messages sont mis en file d'attente, dispatchés et finalement exécutés par des processus différents.
Les messages inter-processus peuvent être mis en file d'attente soit de manière synchrone soit asynchrone.
Le premier garantissant que le thread exécutant la mise en file d'attente soit bloqué jusqu'à ce que le processus recevant le message soit complètement terminé.
Le deuxième retournant directement au thread ayant fait la mise en file d'attente.
Chaque application traite les messages inter-processus avec un pool de 16 threads, appelés Binder threads.
Le choix du Binder thread exécutant le message entrant est choisi de manière non-déterminée et les applications doivent être préparées à gérer de multiple messages arrivant au même moment.
Capture de l'asynchronisme de la plate-forme Android modifier
Cette partie explique comment il est possible de capturer les processus asynchrones sous Android.
Opérations et évènements modifier
Les différentes opérations Android sont définies selon un modèle qui peut être appliqué de manière générique.
{event,pid,tid,mid,type,dispatcher,dispatcher(type),delay,sync,barrier}
Voici une explication des différents champs associés :
- event permet de définir un unique id d’événement afin d'obtenir l'appartenance de celui-ci à une opération précise
- pid est l'identifiant du processus
- mid est un identifiant associé à chaque message
- type est une des valeurs { Delayed, Front, Idle, AtTime, Input, Display, IPC }
- dispatcher est l'identifiant du transmetteur de message
- dispatcher(type) est une des valeurs { Looper, Binder }
- delay est un entier
- sync et barriere sont des booléens
La plupart du temps seuls quelques champs sont remplis.
Les évènements sont eux un nombre fini d'opérations avec un début et une fin ayant pour but de délivrer un message par une machine de transmission ( Looper - Binder - ... ).
Happens-Before modèle modifier
L'appellation "Happens-Before" est le nom donné à une opération qui apparaît avant une autre dans le fil d’exécution.
Il existe un nombre de règles assez important qui sont les suivantes
- EventOp, les opérations exécutées dans un même événement sont ordonnancées via le fil d'exécution
- LooperAtomic, des événements initiés par un même Looper sont ordonnés
- ThreadInit et ThreadExit, toutes les opérations exécutées dans un Thread sont ordonnées après "thread_init" et avant "thread_exit"
- MsgEnqueue, un message enqueue est commandé avant le début de la transmission notifié par l'opération begin
- MsgRemove, l'opération remove est demandée après la transmission de tous les autres messages
- MsgBlocking, pour les opérations de blocages end est demandé avant le message blocking_enqueue_end
Calcul évolutif sur le HB-graphe modifier
La clé de l'analyse repose sur la possibilité de proposer un algorithme de calcul de graphe d'HB fiable depuis une exécution d'un programme donné.
La raison pour laquelle il est nécessaire d'avoir un nouvel algorithme réside dans la complexité des règles HB discutées jusqu'ici. En effet, une fois développé pour Android, un algorithme de construction d'HB graphe pourra être facilement transformé pour d'autres plateformes (iOS - Windows Phone).
Règle efficace de matching modifier
L'algorithme développé évalue la plupart des règles en continu en récupérant des parties de ces règles ce qui permet de retrouver facilement via une opération α une autre opération β.
Ce procédé est utilisé avec : MsgEnqueue, MsgRemove, MsgBlocking, ainsi que toutes les règles de CallBack et Thread afin de garantir que l'opération α est unique dans la trace d'exécution et est efficacement en cache.
Règle d’évaluation de l'ordre modifier
Afin d'assurer de l'efficacité il faut définir un ordre pour les règles d'HB pour chaque opération dans la trace d'exécution de manière à ce qu'une règle soit évaluée une seule fois.
Excepté les règles MsgBegin et IpcAsync, toutes les règles peuvent être évaluées dans n'importe quel ordre à l'exception de ces 2 qui sont évaluées en dernières.
Solutions existantes modifier
CAFA modifier
CAFA[2] est un outil qui se compose d'une ROM Android personnalisée (basée sur le projet Open Source Android 4.3) et d'un outil d'analyse hors ligne.
Les ROM personnalisées disposent de plusieurs composants clés dans Android (par exemple, la machine virtuelle Dalvik (DVM) et les bibliothèques de base) pour collecter des traces d'exécution pour les applications cibles et des services système.
Les tracés collectés sont ensuite utilisés par l'outil d'analyse hors ligne pour reconstituer les modèles «Happens-Before» et détecter les situations de compétitions.
La ROM personnalisée peut être directement installée sur certains appareils Android tels que Google Nexus 4. CAFA est complètement transparent, et peut ainsi suivre et analyser des applications Android non modifiées.
DROIDRACER modifier
DroidRacer[3] est un outil de détection de course dynamique pour les applications Android. Il a été construit en modifiant et instrumentant android-4.0.1_r1.
Il implémente un algorithme de détection de course hors ligne.
Il possède 3 composants :
- L'explorateur d'interface utilisateur
- Le générateur d'opérations
- Le détecteur de situations de compétition
EVENTRACER modifier
EventTracer[4] est un outil qui tente de découvrir les situations de compétition nuisibles (bugs concurrents) dans les pages Web. Il classe les situations découvertes et montre celles qui, selon lui, sont potentiellement dangereuses en premier.
EventRacer se compose de deux parties - un navigateur instrumenté et un analyseur de course.
L'analyse derrière EventRacer est basée sur des techniques développées dans la communauté des langages de programmation et sur des algorithmes[5],[6] spécifiques aux applications web.
SDNRACER modifier
SDNRacer[7] est le premier analyseur de concurrence dynamique et contrôleur-agnostique complet pour les contrôleurs de logiciels de création de réseaux (Software-Defined Networking, SDN).
SDNRacer vérifie une variété d'erreurs, y compris les situations de compétition de données (de niveau élevé), les violations de cohérence des paquets et les violations d'isolation de mises à jour. Il capte précisément l’asynchronisme des environnements SDN grâce à la première formulation d'un modèle «Happens-Before» pour les fonctionnalités Openflow[8] les plus couramment utilisées.
"Scalable Race Detection for Android Applications" (SRDAA) modifier
SRDAA[9] est le dernier projet dynamique d'analyse système en date pour trouver des situations de compétition dans les applications Android.
Celui-ci est basé sur 3 concepts :
- Un modèle HB avancé spécifique à Android
- Un algorithme d'analyse évolutif permettant de construire et d'interroger efficacement le modèle HB
- Un ensemble efficace de filtres spécifiques au domaine qui réduisent le nombre de situations de compétition de données rapportées
Comparaison modifier
SRDAA est bien plus complet que les autres travaux concernant la détection avec un ensemble de règles pour le modèle «Happens-Before» plus complexes et avancées.
| Règles HB | MsgBegin | MsgRemove | barriers | IPCAsync | MsgBlocking | IPCHandle |
|---|---|---|---|---|---|---|
| CAFA | Delayed, Front | x | ||||
| DROIDRACER | Delayed | x | ||||
| SRDAA | All | x | x | x | x | x |
Ils prennent aussi bien plus de temps (plusieurs heures contre quelques secondes) et ne peuvent analyser d'interactions réalistes.
SRDAA détecte les situations de compétition provenant d'un côté du code utilisateur mais également les interactions avec le framework Android.
Concernant la disponibilité des outils :
- CAFA n'est pas disponible publiquement
- DROIDRACER ne peut traiter à l'heure actuelle de traces plus grandes que quelques secondes et continue à planter
- SRDAA est disponible sur un site internet et en tant qu'outil à l'adresse : http://eventracer.org/android/
Note et références modifier
Références modifier
- ↑ Pallavi Maiya, Aditya Kanade et Rupak Majumdar, « Race Detection for Android Applications », Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM, PLDI '14re série, 2014-01-01, p. 316–325 (ISBN 9781450327848) [texte intégral lien DOI (pages consultées le 2016-12-12)]
- ↑ « Race detection for event-driven mobile applications langue non précisée », PLDI ’14, 2014, p. 326–336
- ↑ « droidracer - Software Engineering and Analysis Lab (SEAL), IISc Bangalore », sur www.iisc-seal.net (consulté le 12 décembre 2016)
- ↑ « EVENT RACER for Android », sur eventracer.org (consulté le 12 décembre 2016)
- ↑ Veselin Raychev, Martin Vechev et Manu Sridharan, « Effective Race Detection for Event-driven Programs », Proceedings of the 2013 ACM SIGPLAN International Conference on Object Oriented Programming Systems Languages & Applications, ACM, OOPSLA '13re série, 2013-01-01, p. 151–166 (ISBN 9781450323741) [texte intégral lien DOI (pages consultées le 2016-12-12)]
- ↑ Boris Petrov, Martin Vechev, Manu Sridharan et Julian Dolby, « Race Detection for Web Applications », Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, ACM, PLDI '12re série, 2012-01-01, p. 251–262 (ISBN 9781450312059) [texte intégral lien DOI (pages consultées le 2016-12-12)]
- ↑ Modèle:Anglais « SDNRacer: Detecting Concurrency Violations in Software-Defined Networks », ethz.ch, 2015 [texte intégral]
- ↑ (en) OpenFlow Switch Specification, 2009, 44 p. [lire en ligne]
- ↑ Pavol Bielik, Veselin Raychev et Martin Vechev, « Scalable Race Detection for Android Applications », Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM, OOPSLA 2015re série, 2015-01-01, p. 332–348 (ISBN 9781450336895) [texte intégral lien DOI (pages consultées le 2016-12-12)]