Lokalitätseigenschaft
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
Es wird dabei zwischen der zeitlichen und örtlichen Lokalität unterschieden.
- Zeitliche Lokalität: In einem gewissen Zeitabschnitt wird mit einem relativ kleinen Bereich der gesamten Befehls- oder Datenmenge gearbeitet.
- Örtliche Lokalität: Befehls- oder Datenzugriffe finden auf einen 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
Eine daraus resultierende Überlegung führt bei der Entwicklung von Betriebssystemen dazu, dass Speicherseiten, auf die zuletzt vor längerer Zeit zugegriffen wurde, eher ausgelagert werden, zu Gunsten jüngerer Seiten.
Im Compilerbau muss dabei beachtet werden, dass durch die Verwendung eines Caches diese Lokaliätseigenschaften genutzt werden können.