OSA I:
Yhteisten muuttujien käyttö
Prosessit samassa koneessa

Sisältöä

	Poissulkeminen ja synkronointi

	Semaforit ja rinnakkaisuuden hallinta

	Lukkiutuminen

	Monitorit

 Poissulkeminen ja synkronointi

Rinnakkaiset, atomiset operaatiot

Spin Locks

Semaforit

Synkronointi

Andrews 2.1-2.5, 3.1-3.2, 4.1-4.2, 6.3 ja Stallings 5.1,5.3-5.4

Liisa Marttinen

Atomisuus (atomic action)

alkutila

tilamuutos

välitiloja ei näy

tila muutoksen

jälkeen

yksittäinen konekäsky on atominen

usean konekäskyn vaatima muutos =

kriittinen alue (critical section) on tehtävä

’atomiseksi’ keskinäisellä poissulkemisella

(mutual exclusion)

muut prosessit eivät pääse käsittelemään tilamuutoksen muuttujia eli suorittamaan omaa kriittista aluettaan

process laskija( ) {

int apu, luku, ...;

while (true) {

laske jotain;

luku=f( ); # laske luku

apu = buf[luku];

if (apu = = 0) ....

else

lasketaan taas;

......

{

{

Kriittinen (koodi)alue (critical section)

process kertoma (int arvo) {

int apu = 1, i =2;

while (i<= arvo) {

apu = i*apu;

i++;

}

buf[arvo] = apu;

}

int buf[n];

buf

Yhteinen muistialue

Rinnakkaiset, atomiset operaatiot

Kriittinen alue, useita käsittelijöitä

Vain yksi saa edetä alueella kerrallaan

prosessi P[1]	prosessi P[2]

…	…

input (in,..);	…

input(in,..);

out = in;	out = in;

output (out,..);

…	output(out,..);

Andrews 3.1. (s. 94-95)

char out, in;

procedure echo {

input (in, keyboard);

out = in;

output (out, display);

}

process P[i=1 to 2] {

. . .

echo();

. . .

}

Poissulkeminen

Ohjelman perusmalli

process CS[i=1 to n] { # n rinnakkaista prosessia

while (true) {

ei kriittistä koodia;

}

}

Ohjelmoi kriittiset alueet lyhyiksi!

Entry protocol	# varaa

< kriittinen koodialue > # käytä (exclusive!)

Exit protocol	# vapauta

Halutut ominaisuudet

Poissulkeminen

Vain yksi prosessi kerrallaan suorituksessa kriittisellä alueella

Ei lukkiutumisvaraa, ei ‘elohiirtä’

Jos useita sisäänpyrkijöitä, jotain onnistaa

Ei tarpeettomia viipeitä

Jos alue vapaa, pääsy sallittava

Lopulta onnistaa, ei ‘nälkiintymistä’

Kukaan ei joudu odottamaan ikuisesti

3 safety properties + liveness property

deadlock

livelock

Spin Locks, Busy Waiting

Andrews 3.2 (s. 97-103)

Lukkomuuttujat, Spin Locks

Boolean-muuttuja lock

Lock== true	kriittinen alue varattu

lock==false	kriittinen alue vapaa

Entry protocol

while (lock) ;	# aktiivinen odotus, “pörrää”

# check again if (!lock) # busy loop

lock=true;

Exit protocol

lock=false;

OK? Testaus ja asetus atomisesti!

L == 1

L == 0

L == 0

Toteutus symbolisella konekielellä

muuttuja L: L==1, jos kriittinen alue vapaa

L==0, jos kriittinen alue varattu

LOOP:	LOAD R1,L

JZER R1,LOOP

LOAD R1,=0

STORE R1,L

< kriittinen alue >

LOAD R1,=1

STORE R1,L

LOOP:	LOAD R1,L

JZER R1,LOOP

LOAD R1,=0

STORE R1,L

< kriittinen alue >

LOAD R1,=1

STORE R1,L

Test-and-Set-käsky

Oma konekielen käsky

atominen laitetason suoritus (execute-vaihe)

argumentti: lukkomuuttuja

boolean paluuarvo

TS L

merkitys: < temp=L; L=0; if (temp==1) jump *+2; >

merkitään varatuksi!

Käyttö:

LOOP: TS L
JUMP LOOP

.......

Saa edetä!

Jää odottamaan!

bool TS(bool lock) {

< bool initial = lock; /* arvo talteen */

lock = true; /* lukitse lukko */

return initial; > /* palauta lukon arvo */

}

Andrews s. 99

Test and Set –toiminto lausekielellä esitettynä

Test-and-Set ja TT-K91?

TS Ri,L < Ri  mem[L]

mem[L]  0

if (Ri==1) jump *+2 >

OK? Moniprosessorijärjestelmä? Keskeytys?

LOOP: TS R1,L # L: 1(vapaa), 0(varattu)

JUMP LOOP

< kriittinen alue > # tänne, jos R1 = 1

LOAD R1,=1

STORE R1,L # L  1

entry

exit

Toteutuvatko vaatimukset?

Poissulkeminen ? OK!

Vain yksi prosessi kerrallaan suorituksessa kriittisellä alueella

Ei lukkiutumisvaraa, ei ‘elohiirtä’ ? OK!

Jos useita sisäänpyrkijöitä, jotain onnistaa

Ei turhia viipeitä, ei nälkiintymistä ? OK!

Jos alue vapaa, pääsy sallittava

Lopulta onnistaa ? EI VÄLTTÄMÄTTÄ

Kukaan ei joudu odottamaan ikuisesti

Ongelmana suorituskyky, jos monta prosessia kilpailemassa ja koko ajan tutkimassa ja kirjoittamassa lukkomuuttujaan

Rasittaa muistia ja muistiväylää

Kirjoittaminen häiritsee välimuistin toimintaa

=> Test-and-Test-and-Set = testataan ensin, onko lukko vapaa

Test and Test and Set

kilpailu muistista (lukkomuuttuja) => huono suorituskyky

TS kirjoittaa aina lukkomuuttujaan => välimuisti muuttuu => muiden prosessorien välimuistit eivät enää ole ajantasalla

while (lock) skip; # pörrätään, kun lukko päällä (lock=true)

while (TS(lock)) { # yritetään saada lukko itselle

while (lock) skip; # pörrätään, jos ei saatu (lock = true)

}

nyt useinmiten vain luetaan arvoa ja harvemmin kirjoitetaan!

Lukkomuuttuja ja lukko-operaatiot

Muuttujan tyyppi	lock

Operaatiot

esittely, alkuarvo lock x=1;	# vapaa

LOCK(x)	loop

test=TS(x); # aseta x = 0

until(test==1);	# oliko vapaa?

UNLOCK(x)	x=1;

[ Linux kernel: spinlock_lock(x), spinlock_unlock(x) ]

[ vrt. kirja CSenter, CSexit ]

Csenter - CSexit

<await (B) S;> toteutus:

CSenter;

while (!B) { ??? }

S;

CSexit;

{CSexit; CSenter }

{Csexit; Delay; Csenter; }

Poissulkeminen lukkomuuttujaa käyttäen

lock L=1;	# käytä lukitsemaan tiettyä kriittistä aluetta

# sopimus prosessien kesken!

process CS [i=1 to N] {	# n rinnakkaista!

while (true){

ei kriittistä koodia;

ei kriittistä koodia;

}

}

Tulkinta: L=1  yhdellä lupa edetä

LOCK(L);	# varaa

< kriittinen alue >	# käytä (exclusive!)

UNLOCK(L);	# vapauta

Aktiivinen vs. passiivinen odotus

busy-wait: turhaa laitteiston käyttöä!

kilpailu

useita prosesseja (käyttävät yhteistä prosessoria),

jotka haluavat päästä kriittiselle alueelle

livelock

pienen prioriteetin prosessi kriittisellä alueella

suuren prioriteetin prosessi pörrää LOCK-operaatiossa

vaihtoehto

jos pääsy ei sallittu, odota Blocked-tilassa

Semaforit

Andrews 4.1 (s. 153-155), 6.3 (s. 276-279)

Semaforit

P() aka WAIT() aka Down()

jos kriittinen alue vapaa, lukitse se ja jatka eteenpäin

jos kriittinen alue varattu, odota

V() aka SIGNAL() aka Up()

jos joku odotusjonossa, päästä joku etenemään

muuten vapauta kriittinen alue

atomisia

semafori S

P(S)

V(S)

S.arvo

S.jono

public

public

private

private

alkuarvo

Yleistä semaforeista

Alkuperäinen idea: Dijkstra (60-luvun puoliväli)

binäärisemaforit: vain arvot 0 ja 1 käytössä

Operaatiot

Alustus	sem S=1; sem forks[5] = ([5] 1);

P(S)	(= passeren)

V(S)	(= vrijgeven)

S.arvo

1  vapaa / avoinna / etenemislupa

0  varattu / suljettu / eteneminen kielletty

S.jono

Etenemislupaa Blocked-tilassa odottavat prosessit

Toteutus: PCB:t linkitetyssä listassa (=jono)

Yleiset semaforit: S.arvo ~ resurssilaskuri

S.arvo > 0

vapaiden yksiköiden lkm, etenemislupien määrä

kuinka monta prosessia voi tehdä P()-operaation

joutumatta Blocked tilaan ja semaforin jonoon

S.arvo = 0

ei vapaita

[ jotkut toteutukset: S.arvo < 0 ]

jonossa odottavien prosessien lkm

Ei operaatiota

jonon käsittelyyn / pituuden kyselyyn!

semaforin arvon kyselemiseen!

jos tarve tietää, ylläpidä ko. tieto omassa muuttujassa

P/V:n toteutus KJ:n ytimessä (Andrews Fig 6.5)

P(S)

V(S)

if (S.arvo > 0)

S.arvo = S.arvo - 1

else

aseta prosessin tilaksi Blocked,

lisää prosessi jonoon S.jono

call Vuorottaja()

if (isEmpty(S.jono))

S.arvo = S.arvo + 1

else

siirrä S.jonon ensimmäinen prosessi

Ready-jonoon (tilaksi Ready)

call Vuorottaja()

P/V:n toteutus	(toinen tapa, Stallings Fig. 5.6 ja 5.7)

P(S)

V(S)

Miten ohjelmoijan huomioitava tämä toteutusero?

S.arvo = S.arvo - 1

if (S.arvo < 0)

aseta prosessin tilaksi Blocked,

lisää prosessi jonoon S.jono

call Vuorottaja()

S.arvo = S.arvo + 1

if (S.arvo <= 0)

siirrä S.jonon ensimmäinen prosessi

Ready-jonoon

call Vuorottaja()

Poissulkeminen semaforia käyttäen

sem mutex=1;	# vain perinteinen muuttujan nimi

process CS [i=1 to N] {	# rinnakkaisuus!

while (true){

ei kriittistä koodia;

ei kriittistä koodia;

}

}

yksi semafori kullekin erilliselle kriittiselle alueelle

huomaa oikea alkuarvo

P(mutex);	# varaa

< critical section >	# käytä (exclusive!)

V(mutex);	# vapauta

Vrt. Stallings Fig. 5.10

Bacon Fig 9.19

P(lock)

P(lock)

P(lock)

V(lock)

V(lock)

V(lock)

pagepool

Muistinhallinta

---

GET

...

REL

---

c2

GET

REL

-----

GET

...

REL

---

---

GET

...

REL

---

c1

prosessi

prosessi

koodi

koodi

Esimerkki: Muistinhallinta (1)

count

addr pagepool[1:MAX]; # käyttö pinona

int count=MAX;

function GET(): returns addr {

get = pagepool[count];

count = count-1;

}

procedure REL(addr freepage) {

count = count+1;

pagepool[count] = freepage;

}

pagepool

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

count

function GET: returns addr

{ get = pagepool[count];

function GET: returns addr

{ get = pagepool[count];

get = pagepool[count];

get = pagepool[count];

framepool

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

count

framepool

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

count

get = pagepool[count];

count = count-1

}

Toimiikos toi?

addr pagepool[1:MAX];

int count=MAX;

pagepool

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

count

count = count-1

}

GET==6

GET==6

6

6

Muistinhallinta (1): poissulkeminen

addr pagepool[1:MAX];

int count=MAX;

sem mutex=1;

function GET(): returns addr {

P(mutex);

get = pagepool[count];

count = count-1;

V(mutex);

}

procedure REL(addr freepage) {

P(mutex);

count = count+1;

pagepool[count] = freepage;

V(mutex);

}

pagepool

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

count

mutex

0

Synkronointi

Andrews 4.2 (s. 156-164)

Synkronointi

Tapahtuma: “mikä tahansa kiinnostava”

puskuri_täynnä, io_valmis, laskenta valmis, kriittinen alue vapaa

(Looginen) tapahtuma  semaforimuuttuja

Kumpi ehtii ensin synkronointikohtaan?

 tarvitsee paikan missä odottaa (~jonottaa)

Prosessi P1

käskyjä…

kerro tapahtumasta

käskyjä…

Prosessi P2

käskyjä…

odota tapahtumaa

käskyjä...

Synkronointi semaforia käyttäen

sem A_Ready = 0;

0  ”ei ole tapahtunut”, 1  ”on tapahtunut”

Kumpi ehtii ensin?

Oikea alkuarvo?

Tuottaja

tuota A…

V(A_ready);

…

Kuluttaja

…

P(A_ready);

kuluta A…

Muistinhallinta (2): synkronointi

addr pagepool[1:MAX];

int count=MAX;

sem mutex=1, avail=MAX;

function GET() : returns addr {

P(avail);

P(mutex);

get = pagepool[count];

count = count-1

V(mutex);

}

procedure REL(addr freepage) {

P(mutex);

count = count+1;

pagepool[count] = freepage;

V(mutex);

V(avail);

}

pagepool

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

count

mutex

0

avail

6

Puomisynkronointi (barrier)

n prosessia työskentelee yhdessä

Iteratiivinen käsittely, synkronointi tietyn välivaiheen jälkeen

Prosessi A

xxx

xxx

xxx

xxx

synkronoi

xxx

xxx

Prosessi B

xxx

synkronoi

xxx

xxx

Prosessi C

xxx

xxx

xxx

synkronoi

xxx

xxx

I

II

aika

Worker[1]

xxx

xxx

xxx

xxx

synkronoi

odota

xxx

Worker[2]

xxx

synkronoi

odota

xxx

Worker[3]

xxx

xxx

xxx

synkronoi

odota

xxx

process Worker [i = 1 to N] {

while (…) {

käsittele vaihe x:n alku ;

toimita synkronoititieto kaikille muille;

odota synkronoititietoa kaikilta muilta;

käsittele vaihe x:n loppu;

}

}

xxx xxx xxx

aika

Puomisynkronointi

sem arrive1 = 0, arrive2 = 0;

process Worker1 {

…käsittele alkuosa 1…

V(arrive1);	# lähetä synkronointitapahtuma

P(arrive2);	# odota toista prosessia

…käsittele loppuosa 1…

}

process Worker2 {

…käsittele alkuosa 2…

V(arrive2);	# lähetä synkronointitapahtuma

P(arrive1);	# odota toista prosessia

…käsittele loppuosa 2…

}

Huomaa järjestys!

Puomisynkronointi, yleiset semaforit

sem arrive=0, continue[1:N] = ( [N] 0 );

process Worker [i=1 to N] {

…käsittele alkuosa i…

V(arrive);	# synkronointitapahtuma koordinaattorille

P(continue[i]);	# odota toisia prosesseja

…käsittele loppuosa i…

}

process Coordinator {

while (true) {

count = 0;

while (count < N) {	# odota, kunnes N synkronointitapahtumaa

P(arrive);

count++;

}

for [i = 1 to N] V(continue[i]); # synkronointitapahtuma prosesseille

}

}

Entä jos vain yksi continue-semafori?

Rinnakkaisuuden hallinta

pagepool

{P(mutex)

…

V(mutex)

}

{P(mutex)

…

V(mutex)

}

mutex

hallinnan toteutus

P/V

semafori

avail

GET

REL

resurssien varaus

get/rel

muuttujat

P/V:n toteutus

LOCK/UNLOCK

lukkomuuttuja

P( )

LOCK(lock)

…

UNLOCK(lock)

V( )

LOCK(lock)

…

UNLOCK(lock)

LOCK/UNLOCK toteutus

test-and-set-käsky

lukkomuuttuja

LOCK

loop ..TS(x) ...

UNLOCK

x = 1

Kertauskysymyksiä?

PowerPoint Presentation

Liisa Marttinen

2004-11-01T09:58:47