filosofos

MC514–Sistemas Operacionais: Teoria e Pr´tica a 1s2010

Fil´sofos Famintos o Jantar dos Fil´sofos o Boas solu¸oes c˜ • ausˆncia de deadlock e • ausˆncia de starvation e • alto grau de paralelismo

Representa¸˜o da mesa ca G1

F0

F1

G0

G2

F4

G4

F2

F3

G3

-

T
T
T
T

-

T - T T - H T |H|
T |E|

T
T
T
T

-

T
T
T
T

-

Implementa¸˜o com Sem´foros ca a
Um sem´foro por garfo a • sem init(garfo, 1)
• wait(garfo)
• signal(garfo)

Fil´sofos famintos o Um sem´foro por garfo a G1

F0

F1

G0

G2

F4

G4

F2

F3

G3

Implementa¸˜o simplista ca Fil´sofo i: o while (true) pensa(); wait(garfo[i]); wait(garfo[(i+1) % N]); come(); signal(garfo[i]); signal(garfo[(i+1) % N]);

Deadlock
G1

F0

F1

G0

G2

F4

F2

G4
F3
G3

Veja c´digos: deadlock.c e deadlock-bug-exibicao.c o Outra tentativa... semaforo lock = 1;

Fil´sofo i: o while (true) pensa(); wait(lock); wait(garfo[i]); wait(garfo[(i+1) % N]); come(); signal(garfo[(i+1) % N]); signal(garfo[i]); signal(lock);

Baix´ ıssimo paralelismo
G1

F0

F1

G0
G2

F4

G4

F2

F3

Veja c´digo: sem central.c o G3

O que acontece se lock == 2? semaforo lock = 2;

Fil´sofo i: o while (true) pensa(); wait(lock); wait(garfo[i]); wait(garfo[(i+1) % N]); come(); signal(garfo[(i+1) % N]); signal(garfo[i]); signal(lock);

Menos lugares ` mesa a semaforo lugar mesa = N-1;

Fil´sofo i: o while (true) pensa(); wait(lugar mesa); wait(garfo[i]); wait(garfo[(i+1) % N]); come(); signal(garfo[(i+1) % N]); signal(garfo[i]); signal(lugar mesa);

Menos lugares ` mesa a G1

F0

F1

G0

G2

F2

F4
F3
G4

Veja c´digo: limite lugares.c o G3

Solu¸˜o assim´trica ca e while (true) pensa(); if (i % 2 == 0) wait(garfo[i]); wait(garfo[(i+1) % N]); else wait(garfo[(i+1) % N]); wait(garfo[i]); come();