skrypt.pdf

Przykładowezadanianakolokwiumnr2

***proKtórazfunkcjisystemowychUnixaniejestpotrzebnadokorzystania

zpotoku?***odppipe***odpfork***odpread***odpwrite

***proIlepowstanieł¡cznieprocesówwskutekuruchomieniaponi»szegopro-

gramu?

main(){inti;for(i=0;i<5;++i)if(fork()<0)exit(0);}

***proKtórafunkcjanigdyniezwracawarto±ci − 1?***odpfork***odp

exec***odpclose***odpexit

***proConale»ywstawi¢wprzytoczonymfragmenciekoduwmiejscetrzech

kropek,byspowodowa¢przekierowaniestandardowegowej±cianaplik?

fd=open("plik",0700);close(0);...;close(fd);

***proIleconajwy»ejsierotmo»epowsta¢wwynikudziałanianast¦puj¡-

cegokodu?

fork();fork();if(fork())wait(NULL);

***proKtóryalgorytmpoprawnieimplementujewzajemnewykluczanieza

pomoc¡niepodzielnejoperacjizamianywarto±cizmiennych(exch)?Zakładamy,

»ezmiennaajestwspółdzielona,zainicjowanana0,natomiastbjestlokalna

wka»dymzprocesów;SKoznaczasekcj¦krytyczn¡.***odpb:=1;repeatexch(a,b)untilb=0;SK;a:=0

***odpb:=1;repeatexch(a,b)untilb=1;SK;a:=0***odpb:=1;repeatexch(a,b)untilb=0;SK;b:=0

***odpb:=0;repeatexch(a,b)untilb=0;SK;a:=0

***proKtóryalgorytmpoprawnieimplementujewzajemnewykluczanieza

pomoc¡niepodzielnejoperacjitest-and-set(ts)?Zakładamy,»ezmiennaajest

współdzielona;SKoznaczasekcj¦krytyczn¡.***odpwhilets(a)=1do;SK;a:=0

***odpwhilets(a)=1do;SK;a:=1***odpwhilets(a)=1doa:=0;SK;a:=0

***odpwhilets(a)=1doa:=1;SK;a:=1

***proDwaprocesywspółbie»nekomunikuj¡si¦przezbuforoograniczo-

nejpojemno±ci.Jedenznichjestproducentem,drugi—konsumentem.Dost¦p

dobuforaprocesyprzeprowadzaj¡wedługalgorytmów,wykorzystuj¡cychsema-

forya,b,w.Producentwykonujepokolei:P(a);P(w);wło»eniebajtudobufora;

V(w);V(b).Jakpowinienwygl¡da¢poprawnykodkonsumenta(„pbzb”ozna-

czapobraniebajtuzbufora)?***odpP(b);P(w);pbzb;V(a);V(w)***odp

P(w);P(b);pbzb;V(a);V(w)***odpP(w);P(a);pbzb;V(w);V(b)***odp

P(a);P(w);pbzb;V(w);V(b)

***proDwaprocesywspółbie»nekomunikuj¡si¦przezbuforopojemno±ci

1024bajtów.Jedenznichjestproducentem,drugi—konsumentem.Dost¦p

dobuforaprocesyprzeprowadzaj¡wedługalgorytmów,wykorzystuj¡cychse-

maforya,b,w.Wszczególno±cikodproducentamaposta¢:P(a);P(w);wło-

»eniebajtudobufora;V(w);V(b).Jakiewarto±cipocz¡tkowenale»ynada¢

semaforom?***odpa=1024,b=0,w=1***odpa=0,b=1024,w=1***odp

a=0,b=0,w=1024***odpa=1024,b=1,w=0

***proprocesy P i ( i =1 ,...,N )wykonuj¡wniesko«czonychp¦tlachswoj¡

tre±¢,czylis¡postaci:

process P i :for k i :=1to 1 do { (*); C i ;(**) }

Dodatkowomamytablic¦semaforówliczbowych s [ i,j ]orozmiarze N × N ,któ-

rymnadanopocz¡tkowowarto±¢ d .Którefragmentymo»nawstawi¢wmiejsca

(*)/(**),bywdowolnejchwilispełnionybyłwarunek 8 i,j =1 ,...,N : | k i − k j |¬

d +1?Liczby N oraz d tostałe.Procesyznaj¡swojenumery i .

**odp(*)for j :=1to N doP( s [ i,j ]),(**)for j :=1to N doV( s [ j,i ])

**odp(*)for j :=1to N doP( s [ i,j ]),(**)for j :=1to N doV( s [ i,j ])

**odp(*)for j :=1to N doP( s [ i,i ]),(**)for j :=1to N doV( s [ j,i ])

**odp(*)for j :=1to N doP( s [ i,j ]),(**)for j :=1to N doV( s [ j,j ])

***proWktórymzestanówznajdujesi¦proces,którywykonałnasemaforze

operacj¦P,leczniewszedłdostrefykrytycznej,gdy»tajestakuratzaj¦taprzez

innyproces?***odpoczekuj¡cy***odpwstrzymany***odpgotowy***odp

wykonywany

***proWktórymzestanówznajdujesi¦proces,którywykonał(wmoni-

torze)operacj¦delay?***odpoczekuj¡cy***odpwstrzymany***odpgotowy

***odpwykonywany

***proPoni»szymonitorsłu»ydosynchronizacjiczytelnikówipisarzy:

monitor CP;varlc,lp:int:=0;qc,qp:queue;

entry PoczPis:iflc > 0orlp > 0thendelay(qp);lp:=1

entry KonPis:lp:=0;ifnotempty(qc)thencontinue(qc)elseifnotempty(qp)

thencontinue(qp)

entry PoczCzyt:iflp > 0thendelay(qc);++lc;ifnotempty(qc)thenconti-

nue(qc)

entry KonCzyt: −− lc;ifnotempty(qp)thencontinue(qp)

Istniejescenariusz,przyktórym:***odpdwóchpisarzynarazuzyskadost¦pdo

bazydanych***odpnast¡pizakleszczenie***odpnast¡pizagłodzenieczytelni-

ków***odpnast¡pizagłodzeniepisarzy

***proDwaprocesykorzystaj¡zdwóchsemaforówbinarnych:s1is2.Po-

cz¡tkowos1jestotwarty,za±s2—zamkni¦ty.Kodprocesów: process P1:whiletruedo { P(s1);V(s2);V(s2) } ,

process P2:whiletruedo { P(s2);P(s2);V(s1) } .Wkodzietym:***odpmo»e

(leczniemusi)doj±¢dozakleszczenia***odpnapewnodojdziedozakleszczenia

***odpnapewnoniedojdziedozakleszczenia***odpkodjestniepoprawny

***proSemaforliczbowy(nieograniczony)smiałwarto±¢10.Pó¹niejwyko-

nywanonanimoperacjePiV;wsumie13razywykonanoP(s)i5razyV(s).

Warto±¢semaforapotychoperacjachto:***odp2***odp18***odp5***odp

tegoniemo»naustali¢nieznaj¡ckonkretnejkolejno±ciwykonywaniaPiV

***proRozwa»mydwaprocesy,P1iP2.SemaforbinarnyAjestpocz¡tkowo

otwarty,za±B—zamkni¦ty.Przez N X oznaczmyliczb¦wykona«operacjiX,

przez N Y —liczb¦wykona«operacjiY.Kodprocesów: process P1:whiletruedo { P(A);X;V(B) } ,

process P2:whiletruedo { P(B);Y;V(A) } .Wskaza¢najsilniejszywarunek

zachodz¡cywdowolnejchwili:***odp N Y +1 N X N Y ***odp N X +1

N Y N X ***odp N X +2 N Y N X ***odp N Y +2 N Y N X

***proMamytrzysemaforyliczbowe(nieograniczone):s1,s2is3,zainicjo-

wanena1.Rozwa»amytrzyprocesy.Przez n X , n Y i n Z oznaczamyliczb¦wyko-

na«odpowiednichoperacji.Kodprocesów: process P1:whiletruedo { P(s1);X;V(s2);V(s3) } ,

process P2:whiletruedo { P(s2);Y;V(s1);V(s3) } , process P3:whiletruedo { P(s3);Z;V(s2);V(s1) } .

Wskaza¢najsilniejszywarunekzachodz¡cywdowolnejchwili:***odp n X ¬

n Y + n Z ***odp n X ¬ n Y + n Z +1***odp n X ¬ n Y + n Z − 1***odp

n X ¬ n Y + n Z +2

***proWproblemieczytelnikówipisarzy:***odpniezale»nieodrozkładu

priorytetównapewnoniedojdziedozagłodzeniaczytelnikówanipisarzy***odp

napewnoniedojdziedozagłodzeniaczytelników,natomiastwzale»no±ciod

rozkładupriorytetówmo»edoj±¢dozagłodzeniapisarzy***odpwzale»no±ciod

rozkładupriorytetówmo»edoj±¢dozagłodzeniaczytelnikówlubpisarzy***odp

dlaka»degomo»liwegorozkładupriorytetówmo»edoj±¢dozagłodzeniaktórego±

ztypówprocesów

***proRozwa»mynast¦puj¡cetaskiwAdzie: task semafor:repeatacceptP;acceptVforever,

task T1:semafor.P;X;semafor.V, task T2:semafor.V;Y;semafor.P, task T3:semafor.P;Z;semafor.P,

task T4:semafor.V;A;semafor.V.Zakładamy,»awprocesiejesttasksemafor

ijedentaskzezbioru X { T 1 ,T 2 ,T 3 ,T 4 } .Wskaza¢maksymalnyzbiór X

gwarantuj¡cyzakleszczenie:***odp { T 1 ,T 2 ,T 3 } ***odp { T 2 ,T 3 ,T 4 } ***odp

{ T 2 ,T 3 } ***odp { T 3 ,T 4 }

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: