Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική
Εισαγωγή στα Λ.Σ. Βασικές Δομές Η/Υ Βασικές Δομές Λ.Σ
Διεργασίες Χρονοπρογραμματισμός Συγχρονισμός
Μονοπρογραμματισμός Εναλλαγή Εικονική Μνήμη Κατάτμηση
The R-W problem is another classic problem for which design of synchronization and concurrency mechanisms can be tested.
Once readers have gained control, a flow of reader processes could starve the writer processes.
Η λύση είναι όμοια με εκείνη που δίνει προτεραιότητα στους αναγνώστες. Προσθέτουμε ένα σημαφόρο (writerQueue) στον οποίο θα αναστέλλονται οι εγγραφείς. Αν υπάρχουν εγγραφείς σ' αυτήν την ουρά, τότε οι αναγνώστες που φτάνουν θα πρέπει να ανασταλούν, έτσι θα ολοκληρώσουν όσοι είναι στη βάση και θα αφήσουν την κρίσιμη περιοχή ελεύθερη σε έναν εγγραφέα. Οι δύο διεργασίες δίνονται παρακάτω.
Αν ξεκινήσει ένας writer, ο σημαφόρος writerQueue γίνεται 0 στην γραμμή 27. Αν έρθει writer θα ανασταλεί στην 27, ενώ αν έρθει reader θα ανασταλεί στην γραμμή 8. Ο writer θα μπει στο κρίσιμο τμήμα του και θα ελευθερώσει την ουρά στον writerQueue. Ο χρονοδρομολογητής μπορεί να επιλέξει μια διεργασία reader ή writer. Αν ξεκινήσει ένας reader, δεν θα ανασταλεί στην γραμμή 8. Ας υποθέσουμε ότι έχει μπει και στο κρίσιμο τμήμα του. Αν έρθει ένας ακόμη reader μπορεί να μπει στο κρίσιμο τμήμα του. Αν έρθει ένας writer θα μειώσει τον writerQueue και θα ανασταλεί στη γραμή 29. Τώρα, αν έρθει reader θα ανασταλεί στην 8 και αν έρθει writer θα ανασταλεί στην 27. Έτσι, όταν ολοκληρώσουν οι reader που είναι στα κρίσιμα τμήματά τους, τότε ο writer που είχε ανασταλεί στην 29 θα μπει στο κρίσιμο τμήμα του.
Θα χρησιμοποιήσουμε δύο μεταβλητές rc και wc που μετράνε αντίστοιχα τους αναγνώστες και τους εγγραφείς που είναι στα κρίσιμα τμήματά τους. Οι σημαφόροι rc_mutex και wc_mutex χρησιμοποιούνται για την αποκλειστική πρόσβαση στις μεταβλητές rc και wc αντίστοιχα. Ο σημαφόρος readersQueue χρησιμοποιείται ώστε να δημιουργηθεί μία ουρά αναγνωστών, όταν οι εγγραφείς προσπαθούν να μπουν στο κρίσιμο τμήμα τους. Όταν readersQueue είναι 1 δεν υπάρχει διεργασία στην ουρά. Διαφορετικά οι διεργασίες αναστέλλονται και δημιουργούν ουρά. Ο σημαφόρος db ελέγχει την πρόσβαση στο κρίσιμο τμήμα της κάθε διεργασίας.
Αν ένας αναγνώστης φτάσει στο κρίσιμο τμήμα του έχει κάνει down τον db (γραμμή 11) αλλά όχι τον readersQueue (γραμμή 17). Έτσι, αν φτάσει ένας αναγνώστης μπορεί να κάνει down τον readersQueue. Αυτό θα κάνει όσους αναγνώστες φτάνουν να αναστέλλονται στη γραμμή 10. Όταν ο τελευταίος αναγνώστης βγει από το κρίσιμο τμήμα του θα κάνει up τον db (γραμμή 23) το οποίο ελευθερώνει τους εγγραφείς που έχουν ανασταλεί.
Αν ένας εγγραφέας είναι στο κρίσιμο τμήμα του, έχει κάνει down τόσο τον readersQueue, όσο και τον db. Αυτό έχει το αποτέλεσμα ότι ούτε άλλος εγγραφέας ούτε αναγνώστης μπορεί να μπει στο κρίσιμο τμήμα του. Επίσης, όσοι εγγραφείς φτάνουν αυξάνουν την μεταβλητή wc και περιμένουν στον readersQueue. Αυτό σημαίνει ότι όσο φτάνουν εγγραφείς, ένας ένας θα μπαίνουν στο κρίσιμο τμήμα τους και οι αναγνώστες θα περιμένουν. Μόνο ο τελευταίος εγγραφέας θα κάνει up τον readersQueue και θα μπορούν να προχωρήσουν οι αναγνώστες.
Εδώ μπορεί να παρατηρηθεί το αντίστοιχο φαινόμενο με την προτεραιότητα στους αναγνώστες, δηλαδή, ότι οι αναγνώστες μπορεί να λιμοκτονούν ή τουλάχιστον να υφίστανται μεγάλες καθυστερήσεις.
Copyright 2008 - Άρης Φεργάδης