Comunicarea si sincronizarea inter-proces

Procesele uneori trebuie sa conlucreze

De ce?

o       Realizarea unui scop comun

o       Modularitate

Cum? (modele de comunicare)

o       Comunicare de rezultate (producator - consumator)

o       Efectuarea de servicii (client - server)

o       Conlucrarea pentru un scop comun (procesare paralela) (ex. inmultirea paralela a doua matrici)

o       Folosirea unei resurse comune

Orice colaborare se reduce la doua concepte

o       Transfer de informatie

o       Sincronizare

Sistemul de operare mediaza comunicare si sincronizarea

Cum?

o       Prin primitive puse la dispozitia proceselor

Primitivele au evoluat in timp

o       Pentru a fi complete

o       Pentru a fi usor de inteles, folosit si implementat

o       Au fost determinate de evolutia hardware-lui

o       Au determinat evolutia hardware-ului

o       Au fost incluse in unele limbaje de programare (Ada, Java, Modula)

o       "Puterea" lor poate fi analizata teoretic

"Sabloane" teoretice de probleme

Excludere mutuala

Producator - consumator

Problema filozofilor

Problema fumatorului

Memorie partajata

Excluderea mutuala

o       Ideea 1

Shared int I=0; Shared int I;

While true do While true do

Procesare_necritica; Procesare_necritica;

While (I<>0) do; While (I<>0) do;

I=1; I=1;

Procesare_exclusiva; Procesare_exclusiva;

I=0; I=0;

EndWhile  EndWhile

o       Ideea 2

Shared int I=0; Shared int I;

While true do While true do

Procesare_necritica; Procesare_necritica;

While (I<>1) do While (I<>2) do

If I=0 Then I=1;  If I=0 Then I=2;

Procesare_critica; Procesare_critica;

I=0; I=0;

EndWhile  EndWhile

o       Ideea 3

Shared int turn=0; Shared int turn=0;

while (TRUE) }

Ajutor hardware - Test and Set

Caracteristica esentiala - busy waiting

Regiuni critice

Region V do statement;

Excludere mutuala

DeclareRegion V;

While true do While true do

Procesare_necritica; Procesare_necritica;

Region V do Region V do

Procesare_exclusiva; Procesare_exclusiva;

EndWhile  EndWhile

Producator - consumator

o       Producator

Shared Data;

Shared status = EMPTY;

Region V;

While true do

Produce(item);

Succeded = 0;

While Succeded = 0 do

Region V do

If status = EMPTY then

Data = item;

Status = FULL;

Succeded = 1;

Endif

EndWhile

EndWhile

o       Consumator

Shared Data;

Shared status = EMPTY;

Region V;

While true do

Succeded = 0;

While Succeded = 0 do

Region V do

If status = FULL then

Item = Data;

Status = EMPTY;

Succeded = 1;

Endif

EndWhile

Consume(item);

EndWhile

o       Probleme?

Regiuni critice conditionale

When Conditie Region V Do Statement;

Producator consumator

o       Producator

Shared Data;

Shared status = EMPTY;

Region V;

While true do

Produce(item);

When status = EMPTY Region v Do

Data = item;

Status = FULL;

EndWhen

EndWhile

o       Consumator

Shared Data;

Shared status = EMPTY;

Region V;

While true do

When status = FULL Region v Do

Item = Data;

Status = EMPTY;

EndWhen

Consume(item);

EndWhile

Deja orice problema de sincronizare poate fi rezolvata fara busy-waiting

Semafoare

Doua operatii atomice UP(sem) si DOWN(sem)

Denumite si P(sem) (down) si V(sem) (up)

Binari sau generali

Producatori - consumatori cu buffer

#define N 100 / number of slots in the buffer

semaphore mutex = 1;

semaphore empty = N;

semaphore full = 0;

void producer(void)

void consumer(void)

Semafoarele sunt echivalente cu regiunile critice conditionale

o       Demonstratia

o       implementarea unui semafor folosind RCC

Shared contor_sem;

Region v;

UP()

DOWN()

o       implementarea unei RCC folosind semafoare

Monitoare

Operatii

o       Enter_Monitor, Leave_monitor

o       Wait( variabila_conditie )

o       Signal( variabila_conditie )

Programarea orientata pe obiect

Monitoare in Java

o       Fiecare obiect este un monitor

o       O singura variabila - conditie per monitor

Object o;

Synchronized(o)

Synchronized(o)

Synchronized(o)

Synchronized(o)

Echivalenta monitoare - semafoare

Class semafor

synchronized DOWN()

Problema filozofilor

Generalizarea problemei

Ideea 1

#define N 5 / number of philosophers

semaphore forks[N] := 1; /* all initially free */

void philosopher(int i)

void take_fork(int i)

void put_fork(int i)

Inter-blocari (dead-locks)

o       Mutual Exclusion

o       Hold and Wait

o       No Preemption

o       Circular Wait

Ideea 2

#define N 5 / number of philosophers

void philosopher(int i)

Ideea 3

#define N 5

#define LEFT (i+N1)%N

#define RIGHT (i+1)%N

#define THINKING 0

#define HUNGRY 1

#define EATING 2

int state[N];

semaphore mutex = 1;

semaphore s[N];

void philosopher(int i)

void take_forks(int i)

void put_forks(i)

void test(i)

o       Probleme?

Sincronizare si comunicare prin cozi de mesaje

Primitive

o       Create_message_box(&msgb)

o       Send_message(&msgb, msg)

o       Receive_message(&msgb, &msg)

Rendez-vous (Ada)

Primitive

Task task1;

Select

When conditie1 => accept point1(parametrii) do statement1;

Statement2;

When conditie2 => accept point2(parametrii) do statement3;

Statement4;

Else

Statement5;

End select;

End task;

Task task2;

task1.point2(parametrii);

end task.

Task semafor;

Int i=0;

While true do

Select

When i>0 accept DOWN() do i--;

When true accept UP() do i++;

End select

End while

End task.

Filozofi ideea 1

shared ST_FIL[0..N-1] = THINK;

shared ST_FORK[0..N-1] = ON_TABLE;

task TABLE;

while true do

x = -1;

select

when true TEST(fil) do

if ST_FILE[fil] == HUNGRY and

ST_FORK[fil] == ON_TABLE and

ST_FORK[(fil+1)%N] == ON_TABLE

then

x = fil;

endif

endwhen

when true PUT(fil) do

ST_FORK[fil] == ON_TABLE

ST_FORK[(fil+1)%N] == ON_TABLE

endwhen

endselect

if x >= 0 then

ST_FORK[x] = TAKEN;

ST_FORK[(x+1)%N] = TAKEN;

FIL[x].CAN_EAT();

endif

endwhile

endtask

task FIL[I=0..N-1];

while true do

ST_FIL[I]=HUNGRY;

TABLE.TEST(fil);

select

when true CAN_EAT() do

ST_FIL[I]=EAT;

endwhen

endselect

EAT();

ST_FIL[I]=THINK;

TABLE.PUT(I);

TABLE.TEST((I-1)%N);

TABLE.TEST((I+1)%N);

THINK();

endwhile

endtask

Filozofi ideea 2

shared ST_FIL[0..N-1] = THINK;

shared ST_FORK[0..N-1] = ON_TABLE;

task TABLE;

while true do

x = -1;

select

when true TEST(type, fil) do

if type == SAME then

ST_FIL[fil]=HUNGRY

endif

if ST_FILE[fil] == HUNGRY and

ST_FORK[fil] == ON_TABLE and

ST_FORK[(fil+1)%N] == ON_TABLE

then

x = fil;

endif

endwhen

when true PUT(fil) do

ST_FORK[fil] == ON_TABLE

ST_FORK[(fil+1)%N] == ON_TABLE

endwhen

endselect

if x >= 0 then

ST_FORK[x] = TAKEN;

ST_FORK[(x+1)%N] = TAKEN;

FIL[x].CAN_EAT();

endif

endwhile

endtask

task FIL[I=0..N-1];

while true do

TABLE.TEST(SAME, fil);

select when true CAN_EAT() do

ST_FIL[I]=EAT;

endwhen; endselect;

EAT();

ST_FIL[I]=THINK;

TABLE.PUT(I);

TABLE.TEST(OTHER, (I-1)%N);

TABLE.TEST(OTHER, (I+1)%N);

THINK();

endwhile

endtask

Problema fumatorilor

Problema barbierului