Os-04 Mp Komunikacija

6. MEĐUPROCESNA KOMUNIKACIJA 6.1. Problem proizvođača i potrošača Proizvođač je ciklički proces u kojem se generiraju podaci, uobličuju u tzv. poruku i šalju poruke procesu potrošaču. Potrošač je također ciklički proces koji čeka na poruke i prihvaća poslanu poruku i koristi (potroši) poruku. Pretpostavlja se da proizvođač i potrošač obavljaju svoj posao proizvoljnom brzinom.

1

proizvođač ponavljati

potrošač ponavljati

proizvesti poruku;

čekati poruku;

poslati poruku;

prihvatiti poruku;

do beskonačnosti

potrošiti poruku; do beskonačnosti

Problem proizvođača i potrošača je klasični problem međuprocesne komunikacije ( Producer - Consumer problem, readers and writers problem ).

2

a1

6.1.1. Komunikacija preko neograničenog međuspremnika ( unbounded - buffer ) Međuspremnik se može organizirati u radnom spremniku kao polje

MS[0] MS[1] MS[2]

↑↑ UL IZ

3

proizvođač: ponavljati proizvesti poruku p; MS[UL] :=p ; UL :=UL+1 ; do beskonačnosti potrošač: ponavljati pričekati da bude UL > IZ ; r :=MS[IZ] ; IZ :=IZ+1 ; potrošiti poruku r; do beskonačnosti 4

a2

MS[0] MS[1] MS[2] MS[3] MS[4] MS[5] MS[6] MS[7]

... ↑ IZ

↑ UL

UL - IZ = 4

MS[0] MS[1] MS[2] MS[3] MS[4] MS[5] MS[6] MS[7]

... ↑ ↑ UL IZ

UL - IZ =0

Broj poruka u međuspremniku = UL -IZ Uvodi se opći semafor OSEM(1) OSEM(1).V - broj poruke početna vrijednost OSEM(1).V :=0 početne vrijednosti UL :=0, IZ :=0 5

proizvođač: ponavljati

potrošač: ponavljati

proizvesti poruku p ;

ČEKAJ_OSEM(1) ;

MS[UL] :=p ;

r :=MS[IZ] ;

UL := UL +1 ;

IZ :=IZ+1 ;

POSTAVI_OSEM(1) ;

potrošiti poruku r ;

do beskonačnosti

do beskonačnosti

6

a3

6.1.2. Komunikacija preko ograničenog međuspremnika ( bounded - buffer ) MS 0

1

2

3

4

Ν −2

Ν−1

↑↑ UL IZ

UL :=( UL+1 ) modN IZ :=( IZ+1 ) modN • Treba brojati i prazna mjesta i poruke u spremniku. • Proizvođač mora pričekati ako nema praznih mjesta.

7

OSEM(1).V - broj poruka u međuspremniku OSEM(2).V - broj praznih mjesta u međuspremniku Početne vrijednosti : UL :=0 IZ :=0 OSEM(1).V :=0 OSEM(2).V :=N proizvođač: ponavljati proizvesti poruku p ; ČEKAJ_OSEM(2) ; MS[UL] :=p ; UL :=(UL+1) modN POSTAVI_OSEM(1); do beskonačnosti

potrošač: ponavljati ČEKAJ_OSEM(1) ; r :=MS[IZ] ; IZ :=(IZ+1) modN ; POSTAVITI_OSEM(2); potrošiti poruku r ; do beskonačnosti 8

a4

Nije potrebna posebna zaštita međuspremnika jer : •

proizvođač djeluje samo na kazaljku UL

•

potrošač djeluje samo na kazaljku IZ

Međutim, ako npr. više proizvođača stavlja poruke u međuspremnik, pristup do kazaljke UL postaje kritični odsječak. À

1 À

À

2

À

potrošač

i

može se zaštititi binarnim semaforom BSEM(1)

proizvođači

9

proizvođač i : ponavljati proizvesti poruku p ; ČEKAJ_OSEM(2) ; ČEKAJ_BESM(1) ; MS[UL] := p ; UL :=(UL+1) modN ; POSTAVI_BSEM(1) ; POSTAVI_OSEM(1) ; do beskonačnosti Potrošač ostaje nepromijenjen. 10

a5

6.1.3. Komunikacija preko reda poruka Pretpostavimo da proizvođač i potrošač mogu pristupiti do reda RED_PORUKA. •

Proizvođač stavlja poruke u red, a potrošač uzima poruke iz reda.

•

Kada je red prazan potrošač čeka.

•

Čekanje je praktično ostvariti općim semaforom.

RED_PORUKA

OSEM(1) 0

OSEM(1).V

Početno stanje

11

RED_PORUKA

poruka j

poruka j+1

Dvije poruke u redu • S obzirom da i proizvođač i potrošač pristupaju redu ( opasno kada se stavlja prva poruka u red ili preuzima zadnja ! ), pristup treba zaštititi binarnim semaforom. • Poruka se stavlja u spremnik. Proizvođač mora dobaviti spremnik, a potrošač ga oslobađa. 12

a6

Pretpostavimo da postoji više parova proizvođača i potrošača. Svi proizvođači moraju dobavljati spremnike, a potrošači ih oslobađaju. Smisleno je organizirati skladište spremnika i to kao slog. SKLADIŠTE

...

OSEM (2) OSEM (2).V

Početno OSEM(2).V=N N-broj spremnika u skladištu

13

Ako ponestane spremnika, proizvođač mora čekati na OSEM(2) dok neki potrošač ne vrati spremnik. Pristup do skladišta je kritični odsječak i mora biti zaštićen binarnim semaforom. Pretpostavimo da postoji samo jedan proizvođač i jedan potrošač i da samo oni pristupaju skladištu. Tada se pristup do reda RED_PORUKA i sloga SKLADIŠTE može objediniti u jedan kritični odječak ! proizvođač ponavljati proizvesti poruku p; ČEKAJ_OSEM(2); ČEKAJ_BSEM(1); dobaviti spremnik sa sloga SKLADIŠTE; staviti p u spremnik; uvrstiti spremnik u RED_PORUKA; POSTAVI_BSEM(1); POSTAVI_OSEM(1); do beskonačnosti 14

a7

potrošač ponavljati ČEKAJ_OSEM(1); ČEKAJ_BSEM(1); preuzeti poruku r iz RED_PORUKA; vratiti spremnik na slog SKLADIŠTE; POSTAVI_BSEM(1); POSTAVI_OSEM(2); potrošiti poruku r; do beskonačnosti

15

Jedno krivo rješenje ! proizvođač ponavljati proizvesti poruku; ČEKAJ_BSEM(1); ČEKAJ_OSEM(2); dobaviti spremnika sa sloga SKLADIŠTE; staviti p u spremnik; uvrstiti spremnik u RED_PORUKA; POSTAVI_BSEM(1); POSTAVI_OSEM(2); do beskonačnosti

16

a8

Može se dogoditi slijedeće: •

Skladište je trenutno prazno i proizvođač će biti blokiran na OSEM(2);

•

Potrošač će biti blokiran na BSEM(1);

•

Ni jedan od njih ne može nastaviti.

OSEM (2)

BSEM (1)

-1

proizvođač

potrošač

To je potpuni zastoj ( engl. deadlock ) 17

6.2. Sinkronizacija procesa Ostvarivanje sustava zadataka zahtijeva mehanizme za sinkronizaciju. Problem proizvođača i potrošača nudi osnovnu zamisao. Ako pretpostavimo komunikaciju preko ograničenog spremnika duljine N=1 , tada je na početku OSEM(1).r = 0 (broj poruka) OSEM(2).r = 1 (broj praznik mjesta) UL i IZ nisu potrebni jer postoji samo jedan spremnik MS. proizvođač ponavljati proizvesti poruku p; ČEKAJ_OSEM(2); MS: = p; POSTAVI_OSEM(1); ddo beskonačnosti

potrošač ponavljati ČEKAJ_OSEM(1); r: = MS; POSTAVI_OSEM(2); potrošiti poruku r; ddo beskonačnosti

18

a9

• Međuspremnik čak nije ni potreban • Dva procesa se mogu naprosto vremenski sinkronizirati, a raditi neke proizvoljne poslove OSEM(1)

OSEM(2) Pi

Pj 19

proces pi

proces pj

ponavljati ČEKAJ_OSEM(2); nešto raditi; POSTAVI_OSEM(1); do beskonačnosti

ponavljati ČEKAJ_OSEM(1); nešto raditi; POSTAVI_OSEM(2); do beskonačnosti

Uz početne vrijednosti OSEM(1). r = 0 OSEM(2). r = 1 Krenut će najprije pi i nakon toga naizmjence pj i pi pi pj 20

a10

Općenito se sustav zadataka može ostvariti tako da: • svaki zadatak Ti prije početka ispituje “svoj” opći semafor OSEM(i) • svi neposredni prethodnici postavljaju taj semafor: • početna vrijednost OSEM(i).r = -(di - 1), gdje je di broj neposrednih prethodnika Primjer:

d1 = 0 d2 = 1 d3 = 1 d4 = 1 d5 = 3 d6 = 2 d7 = 2

T1

T3

T2 T5

T4 T6

OSEM(1).r: = 1 OSEM(2).r: = 0 OSEM(3).r: = 0 OSEM(4).r: = 0 OSEM(5).r: = -2 OSEM(6).r: = -1 OSEM(7).r: = -1

Neka je Ti tekst zadatka i T7 21

T4’

ČEKAJ_OSEM(4); T4; POSTAVI_OSEM(5); POSTAVI_OSEM(6);

T5’

ČEKAJ_OSEM(2); T2’ T2; POSTAVI_OSEM(5); POSTAVI_OSEM(6);

ČEKAJ_OSEM(5); T5; POSTAVI_OSEM(7);

T6’

ČEKAJ_OSEM(6); T6; POSTAVI_OSEM(7);

ČEKAJ_OSEM(3); T3’ T3; POSTAVI_OSEM(5);

T7’ ČEKAJ_OSEM(7); T7;

T1’

ČEKAJ_OSEM(1); T1; POSTAVI_ OSEM(2); POSTAVI_ OSEM(3); POSTAVI_ OSEM(4);

Zadaci Ti’ mogu biti pokretani proizvoljnim redosljedom, a sustav će se obavljati u skladu sa zadanim redosljedom. 22

a11

6.3. Problem potpunog zastoja Ilustracija potpunog zastoja je krivo rješenje komunikacije između dva procesa preko reda poruka uz ograničeno skladište spremnika. Nepažljivim ostvarivanjem međusobnog isključivanja može se izazvati potpuni zastoj. Za izazivanje potpunog zastoja potrebna su minimalno dva procesa i dva binarna semafora. proces P1 proces P0 1 3

2

ČEKAJ_BSEM(1); ČEKAJ_BSEM(2);

4

POSTAVI_BSEM(1); POSTAVI_BSEM(2);

ČEKAJ_BSEM(2); ČEKAJ_BSEM(1); POSTAVI_BSEM(2); POSTAVI_BSEM(1); 23

Može se dogoditi da zbog paralelnog izvođenja nastane redoslijed izvođenja 1 2 3 4 BSEM(1)

BSEM(2)

0

0

P1

P0 Potpuni zastoj

U ovom slučaju moglo bi se potpuni zastoj izbjeći ako bi se propisao redoslijed ispitivanja semafora. U općem slučaju to nije moguće. Za analizu fenomena potpunog zastoja ilustrativan je problem pet filozofa (Dijkstra). Filozofi u svom životu ne rade ništa drugo osim što misle i jedu. 24

a12

filozof i ponavljati misliti; jesti; do beskonačnosti Oni jedu po strogo utvrđenom ritualu - protokolu. F2

V2

V3

F3

F1

V4

V1

F4

V0

F0

25

filozof fi ponavljati misliti; prići k stolu; uzeti lijevu vilicu; uzeti desnu vilicu; jesti; spustiti vilice; do beskonačnosti filozof fi ponavljati lijeva vilica BSEM(i) misliti; desna vilica BSEM((i+1) mod 5) ČEKAJ_BSEM(i); ČEKAJ_BSEM((i+1) mod 5); jesti; POSTAVI_BSEM(i); POSTAVI_BSEM((i+1) mod5); 26 do beskonačnosti

a13

Može se dogoditi da u jednom času svi filozofi priđu k stolu, svi prođu kroz BSEM(i) i svi budu blokirani na BSEM((i+1) mod 5). Može se ustanoviti da za nastajanje potpunog zastoja postoje tri nužna uvjeta: • proces koristi sredstvo međusobno isključeno; • proces dodjeljeno mu sredstvo otpušta sam kada je obavio posao (nitko mu ga ne može oduzeti); • proces drži dodijeljeno mu sredstvo dok čeka na dodjelu dodatnog sredstva. Problem potpunog zastoja je ozbiljan i mora se uzeti u obzir! Ideja za razriješenje problema pet filozofa: Dozvoliti da najviše četiri filozofa pristupe stolu. To se može riješiti uvođenjem općeg semafora OSEM(STOL) koji se inicijalizira OSEM(STOL).r: = 4 27

filozof fi pponavljati misliti; ČEKAJ_OSEM(STOL); ČEKAJ_BSEM(i); ČEKAJ_BSEM((i+1) mod N); jesti; POSTAVI_BSEM(i); POSTAVI_BSEM((i+1) mod N); POSTAVI_OSEM(STOL); do beskonačnosti Najviše četiri filozofa nalaze se istovremeno za stolom, te se po principu golubinjaka (eng. pigeonhole principle) jedan domogne dviju vilica. Princip golubinjaka: “Ako se n+1 objekt raspoređuje u n pretinaca tada se u jednom pretincu nalaze dva objekta.” ili: “Ako se više od n+1 objekata stavlja u n pretinaca tada se barem 28 u jednom pretincu nalazi dva ili više objekata.”

a14

6.4. Koncepcija monitora Pokazuje se da je binarni semafor korisni mehanizam, ali da je njegovo korištenje dosta složeno. Problemi nastaju kada se koristi više od jednog semafora. Složeni odnosi između procesa koji komuniciraju vrlo brzo postaju nepregledni. Dodatna je poteškoća da je ispitivanje uvjeta u semaforu povezano s blokiranjem procesa. Stoga je Hoare ( Hoare, C.A.R., “Monitors: An Operating System Concept”, Comunications of the ACM, vol.17, Oct 1974., pg. 549-557) predložio koncepciju monitora. Slično kao i jezgra, monitor se sastoji od skupa procedura i strukture podataka nad kojima procedure djeluju. • Procedure su tako konstruirane da samo jedna po jedna djeluju (međusobno isključeno!). • Struktura podataka nije poznata izvan monitora. • Procesi koji međusobno komuniciraju ne mogu dohvaćati u strukture 29 neposredno već samo preko parametara procedura.

• Unutar monitora (jedne od procedura) ispituju se uvjeti koji utječu na odvijanje procesa. • Ako neki uvjet nije ispunjen proces se (unutar monitora! ) stavlja u red u kojem čeka na ispunjenje uvjeta. • Ako proces uspješno obavi akciju unutar monitora, on izlazi iz monitora i omogućuje da drugi proces uđe u monitor. • Međutim, ako proces mora čekati na ispunjenje uvjeta, on ostaje prividno unutar monitora, ali mora omogućiti da drugi proces uđe u monitor. • Proces koji uvjetuje ispunjenje nekog uvjeta deblokira neki proces i zbog toga bi se dva procesa mogla naći istovremeno u monitoru. Moguće rješenje: Procedure monitora moraju se tako konstruirati da obavljaju deblokiranje na svome kraju i odmah napuštaju monitor. 30

a15

Za konstruiranje monitorskih procedura treba uvesti neke nove jezgrine procedure i u strukturi podataka predvidjeti odgovarajuće redove. Za svaki monitor uvodi se red MONITOR(m). Red je sličan binarnom semaforu MONITOR(m) MONITOR(m).r

MONITOR(m).r =

1 ulaz slobodan 0 ulaz blokiran

Kada proces (na početku svake procedure monitora) naiđe na neprolazni monitor on se svrstava u red. Za svaki od uvjeta koji se unutar monitora m ispituju uvodi se red RED_UVJETA(m,k). RED_UVJETA(m,k)

31

Red MONITOR(m) i redovi RED_UVJETA(m,k) nalaze se unutar jezgre i na njih djeluju dva para jezgrinih procedura: UĐI_U_MONITOR(m) IZAĐI_IZ_MONITORA(M) UVRSTI_U_RED_UVJETA(m,k) UZMI_IZ_REDA_UVJETA( m,k) j-procedura UĐI_U_MONITOR(m) pohraniti kontekst u opisnik AKTIVNI_P; ako je MONITOR(m).r = 1 onda MONITOR(m).r: = 0; obnoviti kontekst iz opisnika AKTIVNI_P; dozvoliti prekidanje; obnoviti sadržaj PC iz opisnika AKTIVNI_P; inače premjestiti opisnik iz reda AKTIVNI_P u red MONITOR(m); AKTIVIRAJ_PRVI_PROCES_IZ_REDA_PRIPRAVNI_P; 32 kraj

a16

j-procedura IZAĐI_IZ_MONITORA(m) pohraniti kontekst u opisnik AKTIVNI_P; premjestiti opisnik iz reda AKTIVNI_P u red PRIPRAVNI_P; ako je MONITOR(m).r = 0 red MONITOR(m) neprazan onda premjestiti prvi opisnik iz reda MONITOR(m) u red PRIPRAVNI_P; inačeMONITOR(m).r: = 1; AKTIVIRAJ_PRVI_PROCES_IZ_REDA_PRIPRAVNI_P; kraj j-procedura UVRSTITI_U_RED_UVJETA(m,k) pohraniti kontekst u opisnik AKTIVNI_P; premjestiti opisnik iz reda AKTIVNI_P u RED_UVJETA(m,k); ako je MONITOR(m).r = 0 red MONITOR(m) neprazan onda premjestiti prvi opisnik iz reda MONITOR(m) u red PRIPRAVNI_P; inačeMONITOR(m).r: = 1; AKTIVIRAJ_PRVI_PROCES_IZ_REDA_PRIPRAVNI_P; 33 kraj

j-procedura UZMI_IZ_REDA_UVJETA(m,k) pohraniti kontekst u opisnik AKTIVNI_P; premjestiti opisnik iz reda RED_UVJETA(m,k) u red PRIPRAVNI_P; ako je MONITOR(m).r = 0 red MONITOR(m) neprazan onda premjestiti prvi opisnik iz reda MONITOR(m) u red PRIPRAVNI_P; inače MONITOR(m).r: = 1; AKTIVIRAJ_PRVI_PROCES_IZ_REDA_PRIPRAVNI_P; kraj Monitorska procedura unutar koje se eventualno neki uvjet ispunjava mora završiti ovako: ako je uvjet (m,k) ispunjen onda UZMI_IZ_REDA_PORUKA(m,k) inače IZAĐI_IZ_MONITORA(m) kraj 34

a17

PROCES IZVAN MONITORA

PROCES UNUTAR MONITORA

PROCES UNUTAR JEZGRE

poziv m_procedure UĐI_U_MONITOR

dozvoljen ulaz

IZAĐI_IZ_MONITORA povratak iz m_procedure poziv m_procedure UĐI_U_MONITOR

blokiranje na ulazu u monitor deblokiranje

UVRSTI_U_RED_UVJETA

blokiranje zbog neispunjenja uvjeta deblokiranje (neki drugi proces je izazvao deblok.)

IZAĐI_IZ_MONITORA povratak iz m_procedure

35

6.5. Primjeri upotrebe monitora 6.5.1. Oponašanje binarnog semafora Struktura podataka jezgre: MONITOR(1)

RED_UVJETA(1,1) MONITOR(1).V

Normalna varijabla unutar monitora 1 semafor prolazan SEM = 0 semafor neprolazan BROJ_ČEKAČA

procesi koji čekaju u redu na prolaz početno: BROJ_ČEKAČA = 0 36

a18

m-procedura ČEKAJ(SEM) UĐI_U_MONITOR(1); ako je SEM = 1 onda SEM := 0; IZAĐI_IZ_MONITORA; inače BROJ_ČEKAČA: = BROJ_ČEKAČA + 1; UVRSTI_U_RED_UVJETA (1,1); kraj

37

m-procedura POSTAVI (SEM) UĐI_U_MONITOR(1); ako je SEM = 0 BROJ_ČEKAČA > 0 onda BROJ_ČEKAČA: = BROJ_ČEKAČA - 1; UZMI_IZ_REDA_UVJETA (1,1); inače SEM := 1; IZAĐI_IZ_MONITORA; kraj proces Pi ponavljaj ČEKAJ (SEM); kritični odsječak; POSTAVI (SEM); nekritični odsječak; do beskonačnosti

38

a19

6.5.2. Komunikacija preko ograničenog spremnika

Struktura podataka jezgre: MONITOR(2) MONITOR(2).V

RED_UVJETA(2,1) za proizvođača RED_UVJETA(2,2) za potrošača

Normalne varijable unutar monitora MS[0...N-1] UL = IZ = 0 BROJ_MJESTA = N

POTROŠAČ_ČEKA = PROIZVOĐAČ_ČEKA=

1 da 0 ne 1 da 0 ne 39

m-procedura POŠALJI_PORUKU(P); UĐI_U_MONITOR(2); ako je BROJ_MJESTA > 0 onda BROJ_MJESTA := BROJ_MJESTA -1; MS[UL] : = P; UL : = (UL + 1) mod N; ako je POTROŠAČ_ČEKA = 0 onda POTROŠAČ_ČEKA = 0; UZMI_IZ_REDA_UVJETA (2,2); inače PROIZVOĐAČ_ČEKA : = 1; UVRSTI_U_RED_UVJETA (2,1); kraj 40

a20

m-procedura PRIHVATI_PORUKU(r); UĐI_U_MONITOR(2); ako je BROJ_MJESTA > N onda r: = MS[IZ]; IZ : = (IZ + 1) mod N; BROJ_MJESTA := BROJ_MJESTA +1; ako je PROITVOĐAČ_ČEKA = 1 onda PROIZVOĐAČ_ČEKA : = 0; UZMI_IZ_REDA_UVJETA (2,1); inače IZAĐI_IZ_MONITORA(2) inače POTROŠAČ_ČEKA : = 1; UVRSTI_U_RED_UVJETA (2,2); kraj 41

a21