Entwurf und Evaluierung eines adaptiven Ersetzungsalgorithmus für den Diskcache eines Hierarchischen-Speicher-Management-Systems

Abstract

Dok. 2 besteht aus einem ISO-9660-CD-Image und enthält den Sourcecode und die Eingabedaten der Simulation. ********************************* Das Ziel dieser Arbeit bestand darin, einen adaptiven Ersetzungsalgorithmus für den Diskcache eines Hierarchischen Speicher Management Systems zu entwickeln, der die besonderen Eigenschaften des Diskcache ausnutzt und das Ersetzungsverhalten verbessert. Vorgestellt wird der Objekt-LRU Ersetzungsalgorithmus (OLRU). Der OLRU Ersetzungsalgorithmus unterscheidet sich von bisherigen Ersetzungsalgorithmen, indem er die Attribute der Cacheobjekte nutzt, um die Ersetzung zu beeinflußen. Eine der Besonderheiten des Diskcache besteht in der Speicherung ganzer Dateien. Durch die unterschiedliche Größe der Dateien bedingt, wird eine Kombinationen von Objekten ersetzt. Dabei werden die Attribute der Objekte durch eine Bewertungsfunktion zusammengefaßt, die es erlaubt, die am besten geeignete Kombinationen von Objekten zu ersetzen. Um eine Adaption des OLRU Algorithmus zu ermöglichen, wurde eine online Optimierung der Parameter der Bewertungsfunktion in den Algorithmus integriert. Die Optimierung erfolgt unter Verwendung eines Genetischen Algorithmus. Der OLRU Algorithmus wurde innerhalb einer Simulationsumgebung eingesetzt. Durch die Verwendung von zwei Zugriffmustern (Traces), die in realen Systemen aufgezeichnet wurden, konnten die Ergebnisse der Simulation evaluiert werden. Die Simulationen zeigen, daß der OLRU Ersetzungsalgorithmus die Leistung des Diskcache deutlich verbessern kann, da er gleichzeitig die Trefferquoten steigert und auch den Ressourcenbedarf bei der Wiederbeschaffung der Objekte senkt. Der Vergleich mit dem am häufigsten eingesetzten online Ersetzungsalgorithmus LRU zeigt, das die mit dem OLRU Algorithmus erzielten Trefferquoten einer deutlichen Vergrößerung des Cachevolumens entsprechen.

Dok. 2 is an ISO-9660-CD-image and contains the sourcecode and the simulation input data. ********************************* The object of this thesis was the design of an adaptable replacement algorithm to be used for the disk cache of a hierarchical storage management system. Thus the Object LRU replacement algorithm (OLRU) is introduced. The OLRU replacement algorithm distinguishes itself from known replacement algorithms, by using properties of cache objects to influence replacement. One of the characteristics of a disk cache is the storage of whole files. Based on the different sizes of files it is necessary to replace a combination of files. The best combination of files can be determined, by using a weighting function that relies on the properties of cache objects, and then be replaced. To enable the adaptability of the OLRU algorithm an online optimization is applied to the parameters of the weighting function. The optimization itself is carried out by a genetic algorithm. The OLRU algorithm was evaluated by simulation. To sets of traces, recorded on real systems, were used to drive the simulation. The simulations proof the ability of the OLRU algorithm to increase the performance of the disk cache. Using OLRU hit rates are increased as well as overall resource usage is decreased. By comparing the results of the OLRU algorithm to the widely used LRU algorithm, a significant increase in the efficiency of cache usage can be shown.