Lokalitätseigenschaft

Mit Lokalitätseigenschaft (auch Lokalitätsprinzip oder Lokalitätseffekt, englisch locality of reference) wird in der Informatik eine Eigenschaft typischer Computerprogramme bezeichnet. Sie besagt, dass die Wahrscheinlichkeit sehr hoch ist, dass Daten, die gerade benutzt werden, auch in naher Zukunft wieder benötigt werden. Man unterscheidet zwischen zeitlicher und räumlicher Lokalität. Die Tatsache, dass sich Programme und Prozesse relativ stationär in Zeit und Raum verhalten, kann auf verschiedene Weise genutzt werden, um die Datenverarbeitungsleistung zu verbessern.

Zeitliche Lokalität

Die zeitliche Lokalität besagt, dass Adressbereiche, auf die zugegriffen wird, auch in naher Zukunft mit hoher Wahrscheinlichkeit wieder benutzt werden. Im zeitlichen Verlauf erfolgt also relativ häufig der Zugriff auf eine gleiche Speicheradresse. Diese Eigenschaft kann in allen Ebenen der Speicherhierarchie ausgenutzt werden, um Speicherbereiche möglichst schnell im Zugriff zu halten. So können beispielsweise Speicherbereiche, auf die erst kürzlich zugegriffen wurde, in einem Cache-Speicher verwaltet werden. Der Cache ist ein relativ kleiner Hochgeschwindigkeitsspeicher, der häufig benötigte Daten zwischen der CPU und dem Arbeitsspeicher puffert.[1]

Räumliche Lokalität

Die räumliche Lokalität besagt, dass nach einem Zugriff auf einen Adressbereich mit hoher Wahrscheinlichkeit der nächste Zugriff auf eine Adresse in unmittelbarer Nachbarschaft erfolgt. Im zeitlichen Verlauf werden also immer wieder Speicheradressen angesprochen, die sehr nahe beieinander liegen. Dies kann man ausnutzen, indem man bei einem Speicherzugriff auch gleich die benachbarten Adressbereiche in die nächste Hierarchiestufe bringt.[2]

Ursachen

Bereits 1968 stellte Peter J. Denning fest, dass sich der Arbeitsbereich (englisch working set) eines Prozesses im Laufe eines Programmes nur sehr langsam verändert.[3]

Die Ursache für die Lokalitätseigenschaft liegt in der Häufigkeit, mit der Schleifen als Konstrukte imperativer Programmiersprachen auftreten[4]:

  • In Schleifen wird zunächst immer wieder auf dieselben Adressen von Befehlen zurückgegriffen, und zwar umso häufiger, je kürzer der Schleifen-Code ist. Die Befehle selbst ändern sich ja nicht, nur die Adressen der jeweils benötigten Daten (Operanden).
  • Beim Abarbeiten von Schleifen wird zum anderen meist die indizierte Adressierung zum Aufruf von Daten (Operanden) herangezogen, die ihrerseits üblicherweise in aufeinander folgenden Speicherplätzen abgelegt sind.

Literatur

  • Andrew S. Tanenbaum: Moderne Betriebssysteme. 3., aktualisierte Auflage. Pearson Studium: München u. a., 2009, insb. S. 263 und 1137.
  • Peter Mandl: Grundkurs Betriebssysteme. Architekturen, Betriebsmittelverwaltung, Synchronisation, Prozesskommunikation. Springer: Wiesbaden, 4. Aufl., 2014.
  • Jürgen Heidepriem: Prozessinformatik 1. Grundzüge der Informatik. Oldenbourg: München, 2000.

Einzelnachweise

  1. ↑ Mandl: Grundkurs Betriebssysteme. 4. Aufl., 2014, S. 215.
  2. ↑ Mandl: Grundkurs Betriebssysteme. 4. Aufl., 2014, S. 216.
  3. ↑ Peter J. Denning: The working set model for program behavior. In: Communications of the ACM Volume 11, Issue 5, 1968, S. 323–333. (Online)
  4. ↑ Heidepriem: Prozessinformatik 1. 2000, S. 192.