C ++ σηματοφόρο (ημι * lockfree *), πού μπορώ να πάρω ένα;

ψήφοι
0

edit: αυτό δεν είναι ένα αντίγραφο από κάθε ερώτηση που επιτρέπει κλείδωμα mutex στη θέση (). Παρακαλούμε διαβάστε προσεκτικά, χρειάζομαι μια θέση lockfree ()! Μην το σήμα αυτό διπλούν, αν δεν έχετε μια πραγματική απάντηση.

Μια σηματοφόρων (όπως και σε linux) είναι ένα χρήσιμο στοιχείο για την οικοδόμηση που δεν βρίσκεται στο πρότυπο ++ γ, και ούτε στην ώθηση (προς το παρόν). Είμαι κατά κύριο λόγο μιλάμε για σηματοφορείς μεταξύ των νημάτων μιας ενιαίας διαδικασίας, κατά τη διάρκεια μιας προτίμησης χρονοδιάγραμμα.

Είμαι ενδιαφέρονται ειδικά σε αυτές που είναι μη αποκλεισμού (δηλαδή lockfree), εκτός αν πρέπει πραγματικά να μπλοκάρει. Δηλαδή, μια θέση () και try_wait () θα πρέπει να είναι πάντα lockfree. Και περιμένετε () κλήσεις θα πρέπει να lockfree αν επικλήσεις τους έντονα-συμβεί-μετά από αρκετά μετά () s έχουν επιστρέψει. Επίσης αναμονής αποκλεισμού () θα πρέπει να αποκλειστεί από τον προγραμματιστή και όχι γύρισμα κλειδωμένο. Τι γίνεται αν θέλω επίσης ένα wait_for με χρονικό όριο - πόσο δεν θα περιπλέξει ακόμη περισσότερο την εφαρμογή, ενώ ακόμα αποφεύγοντας την πείνα;

Οι λόγοι για τους οποίους σηματοφορείς δεν είναι στο πρότυπο εκεί;

Edit3: Λοιπόν, εγώ δεν γνώριζε ότι υπάρχει μια πρόταση με το πρότυπο P0514R4 ότι ακριβώς ασχολείται με αυτά τα θέματα, και έχει λύσεις για όλα τα προβλήματα που τέθηκαν εδώ, εκτός από συγκεκριμένα την προσθήκη ενός std :: σηματοφόρο. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0514r4.pdf

Επίσης, την ενίσχυση δεν έχει αυτά. Συγκεκριμένα, αυτοί στην ενδοεπικοινωνία είναι γύρισμα κλειδωμένο.

Ποιες βιβλιοθήκες υποστηρίζουν κάτι τέτοιο;

Είναι δυνατόν να το εφαρμόσει πάνω API των Windows και άλλα διαδεδομένα συστήματα;

edit: Δεν είναι δυνατή η εφαρμογή της εν λόγω lockfree χρησιμοποιώντας Atomics + mutex + condition_variable - θα πρέπει είτε να μπλοκάρουν σε θέση ή περιστροφή σε αναμονή. Αν θέλετε μια θέση lockfree (), δεν μπορείτε να κλειδώσετε ένα mutex στη θέση (). Θέλω να τρέξω σε μια ενδεχομένως προτίμησης χρονοδιάγραμμα, και δεν θέλω μετά () μπλοκαριστεί από άλλα θέματα που πήρε το mutex και πήρε προκαταλαμβάνεται. Έτσι, αυτό είναι όχι ένα αντίγραφο των ερωτήσεων όπως C ++ 0x δεν έχει σηματοφορείς; Πώς να συγχρονίσετε τα θέματα;

edit2: Μετά από εκτέλεση παράδειγμα μόνο για να αποδείξει το καλύτερο που μπορεί να γίνει με Atomics + mutex + condvar, AFAIK. θέση () και περιμένετε () εκτελεί μια lockfree compare_exchange, και μόνο αν πρέπει, να κλειδώσει το mutex.

Ωστόσο, μετά το () δεν lockfree. Και ακόμη χειρότερα, θα μπορούσε να αποκλειστεί από την αναμονή () που κλείδωσε την mutex και πήρε προκαταλαμβάνεται.

Για λόγους απλούστευσης, θα εφαρμοστεί μόνο post_one () και wait_one_for (Διάρκεια), αντί των υστέρων (int) και wait_for (int, Διάρκεια). Επίσης, υποθέτω δεν-πλαστά-αφύπνισης, που δεν έχει υποσχεθεί από το πρότυπο.

class semaphore //provides acquire release memory ordering for the user
{
private:
    using mutex_t = std::mutex;
    using unique_lock_t = std::unique_lock<mutex_t>;
    using condvar_t = std::condition_variable;
    using counter_t = int;

    std::atomic<counter_t> atomic_count_; 
    mutex_t mutex_;
    condvar_t condvar_;
    counter_t posts_notified_pending_;
    counter_t posts_unnotified_pending_;
    counter_t waiters_running_;
    counter_t waiters_aborted_pending_;

public:
    void post_one()
    {
        counter_t start_count = atomic_count_.fetch_add(+1, mo_acq_rel);
        if (start_count < 0) {
            unique_lock_t lock(mutex_);
            if (0 < waiters_running_) {
                ++posts_notified_pending_;
                condvar_.notify_one();
            }
            else {
                if (0 == waiters_aborted_pending_) {
                    ++posts_unnotified_pending_;
                }
                else {
                    --waiters_aborted_pending_;
                }
            }
        }
    }

    template< typename Duration >
    bool wait_one_for(Duration timeout)
    {
        counter_t start_count = atomic_count_.fetch_add(-1, mo_acq_rel);
        if (start_count <= 0) {
            unique_lock_t a_lock(mutex_);

            ++waiters_running_;
            BOOST_SCOPE_EXIT(&waiters_running_) {
                --waiters_running_;
            } BOOST_SCOPE_EXIT_END

            if( ( 0 == posts_notified_pending_ ) && ( 0 < posts_unnotified_pending_ ) ) {
                --posts_unnotified_pending_;
                return true;
            }
            else {

                auto wait_result = condvar_.wait_for( a_lock, timeout);
                switch (wait_result) {
                case std::cv_status::no_timeout: {
                    --posts_notified_pending_;
                    return true;
                } break;
                case std::cv_status::timeout: {

                    counter_t abort_count = atomic_count_.fetch_add(+1, mo_acq_rel);
                    if (abort_count >= 0) {
                        /*too many post() already increased a negative atomic_count_ and will try to notify, let them know we aborted. */
                        ++waiters_aborted_pending_;
                    }

                    return false;
                } break;
                default: assert(false); return false;
                }
            }
        }
        return true;
    }


    bool try_wait_one()
    {
        counter_t count = atomic_count_.load( mo_acquire );
        while (true) {
            if (count <= 0) {
                return false;
            }
            else if (atomic_count_.compare_exchange_weak(count, count-1, mo_acq_rel, mo_relaxed )) {
                return true;
            }
        }
    }
};
Δημοσιεύθηκε 08/11/2018 στις 00:11
πηγή χρήστη
Σε άλλες γλώσσες...                            


1 απαντήσεις

ψήφοι
2

Ναι, μπορείτε να το κάνετε αυτό για όσο διάστημα το λειτουργικό σας σύστημα διαθέτει το κατάλληλο «πάρκο» και «unpark» μηχανισμού, η οποία δεν απαιτεί τη λήψη μια κλειδαριά για unpark. Πάρκο αναφέρεται σε επιτρέπει ένα νήμα για να πάει για ύπνο (κλείδωμα OS) και unpark αναφέρεται σε ξυπνήσει αυτό το νήμα.

Είστε ήδη κοντά με ατομικό μετρητή σας και condvar προσέγγιση. Το πρόβλημα είναι ότι η condvar ένα mutex που απαιτείται ως μέρος της σημασιολογίας. Έτσι πρέπει να εγκαταλείψει condvars και να πάει λίγο χαμηλότερο επίπεδο. Κατ 'αρχάς, θα πρέπει να συσκευάσετε όλα το κράτος, όπως η τρέχουσα αξία σηματοφόρο, εάν υπάρχουν σερβιτόροι (και ενδεχομένως πόσοι wwaiters), σε ατομική τιμή, και να χειριστείτε αυτό ατομικά με συγκρίνουν-και-ανταλλαγής. Αυτό αποτρέπει αγώνες που θα προκύψει, εάν είχατε αυτές ως ξεχωριστές αξίες.

Στη συνέχεια, μπορείτε να σχεδιάσετε ένα διάγραμμα κατάσταση δείχνει όλες τις πιθανές καταστάσεις του σηματοφόρος, με άκρες για όλες τις πιθανές μεταβατικές καταστάσεις (π.χ., το «δεν σερβιτόροι» κατάσταση θα μεταβεί στο «ναι σερβιτόροι» κατάσταση, όταν ένας σερβιτόρος έρχεται). Μπορείτε να εφαρμόσουν όλες τις μεταβάσεις με συγκρίνουν-και-ανταλλαγής, και κάθε φορά που δεν θα πρέπει να υπολογίσει εκ νέου τη μετάβαση, δεδομένου ότι μπορεί να έχουν αλλάξει!

Στη συνέχεια, το μόνο που χρειάζεται για την υλοποίηση της δέσμευσης. Στα Windows θα πρέπει να χρησιμοποιήσετε Εκδηλώσεις - είτε αυτόματη είτε χειροκίνητη επαναφορά. Και οι δύο έχουν πλεονεκτήματα και τις ιδιορρυθμίες τους, και υπάρχουν περισσότεροι από ένας τρόπος για να δέρμα αυτή η γάτα. Για παράδειγμα, μπορείτε πιθανώς να το πάρετε για να συνεργαστεί με ένα μόνο γεγονότα κοινόχρηστα εκδήλωση και αυτόματη επαναφορά.

Ωστόσο, εδώ είναι ένα σκαρίφημα ενός μηχανισμού που χρησιμοποιούν ένα αντικείμενο σερβιτόρος ανά-νήμα σε μια κλειδαριά ελεύθερη ουρά. Η σηματοφόρο αποτελείται από ατομικά χειραγωγείται λέξη ελέγχου, και μια λίστα με κλειδαριά-free με τύπο στοιχείου waiter_nodeή στοίβα ή ό, τι off-the-shelf ταυτόχρονη λίστα-όπως πράγμα που θέλετε να χρησιμοποιήσετε.

Θα υποθέσουμε ότι κάθε νήμα έχει ένα αντικείμενο waiter_node που περιέχει ένα μόνο εγχειρίδιο αντικείμενο επαναφορά Event. Αυτό θα μπορούσε να δημιουργηθεί μια φορά και αποθηκεύονται σε TLS (ίσως το πιο αποδοτικό), ή κατανέμονται σε πρώτη ζήτηση κάθε φορά που μια αναμονή χρειάζεται να συμβεί και de διατεθεί όταν η αναμονή γίνεται.

Αυτό είναι το βασικό περίγραμμα:

Περιμένετε

  • Εάν η σηματοφόρος είναι διαθέσιμη (θετικό), CAS για να το μειώσετε και να συνεχίσει.
  • Αν το σηματοφόρος δεν είναι διαθέσιμη (μηδέν), το νήμα καλεί ResetEventαπό μόνο του waiter_nodeκαι στη συνέχεια ωθεί το συμβάν στη λίστα σερβιτόρος, ελέγχει ότι η αξία sem εξακολουθεί να είναι μηδέν και στη συνέχεια καλεί WaitForObjectσε το είναι waiter_node. Όταν αυτός επιστρέφει, ξεκινήστε τη ρουτίνα αναμονή πάνω από την κορυφή.

Θέση

  • Αυξήσετε τη λέξη ελέγχου. Pop ένα waiter_node, αν υπάρχουν, και να καλέσει SetEventσε αυτό.

Υπάρχουν όλα τα είδη των «φυλών» εδώ, όπως ένα waiter_nodeπου έσκασε με μια postλειτουργία πριν από το νήμα αναμονής κοιμάται ακόμα και σε αυτό, αλλά θα πρέπει να είναι καλοήθεις.

Υπάρχουν πολλές παραλλαγές ακόμη και σε αυτή την σερβιτόρος ουρά με βάση το σχεδιασμό. Για παράδειγμα, μπορείτε να ενσωματώσετε τη λίστα «κεφάλι» και η λέξη ελέγχου έτσι ώστε να είναι το ίδιο πράγμα. Στη συνέχεια, η waitδεν χρειάζεται να διπλασιάσει ελέγξετε την σηματοφόρος καταμέτρηση δεδομένου ότι η λειτουργία ώθησης επαληθεύει την σηματοφόρος κατάσταση την ίδια στιγμή. Μπορεί επίσης να εφαρμόσει «άμεση απώθηση», όπου το postνήμα σης δεν αυξάνει τη λέξη ελέγχου σε όλα, αν υπάρχουν σερβιτόροι, αλλά ακριβώς σκάει ένα και ξυπνάει με τις πληροφορίες που έχει αποκτήσει με επιτυχία το σηματοφόρος.

Στο Linux, θα αντικαταστήσει Eventμε futex. Είναι πιο εύκολο εκεί για να εφαρμόσει μια λύση «μόνο futex» καθώς futexεπιτρέπει μια ατομική επιχείρηση check-και-μπλοκ στο εσωτερικό του πυρήνα που αποφεύγει πολλά από τους αγώνες που ενέχει η Eventλύση. Έτσι, ένα βασικό σκίτσο είναι μια λέξη ελέγχου, και να σας κάνει μεταβάσεις σας ατομικά με CAS, και στη συνέχεια, χρησιμοποιώντας ένα futex()με το FUTEX_WAITνα κάνει ένα δεύτερο έλεγχο της λέξης ελέγχου και μπλοκάρει ατομικά (αυτό το ατομικό check-και-ύπνου είναι η δύναμη της futex).

Απαντήθηκε 09/11/2018 στις 16:10
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more