Présentation du Problème

Certaines applications (temps réel, multimédia, etc.), notamment les décodeurs jpeg , sont composées de programmes asynchrones se communiquant des données : images, sons, booléens, entiers, etc. Ces programmes peuvent être « producteurs » ou « consommateurs », le producteur place des données dans une file et le consommateur les récupère. On trouve, notamment dans les systèmes embarqués, des applications se décomposant en un réseau complexe de producteurs/consommateurs, chaque programme pouvant être à la fois producteur pour plusieurs programmes et consommateur de données produites par plusieurs programmes. Un programme se découpe en une suite séquentielle d'opérations d'envois et de réceptions de données, conformément à l'exemple de la figure 1.1.

Figure 1.1: échanges de données entre programmes

Le fait que ces programmes soient asynchrones rend indispensable l'utilisation de buffers pour le stockage des données en transit, c'est-à-dire entre le moment où elles sont écrites par le producteur et celui où elles sont lues par le consommateur. Ces buffers sont unidirectionnels et la figure 1.2 illustre ce principe. Nous allons voir que de l'ordre de ces opérations dépendent les dimensions (i.e. nombre de données pouvant y être placées) de chaque buffer, et que du mauvais choix des dimensions pourraient découler soit des inter-blocages, soit l'occupation d'une surface trop élevée par ces buffers.

Figure 1.2: Transit des données dans des buffers

Concrètement, nous avons un ensemble de programmes dont l'exécution est synchronisée par des envois de données. Tout programme est susceptible d'envoyer (resp. recevoir) des informations vers (resp. de) un autre programme. Dans les systèmes embarqués, ces données transitent par des buffers gérés de façon analogue à des fifos. A chaque buffer, sont associés un programme en écriture et un programme en lecture. Il est impossible pour un programme de lire dans un buffer vide, ou d'écrire dans un buffer plein. Cela signifie que si un programme doit écrire dans un buffer plein, elle restera en attente jusqu'à ce qu'un autre programme lise dans ce buffer. Si de même une opération de lecture doit se faire dans un buffer vide, elle restera en attente jusqu'à ce qu'un autre programme écrive dans ce buffer. Si des blocages de la sorte se produisent en cascade, le système peut s'en trouver complètement bloqué.

Un moyen de contourner les problèmes liés à une tentative d'écriture dans un buffer plein pourrait être de fixer la mémoire des buffers à un niveau exagérément élevé. Cependant la mémoire prend beaucoup de place sur les systèmes embarqués. Nous souhaiterions par conséquent, tout en garantissant que leur capacité ne sera pas la cause d'un blocage du système, minimiser la surface occupée par les buffers.

Ce sujet est actuellement étudié par mes encadrants. Sont déjà au point des heuristiques gloutonnes pour le cas général et un algorithme polynomial permettant de déterminer la solution optimale dans un cas particulier. Le contenu de ce chapitre ainsi que l'algorithme décrit dans le dernier chapitre sont extraits d'une publication d'Alix Munier et Jean-Baptiste Note[2].

Le travail que j'ai réalisé dans le cadre de ce TER se résume à :

• concevoir des structures de données permettant de modéliser le problème;
• implémenter un algorithme permettant de résoudre un cas particulier.