Semaphores - (προγραμμα σε C - Λειτουργικά Συστήματα)

[silot]

Καλησπέρα.

 

Θα ήθελα βοήθεια με το παρακάτω πρόβλημα το οποίο αναφέρεται σε λειτουργικά σύστήματα και έχει να κάνει με σημαφόρους και το πρόβλημα του producer - consumer. Το πρόβλημα είναι το παρακάτω:

 

Έστω ο παρακάτω ψευδοκώδικας του <<παραγωγού - καταναλωτή>>

 

#define N 100 //number of slots in the buffer

tydef int semaphore; //semaphores are a special kind of int

semaphore mutex = 1; //controls access to critical region

semaphore empty = N; //counts empty buffer slots

semaphore full = 0; //counts full buffer slots

 

void producer(void)

{

int item;

 

while (true){ //true is the constant 1

item = produce_item(); //generate something to put in buffer

down(&empty); //decrement empty count

down(&mutex); //enter critical region

insert_item(item); //put new item in buffer

up(&mutex); //leave critical region

up(&full);} //increment count of full slots

}

 

 

void consumer(void)

{

int item;

 

while (true){ //infinite loop

 

down(&full); //decrement full count

down(&mutex); //enter critical region

item = remove_item(); //take item from buffer

up(&mutex); //leave critical region

up(&full); //increment count of full slots

consume_item(item); } //do something with the item

}

 

Αναφέρετε αναλυτικά το τι θα συμβεί εάν αντιστρέψουμε την σειρά των 2 εντολών

down() του producer, δηλαδή από:

 

down(&empty);

down(&mutex);

 

σε

 

down(&mutex);

down(&empty);

 

Οποιαδήποτε βοήθεια θα ήταν ευπρόσδεκτη

 

Ευχαριστώ

[eirinikp]

void consumer(void)

{

int item;

 

while (true){ //infinite loop

 

down(&full); //decrement full count

down(&mutex); //enter critical region

item = remove_item(); //take item from buffer

up(&mutex); //leave critical region

up(&full); //increment count of full slots

consume_item(item); } //do something with the item

}

Μήπως ο consumer κάνει up(&empty); αντί για up(&full); ?

Αν είναι σωστή η διόρθωσή μου τότε έχουμε τα εξής:

Προφανώς κάθε φορά που κάποιος θέλει να μπει στην κρίσιμη περιοχή κατεβάζει τον mutex. Αν ο παραγωγός πρώτα κατεβάσει τον mutex και μετά ο empty δεν είναι έτοιμος, τότε μπορεί να κολλήσει για πάντα εκεί διότι θα περιμένει από τον consumer να ανεβάσει τον empty. Όμως ο consumer δε θα μπορεί να το κάνει, γιατί ο producer θα έχει κατεβάσει τον mutex...

[MINDoSOFT]

/*Καλησπέρα! (Αφού τα έγραψα αυτά κατάλαβα οτι λέω το ίδιο πράγμα με την eirinikp οπότε συμφωνώ με αυτά που λέει)

 

Καταρχάς το σωστό πρόγραμμα είναι έτσι */

 

#define N 100 //number of slots in the buffer

tydef int semaphore; //semaphores are a special kind of int

semaphore mutex = 1; //controls access to critical region

semaphore empty = N; //counts empty buffer slots

semaphore full = 0; //counts full buffer slots

 

void producer(void)

{

int item;

 

while (true){ //true is the constant 1

item = produce_item(); //generate something to put in buffer

down(&empty); //decrement empty count

down(&mutex); //enter critical region

insert_item(item); //put new item in buffer

up(&mutex); //leave critical region

up(&full);} //increment count of full slots

}

 

 

void consumer(void)

{

int item;

 

while (true){ //infinite loop

 

down(&full); //decrement full count

down(&mutex); //enter critical region

item = remove_item(); //take item from buffer

up(&mutex); //leave critical region

up(&empty); //increment count of empty slots <--------Εδώ είχε λάθος ο κώδικας

consume_item(item); } //do something with the item

}

 

/* Και εξηγώ γιατί είναι σωστό έτσι...

Ο empty μετρά τις άδειες θέσεις και ο full τις γεμάτες.

Ο empty χρησιμεύει ώστε να μην πάει να εισάγει και άλλο αντικείμενο ο producer στον buffer όταν αυτός είναι γεμάτος (δεν έχει άδειες θέσεις, empty=0)

O full χρησιμεύει ώστε να μην πάει να τραβήξει αντικείμενο ο consumer όταν είναι άδειος ο buffer (καμία θέση γεμάτη, full=0)

 

Αν η σειρά των down() του producer ήταν

down(&mutex); //enter critical region

down(&empty); //decrement empty count

τότε θα μπορούσε να συμβεί deadlock. Πώς;

Ο producer θα κλείδωνε τον mutex σηματοφόρο και μετά θα γινόταν blocked στον empty σηματοφόρο (γιατί γεμίσανε όλες οι θέσεις του buffer, empty=0). Έστω οτι ο consumer πάει να κατεβάσει τον σηματοφόρο full και έστω οτι τα καταφέρνει δεν θα μπορέσει να περάσει ποτέ από το block του σηματοφόρου mutex οπότε ο empty δεν θα γίνει ποτέ up (σύμφωνα με τον σωστό κώδικα) οπότε έχουμε deadlock.

 

Εύχομαι να βοήθησα να ξεκαθαρίσει κάπως το θέμα!

Αν θες κάτι ρώτα*/

[eirinikp]

/*Καλησπέρα! (Αφού τα έγραψα αυτά κατάλαβα οτι λέω το ίδιο πράγμα με την eirinikp οπότε συμφωνώ με αυτά που λέει)

Δεν πειράζει που λες τα ίδια, γιατί τα εξήγησες πολύ καλύτερα!