Βραδιά πρεμιέρας

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

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

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

Αυτό είναι ένα συνηθισμένο μοτίβο που ονομάζεται ανάγνωση-τροποποίηση-εγγραφή (RMW).

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

Ωστόσο, οι σύγχρονες CPU σπάνια έχουν έναν μόνο πυρήνα, και οι εφαρμογές συχνά εκτελούνται σε πολλούς πυρήνες ταυτόχρονα, χωρίς καμία σειρά μεταξύ τους. Όταν πολλοί πυρήνες εκτελούνται την ίδια ακριβώς στιγμή, ένας άλλος πυρήνας μπορεί να διαβάσει ή να γράψει το 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

Ο πιο συνηθισμένος τρόπος για να γίνει μια εντολή ατομική στο 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, που περιγράφονται παρακάτω.

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

Μια απλή 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, επιστρέφεται και κάθε ενδιάμεση τιμή, από μία σε κάθε καλούντα.

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

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

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

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

Σημείωσε ότι το 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 το πιάνει αυτό αρνούμενη να αποθηκεύσει μια τιμή που υπολογίστηκε από παρωχημένη ανάγνωση.

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

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

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

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

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

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

Μια εντολή με πρόθεμα 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 είναι ακόμα σωστός, απλώς σπάταλος.

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