Υλοποίηση μηχανισμού υπολογισμού Miss Ratio καμπυλών σε περιβάλλοντα διαχωρισμένης μνήμης

Abstract

Αντικείμενο της διπλωματικής εργασίας αποτελεί η μελέτη του μοντέλου Memory Disaggregation (μοντέλο διαχωρισμένης μνήμης) ως μια υποσχόμενη προσέγγιση για καταλληλότερη διαχείριση των πόρων μνήμης στο Cloud. Συγκεκριμένα, επεκτείναμε το σύστημα FluidMem με την ανάπτυξη ενός αλγορίθμου που υπολογίζει αποστάσεις επαναχρησιμοποίησης σε σελίδες διεργασιών ή εικονικών μηχανημάτων για προσβάσεις που ανιχνεύει ο μηχανισμός σελιδοποίησης του FluidMem. Ο μηχανισμός σελιδοποίησης που παρέχει το FluidMem κρίθηκε ως κατάλληλη διεπαφή επί της οποίας μπορεί να ληφθεί η προαναφερθείσα μετρική διότι είναι υλοποιημένος σε επίπεδο χρήστη και συνεπώς δεν απαιτούνται τροποποιήσεις στον πυρήνα του λειτουργικού συστήματος. Οι αποστάσεις επαναχρησιμοποίησης λαμβάνονται έπειτα από αίτημα για έναρξη της λήψης του αποτυπώματος μνήμης για μια διεργασία που επιβλέπει το FluidMem και αφορά όλες τις προσβάσεις σε σελίδες της διεργασίας που ανιχνεύει το FluidMem από την απαρχή του αιτήματος έως το ακόλουθο αίτημα τέλους. Τα αποτελέσματα του αποτυπώματος της μνήμης της διεργασίας κατά το συγκεκριμένο χρονικό διάστημα μπορούν έπειτα να διέλθουν από ένα στάδιο επεξεργασίας από το οποίο θα προκύψουν (i) το Ιστόγραμμα Αποστάσεων Επαναχρησιμοποίησης (Reuse Distance Histogram) και (ii) η Miss Ratio Καμπύλη (MRC) της διεργασίας.

Η μέθοδος που εφαρμόσαμε, συνιστά έναν non-intrusive τρόπο που μας παρέχει ικανότητα εκτίμησης της Ενεργά Χρησιμοποιούμενης Μνήμης (WSS) για μεγέθη που μπορούν να είναι και μικρότερα της αρχικής μνήμης που εκχωρείται στα εικονικά μηχανήματα. Το ελάχιστο μέγεθος του WSS που είμαστε σε θέση να ανιχνεύσουμε, εξαρτάται αποκλειστικά και μόνο από το μέγεθος του resizable LRU Buffer του FluidMem, και δεν έχει σχέση με το μέγεθος της μνήμης που αποδόθηκε στο εικονικό μηχάνημα κατά την έναρξή του. Επίσης, μας επιτρέπει να λάβουμε αποφάσεις κατάλληλης αυξομείωσης του μεγέθους του LRU Buffer, αλλά και να προσθέτουμε απομακρυσμένη μνήμη στα εικονικά μηχανήματα, όπου υπάρχει ανάγκη.

Ο αλγόριθμος που προτείνεται αποτελεί μια κομψή υλοποίηση του αλγορίθμου αναζήτησης δέντρων του Olken με αξιοποίηση AVL δέντρων για την αναπαράσταση της στοίβας. Εισάγει πολυπλοκότητα $O(NlogM)$, δεδομένου ότι $N$ είναι ο αριθμός των συνολικών προσβάσεων σε σελίδες που ανιχνεύει το FluidMem και $Μ$ οι μοναδικές προσβάσεις.

Επίσης, το παρατηρούμενο overhead του αλγορίθμου είναι της τάξης του 15\%, και θεωρείται αρκετά μικρό ώστε να αντισταθμίζεται από τα οφέλη που προκύπτουν κατά τη γνώση του WSS των διεργασιών.