Međuprocesna komunikacija-nastavak
Promotrimo primjer sa predavanja: Neka je dan neki višedretveni model sa 7 dretvi i relacija "<" – "treba se dogoditi prije". Neka su definirani sljedeći parovi u toj relaciji:
D1<Dj za j={2,3,4,5,6,7}
D2<Dj za j={5,7}
D3<Dj za j={5,6,7}
D4<Dj za j={6,7}
D5<D7 i D6<D7
Napisati program koji implementira ova pravila (dretva.c - u rješenju su korišteni POSIX semafori). (Napomena: mala modifikacija u odnosu na rješenje iz predavanja.Ne postavljaju se inicijalne vrijednosti i dretve ne čekaju svoj semafor, već semafor onih dretvi koje se trebaju prije izvršiti. Može se realizirati i na način opisan u predavanju. Tada se, s obzirom da semafor ne može imati negativne vrijednosti, koriste System V semafori te se definira broj koji predstavlja nulu, obično maximalna vrijednost semafora / 2 .)
Primjer: Napisati program koji bi pravilno modelirao sljedeći problem: Na obalu rijeke dolaze proizvoljnim redoslijedom kanibali i misionari. Preko rijeke se prevoze čamcem koji može prevoziti 3 osobe. Čamac vozi samo onda kad su sva mjesta popunjena i vraća se s druge strane prazan. Ne smije se dogoditi da se u čamcu nađu 2 kanibala i 1 misionar. Ostale kombinacije su dozvoljene.
Rješenje sa procesima: kanibalp.c
Monitori
Gledajući primjere rukovanje semaforima izgleda jednostavno. No ako pogledamo primjer potrošač-proizvođač možemo primjetiti da ako zamijenimo redoslijed dviju down operacija, može se dogodit da proces ostane trajno blokiran, što ukazuje da treba biti pažljiv u rukovanju sa semaforima. Kako bi bilo lakše pisati točne programe koji rješavaju problem sinkronizacije procesa, Hoare (1974.) i Brinch Hansen(1975.) su predložili viši nivo primitivnih (jendostavnih) sinkronizacijskih metoda - monitore. Monitor je kolekcija procedura, varijabli i struktura podataka koje se grupirane unutar jednog module ili paketa. Procesi mogu pozivati procedure unutar monitora bilo kad, ali ne mogu direktno pristupiti monitorovim internim strukturama. Monitor zapisan u nekom imaginarnom jeziku izgledao bi otprilike ovako:
monitor example
integer i;
condition c;
procedure producer();
.
.
.
end;
procedure consumer();
.
.
.
end;
end monitor;
Monitori imaju važno svojstvo, koje ih čini korisnim kod međusobnog isključivanja, da samo jedan proces može biti aktivan unutar monitora u pojedinom trenutku. Monitori su programska konstrukcija unutar nekog programskog jezika te kompajler poznaje njihovu specijalnost te drugačije rukuje sa pozivima procedura unutar monitora. Ako neki proces poziva neku proceduru unutar monitora dok je neki drugi proces već unutar njega (bez obzira u kojoj proceduri unutar monitora), proces će biti privremeno zaustavljen dok proces koji je unutar monitora ne izađe iz njega. Na ovaj način se kompajler brine oko međusobnog isključivanja, a ne programer, što smanjuje mogućnost pogrešaka.
U prethodnim primjerima vidjeli upoznali smo se sa uvjetnim varijablama (condition variables) koje u kombinaciji sa mutexima nisu patili od race condition-a kao primjer sa sleep i wakeup.
Kako bi riješili problem potrošač-proizvođač pomoću monitora također ćemo koristiti uvjetne varijable, zajedno sa dvije operacije na njima (nazovimo ih wait i signal). Kada neka procedura otkrije da ne može nastaviti svoje izvršavanje iz nekog razloga (npr. spremnik je pun i sl.) ona će izvršiti wait, te čekati na nekoj uvjetnoj varijabli. Ta akcija će uzrokovati blokiranje procesa, ali na način da se dopusti nekom drugom procesu ulazak u monitor. Operacija signal postavljat će uvjetnu varijbalu i signalizirati blokiranom procesu da može nastaviti svoje izvršavanje. Kako bi izbjegli da dva procesa istovremenu krenu sa izvršavanjem moramo definirati što se događa nakon izvršavanja operacije signal.
Hoare je predložio da se novo-probuđeni proces nastavi izvršavati istovremeno suspendirajući (privremeno zaustavljajući) drugi proces. Brinch Hansen je pak predložio da proces nakon izvrašvanja naredbe (operacije) signalmoa izaći iz monitora, odnosno signal se može eventualno pojaviti kao zadnje naredbe unutar neke monitorske procedure. Obično se koristi Brinch Hansenovo rješenje jer je konceptualno jednostavnije i jednostavnije je za implementirati. Ako više procesa čega uvjetno varijablu, nakon naredbe signal, scheduler će probuditi samo jedan blokirani proces.
Napomena: Predloženo je i treće rješenje: da proces koji izvrši signal nastavi svoje izvršavanje dalje, te tek nakon što izađe iz monitora blokirani proces nastavi svoje izvršavanje.
Potrebno je napomenuti da uvjetne varijable nemaju mogućnost brojanja za razliku od semafora, tj. ako je neka uvjetna varijabla signalizirana, a da nitko ne čega na nju, taj se signal izgubi. U nekakvom imaginarnom jeziku (tzv. Pidgin Pascal) problem proizvođač-potrošač bi imao ovakvo rješenje.
monitor ProducerConsumer
condition full, empty;
integer count;
procedure insert (item: integer);
begin
if count=N then wait(full);
insert_item(item);
count := count + 1;
if count = 1 then signal(empty)
end;
function remove:integer;
begin
if count=0 then wait(empty);
remove = remove_item;
count := count -1;
if count = N – 1 then signal(full)
end;
count :=0;
end monitor;
procedure producer;
begin
while true do
begin
item = produce_item;
ProducerConsumer.insert(item)
end;
end;
procedure consumer;
begin
while true do
begin
item = ProducerConsumer.remove();
consume_item
end;
end;
Neki programski jezici podržavaju monitore, mada ne uvijek u formi koju su predložili Hoare i Brinch Hansen. Jedan od takvih jezika je Java (monitore još ima Modula-2). Dodavanjem ključne riječi synchronized prilikom deklaracije metode, osiguravamo da nijedna druga dretve neće moći pristupiti nijednoj synchronized metodi unutar te klase. Rješenje problema potrošač-proizvođač u Javi bi izgledalo ovako:
<primjer ProducerConsumerMonitor.java + Item.java i ProducerConsumer.java>
Java nema uvjetne varijable, već koristi dvije procedure wait i notify koje su ekvivalent sleep i wakeup operacija uz iznimku da kada se koriste unutar synchronized metoda ne podliježu uvjetima utrke (race condition-u). Također,Java nema semafore, mada se lako mogu simulirati pomoću monitora ( vidi Semaphore.java)
Klasični IPC problemi
Problem 5 filozofa (The Dining Philosophers Problem)
1965. Dijkstra je predložio i riješio problem sinkronizacije koji je nazvao "the dinning philosophers problem". Problem je sljedeći: Pet filozofa sjedi za okruglim stolom. Svaki od filozofa ima jedan zdjelu špageta (riže ili sl), a između svakog para zdjela nalazi se jedna vilica (ili štapić). Životni ciklus filozofa sastoji se od alternirajućih perioda razmišljanja i hranjenja. Kad je filozof gladana on pokušava uzeti lijevi i desni štapić. Ako uspije u tome, jede neko vrijeme, odloži štapiće i nastavi razmišljati. Potrebno je napisati program koji simulira rad filozofa, tako da nikad ne dođe do zaglavljivanja.
Očito 'rješenje' , koje nije točno (jer se lako vidi da je moguć potpuni zastoj), bilo bi:
#define N 5 /*broj filozofa*/
void philosopher(int i)
{
while(TRUE){
think();
take_fork(i); /*uzmi lijevu vilicu (štapić)*/
take_fork((i+1)%N) /*uzmi desnu vilicu*/
eat();
put_fork(i); /*odloži lijevu vilicu */
put_fork((i+1)%N); /*odloži desnu vilicu */
}
}
Jedno od poboljšanja bilo bi ako bi posljednjih pet naredbi ogradili i zaštitili binarnim semaforom. Međutim, u tom slučaju, u bilo kojem trenutku samo jedan filozof bi mogao jesti, što očito nije dobro iskorištavanje resursa.
Pravilno rješenje bilo bi sljedeće:
#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2
semaphore mutex;
semaphore s[N]; /*jedan semafor za svakog filozofa*/
int state[N]; /*stanje pojedinog filozofa */
void philosopher (int i)
{
while(TRUE){
think(i);
take_forks(i); /*budi blokiran dok ne uzmeš obje vilice */
eat(i);
put_forks(i); /*odloži vilice na stol */
}
}
void take_forks(int i){
down(mutex); /*uđi u kritični odsječak */
state[i] = HUNGRY; /*zabilježi da je filozof i gladan*/
test(i); /* pokušaj uzeti vilice */
up(mutex); /* izađi iz kritičnog odsječka*/
down(s[i]); /* ostani blokiran ako vilice nisu uzete*/
}
void put_forks(int i){
down(mutex); /*uđi u kritični odsječak */
state[i] = THINKING; /*promijeni stanje filozofa i u razmišljanje*/
test(LEFT); /*pogledaj da li je lijevi susjed može jesti*/
test(RIGHT); /*pogledaj da li je desni susjed može jesti*/
up(mutex); /* izađi iz kritičnog odsječka*/
}
void test(int i){ /* ako je stanje filozofa i gladan, a njegovi susjedi ne jedu, podigni semafor filozofa i te stavi stanje na gladan*/
if( state[i] == HUNGRY
&& state[LEFT] != EATING
&& state[RIGHT] != EATING ) {
state[i] = EATING;
up(s[i]);
}
}
Readers and Writers Problem
Problem 5 filozofa je koristan za modeliranje procesa koji se natječi sa ekskluzivno pravo pristupa limitiranom broju resursa. Sljedeći poznati problem je problem čitača i pisača (readers and writers problem, Courtois 1971.) koji modelira pristup bazi podataka. Lako je smisliti primjer u kojem bi istovremeno pisanje dvaju procesa (ili npr. samo i istovremeno i čitanje i pisanje) u bazu podataka moglo imati loše posljedice (npr. rezervacije karata i sl.). S druge strane ograničavanje prava pristupa na samo jednog korisnika ne bi imalo smisla kad bi svi procesi čitali iz baze. Rješenje problema se može dati na sljedeći način. Bit će nam potrebna 2 binarna semafora. Prvim semaforom (u rješenju ćemo ga nazvati mutex) ćemo osiguurati da nam se dva procesa ne nađu unutar provjere broja trenutnih čitača u bazi. Drugi semafor (u rješenju nazvan db ) služit će da bi osigurao ekskluzivno pravo pisanja.
semaphore mutex=1; /*otvoren na početku*/
semaphore db=1; /* kontrolira pristup bazi - otvoren na početku*/
int rc=0;
void reader(void)
{
while(TRUE){
down(mutex); /*ekskluzivni pristup rc-u*/
rc = rc + 1;
if (rc==1) down(db); /*prvi reader zaključava pristup bazi*/
up(mutex); /* oslobađanje pristupa rc-u */
read_data_base();
down(mutex);
rc = rc - 1;
if(rc==0) up(db); /* zadnji čitač otpušta lock na bazi*/
up(mutex);
use_data_read();
}
}
void writer(void)
while(TRUE){
think_up_data();
down(db); /*čeka na pristup bazi*/
write_data_base();
up(db);
}
}
Ako bolje promotrimo ovo rješenje vidjet ćemo da neće dovesti do potpunog zastoja, ali može imati jednu drugu neželjenu posljedicu. Preptostavimo da svaki čitač treba 5 sekundi za obavljanje posla i da zahtjevi pristižu svake 2 sekunde. U takvom slučaju može se dogoditi da pisač nikad ne dobije mogućnost prolaska kroz semafor.
Kako bi se izbjegla ovakva situacija, program se može malo modificirati: U trenutku kada se čitač pojavi i pisač čeka, čita se privremeno zaustavlja i stavlja u red iza pisača. Na ovaj način pisač samo treba pričekati dotad aktivne čitače. Mana ovog rješenja je da se postiže manja konkurentnost i slabije performanse.
Promotrimo rješenje koje favorizira proces pisač:
void reader(void)
{
while(TRUE){
down(mutex3); /*Samo jedan reader može ući unutra*/
down(r); /*reader je ograničen ovim semaforom*/
/*ovdje reader stiže u prednost jer reader mora ovo proći prije nego zaključa writera */
down(mutex1); /*ekskluzivni pristup rc-u*/
rc = rc + 1;
if (rc==1) down(db); /*prvi reader zaključava pristup bazi*/
up(mutex1); /* oslobađanje pristupa rc-u */
up(r); /* dopuštanje prolaza ostalim reader-ima*/
up(mutex3);
read_data_base();
down(mutex1);
rc = rc - 1;
if(rc==0) up(db); /* zadnji čitač otpušta lock na bazi*/
up(mutex1);
use_data_read();
}
}
void writer(void)
while(TRUE){
think_up_data();
down(mutex2); /*zaključava pristup write countu-u
wc = wc + 1;
if (wc==1) down(r); /*writer zaključa readera i dobije prednost /*jer ga zaključa prije nego reader dođe do db semafora */
up(mutex2);
down(db);
write_data_base();
up(db);
down(mutex2);
wc = wc - 1;
if (wc == 0) up(r); /*zadnji writer odključava readera */
up(mutex2);
}
}
Dodatna objašnjenja:
mutex3 koristimo samo kod čitača i uzrokuje da se čitači međusobno natječu bez miješanja sa pisačem ili nekim drugim čitačem koji je već ušao u provjeru.
mutex1 i mutex2 imaju istu sličnu svrhu kao mutex iz prethodnog rješenja : sprječavaju istovremeni pristup varijablama rc i wc (read count i write count)
r osigurava da ako je reader u kritičnom odsječku i ako neki writer čeka nijedan reader neće moći ući unutra, pa se tako neće moći natjecati za pristup bazi.
Sleeping Barber Problem
Sljedeći klasični problem se 'odvija' u brijačnici. Brijačnica ima jednog brijača, jednu brijačku stolicu i n stolica za mušterije koje čekaju. Ako nema mušterija brijač sjedne u svoju stolicu i zaspe. Kada mušterija dođe, mora probuditi uspavanog brijača. Ako dođe još mušterija oni će ili sjesti na stolice za čekanje (ako ima slobodnih) ili će izaći iz brijačnice ako nema slobodnih mjesta. Problem je modelirati ovaj postupak bez dolaska do uvjeta utrke. Ovaj problem je sličan različitim situacijama čekanja, kao što je npr. helpdesk sa više ljudi i sustavom čekanja za dolazeće telefonske pozive (uz ograničeni kapacitet linija na čekanju).
Rješenje ovog problema koristi tri semafora: customers , koji broji mušterije koje čekaju (osim onoga na brijačkoj stolici, koji ne čeka), barbers, koji broji slobodne brijače (u ovom primjeru 0 ili 1), te binarni semafor mutex koji služi za međusobno isključivanje. Također potrebna nam je i varijabla waiting, koja broji mušterije. Ta varijabla je zapravo kopija semafora customers, međutim potrebna je jer nemamo mogućnost samo pročitati vrijednost semafora. Preko ove varijable nadolazeća mušterija će znati da li treba ući u brijačnicu ili ne.
#define CHAIRS 5
semaphore customers;
semaphore barbers;
semaphore mutex;
int waiting = 0;
void barber(){
while(TRUE) {
down(customers); /*spavaj ako nema mušterija*/
down(mutex); /*dohvati pristup varijabli waiting*/
waiting = waiting - 1;
up(barbers); /*jedan brijač više je slobodan*/
up(mutex);
cut_hair();
}
}
void customer(void){
down(mutex); /*pristup varijabli waiting*/
if(waiting < CHAIRS){
waiting = waiting + 1;
up(customers); /*povećaj broj mušterija koje čekaju*/
up(mutex); /*otpusti pristup varijabli waiting */
down(barbers); /*čekaj slobodnog brijača*/
get_haircut(i);
} else {
up(mutex); /*brijačnica je puna.nemoj čekati.*/
}
}