Αλγόριθμος κρυφής μνήμης

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

  • Ο πιο αποτελεσματικός αλγόριθμος προσωρινής αποθήκευσης θα ήταν να απορρίπτονται πάντα οι πληροφορίες που δεν θα χρειαστούν για το μεγαλύτερο χρονικό διάστημα στο μέλλον. Αυτό το βέλτιστο αποτέλεσμα αναφέρεται ως βέλτιστος αλγόριθμος του Belady ή αλγόριθμος του μάντη. Δεδομένου ότι είναι γενικά αδύνατο να προβλεφθεί πόσο μακριά στο μέλλον θα χρειαστούν πληροφορίες, αυτό δεν είναι γενικά εφαρμόσιμο στην πράξη. Το πρακτικό ελάχιστο μπορεί να υπολογιστεί μόνο μετά από πειραματισμό και μπορεί κανείς να συγκρίνει την αποτελεσματικότητα του πραγματικά επιλεγμένου αλγορίθμου κρυφής μνήμης με το βέλτιστο ελάχιστο.
  • Least Recently Used (LRU): διαγράφει πρώτα τα στοιχεία που χρησιμοποιήθηκαν λιγότερο πρόσφατα. Αυτός ο αλγόριθμος απαιτεί την παρακολούθηση του τι χρησιμοποιήθηκε πότε. Αυτό είναι δαπανηρό αν κάποιος θέλει να διασφαλίσει ότι ο αλγόριθμος απορρίπτει πάντα το λιγότερο πρόσφατα χρησιμοποιημένο στοιχείο. Οι γενικές υλοποιήσεις αυτής της τεχνικής απαιτούν τη διατήρηση "bit ηλικίας" για τις γραμμές cache και την παρακολούθηση της γραμμής cache "Least Recently Used" με βάση τα bit ηλικίας. Σε μια τέτοια υλοποίηση, κάθε φορά που χρησιμοποιείται μια γραμμή cache, η ηλικία όλων των άλλων γραμμών cache αλλάζει. Ο LRU είναι στην πραγματικότητα μια οικογένεια αλγορίθμων προσωρινής αποθήκευσης με μέλη όπως: 2Q των Theodore Johnson και Dennis Shasha και LRU/K των Pat O'Neil, Betty O'Neil και Gerhard Weikum.
  • Πιο πρόσφατα χρησιμοποιημένο (MRU): Αυτός ο αλγόριθμος διαγράφει πρώτα τα πιο πρόσφατα χρησιμοποιημένα στοιχεία. Αυτός ο μηχανισμός προσωρινής αποθήκευσης χρησιμοποιείται συνήθως για προσωρινές μνήμες βάσεων δεδομένων.
  • Ψευδο-LRU (PLRU): Υπάρχουν ορισμένες περιπτώσεις όπου η LRU είναι πολύ δύσκολο να εφαρμοστεί. Σε τέτοιες περιπτώσεις μπορεί να είναι αρκετό να γνωρίζουμε ότι στις περισσότερες περιπτώσεις, ένα από τα λιγότερο πρόσφατα χρησιμοποιημένα στοιχεία διαγράφεται. Ο αλγόριθμος PLRU μπορεί να χρησιμοποιηθεί εκεί, επειδή χρειάζεται μόνο ένα bit ανά στοιχείο cache για να λειτουργήσει.
  • 2-way set associative: για κρυφές μνήμες υψηλής ταχύτητας CPU όπου ακόμη και η PLRU είναι πολύ αργή. Η διεύθυνση ενός νέου στοιχείου χρησιμοποιείται για τον υπολογισμό μιας από τις δύο πιθανές θέσεις στην κρυφή μνήμη όπου επιτρέπεται να τοποθετηθεί. Η LRU από τις δύο απορρίπτεται. Αυτό απαιτεί ένα bit ανά ζεύγος γραμμών κρυφής μνήμης, για να δηλωθεί ποια από τις δύο χρησιμοποιήθηκε λιγότερο πρόσφατα.
  • Κρυφή μνήμη άμεσης χαρτογράφησης: για τις κρυφές μνήμες CPU με τις υψηλότερες ταχύτητες, όπου ακόμη και οι συσχετιστικές κρυφές μνήμες 2 κατευθύνσεων είναι πολύ αργές. Η διεύθυνση του νέου στοιχείου χρησιμοποιείται για τον υπολογισμό της μίας θέσης στην κρυφή μνήμη όπου επιτρέπεται να πάει. Ό,τι υπήρχε πριν απορρίπτεται.
  • Λιγότερο συχνά χρησιμοποιούμενη (LFU): Η LFU μετράει πόσο συχνά χρειάζεται ένα στοιχείο. Αυτά που χρησιμοποιούνται λιγότερο συχνά απορρίπτονται πρώτα.
  • Adaptive Replacement Cache (ARC): εξισορροπεί συνεχώς μεταξύ LRU και LFU, για να βελτιώνει το συνδυασμένο αποτέλεσμα.
  • Αλγόριθμος προσωρινής αποθήκευσης πολλαπλών ουρών (MQ): (από τους Y. Zhou J.F. Philbin και Kai Li).

Άλλα πράγματα που πρέπει να λάβετε υπόψη:

  • Αντικείμενα με διαφορετικό κόστος: κρατήστε αντικείμενα που είναι ακριβό να αποκτηθούν, π.χ. εκείνα που χρειάζονται πολύ χρόνο για να αποκτηθούν.
  • Αντικείμενα που καταλαμβάνουν περισσότερη προσωρινή μνήμη: Αν τα αντικείμενα έχουν διαφορετικά μεγέθη, η κρυφή μνήμη μπορεί να θέλει να απορρίψει ένα μεγάλο αντικείμενο για να αποθηκεύσει πολλά μικρότερα.
  • Αντικείμενα που λήγουν με το χρόνο: (π.χ. μια προσωρινή μνήμη ειδήσεων, μια προσωρινή μνήμη DNS ή μια προσωρινή μνήμη προγράμματος περιήγησης ιστού). Ο υπολογιστής μπορεί να απορρίψει στοιχεία επειδή έχουν λήξει. Ανάλογα με το μέγεθος της κρυφής μνήμης μπορεί να μην απαιτείται περαιτέρω αλγόριθμος προσωρινής αποθήκευσης για την απόρριψη στοιχείων.

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

Ποιες θέσεις μνήμης μπορούν να αποθηκευτούν στην cache από ποιες θέσεις cacheZoom
Ποιες θέσεις μνήμης μπορούν να αποθηκευτούν στην cache από ποιες θέσεις cache

Ερωτήσεις και απαντήσεις

Ερ: Τι είναι ο αλγόριθμος προσωρινής αποθήκευσης;


A: Ένας αλγόριθμος κρυφής μνήμης είναι ένας αλγόριθμος που χρησιμοποιείται για τη διαχείριση μιας κρυφής μνήμης ή μιας ομάδας δεδομένων. Αποφασίζει ποιο στοιχείο θα πρέπει να διαγραφεί από την κρυφή μνήμη όταν αυτή γεμίσει.

Ε: Τι είναι το ποσοστό επιτυχίας;


Α: Το ποσοστό επιτυχίας περιγράφει πόσο συχνά μπορεί να εξυπηρετηθεί ένα αίτημα από την κρυφή μνήμη.

Ε: Τι περιγράφει η καθυστέρηση;


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

Ε: Τι είναι ο βέλτιστος αλγόριθμος του Belady;


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

Ερ: Πώς λειτουργεί ο LRU (Least Recently Used);


Α: Η LRU διαγράφει πρώτα τα στοιχεία που χρησιμοποιήθηκαν λιγότερο πρόσφατα και απαιτεί την παρακολούθηση του τι χρησιμοποιήθηκε πότε με τη χρήση "bit ηλικίας" για κάθε γραμμή cache και την παρακολούθηση του ποια χρησιμοποιήθηκε λιγότερο πρόσφατα με βάση τα bit ηλικίας. Κάθε φορά που χρησιμοποιείται μια γραμμή κρυφής μνήμης, οι ηλικίες όλων των άλλων γραμμών κρυφής μνήμης αλλάζουν ανάλογα.

Ερ: Πώς λειτουργεί το Most Recently Used (MRU);



Α: Το MRU διαγράφει πρώτα τα πιο πρόσφατα χρησιμοποιημένα στοιχεία και αυτός ο μηχανισμός προσωρινής αποθήκευσης χρησιμοποιείται συνήθως για τις κρυφές μνήμες των βάσεων δεδομένων.

Ε: Ποιοι άλλοι αλγόριθμοι υπάρχουν για τη διατήρηση της συνοχής της κρυφής μνήμης;


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

AlegsaOnline.com - 2020 / 2023 - License CC3