Table of Contents
II. Computer Organization and Architecture – 15%
C. Memories and their hierarchies
1. Performance, implementation, and management
a. Definition: Because fast memory is significantly more expensive that slow memory, you cannot load up your system with fast memory. So, you must have different speeds of memory. Managing that memory is a sophisticated operation.
2. Cache, main, and secondary storage
a. Definition: In older systems, the processor would only talk directly to main memory. This memory was too small and lost data when it lost power, so we created secondary storage like hard drives.
b. Definition: Main memory is often so slow and so large (which makes it slower to find anything), that system performance is horrible. Cache memory is smaller and faster. It helps speed up transfers between main memory and the processor.
c. We use cache to speed up access to instructions and data by the processor. Cache is usually very fast, low capacity memory that is between the processor and the main physical memory. Modern processors have level 1 cache that is very small and on the same die as the processor, and level 2 cache that is in the same package as the processor but larger than the level 1 cache. Since cache cannot typically hold all of the data and instructions that we want access to, we try to make sure that the ones we will want next are in the cache. When the processor makes a memory request, it should first make sure that the requested information is not in cache. Addressing for cache is usually rather simple. Since main memory is a binary multiple of the cache memory, we can use a system called direct mapping. For example, if the address of the information in memory is 101011010101, then the address location in cache might be 0101. In this system, when we put information from memory into cache, then we only place it into the cache location that has the same ending address as the original location. Each cache location has an additional field that appends the suffix of the original memory location to what is currently stored in the cache location. The advantage to this system is processor accesses to cache are extremely fast. If the processor first had to lookup the cache location, then it would add overhead to every memory access. The disadvantage is that multiple memory locations can only be mapped to one cache location. If it impossible to have two conflicting locations in cache at the same time. So, when the processor performs a memory access, it first looks in cache. It starts by looking at the cache location that corresponds with the memory location. If the information is not in cache (a cache miss), then the information is read from memory and placed into cache. Why place it into cache? As programs execute, when a piece of data or instruction is used it is often reused very soon afterwards (think of loops). We call this temporal locality. The processor might also copy the information near the requested memory address into cache. Why copy information that has not been explicitly requested? Programs are largely linear, meaning that most programs run an instruction and then run the very next instruction (instead of jumping to a different location in the program). So, we often copy the next memory address to cache to take advantage of this spatial locality.
d. An alternative to direct mapping is set-associative cache. Instead of forcing the information to only one cache location, we allow it to go to any of a set of locations. However, we still do not let the information be placed in any location at all (that is fully associative cache). Since the location of the information in cache is still related to the location of the information in physical memory, we gain a performance advantage over a fully associative cache.
3. Virtual memory, paging, and segmentation
a. Definition: Virtual memory is secondary storage that is logically treated as main memory. Performance can be terrible, but it is often necessary to present the illusion of a very large main memory space. Since the processor cannot talk directly to secondary storage, it is necessary to move information between the main memory and the virtual memory (on the secondary storage). If you move a fixed amount of information each time, it is called paging. Segmentation allows you to move variable amounts.
b. Virtual memory is the system that allows us to have memory space on secondary storage (the hard drive). In most situations, it is not possible to fit all instructions and data into physical memory. Especially, when we are running multiple programs or manipulating large data structures (databases). Virtual memory uses almost identical technology and techniques as caching. However, we have developed a different vernacular for describing virtual memory.
c. We move instructions and data to the disk in units called pages. We tend to make pages large to take advantage of spatial locality (Think KB instead of bytes). When a requested page is not in main (physical) memory, and we must retrieve it from the disk (virtual memory), then we call it a page fault. Keep in mind that a disk access can take up to one million instruction cycles. This fact creates a massive penalty for page faults.
d. Since page faults are very expensive, we use a fully associative paging table, we sometimes track the least recently used (LRU) pages in physical memory, and we mark unchanged pages so that we do not have to write them back to disk.
e. We might also track the frequency of use of each page and page the least frequently used (LFU) pages back to disk first. In a fully associative page table system, we store the actual location for every possible virtual page. In the page table, we only store the base address of the page in memory. When a program wants to access a location in memory, it will construct the call using the virtual page and the offset from the base of that page. Look at question #18 on the practice test. The job makes the call [0, 514]. The 0 refers to the virtual page, not the actual page. The virtual memory system translates the 0 into 3 using the page table. Since each page has 1024 locations, the actual base address is 3072. Now add the offset (514). The actual address is 3586.
