java:starvation_fairness

This is an old revision of the document!


A PCRE internal error occured. This might be caused by a faulty plugin

====== Παρατεταμένη στέρηση πόρων σε νήματα και ισότιμη χρήση των πόρων (Stavration) ====== ===== Παρατεταμένη στέρηση πόρων ===== Η παρατεταμένη στέρηση πόρων μπορεί να οφείλεται στους εξής λόγους: * Νήματα με αυξημένη προτεραιότητα καταναλώνουν όλο τον επεξεργαστικό χρόνο από νήματα με περιορισμένη προτεραιότητα. * Νήματα μπλοκάρονται διαρκώς από τον να μπουν μέσα σε ένα συγχρονισμένο block και να λάβουν το σχετικό lock καθώς σε άλλα νήματα καταλαμβάνουν διαρκώς τα monitor που αντιστοιχούν στους πόρους αυτούς, χωρίς να καλούν συχνά τις μεθόδους //notify()// ή //notifyAll()//. ==== Υλοποιώντας την ισότιμη χρήση των πόρων ==== Στη συνέχεια θα προσπαθήσουμε να δημιουργήσουμε μηχανισμούς που ενισχύουν την ισότιμη κατανομή των πόρων. Κατ'αρχήν ας δούμε τον παρακάτω κώδικα <code java> public class Synchronizer{ public synchronized void doSynchronized(){ //do a lot of work which takes a long time } } </code> Αν περισσότερα του ενός νήματα καλούν την μέθοδο //doSynchronized()// μόνο ένα νήμα θα μπορέσει να μπει στην μέθοδο, ενώ τα υπόλοιπα θα μπλοκάρουν μέχρι το νήμα αυτό να εξέλθει. Σε αυτή την περίπτωση η σειρά με την οποία τα νήματα θα περάσουν από τη συγχρονισμένη μέθοδο //doSynchronized()// δεν μπορεί να προβλεφθεί. ==== Χρησιμοποιώντας Locks αντί για συγχρονισμένα blocks/μεθόδους ==== Προκειμένου να αυξήουμε την αποτελεσματικότητα θα χρησιμοποιήσουμε Locks αντί για συγχρονισμένες μεθόδους και συγχρονισμένα blocks. Τα Locks χρησιμοποιούν τα εργαλεία που είδαμε μέχρι τώρα για να δημιουργήσουν πιο σύνθετους μηχανισμούς. <code java Synchronizer.java> public class Synchronizer{ Lock lock = new Lock(); public void doSynchronized() throws InterruptedException{ this.lock.lock(); //critical section, do a lot of work which takes a long time this.lock.unlock(); } } </code> Παρατηρήστε ότι η μέθοδος //doSynchronized()// δεν ορίζεται πλέον ως συγχρονισμένη. Αντίθετα, ο κώδικας που θέλουμε να προστατεύσουμε επιτρέποντας την πρόσβαση μόνο σε ένα νήμα την φορά βρίσκεται ανάμεσα στις κλήσεις //lock.lock()// και //lock.unlock()//. Μία πρώτη υλοποίηση της κλάσης Lock δίνεται παρακάτω. <code java Lock.java> public class Lock{ private boolean isLocked = false; private Thread lockingThread = null; public synchronized void lock() throws InterruptedException{ while(isLocked){ wait(); } isLocked = true; lockingThread = Thread.currentThread(); } public synchronized void unlock(){ if(this.lockingThread != Thread.currentThread()){ throw new IllegalMonitorStateException( "Calling thread has not locked this lock"); } isLocked = false; lockingThread = null; notify(); } } </code> Εάν κοιτάξετε την κλάση //Synchronizer// και δείτε παράλληλα την υλοποίηση της κλάσης //Lock// θα αντιληφθείτε ότι τα νήματα μπλοκάρουν καθώς επιχειρούν να προσπελάσουν την μέθοδο lock(), εάν περισσότερα τους ενός νήματα καλέσουν την lock() παράλληλα. Επίσης, ακόμη και εάν τα νήματα λάβουν το monitor lock του αντικειμένου που καλεί τη μέθοδο lock() και μπουν τελικά μέσα στη μέθοδο lock(), εάν η κλειδαριά έχει κλειδώσει (__isLocked=true__) τότε τα νήματα θα μπλοκάρουν μέσα στην μέθοδο //wait()//, μέχρι να κληθεί η unlock() και το lock να ελευθερωθεί. Η παραπάνω υλοποίηση της κλειδαριάς δεν μας εξασφαλίζει οποιαδήποτε ισοτιμία ως προς τη κατανομή του χρόνου εκτέλεσης των νημάτων. Η notify() είμαστε σίγουροι ότι θα ξυπνήσει ένα νήμα, αλλά δεν ξέρουμε ποιο νήμα θα είναι αυτό κάθε φορά. Παρακάτω δίνεται η υλοποίηση μίας κλειδαριάς που επιτρέπει την ισότιμη επιλογή νημάτων προς εκτέλεση μέσω ενός μηχανισμού [[wp>Round-robin_scheduling|Round-Robin]]. <WRAP important 80% round center> Όταν περιφρουρούμε ένα κρίσιμο τμήμα κώδικα με μία κλειδαριά (όπως η παραπάνω) το οποίο μπορεί να δώσει ένα ή περισσότερα Exceptions είναι σημαντικό να τοποθετούμε τη μέθοδο unlock() μέσα σε ένα finally block. Με αυτό τον τρόπο είμαστε βέβαιοι ότι ακόμη και εάν συμβεί κάποιο Exception, η κλειδαριά θα ξεκλειδώσει, ώστε να μπορέσουν άλλα νήματα να κλειδώσουν και να εκτελέσουν το κρίσιμο τμήμα του κώδικα. </WRAP> ==== Υλοποίηση Fair Lock ==== Όπως προαναφέρθηκε οι συγχρονισμένες μέθοδοι και τα συγχρονισμένα blocks δεν δίνουν καμία εγγύηση για την σειρά με την οποία θα λάβουν το lock τα νήματα που αναμένουν για αυτό. Αντίστοιχα, η wait() δεν μας δίνει καμία εγγύηση για το ποιο νήμα θα ξυπνήσει κάθε φορά. Κατά συνέπεια, η παραπάνω "κλειδαριά" δεν μας δίνει καμία εγγύηση ισοκατανομής του χρόνου εκτέλεσης των νημάτων που μπλοκάρουν σε αυτή. Η ισοκατανομή θα μπορούσε να επιτευθεί αν το κάθε νήμα περίμενε κλειδώνοντας το monitor lock ενός διαφορετικού αντικειμένου, ώστε κάθε νήμα να κλειδώνει μόνο ένα monitor lock. Σε αυτή την περίπτωση θα μπορούσαμε να χρονοπρογραμματίσουμε μέσα στον κώδικα της κλάσης Lock πιο νήμα θα τρέξει κάθε φορά. Δείτε το παρακάτω παράδειγμα. <code java QueueObject.java> public class QueueObject { private boolean isNotified = true; public synchronized void doWait() throws InterruptedException { while(!isNotified){ this.wait(); } this.isNotified = false; } public synchronized void doNotify() { this.isNotified = true; this.notify(); } public boolean equals(Object o) { return this == o; } } </code> <code java FairLock.java> public class FairLock { private boolean isLocked = false; private Thread lockingThread = null; private List<QueueObject> waitingThreads = new ArrayList<QueueObject>(); public void lock() throws InterruptedException{ QueueObject queueObject = new QueueObject(); boolean isLockedForThisThread = true; synchronized(this){ waitingThreads.add(queueObject); } while(isLockedForThisThread){ synchronized(this){ isLockedForThisThread = isLocked || waitingThreads.get(0) != queueObject; if(!isLockedForThisThread){ isLocked = true; waitingThreads.remove(queueObject); lockingThread = Thread.currentThread(); return; } } try{ queueObject.doWait(); }catch(InterruptedException e){ synchronized(this) { waitingThreads.remove(queueObject); } throw e; } } } public synchronized void unlock(){ if(this.lockingThread != Thread.currentThread()){ throw new IllegalMonitorStateException( "Calling thread has not locked this lock"); } isLocked = false; lockingThread = null; if(waitingThreads.size() > 0){ waitingThreads.get(0).doNotify(); } } } </code> Παρατηρήστε ότι μόνο ένα νήμα λαμβάνει την κλειδαριά κάθε φορά, αλλά ο χρονοπρογραμματισμός των νημάτων γίνεται με την σειρά. Όταν ένα νήμα προσπαθεί να πάρει την κλειδαριά εξυπηρετείται μόνο αν δεν υπάρχουν άλλα νήματα στην ουρά, ενώ αν υπάρχουν αυτά εξυπηρετούνται με την σειρά. Κάθε νήμα περιμένει τη σειρά του λαμβάνοντας το lock ενός διαφορετικού αντικειμένου. Με αυτόν τον τρόπο έχουμε την δυνατότητα καλώντας την notify() για το αντικείμενο για το οποίο περιμένει το κάθε νήμα, να ξυπνήσουμε μόνο το νήμα αυτό, ενώ τα υπόλοιπα κοιμούνται.

java/starvation_fairness.1429461231.txt.gz · Last modified: 2016/02/26 11:15 (external edit)