Επόμενο:ΣΥΣΤΗΜΑ ΚΕΝΤΡΙΚΗΣ ΘΕΡΜΑΝΣΗΣ Πάνω: Διάφορα Προβλήματα Παράλληλου Προγραμματισμού Πίσω: Διάφορα Προβλήματα Παράλληλου Προγραμματισμού
ΟΙ ΓΕΥΜΑΤΙΖΟΝΤΕΣ ΦΙΛΟΣΟΦΟΙ
Το παρακάτω πρόγραμμα είναι το γνωστό πρόβλημα των γευματιζόντων φιλοσόφων. Αυτό αναφέρεται στη προσπάθεια ενός αριθμού φιλοσόφων να γευματίσουν χρησιμοποιώντας δύο πιρούνια. Αυτό δε θα αποτελούσε πρόβλημα αν στο τραπέζι υπήρχε ο απαραίτητος αριθμός από πιρούνια. Ανάμεσα όμως σε ζεύγη γειτονικών πιάτων βρίσκεται ένα πιρούνι. Ο κάθε φιλόσοφος περνάει από εναλλασσόμενες περιόδους σκέψης και φαγητού. Αν ο φιλόσοφος αποκτήσει και τα δύο πιρούνια τρωει και στη συνέχεια τα αφήνει στο τραπέζι για να σκεφτεί. Δυστυχώς όμως η προσπάθεια του φιλοσόφου να φαει δεν αποδίδει πάντα, καθώς ακόμα και αν πιάσει το ένα πιρούνι το άλλο μπορεί να είναι κατειλημμένο από το διπλανό του. Το πρόγραμμα τρέχει για ένα συγκεκριμένο χρονικό διάστημα στο οποίο παρατηρούμε τις δραστηριότητες των φιλοσόφων. Στην προσπάθεια το χρονικό αυτό διάστημα να είναι όσο το δυνατόν μεγαλύτερο αφήνουμε το πρόγραμμα να τρέξει μέχρις ότου γεμίσουν οι buffer και σταματήσει η εκτέλεση. Ο κώδικας του προγράμματος είναι ο ακόλουθος. Αξίζει τον κόπο να τονίσουμε το γεγονός ότι στα αποτελέσματα που θα βγουν από το πρόγραμμα παίζει καθοριστικό ρόλο και το μέγεθος της μεταβλητής delay, που δείχνει ουσιαστικά τη συχνότητα με την οποία ο φιλόσοφος προσπαθεί να φαει. Με άλλα λόγια το μέγεθός της delay καθορίζει και το μέγεθος της συμφόρησης του προγράμματος καθώς οι φιλόσοφοι ανταγωνίζονται στο ποιος θα φαει.
Ο κώδικας του προγράμματος είναι ο ακόλουθος:
Program Dining_Philosophers; const no_of_philosophers = 18; no_of_hands = no_of_philosophers * 2; delay_const = 1; deadline = 10; forever = 32000; Grabbed = 0; Put_Back = 1; Is_Free = 2; Is_Occupied = 0; type flag_channel = channel of integer; var request_fork, free_fork: array[1..no_of_hands] of flag_channel; phil_id: integer; temp1, temp2, temp3 : integer;
Η διεργασία αυτή είναι μια γεννήτρια τυχαίων αριθμών.
procedure random (r_x, r_n: real; var rnd: integer); const r_mod = 27296.0; r_mult = 4525.0; range = 10; offset = 3; var r_seed: real; x, n: integer; begin x := round(r_x + offset) mod range; n := round(r_n + offset) mod range; r_seed := x; r_seed := r_seed * r_mult; r_seed := r_seed / r_mod; rnd := round(n * r_seed) mod range; end;
Η διεργασία αυτή προκαλεί απλά καθυστέρηση - δε κάνει τίποτα.
procedure delay(times : integer); var i : integer; begin for i := 1 to times do end;
Η διεργασία της μελέτης υλοποιεί μια τυχαία καθυστέρηση με τη βοήθεια μιας γεννήτριας τυχαίων αριθμών .
procedure think(phil_id : integer);
var
rnd, i: integer;
begin
random(clock, seqtime, rnd);
for i:=1 to rnd do
delay(delay_const);
end;
Η διεργασία του δείπνου ουσιαστικά έχει την ίδια λειτουργία με αυτή της μελέτης. Υλοποιεί δηλαδή μια τυχαία καθυστέρηση.
procedure eat(phil_id : integer);
var
rnd, i: integer;
begin
random(clock, seqtime, rnd);
for i:=1 to rnd do
delay(delay_const);
end;
Ο νιοστός φιλόσοφος ακολουθεί διαρκώς μια στερεότυπη επανάληψη. Σκέπτεται, αποφασίζει να φαει, προσπαθεί να πιάσει δύο πιρούνια, γευματίζει, αφήνει τα δύο πιρούνια και αποχωρεί. Αυτό όμως δε σημαίνει ότι όποτε προσπαθήσει να πιάσει τα πιρούνια θα τα πιάσει και θα φαει. Στην περίπτωση που πιάσει το ένα πιρούνι και το άλλο είναι ήδη κατειλημμένο ο φιλόσοφος περιμένει μέχρι το deadline. Αν αυτό περάσει τότε ο φιλόσοφος εγκαταλείπει την προσπάθεια αφήνει το πιρούνι και ξαναπροσπαθεί εκ νέου. Αυτό λοιπόν δείχνει ότι ένας φιλόσοφος μπορεί να προσπαθήσει πολλές φορές χωρίς να τα καταφέρει και ίσως να μην καταφέρει να φαει καθόλου μέχρι το τέλος του προγράμματος. Και αυτό γιατί το πρόγραμμα τρέχει για ένα συγκεκριμένο χρονικό διάστημα.
procedure a_phil(phil_id : integer; var l_req, r_req, l_free, r_free : flag_channel);
var
any, back_off : integer;
start_time : real;
begin
while clock < forever do
begin
back_off := Is_Free;
think(phil_id);
writeln('phil:',phil_id:3,' clock: ', clock:7:1,' Enter');
while not (l_free?) do
l_req := phil_id;
any := l_free;
writeln('phil ',phil_id:3,' clock: ', clock:7:1,' Left Grab');
start_time := clock;
while not (r_free?) and (back_off = Is_Free) do
begin
r_req := phil_id;
if (clock > start_time + deadline) then back_off := Is_Occupied;
end;
if (back_off = Is_Free) then
begin
any := r_free;
writeln('phil: ',phil_id:3,' clock: ', clock:7:1,' Right Grab');
eat(phil_id);
writeln('phil: ',phil_id:3,' clock: ', clock:7:1, ' Eat');
l_req := phil_id;
writeln('phil: ',phil_id:3,' clock: ', clock:7:1,' Left Put');
r_req := phil_id;
writeln('phil: ',phil_id:3,' clock: ', clock:7:1,' Right Put');
writeln('phil: ',phil_id:3,' clock: ', clock:7:1, ' Exit');
end;
end;
end;
Το κάθε πιρούνι είναι συνδεδεμένο με δύο διαφορετικούς φιλοσόφους μέσω δύο καναλιών, του left και του right. Η διεργασία του πιρουνιού διαρκώς περιμένει κάποιον από τους δύο αντίστοιχους φιλοσόφους να σηκώσει το πιρούνι. Από τη στιγμή που το πιρούνι καταληφθεί περιμένει σήμα απαλλαγής για να ξαναγίνει διαθέσιμο.
procedure a_fork(a_fork_id : integer; var l_req, r_req, l_free, r_free: flag_channel);
var
status, phil_id : integer;
begin
status := Is_Free;
while clock < forever do
begin
if (status = Is_Free) and (l_req?)then
begin
phil_id := l_req;
status := Is_Occupied;
l_free := phil_id;
end;
if status = Is_Free and ( r_req?) then
begin
phil_id := r_req;
status := Is_Occupied;
r_free := phil_id;
end;
if status = Is_Occupied and ( l_free?) then
begin
phil_id := l_req;
status := Is_Free;
end;
if status = Is_Occupied and (r_free?) then
begin
phil_id := r_req;
status := Is_Free;
end;
end;
end;
Το κυρίως πρόγραμμα :
Βegin
forall phil_id := 1 to no_of_philosophers do
begin
temp1 := (phil_id * 2);
temp2 := temp1 - 1;
temp3 := (temp1 + 1) mod no_of_hands;
fork a_phil(phil_id, request_fork[temp1],
request_fork[temp2], free_fork[temp1], free_fork[temp2]);
fork a_fork(phil_id, request_fork[temp1],
request_fork[temp3], free_fork[temp1], free_fork[temp3]);
join;
join;
end;
Εnd.
Τα αποτελέσματα της εκτέλεσης του προγράμματος για 18 φιλοσόφους έχουν την παρακάτω μορφή:
phil: 1 clock: 151.0 Enter phil: 4 clock: 193.0 Enter phil: 5 clock: 202.0 Enter phil: 8 clock: 199.0 Enter phil: 9 clock: 208.0 Enter phil: 6 clock: 226.0 Enter phil: 7 clock: 220.0 Enter phil: 3 clock: 229.0 Enter phil: 12 clock: 235.0 Enter phil: 11 clock: 241.0 Enter phil 5 clock: 257.0 Left Grab phil 9 clock: 263.0 Left Grab phil: 13 clock: 259.0 Enter phil: 15 clock: 277.0 Enter phil: 2 clock: 280.0 Enter phil 8 clock: 284.0 Left Grab phil: 14 clock: 283.0 Enter phil 6 clock: 301.0 Left Grab phil 7 clock: 305.0 Left Grab phil: 10 clock: 307.0 Enter phil 13 clock: 304.0 Left Grab phil: 18 clock: 304.0 Enter phil 12 clock: 320.0 Left Grab phil: 17 clock: 325.0 Enter phil 10 clock: 332.0 Left Grab phil: 16 clock: 331.0 Enter phil 15 clock: 342.0 Left Grab phil 14 clock: 358.0 Left Grab phil 17 clock: 360.0 Left Grab phil 16 clock: 374.0 Left Grab phil: 9 clock: 388.0 Enter phil 18 clock: 379.0 Left Grab phil: 5 clock: 397.0 Enter phil: 8 clock: 409.0 Enter phil 5 clock: 422.0 Left Grab phil 8 clock: 434.0 Left Grab phil: 13 clock: 444.0 Enter phil: 7 clock: 460.0 Enter phil: 6 clock: 471.0 Enter phil 13 clock: 469.0 Left Grab phil 7 clock: 485.0 Left Grab phil: 16 clock: 514.0 Enter phil: 7 clock: 522.0 Right Grab phil: 12 clock: 535.0 Enter phil: 14 clock: 543.0 Enter phil 16 clock: 539.0 Left Grab phil: 10 clock: 562.0 Enter phil 14 clock: 568.0 Left Grab phil: 5 clock: 577.0 Enter phil: 8 clock: 574.0 Enter phil: 15 clock: 572.0 Enter phil: 16 clock: 576.0 Right Grab phil 10 clock: 587.0 Left Grab phil: 13 clock: 594.0 Enter phil 15 clock: 597.0 Left Grab phil: 17 clock: 590.0 Enter phil: 18 clock: 594.0 Enter phil 5 clock: 602.0 Left Grab phil: 7 clock: 599.0 Eat phil 8 clock: 599.0 Left Grab phil: 14 clock: 605.0 Right Grab phil 17 clock: 615.0 Left Grab phil: 7 clock: 621.0 Left Put phil 13 clock: 619.0 Left Grab phil 18 clock: 619.0 Left Grab phil: 7 clock: 643.0 Right Put phil: 7 clock: 659.0 Exit phil: 14 clock: 697.0 Eat phil: 10 clock: 712.0 Enter phil: 14 clock: 719.0 Left Put phil 10 clock: 737.0 Left Grab phil: 14 clock: 741.0 Right Put phil: 17 clock: 740.0 Enter phil: 14 clock: 757.0 Exit phil: 16 clock: 758.0 Eat phil: 15 clock: 767.0 Enter phil: 18 clock: 759.0 Enter phil: 16 clock: 780.0 Left Put phil 15 clock: 792.0 Left Grab phil: 13 clock: 804.0 Enter phil: 16 clock: 802.0 Right Put phil: 16 clock: 818.0 Exit phil 17 clock: 825.0 Left Grab phil: 5 clock: 832.0 nter phil: 8 clock: 829.0 Enter
Εδώ βλέπουμε ότι οι φιλόσοφοι συγκρούονται με αποτέλεσμα να εγκαταλείπουν, δηλαδή να αφήνουν τα πιρούνια, και να ξαναπροσπαθούν. Μερικοί από αυτούς καταφέρνουν να φάνε. Στη συγκεκριμένη εκτέλεση είναι οι: 7,14,16. Σε κάποια άλλη εκτέλεση του προγράμματος αυτοί που θα φάνε μπορεί να είναι άλλοι ή και οι ίδιοι.
Επίσης θα ήταν καλό να προσθέσουμε ότι υπάρχουν και άλλοι τρόποι να λυθεί το πρόβλημα των φιλοσόφων. Σε διάφορες λύσεις που έχουμε βρει, είτε τα πηρούνια επικοινωνούν μεταξύ τους ειδοποιώντας το ένα το άλλο για τη κατάστασή τους-ελεύθερο ή κατειλημμένο-, είτε υπάρχει κάποιος «τρίτος», εξωτερικός παράγοντας που ρυθμίζει λίγο πολύ τα πράγματα. Η προσπάθειά μας εδώ είναι να αποφύγουμε όσο το δυνατόν τέτοιες καταστάσεις. Δηλαδή, κατά κάποιον τρόπο, οι φιλόσοφοι σε αυτή τη λύση είναι τυφλοί, και το όλο σύστημα λειτουργεί από μόνο του, χωρίς ρυθμιστικές παρεμβάσεις.
Επόμενο:ΣΥΣΤΗΜΑ ΚΕΝΤΡΙΚΗΣ ΘΕΡΜΑΝΣΗΣ Πάνω: Διάφορα Προβλήματα Παράλληλου Προγραμματισμού Πίσω: Διάφορα Προβλήματα Παράλληλου Προγραμματισμού