Međuprocesna komunikacija (IPC[1])

Procesi često moraju komunicirati sa ostalim procesima, iz različitih razloga. Pogledajmo 3 karakteristična primjera tj. potencijalna problema:

1) Kad neki proces želi predati informaciju nekom drugom procesu

2) Kad želimo biti sigurni da 2 ili više procesa neće stati jedan drugome na put u nekim kritičnim aktivnostima (npr. oba procesa pokušavaju uzeti posljednji Mb memorije)

3) Kad postoji ovisnost procesa. Npr. Ako proces A kreira nekakve podatke koje B ispisuje, onda B mora čekati dok A ne kreira neke podatke.

Problemi u slučajevi 2 i 3 prisutni su i kod dretvi, dok je slučaj 1 trivijalan jer dretve dijele isti adresni prostor. Također rješenja koja će vrijediti za procese, vrijedit će i za dretve.

Pretpostavimo da imamo nekoliko različitih procesa koji iz određenih i sasvim razumljivih razloga trebaju međusobnu komunikaciju. Nekoliko metoda omogućit će nam izvršavanje takvih zadataka (uz napomenu da nije sa svima moguće obaviti pojedinu akciju). Promotrit ćemo sljedeće metode/mehanizme:

• Cjevovodi (Pipes)
• Signali (Signals)
• Redovi poruka (Message Queues)
• Semafori
• Zajednička memorija (Shared Memory)
• Sockets

Cjevovodi (Pipes)

Cjevovodi su najstariji oblik Unix međuprocesne komunikacije i omogućeni su od svih Unix sustava. Imaju dva ograničenja:

1. Half-duplex su tipa, tj. protok podataka je samo u jednom pravcu

2. Mogu biti korišteni samo među procesima koji imaju zajedničkog pretka( iznimka su FIFO ili imenovani cjevovodi). Obično proces kreira cjevovod, napravi fork() i cjevovod dijeli između roditelja i djeteta.

Cjevovod se kreira funkcijom pipe (zaglavlje >unistd.h>)

int pipe (int filedes[2]); vraća 0 ako je sve ok, -1 u slučaju greške

Izlaz od filedes[1] služi kao ulaz za filedes[2].

slika: 14.3

primjer pipes1.c

funkcije popen i pclose donekle obavljaju prljavi posao kreiranja cjevovoda, fork-a procesa i zatvaranje nekorištenih krajeva cjevovoda, pokretanje ljuske da bi izvršili neku komandu te čekanja na kraj izvršavanja

FILE *popen (const char *cmdstring,const char *type);

vraća file pointer ako je sve ok, NULL u slučaju greške

int pclose (FILE *fp); vraća 0 ako je sve ok, -1 u slučaju greške

Na ovaj način npr. možemo napraviti sljedeće fp = popen("ls *.c", "r"); i sl.

primjeri pipes2.c i pipes3.c

primjer pipes4.c slika 14.8

Zajednička memorija

Zajednička memorija je efikasan način međusobnog djeljenja podataka među programima. Jedan od programa (procesa) će kreirati određeni prostor u memoriji kojem će ostali procesi pristupati i to na načn da "privežu" segment fizičke memorije na vlastiti virtualni adresni prostor. Promotrit ćemo nekoliko načina kreiranja i korištenja zajedničke memorije u sljedećeim sustavima: System V, POSIX, Windows32.

System V shared memory

(Napomena: Za korištenje donjih funkcija potrebno je uključiti sljedeća zaglavlja: sys/types.h , sys/shm.h i sys/ipc.h)

Kako bi dobili identifikacijski broj zajedničke memorije koristimo sistemski poziv :

int shmget(key_t key, size_t size, int flag);

gdje key parametar (tipa key_t koji je obično int) predstavlja identifikacijski ključ segmenta memorije. U slučaju da kao key navedemo konstantu IPC_PRIVATE kreirati će se novi segment zajedničke memorije. size predstavlja veličinu zajedničkog bloka u byteovima, dok flag predstavlja inicijalna prava pristupa (zadnjih 9 bitova) i kontrolu kreiranje. Druga mogućnost da se kreira novi segment je da se u shmflg parametru aktivira bit za kreiranje koristeći broj IPC_CREATE.

U slučaju uspješnog kreiranja poziv vraća cijeli broj koji predstavlja identifikacijski broj segmenta, inače vraća -1.

Primjer korištenja:

npr. shmget (IPC_PRIVATE , 128, 0600)

ili shmget (3571, 128, IPC_CREATE | 0600)

Jednom kreiran segment memorije na adresni prostor procesa možemo zakačiti pomoću

void *shmget(int shmid, void *addr, int flag);

Obično se kao adrr stavlja NULL pa se segment veže na prvu slobodnu adresu (određenu od strane jezgre). flag se može ostaviti 0 (a može se npr. navesti SHM_RDONLY).

U slučaju uspješnog kreiranja funkcija vraća adresu na koju ju je segment vezan, a u slučaju pogreške vraća -1.

Segment možemo otpustiti pozivom:

int *shmdt(void *addr);

koji vraća -1 u slučaju greške, ili 0 ako je segment otpušten.

Uništavanje segmenta obavlja se preko funkcije

int shmctl(int shmid, int cmd, struct shmid_ds *buf);

Ova funkcija služi za izvođenje različitih akcija sa zajedničkim segmentom (vidi man shmctl), a ako želimo s njom izbrisati segment onda ćemo kao parametar cmd navesti IPC_RMID, dok buf možemo ostaviti NULL.

Podaci o upotrijebljenim sredstvima za međuprocesnu komunikaciju (pa tako i o zajedničkoj memoriji) mogu se dobiti naredbom: ipcs. Naredbom ipcrm mogu se uništavati pojedina sredstva. (-m opcija vidi: man ipcrm, man ipcs)

POSIX Shared Memory

POSIX zajednička memorija je zapravo varijacija od mapepd memory. razlika je u tome što se koristi shm_open() kako bi se otvorio objekt iz zajedničke memorije (umjesto poziva open()) te korištenje shm_unlink() za zatvranje i brisanje objekta, umjesto pozivanja close() (koji inače ne briše objekt). Opcije shm_open() su puno manje od opcija funkcije open().

Win32 shared memory

Kao i u gornjem primjeru za kreiranje zajedničke memorije koristimo se varijantom file mappinga. koristeći se API pozivima CreateFileMapping, MapViewOfFile, OpenFileMapping i UnmapViewOfFile.

Za detaljnije opise poziva pogledati MSDN.

Primjer: Množenje matrice u 4. procesa (WINAPI)

Primjer: Kombinacija exec naredbi, signala, i zajedničke memorije

Race Conditions

U situaciji kada dva ili više procesa (ili dretve) dijele zajedničke varijable, moguć je sljedeći scenario. (Pričica sa printerom... , primjer race_condition.c)

Ovakve i slične situacije, u kojem dva ili više procesa čitaju ili pišu po zajedničkoj memoriji ili koriste neke zajedničke podatke,a konačni rezultat ovisi o tome u kojem se trenutku koji proces izvršava, nazivaju se race condition. (uvjeti utrke , stanje utrke)

Na koji način izbjeći takve situacije? Očito je potrebno imati međusobno isključivanje, tj. mogućnost da dok jedan proces radi sa zajedničkim varijablama drugi procesi nisu u mogućnosti raditi istu stvar. Dio programa u kojem se pristupa zajedničkoj memoriji naziva se kritični odsječak. Da bi pronašli dobro rješenje trebamo zadovoljiti sljedeće četiri uvjeta:

1. Ne smije se dopustiti da dva procesa u isto vrijeme budu unutar njihovih kritičnih odsječaka.

2. Ne smije se osloniti na pretpostavke bazirane na brzini ili broju procesora.

3. Proces izvan svog kritičnog odsječka ne smije blokirati neki drugi proces.

4. Nijedan proces ne smije beskonačno čekati na ulazak u kritični odsječak.

Predloženo je nekoliko rješenja ovih problema (Dekker, Lamport i Petterson), kao i hardversko rješenje sa instrukcijom TSL (Test and Set Lock).

Pogledajmo Lamportov protokol za međusobno isključivanje više procesa (ili dretvi)

zajedničke varijable: TRAŽIM[0..n-1], BROJ[0..n-1]

proces proc(i), pokušaj ulaska u kritični odsječak

ULAZ[i] = 1

BROJ[i] = max(BROJ[0],...,BROJ[n-1]) + 1

ULAZ[i] = 0

za j = 0 do n-1 čini{

dok je ULAZ[j]<>0 čini

ništa

dok je BROJ[j]<>0 ^ (BROJ[j],j)<(BROJ[i],i) čini

ništa

}

/* kritični odsječak*/

BROJ[i] = 0

kraj.

Promotrimo još Petersonovo rješenje:

Hardversko rješenje zasnivalo bi se na korištenju (odnosno postojanju) instrukcije TSL (Test and Set Lock), npr. TSL RX, LOCK koja bi pročitala sadržaj memorije na lokaciji LOCK i prebacila ga u registar RX, a zatim na adresu LOCK stavila vrijednost različitu od nule (npr. 1). Izvršavanje ove instrukcije bi bilo nedjeljivo (zaključavanje memorijske sabirnice).

U ovom slučaju bi imali sljedeća rješenja:

uđi_u_kritični_odsječak:

TSL REGISTER,LOCK |prekopiraj lock u registar i postavi lock na 1

CMP REGISTER,#0 |da li je lock jednak nuli

JNE uđi_u_kritični_odsječak |ako nije, ponovi petlju

RET |izađi iz petlje, ulazak u kritični odsječak

izađi_iz_kritičnog_odsječka:

MOVE LOCK,#0 |stavi nulu u lock

RET |izađi iz petlje, izlazak iz kritičnog odsječka

Međutim mana ovih rješenja je da pate od tzv. busy waitinga (tzv. spin lock metode). Naime dok čekaju na svoj red za ulazak u kritični odsječak cijelo vrijeme ispituju određene varijable i troše procesorko vrijeme. Štoviše, ako su neki od tih procesa višeg prioriteta može se dogoditi da ostali procesi nikad ne dobiju procesorsko vrijeme (priority inversion problem).

Kao metoda za izbjegavanje busy waiting-a ponuđena je ideja sa jednostavnim metodama koje bi u slučaju nemogućnosti ulaska u kritični odsječak blokirale proces umjesto trošenja procesorskog vremena. Takav jednostavan par bi bio sleep i wakeup. Međutim i ovaj pristup, što se lako može vidjeti u donjem primjeru, pati od race condition-a. Kao primjer na koji način se ove dvije primitivne (jednostavne) metode mogu koristiti možemo uzeti problem proizvođač-potrošač (poznat još kao problem ograničenog spemnika, eng. bounded-buffer).

#define N 100

int count=0;

void producer(void){

int item

while(TRUE){

item=produce_item();

if (count==N) sleep();

insert_item(item);

count=count+1;

if (count==1) wakeup(consumer);

}

}

void consumer(void){

int item;

while(TRUE){

if (count==0) sleep();

item = remove_item();

count = count – 1;

if (count==N-1) wakeup(producer);

consume(item);

}

}

Međutim i ovaj pristup pati od race condition-a. Naime count nije zaštićen (i sa postojećim metodama i protokolima to nije moguće napraviti) te je moguće da se signal koji bi trebao 'probuditi' blokirajući proces pojavi prije nego što se zapravo proces blokirao i tako nepovratno nestane, a proces ostane trajno blokiran. (Na Unix operativnom sustavu postoji rješenje koje ne pati od tog problema, vidi primjer kasnije). Ideja za rješavanje problema je npr. dodati tzv wakeup waiting bit. Međutim kako broj procesa raste, ova ideja nije dovoljna.

Rješenje ovakvog problema dao je Dijkstra 1965. Predložio je korištenje cjeobrojne varijable koja bi brojila broj wakeup signala za naknadno korištenje. Takav novi tip varijable nazvao je semaforom. Predložio je dvije operacije down i up (originalno P i V , mi ćemo još koristiti cekajSem i postaviSem). down bi provjeravala da li je vrijednost semafora veća od 0. Ako da umanjila bi vrijednost za 1, a ako ne onda bi proces bio stavljen na 'spavanje' dok uvjet ne bude zadovoljen. Ove akcije bi bile nedjeljive, što je i osnovni preduvjet za rješavanje problema sinkronizacije. up bi povećala vrijednost semafora za 1.

Pogledajmo kako bi sad izgledao rješenje problema potrošač proizvođač koristeći semafore. Rješenje zahtjeva 3 semafora: full koji bi brojao broj popunjenih slotova, zatim semafor empty koji bi brojao broj praznih slotova i semafor mutex koji bi osigurao da potrošač i proizvođač ne pristupaju spremniku u isto vrijeme. full je inicijalno postavljen na 0, empty na broj slobodnih mjesta u spremniku, a mutex inicijalno ima vrijednost 1.

(Napomena: semafori koji služe da dva ili više procesa ne uđu u istom trenutku u neki kritični odsječak, te poprimaju samo vrijednosti 0 i 1 nazivaju se binarni semafori. Mutex dolazi od riječi mutual exclusion)

#define N 100

semaphore mutex=1;

semaphore empty=N;

semaphore full=0;

void producer(void){

int item;

while(TRUE){

item=produce_item();

down(empty);

down(mutex);

insert_item(item);

up(mutex);

up(full);

}

}

void consumer(void){

int item;

while(TRUE){

down(full);

down(mutex);

item = remove_item();

up(mutex);

up(empty);

consume(item);

}

}

Načini kreiranje i korištenja semafora:

System V semafori:

(Napomena: Za korištenje donjih funkcija potrebno je uključiti sljedeća zaglavlja: sys/types.h , sys/sem.h i sys/ipc.h)

System V semafori su dosta kompleksni i odudaraju od uobicajene Dijsktrine ideje, međutim njihov rad je moguće svesti na uobičajeno ponašanje.

Funkcije za rad sa semaforima su slične funkcijama sa rad sa zajedničkom memorijom.

Kako bi dobili identifikacijski broj semafora koristimo sistemski poziv :

int semget(key_t key, inr nsems, int flag);

gdje key parametar (tipa key_t koji je obično int) predstavlja identifikacijski ključ semafora. U slučaju da kao key navedemo konstantu IPC_PRIVATE kreirati će se novi semafor. nsems predstavlja broj semafora u novo kreiranom skupu semafora, dok flag predstavlja inicijalna prava pristupa (zadnjih 9 bitova) i kontrolu kreiranje. Druga mogućnost da se kreira novi segment je da se u shmflg parametru aktivira bit za kreiranje koristeći konstantu IPC_CREATE.

U slučaju uspješnog kreiranja poziv vraća cijeli broj koji predstavlja identifikacijski broj segmenta, inače vraća -1.

Redni brojevi semafora u skupu počinju od nule. Zbog jednostavnosti bilo bi dobro imati uvijek samo po jedan semafor u skupu. Međutim, kao i kod zajedničke memorije, ukupan broj skupova semafora u sustavu je ograničen. Zbog velikog broja korisnika taj je broj lako premašiti, pa je poželjno sve potrebne semafore uvijek dobavljati odjednom, tj. u jednom skupu.

Primjer korištenja:

npr. semget (IPC_PRIVATE , 1, 0600)

ili semget (3571, 1, IPC_CREATE | 0600)

Brisanje semafora sa sustava obavlja se preko funkcije

int semctl(int semid, int semnum, int cmd, union semun arg);

na način da se za cmd navede IPC_RMID, a za semid id semafora. Ostala dva argumenta nisu bitna.

Ova funkcija služi i za izvođenje različitih akcija sa semaforom (vidi man semctl), npr. dohvat/postavljanje vrijednosti pojedinog semafora (semnum) u skupu (cmd je tad GETVAL / SETVAL ili GETALL / SETALL). Funkcija za sve GET komande (osim GETALL) vraća odgovarajuću vrijednost, a za sve ostalo 0 (-1 u slučaju greške).

union semun {

int val; /*za SETVAL*/

struct semid_ds *buf; /*za IPC_STAT i IPC_SET */

unsigned short *array; /*za SETALL ili GETALL */

};

struct sembuf {

short sem_num;

short sem_op;

short sem_flg;

};

int semop(int semid, struct sembuf (*sops)[], int nsops) ;

semop se može upotrijebiti za nedjeljivo izvođenje niza operacija na skupu semafora. Međutim, najčešće je sasvim dovoljno izvesti jednu operaciju u jednom pozivu. U tom slučaju, semid je identifikacijski broj skupa semafora, nsops je 1, a sops je kazaljka na strukturu koja opisuje traženu operaciju. Unutar te strukture, sem_num je redni broj semafora u skupu, sem_op je tražena operacija koju dodatno opisuje i sem_flg.

Za uobičajeno korištenje semafora dovoljne su dvije vrste operacija: povećavanje vrijednosti semafora (sem_op je pozitivan) i smanjivanje vrijednosti semafora (sem_op je negativan). U oba slučaja, sem_flg treba biti 0. semop vraća rezultat 0 ako je sve u redu, ili -1 u slučaju greške.

Smanjivanje vrijednosti semafora odgovara operaciji "čekaj". Ukoliko je vrijednost semafora moguće umanjiti za dani broj, a da ne postane negativna, vrijednost se umanjuje, a proces nastavlja rad. U suprotnom slučaju, proces čeka dok vrijednost semafora ne postane dovoljno velika da se umanjivanje može provesti.

Povećavanje vrijednosti odgovara operaciji "postavi". Vrijednost semafora se povećava za dani broj, a proces nastavlja rad. Proces zaustavljen u redu semafora se oslobađa ako je ovim povećanjem vrijednost semafora postala dovoljno velika da je on može umanjiti, a da ipak ne postane negativna.

Podaci o upotrijebljenim sredstvima za međuprocesnu komunikaciju (pa tako i o semaforima) mogu se dobiti naredbom: ipcs. Naredbom ipcrm mogu se uništavati pojedina sredstva. (-s opcija vidi: man ipcrm, man ipcs)

POSIX semafori:

Posix semafori predstavljaju jednostavniju varijantu korištenja semafora. Za rad sa semaforima koriste se funkcije sem_init, sem_destroy, sem_post, sem_trywait, sem_wait iz headera semaphore.h

WINAPI:

Za rad sa semaforima koriste se API pozivi CreateSemaphore, WaitForSingleObject, ReleaseSemaphore, CloseHandle. Njihovo korištenje je dosta jednostavno, za detalje pogledati MSDN.

primjer: potrošač-proizvođač riješen pomoću semafora.

Kao što je već spomenutu, ako nam ne treba semaforova mogućnost brojanja, već nam treba samo zbog međusobnog isključivanja (tj. radi se o binarnom semaforu) tada koristimo pojednostavljenu verziju zvano mutex. S obzirom da su jednostavni za implementaciju i efikasni, pogodni su za implementaciju u dretvenim bibliotekama jer se nalaze u korisničkom prostoru (neki dretveni paketi imaju i poziv mutex_trylock koji se ne blokira u slučaju neuspjeha, već samo vrati grešku).

Kod za mutex (koristeći TSL bio bi nalik ovom:)

mutex_lock:

TSL REGISTER,MUTEX |prekopiraj mutex u registar i postavi mutex na 1 CMP REGISTER,#0 |da li je mutex jednak nuli

JZE ok |ako je bio nula, mutex je otključan, vrat se van

CALL thread_yield |mutex je zauzet, pokreni neku drugu dretvu

JMP mutex_lock |pokušaj ponovo

ok: RET |izađi iz petlje, ulazak u kritični odsječak

mutex_unlock:

MOVE MUTEX,#0 |stavi nulu u mutex

RET |izađi iz petlje, izlazak iz kritičnog odsječka

primjer korištenja mutexa. /*maknuti komentare iz race_condition.c */

primjer: problem potrošač-proizvođač riješen pomoću mutexa i uvjetnih varijabli (sleep-wakeup) na UNIX-u.

primjer: kanibali i misionari -> primjer s dretvama, primjer s procesima.

---

[1] IPC – Interprocess communication