No title

OBSAH

1

}

w A| ,-./012345
Principy programovacch jazyk zpracoval Martin Kuba 16. kvtna 1995

Obsah 1 vod

1.1 Syntaxe : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

2 Smantika

2.1 Promnn : : : : : : : : 2.2 Datov typy : : : : : : : 2.2.1 Typy : : : : : : : 2.2.2 Podtypy : : : : : 2.2.3 Odvozen typy : 2.2.4 Skalrn typy : : 2.2.5 Pole : : : : : : : 2.2.6 Zznam : : : : : 2.2.7 Ukazatelov typy

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

D-programy : : : : : : : : : : D'-programy : : : : : : : : : BJn programy : : : : : : : : : do-repeat-cycle-exit programy 3.4.1 REn programy : : : : 3.4.2 DREn programy : : : 3.4.3 RECn programy : : : 3.4.4 DRECn programy : : 3.5 Kosarajanova hierarchie : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

: : : : : : : : :

4.1 Nhrada formln ho parametru skutenm : 4.1.1 Hodnotou : : : : : : : : : : : : : : : 4.1.2 Vsledkem : : : : : : : : : : : : : : 4.1.3 Hodnotou-vsledkem : : : : : : : : : 4.1.4 Odkazem : : : : : : : : : : : : : : : 4.1.5 Jm nem : : : : : : : : : : : : : : : : 4.1.6 Srovnn rozd l : : : : : : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

: : : : : : :

3 Srovnn sly jazyk 3.1 3.2 3.3 3.4

4 Podprogramy

: : : : : : : : :

: : : : : : : : :

3

3

4

4 5 5 5 6 6 7 7 8

8

9 10 10 11 11 11 11 11 12

12

13 13 13 13 14 14 14

OBSAH

2

4.2 Reim parametr - ADA : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3 Vedlej efekty podprogram : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.4 Voln podprogram : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

5 Moduly

5.1 Abstraktn datov typ FRONTA : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.1.1 Realizace a pouit nkolika front : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.1.2 Realizace a pouit front rzn ho typu : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

6 Kompilace programu

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

7.1 Paraleln procesy : : : : : : : : : : : : : : : : : : : : : : 7.2 Probl m vzjemn ho vylouen pro N proces : : : : : : 7.2.1 Vzjemn vylouen een .1 : : : : : : : : : : 7.2.2 Vzjemn vylouen een .2 : : : : : : : : : : 7.2.3 Vzjemn vylouen een .3 : : : : : : : : : : 7.2.4 Vzjemn vylouen een .4 : : : : : : : : : : 7.2.5 Vzjemn vylouen Dereerv algoritmus : : : 7.2.6 Vzjemn vylouen pro N proces : : : : : : : : 7.3 Semafory datov typ : : : : : : : : : : : : : : : : : : : 7.3.1 Vzjemn vylouen N proces pomoc semaforu 7.4 Producent a konzument : : : : : : : : : : : : : : : : : : 7.5 Monitory : : : : : : : : : : : : : : : : : : : : : : : : : : 7.6 Readers and writers : : : : : : : : : : : : : : : : : : : : 7.7 The problem of the dining philosophers : : : : : : : : : 7.8 Synchronizace proces Ada : : : : : : : : : : : : : : : 7.8.1 Synchronn vmna dat : : : : : : : : : : : : : : 7.8.2 Selektivn ekn volan ho na randezvous : : : : 7.8.3 Selektivn voln randezvous : : : : : : : : : : : : 7.8.4 Producent a konzument v Ad : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : :

6.0.3 6.0.4 6.0.5 6.0.6

Sestaven , knihovny : Aktulnost knihovny : Rekompilan seznam Vyj mky : : : : : : : :

7 Paraleln programovn

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

: : : :

14 15 15

16

16 18 19

19

19 20 20 20

21

21 21 22 22 23 23 24 25 26 26 27 27 28 29 32 32 32 33 34

1 VOD

3

1 vod Programovac jazyky je mono rozdlit na: imperativn vpoet je posloupnost zmn stavu pamti. Pou vaj promnn a piazovac p kaz. funkcionln (aplikativn) denice a aplikace funkc na argumenty. Pou vaj podm nn p kaz, rekurzi, skldn funkc . '55 IBM , pole, procedury

BASIC

+

FORTRAN

CC

)

CCW

'59 record

COBOL BNF, rekurze

ALGOL 60

?

- PL1

IBM

@@ R '67 OOP C '71 Wirth SIMULA PASCAL ; ? SMALLTALK ? ; ; PPPPq ? ? XXz OOPascal C++ @@

70.lta, paralelismus = @R Concurrent Wirth, moduly MODULA Pascal Euclid ZZ ZZ ? ~ '80 Dod Z '68 Wirth

ALGOL 68

?

ADA

Obrzek 1: Vvoj programovac ch jazyk

1.1 Syntaxe

Programovac jazyky jsou jazyky kontextov . Protoe vak pro analzu kontextovch jazyk nebyly dosud vynalezeny dostaten inn metody, popisuje se syntaxe prog. jazyk pomoc bezkontextovch gramatik (CFG). Zapisujeme je v BNF Baccusov-Naurov form nebo pomoc syntaktickch diagram:

BNF: ::= ] <slice> { <slice> } ::= +|-

syntaktick diagram: - znam - isl

-

m-m +

-

2 SMANTIKA

4

Syntaxe by mla bt odoln vi peklepm, viz slavn p klad ve FORTRANU, kdy v deklaraci cyklu byla omylem napsna teka m sto rky, take peklada to povaoval za piazovac p kaz implicitn deklarovan promnn a d ky tomu Amerianm spadla kosmick druice za mnoho mili!n dolar: DO 10 I = 1.5 vznikla promnn DO10I = 1.5 A(I) =I 10 CONTINUE

2 Smantika

Neformln denovna pirozenou e chyby, nejednoznanost, neplnost

Formln

operan abstraktn po ta axiomatick pravidla ovliv#ovn stavu pamti konstrukty fP e ! x g efP g denotan teorie dom n, Scott,Strackley (pomoc funkc )

]

:=

Sprvn navren s mantika by mla spl#ovat tyto podm nky: RYCHLOST PEKLADU by mla bt vysok EFEKTIVITA KDU by mla bt velk ORTOGONALITA znamen, e m mal poet jasn odliench konstrukt, jejich kombinac se dl ve ostatn UNIFORMITA znamen, e podobn vci se zapisuj syntakticky podobn

2.1 Promnn

Promnn m jm no atributy (typ) um stn (pam$, registr) hodnotu Deklarace promnnch me bt implicitn nebo explicitn, tj. bu% promnn vznikne pi jej m prvn m pouit , nebo se mus pedem jasn denovat zpsobem var] jmno: uren-typu := init-value]

FORTRAN: INTEGER X PASCAL: x:INTEGER a:array 1..10] of REAL ADA,ALGOL60: a:array N..M]of REAL kde velikost pole se ur za runtime.

Je zaj mav si vimnout, e v piazovac m p kazu x:=x+1 znamen x na lev stran p kazu um stn promnn , tzv. L-hodnotu, kdeto x na prav stran hodnotu promnn , tzv. R-hodnotu. Aliasing promnnch je p pad, kdy v ce promnnch rznch typ sd l tot m sto v pamti, nap. Pascalovsk variantn zznamy nebo C kov uniony:

2 SMANTIKA FORTRAN:

PASCAL:

C:

5

REAL X LOGICAL Y EQUIVALENCE X,Y record case DRUH:boolean of TRUE: x:integer FALSE: y:real end

union {int x float y}

Deklarace typu type jmno-typu = definice-typu

peddenovan typy (char,int,boolean)

Typov kompatibilita Kdy jsou dv promnn t ho typu ?

jsou-li deklarovny pomoc t ho typu (ekvivalence jm nem) maj -li jejich typy tut strukturu se shodnmi komponentami (strukturn ekvivalence)

Pklad 2.1

type T=array 1..5] of real var x:array 1..5] of real y:array 1..5] of real z:T

Podle strukturln ekvivalence jsou x,y,z stejn ho typu, podle ekvivalence jm nem maj rzn typy. Je tu jet jeden zdrhel, a to pi nsobnch deklarac ch a ekvivalenci jm nem: A,B :array 1..5] of real

V Pascalu maj stejn typ, v jazyku ADA rzn.

2.2 Datov typy

2.2.1 Typy

Typ je dn mnoinou hodnot a mnoinou operac . Zat m byly vynalezeny typy Skalrn digits,integer,enum,char. . . Strukturovan array,record,set,le Ukazatel hodnoty jsou um stn objekt

2.2.2 Podtypy

Podtyp je dn bzovm typem a omezen m mnoiny hodnot: SUBTYPE T1 is T range 1..10

T1 nen nov typ, operace m toton hodnoty objekt typu T1 jsou omezeny T je podtypem T (tj. sebe sama)

2 SMANTIKA

6

2.2.3 Odvozen typy

Z rodiovsk ho typu odvod m odvozen typ: TYPE OT is new RT omezen]

OT je nov typ val(OT)=val(RT) OT zdd mutace vech operac RT explicitn konverze

Odvozen typ hl d s tn hrutiek s jabl kama: type pohruek is new integer type pojablek is new integer var H,H1:pohruek J:pojablek I:integer

Lze s tat H+H1+2, ale nelze s tat H+J.

2.2.4 Skalrn typy

Skalrn typy mohou bt: vtov diskr tn celoseln diskr tn numerick reln numerick Hodnoty skalrn ch typ jsou uspodan pro kad typ existuj konstanty S'FIRST (minint) a S'LAST (maxint). Na diskr tn ch typech se denuj operace pedchdce PRED a nsledn ka SUCC, na vtovch nav c operace POS a VAL pro konverzi na poadovou hodnotu a zpt. U relnch typ je nutn si uvdomit, e reln slo je reprezentovno jen do urit pesnosti, take nkter matematicky sprvn rovnosti nemus platit, viz slavn p klad: for k:=1 to 17 do begin a 1]:=1/k for j:= 2 to 40 do a j]:=(k+1)*a j-1]-1 end 1 Teoreticky plat a j k k1 ; k . Teoreticky tedy jsou v poli hodnoty 3.3E-01. . . 3.3E-01 Prakticky tam budou hodnoty 3.3E-01. . . -9.16E+10 Celkem solidn nepesnost. ] = (1 +

)

1 =

Reln typy se dl na: FLOAT - s pohyblivou dovou rkou, relativn pesnost dan potem cifer FIXED - s pevnou dovou rkou, absolutn pesnost v dan m rozsahu

2 SMANTIKA

7

2.2.5 Pole

Pole je homogenn struktura, zadan dimenz potem index rozsahem index typem komponenty Pole mohou bt: determinovan interval diskr tn ch hodnot (Pascal) ? statick (Pascal) ? dynamick nedeterminovan lib. interval diskr tn ho typu uren na rovni deklarace P klad: type VEKTOR is array ( int<> ) of int type MATICE is array (int<>,int<>) of int V1: VEKTOR (-1..8) V2: VEKTOR (0..100) NM: MATICE (1..N,1..M)

Atributy: B'FIRST 1 B'LAST 100 B'RANGE 1..100 B'LENGTH 100 NM'LAST hodnota N NM'LAST(2) hodnota M Deskriptor pole: Typ doln mez indexu 1 horn mez indexu 1 doln mez indexu 2 horn mez indexu 2 .. . horn mez indexu n Typ komponenty D lka komponenty Operace zp stupnn komponenty:

LocA I LocA I ; D dk LocA I J LocA I ; D1 dr LocA I J I dr J dk ] =

] =

] =

+ (

)

+(

+

)

J ; D2 dk

+(

+

2.2.6 Zznam

Zznam je nehomogenn struktura: type DAT is record DEN:1..31 MES:(JAN,FEB,...) ROK:1..2000 end

)

dr H2 ; D2 dk LocA ; D1 d ; d2 dk = (

=

+ 1)

3 SROVNN SLY JAZYK

8

Selektor komponenty D:DAT' D.DEN DEN IN D DEN OF D D :=(DEN=>12,MES=>OCT,ROK=>1946)

Diskriminant Speciln komponenta diskr tn ho typu.

poten hodnota komponenty denice typu komponenty uren varianty ve variantn sti nen povolena operace := (nutno zmnit celou hodnotu zznamu)

type BUFSIZE is 0..MAX type BUFFER(SIZE:BUFSIZE := 100) is record UK: BUFSIZE :=0 HODN:array(1..SIZE)of char end VELKY: BUFFER(200) ZPR!VA:BUFFER

Variantn zznam type POHLAVI is (M,") type OSOBA(P :POHLAVI := M) is record jmno: string(1..20) case P of M: v#ka:integer vous:bool ": mry:array(1..3)of integer endcase endrec A,B("):OSOBA

2.2.7 Ukazatelov typy

type UKAZ is "M mnoina hodnot je skryt, krom nil. Alokace objektu: new(x) Vrcen na haldu: dispose(x) Pi piazovn ukazatel mohou vzniknout nedostupn objekty, tak bacha !

3 Srovnn sly jazyk Budeme srovnvat s lu jednotlivch t d d c ch struktur zkoumn m vztah (relac ) mezi t dami program generovanch pouit m pouze d c ch struktur p slunch t d. Relace denujeme na zklad rznch typ transformac mezi programy. Typy transformac programu P1 na P2 (vechny zachovvaj funkn ekvivalentnost P1 a P2 : velmi psn (vp) je zakzno ? zavdt nov primitivn akce, promnn , predikty ? mnit vpoetn historie pro jednotliv vstupy

3 SROVNN SLY JAZYK

9

? duplikovat pvodn akce a predikty

smantick (sem) je zakzno

? zavdt nov primitivn akce, promnn , predikty je povoleno ? mnit vpoetn historie ? duplikovat pvodn akce a predikty funkn (f) je povoleno ve P klad: konstrukci CYKL: if b goto VEN a goto CYKL VEN:

meme velmi p sn transformovat na while not(b) do Nebo if b then a else c funkn ztransformujeme na:

a

p:=true while (b and p) do begin a p:=false end while p do begin c p:=falseend

Relace mezi tdami program T1 t T2 jestlie kad program t dy T1 me bt transformovn na program t dy T2 . T1
)

(

)

(

"jakkoliv t da program" L pro vechny typy transformac ! L je t da program s lib. nvt m a goto. a- primitivn akce (piazovac p kaz, I/O p kaz, voln procedury,. . . ) je programem kad t dy. Sekvence program kad t dy je opt programem t to t dy.

3.1 D-programy

Jsou-li D1 D2 D-programy, pak i vtven if b then D1 else D2 cyklus while b do D1 jsou D-programy.

Bhm,Jacopini: D f L

Transformace zavd booleovsk promnn , jejich hodnoty se ukldaj do zsobn ku, test vrcholu zsobn ku se vyu v k rozhodovn o pedn zen (viz t Hoej,SOFSEM 1974).

3 SROVNN SLY JAZYK

10

Knuth: lib. L-program lze pev st na D-program takto: p:=1 while (p>0) do begin if p=1 then {krok1 p:= n$slednk-kroku-1} if p=2 then {krok2 p:= n$slednk-kroku-2} ... if p=n then {krokn p:= n$slednk-kroku-n} end

Ashcroft,Mann: Bez pomocnch promnnch se nelze obecn obej t, tj. D <sem L. Kosarajan: L-programy transformolvateln (s manticky) na D-programy jsou programy, kter neobsahuj cyklus s dvma i v ce rznmi vstupy z cyklu.

3.2 D'-programy

Jsou-li D1 D2 : : : Dn D'-programy, pak i vtven if b then D1 else D2 vtven if b then D1 vtven case e of D1 : : : Dn end cykly while b do D1 cykly repeat D1 until b jsou D'-programy. (Pascal je D'-struktury a goto). 0

0

0

0

0

0

0

0

0

0

D sem D take D <sem L (kad D-program je D'-programem). 0

e

of

repeat

D1

case

0

0

D : : : Dn 0

0

1

until

b

3.3 BJn programy

end

, if e=1 then

P P P

b b b

0

else if e=2 then

,

(B+hm, Jacopini) Jsou-li P1 : : : Pn BJn -programy, pak i vtven if b then P1 else P2 cykly ck k n tvaru loop if 1 then exit 1 if 2 then exit 2 . . . if k then exit k endloop

D1

D1 0

b

D2

else ...

0

while not( ) do

D1 0

3 SROVNN SLY JAZYK

11

jsou BJn-programy.

D vp BJ1 ) D sem D sem BJ1 <sem L Cyklus c1 z BJ1 -struktur je cyklus while. Pro vechna n je BJn <sem BJn+1 . 0

3.4 do-repeat-cycle-exit programy 3.4.1 REn programy

Tyto programy obsahuj vtven if b then P1 else P2 cyklus repeat P1 end p kaz exit(i), kde < i n 0

3.4.2 DREn programy

Tyto programy obsahuj tot co REn programy plus cyklus while b do P1

3.4.3 RECn programy

Tyto programy obsahuj tot co REn programy plus p kaz cycle(i), kde < i n 0

3.4.4 DRECn programy

Tyto programy obsahuj obsahuj vech pt konstrukc z DREn a RECn . repeat P end je cyklus, ve kter m se P provd tak dlouho, dokud se nenaraz na exit(i) resp. cycle(i). exit(i) je ukonen vech repeat ... end cykl nadazench p kazu exit(i) a do rovn i vetn (hloubka uzvorkovn exit(i) "zvorkami" repeat ... end). cycle(i) znovuzahjen provdn cuklu nadazen ho cycle(i) na i-t rovni repeat

-

...... repeat ... ... ... .. ... repeat .. .. .. .. ... ... .. . . . . . . . . . . . . cycle(1) .. .. .. exit(3) ............... .. .. .. .. exit(1) ........... .... .. . . .. . . . . . . . . . . . . . . . . . . . . . cycle(2) ..... ..... .. .. .. .. end . . . . . . . . . . . . . . . . . . . . . . . . . . .. ... .. .. end .. .. .. .. end .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..

-

Zejm REn sem DREn RECn DRECn . Plat BJn <sem RE1 , a protoe BJn <sem BJn+1 , kad BJn+1 program lze vyjdit jako RE1 program.

4 PODPROGRAMY

12

Ledgard : REequivsem RECn <sem DREn DRECn .

Analogicky DREn <sem DREn+1 . Kosarajan s Petersonem dokzali, e RE sem L. Libovoln L-program s npredikty, n (vetn v censobnch vskyt t ho prediktu) lze vyjdit jako REn 1 program takov, e a) maximln rove# vnoen cykl repeat-end je men nebo rovna n ; b) maximln rove# vnoovn if-then-else je men nebo rovna n 1

2

;

1

3.5 Kosarajanova hierarchie RE

1

REC1 DRE1 DREC1 L

? ? REC ? REC ? BJ ? BJn ? BJ ?

REn RECn RE2 RE1

2 1

? ? DREC ?

DREn DRECn DRE2

2

DRE1 DREC1

1

1

DD

0

BJ1

V tomto obrzku znamen # relaci <sem a relaci sem .

4 Podprogramy Motivace: Podprogramy jsou procedury a funkce. Zmenuj velikost k!du, protoe odstra#uj jeho opakovn . Podporuj rozklad probl mu na podprobl my, co se uplatn pi metodice nvrhu algoritm. Podprogram se denuje deklarac , pouije se voln m. Voln procedury je p kaz, kdeto voln funkce je vraz. Denice m dv sti: hlaviku, co je dohoda s uivatelem, a tlo, kter je realizac dohody, pro uivatele nen podstatn . Dvody pro fyzick oddlen hlaviky a tla: itelnost rekurze (pi vzjemn m voln , pi voln sebe sama) podprogram modulu (modulrn vstavba program) Hlavika udv jm no podprogramu (nab zen sluby) seznam formln ch parametr ? specikace jejich typu ? zpsob nhrady formln ho skutenm

hodnotou (Pascal)

vsledkem (Ada)

hodnotou-vsledkem (Ada)

4 PODPROGRAMY

13

odkazem (adresou-Pascal, jm nem-Algol60) ? reim (m sto zpsobu nhrady)

in vstupn parametr

out vstupn parametr

inout v/v parametr

u funkce typ vracen hodnoty

4.1 Nhrada formln ho parametru skute nm 4.1.1 Hodnotou

skuten . ...

.

A(...,s,...) ..

formln

-

........................ .

hodnota

procedure p:=s

... ...

A(...,p,...)

x:=p p:=4

Pi voln procedury je hodnota skuten ho parametru zkop rovna do lokln promnn p. Zmny hodnoty p se na skuten m parametru neprojevuj , hodnota skuten ho parametru nen zmnna.

4.1.2 Vsledkem procedure A(...,p,...)

A(...,s,...) .

O

.. .. .. .. .. .. .. .. .. .. .. . .......................

vsledek

p:=4 x:=p s:=p

Hodnota skuten ho parametru v dob voln nen pouita. ,skal tohoto je, e zle na poad , v kter m se zpracovvaj parametry, nap. A(s,s) A(B(i),i).

4.1.3 Hodnotou-vsledkem .hodnota ............... . ...

A(...,s,...) .

O

.. .. .. . ......

-

.. .. .. .. .. .. .. .. .. .. .. . .......................

vsledek

procedure A(...,p,...) p:=s x:=p p:=4 s:=p

V prbhu vpotu procedury nen globln s mnno, a na konci se zkop ruje hodnota p do s.

4 PODPROGRAMY

14

4.1.4 Odkazem A(...,s,...) .

I

-

.........................

procedure A(...,p,...)

ztotonn p a s x:=p p:=4

Pi voln odkazem je formln parametr ztotonn se skutenm, take zmny formln ho parametru se ihned projevuj na obsahu skuten ho parametru.

4.1.5 Jmnem procedure A(...,p,...)

A(...,s,...)

x:=p ( x:=s

Zavolm-li A skutenm parametrem, tak jsou vechny vskyty p nahrazeny textov s.

4.1.6 Srovnn rozdl I:integer A:array 1..10]of integer procedure V#m%na(x,y) pom:integer begin pom:=x x:=y y:=pom end begin I:=3 A I}:=6 write(I,A I]) V#m%na(I,A I]) write(I,A I]) end

Vstup: hodnotou vsledkem hodn.-vsl. odkazem jm nem

3 6 3 6 ? ? 6 3/6 6 3 6 3

4.2 Reim parametr - ADA

neuvd zpsob nhrady formln ho skutenm explicitn, ale vyaduje udn reimu parametru.

in vstupn hodnota dna skutenm parametrem, povolena pouze reference, nelze mnit jeho hodnotu out vstupn parametr jeho hodnota dv hodnotu skuten ho prametru, povolena pouze denice, nelze ho uvdt

na prav stran piazovac ho p kazu inout povolena denice i reference

4 PODPROGRAMY

15

Parametr skalrn ho datov ho typu lze pedvat nhrada hodnotou (in) vsledkem (out) hodnotouvsledkem (inout) Parametr strukturovan ho typu lze pedvat kop rovn m nebo referenc , jsou-li vsledky rzn , jde o chybn program.

4.3 Vedlej efekty podprogram

jsou zmny hodnot globln ch promnnch v tle podprogramu a to bu% p mo zmnou hodnoty globln promnn , nebo pomoc parametr. U procedur jsou vedlej efekty nutn , jinak by byly jen przdnmi p kazy. U funkc je vedlej efekt nedouc , u nkterch jazyk je zkaz kontrolovan kompiltorem. function F(var x:real):real begin x:=abs(x) F:=sqrt(x) end ... x:=-9 write(x+F(x))

Voln odkazem mn hodnotu skuten ho parametru bhem vpotu, take nen jasn , co program vytiskne.

4.4 Voln podprogram

Zajitn nvratu (z hlediska implementace) a pedn zen . Ped pedn m zen schova registr, po nvratu obnova. Podprogramy jsou oteven na m sto voln se zkop ruje tlo uzaven Jednoduch nvratov mechanismus spo v v tom, e pi voln podprogramu se do nj zap e adresa, kam se m vrtit zen . Tento model selhv pi rekurzivn m voln procedur. Rekurzivn podprogramy mohou opakovan volat sebe sama, nebo se mohou volat navzjem, nap. podprogram A zavol podprogram B, ten zavol C a ten opt zavol A. Klasickm p kladem rekurzivn ho voln je program pro vpoet Fibonacciho sel: function Fib(n):int begin if n=1 or n=2 then Fib:=1 else Fib:=Fib(n-1)+Fib(n-2) end

Zsobn k nvratovch adres je nutn, stejn jako aby kad zavoln procedury vytvoilo dal kopii lokln ch promnnch. Aktivan zznam bloku (procedury) obsahuje: parametry (skuten ) nvratovou adresu ukazatel na aktivan zznam volaj c ho lokln promnn ukazatel na aktivan zznam s globln mi promnnmi pomocn promnn pro vyhodnocen vraz

5 MODULY

16

Blokov struktura Blok ! <deklarace>

]

=posloupnost deklarac nsledovan posloupnost p kaz

BASIC, COBOL - program je jedinn blok, vechny promnn jsou globln FORTRAN - hl. program je blok, kad podprogram je blok, jsou zapisovny za sebou PASCAL, ADA, ALGOL - program je jedinn blok, ale m vnoen bloky vnoovn blok (nesting).

S t m souvis rozsah platnosti deklarac . Scope deklarace platnost pouze pro vnitek bloku, s vyj mkou vnoench blok s redeklarac t ho jm na. Objekt je lokln ve sv m bloku, globln ve vnoench bloc ch, a neexistuje v nadazench bloc ch.

Petovn jmen podprogram (overloading)

maj -li rzn podprogramy stejn jm no ) overloading nezakrvaj se, pokud maj rzn prol parametr (stejn poet, rzn typ) maj -li parametry stejn prol, zakrvaj se stejnm zpsobem jako objekty

Syntactic suggar

je mono pojmenovat skuten parametry

uvedeme-li jm na parametr, nemus me zachovvat poad je monost explicitn ho zadvn parametr

proc P(PAR1,PAR2,PAR3) voln : P(PAR2=>1,PAR3=>A,PAR1=>1)

proc P(P1,in P2:=0) voln : P(P1=>1)

monost denovat opertory

function "+"(lev#,prav#:vektor):vektor A,B,C:vektor A:=B+C m sto +(B,C)

5 Moduly Moduly jsou programov jednotky, nab zej c celou adu slueb programovch (procedury a funkce) a datovch (typy, objekty). Kad modul m dv sti Hlavika viditeln st specikace slueb Tlo skryt st realizace slueb Modul je abstraktn deklarac . Tlo me obsahovat vnitn procedury, funkce, promnn . P klad modulu si uvedeme na implementaci fronty.

5.1 Abstraktn datov typ FRONTA

Signatura: new vytv frontu add pidv prvek remove odstra#uje prvek empty vrac booleovskou hodnotu, zda je fronta przdn front vrac prvek v ele fronty

5 MODULY

17

AXIOMY: empty(add(x,f))=false front(add(x,new))=x front(add(y,add(f,x)))=front(add(x,f)) remove(add(x.new))=new remove(add(y,add(f,x)))=add(y,remove(add(x,f))) front(new), remove(new) nedenovno

Operan s mantika:

new <> add x < x1 x2 : : : xn > front < x1 x2 : : : xn > remove < x1 x2 : : : xn > empty < x1 x2 : : : xn > empty <> true =

(

< x1 x2 : : : xn x > x1 < x2 : : : xn > false

) =

(

) =

(

(

(

) =

) =

) =

Fronta je implementovna jako linern zetzen seznam, doplnn o dva ukazatele elo ukazuje na prvek v ele fronty a voln# ukazuje na voln m sto za koncem fronty. Modul neumo#uje nesmysly typu elo:=18. pack FRONTA is proc Ini proc Vlo'(x:int) proc Odeber(x:int) fun empty:bool end FRONTA pack body FRONTA is type Elem is rec Dal:=Êlem Hodn:int end rec elo:Êlemvoln#:Êlem proc Ini begin elo:=new(Elem) voln#:=elo end proc Vlo'(x:int) begin Voln#^.hodn:=x Voln#^.Dal:=new(Elem) Voln#:=Voln#^.Dal end proc Odeber(x:int) ...

5 MODULY fun empty:bool begin Empty:=elo=voln# end end.

Vyuit slueb modulu fronta program B with FRONTA begin ... Fronta.Ini Fronta.Vlo'(25) ... end B

5.1.1 Realizace a pouit nkolika front I. Pouit generickch programovch jednotek generic pack VZOR-FRONTY is proc Ini proc Vlo'(xint) proc Odeber(x:int) fun Empty:bool end pack body VZOR-FRONTY is to sam co u modulu FRONTA end program A with VZOR-FRONTY pack Vstupn-fronta is new VZOR-FRONTY pack V#stupn-fronta is new VZOR-FRONTY begin Vstupn-fronta.Ini V#stupn-fronta.Ini ... end A

II. Export datovho typu pack ADT-FRONTA is type FRONTA is private proc Ini(F:FRONTA) proc Vlo'(F:FRONTA,x:int) ... end pack body ADT-FRONTA is type Elem is ... type FRONTA is rec elo:Êlem voln#:Êlem end rec proc Ini(F:FRONTA) begin F.elo:=new(Elem) F.voln#:=F.elo

18

6 KOMPILACE PROGRAMU

19

end atd.

5.1.2 Realizace a pouit front r znho typu Zavedeme parametr generick ho modulu

generic type T is private pack PAR-VZOR-FRONTA is proc Ini ... end. program A pack FRONTA-INT is new PAR-VZOR-FRONTA(T=>int) pack FRONTA-CHAR is new PAR-VZOR-FRONTA(T=>char)

6 Kompilace programu

programov jednotka procedura, funkce, modul, proces, . . . kompilan jednotka program, progr. jednotka, specikace (hlavika) prog. jednotky, tlo prog. jednotky Peklad vechny programov jednotky spolen (Pascal) vechny programov jednotky oddlen a nezvisle (FORTRAN) vhoda: pi ladn jedn procedury nemus m znova pekldat cel program nevhoda: nezachyt nekorektnosti pi vzjemn m voln procedur (rzn poet parametr, neshodnost typ) programov jednotky mono kompilovat separtn v takov m poad , aby bylo mono kontrolovat korektnost pouit slueb jinch programovch jednotek (Ada) Knihovna kompilan ch jednotek jmno jednoznan denice (proc,fun,pack,task) druh integer verze, pi kad m pekladu, kter mn sluby +1 {(p)ed1,ver1),...,(p)edn,vern)} seznam kompilan ch pedchdc {(n$sl1,...,n$sln)} nsledn ci proc P(in X:T1 out y:T2) fun F(in X:T3):T4 type T ... sluby

6.0.3 Sestaven, knihovny

proven plnosti knihovny vzhledem k hlavn programov jednotce Main proc KOMP-STR(lib,M,CH,KS) kde lib knihovna, vstupn parametr M hlavn pr. jednotka (Main) CH chybj c pr.j. (nevrt vechny), vstupn parametr KS kompilan struktura pro M

6 KOMPILACE PROGRAMU

20

KS:= CH:={M} while CH6= and CH\lib6= do nech* 2CH\lib CH:=CH-{ }{m|( ,v)2 .p)ed} .n$sl CH:=CH-KS KS:=KS{ } end do if CH= then "pln, v KS kompilan struktura" else "nepln, v KS chybj c "

n

n

n

n

n

n

6.0.4 Aktulnost knihovny fun AKTU!LN+(KS):Bool ,pln$ kompilan struktura pro pr.j. M AKT:=true POM:=KS while POM6= and AKT do nech* 2POM AKT:={p|(p,v)2 .p)ed and v6=p.verze}= POM:=POM-{ } end do aktu$ln:=AKT

n

n

n

6.0.5 Rekompilan seznam proc REKOMP(KS,OK,RS)

kompilan struktura OK pr.j. z KS, kter jsou OK RS rekompilan seznam

KS

OK:= PS:=<> POM:=KS while POM6= do nech* 2POM tak, 'e {p|(p,v)2 .p)ed)OKRS if {p|(p,v)2 .p)ed}OK and 8( ) 2 .p)ed then OK:=OK{ } else RS:=RS+< > POM:=POM-{ } end do

n

n

n n n

n p v

n

6.0.6 Vyjmky standardn numeric, domain, range' zpracovn : hlen a abort uivatelsk deklarace: error, exception

vyvoln : raise error zpracovn

begin ... exception when error => ... when numeric.error => ... when other => ... end

Rozsah platnosti jm na vyj mky uren staticky. Pedn zen po vyvoln vyj mky (nalezen handleru).

7 PARALELN PROGRAMOVN

21

7 Paraleln programovn 7.1 Paraleln procesy

spolen pam$, zas ln zprv asymchronn bh ? dn pedpoklady o vzjemn rychlosti proces ? libovoln prol nn instrukc proces ? prol naj se atomick instrukce

N:integer := 0 task body P1 is begin N:=N+1 end P1 task body P2 is begin N:=N+1 end P2

Me doj t k libovoln mu prol nn atomickch instrukc :

. . . pkaz N:=N+1 je atomick

. . . pkaz N:=N+1 nen atomick

proces instukce N 0 P1 INC N 1 P2 INC N 2 proces P1 P2 P1 P2 P1 P2

instrukce Load R1,N Load R2,N INC N INC N Store R1,N Store R2,N

N R1 R2 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1

7.2 Problm vzjemnho vylou en pro N proces

N proces provd posloupnosti p kaz, kter mohou bt rozdleny na sti, tzv. kritick sekce a sekce, kter nejsou kritick . Program mus m t vlastnost vzjemnho vylouen provdn p kaz kritickch sekc dvou i v ce proces se nesm prol nat, tj. dn dva procesy nesm bt souasn ve svch kritickch sekc ch.

Poadavky a pedpoklady

1. -een mus spo vat v pidn jistch p kaz tzv. vstupnho protokolu ped p kazy kritick sekce a jinch p kaz tzv. vstupnho protokolu za p kazy kritick sekce. Obecn: loop

Nekritick sekce' Vstupn protokol' Kritick sekce' Vstupn protokol' endloop

2. Pedpokld se, e procesy nemohou skonit bhem provdn kritickch sekc a protokol. Mohou skonit v sekc ch, kter nejsou kritick , co nesm ovlivnit provdn ostatn ch proces. 3. Nesm doj t k uvznut (deadlocku), jestlie nkolik proces provd vstupn protokol, jeden z nich mus uspt. 4. Nesm doj t ke strdn (starvation) jednotliv ho procesu provd -li prbn vstupn protokol (v konkurenci s ostatn mi procesy), mus v konen dob uspt. Provd -li proces vstupn protokol bez konkurence jinch proces, mus uspt (a to, pokud mono, rychle).


22

7.2.1 Vzjemn vylouen e!en .1 p: integer range 1..2 := 1

. . . kter proces me do KS

task body P1 is begin loop Nekritick$_sekce_1 loop exit when p=1 end loop Kritick$_sekce_1 p:=2 end loop end P1 task body P2 is begin loop Nekritick$_sekce_2 loop exit when p=2 end loop Kritick$_sekce_2 p:=1 end loop end P1 +

+

+

;

m vlastnost vzjemn ho vylouen (kdyby P1 i P2 byly souasn v KS, pi vstupujednoho bylo p=1, pi vstupu druh ho p=2, piem v KS nen mono p mnit spor) nenastane deadlock (oba procesy mohou nekonen dlouho souasn provdt svoje vstupn protokoly, muselo by souasn platit p=1, p=2) nikdo nestrd (P1 by musel neustle vstupovat do KS, piem P2 by souasn neustle provdl svj vstupn protokol, ale jakmile P1 opust KS, zmn p tak, e do KS vstoup P2) me selhat bez konkurence partnera (jestlie P2 skon v nekritick sekci, hodnota p neme bt ji nikdy zmnna z 2 na 1. P1 tedy nejpozdji pi druh m pokusu o vstup do KS uvzne ve sv m vstupn m protokolu)

7.2.2 Vzjemn vylouen e!en .2 C1,C2: integer range 0..1:=1 task body P1 is begin loop Nekritick$_sekce_1 loop exit when C2=1end loop C1:=0 Kritick$_sekce_1 C1:=1 end loop end P1 task body P2 is begin loop Nekritick$_sekce_2 loop exit when C1=1end loop C2:=0 Kritick$_sekce_1

7 PARALELN PROGRAMOVN C2:=1 end loop end P2

;

nem vlastnost vzjemn ho vylouen . K poruen vede tato posloupnost: 1. P1 testuje C2 a C2=1 2. P2 testuje C1 a C1=1 3. P1 nastav C1 na 0 4. P2 nastav C2 na 0 5. P1 vstoup do KS 6. P2 vstoup do KS

7.2.3 Vzjemn vylouen e!en .3 C1,C2: integer range 0..1:=1 task body P1 is begin loop Nekritick$_sekce_1 C1:=0 loop exit when C2=1end loop Kritick$_sekce_1 C1:=1 end loop end P1 task body P2 is begin loop Nekritick$_sekce_2 C2:=0 loop exit when C1=1end loop Kritick$_sekce_2 C2:=1 end loop end P2

' +

;

m vlastnost vzjemn ho vylouen me nastat deadlock 1. P1 nastav C1 na 0 2. P2 nastav C2 na 0 3. P1 testuje C2 a zstv viset 4. P2 testuje C1 a zstv viset

7.2.4 Vzjemn vylouen e!en .4 C1,C2: integer range 0..1:=1 task body P1 is begin loop Nekritick$_sekce_1 C1:=0

23

7 PARALELN PROGRAMOVN loop exit when C2=1 C1:=1 C1:=0 end loop Kritick$_sekce_1 C1:=1 end loop end P1 task body P2 is begin loop Nekritick$_sekce_2 C2:=0 loop exit when C1=1 C2:=1 C2:=0 end loop Kritick$_sekce_2 C2:=1 end loop end P2 +

; ;

m vlastnost vzjemn ho vylouen proces me strdat me nastat deadlock

7.2.5 Vzjemn vylouen Dereer v algoritmus C1,C2: integer range 0..1:=1 p: integer range 1..2:=1 task body P1 is begin loop Nekritick$_sekce_1 C1:=0 loop exit when C2=1 if p=2 then C1:=1 loop exit when p=1 end loop C1:=0 endif end loop Kritick$_sekce_1 C1:=1 p:=2 end loop end P1 task body P2 is begin

24

7 PARALELN PROGRAMOVN loop Nekritick$_sekce_2 C2:=0 loop exit when C1=1 if p=1 then C2:=1 loop exit when p=2 end loop C2:=0 endif end loop Kritick$_sekce_2 C2:=1 p:=1 end loop end P1 + + + +

m vlastnost vzjemn ho vylouen nenastane deadlock nikdo nestrd neselhv ani bez konkurence partnera

7.2.6 Vzjemn vylouen pro N proces Algoritmus "bakery"

Vybr$: array(1..N) of integer :=(others=>0) .slo: array(1..N) of integer :=(others=>0) task body Pi is I:constant integer := (slo tohoto procesu) begin loop Nekritick$_sekce_i Vybr$(I):=1 .slo(I):=1+max(.slo) Vybr$(I):=0 for J in 1..N loop if J<>I then loop exit when Vybr$(J)=0 endloop loop exit when ((.slo(J)=0) or (.slo(I)<.slo(J)) or (.slo(I)=.slo(J) and I<J)) endloop endif endloop Kritick$_sekce_i .slo(I):=0 endloop end Pi + + + +

m vlastnost vzjemn ho vylouen nenastane deadlock nikdo nestrd neselhv ani bez konkurence partner

25


26

7.3 Semafory datov typ

mnoina hodnot: nezporn cel sla (obecn semafor) nebo {0,1} (binrn semafor) Operace (semafor s neuritm ekn m) Wait(s) if S>0 then S:=S-1 else

pozastav provdn procesu na semaforu S

Signal(S)

if na semaforu S jsou pozastaveny njak procesy then vyber jeden z nich a nech ho pokraovat else S:=S+1

Vlastnosti semaforu Wait(S) a Signal(S) jsou

atomick operace (zajitno HW nebo OS). Konkr tn u Wait dn p kaz neme prol nat mezi testem S>0 a sn en m hodnoty S nebo pozastaven m procesu. Semafor mus bt inicializovn nezpornou poten hodnotou Pro semafor S plat tyto invarianty: S=> and S=S0+#Signal+#Wait

Varianty semaforu semafor s neuritm ekn m semafor s ekn m ve front FIFO Wait(s) if S>0 then S:=S-1 else

S'

Signal(S)

if na semaforu S then vyber prvn else S:=S+1

pozastav provdn procesu na semaforu S a zaa% ho do fronty na semaforu

jsou pozastaveny njak procesy z fronty a nech ho pokraovat

semafor s aktivn m ekn m Wait(s) loop if S>0 then S:=S-1 exit endif endloop

Signal(S) S:=S+1

7.3.1 Vzjemn vylouen N proces pomoc semaforu S:semaphore:=1 task body Pi is begin loop Nekritick$_sekce_i Wait(S) Kritick$_sekce_i Signal(S) endloop end Pi + +

m vlastnost vzjemn ho vylouen nenastane deadlock

7 PARALELN PROGRAMOVN +

; ;

27

nikdo nestrd pro semafory s ekn m ve front pro N>2 me doj t ke strdn pro semafory s neuritm ekn m me doj t ke strdn pro semafory s aktivn m ekn m

7.4 Producent a konzument

Probl m: Jsou dva typy proces. Producenti produkuj datov elementy, kter zas laj konzumentm. Konzumenti zpracovvaj datov elementy, kter dostvaj od producent. Producent zas l elementy do fronty (FIFO bu2eru), odkud si je konzument vyzvedv, tj. vechny vyprodukovan jsou zkonzumovny ve stejn m poad . Producent nesm zas lat do pln fronty, konzument nesm st z przdn .

e!en pomoc kruhovho bu"eru a semafor Buff: array(0..N-1)of element In,Out:integer:=0 Poet:semaphore:=0 poet prvk/ v bufferu Voln:semaphore:=N poet voln#ch mst task body Producent is I:element begin loop Produkuj(I) Wait(Voln) Buff(In):=I In:=(In+1)mod N Signal(Poet) endloop end Producent task body Konzument is I:element begin loop Wai(Poet) I:=Buf(Out) Out:=(Out+1)mod N Signal(Voln) Konzumuj(I) endloop end Konzument

7.5 Monitory

-een probl mu producentkonzument monitor PKmon is Poet:integer:=0 In,Out:integer:=0 Buf:array(0..N-1) of element Nen_pln#,Nepr$zdn#:condition

<- podmnkov prom%nn

procedure Ulo'(in I:integer) is begin if Poet=N then Wait(Nen_pln#) endif Buf(In)=IIn:=(In+1)mod N Poet:=Poet+1 Signal(Nepr$zdn#)


28

end procedure Odeber(out I:integer) is begin if Poet=0 then Wait(Nepr$zdn#) endif I:=Buf(Out)Out:=(Out+1)mod N Poet:=Poet-1 Signal(Nen_pln#) end end monitor task body Producent is I:element begin loop Produkuj(I)Ulo'(I)endloop end task body Konzument is I:element begin loop Odeber(I)Konzumuj(I) endloop end

Monitor programov jednotka: datov objekty, procedury, podm nkov promnn vlastnost vzjemn ho vylouen , pouze jeden proces me provdt proceduru monitoru podm nkov promnn operace: Wait(c) proces je pozastaven ve FIFO front na promnnou C. Nevztahuje se na nj vlastnost ME. Signal(c) je-li fronta na C neprzdn, je oiven proces z ela fronty Nonempty(C) funkce vrac true, je-li fronta na C neprzdn

Emulace semaforu pomoc monitoru monitor Emulace_semaforu is S:integer:= ... Nenulov#:condition procedure Wait_semaforu is begin if S=0 then Wait(Nenulov#) endif S:=S-1 end procedure Signal_semaforu is begin S:=S+1Signal(Nenulov#) end

Poznmka rovn emulace monitoru pomoc semafor je mon, ale je komplikovanj , monitor je prostedek vy rovn.

7.6 Readers and writers

3teni a p sai - abstrakce p stupu do DB. Probl m: jsou dva typy proces Readers tou data ze sd len pamti, vi sob navzjem nemaj poadavek vzjemn vlunosti. Writers zapisuj data do sd len pamti, poaduj vzjemnou vlunost jak vi sob navzjem, tak i vi tenm.

7 PARALELN PROGRAMOVN task body Reader is begin loop Zahaj_ten .ti_data Konec_ten endloop end Reader task body Writer is begin loop Zahaj_z$pis Pi_data Konec_z$pisu endloop end Writer

Monitor pro probl m Readers and writers monitor RWM ten$)i:integer:=0 pe:boolean:=false OK_ten,OK_z$pis:condition procedure Zahaj_ten is begin if pe or Nonempty(OK_z$pis) then Wait(OK_ten) endif ten$)i:=ten$)i+1 Signal(OK_ten) end procedure Konec_ten is begin ten$)i:=ten$)i-1 if ten$)i=0 then Signal(OK_z$pis) endif end procedure Zahaj_z$pis is begin if ten$)i<>0 or pe then Wait(OK_z$pis) endif end procedure Konec_z$pis is begin pe:=false if nonempty(OK_ten) then Signal(OK_ten) else Signal(OK_z$pis) endif end end RWM

7.7 The problem of the dining philosophers

Probl m: ve spolenosti je 5 lozof. Tito jen jed a pemlej : task body Filozof is begin loop p)em#len vstupn_protokol jdlo v#stupn protokol endloop end Filozof

29

7 PARALELN PROGRAMOVN U stolu je do kruhu 5 tal , mezi nimi je 5 vidliek. Mme navrhnout protokoly, aby byly splnny poadavky Filozof me j st jen m-li 2 vidliky Jednu vidliku nemohou uchopit 2 lozofov souasn nenastane deadlock nikdo nestrd (nehladov ) chovn lozofa, kter mu nekonkuruje soused, je efektivn

e!en pomoc semafor Vidlika:array(0..4) of semaphore :=(others=>1) task body Filozof is (I je identifikace filozofa) begin loop P)em#len Wait(Vidlika(I)) Wait(Vidlika((I+1) mod 5))) Jdlo Signal(Vidlika(I)) Signal(Vidlika((I+1) mod 5))) endloop end Filozof

jednu vidliku nemohou uchopit dva lozofov souasn me nastat deadlock (vichni souasn uchop vidliky po levici)

Deadlock pedchoz ho een odstran me nap klad t m, e souasn povol me j st jen tyem lozofm. Volno:semaphore :=4 Vidlika:array(0..4) of semaphore :=(others=>1) task body Filozof is (I je identifikace filozofa) begin loop P)em#len Wait(Volno) Wait(Vidlika(I)) Wait(Vidlika((I+1) mod 5))) Jdlo Signal(Vidlika(I)) Signal(Vidlika((I+1) mod 5))) Signal(Volno) endloop end Filozof

jednu vidliku nemohou uchopit dva lozofov souasn neme nastat deadlock nikdo nestrd mus me pedpokldat, e semafor Volno m FIFO uspodn

30


31

Asymetrick e!en Aspo# jeden lozof se bude dit jinm algoritmem ne ostatn . Nechme prv tyi lozofy provdt pvodn nvrh, pt ho nechme naped ekat na svoji pravou vidliku a pak teprve na levou. Vidlika:array(0..4) of semaphore :=(others=>1) task body Filozof0123 is (I je identifikace filozofa) begin loop P)em#len Wait(Vidlika(I)) Wait(Vidlika((I+1) mod 5))) Jdlo Signal(Vidlika(I)) Signal(Vidlika((I+1) mod 5))) endloop end Filozof0123 task body Filozof4 is begin loop P)em#len Wait(Vidlika(0)) Wait(Vidlika(4)) Jdlo Signal(Vidlika(4)) Signal(Vidlika(0)) endloop end Filozof4

jednu vidliku nemohou uchopit dva lozofov souasn neme nastat deadlock nikdo nestrd

e!en pomoc monitoru monitor Vidl-monitor Fork:array(0..4) of integer range 0..2 :=(others=>2) OK_jdlo:array(0..4) of condition procedure Uchop_vidliku(I:integer) is begin if fork(I)<>2 then Wait(OK_jdlo(I) endif fork((I+1) mod 5) := fork((I+1) mod 5)-1 fork((I-1) mod 5) := fork((I-1) mod 5)-1 end procedure Vra*_vidliku(I:integer) is begin fork((I+1) mod 5) := fork((I+1) mod 5)+1 fork((I-1) mod 5) := fork((I-1) mod 5)+1 if fork((I+1) mod 5)=2 then Signal(OK_jdlo((I+1) mod 5)) endif if fork((I-1) mod 5)=2 then Signal(OK_jdlo((I-1) mod 5)) endif end end Vidl-monitor task body Filozof is begin loop P)em#len


32

Uchop_vidliku(I) Jdlo Vra*_vidliku(I) endloop end

jednu vidliku nemohou uchopit dva lozofov souasn neme nastat deadlock proces me strdat dva lozofov se mohou spiknout, e vyhladov sv ho spolen ho souseda.

7.8 Synchronizace proces Ada

soubh proces randezvous task A task body A is begin repeat ... B.SYNCHRON ... until false end

task B entry SYNCHRON end B task body B is begin repeat ... ACCEPT SYNCHRON ... until false end

procesy jsou paraleln synchronn proces B ek na synchronizan m m st aktivn proces si rande vyaduje (stav se do fronty na ekn na B) po uskutenn rande asynchronn proces pokrauje

7.8.1 Synchronn vmna dat task A is end A task body A is x1:D1 y1:D2 begin ... B.KOM(x1,y1) ... end A

task B is entry KOM(x:in D1,y:out D2) end B task body B is x2:D2 y2:D2 z:D1 w:D2 begin ... accept KOM(x2:in D1y2:out D2) do z:=x2 y2:=w end KOM ... end B

7.8.2 Selektivn ekn volanho na randezvous

e probl m zatvrdnut pasivn ho procesu. p1,. . . ,pn jsou zmky, proces nab z n slueb souasn, na sluby se stav fronty aktivn ch proces, u jednch dve ek proces maximln 30 sekund, pak pokrauje. Proces vyb r procesy z front za false zmkem nedeterministicky.

7 PARALELN PROGRAMOVN select when p1 => accept E1 do ... end or when p2 => accept E2 do ... end or ... or when pn => accept En do ... end or delay 30.0sec or terminate end select

7.8.3 Selektivn voln randezvous select T.E(...) ... else end select

select T.E(...) ... or delay 10sec end select

pack SEMAFORY is task type B_SEM is entry WAIT entry SIG end B_SEM task type SEM is entry INIT(N:in int) entry WAIT entry SIG end SEM pack body SEMAFORY is task body B_SEM is loop select accept WAIT accept SIG or terminate end select endloop end B_SEM task body SEM is K:int N1:int begin accept INIT(N:in int) do K:=NN1:=N end loop select when K>0 > accept WAIT do K:=K-1 or accept SIG do if K
33

7 PARALELN PROGRAMOVN end SEM end SEMAFORY

7.8.4 Producent a konzument v Ad task body P is loop produkce C BUF.WRITE(C) exit when C="#" end loop end P

task body K is loop BUF.READ(C) konzumace C exit when C="#" end loop end K

task BUF is entry READ(C:out char) entry WRITE(C:in char) end BUF task body BUF is B:array(1..100)of char po:int:=0 In,Out:range 1..100:=1 begin loop select when po<100 => accept WRITE(C:in char) do B(In):=C end In:=(In mod 100)+1 po:=po+1 or when po>0 => accept READ(C:out char) do C:=B(Out) end Out:=(Out mod 100)+1 po:=po-1 or terminate end select end loop end BUF

34

No title

Recommend Documents