Locality property

from Wikipedia, the free encyclopedia

With locality property (also locality principle or locality effect , English locality of reference ) a property of typical computer programs is designated in computer science . It says that there is a very high probability that data that is currently in use will also be needed again in the near future. A distinction is made between temporal and spatial locality. The fact that programs and processes are relatively stationary in time and space can be used in various ways to improve data processing performance.

Temporal locality

The temporal locality means that address areas that are accessed will most likely be used again in the near future. In the course of time, the same memory address is accessed relatively frequently . This property can be used at all levels of the storage hierarchy in order to keep storage areas accessible as quickly as possible. For example, memory areas that were only recently accessed can be managed in a cache memory. The cache is a relatively small, high-speed memory that buffers frequently used data between the CPU and the main memory .

Spatial locality

The spatial locality means that after an access to an address range, there is a high probability that the next access to an address will take place in the immediate vicinity. Over time, memory addresses that are very close to one another are addressed again and again. You can take advantage of this by bringing the neighboring address areas to the next hierarchy level when accessing the memory.

causes

As early as 1968, Peter J. Denning noticed that the working set of a process only changes very slowly in the course of a program.

The cause of the locality property lies in the frequency with which loops appear as constructs of imperative programming languages :

  • In loops, the same address of commands is used again and again, and the more frequently the shorter the loop code. The commands themselves do not change, only the addresses of the required data (operands).
  • When processing loops, on the other hand, the indexed addressing is usually used to call up data (operands), which in turn are usually stored in successive memory locations.

literature

  • Jürgen Heidepriem: Process Informatics 1. Basics of Informatics. Oldenbourg: Munich, 2000.
  • Peter Mandl: Basic course operating systems. Architectures, resource management, synchronization, process communication. Springer: Wiesbaden, 4th edition, 2014.
  • Andrew S. Tanenbaum : Modern Operating Systems. 3rd, updated edition. Pearson studies: Munich a. a., 2009, especially pp. 263 and 1137.

Individual evidence

  1. ^ Mandl: Basic course operating systems. 4th ed., 2014, p. 215.
  2. ^ Mandl: Basic course operating systems. 4th ed., 2014, p. 216.
  3. ^ Peter J. Denning: The working set model for program behavior. In: Communications of the ACM Volume 11, Issue 5, 1968, pp. 323-333. ( Online )
  4. ↑ Heidepriem: Process Informatics 1. 2000, p. 192.