Département

Informatique théorique

Interwikis

Sur les autres projets Wikimedia :

« Android » sur Wikipédia

Approche de programmation concurrente sous Android

Définition

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

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

Image d'une ListView, chaque ligne contenant une image différente pour représenter une situation de compétition

Situation

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

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

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

Une invalidation désigne une opération qui peut utiliser un objet qui ne serait plus dans un état valide.

Situation

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

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

Une solution serait de vérifier si l'activité est toujours dans un état valide à la fin de la tâche asynchrone.

Callback

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

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

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

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

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

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

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

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

Cette partie explique comment il est possible de capturer les processus asynchrones sous Android.

Opérations et évènements

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

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

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

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

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

CAFA

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

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

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

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)

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

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

Références

↑ 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 '14^re 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 '13^re 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 '12^re 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 2015^re série, 2015-01-01, p. 332–348 (ISBN 9781450336895) [texte intégral lien DOI (pages consultées le 2016-12-12)]

[1] 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 '14^re série, 2014-01-01, p. 316–325 (ISBN 9781450327848) [texte intégral lien DOI (pages consultées le 2016-12-12)]

[2] « Race detection for event-driven mobile applications langue non précisée », PLDI ’14, 2014, p. 326–336

[3] « droidracer - Software Engineering and Analysis Lab (SEAL), IISc Bangalore », sur www.iisc-seal.net (consulté le 12 décembre 2016)

[4] « EVENT RACER for Android », sur eventracer.org (consulté le 12 décembre 2016)

[5] 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 '13^re série, 2013-01-01, p. 151–166 (ISBN 9781450323741) [texte intégral lien DOI (pages consultées le 2016-12-12)]

[6] 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 '12^re série, 2012-01-01, p. 251–262 (ISBN 9781450312059) [texte intégral lien DOI (pages consultées le 2016-12-12)]

[7] Modèle:Anglais « SDNRacer: Detecting Concurrency Violations in Software-Defined Networks », ethz.ch, 2015 [texte intégral]

[8] (en) OpenFlow Switch Specification, 2009, 44 p. [lire en ligne]

[9] 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 2015^re série, 2015-01-01, p. 332–348 (ISBN 9781450336895) [texte intégral lien DOI (pages consultées le 2016-12-12)]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]