Un environnement pseudo—parallèle pour le système Unix
Contents
1. La valeur d une variable permet de distinguer entre la premi re ex cution et la deuxi me Une mise en oeuvre de cette technique repose par exemple sur la pr sence d un instruction d incr mentation en tant qu instruction suivante Le test de la variable permettra d orienter l ex cution volont La derni re solution utilise une instruction sp cialis e qui effectue l change en une seule instruction sauvegarde et restauration Il n y a dons plus de probl me de r ex cution La pile est implicitement utilis e pour stocker la sauvegarde Cette instruction sp cialis e existe dans tous les langages machines et est celle utilis e lors des appels de sous programme Malheureusement aucune des solutions propos es n est r alisable directement l aide d un langage volu L alternative consiste donc soit utiliser l assembleur pour r aliser les actions voulues L implantation du Vax 11 780 sous Unix 4 3 BSD choisit cette alternative en utilisant la troisi me technique S instruction sp cialis e CALLS soit utiliser les fonctions pr d finies de la biblioth que standard quand elles permettent de manipuler les registres Ainsi l implantation sur le Bull SPS7 sous Spix utilise les fonctions setimp et longjmp 6 En fait ces fonctions masquent un code utilisant l assembleur Cette implantation utilise la seconde technique la fonction setjmp retourne une valeur modifiable entre les deux ex cution2. une autre coroutine Cette action et le nom de cette coroutine doivent tre connus par d faut Une premi re possibilit est de reprendre la coroutine ayant cr e la coroutine venant de se terminer Malheureusement on ne peut pas conna tre avec exactitude l histoire de cette coroutine cr atrice Elle peut aussi bien tre elle m me termin e Il faut trouver une coroutine dont on est s r de l existence En fait il existe bien une coroutine un peu sp cifique C est la premi re coroutine du programme qui est cr e implicitement lors du lancement du programme Cette coroutine initiale est la m re directe ou indirecte de toutes les coroutines qui forment l application pseudo parall le Nous d cidons que la dur e de vie du programme lui soit li e C est dire que le programme d bute par cette coroutine initiale et finit lorsque cette coroutine se termine Lors de la terminaison d une coroutine on retournera donc le contr le cette coroutine initiale dont on sait qu elle est pr sente par d finition Ceci est r alis en d clarant une variable globale co_principale r f ren ant en permanence le contexte de la coroutine initiale et en ins rant la fin du code de chaque coroutine un appel de fonction resume co_ principale Ce terme de principale s explique par le fait que cette coroutine a pour fonction d appel la fonction main du programme En fait pour faciliter la mise en oeuvre nous cr ons une fonction
3. Pr alablement toute tude nous allons d finir quel type de syst mes parall les et d applications parall les la notion de coroutine est adapt e Pour ce faire on peut classifier dans une premi re approche les diff rents syst mes parall les avec ou sans m moire commune Les syst mes parall les m moire commune ont des processeurs qui partagent un espace commun de m morisation Les changes peuvent alors s effectuer relativement grand d bit vitesse d acc s la m moire ils sont de plus r manents conservation des informations par la m moire mais cela impose aux processeurs d tre tr s proches g n ralement situ s dans la m me machine Les machines multiprocesseurs en sont un bon exemple Dans les syst mes distribu s cet espace commun n existe pas Les changes s effectuent alors par l interm diaire d un r seau ou bus ils sont moins rapides technologie gale ils sont fugitifs ils passent sur le r seau G n ralement le m canisme d change utilise des messages L architecture du syst me est plus souple on rencontre des syst mes parall les soit situ s dans une m me machine soit loign s de plusieurs m tres plusieurs processeurs reli s par un r seau local A ces deux classes on peut habituellement associer respectivement deux modes de synchronisations Une synchronisation forte tightly coupled o les processus s changent de mani re r p t e de nombreuses informa
4. co_init si la premi re et troisi me tapes se d roulent sur la pile de l appelante la seconde tape se d roule sur la pile de l appel e Ainsi durant un bref instant la coroutine cr e a pris vie en ex cutant un code issu de la coroutine cr atrice Elle s est ex cut e en mode attach Plus tard lorsque le premier resume aura provoqu l ex cution de sa fonction 10 d appel elle sera ex cut e de mani re totalement ind pendante en mode d tach Notre environnement est peu restrictif Certaines erreurs de fonctionnements peuvent donc appara tre Nous allons proposer ici deux modifications m me de corriger ou de d tecter deux de ces erreurs le d passement de pile d une coroutine et la reprise d une coroutine termin e Le code que nous pr sentons en annexe ne poss de pas ces traitements car ils nous ont sembl peu portables ou encombrants N anmoins nous mettons la disposition des utilisateurs potentiels les renseignements suffisants pour mettre en oeuvre ces traitements Le d passement de pile est provoqu par un trop grand nombre d appels imbriqu s de sous programmes avec trop de param tres ou trop de variables locales Ce d passement peut ne pas tre d tect imm diatement et ainsi provoquer une ex cution erron e Une solution ce probl me consiste attribuer chaque coroutine un segment Les fonctions mises en oeuvre sont les primitives de la version V shmctl shmget shm
5. sur la nouvelle pile chaque l ment pour recr er la structure compatible et n cessaire la commutation nous allons utiliser ce principe pour qu automatiquement cette structure se recr e Apr s avoir sauvegard dans des variables globales les variables locales n cessaires l initialisation et sauvegard un point de reprise pour l appelante dans son descriptif setjmp le code de la fonction co_init se structure en trois tapes La premi re tape pr pare le changement de pile On y parvient en rechargeant le descriptif de coroutine dont le pointeur de pile a t modifi L ex cution de la fonction longjmp modifie la pile courante retourne au point de reprise et passe l tape suivante La deuxi me tape se d roule sur la pile de la coroutine cr e On prend soin de r tablir le pointeur de pile vers la pile de l appelante Puis on appelle la fonction co_control dont le contexte tout naturellement s empile La premi re instruction de cette fonction est un appel la fonction resume Le contexte de la fonction resume s empile tout aussi naturellement sur la pile de la coroutine cr e L ex cution de cette fonction provoque la reprise de la coroutine appelante car le pointeur de pile a t r tabli On retourne alors au point de reprise On se retrouve la troisi me tape sur la pile de la coroutine appelante la fin de la fonction co_init Durant l ex cution de la fonction
6. environnement est totalement crit en langage C et n utilise que des fonctions de la biblioth que standard du syst me Unix Il ne comporte que 3 fonctions dont le code figure en annexe CO_CONTEXT co_alloc longueur Allocation d un contexte de coroutine int longueur Taille du contexte en octets co_inif coroutine fonction param tre Initialisation d une coroutine CO_CONTEXT coroutine Contexte de la coroutine initialiser int fonction Fonction d appel de la coroutine int param tre Param tre de la fonction d appel resume coroutine in out Ex cution d une coroutine CO_CONTEXT coroutine Contexte de la coroutine reprendre int in Param tre pass la coroutine appel e int out Param tre re u de la coroutine appelante La cr ation d une coroutine consiste r server un nouvel espace pour sa pile co_alloc et initialiser cette pile avec une structure compatible avec celle du compilateur co_init La commutation entre deux coroutines revient changer le pointeur de pile resume La mise en place de l ensemble de ces fonctions et d autres plus volu es dans une librairie permet chacun d y acc der d en faciliter la mise en oeuvre et d en promouvoir l utilisation 7 Sur les ordinateurs o nous avons r alis l implantation la librairie usr lib liblocal cor a contient les principales fonctions et le fichier usr i
7. objets ce que l on nomme son contexte Le contexte est modifi lors de l ex cution de la coroutine et est sauvegard lors de la suspension de cette derni re Commuter des coroutines revient substituer au contexte de coroutine courante de l appelante celui de la coroutine appel e En fait cette commutation demande d effectuer deux op rations 1 la sauvegarde du contexte de la coroutine appelante pour sa reprise ult rieure 2 la restauration partir de la sauvegarde du contexte de la coroutine appel e Dans notre implantation on peut d finir trois types de contextes associ s aux diff rents objets manipul s par le programme Figure 1 Le contexte associ chaque sous programme contient ses variables locales ses param tres et 5 une sauvegarde du descriptif du sous programme appelant Ce descriptif est utilis lors du retour pour restaurer le contexte du sous programme appelant Chaque appel d un sous programme cr e un contexte qui lui est associ Le contexte de chaque coroutine CO_CONTEXT contient son espace propre et son descriptif CO_DESCR L espace propre chacune des coroutines est d termin par l encha nement des sous programmes et est d fini par leur contexte Le descriptif de coroutine contient une sauvegarde du jeu de registres registre compteur ordinal registre pointeur de pile registres g n raux etc Le contexte du programme comporte l espace global du programme et un con
8. sp ciale permettant d effectuer et de contr ler de mani re l gante la fois le d marrage et la terminaison d une coroutine Cette fonction sp ciale comporte en tant que premi re instruction la fonction d appel associ e la coroutine cr e et en tant que deuxi me instruction une reprise de la coroutine initiale La reprise de la coroutine initiale se fait ainsi naturellement la fin de l ex cution de la fonction d appel CONTEXT co_principale la coroutine principale void co_control fonction_d_appel argument fonction de contr le des coroutines int fonction_d_appel int argument fonction_d_appel argument fonction d appel associ la coroutine cr e resume co_principale reprise de la coroutine initiale Maintenant la premi re fonction ex cut e d une coroutine n est plus sa fonction d appel mais pour toutes les coroutines la fonction co_control Ce qui revient n anmoins au m me cette derni re fonction appelant aussit t la fonction d appel Le contexte de sous programme cr lors de la deuxi me tape de pr paration d une coroutine est donc celui de la fonction co_control Ceci simplifie la r alisation car cette fonction est unique alors que chaque coroutine peut avoir une fonction d appel diff rente 3 6 Les param tres Nous venons de voir que chaque coroutine peut poss der une fonction d appel diff rente La fonction co_control poss de donc
9. un param tre qui pr cise le nom de la fonction d appel Cependant le nom de cette fonction d appel provient du deuxi me param tre de la fonction de pr paration co_init H convient de transmettre ce nom entre la fonction co_init qui pr pare et la fonction co_control qui lance effectivement la fonction d appel Malheureusement ces deux fonctions ne s ex cutent pas dans le m me contexte ou plus pr cis ment pas par rapport la m me pile Et la pile sert pour le passage des param tres lors de 9 l appel d un sous programme Il faut donc que la fonction co_init recopie son deuxi me param tre en tant que premier param tre dans le contexte associ la fonction co_control de la pile de la coroutine cr e Cette recopie n cessite de conna tre avec pr cision la place du param tre dans la nouvelle pile Bien entendu cette recopie est n cessaire aussi pour l argument de la fonction d appel Un probl me et une solution similaire existent pour les param tres in et out de la fonction de commutation resume Le param tre in de la coroutine appelante doit tre transmis la coroutine appel e en tant que param tre out La fonction resume recopie la valeur du deuxi me param tre de la coroutine appelante dans le troisi me de la coroutine appel e Ce probl me se retrouve une troisi me fois lors de la terminaison d une coroutine La coroutine initiale devrait r cup rer la valeur de
10. ESULTAT Pointeur de contexte de la coroutine initialisee ou NULL si l intialisation de la corouline n a pu etre effecluee CO_CONTEXT gt REMARQUE Si parametre est NULL on considere que la corouline n a pas de parametre On initialise le pointeur de descriptif 16 CO_CONTEXT co_init cor __initialisee fonction parametre CO_CONTEXT cor_initialisec int fonction int parametre CO _DESCR descriptif extern void co_control i fonction du demarrage des coroutines cor_fonction fonction i 5 sauvegarde sous forme de variables globales cor_parametre parametre des variables utiles a l execution du boot cor_appelante cor_courante cor_courante cor_initialisec switch setjmp cor_appetante gt pdeser amp descriptif initialise le point de reprise pour les tapes suivantes case DEBUT_INIT Debut de l initialisation sur la pile de l appelant save_SP cor_appelante gt pdeser gt reg SP fF sauvegarde le ptr de pile de l appelante cor_appelante gt pdescr gt reg SP int cor_initialisee 2 chargement du ptr de pile de l appelee Tongjmp cor_appelante gt pdescr SUITE_INIT F passage a l etape suivante ct changement de pile case SUITE_INIT Suite de l initialisation sur la pile de l appelee cor_appelante gt pdescr gt reg SP save_SP chargement du plr de pile de l appelante co_control cor_fonction cor_para
11. Un environnement pseudo parall le pour le syst me Unix Jo l BERTHELIN Bernard COUSIN Laboratoire MASI Universit Pierre et Marie Curie 4 place Jussieu 75252 PARIS cedex 05 R sum Le pseudo parall lisme permet plusieurs applications de s ex cuter en simultan it apparente sur une m me machine Fond e essentiellement sur la notion de coroutine ce concept existe dans de nombreux syst mes et langages Nous proposons un environnement efficace et l mentaire permettant l exploitation ais e de ce concept inexistant en langage C afin de b n ficier d une approche simplifi e du parall lisme Cet environnement portable est totalement crit en langage C et n utilise que des fonctions de la biblioth que standard du syst me Unix Les valuations de performances effectu es ont permi de d gager une baisse importante de l utilisation du processeur gr ce cet environnement Mots cl s pseudo parall lisme parall lisme coroutine syst me Abstact The quasi parallelism enables several applications in one processor to be simultaneously executed Based on the coroutine notion this concept is used in numerous systems and languages In order to have a straightforward approach of parallelism we propose an efficient and basic environment It allows an easily use of the coroutine concept which is non existent in the C language This portable environment in its entirety is coded in C language and only uses standard library
12. ables globales utitisecs static CO_CONTEXT cor_appelante cor_ courante amp cor_principale static int cor_fonclion cor_parametre save_SP t CO_AELOC Lenght DESCRIPTION Allouc un contexte de corouline ENTREE Int lenght taille de la pile demandce en octets RESULTAT Pointeur de contexte de coroutine ou NULL si le contexte n a pas pu etre allouc REMARQUE Une verification de la taille de la pile demandee est cffectuce Si la taille est negative ou nulle ou trop petite lenght lt MINSTACK une pile minimum correcte est allouee lenght MINSTACK M CO_CONTEXT co_alloc lenght int lenght CO_CONTEXT pile lenght lenght amp TAILLE_ELEM 1 taille de l allocation en nombre entier if lenght lt MINSTACK lenght MINSTACK verficatiion de taille de pile if pile CO_CONTEXT malloc lenght sizeof CO_DESCR lt 0 allocation du contexte retum CO_CONTEXT NULL ifdef DEBUG printf x co_alloc x n char pile lenght lenght endif retum CO_CONTEXT X char pile lenght CO_INIT Cor_initialisee Fonction Parametre DESCRIPTION Initialise le contexte d une coroutine ENTREE CO_CONTEXT cor_initialisce pointeur de contexte de la coroutine a initialiser z int fonction adresse de la fonction d appel de la coroutine ig int parametre pointeur sur un parametre initial de la coroutine R
13. ag s 11 3 9 L Evaluation des performances Nos mesures de performance ont montr que le temps moyen d ex cution d un resume est de 0 05 milisecondes Alors que celui des m canismes quivalents sous le syst me Unix taient de 0 45 milisecondes pour le write read d un pipe De m me le temps moyen d ex cution d un initialisation d une coroutine l aide de la fonction co_init se monte 0 08 milisecondes alors que ce temps est de 0 42 milisecondes pour la cr ation d un nouveau processus avec la fonction fork et de 25 6 milisecondes pour un changement de code avec la fonction execl Nous avons tudi les temps d ex cution d une application de transfert de caract res utilisant soit deux processus et un pipe soit deux coroutines Le temps syst me est nettement pr pond rant dans l option avec deux processus Les primitives de lecture et d criture du pipe read et write s ex cutent en mode syst me Alors que c est l inverse avec les deux coroutines le temps d ex cution en mode syst me est pratiquement nul Cependant le cumul de temps d ex cution CPU time donne toujours un net avantage en faveur des coroutines un gain d environ 900 N anmoins nous avons constat la possibilit d un effet pervers de cette inversion d attribution du temps entre le mode syst me et le mode usager Un processus ne consommant que du temps syst me risque d obtenir une plus forte priorit qu un proces
14. ager code donn es globales tas Et chaque coroutine est assur e de poss der toutes les propri t s inh rentes au langage C r entrance r cursivit localit des variables sous programme param trage Cependant le compilateur impose les contraintes suivantes sur notre implantation des coroutines L ensemble du code toutes les fonctions est accessible toutes les coroutines N importe quelle fonction peut donc tre utilis e par n importe quelle coroutine Puisque dans le langage C il n y a aucun moyen d imbriquer les d claration de fonctions au contraire d Algol ou de Pascal Cependant pour chaque coroutine on distingue une fonction particuli re la fonction d appel La fonction d appel est la premi re fonction ex cut e lors du d marrage de la coroutine De mani re similaire il n existe que deux espaces de donn es dans un programme crit en C les donn es globales l ensemble des sous programmes et les donn es locales chaque sous programme Il en sera de m me pour nos coroutines Ainsi il n est pas possible cause du compilateur d avoir des donn es propres chaque coroutine et cependant globales l ensemble de ses sous programmes Le choix d un autre langage support aurait permis nous en sommes certains de lever sans probl me l ensemble de ces contraintes N anmoins le d veloppement de notre environnement pseudo parall le sur un syst me Unix nous a conduit conserver le langage C Notre
15. angage cible 3 Le bas de pile est compl t par un pointeur r f ren ant le descripteur de coroutine c est dire pointant sur le haut de pile Dans cette position le pointeur peut tre consid r comme une variable locale du sous programme appelant cens avoir appel la coroutine C est ainsi que la fonction co_init pr pare du contexte d une coroutine nouvellement cr e Les deux premi res structures d pendent videmment des particularit s du processeur de son jeu de registres et de celles du compilateur de sa structure d appel de sous programme Par souci d homog n it il convient de reprendre la coroutine cr e non pas la premi re instruction de sa premi re fonction sa fonction d appel mais comme toutes les autres coroutines lors de leur reprise en fin de la fonction de commutation La deuxi me tape 2 de la pr paration est modifi e comme suit 2a Cr ation d un contexte pour le sous programme de commutation resume 2b Cr ation d un contexte pour le sous programme d appel 3 5 La Terminaison d une coroutine Les coroutines se passent entre elles explicitement le contr le du processeur par l interm diaire de la fonction de commutation resume Cependant que se passe t il lors de l ex cution de la derni re instruction associ e une coroutine On aboutit un tat incoh rent car on retourne vers un sous programme qui n existe pas Il convient plus t t de rendre la main
16. at shmdt Le segment contient le contexte de la coroutine sa pile Tout d bordement entra ne une violation des limites du segment ce qui est imm diatement d tect La r cup ration du signal mis lors de cette d tection permet d incriminer la coroutine courante et de rem dier au probl me L appel d une coroutine termin e est un risque probable d s lors que l on ne peut effectuer aucun contr le lors de la compilation sur l existence suppos e d une pile Une solution simple mais encombrante consiste conserver le contexte de coroutine apr s sa terminaison et placer dans la fonction co_control un message d erreur apr s la reprise de la coroutine principale resume co_principale Ainsi toute reprise ult rieure aura pour effet de provoquer l ex cution de ce traitement d erreur 3 8 Le Portage Le portage de notre environnement initialement con u sur Bull SPS7 sous Spix proche de la Version V d AT amp T a t effectu sur Yax 11 780 puis sur Sun 3 50 sous 4 3 BSD Il s est av r qu il est impossible d utiliser les fonctions de la biblioth que standard setjmp et longjmp du Vax Il est interdit de modifier le contenu de la structure jmp_buf contenant le jeu de registres car la fonction longjmp effectue un contr le lors du rechargement Toute modification aboutit in vitablement la fonction longjmperror et au message longjmp botch Nous avons en fait r alis deux implantation
17. ation l change de contextes s effectue en changeant les piles c est dire l espace de donn e associ aux coroutines la valeur des registres g n raux et le code En fait les espaces relatifs la pile et l instruction ex cuter sont eux m mes r f renc s par deux registres le 6 registre pointeur de pile et le registre compteur ordinal Ce qui revient dire que commuter deux coroutines c est changer la valeur de l ensemble des registres entre la coroutine appelante et appel e Sauvegarder et restaurer la valeur de la plupart des registres est tr s simple Cependant tous les informaticiens notamment ceux familiers avec le langage machine savent que la manipulation du compteur ordinal est dangereuse Car il progresse sans arr t avec l ex cution du code en indiquant la prochaine instruction ex cuter Ainsi lorsque l on ex cute l instruction de sauvegarde du compteur ordinal la valeur sauvegard e pointe sur l instruction suivante De ce fait cette instruction a toutes les chances d tre ex cut e deux fois La premi re fois dans la suite normale l instruction de sauvegarde la deuxi me fois lors de la restauration apr s une reprise de la coroutine Cette r ex cution peut tre vit e l aide d une des trois techniques suivantes On saute les instructions suivantes en augmentant la valeur du compteur ordinal avant sa sauvegarde La r ex cution red marrera quelques instructions plus loin
18. eur ordinal sauvegarde et restauration du descriptif de sous programme La connaissance de ces m canismes nous est indispensable pour comprendre l implantation propos e et peut permettre au lecteur de mieux utiliser les langages de programmation Une valuation des performances nous a permis de mettre en vidence le co t important de la cr ation et de la gestion des processus au regard de celui des coroutines et de rappeler l int r t du pseudo parall lisme vis vis du vrai parall lisme si le temps de communication est comparable au temps de calcul demand Cet environnement nous a permis de d velopper un important ensemble d applications Un simulateur de syst me d exploitation utilis des fins p dagogiques en illustration d un cours de ma trise d informatique plusieurs milliers de lignes Un diteur utilisant le multi fen trage chaque fen tre est associ e une coroutine qui poss de ainsi son contexte propre 12 L bauche d un compilateur chaque phase du compilateur est associ e une coroutine Un traducteur de Modula 2 en C les coroutines sont utilis es pour implanter le module Process associ l ex cution pseudo parall le en Modula 2 Il est performant car la cr ation et la commutation entre coroutines ne demande l ex cution que de quelques instructions valuation du co t environ 25 micro secondes H est minimal il ne comporte que 3 fonctions de quelques dizaines de
19. functions of the Unix system The evaluation shows the good performance of our quasi parallel environment Keywords quasi parallelism parallelism coroutine system 1 Introduction L volution des outils de programmation doit suivre celle de l architecture machines parall les et syst mes r partis et celle des applications de plus en plus interactives r agissant des v nements externes et asynchrones C est pourquoi nous pr sentons un environnement propice la programmation pseudo parall le ce qui nous permettra d introduire les principaux concepts li s au parall lisme Les efforts de conception des syst mes d exploitation ont provoqu l mergence de la notion de coroutine notamment pour la gestion en temps partag Cette notion la base de la gestion du pseudo parall lisme permet plusieurs applications de s ex cuter en simultan it apparente sur une m me machine Elle existe de mani re vidente ou sous jacente dans de nombreux langages Simula 1 Modula 2 2 Scheme Smalltalk 3 etc et applications multi fen trage compilateur syst me d exploitation etc Le noyau du syst me Unix est lui aussi con u autour de cette notion Malheureusement ce m canisme de coroutine est inaccessible l utilisateur de ce syst me C est pourquoi nous proposons un environnement simple crit en langage C permettant l exploitation ais e de cette notion 2 Les coroutines 2 1 Pr sentation
20. lignes Il est l mentaire car il permet de r aliser parfaitement de nombreux m canismes de synchronisation ou de communication cf les nombreux exemples r alis s producteur consommateur moniteur s maphore simulation de pipe etc et est capable de s adapter de nombreuses politiques de gestion ou d encha nement des coroutines Il est portable nous avons d j implant notre environnement sur diff rentes machines Bull SPS7 Vax 11 780 et Sun 3 50 Cet ensemble est en voie d accroissement sur d autre machines Unix Gould Apple etc Simple portable peu co teux adaptable notre environnement respecte la philosophie nixienne et il pousse malheureusement la ressemblance au langage C jusqu permettre tous les abus d utilisations Bibliographie 1 O J Dahl B Myhrhaug K Nygaard Some features of the Simula 67 language 24 conference on the applications of simulation New York 1968 2 N Wirth Programming in Modula 2 Springer verlag 1982 3 A Goldberg D Robson Smalltalk 80 language and its implementation Addison Wesley 1983 4 B Stroustrup The C programming langage Addison Wesley 1987 S1Vax 11 architecture reference manual Digital Equipment corporation May 1982 6 Spix system programmer reference manual Bull November 1986 7 J Berthelin B Cousin Manuel d utilisation de l environnement pour le pseudo parall lisme version 1 0 Paris Octobre 1988 13 Figure 1 Contex
21. metre execute le demarrage de Ja coroutine case FIN_INIT break Fin d initialisation retour sur la pile appelante default retum CO_CONTEXT NULL f Etape illegale ifdef DEBUG printf x co_init x x x n cor_initialisce cor_inilialisee fonclion parametre endif return cor_initialisce P CO_CONTROL Fonction Parametre Fonction Locale DESCRIPTION Initialise la pile de la coroutine en effectuant un debut d execution s Initialise e descripteur de la coroutine en fixant un point de reprise z Execute la corouline puis reprend la corouline principale ENTREE Int fonction adresse de la fonction d appel a Int parametre pointeur sur un parametre initial de la coroutine RESULTAT Sans REMARQUE L execution de la coroutine ne sera faite que lors du prochain resume I static void co_control fonction parametre initialise la pile int fonction int parametre int valeur_retournee ifdef DEBUG printf coroutine fonction x parametre endif resume cor _appelanie FIN_INIT amp valeur_retournec 1 initialise le decriptif de l appelec if parametre int NULL passe un parametre si besoin resume amp cor_principale fonction amp valeur_retoumncc ct execute la fonction d appel else puis reprend la coroutine principale resume amp cor_principale fonclion parametre amp valeur _ ret
22. n de nombreux probl mes Elle seule semble propice r pondre nos nombreuses contraintes Implantation dans un syst me Unix pour permettre une grande diffusion Cependant ce choix pr sente quelques difficult s car les processus Unix sont s quentiels Les chapitres suivants montreront comment contourner ces probl mes Ecriture en langage volu pour assurer une plus grande portabilit et pour permettre une mise en oeuvre ais e Efficacit tant en occupation m moire et nombre de fonctions de base qu en temps d ex cution Ce qui permet notre environnement de ne pas perdre les avantages inh rents la simplicit de la notion de coroutine Notre environnement doit tre stable et coh rent car la mise au point d applications parall les est beaucoup plus difficile que pour les applications s quentielles Notre environnement veut promouvoir l utilisation de coroutine H doit donc tre d un emploi ais pour faciliter l abord de la programmation pseudo parall le aux novices Un programme crit en langage C se caract rise par quatre espaces le code les fonctions les donn es les variables globales la pile les variables locales et les param tres le tas les variables dynamiques Il suffit d attribuer chaque coroutine une pile distincte pour permettre une ex cution pseudo parall le de plusieurs coroutines l int rieur d un m me programme Cette attribution permet toutes les coroutines de part
23. nclude local cor h contient les types et constantes Un fichier d aide en ligne usr cat_man p_man man3 local coroutine compl te notre environnement pour le pseudo parall lisme 3 R alisation 3 1 Introduction Comme nous venons de le dire le m canisme de base de commutation des coroutines est fourni par un appel la fonction resume Cette fonction permet de suspendre l ex cution de la coroutine appelante et d encha ner sur l ex cution de la coroutine appel e Cette derni re est reprise l endroit du code o elle avait auparavant t suspendue par un pr c dent appel de la fonction resume On note l unicit et la sym tricit de ce m canisme au contraire de celui associ au sous programme qui est double appel et retour et de ce fait distingue appelant et appel De plus le contexte associ chaque occurrence d un sous programme ne dure que le temps de l appel de ce sous programme tandis que celui associ aux coroutines est r manent Ainsi les objets locaux aux sous programmes sont cr s chaque appel d truit au moment du retour d appel le code lui m me red marre syst matiquement au m me point d entr e chaque appel du sous programme Par contre durant la suspension d une coroutine les objets locaux appartenant cette coroutine sont conserv s et l ex cution reprend l o on l avait suspendue 3 2 Le Contexte de coroutine CONTEXT On associe chaque coroutine l ensemble de ses
24. nt de la commutation et de le d finir comme une variable locale de la fonction de commutation On s aper oit que la totalit du contexte d une coroutine est m moris e dans sa pile Une coroutine sera donc r f renc e par l adresse de sa pile plus exactement par l adresse du bas de pile fournie au moment de sa r servation Il faut que le descriptif de la coroutine quand elle est suspendue soit r f renc par un pointeur Car lors de la commutation on recharge les registres du processeur avec les valeurs sauvegard es dans le descriptif Or la situation du haut de pile tant minemment variable il faut la localiser avec pr cision Ce qui est fait en pla ant en bas de pile qui est une adresse fixe une variable contenant lors de chaque suspension l adresse du haut de pile La Figure 2 illustre ces propos On trouve gauche la structure habituelle d une pile d un langage volu droite celle modifi e d une pile associ e une coroutine lorsqu elle est suspendue L implantation en C d finit les types suivants CO_CONTEXT est le type associ au contexte de coroutine Les fonctions retournent ou ont des param tres de ce type CO_CONTEXT co_alloc CO_CONTEXT co_init resume cor CO_CONTEXT cor CO_DESCR est le type associ au descriptif de coroutine La variable du bas de pile pointant sur le descriptif se d clare donc CO_DESCR pdescr 3 3 La Commutation de coroutines resume Lors de la commut
25. oulev s lors de la commutation de coroutine Mais que se passe t il lorsqu une coroutine vient d tre cr e Elle ne poss de pas encore de contexte Elle n existe pas on ne peut donc pas la reprendre Il faut pr parer le contexte n cessaire son d marrage sa premi re reprise qui doit tre compatible avec la fonction de commutation Il faut que le premier resume trouve une organisation interne de la pile compatible avec celle habituellement attendue par cette fonction Cette organisation est d termin e par les contraintes d implantation de la fonction de commutation telles qu elles ont t d finies au chapitre pr c dent 1 Il faut trouver en haut de pile le descriptif de la coroutine Ce descriptif est utilis pour restaurer les registres lors de la reprise La structure de ce descriptif est d termin e par la technique employ e pour effectuer la commutation de coroutine 2 Il faut cr er un contexte de sous programme pour la premi re fonction de la coroutine fonction d appel avec ses variables locales ses param tres et son descriptif de sous programme Ce descriptif est cens correspondre au sous programme appelant qui aurait d appeler la coroutine cr e En fait ce sous programme appelant n existe pas vraiment il n est utile que pour ex cuter la coroutine cr e dans un environnement local et compatible La structure du contexte de sous programme est impos e par celle employ e par le compilateur du l
26. ournec lors du retour de la fonction 17 fs RESUME Cor_appelee In Out DESCRIPTION Reprend l execution d une coroutine en lui passant un parametre si besoin ENTREE CO_CONTEXT cor_appelee pointeur de contexte de la coroutine appelce int in pointeur sur le parametre passe a la coroutine appelee int out pointeur sur la variable qui contiendra le parametre passe a la coroutine appelce RESULTAT Sans mais la variable out permet de recuperer le parametre in entre coroutine REMARQUE La pointeur out permet de recuperer un parametre in passe par la coroutine appelante resume cor_appclee in out CO_CONTEXT cor_appelee int in out CO_DESCR descriptif ifdef DEBUG print resume x x x n inticor_appelee int in int out endif cor_appelante cor_courantc m a j la nouvelle coroutine courante cor_courante cor_appelee descriptif ctat ETAT_ZERO initialise le nombre de passage le if suivant ZERO out int setjmp cor_appelante gt pdeser amp descriptif fixe un point de reprise pour l appelante if descriptif etat ETAT ZERO f si premier passage descriptif ctat ETAT UN initialise le nombre de passage le if UN longjmp cor_appelee gt pdescr in saute au point de reprise de la coroutine appelec LL 7 Soo oook i kK oak ok ooo o k okk ichier cor h ARR ER NERO EE CE OO incl
27. rall le En fait l immense majorit des ordinateurs poss de cette caract ristique Le troisi me type est possible sur les syst mes ne poss dant qu un seul processeur de traitement Il consiste multiplexer dans le temps les diff rents processus ex cuter sur le seul processeur Les ordinateurs autorisant une gestion multi t ches poss dent un syst me d exploitation permettant ce multiplexage de la puissance de traitement du processeur entre les diff rents processus appel gestion en temps partag time sharing Ce type de parall lisme n est qualifi que de pseudo parall lisme Car le parall lisme apparent entre les processus il existe effectivement plusieurs processus en cours d ex cution dispara t d s que l on regarde au niveau des instructions tout moment il n y a qu une instruction d un des processus en ex cution I n y a qu un seul processeur qui ne supporte qu une seule ex cution s quentielle Nous d veloppons notre environnement pour ce troisi me type de parall lisme Notre environnement veut promouvoir l utilisation du pseudo parall lisme qui s av re dans de nombreuses applications propice et efficace Il permet au programmeur de b n ficier d une approche simplifi e du parall lisme Notre objectif est d offrir une alternative aux trois fa ons de programmer suivantes Une programmation en langage s quentiel strict utilisant un seul processus Dans cette approche la conception de certaine
28. retour de la fonction d appel de la coroutine qui se termine Dans la fonction co_control lors de la reprise de la coroutine principale la valeur de retour de la fonction d appel est attribu au param tre in Cet instant transitoire o l on est entre deux piles oblige d clarer certaines des variables globales de l environnement Ces variables sont utilis es par les deux fonctions co_init et resume 3 7 Les Am liorations Nous avons d fini au chapitre 3 3 traitant de la pr paration et pr cis au chapitre 3 4 traitant de la terminaison les actions n cessaires la cr ation d une coroutine Nous en d duisons qu il faut bien conna tre la structure de la pile celle du processeur le fonctionnement de l appel et de retour de sous programme L ensemble de ces connaissances est difficile acqu rir Nous allons tenter d all ger la charge de travail du porteur de l environnement en constatant qu on pourrait automatiquement cr er un nouveau contexte de coroutine en jouant astucieusement avec le pointeur de pile Par exemple si avant d appeler un resume on modifie le pointeur de pile la sauvegarde du descriptif de coroutine est effectu e sur la nouvelle pile De m me si avant l appel d un sous programme on modifie le pointeur de plie le contexte du nouveau sous programme est empil sur la nouvelle pile C est ainsi que nous proposons de modifier la fonction co_init Au lieu d empiler la main
29. s la premi re ex cution la valeur retourn e est nulle la seconde la valeur est celle du dernier param tre de la fonction longjmp Dans le cas de l implantation sur SPS7 le code de la fonction de commutation devient resume descr_appel e CO_DESCR descr_appel e Descriptif de la coroutine appel e CO_DESCR descr_appelante Descriptif de la coroutine appelante int setjmp La fonction setjmp retourne O ou la valeur du dernier param tre de la fonction longjmp if setimp descr_appelante 0 Sauvegarde de l appelante longjmp descr_appel e 1 Restauration de l appel e le param tre doit tre 0 else Code ex cut lors du deuxi me retour On peut remarquer que toutes les commutations se passent dans la m me fonction celle qui commute ici resume sur la m me instruction celle qui modifie le compteur ordinal Ainsi toutes les coroutines se suspendent sur cette instruction et reprennent sur ce m me point Ces similitudes facilitent grandement la commutation on sait d avance d o on part et o on arrive Lors de leur reprise le comportement des diff rentes coroutines diverge en fonction de l empilement des contextes de sous programmes repr sentant la dynamique d ex cution des diff rentes coroutines et de la valeur de leurs variables locales 3 4 La Pr paration des coroutines co_init Nous venons de r soudre les probl mes s
30. s applications devient vite difficile et leur maintenance inextricable Surtout si ces applications g rent plusieurs entit s poss dant un contexte propre mais volutif et interagissent des instants variables suivant l volution de leur ex cution Les coroutines proposent une fa on plus simple et plus naturelle d appr hender ces applications Une programmation en langage s quentiel utilisant une coop ration de plusieurs processus Dans cette approche il est co teux de faire partager aux diff rents processus un m me contexte car les m canismes disponibles pipe socket segment partageable s maphore signaux etc ont souvent une mise en oeuvre complexe et sont parfois mal adapt s aux besoins particuliers Enfin la gestion des diff rents processus est assur e par le scheduler du syst me ce qui naturellement est beaucoup moins souple et moins efficace que celle offerte par notre environnement qui laisse enti re libert au programmeur Une programmation dans un langage int grant les concepts de pseudo parall lisme Ces langages sont souvent d un niveau conceptuel plus lev et int grent des notions suppl mentaires qui risquent de d router le n ophyte Notre environnement n introduit aucune contrainte suppl mentaire par rapport au langage C pas de nouveaux mots clefs pas de contraintes d utilisation et n offre qu un seul et nouveau concept les coroutines On a besoin de pseudo parall lisme directemen
31. s sur Vax Pour la premi re implantation nous avons choisi de r crire en assembleur une fonction longjmp notre go t C est dire rechargeant les registres sans contr le En fait nous l avons d calqu e de la pr c dente version en enlevant les tests g nants Pour la deuxi me implantation nous avons d cid de r crire la totalit de la fonction resume en assembleur et de ne pas utiliser les fonctions setjmp et longjmp Nous avons choisi d utiliser alors la deuxi me technique d crite au paragraphe 4 2 pour effectuer la commutation de coroutine Cette technique utilise l instruction sp cialis e d appel de sous programme Calls pour effectuer en une seule instruction la sauvegarde et le restauration du jeu de registres Cette deuxi me implantation a pour avantage d tre l g rement plus rapide que la pr c dente Le portage sur Sun n a consist qu en une modification de la valeur de la constante r f ren ant le pointeur de pile dans la structure de sauvegarde des registres Il est pass de 12 14 L int gralit du code a t conserv L ensemble de ces portages semble confirmer la justesse de nos affirmations Il est possible dans toute machine Unix d avoir un environnement identique favorisant la programmation du pseudo parall lisme Le portage de cet environnement n cessite g n ralement que quelques judicieuses adaptations De nouveaux portages sur Gould et sur Macintosh sont an et d j envis
32. sus consommant la m me somme de temps mais en mode usager Car la priorit d ex cution d un processus peut n tre calcul par le scheduler qu partir du temps de consommation du CPU en mode usager Cependant les coroutines utilisant moins le processeur si le b n fice n en revient pas directement son utilisateur peu d am lioration du temps de r ponse du fait de l accroissement de la priorit l ensemble des utilisateurs y retrouvent leur compte Nos mesures mettent en vidence les avantages des coroutines Gestion interne donc optimale de l encha nement des coroutines ce qui minimise le temps d ex cution Alors que les processus sont contr l s par le scheduler du noyau Les coroutines partagent un espace commun les variables globales ce qui minimise le temps et l espace n cessaire la transmission des informations Cette transmission p nalise les processus sous Unix 4 Conclusion Notre tude par une pr sentation d taill e de l ensemble des probl mes rencontr s et une discussion des diff rentes solutions possibles veut veiller le lecteur aux probl mes du syst me du pseudo parall lisme et permet de rappeler des caract ristiques propres la gestion des langages volu s Les m canismes relatifs aux sous programmes sont tout particuli rement abord s m morisation et acc s aux param tres m morisation et acc s aux variables locales conflit lors de la manipulation du compt
33. t en C sans l interm diaire d un compilateur disproportionn avec certaines applications et qui risque de poser des probl mes de portabilit 2 2 D finition Une coroutine est une unit l mentaire d ex cution s quentielle poss dant en propre un contexte local g n ralement constitu d une pile et partageant avec les autres coroutines un espace global une m moire commune Une coroutine l appelante appelle une autre coroutine 3 l appel e et lui c de son droit d ex cution en se suspendant H y a donc toujours au plus une seule coroutine en activit les autres tant toutes suspendues L encha nement des ex cutions des coroutines est exprim de mani re explicite chaque coroutine poss de un nom unique et connu de tous L ex cution d une coroutine peut tre per ue comme l ex cution d un sous programme qui peut tre interrompue pour ex cuter une autre coroutine puis reprise ult rieurement Plus pr cis ment un sous programme a deux m canismes de base l appel nommant explicitement le sous programme appel et le retour intervenant implicitement en fin de code de l appel Alors que la coroutine ne poss de qu un m canisme commun ment appel resume servant la fois d appel de reprise et de retour en nommant explicitement chaque fois la coroutine suivante qui est reprise 1 o elle s tait arr t e La notion de coroutine a d j prouv sa grande g n ralit et son adaptatio
34. tes espaces et descriptifs Contexte du Descriptif programme d une coroutine Descriptif du processus Contexte d une coroutine Espace global du programme Espace local d un sous programme Descriptif d un sous programme Espace de stockage des donn es Contexte de programme locales ou globales C Contexte de coroutine C Descriptifs contenant les informations de gestion relatives au programme aux coroutines ou aux sous programmes 14 Figure 2 La structure d une pile de coroutine haut de pile Descriptif de coroutine variables locales RSA RS ER Contexte d un appelant sous programme nom de la coroutine adresse de sa pile bas de pile Pointeur de haut de pile 15 PAR EEE RO OO OO c J Berthelin amp B Cousin Sun Oct 23 15 23 25 MET 1988 z Environnment des coroutines x CONSEILS POUR LE PORTAGE La mise en oeuvre des coroulines est dependante de la machine 11 faut donc 1 Analyser le code gencre par l utilisation des fonctions e setjmp et longjmp pour mettre en evidence dans la structure retoumee le champ contenant le pointeur de pile s 2 Si votre machine a une fonction longjmperror gt reccrire la fonction longjmp en supprimant le code qui maintient l integrite de la pile 3 Changer la definition de SP dans le fichier cor h AO CE AE EC ONE include lt local cor h gt CO_CONTEXT cor principale Les vari
35. texte pour chacune des coroutines du programme L espace global contient les variables globales dynamiques ou externes accessibles par l ensemble des coroutines On place habituellement dans le contexte de programme les informations relatives au processus supportant le programme descriptif de processus registre de gestion de la m moire registre d tat etc Il convient de rappeler que la plupart des implantations des langages volu s utilise une pile pour stocker les variables locales les param tres et pour sauvegarder les contextes d ex cutions lors de l appel de sous programme Car la pile propose une structure propice la gestion dynamique inh rente aux appels imbriqu s de sous programme Enfin les machines actuelles offrent des instructions sp cifiques pour g rer efficacement l empilement lors de l appel de sous programme et le d pilement lors du retour Les moments o les appels et les retours de sous programme s effectuent sont d termin s durant l ex cution Donc pour pouvoir b n ficier de la notion de sous programme l int rieur des coroutines il est n cessaire que chacune des coroutines poss de en propre une pile Plut t que d avoir d un c t la pile contenant les contextes des sous programmes m morisant la dynamique de leurs appels et de l autre le descriptif de coroutine il nous est possible de les regrouper l int rieur de la pile Il suffit pour que le descriptif se trouve en haut de pile au mome
36. tions Une synchronisation faible loosely coupled o les processus des diff rents processeurs ne partagent que peu d informations pour mener bien leur ex cution H est clair que la premi re classe d architecture r pondra mieux aux besoins du premier mode de synchronisation N anmoins cette architecture bien que plus performante est souvent plus co teuse car elle demande le d veloppement d un mat riel m me de r gler les probl mes d acc s multiples la m moire partag e C est elle que nous nous int resserons dans cet article On peut distinguer diff rents types de parall lisme utilisant une m moire commune Le premier type est bas sur un ordinateur poss dant plusieurs processeurs capables d assurer chacun une partie de l ex cution ces processeurs sont en g n ral identiques Les synchronisations dans ce genre de machine doivent s effectuer fr quemment et un niveau tr s fin Ce genre de machine poss de donc des instructions sp cialis es assurant les traitements parall les et leurs synchronisations Ce type de machine autorise un vrai parall lisme du traitement des ex cutions qui se d roulent en parall le sur plusieurs processeurs Le deuxi me type est caract ristique des machines o l on ne parall lise qu une certaine cat gorie de traitement g n ralement les entr es sorties l aide de processeurs sp cialis s Seuls les traitements appartenant ces cat gories sont r alis s en pa
37. ude lt stdio h gt include lt setjmp h gt undef DEBUG 1 dcfine TAILLE_ELEM sizeof char define MINSTACK Gnt 1000 TAILLE_ELEM define DEBUT_INIT 0 define SUITE_INIT 1 define FIN_INIT 2 define SP m 12 define ETAT_ZERO 0 1 define ETAT_UN define detacher in out resume amp cor_principale in out typedef struct jmp_buf int CO_DESCR typedef struct CO_DESCR pdescr reg etat CO_CONTEXT CO_CONTEXT co_alloc CO_CONTEXT co_init resume extern CO_CONTEXT cor_principale taille d un element de la pile d unc coroutine taille minimale de la pile d unc coroutine etape de la fonction co_init etape de la fonction co_init etape de la fonction co_init numero du registre pointeur de pile dans le descriptif etat d une coroutine bloqu et See etat d une coroutine libre coers en buse definition du descritif de coroutine definition du contexte de coroutine fonction d allocation des coroutines fonction d initialisation des coroutines fonction de commutation des coroutines 4 nom de la coroutine principale 18
Download Pdf Manuals
Related Search