Αρχική ΑΕΠΠ - Δομές Δεδομένων Λειτουργικά Συστήματα Δίκτυα Υπολογιστών ΙΙ Βάσεις Δεδομένων Παιδαγωγικά - Διδακτική

Εισαγωγικά

Εισαγωγή στα Λ.Σ. Βασικές Δομές Η/Υ Βασικές Δομές Λ.Σ

Διεργασίες

Διεργασίες Χρονοπρογραμματισμός Συγχρονισμός

Σημαφόροι
Κλασσικά Προβλήματα
Όχι και τόσο Κλασσικά Προβλήματα

Αδιέξοδα

Μνήμη

Μονοπρογραμματισμός Εναλλαγή Εικονική Μνήμη Κατάτμηση

Είσοδος / Έξοδος

Σύστημα Αρχείων

Διεπαφή Υλοποίηση 

 Ιστορικό Πρόσφατες αλλαγές Εκτύπωση Αναζήτηση

Αναγνώστες - Εγγραφείς

The R-W problem is another classic problem for which design of synchronization and concurrency mechanisms can be tested.

  • There is a data area that is shared among a number of processes.
  • Any number of readers may simultaneously write to the data area.
  • Only one writer at a time may write to the data area.
  • If a writer is writing to the data area, no reader may read it.
  • If there is at least one reader reading the data area, no writer may write to it.
  • Readers only read and writers only write
  • A process that reads and writes to a data area must be considered a writer (consider producer or consumer)

Semaphore Solution: Readers have Priority

int readcount = 0;
semaphore wsem = 1; //
semaphore x = 1; //

void reader(){
   while(1){
      wait(x);
        readcount++;
        if (readcount==1)
             wait(wsem);
      signal(x);
      doReading();
      wait(x);
        readcount--;
        if (readcount==0)
             signal(wsem);
      signal(x);
   }
}

void writer(){
  while(1){
      wait(wsem);
      doWriting();
      signal(wsem);
   }
}
[Get Code]

Once readers have gained control, a flow of reader processes could starve the writer processes.

Προτεραιότητα στου Αναγνώστες - Αποφυγή Λιμοκτονίας Εγγραφέων

Η λύση είναι όμοια με εκείνη που δίνει προτεραιότητα στους αναγνώστες. Προσθέτουμε ένα σημαφόρο (writerQueue) στον οποίο θα αναστέλλονται οι εγγραφείς. Αν υπάρχουν εγγραφείς σ' αυτήν την ουρά, τότε οι αναγνώστες που φτάνουν θα πρέπει να ανασταλούν, έτσι θα ολοκληρώσουν όσοι είναι στη βάση και θα αφήσουν την κρίσιμη περιοχή ελεύθερη σε έναν εγγραφέα. Οι δύο διεργασίες δίνονται παρακάτω.

  1. typedef int semaphore;
  2.  
  3. int rc = 0;
  4. semaphore mutex, writersQueue, db;
  5. mutex = writersQueue = db = 1;
  6.  
  7. void reader(void) {
  8.   down(&writersQueue);  /* Αν υπάρχει writer που περιμένει η reader αναστέλλεται */
  9.   up(&writersQueue);    /* Κάνει ξανά την writersQueue 1 */
  10.  
  11.   down(&mutex);         /* Αποκλειστική πρόσβαση στην rc */
  12.   rc++;                 /* Ένας ακόμη reader */
  13.   if (rc==1) down(&db); /* Ο πρώτος προσπαθεί να πάρει αποκλειστική πρόσβαση */
  14.   up(&mutex);           /* Ελεύθερη πρόσβαση στην rc */
  15.  
  16.   read_data_base();     /* κρίσιμο τμήμα */
  17.  
  18.   down(&mutex);         /* Αποκλειστική πρόσβαση στην rc */
  19.   rc--;                 /* Ένας reader λιγότερος */
  20.   if (rc==0) up(&db);   /* Αν είναι ο τελευταίος ελευθερώνει την ουρά στον db */
  21.   up(&mutex);           /* Ελεύθερη πρόσβαση στην rc */
  22.  
  23.   use_data_read();      /* μη κρίσιμο τμήμα */
  24. }
  25.  
  26. void writer(void) {
  27.   down(&writersQueue);  /* Ένας writer στην ουρά. Αν υπάρχουν άλλοι αναστέλλεται */
  28.   down(&db);            /* Αποκλειστική πρόσβαση */
  29.  
  30.   write_data_base();    /* Κρίσιμο τμήμα */
  31.  
  32.   up(&writersQueue);    /* Απελευθέρωσε έναν writer ή reader από την ουρά */
  33.   up(&db);              /* Ελεύθερη πρόσβαση */
  34. }
[Get Code]

Αν ξεκινήσει ένας 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 θα μπει στο κρίσιμο τμήμα του.

Semaphore Solution: Writers have Priority

Θα χρησιμοποιήσουμε δύο μεταβλητές rc και wc που μετράνε αντίστοιχα τους αναγνώστες και τους εγγραφείς που είναι στα κρίσιμα τμήματά τους. Οι σημαφόροι rc_mutex και wc_mutex χρησιμοποιούνται για την αποκλειστική πρόσβαση στις μεταβλητές rc και wc αντίστοιχα. Ο σημαφόρος readersQueue χρησιμοποιείται ώστε να δημιουργηθεί μία ουρά αναγνωστών, όταν οι εγγραφείς προσπαθούν να μπουν στο κρίσιμο τμήμα τους. Όταν readersQueue είναι 1 δεν υπάρχει διεργασία στην ουρά. Διαφορετικά οι διεργασίες αναστέλλονται και δημιουργούν ουρά. Ο σημαφόρος db ελέγχει την πρόσβαση στο κρίσιμο τμήμα της κάθε διεργασίας.

  1. typedef int semaphore;
  2.  
  3. int rc, wc;
  4. rc = wc = 0;
  5.  
  6. semaphore rc_mutex, wc_mutex, readersQueue, db
  7. rc_mutex = wc_mutex = readersQueue = db = 1;
  8.  
  9. void reader(void) {
  10.   down(&readersQueue);
  11.  
  12.   down(&rc_mutex);
  13.   rc++;
  14.   if (rc==1) down(&db);
  15.   up(&rc_mutex);
  16.  
  17.   up(&readersQueue);
  18.  
  19.   read_db();  /* κρίσιμο τμήμα */
  20.  
  21.   down(&rc_mutex);
  22.   rc--;
  23.   if (rc==0) up(&db);
  24.   up(&rc_mutex);
  25. }
  26.  
  27. void writer(void) {
  28.   down(&wc_mutex);
  29.   wc++;
  30.   if (wc==1) down(&readersQueue);
  31.   up(&wc_mutex);
  32.  
  33.   down(&db);
  34.   write_db();
  35.   up(&db);
  36.  
  37.   down(&wc_mutex);
  38.   wc--;
  39.   if (wc==0) up(&readersQueue);
  40.   up(&wc_mutex);
  41. }
[Get Code]

Αν ένας αναγνώστης φτάσει στο κρίσιμο τμήμα του έχει κάνει down τον db (γραμμή 11) αλλά όχι τον readersQueue (γραμμή 17). Έτσι, αν φτάσει ένας αναγνώστης μπορεί να κάνει down τον readersQueue. Αυτό θα κάνει όσους αναγνώστες φτάνουν να αναστέλλονται στη γραμμή 10. Όταν ο τελευταίος αναγνώστης βγει από το κρίσιμο τμήμα του θα κάνει up τον db (γραμμή 23) το οποίο ελευθερώνει τους εγγραφείς που έχουν ανασταλεί.

Αν ένας εγγραφέας είναι στο κρίσιμο τμήμα του, έχει κάνει down τόσο τον readersQueue, όσο και τον db. Αυτό έχει το αποτέλεσμα ότι ούτε άλλος εγγραφέας ούτε αναγνώστης μπορεί να μπει στο κρίσιμο τμήμα του. Επίσης, όσοι εγγραφείς φτάνουν αυξάνουν την μεταβλητή wc και περιμένουν στον readersQueue. Αυτό σημαίνει ότι όσο φτάνουν εγγραφείς, ένας ένας θα μπαίνουν στο κρίσιμο τμήμα τους και οι αναγνώστες θα περιμένουν. Μόνο ο τελευταίος εγγραφέας θα κάνει up τον readersQueue και θα μπορούν να προχωρήσουν οι αναγνώστες.

Εδώ μπορεί να παρατηρηθεί το αντίστοιχο φαινόμενο με την προτεραιότητα στους αναγνώστες, δηλαδή, ότι οι αναγνώστες μπορεί να λιμοκτονούν ή τουλάχιστον να υφίστανται μεγάλες καθυστερήσεις.

Τελευταία ενημέρωση: 04-09-2008 (20:25)

Copyright 2008 - Άρης Φεργάδης