Locality of reference

Some facts about the history of the "Principle of locality" and what it means. http://denninginstitute.com/pjd/PUBS/CACMcols/cacmJul05.pdf

14 flashcards · Computer Science · by initBasti

1. What was a major reason for the superiority of the concept of virtual memory?

   Mainly because it increased the programmer's productivity by a lot.

2. How was the "Locality of reference" discovered?

   While observing working sets of processes, the tendency for clustering of references was noticed. At that time programmers planned their usage of subsets of pages and the time phases of usage. But that behavior was also noticed when it was not planned. Each program has a unique pattern, because of loops, modules and grouping of data in structures. So the locality of reference is a consequence out of the way we humans solve problems ("Divide and Conquer" for example).

3. Which problem was particularly noticeable before the locality of reference was discovered?

   The performance was very sensitive to the combination of: The choice of the replacement algorithm The way the compiler grouped code into pages The multi-programming level (thrashing)

4. What are areas where the "locality of reference" is part of the design?

   Used for: processor caches disk controller caches storage hierarchies network interfaces database systems search engines web browsers Information hiding principle

5. With the concept of CPU addressing hardware-translated-addresses into memory locations via a page table and all instructions + data fitting into a single address space on disk, the OS picked a page to be replaced at the next page fault, when RAM was full. Which two performance problems did arise out of that situation?

   constantly translating addresses to locations Replacing loaded pages with pages from disk

6. What is a solution to the problem of having to constantly translate addresses to memory locations?

   Storing copies of recently used page table entries, inside a small associative memory. Also known as address cache or Translation Lookaside Buffer.

7. Why is the replacement of loaded pages a problematic topic?

   Because the time it takes to load something from disk is much slower than a CPU instruction cycle. -> Adds a significant delay to the job completion time. (Especially in the past where disks were even slower)

8. What kind of thrashing occurred in multi-programming systems?

   The thrashing was triggered by a multi-programming level that was too high. The increment of the multi-programming level pushed all working sets of loaded programs into a state of insufficiency. Thrashing is the collapse of through-output of a system, caused by either a working set of process not fitting into main memory or into the TLB and also by memory locations competing for cache lines. (multi-programming is parallel processing of multiple processes by a single processor, in which small pa…

9. Which algorithm emerged as the best performer out of the extensive tests at the Watson laboratory?

   the LRU (least recently used) algorithm

10. What defines a process working set? (The current memory pages required by the process)

    Set of pages used during a fixed-length sampling window in the immediate past.

11. How can a process working set be measured?

    By periodically reading and resetting the used bits in the page table and measuring the virtual time as the number of memory references (in order to not be confused by interrupts).

12. What was the solution to thrashing?

    A feedback control mechanism that limits the multi-programming level by holding back processes in a holding queue when their working set did not fit into main memory.

13. Definition of locality

    Distance from an processor to an object x at time t D(x,t) Object x is in the locality set if : D(x,t) < T, where T is the Threshold. Distance can have three meanings: temporal distance (time gap to a reference) spatial distance (number of hops or addresses inbetween) cost distance (non-decreasing function of time since last reference)

14. Locality of reference , was discovered in the early development of virtual memory while trying to find a solution to thrashing of a systems through output . A major way to benefit from this principle is to use caches in different parts of a computer system.