INF2610
Hiver 2012
Module 4 : Synchronisation
4.1 Traditionnellement, les smaphores taient implants en mode noyau afin de pouvoir rer les attentes et rveils lors!ue les smaphores sont infrieurs ou au" # 0. $st%&e essentiel' (ans !uels &as pourrait%on faire mieu"' )omment' $st%&e !ue l*al orithme de l*attente a&tive ave& alternan&e fon&tionne aussi sur un ordinateur multi%pro&esseur # mmoire parta e' $st%&e !ue l*al orithme de ,eterson pour l*e"&lusion mutuelle peut fon&tionner sur un syst-me ave& ordonnan&ement premptif' Non premptif' ,eut%on utiliser une instru&tion d*&han e atomi!ue .s/ap0 plut1t !u*une instru&tion T23 .test and set lo&40 afin de raliser une fon&tion permettant de rer l*entre dans une r ion &riti!ue' )omment peut%on pro rammer des smaphores en utilisant seulement la &apa&it de l*ordinateur # dsa&tiver les interruptions' ,eut%on pro rammer des smaphores # l*aide de mute" et de varia6les ordinaires' ,eut%il 8tre pertinent d*utiliser une 6arri-re si on n*a !ue deu" pro&essus' $st%&e !ue deu" fils d*e"&ution dans un m8me pro&essus peuvent se syn&hroniser # l*aide de smaphore, s*il s*a it de fils rs par le syst-me' :rs en mode usa er' <n vous propose de rempla&er /ait et si nal pour les &onditions par une forme plus nrale permettant d*attendre sur une e"pression .e. . /ait until ." = 0 >> " ? y = n00. )ette primitive serait plus fle"i6le. $st%&e !ue &e serait avanta eu"'
4.2 4.+ 4.4
4.5 4.6 4.7 4.9
4.;
4.10 )onsidre@ un syst-me multi&ou&he &ompos de trois &ou&hes ,0, ,1 et ,2. 3es &ou&hes sont des pro&essus &on&urrents !ui &ommuni!uent au moyen de deu" tampons T0 et T1 de m8me taille NA ,0 et ,1 parta ent le tampon T0 et ,1 et ,2 parta ent le tampon T1. )ha!ue &ou&he se &har e dBun traitement parti&ulier A 3e pro&essus ,0 se &har e de lire du &lavier des messa es !uBil traite avant de les dposer dans le tampon T0. 3e traitement dBun messa e par la &ou&he ,1 &onsiste # lBen&rypter. Il est ralis par la fon&tion $n&rypter suivante A Message Encrypter (Message); 3a fon&tion Message Lire (); permet de lire un messa e du &lavier. 3e pro&essus ,1 se &har e de transfrer dire&tement les messa es du tampon T0 vers le tampon T1. 3e pro&essus ,2 r&up-re les messa es du tampon T1 pour les envoyer # un destinataire. 3Benvoi dBun messa e est ralis par la fon&tion $nvoyer A Envoyer (Message );
clavier
P0 T0 P1 T1
P2 Envoyer (m)
$"pli!ue@ &omment les pro&essus peuvent utiliser les smaphores pour &ontr1ler les a&&-s au" tampons parta s .e"&lusion mutuelle, pas dBinter6lo&a e0. (onne@ les pseudo&odes des trois pro&essus.
4.11 2maphores 1. $"pli!ue@ &e !ui peut arriver si la file dBattente dBun smaphore est re selon la dis&ipline 3IF< .last in first out0. 2. $"pli!ue@ un avanta e de lButilisation de moniteurs sur les smaphores pour la syn&hronisation de pro&essus. +. )omplte@, en aCoutant les smaphores et les oprations , et D n&essaires, les &odes du produ&teur et du &onsommateur suivants. 3e produ&teur produit plusieurs ressour&es # la fois alors !ue le &onsommateur &onsomme une seule ressour&e # la fois. &har TENFG HH ta6leau de N &ara&t-res 2emaphore ,lein I0, DideIN, Jute"I1 ,rodu&teur K int ipI0, JG &har &hENFG Lepeter K JI3ire.&h,N0G (eposer.&h, J, ip0G ip I .ip ? J0 M NG N )onsommateur K int i&I0G &har &G Lepeter K & I Letirer. i&0G i& I .i&?10 MN Traiter.&0G N
N N 3a fon&tion O int 3ire.&har &hEF, int N0G P &onstruit, dans &h, une &haQne de &ara&t-res de lon ueur &omprise entre 1 et N in&lusivement. $lle retourne la lon ueur de la &haQne. 3a fon&tion O void (eposer.&har &hEF, int J, int ip0G P ins-re, dans le tampon T, la &haQne de &ara&t-res &h. J est la lon ueur de la &haQne. 3a fon&tion O &har [Link] i&0G P retire un &ara&t-re du tampon T. $lle retourne le &ara&t-re retir. +
3a fon&tion O void Traiter.&har &0G P traite le &ara&t-re. 4.12 Trois pro&essus &on&urrents ,1, ,2 et ,+ e"&utent &ha&un le pro ramme suivantA ,i .0 HH i I 1,2,+ K int nI0G /hile.true0 printf.R&y&le Md de MdR, n??, i0G N Synchronisez les &y&les des pro&essus # lBaide de smaphores de mani-re # &e !ue A )ha!ue &y&le de ,1 sBe"&ute en &on&urren&e ave& un &y&le de ,2. 3e pro&essus ,+ e"&ute un &y&le, lors!ue ,1 et ,2 terminent tous les deu" lBe"&ution dBun &y&le. 3ors!ue ,+ termine un &y&le, les pro&essus ,1 et nouveau &y&le et ainsi de suiteS ,2 entament &ha&un un
4.1+ 3a ville de Jontral veut restru&turer la &ir&ulation sur son territoire. 3e &onseil muni&ipal d&ide don& de resyn&hroniser les interse&tions pour rduire le trafi& au" heures de pointe. 3a ville vous en a e pour raliser un mod-le de syn&hronisation, # lBaide de smaphores, dBune interse&tion typi!ue de la ville. Il est important de noter !ue le vira e # droite sur le feu rou e nBest pas l al sur lBQle de Jontral. 3Binterse&tion &hoisie poss-de + voies nord%sud et 2 voies est% ouest. 3 voies nord-sud : ,armi les + voies nord%sud, la plus # droite permet de tourner # droite et dBaller tout droit. 3a &entrale permet dBaller tout droit tandis !ue &elle de au&he est une voie rserve pour le tournant # au&he. 3es &ondu&teurs en a s dans &ette voie doivent attendre la fl-&he verte pour tourner, tandis !ue le feu vert dans les deu" autres voies sont des feu" pleins .feu" ronds0. 3es voies opposes sont soumises au" m8mes r- les. 2 voies est-ouest : 4
3a voie la plus # droite de &es deu" voies permet au" &ondu&teurs de tourner # droite ou dBaller tout droitG par &ontre, la plus # au&he de &es voies permet seulement dBaller tout droit. )omme dans la maCorit des interse&tions de la ville, le vira e # au&he nBest pas permis dans &e sens de la &ir&ulation. 3e feu !ui permet de traverser lBinterse&tion pour &es voies est un feu plein. 3es voies opposes sont soumises au" m8mes r- les. 3e s&hma suivant illustre lBe"pli&ation A
<n suppose !ue lBinterse&tion est touCours li6re A d-s !uBun &ondu&teur sBen a e, il sera apte # traverser enti-rement lBinterse&tion. 3es feu" du sens est%ouest ouest%est sont initialement verts. 3es feu" opposs sont touCours dans le m8me tat A si la fl-&he est verte lBautre fl-&he lBest aussi. 3a s!uen&e de passa e au vert doit suivre lBordre suivant A le feu est%ouest, puis le feu" nord%sud, et la fl-&he pour finir. 2eulement un des trois numrs peut 8tre vert # la fois. )ha!ue voie poss-de sa file de voitures en attente du feu vert. )es files seront modlises par des listes de la 2T3. (e plus, un pro&essus l er sera en &har e de syn&hroniser les feu" # lBaide de smaphores. 3Battente a&tive dans le mod-le nBest pas a&&epta6le. denti!ier les mod-les de syn&hronisation &lassi!ues prsents dans &e syst-me. "#ter$inez le nom6re de pro&essus l ers n&essaires, le nom6re de smaphores et de mute" ave& leurs valeurs initiales. ndi%uez le r1le de &ha&un.
4.14 (eu" pro&essus T et U &ommuni!uent au moyen dBun tampon T pouvant &ontenir !uBun seul messa e # la fois. )e tampon est utilis, de faVon alterne, pour la &ommuni&ation dans les deu" sens .attention un seul pro&essus utilise # la fois &e tampon0. 3e pro&essus T dpose un messa e dans le tampon puis attend la rponse de U avant de dposer # nouveau un autre messa e et ainsi de suiteS. 3ors!ue U reVoit un messa e de T, il dpose sa rponse dans le tampon puis se met en attente dBun autre messa e de T et ainsi de suiteS 2yn&hronise@ au moyen de smaphores les pro&essus T et U .pour rpondre # la !uestion, &omplte@ le &ode suivant0 semaphore S.. G HW0WH &har TE256F G void depot .&har 6ufEF 0 G void re&uperer.&har 6ufEF 0 G ,ro&essus T K &har messE256F, repE256F G /hile .10 K HW 1 WH lire .mess0G depot .mess 0 G HW 2WH re&uperer.rep0 G HW+WH N N N N K ,ro&essus U &har messE256F , repE256F G
/hile .10 K HW 4 WH re&uperer. mess0 G [Link],rep0 HW5WH depot.rep0G HW 6WH
2uppose@ maintenant !uBun troisi-me pro&essus ) veuille &ommuni!uer ave& U en utilisant lBuni!ue tampon T. 3es pro&essus T et ) se &omportent de la m8me mani-re. U peut don& re&evoir un messa e de T ou ), la rponse doit 8tre r&upre par le pro&essus e"pditeur du messa e. 2yn&hroniser au moyen de smaphores les pro&essus T, U et ). 4.15 2yn&hronise@ au moyen de smaphores lBen&haQnement des oprations de fa6ri&ation de stylos # 6ille. )ha!ue stylo est form dBun &orps, dBune &artou&he, dBun 6ou&hon arri-re et dBun &apu&hon. 3es oprations # effe&tuer sont les suivantes A remplissa e de la &artou&he ave& lBen&re .opration L)0, 6
assem6la e du 6ou&hon arri-re et du &orps .opration U<0, assem6la e de la &artou&he ave& le &orps et le &apu&hon .opration T20, em6alla e .opration $J0.
)ha!ue opration est effe&tue par une ma&hine sp&ialise .mL), mU<, mT2, m$J0. 3es sto&4s de pi-&es dta&hes et dBen&re sont supposs disponi6les !uand la ma&hine est disponi6le. 3es oprations L) et U< se font en parall-le. 3Bopration T2 doit 8tre effe&tue, apr-s &es deu" oprations, en prlevant dire&tement les lments sur les ma&hines mL) et mU<. 3e produit assem6l est dpos dans un sto&4 en attente de lBopration $J. 3Bopration $J se fait don& apr-s T2, # partir du sto&4. 3e sto&4 est suppos de taille N et de dis&ipline FIF<. mRC( ) { while (1) { RC( ) ; } } } 4.16 <n dispose dBune &arte le&troni!ue # 6ase de mi&ro&ontr1leurs pour &ontr1ler un ensem6le de ro6ots. 3a &arte est livre ave& un lo i&iel sous 3inu", !ui permet de &rer son propre pro ramme pour &ommander et &oordonner un ensem6le de ro6ots, et de le &har er ensuite dans la mmoire non volatile .sur la &arte0 par un port srie. <n vous solli&ite pour &rire un pseudo&ode !ui &ontr1le le dpla&ement de plusieurs ro6ots sur les &hemins suivants A } mBO( ) { while (1) { BO( ) ; mAS( ) { while (1) { AS( ) ; } } mEM( ) { while (1) { EM() ; } }
3es ro6ots peuvent partir de T vers ) ou de ( vers T. ,our viter tout ris!ue de &ollision, il faut sBassurer !ue &ha!ue se ment du &hemin .se ments TU, U) et (U0 est utilis par un ro6ot au plus.
,our rpondre # &ette !uestion, &omplte@ le pseudo&ode suivant afin !ue les r- les &i%dessus soient respe&tes. (ans &e pro ramme, &ha!ue ro6ot est &ommand par un pro&essus. $st%&e !ue votre solution prsente un pro6l-me de famine ' inter6lo&a e ' Xustifie@. /*0*/ void TraverserSegAB ( ) ; // Traverser le segment AB void TraverserSegB ( ) ; // Traverser le segment B void TraverserSegB! ( ) ; // Traverser le segment B! Process"s #o$otA Process"s #o$ot!A K K HW 1 WH Traverser2e TU . 0 G HW 2WH Traverser2e U). 0 G HW+WH N N HW 4 WH Traverser2e U(. 0 G HW5WH Traverser2e TU. 0G HW 6WH
4.17 3a &ir&ulation dans une interse&tion de deu" voies # sens uni!ue est r le par des si nau" lumineu" .feu vertHrou e0. <n suppose !ue les voitures traversent lBinterse&tion en ligne droite et !ue l&intersection peut contenir au plus une voiture ' la !ois.
<n impose les &onditions suivantes A 9
o o
toute voiture se prsentant # lBinterse&tion la fran&hit en un temps fini G
les feu" de &ha!ue voie passent alternativement du vert au rou e, &ha!ue &ouleur tant maintenue pendant un temps fini .(ureeYduYfeu0 G
o
les arrives sur les deu" voies sont rparties de faVon !uel&on!ue.
3e fon&tionnement de &e syst-me peut 8tre modlis par un ensem6le de pro&essus parall-lesA
o o
un pro&essus P !ui e"&ute la pro&dure Changement !ui &ommande les feu"G
un pro&essus est asso&i # &ha!ue voitureG la traverse du &arrefour par une voiture !ui &ir&ule sur la voie i .i I 1, 20 &orrespond # l*e"&ution d*une pro&dure Traverseei() par le pro&essus asso&i # la voiture. ,our simuler un tel syst-me, on vous demande, dans un premier temps, de &omplter, en aCoutant les smaphores et le &ode n&essaires, les pro&dures suivantes (attention A vous ne deve@ pas aCouter de varia6les dBautres types0 A
HH Feu I 1 si le feu" de la voie 1 est vert, Feu I2 si le feu" de la voie 2 est vert HH&ir&uler simule la traverse de lBinterse&tion (ans une se&onde tape, il vous est demand de &omplter le moniteur suivant, en aCoutant les varia6les de &ondition et le &ode n&essaires A
HH Feu I 1 si le feu" de la voie 1 est vert, Feu I2 si le feu" de la voie 2 est vert HH N6/1 est le nom6re de voitures .S. sur la voie 1 HHN6/2 est le nom6re de voitures ..S..sur la voie 2.
4.19 <n souhaite implmenter au moyen de smaphores les &ompteurs dBvnements. Zn &ompteur dBvnements est un &ompteur asso&i # un vnement. 2a valeur indi!ue le nom6re dBo&&urren&es de lBvnement asso&i. :nralement, &e &ompteur est parta entre plusieurs pro&essus et sert # les syn&hroniser. (ans &e sens, trois oprations atomi!ues sont dfinies pour un &ompteur dBvnement $A Lead.$0 A retourne la valeur de $ au pro&essus appelant. Tdvan&e.$0 A in&rmente de 1 la valeur de $ et d6lo!ue tous les pro&essus en attente !ue $ attei ne &ette nouvelle valeur. T/ait.$, v0 A 6lo!ue le pro&essus appelant, si la valeur de $ est stri&tement infrieure # v. Il nBy a pas de 6lo&a e du pro&essus appelant si la valeur de $ est dC# ale ou plus rande !ue v. (o$pl#tez) au moyen de s#$aphores, la stru&ture et les pro&dures T/ait, Lead et Tdvan&e suivantes .sous forme de pseudo&ode0. ndi%uez &lairement les stru&tures de donnes aCoutes dans la stru&ture )ompteur$venement ainsi !ue les oprations asso&ies. str"ct om%te"rEvenement & int val ; /* 0 */ ' 10
void A(ait ( om%te"rEvenement *E; int )ale"r) & /*1*/ ' void Advance ( om%te"rEvenement *E) & /* 2 */ ' int #ead ( om%te"rEvenement *E) & /* * * / ' om%te"rEvenement E+ /* ,*/ ;
4.1; <n &onsid-re le pro6l-me du passa e # niveau # voie uni!ue. ,our simuler le fon&tionnement de &e syst-me, on se propose de le modliser par un ensem6le de pro&essus parall-les A un pro&essus )ontr1leur !ui se &har e de &ommander la fermeture et lBouverture des 6arri-res. 3es 6arri-res doivent 8tre fermes lors!uBun train traverse le passa e # niveau. 3e &ontr1leur ouvre les 6arri-res sBil nBy a au&un train en attente du passa e # niveau. un pro&essus Train est asso&i # &ha!ue train. Il est &r de faVon alatoire pour simuler lBarrive dBun train ainsi !ue la traverse du passa e # niveau. (o$pl#tez) en aCoutant les s#$aphores et le code n&essaires, les pro&dures suivantes e"&utes par les pro&essus )ontr1leur et Train (attention A vous ne deve@ pas aCouter de varia6les dBautres types0. 2i 6esoin est, vous pouve@ utiliser lBopration int ,[Link] s0 !ui est lB!uivalent de semYtry/ait.[s0. E*pli%uez le r1le de &ha!ue smaphore . indi%uez lButilit de sa %ueue ainsi !ue sa valeur initiale0. +ttention : Dous ne deve@ pas aCouter de varia6les autres !ue les smaphores.
11
Semaphore
HW0WH Train() & ////////// /***/ Traverser(); /////////// /*,*/
ontr-le"r () & (.ile(1) & /////////// /*1*/ 0ermerBarrieres() ; /////////// /*2*/ 1"vrirBarrieres() ; ' '
'
4.20 <n dispose d*un m&anisme d*enre istrement # un ensem6le de &ours, tel !ue tout tudiant ne peut 8tre ins&rit !u*# au plus trois &ours, et !ue &ha!ue &ours a un nom6re limit de pla&es. Zn tudiant ins&rit dC# # trois &ours peut sBil le souhaite en a6andonner un, pour en &hoisir un autre dans la limite des pla&es disponi6les. 2i &et &han e nBest pas possi6le, lBtudiant ne doit pas perdre les &ours au"!uels il est dC# ins&rit. 3e 6ureau des affaires a&admi!ues souhaite don& mettre en pla&e un syst-me de permutation de &ours, permettant # un tudiant de &han er de &ours. Il vous solli&ite pour vrifier si lBimplmentation !ue vous ave@ propose il y a un an .avant se suivre le &ours INF+6000 est &orre&te A void $&han e)ours .,utilisateur utilisateur, ,)ours &ours1, &ours20 K &ours1%\verrouille .0G HH verrouille lBa&&-s # lBo6Cet &ours1 &ours1%\desins&rit .utilisateur0G if .&ours2%\est,lein II false0 K &ours2%\verrouille .0G HH verrouille lBa&&-s # lBo6Cet &ours2 &ours2%\ins&rit .utilisateur0G &ours2%\deverrouille .0G HHdverrouille lBa&&-s # lBo6Cet &ours2 N &ours1%\deverrouille .0G HHdverrouille lBa&&-s # lBo6Cet &ours2 12
N ,#ri!iez si l-i$pl#$entation est correcte A 2i elle est &orre&te, e*pli%uez pour%uoi, en montrant &omment est r le &as o] deu" tudiants .ou plus0 veulent a&&der en m8me temps au syst-me. 2i elle est in&orre&te ) listez et e*pli%uez les pro.l/$es, et proposez une solution !ui fon&tionne.
4.21 <n vous solli&ite pour implmenter en utilisant les smaphores un autre m&anisme de syn&hronisation appel O Uarri-res P. )e m&anisme est tr-s utile pour syn&hroniser un roupe de pro&essus &omposs &ha&un de plusieurs phases !ui fon&tionnent selon la r- le suivante A Tu&un pro&essus ne peut entamer sa phase suivante tant !ue les autres nBont pas fini leurs phases &ourantes. ,our raliser une telle syn&hronisation, une 6arri-re est pla&e # la fin de &ha!ue phase. 3ors!uBun pro&essus atteint une 6arri-re, il est 6lo!u Cus!uB# &e !ue tous les autres pro&essus attei nent la 6arri-re. 3es pro&essus peuvent alors e"&uter leurs phases suivantes. ,ar e"emple, les trois pro&essus T, U et ) suivants &onsistent en deu" phases O a&!uisition P et O traitement P de param-tres. Tve& la 6arri-re ^, il ne peut y avoir un pro&essus # lBtape a&!uisition de param-tres et un autre # lBtape de traitement. )ette 6arri-re permet au" trois pro&essus de se syn&hroniser avant dBentamer une autre phase. UarrierYt ^ .+0 G HH + est le nom6re de pro&essus utilisant la 6arri-re ^. ,ro&essus U K /hile .10 K T&!uis,aram.20 G ^.Uarriere. 0 G Trt,aram.20 G ^.Uarriere. 0 G N N ,ro&essus ) K /hile .10 K T&!uis,aram.+0 G ^.Uarriere. 0 G Trt,aram.+0 G ^.Uarriere. 0 G N N
,ro&essus T K /hile .10 K T&!uis,aram.10 G ^.Uarriere. 0 G Trt,aram.10 G ^.Uarriere. 0 G N N
(onne@ une implmentation au moyen de smaphores de &e m&anisme de syn&hronisation .sous forme de pseudo%&ode0. ,our rpondre # &ette !uestion, dfinisse@ une &lasse dBo6Cet UarrierYt en pr&isant ses attri6uts et ses mthodes. 1+
<n veut maintenant utiliser les 6arri-res pour syn&hronise@ une &haQne de produ&tion de stylos # 6ille. )ha!ue stylo est form dBun &orps, dBune &artou&he, dBun 6ou&hon arri-re et dBun &apu&hon. 3es oprations # effe&tuer pour fa6ri!uer un stylo sont les suivantes A remplissa e de la &artou&he ave& de lBen&re .opration L). 00, assem6la e du 6ou&hon arri-re et du &orps .opration U<. 00, assem6la e de la &artou&he ave& le &orps et le &apu&hon .opration T2. 00, em6alla e .opration $J. 00.
)ha!ue opration est effe&tue par une ma&hine sp&ialise &ommande par un pro&essus .mL), mU<, mT2, m$J0. 3es sto&4s de pi-&es dta&hes et dBen&re sont supposs disponi6les !uand la ma&hine est disponi6le. 3es oprations L) et U< se font en parall-le. Tvant dBentamer lBopration T2, la ma&hine mT2 doit prlever les lments sur les ma&hines mL) et mU< .opration :,.00. 3e produit assem6l est ensuite prlev par m$J pour lBem6alla e. (onne@ le pseudo%&ode de &ha!ue pro&essus. Indi!ue@ &lairement les 6arri-res utilises, leurs valeurs ainsi !ue leurs r1les. 0arrier1t $5(( ) 6 7hile (8) 6 23832 5(( ) ; 23232 9 9 $0:( ) 6 7hile (8) 6 23332 0:( ) ; 23432 9 9 23432
14
$+S( ) 6 7hile (8) 6 23;32 <=( ) ; 23>32 +S( ) ; 23?32 9 9 $EM() 6 7hile (8) 6 23@32 <=( ) ; 23A32 EM( ) ; 238432 9 9 Zne mauvaise utilisation des 6arri-res peut%elle mener vers des inter6lo&a es ' Xustifie@ ' 4.22 2oient trois pro&essus &on&urrents ,1, ,2 et ,+ !ui parta ent les varia6les n et out. ,our &ontr1ler les a&&-s au" varia6les parta es, un pro rammeur propose les &odes suivantsA 2emaphore mute"1 I 1 G 2emaphore mute"2 I 1 G )ode du pro&essus p1 A ,.mute"10 G ,.mute"20 G outIout?1 G nIn%1 G [Link]"20 G [Link]"10 G )ode du pro&essus p2 A ,.mute"20 G outIout%1 G 15
[Link]"20 G )ode du pro&essus p+ A ,.mute"10 G nIn?1 G [Link]"10 G )ette proposition est%elle &orre&te ' 2inon, indi!uer parmi les 4 &onditions re!uises pour raliser une e"&lusion mutuelle &orre&te, &elles !ui ne sont pas satisfaites ' ,roposer une solution &orre&te. <n veut effe&tuer en parall-le le produit de deu" matri&es T et U dBordre n .n"n0. ,our se faire, on &re m .m=n0 pro&essus l ers .threads0. )ha!ue pro&essus l er se &har e de &al&uler !uel!ues li nes de la matri&e rsultat L A ,our C I 0 # n%1 LEi,CF I 4I0,n%1 TEi,4FWUE4,CF G (onner sous forme de &ommentaires .en utilisant les smaphores et les oprations , et D0, le &ode des pro&essus l ers A )al&ul3i nes . 0. ,r&iser les smaphores utiliss et les varia6les parta es.
4.2+ (eu" villes T et U sont relis par une seule voie de &hemin de fer. 3es trains peuvent &ir&uler dans le m8me sens de T vers U ou de U vers T. Jais, ils ne peuvent pas &ir&uler dans les sens opposs. <n &onsid-re deu" &lasses de pro&essus A les trains allant de T vers U .Train TversU0 et les trains allant de U vers T .Train UversT0. )es pro&essus se d&rivent &omme suit A Train TversU A (emande dBa&&-s # la voie par T G )ir&ulation sur la voie de T vers UG 2ortie de la voie par UG (emande dBa&&-s # la voie par U G )ir&ulation sur la voie de U vers TG 2ortie de la voie par TG
Train UversT A
,armi les mod-les tudis en &lasse .produ&teurH&onsommateur, le&teurHrda&teur, les philosophes0, &e pro6l-me &orrespond # !uel mod-le ' $&rire sous forme de &ommentaires en utilisant les smaphores, les oprations , et D, les &odes de demandes dBa&&-s et de sorties, de faVon # &e !ue les pro&essus respe&tent les r- les de &ir&ulation sur la voie uni!ue. 16
4.24 )onsidrons le pro6l-me produ&teurH&onsommateur, vu en &lasse. Tdapte@ la solution suivante A Tu &as de n produ&teurs, n &onsommateurs et un seul tampon de taille .Ja", il peut &ontenir au plus Ja" messa es0. 3es produ&teurs produisent des messa es et les dposent dans le tampon. )ha!ue messa e dpos dans le tampon est r&upr .&onsomm0 par un seul &onsommateur. Tu &as dBun seul produ&teur, n &onsommateurs et n tampons de m8me taille .Ja"0. )ha!ue messa e produit par le produ&teur est dpos dans tous les tampons en &ommenVant par le premier. 3e &onsommateur i r&up-re .&onsomme0 les messa es dposs dans le tampon i. 2emaphore Jute" I1, DideIJa", ,leinI0 G Jessa e tampon EJa"F G ,rodu&teur . 0 K int ip I0 G Jessa e m G Lepeter K m I &reermessa e.0 G ,.Dide0 G ,.Jute"0 G TamponEipFImG [Link]"0 G ip?? G D.,lein0 G Ntant !ue vrai G N )onsommateur. 0K int i& I0 G Jessa e m G Lepeter K ,.,lein0 G ,.Jute"0 G m I TamponEi&FG [Link]"0 G i&?? G D.Dide0 G Ntant !ue vrai G N 17