 Johdantoa

Rinnakkaisuus vs. samanaikaisuus

Laitearkkitehtuureja

Prosessien välinen kommunikointi

Yhteiskäyttöinen muisti

Sovellusten luokittelua

Ohjelmointiparadigmoja, syntaksia

Andrews, Ch 1

Auvo Häkkinen

Rinnakkaisuus - Samanaikaisuus

Peräkkäisyyteen perustuvat sovellukset

yksi kontrollisäie

Rinnakkaiset sovellukset

useita kontrollisäikeitä

kun yksi odottaa, muut voivat edetä

suora tai epäsuora kommunikointi

synkronointi, poissulkeminen (atomisuus)

Rinnakkaisuus vs. samanaikaisuus

Auvo Häkkinen

Miksi rinnakkaisuutta?

Tavoitteita

parantunut suorituskyky

parantunut luotettavuus

komponenttien yksinkertaisuus

sopivuus hajautettuun ympäristöön

Hinta

monimutkaisempi suunnitella

Käyttäytymisen hallinta vaikeampaa

Liisa Marttinen

Keskinäinen kommunikointi

prosessi i

prosessi j

Prosessien ja/tai säikeiden välillä on hyvin monenlaista tarvetta kommunikointiin

kommunikointiin

voidaan käyttää

yhteistä muuttujaa

sanomanvälitystä

Liisa Marttinen

Prosessit voivat häiritä toisiaan!

yhteinen muisti

k=k+1;

i=i-1

k=k+1;

i=i-1;

i: 10

k:

prosessi i

prosessi j

Prosessien tai säikeiden yhteistoiminta pitää varmistaa!

5

Liisa Marttinen

Prosessien toiminta pitää jotenkin synkronoida!

Esim. tuottaja ja kuluttaja,joiden välissä on puskuri

Mitä ongelmia voi syntyä? Mitä toimintoja tässä pitää synkronoida?

tuottaja kirjoittaa puskuriin

kuluttaja lukee puskurista

puskurin käsittely

kirjoittamisen ja lukemisen tahdistus

Liisa Marttinen

Termejä

keskinäinen poissulkeminen (mutual exclusion)

varmistetaan, ettei yhteistoiminnan onnistumisen kannalta kriittisiä osia prosessien ohjelmakoodista suoriteta samanaikaisesti

kriittinen alue (critical section): vain yksi prosesseista voi suorittaa kriittistä aluettaan

esim. äskeisessä tuottaja-kuluttaja-ongelmassa tuottaja ja kuluttaja eivät pääse samanaikaisesti käsittelemään puskuria.

ehtosynkronointi (condition synchronization)

prosessin eteneminen estetään, kunnes tietty ehto toteutuu

kuluttaja saa ottaa puskurista vasta kun tuottaja on sinne jotakin tuonut

tuottaja saa kirjoittaa uutta vasta kun kuluttuja on entisen lukenut

Auvo Häkkinen

Laitteistoarkkitehtuureja

Auvo Häkkinen

SISD (Single Instruction Single data)

tavallisia prosessoreja

SIMD (Single Instruction Multiple data)

taulukkoprosessori,

vektoriprosessori

Rinnakkaisuus? Samanaikaisuus?

Andrews Fig 1.1

Primary memory

Level 2 cache

Level 1 cache

CPU

Auvo Häkkinen

MIMD, tiukasti kytketty

= moniprosessorijärjestelmä, yhteiskäyttöinen muisti

Rinnakkaisuus? Samanaikaisuus?

Muistin eheys?

Andrews Fig 1.2

Auvo Häkkinen

MIMD, löyhästi kytketty

= hajautetut, erilliset koneet

Sanomanvälitys

Rinnakkaisuus? Samanaikaisuus?

Muistin eheys?

Andrews Fig 1.3

Auvo Häkkinen

Prosessien välinen kommunikointi
Inter Process Communication, IPC

Auvo Häkkinen

Miksi?

Synkronointitarve

Poissulkeminen: vuorot yhteisten resurssien käytössä

Ehtosynkronointi: odota toisen etenemistä

Kuinka?

Talleta paikkaan, josta toinen voi lukea

Muuta yhteiskäyttöisen muuttujan arvoa

= yhteinen muistialue

 Sovellus: poissulkeminen / synkronointi

Kirjoita yhteiskäytössä olevaan kommunikointikanavaan

= sanomanvälitys

 KJ: poissulkeminen / synkronointi

Auvo Häkkinen

Prosessi A

Prosessi B

Prosessi A

10

B: load from X

Prosessi B

Prosessi A

Kommunikointi AB

A  B

A: store into X

B: load from X

B  A

B: store into Y

A: load from Y

…

A’=X;

Y=f(A’);

...

X:

Y:

0

5

A: 10

A’: 5

A  B

A: store into X

…

A=f(..)

X=A;

A=f(Y);

...

…

A’=X;

Y=f(A’);

...

A’: 10

10

…

A=f(..)

X=A;

A=f(Y);

...

A B

B  A

10

 Yhteiskäyttöinen muisti

Ongelmakohtia?

Liisa Marttinen

Kommunikointi AB

B: store into Y

A: load from Y

Prosessi A

Prosessi B

Prosessi A

10

A: store to X

Prosessi B

Prosessi A

…

A’=X;

Y=f(A’);

...

X:

Y:

0

5

A: 10

A’: 5

A  B

B: load from X

…

A=f(..)

X=A;

A=f(Y);

...

 Yhteiskäyttöinen muisti

10

välimuistit ja keskusmuistin päivitys!

Jos B on nopeampi!

Auvo Häkkinen

Prosessi B

Prosessi A

Prosessi A

receive X from A

Prosessi A

Prosessi B

…

X=f(..);

send X to B

...

X: 10

OS	procedure send

kernel	procedure receive

10

receive

…

X=f(..);

send X to B

...

receive

OS	procedure send

kernel	procedure receive

…

receive X from A

Y=f(X);

...

X: 10

X: 5

buffer A_B

X=f(..);

send X to B

send

10

10

10

 Sanomanvälitys

receive X from A

receive

Ongelmakohtia?

Liisa Marttinen

Kommunikointitavat

Yhteiskäyttöinen muisti

Sanomanvälitys

viestien tahdistus

muistipaikan käyttö

LOAD

STORE

LOAD

STORE

SEND

RECEIVE

SEND

RECEIVE

Auvo Häkkinen

Kumpi kommunikointitapa?

Tarkkuus / nopeus (granularity)

Yhteiskäyttöinen muisti

välitön vaikutus

käskyn tarkkuudella

Sanomanvälitys, dedikoidut prosessorit

LAN: 5-10 ms viiveet

proseduurin tarkkuudella

Sanomanvälitys, yleiset palvelinkoneet

LAN/WAN: 10 ms – n sekunnin viiveet

palvelun tarkkuudella

Auvo Häkkinen

Luotettavuus

Yhteiskäyttöinen muisti

täysin luotettava (tai täysi epäonnistuminen)

Sanomanvälitys

Saman koneen sisäisesti

sama kuin yhteiskäyttöisellä muistilla (lähes)

LAN

kommunikointi luotettavaa

prosessit voivat epäonnistua toisista riippumatta

WAN

epäluotettava kommunikointi

prosessit voivat epäonnistua toisista riippumatta

Auvo Häkkinen

Yhteiskäyttöinen muisti

Auvo Häkkinen

Prosessi ja sen säikeet

Stallings Fig 4.2

Auvo Häkkinen

Yhteiskäyttöinen muisti / Säikeet

Nopein kommunikointitapa

Yhteiskäyttöinen muisti

oletusarvoisesti saman prosessin säikeille

KJ huolehtii viittauksista yhteisiin globaaleihin muuttujiin (kirjanpito PCB:ssä)

Kullakin säikeellä oma pino

dynaaminen tilanvaraus aliohjelmia kutsuttaessa

kullakin säikeellä omat paikalliset muuttujat

Käyttö normaaleilla muistiviitekäskyillä

LOAD, STORE, …

Auvo Häkkinen

POSIX-kirjasto, pthread

Yli 60 funktiota

Luonti, pysäytys, lopettaminen, …

pthread_create(), pthread_attr_init()

pthread _exit(), pthread_join(), pthread_detach()

sched_yield()

Synkronointi, poissulkeminen

mutexit, rw-lukot, ehtomuuttujat

JAVA: pakkaus java.lang

luokka Thread

säie.start(), säie.stop(), säie.sleep()

 Lue man- / opastussivut

 Andrews ch 4.6, 5.4

Auvo Häkkinen

#include <pthread.h>

// esittele globaalit muuttujat tässä (shared)

int main(int argc, char *argv[]) {

pthread_t pid, cid;

printf(“Creating two threads\n");

pthread_create(&pid, NULL, Producer, NULL);

pthread_create(&cid, NULL, Consumer, NULL);

pthread_join(pid, NULL);

pthread_join(cid, NULL);

printf(“Threads joined\n");

}

void *Producer(void *arg) {	// säikeen suoritus alkaa tästä

// esittele paikalliset muuttujat tässä (private)

printf(“Producer started\n");

}

void *Consumer(void *arg){	// säikeen suoritus alkaa tästä

printf(“Consumer started\n");

}

Auvo Häkkinen

Yhteiskäyttöinen muisti / Prosessit

Eri vanhemmista peräisin olevat prosessit

Palvelupyynnöt alueiden luomiseksi ja liittämiseksi prosessin osoiteavaruuteen

shmget(), shmctl(), shmat(), shmdt(), ftok()

Muistiin viittaus normaaleilla käskyillä

KJ: kirjanpito yhteiskäytössä olevista alueista

Käyttöoikeudet kuten tdstoilla

kuka: u, g, o

miten: r, w, x

 Lue man-sivut

Auvo Häkkinen

# esittele yhteiset muuttujat tässä

# esittele yhteiset aliohjelmat tässä

process Prosessi_A(käynnistysparametrit) {

# esittele paikalliset muuttujat tässä (yksityisessä käytössä)

# esittele paikalliset aliohjelmat tässä

lauseet;

}

process Prosessi_B(käynnistysparametrit){

lauseet;

}

RIO-kurssi

Emme ota kantaa siihen kuinka prosessit käynnistetään

Huom: kullakin prosessilla oma pino

Auvo Häkkinen, Liisa Marttinen

Keskeytykset / Vuorottaminen

Prosessin suoritus voi keskeytyä kahden konekielisen käskyn välissä

Prosessori automaattisesti suorittamaan KJ:tä

Keskeytys voi aiheuttaa prosessin vaihdon…

KJ tallettaa rekistereiden arvot PCB:hen

KJ lataa rekistereille uudet arvot toisesta PCB:stä

kun prosessi päivittämässä yhteistä data

LOAD R1,A

LOAD R1,A

ADD R1,=5

STORE R1, A

ADD R1,=10

STORE R1, A

Atomisuus?

lopputulos riippuu

suoritusjärjestyksestä:

A= A+5, A=A+10, A= A+15

Auvo Häkkinen

Rinnakkaisten sovellusten luokittelua

 Moniajojärjestelmät

 Hajautetut järjestelmät

 Rinnakkaislaskenta

Auvo Häkkinen

 Moniajojärjestelmät

Toisistaan riippumattomat prosessit

Sovellus, jossa useita säikeitä / prosesseja

Alusta

yhteiskäyttöinen muisti, yksi tai useampi CPU

vuorottelu

Esim.

Ikkunointiympäristöt

Osituskäyttöön perustuvat järjestelmät (esim. palvelimet)

Tosiaikaiset ohjausjärjestelmät

Helppo suunnitella, tehokasta laskentaa

kukin prosessi tekee yhtä asiaa

Auvo Häkkinen

 Hajautetut järjestelmät

Itsenäisten koneiden verkot, sanomanvälitys

CPU:t joilla omaa muistia + yhdistävä verkko

off-load processing

Esim.

Tiedostopalvelin

Tietokanta/transaktiojärjestelmät, esim. lipunvaraus, pankit

Web palvelimet Internetissä (… DNS)

Globaalit yritysjärjestelmät: Integroidut business-alueet

Vikasietoiset järjestelmät, toisinnus

Bacon Fig 1.1: A distributed control system

Bacon Fig 1.2: Multimedia workstations

Bacon Fig 1.3: Airline booking system

Bacon Fig 1.5: A simple distributed operating system

Auvo Häkkinen

 Rinnakkaislaskenta

Nopeammin, enemmän aikayksikössä

Esim.

Tieteellinen laskenta, mallintaminen (esim. sääennuste)

Grafiikka ja kuvankäsittely

Laajat kombinatoriset ja optimointiongelmat (esim. talous)

Rinnakkainen data: SIMD

sama temppu, mutta vain osalle dataa

Bacon Fig 1.6: Replicated code, partitioned data

Rinnakkainen laskenta: MIMD

eri temput eri prosesseille (eri data)

Bacon Fig 1.7: A four step pipeline

Auvo Häkkinen

Missä luokittelun erot?

Kommunikointinopeus

yhteinen muisti vs. sanomanvälitys

Yhteistoiminnan luonne

asiakas - palvelija

Toiminnan autonomisuus (ml. virheet.)

samassa koneessa vs. erilliset koneet

verkko

Auvo Häkkinen

Ohjelmointiparadigmat

 Iteratiivinen rinnakkaisuus

 Rekursiivinen rinnakkaisuus

 Tuottaja - Kuluttaja

 Asiakas - Palvelija

 Vuorovaikutteiset kumppanit/ryhmät

Auvo Häkkinen

 Iteratiivinen rinnakkaisuus

Monta identtistä iteratiivista prosessia

sama koodi, toistosilmukka

Kukin laskee toistossa tuloksen osasta dataa,

sitten tulokset yhdistetään

yhteinen muisti tai sanomanvälitys

esim. puurakenteiset algoritmit

Monta tapaa järjestää rinnakkaisiksi,

jos read set ja write set erillisiä

Esim.

Matriisin kertolasku (s. 13-16)

Bacon Fig 1.6: Replicated code, partitioned data.

Liisa Marttinen

Matriisin kertominen

X

=

a[n,n]

b[n,n]

c[n,n]

0

1

2

3

.

n-1

0 1 2 3...n-1

a[0,*] . b[*,0]

= a[0,0] * b[0,0] +

a[0,1] * b[1,0] +

...

a[0,n-1] * b[n-1,0]

= C[0,0]

Auvo Häkkinen

jokainen rivi

jokainen sarake

Auvo Häkkinen

1-9000

1-3000

3000-6000

6000-9000

1-1000

1000-2000

2000-3000

Muita helposti rinnakkaistettavia

Esim.

 järjestäminen

 etsiminen

 spekulatiivinen laskenta

 päätöspuut

 pelit

Puurakenteiset algoritmit

Auvo Häkkinen

 Rekursiivinen rinnakkaisuus

Rekursiivinen aliohjelma kutsuu itseään

tilanvaraus pinosta

’Hajoita ja Hallitse’

Voidaan tehdä rinnakkain, jos kullakin kutsulla erilliset write -joukot

eivät käytä globaaleja muuttujia

kullekin erilliset viite- ja tulosparametrit

Esim.

Quicksort

Integraalin approksimointi

(s. 18-19)

Liisa Marttinen

Integraalin approksimointi

a

b

f(x)

m = (a+b)/2

a:n ja b:n

puoliväli

A

B

C

Onko jo riittävä hyvä approksimaatio:

|A + B - C| < epsilon

Jos ei ole, niin jatketaan

Auvo Häkkinen

co larea = quad(left, mid,fleft,fmid,larea)

// rarea = quad(mid,right,fmid,fright,rarea)

oc

Auvo Häkkinen

 Tuottaja - Kuluttaja

Tietoa virtaa vain yhteen suuntaan

Tuottaja laskee ja laittaa tiedon kuluttajan saataville

Kuluttaja käyttää tuotetun tiedon

klassinen rajoitetun puskurin hallintaongelma

Esim: Unixin putket (liukuhihna)

sed -f Script $* | tbl | eqn | groff Macros -

Puskurointi?

Andrews Fig 1.5

Auvo Häkkinen

tuottaja

kuluttaja

puskuri B

process Producer {

while (true) {

produce X;

store X into B[*];

}

}

process Consumer {

while (true) {

load Y from B[*];

consume Y;

}

}

Ongelmia? Huomioitavaa?

Auvo Häkkinen

Yleistys

node 1

node 2

node 3

node 4

liukuhihna

suodatus

node

node

node

node

node

node

94

6

17

8

2

21

Auvo Häkkinen

 Asiakas – Palvelija

Tietoa virtaa molempiin suuntiin

pyyntö-vastaus protokolla

Asiakas ja palvelija voivat olla eri koneissa

kutakin pyyntöä palvelemaan oma säie

Esim. tdstopalvelin (read, write)

klassinen lukijat / kirjoittajat ongelma

Andrews Fig 1.6

Client 1

Client n

Server

Request

Reply

Reply

Request

…

Auvo Häkkinen

process Client [i] {

...

send y to F;

receive x from F;

...

...

}

process Server F {

while (true) {

receive msg from *;

x=f(msg);

send x to msg.sender;

}

}

client 1

server F

request

reply

client 2

request

reply

Auvo Häkkinen

Yleistys

node 1

node 2

request

reply

node 3

node 4

A asiakas: node 1

palvelija: node 2

A

B

B asiakas: node 2

palvelija: node 3

Käsite liittyy

kommunikointiin,

ei solmuun

Auvo Häkkinen

 Interaktiiviset kumppanit / ryhmät

Toimivat palvelijoina sekä asiakkaina

Koordinoija tai rengas tai liukuhihna,

tai kaikki kommunikoivat kaikkien kanssa

Sanomanvälitys

send msg to Worker[0]

receive msg from Coordinator

Andrews Fig 1.7

Worker 0

Worker n-1

Worker 0

Coordinator

Worker n-1

data

data

results

…

Auvo Häkkinen

Prosessi A

…

vaihe 1

send xa to B

receive xb from B

vertaa

vaihe 2

…

Prosessi B

…

vaihe 1

send xb to A

receive xa from A

vertaa

vaihe 2

…

Asynkroninen vs. synkroninen kommunikointi

Yksisuuntainen operaatio

Auvo Häkkinen

Esim:

hajautettu

matriisin

kertolasku

(s. 23-26)

Koordinoija

jakaa työt,

kokoaa tulokset

Auvo Häkkinen

Rengas liukuhihnasta

Auvo Häkkinen

Yleistys: 2-suuntainen liukuhihna

while {

xxx

xxx

xxx

send

receive

xxx

}

while {

xxx

xxx

xxx

receive

send

receive

send

xxx

}

while {

xxx

xxx

xxx

xxx

receive

send

xxx

}

Solmu i-1	Solmu i	Solmu i+1

synkronointipisteet:

receive: odota synkronointitietoa

send: lähetä synkronointitieto

Auvo Häkkinen

Yleistys: Heartbeat

while (true) {

compute

send for all

receive

}

Esim. Internetin reititystaulut

algoritmi vs. käyttäytyminen

Auvo Häkkinen

process Worker [i=1 to numWorkers]

{

declaration of local variables;

initialisation of local variables;

while (not done) {

send values to neighbors;

receive values from neighbors;

update local values;

}

}

Heartbeat

to/from neighbors  toistosilmukka

Auvo Häkkinen

Heartbeat, ongelmat

Lukkiutumisvaara

synkroninen vs. asynkroninen kommunikointi

Käyttäytyminen

Turhaa työtä?

“Lyhyin reitti” tiedon välitys

- mitä jos reitti katoaa?

kuormantasaus

- välitetään tietoa ‘vapaasta kapasiteetista’

- mitä jos verkko ruuhkautunut?

Auvo Häkkinen

Rinnakkaisuuden
ongelmakenttä

Auvo Häkkinen

Rinnakkainen data	 poissulkeminen

Esim. yhteinen puskuri	 datan ajantasaisuus

read - update - write

Rinnakkainen suoritus	 synkronointi

Esim. tuota - kuluta

Resurssien jakelu	 lukkiutuminen

Joku huutaa lisää

Vuorojen jakelu	 nälkiintyminen

Onneton prioriteetti

Ratkottavien ongelmien aiheita antavat…

Auvo Häkkinen

Täysin	Poissulkeminen

erilliset Kilpailu	Lukkiutuminen

prosessit	Nälkiintyminen

Prosessit	Poissulkeminen

epäsuorasti Yhteistyö	Lukkiutuminen

tietoisia toisista	Yhteinen muisti	Nälkiintyminen

Datan ajantasaisuus

Prosessit

suorasti Yhteistyö	Lukkiutuminen

tietoisia toisista Sanomanvälitys	Nälkiintyminen

ks. Stallings Tab 5.1

Suoritusjärjestys / ajoitus

Prosessin lopputulos

Auvo Häkkinen

Syntaksimerkinnät

Auvo Häkkinen

Ohjelmointimerkinnät

Yleiset kurssin algoritmien ohjelmointimerkinnät

Alkujuuret: Pascal, C, C++, Java

Yksikäsitteisesti, ymmärrettävästi

Esittelyt

int i, j = 3;

double sum = 0;

real x;

int a[n] # int a[0:n-1]

int b[1:n] # array of n integers

double c[n,n] = ([n] ([n] 1.0))

Auvo Häkkinen

Peräkkäisesti suoritettavat lauserakenteet

if (ehtolauseke)

lauseet;

else

lauseet;

while (ehtolauseke) {

lauseet;

}

for [määrä1,…, määräN] {

lauseet;

}

toistojen lukumäärät:	i=0 to N

i=1 to N by 2

i=0 to n-1 st i!=x

i=0 to N, j=0 to M

Auvo Häkkinen

Rinnakkaisesti suoritettavat lauserakenteet

co lause1; # N rinnakkaista suoritusta

// ...	# voivat edetä eri CPU:illa

// lauseN;	# vapaassa järjestyksessä

oc

# jatka tästä vasta kun kaikki haarat suoritettu

Prosessit

process foo {	# yksi prosessi ...	lauseet;

}

process bar[i=1 to N]{	# N prosessia

lauseet;

}

Käytämme kurssilla ensisijaisesti prosessimerkintää!

Auvo Häkkinen

Funktiot ja Proseduurit

int addone(int v) {	# palauttaa kokonaisluvun

return(v+1);

}

main() {	# proseduuri, ei palauta arvoa

int n, sum;

read(n);

for [i = 1 to n]

sum = sum + addone(i);

write (“the final value is”, sum);

}

Auvo Häkkinen

Spesifiointimerkinnät

Atominen transaktio

state_1	# laskennan tila ennen atomisia operaatioita

< S1; … Sn; >	# lista atomisia operaatioita

state_2	# laskennan tila atomisen osan jälkeen

Muut prosessit näkevät joko tilan state_1 tai state_2,

mutta eivät koskaan atomisen alueen välituloksia

Esim. x=0; y=10;

< x=x+1; y=y+1; >

Muut samoja muuttujia käyttävät prosessit näkevät

x==0 JA y==10 tai x==1 JA y==11

Auvo Häkkinen

< await >

< await (ehtolauseke) lauseet; >

Synkronointipisteen merkintä

“odota tässä kunnes ehtolausekkeen arvoksi tulee true”

Kun suoritus jatkuu kohdasta lauseet, ehto takuuvarmasti voimassa

Lauseosan suoritus atominen

Välivaiheet eivät näy muille prosesseille

Esim. < await (s>0) s=s-1; >

Toteutus?

semaforit, monitorit, sanomanvälitys, …

Eräissä tapauksissa ohjelmoija joutuu vielä tarkistamaan ehdon voimassaolon, ennenkuin voi antaa suorituksen jatkua!

(Esim. useita odottajia, jotka pääsevät yhtäaikaa jatkamaan)

Auvo Häkkinen

Kertauskysymyksiä?

Johdantoa

Averell

2004-11-03T11:35:22