Lokalitätseigenschaft

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Informatik wird mit Lokalitätseigenschaft (englisch: locality of reference) die beobachtbare Eigenschaft typischer Computerprogramme bezeichnet, in einem gewissen Zeitabschnitt nur auf einen relativ kleinen Bereich der gesamten Datenmenge zuzugreifen. Sie bildet die Basis für den Einsatz eines Caches.

Arten von Lokalitäten[Bearbeiten]

Es wird dabei zwischen der räumlichen und der zeitlichen Lokalität unterschieden.

  • Zeitliche Lokalität: In einem gewissen Zeitabschnitt wird mit einem relativ kleinen Bereich der gesamten Befehls- oder Datenmenge gearbeitet.
  • Räumliche Lokalität: Befehls- oder Datenzugriffe finden auf einem relativ kleinen Bereich des gesamten Adressraums statt.

Die Lokalitäten begründen sich auf folgende Beobachtung:

Die Befehle eines Programmes werden sequentiell ausgeführt, was lediglich durch im Quelltext vorkommende Verzweigungen unterbrochen wird. Nachfolgende Befehle werden also sehr wahrscheinlich ebenfalls verarbeitet. Verzweigungen finden dabei zu großen Teilen nur in Schleifen und Prozeduren statt, welche häufig mehrmals wiederholt ausgeführt werden. Verzweigungen zu entfernten Adressen, welche die Lokalität verletzen, sind dabei relativ selten.

Zudem führt das wiederholte Ausführen der gleichen Befehlsfolge zu einem erneuten Zugriff auf Programmdaten.

Weitere Auswirkungen[Bearbeiten]

Eine daraus resultierende Überlegung führt bei der Entwicklung von Betriebssystemen dazu, dass Speicherseiten, auf die zuletzt vor längerer Zeit zugegriffen wurde, zu Gunsten jüngerer Seiten, eher ausgelagert werden.

Im Compilerbau muss dabei beachtet werden, dass durch die Verwendung eines Caches diese Lokalitätseigenschaften genutzt werden können.