Ατομικές πράξεις σε

Σχετικά με την έννοια Ατομικές πράξεις

Μια μεμονωμένη εντολή μπορεί να μοιάζει με μία αδιαίρετη πράξη, ενώ δεν είναι καθόλου κάτι τέτοιο. Πάρε για παράδειγμα την πρόσθεση του πέντε σε μια τιμή στη μνήμη:

add qword [rel counter], 5

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

1. ανάγνωση της τρέχουσας τιμής από τη μνήμη·
2. τροποποίηση αυτής της τιμής σε έναν καταχωρητή, προσθέτοντας πέντε σε αυτήν·
3. εγγραφή του αποτελέσματος πίσω.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

Αυτό είναι ένα συνηθισμένο μοτίβο που ονομάζεται read-modify-write (RMW).

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

Ωστόσο, οι σύγχρονοι επεξεργαστές σπάνια έχουν έναν μόνο πυρήνα, και οι εφαρμογές συχνά τρέχουν σε πολλούς πυρήνες ταυτόχρονα, χωρίς κάποια σειρά ανάμεσά τους. Όταν τρέχουν πολλοί πυρήνες την ίδια ακριβώς στιγμή, ένας άλλος πυρήνας μπορεί να διαβάσει ή να γράψει το counter μέσα σε αυτό το παράθυρο, μετά τη φόρτωση αυτού του πυρήνα και πριν την αποθήκευσή του. Δύο νήματα φορτώνουν το καθένα την ίδια παλιά τιμή, προσθέτουν το καθένα πέντε, και αποθηκεύουν το καθένα το αποτέλεσμά τους. Έγιναν δύο προσθέσεις, αλλά η τιμή μετακινήθηκε μόνο κατά πέντε. Μια ενημέρωση χάθηκε σιωπηλά.

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

Δεν εκτίθεται κάθε τιμή με αυτόν τον τρόπο. Κάθε νήμα έχει τους δικούς του καταχωρητές και τη δική του στοίβα, οπότε μια τιμή που βρίσκεται σε έναν καταχωρητή, ή μια τοπική μεταβλητή στη στοίβα ενός νήματος, είναι αποκλειστική για αυτό το νήμα και δεν μπορεί να υποστεί ανταγωνισμό. Μόνο η μνήμη που μοιράζονται τα νήματα, όπως το counter παραπάνω, χρειάζεται προστασία.

Το x86-64 προσφέρει ένα σύνολο εντολών για να λύσει αυτό το πρόβλημα, κάνοντας μια εντολή αδιαίρετη. Συμπεριφέρεται σαν ένα ενιαίο σύνολο όχι μόνο για τον πυρήνα που την εκτελεί, αλλά και για κάθε άλλον πυρήνα. Μια πράξη που μένει συνεκτική, που κανένας άλλος πυρήνας δεν μπορεί να τη διασπάσει, ονομάζεται ατομική.

Ατομική ανταλλαγή

Η εντολή xchg ανταλλάσσει δύο τελεστέους. Ο τελεστέος προορισμού γίνεται ίσος με την προηγούμενη τιμή του τελεστέου πηγής, ενώ ο τελεστέος πηγής γίνεται ίσος με την προηγούμενη τιμή του τελεστέου προορισμού. Νοητικά, μπορεί να ιδωθεί σαν δύο εντολές mov που συμβαίνουν ταυτόχρονα.

Όπως συνήθως, μπορεί να χρησιμοποιηθεί με δύο τελεστέους καταχωρητών ή με έναν τελεστέο μνήμης και έναν τελεστέο καταχωρητή:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

Όταν χρησιμοποιείται με τελεστέο μνήμης, η xchg είναι πάντα ατομική. Ο επεξεργαστής επιβάλλει κλείδωμα στη θέση για όλη τη διάρκεια, τον ίδιο μηχανισμό που χρησιμοποιεί το πρόθεμα lock για άλλες εντολές, όπως περιγράφεται στη συνέχεια.

Το πρόθεμα lock

Ο πιο συνηθισμένος τρόπος για να γίνει μια εντολή ατομική στο x86-64 είναι να προσθέσεις το πρόθεμα lock. Συγχωνεύει την ανάγνωση, την τροποποίηση και την εγγραφή σε ένα αδιαίρετο βήμα. Αυτό σημαίνει ότι ο πυρήνας κρατά τη μνήμη αποκλειστικά καθ' όλη τη διάρκεια της διαδικασίας, οπότε κανένας άλλος πυρήνας δεν μπορεί να διαβάσει ή να γράψει αυτή τη θέση στο ενδιάμεσο.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

Το lock λειτουργεί μόνο όταν ο προορισμός είναι μνήμη, και μόνο σε εντολές που διαβάζουν, τροποποιούν και γράφουν αυτή τη μνήμη:

1. αριθμητικές πράξεις, όπως add, sub, inc, dec, neg·
2. πράξεις bit, όπως and, or, xor, not·
3. οι πράξεις bit bts, btr, btc·
4. κάποιες άλλες ειδικές εντολές, όπως οι xadd και cmpxchg, που περιγράφονται παρακάτω.

Σε οποιαδήποτε άλλη εντολή, όπως μια απλή mov, το πρόθεμα είναι άκυρο και ο επεξεργαστής προκαλεί σφάλμα μη έγκυρου κωδικού λειτουργίας. Μια μεμονωμένη φόρτωση ή μια μεμονωμένη αποθήκευση δεν χρειάζεται πρόθεμα: μια προσπέλαση με φυσική στοίχιση είναι από μόνη της ατομική.

Ατομικές πράξεις bit

Ανάμεσα στις εντολές που μπορούν να κλειδωθούν, οι έλεγχοι bit ταιριάζουν φυσικά με το spinlock στο τέλος αυτού του κειμένου. Κάθε μία από τις bts, btr και btc αντιγράφει ένα επιλεγμένο bit στη σημαία μεταφοράς και μετά το θέτει, το καθαρίζει ή το αντιστρέφει. Με το πρόθεμα lock αυτό γίνεται read-modify-write ενός bit: το bit αλλάζει ατομικά, και το CF αναφέρει την προηγούμενη τιμή του.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

Όταν μια πράξη θέσης βρίσκει το bit ήδη θέσιμο, αυτό σημαίνει ότι ένα άλλο νήμα το διεκδίκησε πρώτο. Αυτή είναι μια εκδοχή ενός bit από τη διεκδίκηση σημαίας που κάνει η xchg για μια ολόκληρη λέξη.

Ανταλλαγή και πρόσθεση

Μια απλή lock add ενημερώνει τη μνήμη αλλά πετάει την παλιά τιμή. Συχνά η παλιά τιμή είναι ακριβώς αυτό που θέλουμε, για παράδειγμα για να δώσουμε σε κάθε νήμα έναν ξεχωριστό αριθμό εισιτηρίου.

Η εντολή xadd (το x από το exchange) επιστρέφει την προηγούμενη τιμή ενώ προσθέτει. Γράφει το άθροισμα στον προορισμό και αφήνει την αρχική τιμή του προορισμού στον καταχωρητή πηγής.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

Με το πρόθεμα lock αυτό είναι ένα ατομικό fetch-and-add. Όταν το τρέχουν πολλά νήματα στον ίδιο μετρητή, κάθε κλήση επιστρέφει μια διαφορετική παλιά τιμή.

Όπως με το lock add, ο μετρητής καταλήγει στον ακριβή αριθμό των κλήσεων. Ωστόσο, σε αντίθεση με το lock add, επιστρέφεται και κάθε ενδιάμεση τιμή, μία σε κάθε καλούντα.

Η πηγή μπορεί να είναι οποιοσδήποτε καταχωρητής γενικού σκοπού, και το πλάτος του τελεστέου κυμαίνεται από ένα byte έως ένα quadword. Η πρόσθεση μιας αρνητικής τιμής μετατρέπει την ίδια εντολή σε fetch-and-subtract.

Σύγκριση και ανταλλαγή

Η xadd προσθέτει και η xchg αντικαθιστά, αλλά καμία από τις δύο δεν μπορεί να κάνει τη νέα τιμή να εξαρτάται από την τρέχουσα και να την εφαρμόσει μόνο αν τίποτα δεν άλλαξε στο μεταξύ. Αυτή η υπό συνθήκη ενημέρωση είναι αυτό που παρέχει η cmpxchg, η σύγκριση και ανταλλαγή, και είναι η πιο γενική από αυτές τις πρωταρχικές πράξεις.

Η cmpxchg dest, src χρησιμοποιεί τον rax ως σιωπηρό συσσωρευτή και τον συγκρίνει με το dest:

• Αν dest == rax, τότε dest = src και ZF = 1.
• Αν dest != rax, τότε rax = dest και ZF = 0.

Ο συσσωρευτής ακολουθεί το μέγεθος του τελεστέου: al για ένα byte, μετά ax, eax και rax για τις μεγαλύτερες μορφές.

Πρόσεξε ότι το dest ενημερώνεται μόνο όταν είναι ίσο με την αναμενόμενη τιμή, που έχει προηγουμένως φορτωθεί στον rax. Αυτή η ισότητα διασφαλίζει ότι το dest κρατά ακόμη την τιμή από την οποία υπολογίστηκε η νέα, οπότε μια ενημέρωση που βασίζεται σε μια παρωχημένη ανάγνωση δεν εφαρμόζεται ποτέ. Αυτό κάνει την cmpxchg το δομικό στοιχείο για μια ατομική ενημέρωση, γνωστή και ως compare-and-swap (CAS):

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

Αυτός ο βρόχος επανάληψης είναι η καρδιά των ενημερώσεων χωρίς κλείδωμα. Το παράθυρο ανάμεσα στην ανάγνωση και στη σύγκριση και ανταλλαγή είναι ακριβώς το σημείο όπου ένα άλλο νήμα μπορεί να παρέμβει, και η cmpxchg το πιάνει αρνούμενη να αποθηκεύσει μια τιμή που υπολογίστηκε από παρωχημένη ανάγνωση.

Μια λεπτομέρεια αξίζει να την ξέρεις. Η cmpxchg ελέγχει ότι η τιμή είναι ίση με αυτή που διαβάστηκε, όχι ότι η θέση δεν αγγίχτηκε ποτέ. Αν ένα άλλο νήμα μετακινήσει την τιμή από το A στο B και πίσω στο A μέσα στο παράθυρο, η ανταλλαγή πετυχαίνει ακόμα, παρόλο που ο κόσμος άλλαξε από κάτω της.

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

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

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

Υπάρχει μια εντολή διπλού πλάτους που ονομάζεται cmpxchg16b, η οποία είναι σημασιολογικά ίδια με την cmpxchg αλλά λειτουργεί σε 16 byte ταυτόχρονα και μπορεί να χρησιμοποιηθεί σε αυτή την περίπτωση. Δεν έχει τελεστέο πηγής, αλλά χρησιμοποιεί το rcx:rbx ως τιμή αντικατάστασης. Ο μόνος τελεστέος της είναι μια θέση μνήμης με στοίχιση 16 byte. Αυτή η εντολή χρησιμοποιεί επίσης το rdx:rax ως συσσωρευτή, αντί για μόνο τον rax.

Διάταξη μνήμης

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

Η έννοια branchless-code εισήγαγε την ιδέα ότι ένας σύγχρονος πυρήνας δεν εκτελεί τις εντολές μία προς μία. Κρατά πολλές σε εξέλιξη ταυτόχρονα και προχωρά μπροστά όπου μπορεί. Αυτό σημαίνει ότι μια εγγραφή μπορεί να γίνει ορατή στους άλλους πυρήνες αργότερα από ό,τι υπονοεί το πρόγραμμα, ενώ εντολές μετά από αυτήν έχουν ήδη προχωρήσει.

Το x86-64 διατηρεί μια ισχυρή διάταξη μνήμης ανάμεσα σε συνηθισμένες φορτώσεις και αποθηκεύσεις, έτσι ώστε σε κάθε πυρήνα:

1. μια φόρτωση δεν αναδιατάσσεται ποτέ μετά από μια μεταγενέστερη φόρτωση·
2. μια αποθήκευση δεν αναδιατάσσεται ποτέ μετά από μια μεταγενέστερη αποθήκευση·
3. μια φόρτωση δεν αναδιατάσσεται ποτέ μετά από μια μεταγενέστερη αποθήκευση.

Η μόνη δυνατή αναδιάταξη είναι μια αποθήκευση να φαίνεται ότι ολοκληρώνεται μετά από μια μεταγενέστερη φόρτωση διαφορετικής διεύθυνσης.

Μια εντολή με πρόθεμα lock, ή μια xchg με τελεστέο μνήμης, είναι ένα πλήρες φράγμα: τίποτα δεν φαίνεται να περνά από πάνω του προς καμία κατεύθυνση. Γι’ αυτό αρκούν για να εξασφαλίσουν πλήρη διάταξη στις περισσότερες περιπτώσεις.

Ο μηχανισμός πίσω από τη μία αναδιάταξη που επιβιώνει είναι ο buffer αποθήκευσης. Για να συνεχίσει να προχωρά μπροστά, ένας πυρήνας τοποθετεί κάθε αποθήκευση σε αυτόν τον buffer και αφήνει μεταγενέστερες εντολές να προχωρήσουν πριν η αποθήκευση φτάσει στη μνήμη που μπορούν να δουν οι άλλοι πυρήνες. Μια εγγραφή που ακολουθείται από μια ανάγνωση διαφορετικής θέσης μπορεί επομένως να φανεί εκτός σειράς: η εγγραφή μπορεί να κάθεται ακόμη στον buffer ενώ η μεταγενέστερη ανάγνωση προχωρά. Αυτό το μοντέλο, όπου τα πάντα είναι διατεταγμένα εκτός από αυτό το κενό εγγραφής-και-μετά-ανάγνωσης, ονομάζεται συνολική διάταξη αποθηκεύσεων.

Αυτό το μόνο κενό αρκεί για να σπάσει μια χειραψία «αποθήκευση και μετά έλεγχος». Αν δύο νήματα γράψουν το καθένα τη δική του σημαία και μετά διαβάσουν του άλλου, και οι δύο αναγνώσεις μπορούν να επιστρέψουν χωρίς η σημαία να έχει τεθεί, επειδή καμία από τις δύο αποθηκεύσεις δεν έχει αφήσει ακόμη τον buffer αποθήκευσής της. Η εντολή mfence κλείνει το κενό αδειάζοντας τον buffer αποθήκευσης: κάθε εγγραφή πριν από αυτήν γίνεται ορατή πριν από οποιαδήποτε ανάγνωση μετά από αυτήν.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

Υπάρχουν επίσης δύο στενότερα φράγματα:

• Η sfence διατάσσει τις εγγραφές μεταξύ τους και έχει σημασία κυρίως με τις μη χρονικές αποθηκεύσεις ροής·
• Η lfence διατάσσει τις αναγνώσεις.

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

Αυτές οι εγγυήσεις έχουν ονόματα που ξεπερνούν το x86. Μια πράξη έχει διάταξη απόκτησης όταν καμία μεταγενέστερη προσπέλαση δεν μπορεί να φανεί ότι μετακινείται πριν από αυτήν, και διάταξη απελευθέρωσης όταν καμία προγενέστερη προσπέλαση δεν μπορεί να φανεί ότι μετακινείται μετά από αυτήν. Στο x86 κάθε φόρτωση είναι μια απόκτηση, κάθε αποθήκευση είναι μια απελευθέρωση, και μια εντολή με πρόθεμα lock, ή μια xchg με μνήμη, είναι και τα δύο ταυτόχρονα.

Αναμονή με περιστροφή και pause

Οι εντολές που θέτουν μια σημαία και ταυτόχρονα επιστρέφουν την προηγούμενη κατάστασή της είναι γνωστές ως test-and-set. Μπορούν να χρησιμοποιηθούν ως βάση για ένα spinlock, εξασφαλίζοντας σε έναν πυρήνα αποκλειστική πρόσβαση σε κάποιο μέρος του κώδικα.

Αυτός είναι ο γενικός αλγόριθμος, χρησιμοποιώντας την εντολή xchg με μια δυαδική σημαία:

1. Η σημαία ξεκινά ως 0.
2. Για να αποκτήσει το κλείδωμα, ένας πυρήνας ανταλλάσσει την τιμή της σημαίας με 1.
3. Αν η τιμή που επιστρέφεται είναι 1, αυτό σημαίνει ότι το κλείδωμα το κρατά ένας άλλος πυρήνας. Ο τρέχων πυρήνας τότε περιμένει και προσπαθεί να αποκτήσει ξανά το κλείδωμα.
4. Αν η τιμή που επιστρέφεται είναι 0, αυτό σημαίνει ότι το κλείδωμα ήταν ελεύθερο. Η xchg το έχει τώρα θέσει σε 1, και οι άλλοι πυρήνες θα περιμένουν μέχρι αυτός ο πυρήνας να το απελευθερώσει.
5. Μόλις ο τρέχων πυρήνας τελειώσει τη δουλειά του, η ενημέρωση της σημαίας με 0 απελευθερώνει το κλείδωμα.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

Η εντολή pause στον βρόχο αναμονής δεν αλλάζει αυτό που υπολογίζει ο κώδικας. Υποδεικνύει στον επεξεργαστή ότι πρόκειται για αναμονή με περιστροφή. Η CPU μπορεί τότε να μειώσει την κατανάλωση ενέργειας του νήματος που περιμένει και να παραχωρήσει χρόνο σε ένα αδελφό νήμα που μοιράζεται τον ίδιο πυρήνα. Ένας βρόχος περιστροφής χωρίς pause είναι ακόμα σωστός, απλώς σπάταλος.

Πρόσεξε ότι σε ένα test-and-set, μια εντολή όπως η xchg θέτει πάντα τη σημαία, ακόμη και όταν ήταν ήδη θέσιμη. Αυτό σημαίνει ότι αποκτά αποκλειστική πρόσβαση στη μνήμη σε κάθε περιστροφή, ακόμη και όταν είναι πιθανό το κλείδωμα να κρατείται ακόμα.

Υπάρχει μια παραλλαγή αυτού του αλγορίθμου, γνωστή ως test-and-test-and-set, που πρώτα ελέγχει (διαβάζει) τη σημαία για να δει αν είναι ήδη θέσιμη. Έπειτα επιχειρεί το test-and-set (την xchg σε αυτή την περίπτωση) μόνο όταν το κλείδωμα φαίνεται ελεύθερο:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

Μόλις το νήμα τελειώσει τη δουλειά του, μπορεί να απελευθερώσει το κλείδωμα με μια απλή αποθήκευση του 0 χρησιμοποιώντας mov. Δεν χρειάζεται τίποτα περισσότερο από μια mov, επειδή στο x86-64 οι φορτώσεις και οι αποθηκεύσεις δεν αναδιατάσσονται ποτέ μετά από μια μεταγενέστερη αποθήκευση. Μια αποθήκευση που δεν προσπερνά ποτέ τις προσπελάσεις πριν από αυτήν λέγεται ότι έχει διάταξη απελευθέρωσης, και στο x86 κάθε απλή αποθήκευση τη φέρει.