Please enable JavaScript.

Coggle requires JavaScript to display documents.

The locality principle (Applications (Design of caches, Spam blocking,…

- - - - D(x,t)
        
        Measures the distance from a processor to an object x at
        time t
        
        Object x is in the locality set at time t if the distance is less than a threshold: D(x,t) <= T.
    - - Temporal
        
        Measures the time since prior reference or access time within a network
      - Spatial
        
        Measures hops in a network or address separation in a sequence
      - Cost
        
        Measures any nondecreasing accumulation of cost since prior reference
- - - - Manages memory with multithreading and multitasking
      - Simulated a large main memory within a small real one
      - Doubled or tripled programmer productivity
    - - It was sensitive to the choice of replacement algorithm
        
        The ideal page to replace is the one that will not be used again for the longest time
      - It was sensitive to the ways compilers grouped code on to pages
      - Prone to thrashing
        
        Near-complete collapse of system throughput due to heavy paging
        
        Spent most of its time resolving page faults and little running the CPU
    - - It was transformed to a robust technology that regulated itself dynamically and optimized throughput without user intervention
      - Introduced the concept of addresses naming values, not memory locations
    - - Shed no light on the dynamic partitions used in multiprogrammed virtual memory systems
      - No notion of a dynamic, intrinsic memory demand that would tell which pages were essential and which were replaceable
  - - - Each computing device of the real system is represented as a server with a queue
      - The server processes a job for a random service time and then sends it to another server according to a probability distribution for the inter-server transition
      - There is a server representing the CPU and a server representing the paging disk
    - - The thrashing curve is actually the system doing the best it can as the paging-disk bottleneck worsens with increasing load
- - - - Later called overlays
  - - - Set of pages used during a fixed-length sampling window in the immediate past
      - W(t,T)
        
        Set of pages referenced in the virtual time of length T preceding time t
    - - The window had to be measured in the virtual time of the process
        
        Time as the number of memory references made
      - Could be measured by periodically reading and resetting the use bits in a page table
  - - - Criteria for load controls that prevented thrashing
        
        L=S
        
        Monitoring the mean lifetime L between page faults and
        adjusting load to keep that value near the paging disk service time S
        
        Not reliable
        
        Knee criterion
        
        The system adjusted load to keep the observed lifetime near the knee lifetime -- was consistently more reliable, even though knee lifetime was not close to S
        
        Not reliable. It is not possible to know the knee lifetime without running the program to completion.