Σημαφοροι(Λειτουργικα συστηματα)

[Blame_the_butcher]

Καλησπερα παιδια, δεν ξερω αν ειμαι στη σωστη κατηγορια , αλλα εχω ενα προβλημα σχετικα με σημαφορους και ηθελα αν καποιος γνωριζει να με βοηθουσε στην επιλυση του ..
 

Δύο φίλοι πηγαίνουν για ψάρεμα με μια βάρκα. Καθένας από τους δύο κάνει τα εξής: περπατά μέχρι την αποβάθρα αν ο άλλος δεν είναι ήδη εκεί τον περιμένει, μπαίνει στη βάρκα και φεύγουν μαζί. Δώστε μια λύση στο πρόβλημα χρησιμοποιώντας σημαφόρους.

 

αυτο ειναι το προβλημα.. δεν θελει κωδικα , απλα θεωρητικη επιλυση χρησιμοποιωντας σημαφορους

[Kostas93]

αρχικοποιείς τον σημαφόρο στο 2 και μόλις παει ο καθε ένα το μειώνεις κατά 1 καθε φορά.
έτσι, μόλις έρθει και ο δεύτερος ο σημαφόρος θα είναι 0 και θα μπει στο κρίσιμο σημείο. όσο θα λείπει έστω ένας απο τους δύο δε θα μπορεί να μπει.

[Blame_the_butcher]

Μονο εναν σημαφορο χρησιμοποιω?? μηπως μπορω να  σου γραψω και αλλο ενα προβλημα που προσπαθω να καταλαβω πως δουλευει? Ευχαριστω πολυ για την γρηγορη απαντηση.

[Kostas93]

γράψε ότι θέλεις, αν μπορώ να σε βοηθήσω θα το κάνω, αν δε μπορώ θα το κάνει κάποιος άλλος.

απο λειτουργικά γενικα τι ξέρεις? mutex/semaphores κτλ?
 

Ο σημαφόρος είναι ένας ακέραιος αριθμός στον οποίο επιτρέπεται η πρόσβαση μόνο με τρεις αυστηρά ορισμένες λειτουργίες:

αρχικοποίηση

wait

signal

Αρχικοποιείται σε μία ακέραιη τιμή. Μετά την αρχικοποίηση επιτρέπονται μόνο η wait() και η signal()

 

wait() : Αν ο σημαφόρος είναι <= 0, η διεργασία περιμένει ("κολλάει"). Αν είναι > 0 ο σημαφόρος μειώνεται κατά 1 και η διεργασία συνεχίζει την εκτέλεσή της.

 

signal() : Ο σημαφόρος αυξάνεται κατά 1.

οπότε μάλλον στο είπα ανάποδα, πρέπει να το αρχικοποιήσεις σε αρνητικό και να κάνει signal κάθε φορά η διεργασία (άνθρωπος) που έρχεται.

[Blame_the_butcher]

Άσκηση 2

Ένα κουρείο αποτελείται από μία αίθουσα αναμονής με n καρέκλες και ένα δωμάτιο κουρέματος με μία καρέκλα. Αν δεν υπάρχουν πελάτες να εξυπηρετηθούν, ο κουρέας αποκοιμάται. Αν ένας πελάτης μπει στο κουρείο και βρει όλες τι καρέκλες κατειλημμένες, φεύγει από το κουρείο. Αν ο κουρέας είναι απασχολημένος αλλά υπάρχουν διαθέσιμες καρέκλες, τότε ο πελάτης κάθεται σε μία από τις ελεύθερες καρέκλες. Αν ο κουρέας κοιμάται, ο πελάτης ξυπνάει τον κουρέα. Χωρίς απαραίτητα να γράψετε  πρόγραμμα που θα συντονίζει τον κουρέα και τους πελάτες, αναφέρετε με ποιο τρόπο μπορείτε να χρησιμοποιήσετε σημαφόρους για να αντιμετωπίσετε το πρόβλημα.

Άσκηση 3

Οι εξυπηρετητές μπορούν να σχεδιαστούν έτσι ώστε να περιορίζεται το πλήθος των ανοικτών συνδέσεων. Για παράδειγμα, ένας εξυπηρετητής μπορεί να επιθυμεί να έχει μόνο N συνδέσεις υποδοχών (socket connections) κάθε χρονική στιγμή. Μόλις γίνουν N συνδέσεις, ο εξυπηρετητής δεν θα δεχθεί άλλη εισερχόμενη σύνδεση μέχρι να αποδεσμευτεί μία υπάρχουσα σύνδεση. Εξηγήστε πως μπορούν να χρησιμοποιηθούν οι σημαφόροι από έναν εξυπηρετητή για τον περιορισμό του πλήθους των ταυτόχρονων συνδέσεων.

 

αυτα ειναι.. δν ξερω πολλα απλα δινω το μαθημα και προσπαθω να διαβασω και μου φαινεται αρκετα δυσκολο .. χρονοπρογραμματισμο , σφαλματα σελιδας κτλπ

[Kostas93]

λοιπόν, σκέφτηκα λίγο καλύτερα το πρώτο πρόβλημα σου.

Αν χρησιμοποιήσεις 2 σεμαφόρους μπορεί να κάνει ο ένας signal τον άλλο.
Δηλαδή έχει τον σεμαφόρο p1 και τον p2 αρχικοποιημένους στο 0.
Ας πούμε πως έρχεται πρώτος ο 2. Θα κάνει signal τον p1 και η τιμή του θα γίνει 1. Παράλληλα αυτός θα περιμένει (wait) επειδή το p2 είναι 0.
Μόλις έρθει ο 1, θα μπει στη βάρκα καθώς θα έχει τιμή 1 ο σεμαφόρος του και θα περάσει απο το δικό του wait και θα κάνει signal στον P2 έτσι ώστε και αυτός να γίνει 1 και να μπει στη βάρκα.

Αντίστοιχα αν γίνει το ανάποδο.
Αυτή πιστεύω ειναι και η πιο σωστή λύση, οπότε ξέχνα τα παραπάνω.

Άσκηση 2

Ένα κουρείο αποτελείται από μία αίθουσα αναμονής με n καρέκλες οπότε θες ενα σεμαφορο αρχικοποιημένο στο n και κάθε φορά που μπαίνει ένας μέσα θα μειώνεται κατά 1, έτσι εξασφαλίζεις ότι θα μπουν μόνο n άτομα όσα και οι καρέκλες, επίσης κάθε φορά που φεύγει ένας κανει signal και αυξάνει ο σεμαφόρος, έτσι ώστε να μπορεί να μπει κάποιος που πιθανότατα λόγο του wait δε μπορούσε να μπει πριν. και ένα δωμάτιο κουρέματος με μία καρέκλα. Αν δεν υπάρχουν πελάτες να εξυπηρετηθούν, ο κουρέας αποκοιμάται αν ο σεμαφορος ειναι n, δηλαδή δεν ειναι κανένας μέσα δίνεις signal sleep στον κουρέα . Αν ένας πελάτης μπει στο κουρείο και βρει όλες τι καρέκλες κατειλημμένες, φεύγει από το κουρείο (αυτό εξασφαλίστηκε με τον σεμαφόρο πάνω, όταν παει να μπει, ο σεμαφόρος θα ειναι 0 και θα κολήσει στο wait,συνεπώς δε θα μπορεί να μπει). Αν ο κουρέας είναι απασχολημένος αλλά υπάρχουν διαθέσιμες καρέκλες, τότε ο πελάτης κάθεται σε μία από τις ελεύθερες καρέκλες. Αν ο κουρέας κοιμάται, ο πελάτης ξυπνάει τον κουρέα(λογικά αυτό ειναι ένα while που ελέγχει συνέχεια τον σεμαφόρο και δίνει signal για sleep για πάρα πολύ λίγο όμως, συνεπώς αυτό τρέχει ατέρμονα μέχρι να μπει κάποιος, να μειωθεί ο σεμαφόρος και να βγει απο το while (ξυπνήσει) ο κουρέας) Χωρίς απαραίτητα να γράψετε  πρόγραμμα που θα συντονίζει τον κουρέα και τους πελάτες, αναφέρετε με ποιο τρόπο μπορείτε να χρησιμοποιήσετε σημαφόρους για να αντιμετωπίσετε το πρόβλημα.

Υ.Γ. αν θες να αντιμετωπίσεις και το αν δουλεύει ή όχι ενώ έχει κόσμο μπορεις να βάλεις έναν σεμαφόρο για τον κουρέα στο 1, όταν έρχεται ένας πελάτης μπαίνει στο δωμάτιο και ο σεμαφόρος γίνεται 0, άρα δε μπορει΄να μπει και δεύτερος. μόλις φύγει ο πελάτης κανει signal και ο σεμαφόρος ξαναγίνεται 1, άρα μπαινει ο επόμενος.
Το πως θα εξασφαλίσεις να μπουν με τη σειρά που ήρθαν είναι άλλη υπόθεση, αλλά όπως βλέπω δε σε απασχολεί στο πρόβλημα
Με αυτό το τρόπο δε χρειάζεσαι και το while, απλά ελέγχεις τον σεμαφόρο του κουρέα. όσο είναι 1 μπορει να κοιμάται.

[Blame_the_butcher]

Ευχαριστε αδερφε , αρκετα αναλυτικη η απαντηση σου , το καταλαβα καλυτερα το 1ο προβλημα

[Kostas93]

Άσκηση 3

Οι εξυπηρετητές μπορούν να σχεδιαστούν έτσι ώστε να περιορίζεται το πλήθος των ανοικτών συνδέσεων. Για παράδειγμα, ένας εξυπηρετητής μπορεί να επιθυμεί να έχει μόνο N συνδέσεις υποδοχών (socket connections) κάθε χρονική στιγμή. Μόλις γίνουν N συνδέσεις, ο εξυπηρετητής δεν θα δεχθεί άλλη εισερχόμενη σύνδεση μέχρι να αποδεσμευτεί μία υπάρχουσα σύνδεση. Εξηγήστε πως μπορούν να χρησιμοποιηθούν οι σημαφόροι από έναν εξυπηρετητή για τον περιορισμό του πλήθους των ταυτόχρονων συνδέσεων.

Και εδώ βασιζεσαι στις 3 λειτουργίες του σεμαφόρου.

Τον αρχικοποιείς ίσο με n, και κάθε φορά που γίνεται μια σύνδεση (περνάει απο το wait δηλαδή) μειώνεται ο σεμαφορος κατά 1. Μόλις ο σεμαφόρος γίνει 0 δε μπορει να γίνει άλλη σύνδεση (θα κολλήσει στο wait). Μόλις κάποιος πάει να κλείσει τη σύνδεση κάνει signal και αυξάνει τον σεμαφόρο, συνεπώς θα "ξεκολλήσει" κάποια άλλη σύνδεση απο το wait και θα μπει αυτή, θα μειωθεί και πάλι ο σεμαφορος και δε θα μπουν παραπάνω συνδέσεις ταυτόχρονα.

 

σε ποια σχολή είσαι?

χρονοπρογραμματισμο που λες εννοεις round-robin/first come first served, shortest job first κτλ?

Αν είναι να σου στείλω τις διαφάνεις απο τη σχολή μου, μήπως και σε βοηθήσουν λίγο.

[Blame_the_butcher]

σε ποια σχολή είσαι?

χρονοπρογραμματισμο που λες εννοεις round-robin/first come first served, shortest job first κτλ?

Αν είναι να σου στείλω τις διαφάνεις απο τη σχολή μου, μήπως και σε βοηθήσουν λίγο.

 

Στο τει λαμιας πληροφορικη ειμαι .. ναι αυτα εννοω ..αν και τα χω καταλαβει τα συγκεκριμενα δν θα με χαλαγαν και παραπανω σημειωσεις Btw εισαι τεραστιος , νομιζω πως το ενιωσα το θεμα με τους σημαφορους

[Kostas93]

δεν είναι και πολύ αναλυτικές, και έχουν αρκετό κώδικα μέσα, αλλά ότι πάρεις απο αυτές καλό είναι
http://www.cslab.ntua.gr/courses/os/files/2014-15/os-03-synchronization.pdf
http://www.cslab.ntua.gr/courses/os/files/2014-15/os-04-scheduling.pdf

 

mutex αν εχετε, είναι σεμαφορος αρχικοποιημένος στο 1. (αν σε βοηθάει να το σκέφτεσαι έτσι).

[Blame_the_butcher]

αδερφε κατι που παρατηρησα στην ασκηση 1 με τις βαρκες ... οτι μας ενδιαφερει ο τροπος με τον οποιο πανε οι φιλοι μεχρι την προβλητα.. νομιζω οτι ετσι οπως το λυσες προυποθετει ο ενας να βρισκεται ηδη εκει .. η κανω λαθος ??

[Kostas93]

αν το κοιτάξεις με τους 2 σημαφόρους, τότε όχι. (η λύση με έναν δε δουλεύει).

Αρχικοποιείς 2 σημαφόρους στο 0.

Η προβλήτα είναι το wait σου. Για να περάσει καποιος πρέπει να έχει σημαφόρο ίσο με 1.
Αν πάει ο Α πρώτος, θα έχει σημαφόρο ίσο με 0, άρα θα μείνει στη προβλήμα, αλλά θα κάνει signal τον σημαφόρο του Β, άρα ο σημαφορος του Β θα γίνει 1. Όση ώρα και να περάσει αυτό δεν αλλάζει. Μόνο όταν ο Β φτάσει, θα κάνει signal τον Α, και θα περάσει ο καθένας τους απο το wait του (είναι δύο διαφορετικά wait, σκέψου τα σαν wait(A) και wait( B ) και θα μπουν στη βάρκα.

Ακόμη και αν έρθει ο Β πρώτος η διαδικασία είναι ίδια.

Σε ψευτοκώδικα είναι κάπως έτσι,

A=B=0  ;αρχικα σημαφόροι ίσοι με 0

κώδικας Α                          Κώδικα Β
.                                          .

.                                          .

.                                          .
signal ( B )                          signal (A)     ;αυξάνει κατά 1 την εκάστοτε μεταβλητή
τέλος κώδικα Α                   τέλος κώδικα Β

 

Κώδικας Βάρκας (κοινός κωδικας)
wait (A)           ;μπαινει ο Α και το Α γίνεται 0

wait ( B )          ;μπαίνει ο Β και το Β γίνεται 0
.

.

.

Τέλος κώδικα Βάρκας.
 

Τα δύο κομμάτια (αυτά που είναι δίπλα δίπλα) ψευτοκώδικα που είναι πάνω είτε εκτελεστούν παράλληλα είτε σειριακά δε σε πειράζει, Για να μπουν και οι δύο στη βάρκα θα πρέπει να περάσουν ο καθένας το wait του, συνεπώς θα κολλήσουν πριν τις ... όπου είναι και το κομμάτι που σε ενδιαφέρει και πρέπει να μπουν μαζί.


Υπάρχει πολύ πιο έξυπνος τρόπος να γίνει με fences κτλ αλλά δε νομίζω να τα έχετε διδαχτεί αυτά.

[zisis13]

Βλεπω ο Αντωνής έχει βγαλει τον κοσμο στα forums

[Sirodeath]

Βλεπω ο Αντωνής έχει βγαλει τον κοσμο στα forums

Χαχαχα αυτο σκευτηκα κ εγω

[Kostas93]

είσαστε όλοι απο την ίδια σχολή;