Forums Développement Multimédia

Les formations Mediabox
Les formations Mediabox

Grand Central Dispatch : kesako ?

Compatible MacOS 10.6. Cliquer pour en savoir plus sur les compatibilités.Par moonlightshadow, le 9 janvier 2010

Dans cet article, nous vous proposons de comprendre le fonctionnement de Grand Central Dispatch suite à une présentation que nous avons effectué à l’école, Greensource et moi-même.

Pour toute remarque ou question, vous pouvez laisser des commentaires sur le blog ou nous contacter par email: thomasdupont.35 [at] gmail.com ou greensource [at] gmail.com


Problématique

Dans l’histoire de la micro-informatique, l’augmentation de puissance a toujours été un objectif important.

Croissance par la fréquence

Jusqu’à récemment, cette augmentation s’obtenait grâce à l’augmentation du nombre de transistor. Suivant la loi de Moore, les processeurs doublaient leur fréquence tous les 18 mois. Malheureusement depuis quelques années cette montée en fréquence n’est plus possible à cause des problématiques de dissipation thermique principalement.

Évidemment des solutions alternatives sont alors apparues pour pouvoir améliorer tout de même les performances.

Croissance par le nombre de coeurs processeur

Les solutions développées furent d’augmenter le nombre d’unité de calcul sur un processeur (processeur multi-coeurs) ou encore le nombre de processeurs par machine. Cette solution, si en théorie permet en effet de continuer à faire progresser la puissance de nos machines, pose dans la réalité de nombreux problèmes.

En effet pour pouvoir profiter de cette nouvelle architecture des processeurs il est nécessaire d’adapter le logiciel. Pour qu’une architecture multi-coeurs soit pleinement utilisée, il faut que les calculs soient effectués en parallèle et non plus de manière séquentielle. Or adapter ou créer un logiciel pour qu’il effectue certaines tâches en parallèle reste assez difficile et surtout source de beaucoup de problèmes.



État de l’art

Programmation manuelle des threads

Aujourd’hui la plupart des solutions reposent sur une gestion manuelle des threads, c’est à dire que c’est le programmeur qui s’occupe de cette tâche au sein de son application.

Concept

Pour chaque partie de son application qu’un programmeur souhaite rendre concurrente aux autres, il doit déclarer un nouveau thread, le lancer, lui donner une priorité mais surtout vérifier partout où cela était nécessaire que les accès concurrents aux données ne poseraient pas de soucis.

Limitation

Une gestion des threads au niveau de l’application pose un problème: l’application n’a pas une vision globale des ressources systèmes, elle ne peut donc pas faire de choix judicieux par rapport aux priorités des threads ainsi que pour l’allocation des ressources.

D’autres part, laisser la charge de la gestion des threads au programmeur est très pénible pour celui-ci. Aujourd’hui le développement d’applications de haut niveau se fait à un niveau d’abstraction assez élevé, or la gestion des threads se situe à un niveau assez bas. Sans compter le risque très élevé d’erreurs.


Introduction de la gestion des threads par le système

Une solution aux problèmes soulevés précédemment est de laisser le système gérer la concurrence.

Concept

Le principe est d’inscrire une tâche atomique à effectuer dans une file d’attente gérée par le système d’exploitation. C’est donc le système d’exploitation qui allouera à chaque tâche les ressources adaptées au moment le plus opportun.

Avantages

Cela parait en effet assez logique que ce soit le système qui gère cette ressource puisque c’est lui qui a une vue d’ensemble sur les ressources nécessaires. C’est donc lui le mieux placé pour gérer ces ressources.

Pour le programmeur la tâche est aussi simplifiée car il lui reste désormais seulement à créer des blocs de code et de les ajouter à une file d’exécution. C’est le système qui se chargera des problèmes de concurrence.



Grand Central Dispatch

Grand Central Dispatch est un outil OpenSource inventé par Apple pour mettre en oeuvre cette gestion des threads par le système.
Il est basé sur une librairie C (donc d’assez bas niveau), mais offre également, pour ceux qui sont allergiques au C, une API haut niveau en Objective-C.

Les blocks

Avant d’attaquer directement Grand Central Dispatch, nous allons voir un peu plus une extension au langage C créé par Apple pour Grand Central Dispatch. Il s’agit des blocks. Un Block regroupe un ensemble d’instructions.

^{ printf("hello "); printf("world!"); };

Dans cet exemple on voit deux instructions intégrées au sein d’un block.

En plus de regrouper des instructions, les blocks peuvent prendre des paramètres et rendre un résultat.

void (^aBlock)(int) = (int value){ printf("valeur : %i",value); };
aBlock(3);

Dans cet exemple on déclare un block aBlock prenant un paramètre int et ne rendant aucun résultat. Ce block va afficher cette valeur. Comme on peut le voir à la deuxième ligne, l’exécution d’un bloc est très simple.

Vous vous dites peut-être ”mais quel est l’avantage d’un block par rapport à une fonction ?” . En effet, les deux concepts sont assez proches. Il y a deux différences principales : la déclaration d’un block se fait inline et anonymement ce qui est plus rapide et moins lourd que la mise en place d’une fonction. L’autre différence est qu’un block peut avoir accès aux variables accessibles à la porté englobante de ce block.

libdispatch

Libdispatch est la coeur de Grand Central Dispatch. Il s’agit de la bibliothèque C pour la gestion des threads dont le but est d’abstraire les threads de programmeur.

Le principal outil de libdispatch se nomme les Dispatch Queues.

Une Dispatch Queue va gérer un ensemble de blocks et demander au système de se charger de l’exécution de chacun d’eux. C’est en effet le système qui va choisir le nombre de threads à créer ainsi que la priorité de chacun d’eux, etc…

Il existe différents types de Dispatch Queues, dont principalement :

  • Private Dispatch Queue (serial)
  • Global Dispatch Queue (concurrent)

Les Private Dispatch Queues vont exécuter de manière séquentielle les blocks (en FIFO: First In – First Out).

dispatch_queue_t myPrivateQueue = dispatch_queue_create("MyQueue", null);

Les Global Dispatch Queues vont exécuter de manière simultanée les blocks. Le nombre réel de blocks qui seront exécutés à un instant donné va dépendre des conditions du système. Une différence avec les privates queues est qu’on ne peut pas créer de global queue, mais on peut utiliser 3 différentes global queues déjà existantes.

dispatch_queue_t myGlobalQueue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);

Il existe plusieurs manières d’ajouter un block à une Dispatch Queue :

  • Ajout synchrone
  • Ajout asynchrone
  • Ajout itératif

L’ajout synchrone va ajouter un block à une queue et attendre que ce bloc soit exécuté avant de reprendre la main.

dispatch_sync(myGlobalQueue, ^{ aBlock(3); });

A l’inverse l’ajout asynchrone va ajouter un Block à une queue et va continuer le traitement immédiatement.

dispatch_async(myGlobalQueue, ^{aBlock(3); });

Le dernier type d’ajout est un peu particulier et permet de paralléliser les boucles.

for (i=0 ; i < count ; i++) {
    results[i] = do_work(i);
}

Si par exemple nous avons une boucle dont chaque traitement ne dépend pas des traitement précédents, nous pouvons la paralléliser.

dispatch_apply(count, myPrivateQueue, ^(size_t i){ results[i] = do_work(i); });

Cette fonction permet d’ajouter à la queue le bloc passé en troisième paramètre exactement « count » fois en lui passant les valeurs de 0 à « count »-1.

Il existe d’autres outils associés aux Dispatch Queues, à savoir:

  • Dispatch Groups
  • Dispatch Semaphores
  • Dispatch Sources

Les Dispatch Groups permettent la synchronisation. En effet il est possible d’attendre que tous les blocks ajoutés à un même groupe soient exécutés.

Les Dispatch Semaphores sont une mise en oeuvre de sémaphores classiques. Ils permettent donc de restreindre l’accès à une ressource à un nombre précis de threads. Une différence dans Grand Central Dispatch est que si on veut restreindre l’accès à 1 seul thread à la fois, on n’est pas obligé d’utiliser les sémaphores, mais il nous suffit d’ajouter tous les blocks qui veulent y accéder dans une private queue. Les blocks seront donc exécutés de manière séquentielle, il n’y a donc aucun risque d’accès concurrent.

Les Dispatch Sources génèrent des notifications en réponse à des événements du système.


API haut niveau

Pour ceux qui n’aiment pas le C, ou tous ceux qui adorent l’Objective-C, Apple a mis en place une API haut niveau pour utiliser Grand Central Dispatch.

En réalité cette API existait avant l’arrivée de Grand Central Dispatch, mais profite maintenant de toute sa puissance. L’avantage d’avoir mis à jour leur librarie est que toutes les applications qui l’utilisaient avant MacOS X 10.6 ont juste besoin d’être recompilées pour voir leurs performances améliorées.

Cette API propose plusieurs classes, dont les principales sont :

  • NSOperationQueue
  • NSBlockOperation
  • NSInvocationOperation

Les NSOperationQueue sont une mise en oeuvre des Dispatch Queues.

Les NSBlockOperationQueue sont une mise en oeuvre de toutes les méthodes d’ajout de blocks à une queue.

La grande nouveauté vient de la classe NSInvocationOperation, en effet elle permet, pour ceux qui sont vraiment allergiques au C et qui n’aiment pas les blocks, de définir comme tâche à exécuter parallèlement toute une méthode.


Limites de GCD

Les limites de Grand Central Dispatch sont des limites communes à tous les systèmes de mise en oeuvre du parallélisme par le système (Sun, par exemple, propose une sorte d’api similaire).

Il s’agit du fait qu’on ne peut pas prendre n’importe quel logiciel et lui appliquer Grand Central Dispatch pour qu’il marche mieux, le logiciel doit avoir été conçu de manière parallèle.

De plus certaines tâches ne peuvent pas profiter de la puissance de Grand Central Dispatch, je pense notamment aux boucles dont chaque itération a besoin des calculs de l’itération précédente pour fonctionner.

Pour plus de renseignements sur Grand Central Dispatch, vous pouvez lire la documentation d’apple.