 Semaforit ja rinnakkaisuuden hallinta

Tuottajat ja kuluttajat

Resurssien hallinta, vuoron antaminen

Lukijat ja kirjoittajat

Andrews 4.2, 4.4-4.6

Tuottajat ja kuluttajat

Andrews: ss.158-160

Andrews Fig. 4.3: Producers and consumers using semaphores.

(split binary semaphores)

Toimiiko oikein? Mitä pitääkään tarkistaa?

Tuottaja i

..........

......

P(empty);

.....

V(full);

..........

Kuluttaja j

........

........

P(full)

........

V(empty)

........

Sem empty = 1, full = 0

Kumpi pääsee ensin vai pääseekö kumpikaan?

Säilyykö oikea järjestys (tahdistus)?

- saa tuottaa, vain jos kuluttaja lukenut

- saa kuluttaa, vain jos tuottaja jotain tuottanut

Tuleeko sekaannusta, jos kaksi tuottajaa tai kuluttajaa yrittää samaan aikaan?

Nälkiintyykö joku?

Andrews Fig. 4.4: Bounded buffer using semaphores.

0

Andrews Fig. 4.5: Multiple producers and consumers using semaphores.

0

Entä, jos vain yksi mutex?

Lukijat ja kirjoittajat

Lukijat ja kirjoittajat

Yhteinen tietokanta DB

tai joku muu objekti, esim. tiedosto, lista, …

Kaksi kilpailevaa käyttäjäluokkaa

Lukijat (readers)

lukevat

useita lukijoita voi olla käsittelemässä yhtäaikaa

Kirjoittajat (writers)

lukevat ja muuttavat

vain yksi kerrallaan muuttamassa

Luokka aktiivinen vain,

jos toinen luokka passiivinen

Ratkaisu 1: R/W poissulkemisongelmana

Yksinkertaistettu ongelma, yksink. ratkaisu

Poissulkeminen kaikille muille	=> semafori rw

Andrews Fig 4.8

Salli lukijoiden toimia rinnakkain

Luokan poissulkeminen	=> semafori rw

Eka lukija varaa DB:n lukijaluokalle,

viimeinen lukija vapauttaa DB:n

Kuka on eka / viimeinen?	=> laskuri nr

“testaa, varaa / vapauta”	=> atominen: < … >

Andrews Fig 4.9 and Fig 4.10

Andrews: ss. 167-169

sem rw =

1

Lukija

Kirjoittaja

Lue tietokannasta; Kirjoita tietokantaan;

P(rw);

P(rw);

V(rw);

V(rw);

process {

process {

while (true) { while (true) {

.... .....

} }

} }

Vain yksi tietokannan käsittelijä kerrallaan!

- yksi kirjoittaja OK!

- yksi lukija TURHA RAJOITUS!

Andrews Fig. 4.8:

An overconstrained solution.

1. lukija varaa tietokannan ja viimeinen lukija vapauttaa sen

sem rw = 1;

int nr = 0;

process Reader [i=1 to M] {

while (true) {

. . .

nr = nr + 1;

if (nr = =1) P(rw); # ensimmäinen lukija

read the database;

nr = nr -1;

if (nr = = 0) V(rw); # viimeinen lukija, muita ei

# tällä kertaa ole!

}

}

P(mutex)

V(mutex)

P(mutex)

V(mutex)

sem mutex =1;

<

<

>

>

Andrews Fig. 4.9: Outline of

readers and writers solution.

Andrews Fig. 4.10:

Readers and writers exclusion

using semaphores.

Ratkaisu 2: R/W synkronointiongelmana

Odota, kunnes sopiva ehto tulee todeksi

Toiminnallisuus: < await (ehto) lauseet; >

Ehdon testaus ja lauseosa atomiseksi

Tila

BAD:	(nr > 0 and nw > 0) or nw > 1

RW:	(nr == 0 or nw ==0) and nw <= 1

RW muuttumaton, oltava voimassa aina

nr = number of readers, nw = number of writers

Ohjelmoi s.e. ehto RW on aina true

saa lukea	nw == 0 (ei kukaan kirjoittamassa)

saa kirjoittaa	nr==0 and nw==0 (ei muita kirjoittajia eikä lukijoita)

Andrews Fig. 4.11:

A coarse-grained readers/writers solution.

Ratkaisu 2, laajennettu

Ota huomioon käyttövuorot

Lukijat ensin, tai …

Vuoro prioriteetin perusteella: Kirjoittajat ensin!

(jos muutokset tärkeitä; nälkiintymisvaara)

Onko, joku odottamassa vuoroa?

Ei voi kysyä semafori-operaatioilla  omat laskurit: dw,dr

Vuorojen toteutus rutiinissa SIGNALNEXT

Kriittinen alue vapautuu joku muu saa jatkaa, kuka?

odottava lukija, odottava kirjoittaja, kokonaan uusi tulija

SIGNALNEXT on sama kuin kirjassa käytetty SIGNAL

jotta ei sekottuisi monitorin signal-operaatioon

Andrews Fig. 4.12

Jaettu binääriarvoinen semafori

Liitä kuhunkin vahtiin (ehtoon) semafori ja laskuri : sem e, r,w;

Vain yksi semafori kerrallaan ‘auki’ ( 0 <= (e+r+w) <= 1)

alussa: sem e =1, r=0, w=0;

await (nw==0) nr = nr+1

semafori: r = 0 waiting place for readers

laskuri:	dr	number of delayed readers

await (nr==0 and nw==0) nw = nw+1

semafori: w = 0	waiting place for writers

laskuri:	dw	number of delayed writers

poissulkeminen < … >

semafori: e = 1	waiting place for entry

laskurit:	nr, nw numbers of readers and writers

process Reader {

while (true) {

<await (nw == 0) nr = nr + 1;>

read the database;

<nr = nr -1;>

}

}

#

P(e); #varmistaa atomisuuden

if (nw > 0){ #joudutaan odottamaan

dr = dr + 1;

P(r);}

V(e);

nr=nr+1;

SIGNALNEXT;

#

P(e); #varmistaa atomisuuden

nr=nr-1;

SIGNALNEXT;

process Writer {

while (true) {

<await (nw == 0) nr = nr + 1;>

write the database;

<nr = nr -1;>

}

}

#

P(e); #varmistaa atomisuuden

if (nr>0 or nw > 0){ #joudutaan odottamaan

dw = dw + 1;

P(w);}

V(e);

nw=nw+1;

SIGNALNEXT;

#

P(e); #varmistaa atomisuuden

nw=nw-1

SIGNALNEXT;

Andrews Fig. 4.12: Outline of readers and writers with passing the baton.

SIGNALNEXT - vuoron antaminen: Lukijat ensin!

if (nw == 0 and dr > 0) {

dr = dr -1;

V(r);	# herätä odottava lukija, tai

}

else if (nr == 0 and nw == 0 and dw > 0) {

dw = dw -1;

V(w);	# herätä odottava kirjoittaja, tai

}

else

V(e);	# päästä joku uusi etenemään

Menetelmä: Viestikapulan välitys (Baton passing)

Viestikapulan välitys (Baton passing)

semafori ~ viestikapula;

koska semaforit e, r ja w muodostavat jaetun binäärisemaforin, niin kulloinkin yhdellä niistä on arvo 1 ja muilla arvo 0

Vain yksi etenee kerrallaan kriittisillä alueilla

pyydettävä etenemislupaa: P(e)

se etenee, joka ‘saa’ haltuunsa semaforin e

Muiden odotettava

täysin uusi lukija tai kirjoittaja: P(e)

vuoroaan jonottamaan jääneet lukijat ja kirjoittajat:

Jos etenijän pyyntöön ei voi suostua:

Lukijat:	V(e); P(r) (jää odottamaan lukijan vuoroaan)

Kirjoittajat:	V(e); P(w) (jää odottamaan kirjoittajan vuoroaan)

Etenijä aktivoi itse “seuraavan viestikapulan haltijan” (kohdassa SIGNALNEXT)

jos vuoroaan odottavia,

herätä odottaja semaforista: joko V(r) tai V(w)

jätä sille poissulkemissemafori valmiiksi kiinni: älä tee V(e)

jos ei odottajia,

jätä viestikapula vapaaksi uusille tulijoille: V(e)

Herätetty välittää aikanaan kapulan seuraavalle ja se seuraavalle ja ...

 Takaa ettei kukaan pääse ‘etuilemaan’!

Ehdot taatusti voimassa, kun jonottaja saa prosessorin

SIGNALNEXT aktivoi vain yhden prosessin, kun ehto tuli todeksi

FCFS

SIGNALNEXT - vuoron antaminen: Lukijat ensin!

if (nw == 0 and dr > 0) {

dr = dr -1;

V(r);	# herätä odottava lukija, tai

}

else if (nr == 0 and nw == 0 and dw > 0) {

dw = dw -1;

V(w);	# herätä odottava kirjoittaja, tai

}

else

V(e);	# päästä joku uusi etenemään

Osa ehdoista on jo tiedossa, kun ollaan lukijassa tai kirjoittajassa => voidaan jättää pois eikä tarvitse enää testata!

Andrews Fig. 4.13: A readers / writers solution using passing the baton.

Lukijat ensin

Tarpeettomat osat annetusta

SIGNALNEXT

-koodista poistettu

SIGNALNEXT - vuoron antaminen: Kirjoittajat ensin!

Reader: uusi lukija odottamaan, jos kirjoittaja odottamassa (rivi 5)

if (nw>0 or dw>0)	# DELAY

{ dr=dr+1; V(e); P(r); }

Writer: herätä lukija vain, jos kirjoittajia ei odottamassa (rivi 13)

if (dw>0) { # SIGNALNEXT

dw = dw-1; V(w);	# herätä kirjoittaja

}

elseif (dr>0) {	# herätä lukija

dr = dr-1; V(r);

}

else V(e);	# herätä uusi

Muuta kuvaa 4.13 vastaavasti

Resurssien hallinta
ja vuoronantaminen

Resurssien hallinta

Manageri

Objektit: varaus ja vapautus

Vuorot: kuka odottajista saa jatkaa?

Sisäinen kirjanpito kustakin erillisestä resurssista (private)

ominaisuudet (esim. muistiosoite, koko, …)

vapaa / varattu

käyttäjä (esim. prosessin ID)

Rajapinta, API (public)

pyydä(parametrit)

vapauta(parametrit)

Operaatioiden raaka runko

pyydä(parametrit)

< await (pyyntöön voi suostua)

anna resurssi, merkitse varatuksi >

vapauta(parametrit)

< palauta resurssi kirjanpitoon >

Vrt. kriittisen alueen entry protocol, exit protocol

prosessi

c2

pagepool

Muistinhallinta

---

GET

---

REL

----

GET

REL

-----

GET

---

REL

---

---

GET

---

REL

---

c1

prosessi

koodi

koodi

c3

c4

avail

0

mutex

1

Muistinhallinta (3) pyynnöt sivu kerrallaan

jono

FCFS!

count

Poissulkemisongelmana

int count=MAX;

sem mutex=1, avail=MAX;

function GET(): returns addr {

P(avail) ; // await

P(mutex);	// anna, merkitse

get = pagepool[count];

count = count-1;

V(mutex);

}

procedure REL(addr freepage) {

P(mutex);	// palauta

count = count+1;

pagepool[count] = freepage;

V(mutex);

V(avail) ;	// pyyntöön voi suostua

}

pagepool

1,7,3,8,5,6,2,9,…..

count

mutex

0

avail

6

Toimivatko rutiinit oikein

Poissulkeminen?

Ei lukkiutumista (deadlock/livelock)?

Ei tarpeettomia viipeitä?

Lopulta onnistaa?

sem avail ~ resurssin varaus

yksi kerrallaan; jos ei heti onnistu, niin jonoon odottamaan (FCFS), josta vuorollaan saa resurssin varatuksi

sem mutex ~ resurssin käyttöönotto

yksi kerrallaan; jos ei heti onnistu, niin FCFS- jonoon odottamaan, josta vuorollaan kirjaa resurssin haltuunsa

vapautettaessa ensin kirjataan vapaaksi ja sitten annetaan muiden varattavaksi

VÄÄRIN!

int count=MAX;

sem mutex=1, avail=MAX;

function GET(): returns addr {

P(mutex);

P(avail) ;

get = pagepool[count];

count = count-1;

V(mutex);

}

procedure REL(addr freepage) {

P(mutex) ;

count = count+1;

pagepool[count] = freepage;

V(avail) ;

V(mutex);

}

pagepool

1,7,3,8,5,6,2,9,…..

count

mutex

0

avail

6

Resurssien hallinta, Yleinen ratkaisu

pyydä(parametrit)

P(mutex);	# poissulkeminen

if (pyyntöön ei voi suostua) DELAY; # odota semaforissa

anna resurssi;

SIGNALNEXT;

vapauta(parametrit)

P(mutex);

palauta resurssi;

SIGNALNEXT;

DELAY ~

V(mutex), P(odotussemafori)

SIGNALNEXT ~

V(odotussemafori) else V(mutex)

DELAY:

Älä jätä prosessia

Blocked-tilaan

tärkeä semafori kiinni!

SIGNALNEXT:

Herätä odottaja,

jätä kriittinen alue kiinni

(baton passing).

Palvelujärjestys

Semaforin jonot aina FCFS

Ongelma? Jäljellä 10 sivutilaa, eka haluaa 12, toka 5!

Voiko semaforiin liittää prioriteetin?

Jonotusjärjestys?

Montako erilaista? Dynaaminen vuorottelu?

Ratkaisu: yksityiset semaforit + oma jono

Kullekin prosessille oma semafori, jossa odottaa yksin

Vuoron antamiseen käytettävä tietorakenne (jono) erikseen

alkiossa semafori ja kenties muuta tietoa

Vuorottaja valitsee sopivan prosessin vuorojonosta,

ja päästää liikkeelle semaforissa odottavan asiakkaan

---

GET

---

REL

---

---

GET

---

REL

---

---

GET

---

REL

----

C1

pagepool

{ P(mutex)

…

SIGNAL

}

GET

REL

mutex

1

{ P(mutex)

if …

DELAY

SIGNAL

}

jono RQ

pyynnöille

count

sem

C3

FCFS!

count

12

Muistinhallinta (4) pyynnöt useita sivuja kerralla

10

PCB

PCB

procedure GET (nbr_of_units) {

P(mutex);

if (request can not be satisfied) { # DELAY

RQ[tail].count = nbr_of_units;

V(mutex);

P(RQ[tail].sem);

}

take nbr_of_units for this process;

if (! empty(RQ) and RQ[i].count < count)

V(RQ[i].sem); # SIGNAL

else

V(mutex);

}

procedure REL (list_of_units) {

P(mutex);

return units into pagepool;

if (! empty(RQ) and RQ[i].count < count)

V(RQ[i].sem); # SIGNAL

else

V(mutex);

}

SJN: Lyhyin työ seuraavaksi

request(time,id):

P(e);

if (!free) DELAY;

free = false;

SIGNAL;

release():

P(e);

free = true;

SIGNAL;

DELAY:

Odottajan ID ja TIME (suoritusaika) suoritusajan mukaan järjestettyyn jonoon (PAIRS) oikeaan kohtaan

V(e) eli vapauta kriittinen alue

jää odottamaan vuoroasi P(b[ID])

Tässä tarvitaan kullekin oma semafori, jotta pystytään ’herättämään’ oikea prosessi: b[n] = ([n] 0)

PAIRS-jono määrää järjestyksen: herätetään aina jonon ensimmäinen prosessi

SIGNALNEXT:

Reguest-vaihe

vapauta kriittinen alue V(e) eli päästä joku uusi Request-vaiheeseen

Release-vaiheen lopussa

Jos jonossa odottajia, niin ota jonon ensimmäisen alkiopari (time, ID) ja herätä prosessi ID: V(b[ID];

muuten V(e)

Andrews Fig. 4.14: Shortest job next allocation using semaphores.

Entä, jos resurssia enemmän kuin 1 yksikkö?

amount = montako yksikköä prosessi tarvitsee tai palauttaa

avail = montako yksikköä on vapaana (~free)

request:

testattava, onko vapaana tarvittu määrä yksiköitä amount <= avail. Jos on, niin varataan, muuten talletetaan myös amount

myös tässä voidaan vapauttaa odottavia prosesseja, jos vapaita resursseja on tarpeeksi

release:

vapautetaan jonosta ensimmäinen prosessi, jonka tarpeet pystytään tyydyttämään

POSIX-kirjasto, pthread

# include <pthread.h>

pthread_mutex_init(), _lock(), _trylock(), _unlock(), _destroy() _mutexatrr_*(), …

pthread_rwlock_init(), _rwlock_rdlock(),_rwlock_tryrdlock(), _rwlock_wrlock(), _rwlock _trywrlock(), _rwlock_unlock(), _rwlock_destroy(), _rwlockattr_*(), …

# include <semaphore.h>

sem_init(), sem_wait(), sem_trywait(), sem_post(), sem_getvalue(), sem_destroy(), …

Java

ei semaforeja

synchronized objects  oma toteutus?

 Lue man- / opastussivut

 Andrews ch 4.6, 5.5

Kurssi: Verkkosovellusten toteuttaminen

Kurssi: Ohjelmointitekniikka (Java)

Kertauskysymyksiä?

 Semaforit ja rinnakkaisuuden hallinta

Liisa Marttinen

2004-11-08T09:58:24