1 1 Memory Management!2 Goals of this Lecture!• Help you learn about:"• The memory hierarchy"• Spatial and temporal locality of reference"• Caching, at multiple levels"• Virtual memory"• … and thereby …"• How the hardware and OS give application pgms:"• The illusion of a large contiguous address space"• Protection against each other"Virtual memory is one of the most important concepts in systems programming"2 3 Motivation for Memory Hierarchy!• Faster storage technologies are more costly"• Cost more money per byte"• Have lower storage capacity"• Require more power and generate more heat"• The gap between processing and memory is widening"• Processors have been getting faster and faster"• Main memory speed is not improving as dramatically"• Well-written programs tend to exhibit good locality"• Across time: repeatedly referencing the same variables"• Across space: often accessing other variables located nearby "Want the speed of fast storage at the cost and capacity of slow storage. Key idea: memory hierarchy!"4 Simple Three-Level Hierarchy!• Registers"• Usually reside directly on the processor chip"• Essentially no latency, referenced directly in instructions"• Low capacity (e.g., 32-512 bytes)"• Main memory"• Around 100 times slower than a clock cycle"• Constant access time for any memory location"• Modest capacity (e.g., 512 MB-2GB)"• Disk"• Around 100,000 times slower than main memory"• Faster when accessing many bytes in a row"• High capacity (e.g., 200 GB)"3 5 Widening Processor/Memory Gap!• Gap in speed increasing from 1986 to 2000"• CPU speed improved ~55% per year"• Main memory speed improved only ~10% per year"• Main memory as major performance bottleneck"• Many programs stall waiting for reads and writes to finish"• Changes in the memory hierarchy"• Increasing the number of registers"• 8 integer registers in the x86 vs. 128 in the Itanium"• Adding caches between registers and main memory"• On-chip level-1 cache and off-chip level-2 cache"An Example Memory Hierarchy!registers!on-chip L1!cache (SRAM)!main memory!(DRAM)!local secondary storage!(local disks)!Larger, !slower, !and !cheaper !(per byte)!storage!devices!remote secondary storage!(tapes, distributed file systems, Web servers)!Local disks hold files retrieved from disks on remote network servers.!Main memory holds disk !blocks retrieved from local !disks.!off-chip L2!cache (SRAM)!L1 cache holds cache lines retrieved from the L2 cache memory.!CPU registers hold words retrieved from L1 cache.!L2 cache holds cache lines retrieved from main memory.!L0:!L1:!L2:!L3:!L4:!L5:!Smaller,!faster,!and !costlier!(per byte)!storage !devices!4 7 Locality of Reference!• Two kinds of locality"• Temporal locality: recently referenced items are likely to be referenced in near future"• Spatial locality: Items with nearby addresses tend to be referenced close together in time."• Locality example"• Program data"• Temporal: the variable sum • Spatial: variable a[i+1] accessed soon after a[i] • Instructions"• Temporal: cycle through the for-loop repeatedly"• Spatial: reference instructions in sequence"sum = 0; for (i = 0; i < n; i++) sum += a[i]; return sum; 8 Locality Makes Caching Effective!• Cache"• Smaller, faster storage device that acts as a staging area "• … for a subset of the data in a larger, slower device"• Caching and the memory hierarchy"• Storage device at level k is a cache for level k+1"• Registers as cache of L1/L2 cache and main memory"• Main memory as a cache for the disk"• Disk as a cache of files from remote storage"• Locality of access is the key"• Most accesses satisfied by first few (faster) levels"• Very few accesses go to the last few (slower) levels "5 Caching in a Memory Hierarchy!0! 1! 2! 3!4! 5! 6! 7!8! 9! 10! 11!12! 13! 14! 15!Larger, slower, cheaper storage!device at level k+1 is partitioned!into blocks.!Data copied between levels in block-sized transfer units!9! 3!Smaller, faster, more expensive!device at level k caches a subset!of the blocks from level k+1!Level k:!Level k+1:!4!4! 10!10!10 Cache Block Sizes!• Fixed vs. variable size"• Fixed-sized blocks are easier to manage (common case)"• Variable-sized blocks make more efficient use of storage"• Block size"• Depends on access times at the level k+1 device"• Larger block sizes further down in the hierarchy"• E.g., disk seek times are slow, so disk pages are larger"• Examples"• CPU registers: 4-byte words"• L1/L2 cache: 32-byte blocks"• Main memory: 4 KB pages"• Disk: entire files"6 11 Cache Hit and Miss!• Cache hit"• Program accesses a block available in the cache"• Satisfy directly from cache"• E.g., request for “10”"• Cache miss"• Program accesses a block not available in the cache"• Bring item into the cache"• E.g., request for “13”"• Where to place the item?"• Which item to evict?"0! 1! 2! 3!4! 5! 6! 7!8! 9! 10! 11!12! 13! 14! 15!8!9! 14! 3!Level k:!Level k+1:!4!4!10!10!12 Three Kinds of Cache Misses!• Cold (compulsory) miss"• Cold misses occur because the block hasnʼt been accessed before"• E.g., first time a segment of code is executed"• E.g., first time a particular array is referenced"• Capacity miss"• Set of active cache blocks (the “working set”) is larger than cache"• E.g., manipulating a 1200-byte array within a 1000-byte cache"• Conflict miss"• Some caches limit the locations where a block can be stored"• E.g., block i must be placed in cache location (i mod 4)"• Conflicts occur when multiple blocks map to the same location(s)"• E.g., referencing blocks 0, 8, 0, 8, 0, 8, ... would miss every time"7 13 Cache Replacement!• Evicting a block from the cache"• New block must be brought into the cache"• Must choose a “victim” to evict"• Optimal eviction policy"• Evict a block that is never accessed again"• Evict the block accessed the furthest in the future!• Impossible to implement without knowledge of the future"• Using the past to predict the future"• Evict the “least recently used” (LRU) block"•
View Full Document
Unlocking...